一致性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ù)庫(kù)的人都知道，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ù)器上。

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

一致性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)如下：

整個(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)空間的位置如下：

接下來使用如下算法定位數(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)空間上的位置如下：

根據(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，如下圖所示：

此時(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)分布如下，

此時(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)：

同時(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ù)分布。