轉(zhuǎn)載請說明出處：http://blog.csdn.net/cywosp/article/details/23397179
一致性哈希算法在1997年由麻省理工學(xué)院提出的一種分布式哈希（DHT）實現(xiàn)算法奕删，設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點(Hot spot)問題载城，初衷和CARP十分類似税产。一致性哈希修正了CARP使用的簡 單哈希算法帶來的問題，使得分布式哈希（DHT）可以在P2P環(huán)境中真正得到應(yīng)用查坪。
一致性hash算法提出了在動態(tài)變化的Cache環(huán)境中，判定哈希算法好壞的四個定義：
1沛婴、平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去欺旧，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件让网。
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)該避免的，因為它導(dǎo)致相同內(nèi)容被存儲到不同緩沖中去莉御，降低了系統(tǒng)存儲的效率撇吞。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度俗冻。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性牍颈。
4迄薄、負(fù)載(Load)：負(fù)載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中煮岁，那么對于一個特定的緩沖區(qū)而言讥蔽，也可能被不同的用戶映射為不同 的內(nèi)容。與分散性一樣画机，這種情況也是應(yīng)當(dāng)避免的冶伞，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。
在分布式集群中步氏，對機器的添加刪除响禽，或者機器故障后自動脫離集群這些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法荚醒，那么在有機器添加或者刪除后芋类，很多原有的數(shù)據(jù)就無法找到了，這樣嚴(yán)重的違反了單調(diào)性原則界阁。接下來主要講解一下一致性哈希算法是如何設(shè)計的：
環(huán)形Hash空間
按照常用的hash算法來將對應(yīng)的key哈希到一個具有232次方個桶的空間中侯繁，即0~(232)-1的數(shù)字空間中。現(xiàn)在我們可以將這些數(shù)字頭尾相連泡躯，想象成一個閉合的環(huán)形贮竟。如下圖
把數(shù)據(jù)通過一定的hash算法處理后映射到環(huán)上
現(xiàn)在我們將object1、object2较剃、object3咕别、object4四個對象通過特定的Hash函數(shù)計算出對應(yīng)的key值，然后散列到Hash環(huán)上重付。如下圖：
Hash(object1) = key1顷级；
Hash(object2) = key2凫乖；
Hash(object3) = key3确垫；
Hash(object4) = key4；
將機器通過hash算法映射到環(huán)上
在采用一致性哈希算法的分布式集群中將新的機器加入帽芽，其原理是通過使用與對象存儲一樣的Hash算法將機器也映射到環(huán)中（一般情況下對機器的hash計算是采用機器的IP或者機器唯一的別名作為輸入值）删掀，然后以順時針的方向計算，將所有對象存儲到離自己最近的機器中导街。
假設(shè)現(xiàn)在有NODE1披泪，NODE2，NODE3三臺機器搬瑰，通過Hash算法得到對應(yīng)的KEY值款票，映射到環(huán)中控硼，其示意圖如下：
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
通過上圖可以看出對象與機器處于同一哈希空間中艾少，這樣按順時針轉(zhuǎn)動object1存儲到了NODE1中卡乾，object3存儲到了NODE2中，object2缚够、object4存儲到了NODE3中幔妨。在這樣的部署環(huán)境中，hash環(huán)是不會變更的谍椅，因此误堡，通過算出對象的hash值就能快速的定位到對應(yīng)的機器中，這樣就能找到對象真正的存儲位置了雏吭。
機器的刪除與添加
普通hash求余算法最為不妥的地方就是在有機器的添加或者刪除之后會照成大量的對象存儲位置失效锁施，這樣就大大的不滿足單調(diào)性了。下面來分析一下一致性哈希算法是如何處理的杖们。
-
節(jié)點（機器）的刪除
以上面的分布為例沾谜，如果NODE2出現(xiàn)故障被刪除了，那么按照順時針遷移的方法胀莹，object3將會被遷移到NODE3中基跑，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對象沒有任何的改動描焰。如下圖：
-
節(jié)點（機器）的添加
如果往集群中添加一個新的節(jié)點NODE4媳否，通過對應(yīng)的哈希算法得到KEY4，并映射到環(huán)中荆秦，如下圖：
通過按順時針遷移的規(guī)則篱竭，那么object2被遷移到了NODE4中，其它對象還保持這原有的存儲位置步绸。通過對節(jié)點的添加和刪除的分析掺逼，一致性哈希算法在保持了單調(diào)性的同時，還是數(shù)據(jù)的遷移達(dá)到了最小瓤介，這樣的算法對分布式集群來說是非常合適的吕喘，避免了大量數(shù)據(jù)遷移，減小了服務(wù)器的的壓力刑桑。
平衡性
根據(jù)上面的圖解分析氯质，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由祠斧，因為還缺少了平衡性闻察。下面將分析一致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）辕漂，object1存儲到了NODE1中呢灶，而object2、object3钉嘹、object4都存儲到了NODE3中填抬，這樣就照成了非常不平衡的狀態(tài)。在一致性哈希算法中隧期，為了盡可能的滿足平衡性飒责，其引入了虛擬節(jié)點。
——“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機器）在 hash 空間的復(fù)制品（ replica ）仆潮，一實際個節(jié)點（機器）對應(yīng)了若干個“虛擬節(jié)點”宏蛉，這個對應(yīng)個數(shù)也成為“復(fù)制個數(shù)”，“虛擬節(jié)點”在 hash 空間中以hash值排列性置。
以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例拾并，之前的對象在機器上的分布很不均衡，現(xiàn)在我們以2個副本（復(fù)制個數(shù)）為例鹏浅，這樣整個hash環(huán)中就存在了4個虛擬節(jié)點嗅义，最后對象映射的關(guān)系圖如下：
根據(jù)上圖可知對象的映射關(guān)系：object1->NODE1-1，object2->NODE1-2隐砸，object3->NODE3-2之碗，object4->NODE3-1。通過虛擬節(jié)點的引入季希，對象的分布就比較均衡了褪那。那么在實際操作中，正真的對象查詢是如何工作的呢式塌？對象從hash到虛擬節(jié)點到實際節(jié)點的轉(zhuǎn)換如下圖：
“虛擬節(jié)點”的hash計算可以采用對應(yīng)節(jié)點的IP地址加數(shù)字后綴的方式博敬。例如假設(shè)NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點”前峰尝，計算 cache A 的 hash 值：
Hash(“192.168.1.100”);
引入“虛擬節(jié)點”后偏窝，計算“虛擬節(jié)”點NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2
