理解一致性哈希算法
整理自:
版權(quán)歸原作者所有
哈希算法設(shè)計(jì)原則
一致性hash算法提出了在動(dòng)態(tài)變化的Cache環(huán)境中，判定哈希算法好壞的四個(gè)定義：
- 平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。
- 單調(diào)性(Monotonicity)：?jiǎn)握{(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。
- 分散性(Spread)：在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見(jiàn)的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去，降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。
- 負(fù)載(Load)：負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。
一致性哈希算法就是這樣一種哈希方案。接下來(lái)主要講解一下一致性哈希算法是如何設(shè)計(jì)的：
環(huán)形Hash空間
按照常用的hash算法來(lái)將對(duì)應(yīng)的key哈希到一個(gè)具有2^32次方個(gè)桶的空間中，即0~(2^32)-1的數(shù)字空間中?，F(xiàn)在我們可以將這些數(shù)字頭尾相連，想象成一個(gè)閉合的環(huán)形。如下圖:
把數(shù)據(jù)通過(guò)一定的hash算法處理后映射到環(huán)上
現(xiàn)在我們將object1、object2、object3、object4四個(gè)對(duì)象通過(guò)特定的Hash函數(shù)計(jì)算出對(duì)應(yīng)的key值，然后散列到Hash環(huán)上。如下圖:
Hash(object1) = key1;
Hash(object2) = key2;
Hash(object3) = key3;
Hash(object4) = key4;
分散性
將機(jī)器通過(guò)hash算法映射到環(huán)上
在采用一致性哈希算法的分布式集群中將新的機(jī)器加入，其原理是通過(guò)使用與對(duì)象存儲(chǔ)一樣的Hash算法將機(jī)器也映射到環(huán)中（一般情況下對(duì)機(jī)器的hash計(jì)算是采用機(jī)器的IP或者機(jī)器唯一的別名作為輸入值），然后以順時(shí)針的方向計(jì)算，將所有對(duì)象存儲(chǔ)到離自己最近的機(jī)器中。
假設(shè)現(xiàn)在有NODE1，NODE2，NODE3三臺(tái)機(jī)器，通過(guò)Hash算法得到對(duì)應(yīng)的KEY值，映射到環(huán)中，其示意圖如下：
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
通過(guò)上圖可以看出對(duì)象與機(jī)器處于同一哈?？臻g中，這樣按順時(shí)針轉(zhuǎn)動(dòng)object1存儲(chǔ)到了NODE1中，object3存儲(chǔ)到了NODE2中，object2、object4存儲(chǔ)到了NODE3中。在這樣的部署環(huán)境中，hash環(huán)是不會(huì)變更的，因此，通過(guò)算出對(duì)象的hash值就能快速的定位到對(duì)應(yīng)的機(jī)器中，這樣就能找到對(duì)象真正的存儲(chǔ)位置了。
單調(diào)性
在分布式集群中，對(duì)機(jī)器的添加刪除，或者機(jī)器故障后自動(dòng)脫離集群這些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有機(jī)器添加或者刪除后，很多原有的數(shù)據(jù)就無(wú)法找到了，這樣嚴(yán)重的違反了單調(diào)性原則。
一個(gè)設(shè)計(jì)良好的分布式哈希方案應(yīng)該具有良好的單調(diào)性，即服務(wù)節(jié)點(diǎn)的增減不會(huì)造成大量哈希重定位。
普通hash求余算法最為不妥的地方就是在有機(jī)器的添加或者刪除之后會(huì)照成大量的對(duì)象存儲(chǔ)位置失效，這樣就大大的不滿足單調(diào)性了。下面來(lái)分析一下一致性哈希算法是如何處理的。
節(jié)點(diǎn)（機(jī)器）的刪除
以上面的分布為例，如果NODE2出現(xiàn)故障被刪除了，那么按照順時(shí)針遷移的方法，object3將會(huì)被遷移到NODE3中，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對(duì)象沒(méi)有任何的改動(dòng)。如下圖：
節(jié)點(diǎn)（機(jī)器）的添加
如果往集群中添加一個(gè)新的節(jié)點(diǎn)NODE4，通過(guò)對(duì)應(yīng)的哈希算法得到KEY4，并映射到環(huán)中，如下圖：
通過(guò)按順時(shí)針遷移的規(guī)則，那么object2被遷移到了NODE4中，其它對(duì)象還保持這原有的存儲(chǔ)位置。通過(guò)對(duì)節(jié)點(diǎn)的添加和刪除的分析，一致性哈希算法在保持了單調(diào)性的同時(shí)，還是數(shù)據(jù)的遷移達(dá)到了最小，這樣的算法對(duì)分布式集群來(lái)說(shuō)是非常合適的，避免了大量數(shù)據(jù)遷移，減小了服務(wù)器的的壓力。
平衡性
根據(jù)上面的圖解分析，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由，因?yàn)檫€缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲(chǔ)到了NODE1中，而object2、object3、object4都存儲(chǔ)到了NODE3中，這樣就照成了非常不平衡的狀態(tài)。在一致性哈希算法中，為了盡可能的滿足平衡性，其引入了虛擬節(jié)點(diǎn)。
“虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)（機(jī)器）在 hash 空間的副本（ replica ），一個(gè)真實(shí)節(jié)點(diǎn)（機(jī)器）對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“副本個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 環(huán)中以hash值排列。
思考:
- 需要維護(hù)一個(gè)實(shí)際節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的映射，當(dāng)每次找到一個(gè)虛擬節(jié)點(diǎn)時(shí)，需要能路由到真實(shí)節(jié)點(diǎn)
- 需要設(shè)計(jì)虛擬節(jié)點(diǎn)個(gè)數(shù)的算法，虛擬節(jié)點(diǎn)個(gè)數(shù)越多，平衡性越好，但與實(shí)際節(jié)點(diǎn)的映射數(shù)量會(huì)越大，在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為32甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對(duì)均勻的數(shù)據(jù)分布。
以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例，之前的對(duì)象在機(jī)器上的分布很不均衡，現(xiàn)在我們以2個(gè)副本（復(fù)制個(gè)數(shù)）為例，這樣整個(gè)hash環(huán)中就存在了4個(gè)虛擬節(jié)點(diǎn)，最后對(duì)象映射的關(guān)系圖如下：
根據(jù)上圖可知對(duì)象的映射關(guān)系：
object1->NODE1-1
object2->NODE1-2
object3->NODE3-2
object4->NODE3-1
通過(guò)虛擬節(jié)點(diǎn)的引入，對(duì)象的分布就比較均衡了。那么在實(shí)際操作中，正真的對(duì)象查詢是如何工作的呢？對(duì)象從hash到虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的轉(zhuǎn)換如下圖：
“虛擬節(jié)點(diǎn)”的hash計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的IP地址加數(shù)字后綴的方式。
例如假設(shè)NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點(diǎn)”前，計(jì)算Node1的 hash 值：
node1 = Hash(“192.168.1.100”);
引入“虛擬節(jié)點(diǎn)”后，計(jì)算“虛擬節(jié)”點(diǎn)NODE1-1和NODE1-2的hash值：
node1_1 = Hash(“192.168.1.100#1”); // NODE1-1
node1_2 = Hash(“192.168.1.100#2”); // NODE1-2
這里就需要維護(hù)一個(gè)node1_*與node1的映射，以便命中到虛擬節(jié)點(diǎn)的請(qǐng)求可以找到真實(shí)節(jié)點(diǎn)。
