一致性Hash算法在1997年由麻省理工學(xué)院提出的一種分布式哈希（DHT）實(shí)現(xiàn)算法，設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)（Hot Spot）問題择葡，初衷和CARP十分相似。一致性Hash修正了CARP使用的簡單哈希算法帶來的問題剃氧，使得分布式哈希（DHT）可以在P2P環(huán)境中真正得到應(yīng)用敏储。

一致性Hash算法提出了在動態(tài)變化的Cache環(huán)境中，判定哈希算法好壞的四個定義：

1她我、平衡性（Balance）：平衡性是指哈希的結(jié)果能夠盡可能分布在所有的緩沖(Cache)中去虹曙，這樣可以使得所有的緩沖空間得到利用。很多哈希算法都能夠滿足這一條件番舆。

2酝碳、單調(diào)性（Monotonicity）：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中恨狈。哈希的結(jié)果應(yīng)該能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去疏哗，而不會映射到舊的緩沖集合中的其他緩沖區(qū)。

3禾怠、分散性（Spread）：在分布式環(huán)境中返奉，終端有可能看不到所有的緩沖，而只能看到其中的一部分吗氏。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上去芽偏，由于不同終端所見的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致弦讽，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中污尉。這種情況顯然是應(yīng)該避免的膀哲，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲到不同緩沖中去，降低了系統(tǒng)存儲的效率被碗。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度某宪。好的哈希算法應(yīng)該能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性锐朴。

4兴喂、負(fù)載（Load）：負(fù)載問題實(shí)際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中焚志，那么對于一個特定的緩沖區(qū)而言衣迷，也可能被不同的用戶映射到不同的內(nèi)容。與分散性一樣娩嚼，這種情況也是應(yīng)當(dāng)避免的蘑险，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

在分布式集群中岳悟，對機(jī)器的添加刪除佃迄，或者機(jī)器故障后自動脫落集群這些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法贵少，那么在有機(jī)器添加或者刪除后呵俏，很多原有的數(shù)據(jù)就無法找到了，這樣嚴(yán)重的違反了單調(diào)性原則滔灶。

解釋使用hash(object)%N普碎，其中N是指N個cache服務(wù)器/N個節(jié)點(diǎn)為啥不行：

如果N個cache服務(wù)器中編號為a的服務(wù)器故障了，需要把a(bǔ)從服務(wù)器群中移除录平，這個時候cache服務(wù)器的數(shù)量就變成了N-1臺麻车，那么所有對象(object)映射到cache服務(wù)器的計算公式就變成了hash(object)%N-1，對斗这，影響到了所有的對象與cache服務(wù)器的映射關(guān)系动猬，類似，由于訪問加重表箭，需要添加cache服務(wù)器赁咙，這時候cache服務(wù)器是N+1臺，映射公式就變成了hash(object)%N+1,這就意味著幾乎所有的cache都失效了免钻，對于服務(wù)器而言彼水，這是一場災(zāi)難，所有訪問都會直接沖向后臺服務(wù)器极舔。

接下來主要講解一下哈希算法是如何設(shè)計的：

環(huán)形Hash空間

按照常用的hash算法來將對應(yīng)的key哈希到一個具有2^{32次方個桶的空間中凤覆，即0~（2}32）-1的數(shù)字空間。現(xiàn)在我們可以將這些數(shù)字頭尾相連拆魏，想象成一個閉合的環(huán)形盯桦。如下圖

image

把數(shù)據(jù)(對象)通過一定的hash算法處理后映射到環(huán)上

現(xiàn)在我們將object1澡绩、object2、object3俺附、object4四個對象通過特定的Hash函數(shù)計算出對應(yīng)的key值，然后散列到hash換上溪掀。如下圖：

Hash(object1)=key1;Hash(object2)=key2;Hash(object3)=key3;Hash(object4)=key4;

image

將機(jī)器通過hash算法映射到環(huán)上

在采用一致性哈希算法的分布式集群中將新的機(jī)器加入事镣，其原理是通過使用與對象存儲一樣的Hash算法將機(jī)器也映射到換種（一般情況下對機(jī)器的hash計算是采用機(jī)器的IP或者唯一的別名作為輸入值），然后以順時針的方向計算揪胃，將所有對象存儲到離自己最近的機(jī)器中璃哟。

假設(shè)現(xiàn)在有NODE1,NODE2,NODE3三臺機(jī)器中，通過hash算法得到對應(yīng)的KEY值喊递，映射到環(huán)中随闪，其示意圖如下：

Hash（NODE1）=KEY1;Hash（NODE2）=KEY2;Hash（NODE3）=KEY3;

image

通過上圖可以看出對象與機(jī)器處于同一個哈希空間中骚勘，這樣按順時針轉(zhuǎn)動object1（對象）存儲到了NODE1（機(jī)器）中,object3（對象）存儲到了NODE2（機(jī)器）中,object2铐伴、object4（對象）存儲到了NODE3（機(jī)器）中。在這樣的部署環(huán)境中俏讹，hash環(huán)是不會變更的当宴，因此，通過算出對象的hash值就能快速的定位到對應(yīng)的機(jī)器中泽疆，這樣就能找到對象真正的存儲位置了户矢。

機(jī)器刪除與添加

普通hash求余算法最為不妥的地方就是在有機(jī)器的添加與刪除以后會造成大量的對象存儲位置的失效，這樣就大大的不滿足單調(diào)性了殉疼。下面來分析一下一致性哈希算法是如何處理的梯浪。

1、節(jié)點(diǎn)（機(jī)器）的刪除

  以上面的分布式集群為例瓢娜，如果NODE2出現(xiàn)故障被刪除了挂洛，那么按照順時針遷移的方法，object3將會被遷移到NODE3中恋腕，這樣僅僅是object3的映射位置發(fā)生了變化抹锄，其他的對象沒有任何的變動，如下圖：

image

2荠藤、節(jié)點(diǎn)（機(jī)器）的添加

 如果往集群中添加一個新的節(jié)點(diǎn)NODE4,通過對應(yīng)的Hash算法得到KEY4伙单，并映射到環(huán)中，如下圖：

image

通過按照順時針遷移的規(guī)則哈肖，那么object2被遷移到NODE4中吻育，其他對象還保持這原有的存儲位置。通過對節(jié)點(diǎn)的添加和刪除的分析淤井，一致性哈希算法在保持了單調(diào)性的同時布疼，還是數(shù)據(jù)的遷移達(dá)到了最小摊趾，這樣的算法對分布式集群來說非常合適的，避免了大量收數(shù)據(jù)遷移游两，減少了服務(wù)器的壓力砾层。

平衡性

根據(jù)上面的圖解分析，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性贱案，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由肛炮，因?yàn)槿鄙倭似胶庑浴Ｏ旅鎸⒎治鲆恢滦怨Ｋ惴ㄊ侨绾螡M足平衡性的宝踪。hash算法是不保證平衡性的侨糟，如上面只部署了NODE1和NODE3的情況(NODE2被刪除的圖)，object1存儲在NODE1中瘩燥，而object2秕重、object3、object4都存儲在NODE3中厉膀，這樣就造成了非常不平衡的狀態(tài)溶耘。在一致性哈希算法中，為了盡可能的滿足平衡性服鹅，其引入了虛擬節(jié)點(diǎn)汰具。

何為虛擬節(jié)點(diǎn)？虛擬節(jié)點(diǎn)（Virtual node）是實(shí)際節(jié)點(diǎn)（機(jī)器）在hash空間的復(fù)制品（replica）菱魔，一個實(shí)際節(jié)點(diǎn)對應(yīng)了若干個“虛擬節(jié)點(diǎn)”留荔，這個對應(yīng)個數(shù)也稱為“復(fù)制個數(shù)”，“虛擬節(jié)點(diǎn)”在hash空間中以hash值排列澜倦。

在上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例聚蝶，之前的對象在機(jī)器上的分布很不均衡，現(xiàn)在我們以2個副本（每個節(jié)點(diǎn)復(fù)制2個）為例藻治，這樣整個hash環(huán)就存在4個虛擬節(jié)點(diǎn)碘勉，最后對象映射的關(guān)系圖如下：

image

根據(jù)上圖可知對象的映射關(guān)系：object1->NODE1-1,object2->NODE1-2 ,object3->NODE3-2,object4->NODE3-1，通過虛擬節(jié)點(diǎn)的引入桩卵，對象的分布就比較均衡了验靡。那么在實(shí)際操作中，真正的對象查詢是如何工作的呢雏节？對象從hash到虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的轉(zhuǎn)換如下圖：

image

虛擬節(jié)點(diǎn)”的hash計算可以采用對應(yīng)節(jié)點(diǎn)的IP地址加數(shù)字后綴的方式胜嗓。例如假設(shè)NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點(diǎn)”前钩乍，計算 cache A 的 hash 值：

Hash(“192.168.1.100”);

引入“虛擬節(jié)點(diǎn)”后辞州，計算“虛擬節(jié)”點(diǎn)NODE1-1和NODE1-2的hash值：

Hash(“192.168.1.100#1”); // NODE1-1

Hash(“192.168.1.100#2”); // NODE1-2

參考：https://blog.csdn.net/cywosp/article/details/23397179/

       [http://www.reibang.com/p/e8fb89bb3a61](http://www.reibang.com/p/e8fb89bb3a61)