1致性哈希算法在1997年由麻省理工學院提出的1種散布式哈希（DHT）實現(xiàn)算法，設計目標是為了解決因特網(wǎng)中的熱門(Hot spot)問題，初衷和CARP10分類似。1致性哈希修正了CARP使用的簡 單哈希算法帶來的問題，使得散布式哈希（DHT）可以在P2P環(huán)境中真正得到利用。
1致性hash算法提出了在動態(tài)變化的Cache環(huán)境中，判定哈希算法好壞的4個定義：
1、平衡性(Balance)：平衡性是指哈希的結果能夠盡量散布到所有的緩沖中去，這樣可使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這1條件。
2、單調(diào)性(Monotonicity)：單調(diào)性是指如果已有1些內(nèi)容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結果應能夠保證原有已分配的內(nèi)容可以被映照到原本的或新的緩沖中去，而不會被映照到舊的緩沖集合中的其他緩沖區(qū)。
3、分散性(Spread)：在散布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的1部份。當終端希望通過哈希進程將內(nèi)容映照到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而致使哈希的結果不1致，終究的結果是相同的內(nèi)容被不同的終端映照到不同的緩沖區(qū)中。這類情況明顯是應當避免的，由于它致使相同內(nèi)容被存儲到不同緩沖中去，下降了系統(tǒng)存儲的效力。分散性的定義就是上述情況產(chǎn)生的嚴重程度。好的哈希算法應能夠盡可能避免不1致的情況產(chǎn)生，也就是盡可能下降分散性。
4、負載(Load)：負載問題實際上是從另外一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映照到不同的緩沖區(qū)中，那末對1個特定的緩沖區(qū)而言，也可能被不同的用戶映照為不同 的內(nèi)容。與分散性1樣，這類情況也是應當避免的，因此好的哈希算法應能夠盡可能下降緩沖的負荷。

在散布式集群中，對機器的添加刪除，或機器故障后自動脫離集群這些操作是散布式集群管理最基本的功能。如果采取經(jīng)常使用的hash(object)%N算法，那末在有機器添加或刪除后，很多原本的數(shù)據(jù)就沒法找到了，這樣嚴重的違背了單調(diào)性原則。接下來主要講授1下1致性哈希算法是如何設計的：

環(huán)形Hash空間
依照經(jīng)常使用的hash算法來將對應的key哈希到1個具有2^32次方個桶的空間中，即0~(2^32)⑴的數(shù)字空間中。現(xiàn)在我們可以將這些數(shù)字頭尾相連，想象成1個閉合的環(huán)形。以下圖

把數(shù)據(jù)通過1定的hash算法處理后映照到環(huán)上
現(xiàn)在我們將object1、object2、object3、object44個對象通過特定的Hash函數(shù)計算出對應的key值，然后散列到Hash環(huán)上。以下圖：

將機器通過hash算法映照到環(huán)上
在采取1致性哈希算法的散布式集群中將新的機器加入，其原理是通過使用與對象存儲1樣的Hash算法將機器也映照到環(huán)中（1般情況下對機器的hash計算是采取機器的IP或機器唯1的別名作為輸入值），然后以順時針的方向計算，將所有對象存儲到離自己最近的機器中。
假定現(xiàn)在有NODE1，NODE2，NODE33臺機器，通過Hash算法得到對應的KEY值，映照到環(huán)中，其示意圖以下：

通過上圖可以看出對象與機器處于同1哈希空間中，這樣按順時針轉(zhuǎn)動object1存儲到了NODE1中，object3存儲到了NODE2中，object2、object4存儲到了NODE3中。在這樣的部署環(huán)境中，hash環(huán)是不會變更的，因此，通過算出對象的hash值就可以快速的定位到對應的機器中，這樣就可以找到對象真實的存儲位置了。
機器的刪除與添加
普通hash求余算法最為不妥的地方就是在有機器的添加或刪除以后會照成大量的對象存儲位置失效，這樣就大大的不滿足單調(diào)性了。下面來分析1下1致性哈希算法是如何處理的。
1. 節(jié)點（機器）的刪除
以上面的散布為例，如果NODE2出現(xiàn)故障被刪除，那末依照順時針遷移的方法，object3將會被遷移到NODE3中，這樣僅僅是object3的映照位置產(chǎn)生了變化，其它的對象沒有任何的改動。以下圖：

2. 節(jié)點（機器）的添加
如果往集群中添加1個新的節(jié)點NODE4，通過對應的哈希算法得到KEY4，并映照到環(huán)中，以下圖：

通過按順時針遷移的規(guī)則，那末object2被遷移到了NODE4中，其它對象還保持這原本的存儲位置。通過對節(jié)點的添加和刪除的分析，1致性哈希算法在保持了單調(diào)性的同時，還是數(shù)據(jù)的遷移到達了最小，這樣的算法對散布式集群來講是非常適合的，避免了大量數(shù)據(jù)遷移，減小了服務器的的壓力。

平衡性
根據(jù)上面的圖解分析，1致性哈希算法滿足了單調(diào)性和負載均衡的特性和1般hash算法的分散性，但這還其實不能當作其被廣泛利用的緣由，由于還缺少了平衡性。下面將分析1致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲到了NODE1中，而object2、object3、object4都存儲到了NODE3中，這樣就照成了非常不平衡的狀態(tài)。在1致性哈希算法中，為了盡量的滿足平衡性，其引入了虛擬節(jié)點。
“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機器）在 hash 空間的復制品（ replica ），1實際個節(jié)點（機器）對應了若干個“虛擬節(jié)點”，這個對應個數(shù)同樣成為“復制個數(shù)”，“虛擬節(jié)點”在 hash 空間中以hash值排列。
以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例，之前的對象在機器上的散布很不均衡，現(xiàn)在我們以2個副本（復制個數(shù)）為例，這樣全部hash環(huán)中就存在了4個虛擬節(jié)點，最后對象映照的關系圖以下：

根據(jù)上圖可知對象的映照關系：object1->NODE1⑴，object2->NODE1⑵，object3->NODE3⑵，object4->NODE3⑴。通過虛擬節(jié)點的引入，對象的散布就比較均衡了。那末在實際操作中，正真的對象查詢是如何工作的呢？對象從hash到虛擬節(jié)點到實際節(jié)點的轉(zhuǎn)換以下圖：

“虛擬節(jié)點”的hash計算可以采取對應節(jié)點的IP地址加數(shù)字后綴的方式。例如假定NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點”前，計算 cache A 的 hash 值：

引入“虛擬節(jié)點”后，計算“虛擬節(jié)”點NODE1⑴和NODE1⑵的hash值：