亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

一致性哈希算法與Java實現

系統 2454 0
一致性哈希算法是分布式系統中常用的算法。比如,一個分布式的存儲系統,要將數據存儲到具體的節點上,如果采用普通的hash方法,將數據映射到具體的節點上,如key%N,key是數據的key,N是機器節點數,如果有一個機器加入或退出這個集群,則所有的數據映射都無效了,如果是持久化存儲則要做數據遷移,如果是分布式緩存,則其他緩存就失效了。

因此,引入了一致性哈希算法:

一致性哈希算法與Java實現

把數據用hash函數(如MD5),映射到一個很大的空間里,如圖所示。數據的存儲時,先得到一個hash值,對應到這個環中的每個位置,如k1對應到了圖中所示的位置,然后沿順時針找到一個機器節點B,將k1存儲到B這個節點中。

如果B節點宕機了,則B上的數據就會落到C節點上,如下圖所示:

一致性哈希算法與Java實現

這樣,只會影響C節點,對其他的節點A,D的數據不會造成影響。然而,這又會造成一個“雪崩”的情況,即C節點由于承擔了B節點的數據,所以C節點的負載會變高,C節點很容易也宕機,這樣依次下去,這樣造成整個集群都掛了。

為此,引入了“虛擬節點”的概念:即把想象在這個環上有很多“虛擬節點”,數據的存儲是沿著環的順時針方向找一個虛擬節點,每個虛擬節點都會關聯到一個真實節點,如下圖所使用:

一致性哈希算法與Java實現

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點,機器A負載存儲A1、A2的數據,機器B負載存儲B1、B2的數據,機器C負載存儲C1、C2的數據。由于這些虛擬節點數量很多,均勻分布,因此不會造成“雪崩”現象。

Java 實現:

  1. public class Shard<S>{ //S類封裝了機器節點的信息,如name、password、ip、port等
  2. private TreeMap<Long,S>nodes; //虛擬節點
  3. private List<S>shards; //真實機器節點
  4. private final int NODE_NUM= 100 ; //每個機器節點關聯的虛擬節點個數
  5. public Shard(List<S>shards){
  6. super ();
  7. this .shards=shards;
  8. init();
  9. }
  10. private void init(){ //初始化一致性hash環
  11. nodes= new TreeMap<Long,S>();
  12. for ( int i= 0 ;i!=shards.size();++i){ //每個真實機器節點都需要關聯虛擬節點
  13. final SshardInfo=shards.get(i);
  14. for ( int n= 0 ;n<NODE_NUM;n++)
  15. //一個真實機器節點關聯NODE_NUM個虛擬節點
  16. nodes.put(hash( "SHARD-" +i+ "-NODE-" +n),shardInfo);
  17. }
  18. }
  19. public SgetShardInfo(Stringkey){
  20. SortedMap<Long,S>tail=nodes.tailMap(hash(key)); //沿環的順時針找到一個虛擬節點
  21. if (tail.size()== 0 ){
  22. return nodes.get(nodes.firstKey());
  23. }
  24. return tail.get(tail.firstKey()); //返回該虛擬節點對應的真實機器節點的信息
  25. }
  26. /**
  27. *MurMurHash算法,是非加密HASH算法,性能很高,
  28. *比傳統的CRC32,MD5,SHA-1(這兩個算法都是加密HASH算法,復雜度本身就很高,帶來的性能上的損害也不可避免)
  29. *等HASH算法要快很多,而且據說這個算法的碰撞率很低.
  30. *http://murmurhash.googlepages.com/
  31. */
  32. private Longhash(Stringkey){
  33. ByteBufferbuf=ByteBuffer.wrap(key.getBytes());
  34. int seed= 0x1234ABCD ;
  35. ByteOrderbyteOrder=buf.order();
  36. buf.order(ByteOrder.LITTLE_ENDIAN);
  37. long m=0xc6a4a7935bd1e995L;
  38. int r= 47 ;
  39. long h=seed^(buf.remaining()*m);
  40. long k;
  41. while (buf.remaining()>= 8 ){
  42. k=buf.getLong();
  43. k*=m;
  44. k^=k>>>r;
  45. k*=m;
  46. h^=k;
  47. h*=m;
  48. }
  49. if (buf.remaining()> 0 ){
  50. ByteBufferfinish=ByteBuffer.allocate( 8 ).order(
  51. ByteOrder.LITTLE_ENDIAN);
  52. //forbig-endianversion,dothisfirst:
  53. //finish.position(8-buf.remaining());
  54. finish.put(buf).rewind();
  55. h^=finish.getLong();
  56. h*=m;
  57. }
  58. h^=h>>>r;
  59. h*=m;
  60. h^=h>>>r;
  61. buf.order(byteOrder);
  62. return h;
  63. }
  64. }

一致性哈希算法與Java實現


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美综合精品 | 九九精品成人免费国产片 | 婷婷狠狠 | 日韩美一区二区 | 亚洲一区二区中文字幕 | 亚洲综合一区二区三区四区 | 日本不卡免费在线 | 黄色男人的天堂 | 黄色成人在线 | 久久久精品久久久久特色影视 | 久久r热这里有精品视频 | 四虎影视国产在线观看精品 | 在线观看视频色 | 久久久99精品免费观看精品 | 一级一级18女人毛片 | 99九色| 久久久综合色 | 女人十六毛片 | 色午夜在线 | 中文字幕一区视频 | 天天碰天天操 | 不卡免费视频 | 欧美日韩亚洲国产精品 | 色综合久久综合网欧美综合网 | 天天做天天爱天天影视综合 | www.欧美成人 | 国产一区中文字幕 | 欧美videos粗暴高清性 | 国产大尺度福利视频在线观看 | 天天狠狠色噜噜 | 国产中的精品一区的 | 亚洲成人国产精品 | 天天做爽夜夜做爽 | 五月激情丁香婷婷综合第九 | 久久香蕉国产线看观看网站 | 国产精品美女一区二区三区 | 一级毛片成人午夜 | 免费成人小视频 | 日本一级在线播放线观看免 | 26uuu在线视频 | 99久久精品免费看国产四区 |