一致性Hash算法背景

一致性哈希算法在1997年由麻省理工學(xué)院的Karger等人在解決分布式Cache中提出的走孽，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot spot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題，使得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. 然后采用同樣的方法求出存儲數(shù)據(jù)的鍵的哈希值摩泪，并映射到相同的圓上笆焰。
3. 然后從數(shù)據(jù)映射到的位置開始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上见坑。如果超過2³²仍然找不到服務(wù)器嚷掠，就會保存到第一臺memcached服務(wù)器上。

image

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

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í)，如果某臺服務(wù)器失效执泰，對于整個(gè)系統(tǒng)來說如果不采用合適的算法來保證一致性枕磁，那么緩存于系統(tǒng)中的所有數(shù)據(jù)都可能會失效（即由于系統(tǒng)節(jié)點(diǎn)數(shù)目變少，客戶端在請求某一對象時(shí)需要重新計(jì)算其hash值（通常與系統(tǒng)中的節(jié)點(diǎn)數(shù)目有關(guān)）术吝，由于hash值已經(jīng)改變计济，所以很可能找不到保存該對象的服務(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ū)中去幔翰，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)漩氨。簡單的哈希算法往往不能滿足單調(diào)性的要求，如最簡單的線性哈希：x = (ax + b) mod (P)遗增，在上式中叫惊，P表示全部緩沖的大小。不難看出做修，當(dāng)緩沖大小發(fā)生變化時(shí)(從P1到P2)霍狰，原來所有的哈希結(jié)果均會發(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)中會頻繁發(fā)生，因此會帶來極大計(jì)算和傳輸負(fù)荷屏箍。單調(diào)性就是要求哈希算法能夠應(yīng)對這種情況绘梦。

• 分散性(Spread)

在分布式環(huán)境中，終端有可能看不到所有的緩沖赴魁，而是只能看到其中的一部分卸奉。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見的緩沖范圍有可能不同尚粘，從而導(dǎo)致哈希的結(jié)果不一致择卦，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的郎嫁，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲到不同緩沖中去秉继，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度泽铛。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生尚辑，也就是盡量降低分散性。

• 負(fù)載(Load)

負(fù)載問題實(shí)際上是從另一個(gè)角度看待分散性問題盔腔。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中杠茬，那么對于一個(gè)特定的緩沖區(qū)而言月褥，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣瓢喉，這種情況也是應(yīng)當(dāng)避免的宁赤，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

• 平滑性(Smoothness)

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

原理

基本概念

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

image

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

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

image

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

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

image

根據(jù)一致性哈希算法，數(shù)據(jù)A會被定為到Node A上媒峡，B被定為到Node B上瘟栖，C被定為到Node C上，D被定為到Node D上谅阿。

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

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

image

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

綜上所述，一致性哈希算法對于節(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)中只有兩臺服務(wù)器，其環(huán)分布如下蚕捉，

image

此時(shí)必然造成大量數(shù)據(jù)集中到Node A上奏篙，而只有極少量會定位到Node B上。為了解決這種數(shù)據(jù)傾斜問題迫淹，一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制秘通，即對每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)敛熬，稱為虛擬節(jié)點(diǎn)肺稀。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號來實(shí)現(xiàn)。例如上面的情況应民，可以為每臺服務(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)也能做到相對均勻的數(shù)據(jù)分布母剥。

環(huán)形Hash空間

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

image.png

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

現(xiàn)在我們將object1、object2炫隶、object3淋叶、object4四個(gè)對象通過特定的Hash函數(shù)計(jì)算出對應(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ī)器加入，其原理是通過使用與對象存儲一樣的Hash算法將機(jī)器也映射到環(huán)中（一般情況下對機(jī)器的hash計(jì)算是采用機(jī)器的IP或者機(jī)器唯一的別名作為輸入值）檐薯，然后以順時(shí)針的方向計(jì)算凝赛，將所有對象存儲到離自己最近的機(jī)器中。

假設(shè)現(xiàn)在有NODE1坛缕，NODE2哄酝，NODE3三臺機(jī)器，通過Hash算法得到對應(yīng)的KEY值祷膳，映射到環(huán)中陶衅，其示意圖如下：

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

image.png

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

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

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

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

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

image.png

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

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

image.png

通過按順時(shí)針遷移的規(guī)則蓬痒，那么object2被遷移到了NODE4中泻骤，其它對象還保持這原有的存儲位置。通過對節(jié)點(diǎn)的添加和刪除的分析乳幸，一致性哈希算法在保持了單調(diào)性的同時(shí)，還是數(shù)據(jù)的遷移達(dá)到了最小钧椰，這樣的算法對分布式集群來說是非常合適的粹断，避免了大量數(shù)據(jù)遷移，減小了服務(wù)器的的壓力嫡霞。

平衡性

根據(jù)上面的圖解分析瓶埋，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由诊沪，因?yàn)檫€缺少了平衡性养筒。下面將分析一致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的端姚，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）晕粪，object1存儲到了NODE1中，而object2渐裸、object3巫湘、object4都存儲到了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ī)器）對應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以hash值排列讯柔。

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

image.png

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

image.png

image.png

“虛擬節(jié)點(diǎn)”的hash計(jì)算可以采用對應(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