一致性Hash算法背景

一致性哈希算法在1997年由麻省理工學(xué)院的Karger等人在解決分布式Cache中提出的，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot spot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來的問題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。

但現(xiàn)在一致性hash算法在分布式系統(tǒng)中也得到了廣泛應(yīng)用，研究過memcached緩存數(shù)據(jù)庫的人都知道，memcached服務(wù)器端本身不提供分布式cache的一致性，而是由客戶端來提供，具體在計(jì)算一致性hash時(shí)采用如下步驟：

1. 首先求出memcached服務(wù)器（節(jié)點(diǎn)）的哈希值，并將其配置到0～2³²的圓（continuum）上。
2. 然后采用同樣的方法求出存儲(chǔ)數(shù)據(jù)的鍵的哈希值，并映射到相同的圓上。
3. 然后從數(shù)據(jù)映射到的位置開始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上。如果超過2³²仍然找不到服務(wù)器，就會(huì)保存到第一臺(tái)memcached服務(wù)器上。

image

從上圖的狀態(tài)中添加一臺(tái)memcached服務(wù)器。余數(shù)分布式算法由于保存鍵的服務(wù)器會(huì)發(fā)生巨大變化而影響緩存的命中率，但Consistent Hashing中，只有在園（continuum）上增加服務(wù)器的地點(diǎn)逆時(shí)針方向的第一臺(tái)服務(wù)器上的鍵會(huì)受到影響，如下圖所示：

image

一致性Hash性質(zhì)

考慮到分布式系統(tǒng)每個(gè)節(jié)點(diǎn)都有可能失效，并且新的節(jié)點(diǎn)很可能動(dòng)態(tài)的增加進(jìn)來，如何保證當(dāng)系統(tǒng)的節(jié)點(diǎn)數(shù)目發(fā)生變化時(shí)仍然能夠?qū)ν馓峁┝己玫姆?wù)，這是值得考慮的，尤其實(shí)在設(shè)計(jì)分布式緩存系統(tǒng)時(shí)，如果某臺(tái)服務(wù)器失效，對(duì)于整個(gè)系統(tǒng)來說如果不采用合適的算法來保證一致性，那么緩存于系統(tǒng)中的所有數(shù)據(jù)都可能會(huì)失效（即由于系統(tǒng)節(jié)點(diǎn)數(shù)目變少，客戶端在請(qǐng)求某一對(duì)象時(shí)需要重新計(jì)算其hash值（通常與系統(tǒng)中的節(jié)點(diǎn)數(shù)目有關(guān)），由于hash值已經(jīng)改變，所以很可能找不到保存該對(duì)象的服務(wù)器節(jié)點(diǎn)），因此一致性hash就顯得至關(guān)重要，良好的分布式cahce系統(tǒng)中的一致性hash算法應(yīng)該滿足以下幾個(gè)方面：

• 平衡性(Balance)

平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。

• 單調(diào)性(Monotonicity)

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖區(qū)加入到系統(tǒng)中，那么哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖區(qū)中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。簡(jiǎn)單的哈希算法往往不能滿足單調(diào)性的要求，如最簡(jiǎn)單的線性哈希：x = (ax + b) mod (P)，在上式中，P表示全部緩沖的大小。不難看出，當(dāng)緩沖大小發(fā)生變化時(shí)(從P1到P2)，原來所有的哈希結(jié)果均會(huì)發(fā)生變化，從而不滿足單調(diào)性的要求。哈希結(jié)果的變化意味著當(dāng)緩沖空間發(fā)生變化時(shí)，所有的映射關(guān)系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi)，緩沖的變化等價(jià)于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會(huì)頻繁發(fā)生，因此會(huì)帶來極大計(jì)算和傳輸負(fù)荷。單調(diào)性就是要求哈希算法能夠應(yīng)對(duì)這種情況。

• 分散性(Spread)

在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見的緩沖范圍有可能不同，從而導(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ù)載問題實(shí)際上是從另一個(gè)角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

• 平滑性(Smoothness)

平滑性是指緩存服務(wù)器的數(shù)目平滑改變和緩存對(duì)象的平滑改變是一致的。

原理

基本概念

一致性哈希算法（Consistent Hashing）最早在論文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。簡(jiǎn)單來說，一致性哈希將整個(gè)哈希值空間組織成一個(gè)虛擬的圓環(huán)，如假設(shè)某哈希函數(shù)H的值空間為0-2^³²-1（即哈希值是一個(gè)32位無符號(hào)整形），整個(gè)哈?？臻g環(huán)如下：

image

整個(gè)空間按順時(shí)針方向組織。0和2³²-1在零點(diǎn)中方向重合。

下一步將各個(gè)服務(wù)器使用Hash進(jìn)行一個(gè)哈希，具體可以選擇服務(wù)器的ip或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺(tái)機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中四臺(tái)服務(wù)器使用ip地址哈希后在環(huán)空間的位置如下：

image

接下來使用如下算法定位數(shù)據(jù)訪問到相應(yīng)服務(wù)器：將數(shù)據(jù)key使用相同的函數(shù)Hash計(jì)算出哈希值，并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時(shí)針“行走”，第一臺(tái)遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。

例如我們有Object A、Object B、Object C、Object D四個(gè)數(shù)據(jù)對(duì)象，經(jīng)過哈希計(jì)算后，在環(huán)空間上的位置如下：

image

根據(jù)一致性哈希算法，數(shù)據(jù)A會(huì)被定為到Node A上，B被定為到Node B上，C被定為到Node C上，D被定為到Node D上。

下面分析一致性哈希算法的容錯(cuò)性和可擴(kuò)展性?，F(xiàn)假設(shè)Node C不幸宕機(jī)，可以看到此時(shí)對(duì)象A、B、D不會(huì)受到影響，只有C對(duì)象被重定位到Node D。一般的，在一致性哈希算法中，如果一臺(tái)服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即沿著逆時(shí)針方向行走遇到的第一臺(tái)服務(wù)器）之間數(shù)據(jù)，其它不會(huì)受到影響。

下面考慮另外一種情況，如果在系統(tǒng)中增加一臺(tái)服務(wù)器Node X，如下圖所示：

image

此時(shí)對(duì)象Object A、B、D不受影響，只有對(duì)象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一臺(tái)服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即沿著逆時(shí)針方向行走遇到的第一臺(tái)服務(wù)器）之間數(shù)據(jù)，其它數(shù)據(jù)也不會(huì)受到影響。

綜上所述，一致性哈希算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯(cuò)性和可擴(kuò)展性。

另外，一致性哈希算法在服務(wù)節(jié)點(diǎn)太少時(shí)，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問題。例如系統(tǒng)中只有兩臺(tái)服務(wù)器，其環(huán)分布如下，

image

此時(shí)必然造成大量數(shù)據(jù)集中到Node A上，而只有極少量會(huì)定位到Node B上。為了解決這種數(shù)據(jù)傾斜問題，一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號(hào)來實(shí)現(xiàn)。例如上面的情況，可以為每臺(tái)服務(wù)器計(jì)算三個(gè)虛擬節(jié)點(diǎn)，于是可以分別計(jì)算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六個(gè)虛擬節(jié)點(diǎn)：

image

同時(shí)數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三個(gè)虛擬節(jié)點(diǎn)的數(shù)據(jù)均定位到Node A上。這樣就解決了服務(wù)節(jié)點(diǎn)少時(shí)數(shù)據(jù)傾斜的問題。在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為32甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對(duì)均勻的數(shù)據(jù)分布。

環(huán)形Hash空間

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

image.png

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

現(xiàn)在我們將object1、object2、object3、object4四個(gè)對(duì)象通過特定的Hash函數(shù)計(jì)算出對(duì)應(yīng)的key值，然后散列到Hash環(huán)上。如下圖：

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

image.png

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

在采用一致性哈希算法的分布式集群中將新的機(jī)器加入，其原理是通過使用與對(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ī)器，通過Hash算法得到對(duì)應(yīng)的KEY值，映射到環(huán)中，其示意圖如下：

Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;

image.png

通過上圖可以看出對(duì)象與機(jī)器處于同一哈希空間中，這樣按順時(shí)針轉(zhuǎn)動(dòng)object1存儲(chǔ)到了NODE1中，object3存儲(chǔ)到了NODE2中，object2、object4存儲(chǔ)到了NODE3中。在這樣的部署環(huán)境中，hash環(huán)是不會(huì)變更的，因此，通過算出對(duì)象的hash值就能快速的定位到對(duì)應(yīng)的機(jī)器中，這樣就能找到對(duì)象真正的存儲(chǔ)位置了。

機(jī)器的刪除與添加

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

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

以上面的分布為例，如果NODE2出現(xiàn)故障被刪除了，那么按照順時(shí)針遷移的方法，object3將會(huì)被遷移到NODE3中，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對(duì)象沒有任何的改動(dòng)。如下圖：

image.png

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

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

image.png

通過按順時(shí)針遷移的規(guī)則，那么object2被遷移到了NODE4中，其它對(duì)象還保持這原有的存儲(chǔ)位置。通過對(duì)節(jié)點(diǎn)的添加和刪除的分析，一致性哈希算法在保持了單調(diào)性的同時(shí)，還是數(shù)據(jù)的遷移達(dá)到了最小，這樣的算法對(duì)分布式集群來說是非常合適的，避免了大量數(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 空間的復(fù)制品（ replica ），一實(shí)際個(gè)節(jié)點(diǎn)（機(jī)器）對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以hash值排列。

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

image.png

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

image.png

image.png

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

Hash(“192.168.1.100”);

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

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

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