一致性哈希算法的理解

版權(quán)聲明： 本文由 一只博客 發(fā)表于?bloghome博客

文章鏈接：?https://www.bloghome.com.cn/user/cnn237111

關(guān)于一致性哈希算法，網(wǎng)上有很多博文都有講解。推薦2個(gè)。

http://blog.codinglabs.org/articles/consistent-hashing.html

http://blog.csdn.net/cywosp/article/details/23397179

總結(jié)一下：

1. 網(wǎng)上博文的例子都將hash值的結(jié)果定義在0 - 2³²-1，實(shí)際上也是非必要的，你可以設(shè)定的比這個(gè)范圍小，或者比這個(gè)范圍大，都是可以的，重要的是它是一個(gè)環(huán)。

   
   

2.一致性哈希并不保證節(jié)點(diǎn)被映射的均衡性，假設(shè)哈希值是均衡的，那么節(jié)點(diǎn)要被均衡的映射，就必須讓各個(gè)節(jié)點(diǎn)之間的距離相等，也就是說各個(gè)節(jié)點(diǎn)平分環(huán)的周長(zhǎng)。

3.當(dāng)存在故障節(jié)點(diǎn)后，一致性哈希并不保證故障節(jié)點(diǎn)上的值能通過算法恢復(fù)（除非已實(shí)現(xiàn)主備機(jī)制）

4.當(dāng)故障節(jié)點(diǎn)被移除，故障節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的壓力會(huì)增加（如果各個(gè)節(jié)點(diǎn)的壓力是均衡的，那么壓力增加1倍）。

5.當(dāng)插入新節(jié)點(diǎn)，一致性哈希算法并不能避免重新hash步驟，但是不需要把所有的數(shù)據(jù)都重新hash一遍，只需要hash一部分。這種方式將hash的范圍減到最小，僅僅是將新節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的一部分?jǐn)?shù)據(jù)，歸還給新節(jié)點(diǎn)。

6,當(dāng)哈希算法的值不均衡時(shí)，環(huán)上的各個(gè)節(jié)點(diǎn)的壓力也是不均衡的。可以采用添加虛擬節(jié)點(diǎn)的方式，使平衡?？梢栽跓狳c(diǎn)節(jié)點(diǎn)的后面，插入多個(gè)虛擬節(jié)點(diǎn)，一旦映射落到虛擬節(jié)點(diǎn)上，再通過其他的hash算法，映射到壓力較低的節(jié)點(diǎn)。采用的算法可以是簡(jiǎn)單粗暴，比如舉個(gè)栗子：

如下圖，在沒有虛擬節(jié)點(diǎn)的時(shí)候，假設(shè)由于hash算法的不均衡性，落在節(jié)點(diǎn)4和節(jié)點(diǎn)5的hash值特別多，勢(shì)必造成節(jié)點(diǎn)5的壓力比較大，而此時(shí)如果節(jié)點(diǎn)6和節(jié)點(diǎn)2的壓力有比較小，那么在節(jié)點(diǎn)4和節(jié)點(diǎn)5之間插入2個(gè)虛擬節(jié)點(diǎn)（節(jié)點(diǎn)a和節(jié)點(diǎn)b），根據(jù)一致性哈希的算法，節(jié)點(diǎn)a和節(jié)點(diǎn)5之間的hash值落到節(jié)點(diǎn)5上，節(jié)點(diǎn)a和節(jié)點(diǎn)b的hash值落在節(jié)點(diǎn)a上，節(jié)點(diǎn)b和節(jié)點(diǎn)4之間的hash落在節(jié)點(diǎn)b上。但是節(jié)點(diǎn)a和節(jié)點(diǎn)b是虛擬節(jié)點(diǎn)，因此可以強(qiáng)制的讓節(jié)點(diǎn)a映射到節(jié)點(diǎn)6，節(jié)點(diǎn)b強(qiáng)制映射到節(jié)點(diǎn)2，這樣，節(jié)點(diǎn)5的壓力會(huì)減輕，從而使得所有節(jié)點(diǎn)負(fù)載相對(duì)均衡。

以上是一些總結(jié)，如有不對(duì)，歡迎指出糾正。