圖解什么是一致性哈希算法

1. 寫在前面

周末就像太陽(yáng)，總會(huì)到來(lái)，也總會(huì)離開。

此刻，沒錯(cuò)，是周六呀！還是雙休那種！

昨晚在B站看了幾個(gè)長(zhǎng)視頻，導(dǎo)致2點(diǎn)才睡覺，早上一覺醒來(lái)已經(jīng)10點(diǎn)了。

在這里溫馨提示各位盆友們，雖然我們都是年輕人，但還是要規(guī)律作息，早睡早起。

廢話不多說(shuō)了，開始今天的話題：

什么是一致性哈希算法。

2. 蒙圈的字面含義

第一次聽這個(gè)術(shù)語(yǔ)時(shí)候困惑于是個(gè)啥意思？

一致性，咱懂
哈希算法，咱也懂
一致性+哈希算法  什么鬼？

雖然我大白腦袋比較空，但是我不信所有的網(wǎng)友都知道這個(gè)術(shù)語(yǔ)，于是在知乎找到個(gè)問題，還以為是我寫的呢：

看來(lái)還真是有像大白這樣，腦袋不靈光但是充滿好奇的年輕人呀！

于是我決定上路，搞它！

3.分布式系統(tǒng)和一致性哈希

要理解一致性哈希算法就需要知道分布式系統(tǒng)的一些特點(diǎn)。

年輕人你肯定會(huì)問：為啥呢？

因?yàn)?，一致性哈希算法就是為了解決分布式系統(tǒng)中的一些關(guān)鍵問題。

3.1 分布式系統(tǒng)概覽

高并發(fā)和海量數(shù)據(jù)處理等場(chǎng)景越來(lái)越多，實(shí)現(xiàn)服務(wù)應(yīng)用的高可用、易擴(kuò)展、短延時(shí)等成為必然。

在此情況下分布式系統(tǒng)應(yīng)運(yùn)而生，互聯(lián)網(wǎng)的場(chǎng)景無(wú)外乎存儲(chǔ)和計(jì)算，因此分布式系統(tǒng)可以簡(jiǎn)單地分為：

• 分布式存儲(chǔ)
• 分布式計(jì)算

可以簡(jiǎn)單認(rèn)為分布式系統(tǒng)就是一批物理不相鄰的計(jì)算機(jī)組合起來(lái)共同對(duì)外提供服務(wù)。

對(duì)于用戶來(lái)說(shuō)具體有多少規(guī)模的計(jì)算機(jī)完成了這次請(qǐng)求，完全是無(wú)感知的。

分布式系統(tǒng)中的計(jì)算機(jī)越多，意味著計(jì)算和存儲(chǔ)資源等也就越多，能夠處理的并發(fā)訪問量也就越大，響應(yīng)速度也越快。

如圖為簡(jiǎn)單整體架構(gòu)：

3.2 分布式和集群化

集群是從原來(lái)的單機(jī)演變來(lái)的，單臺(tái)機(jī)器扛不住就加機(jī)器，直到服務(wù)負(fù)載、穩(wěn)定性、延時(shí)等指標(biāo)都滿足。

集群中的N臺(tái)機(jī)器上部署一樣的程序，就像一臺(tái)機(jī)器被復(fù)制多份一樣，這種形式就是集群化。

分布式是將一個(gè)完整的系統(tǒng)，按照業(yè)務(wù)功能拆分成一個(gè)個(gè)獨(dú)立的子系統(tǒng)，這些服務(wù)之間使用更高效的通信協(xié)議比如RPC來(lái)完成調(diào)度，各個(gè)子服務(wù)就像在一臺(tái)機(jī)器上一樣，實(shí)現(xiàn)了業(yè)務(wù)解耦，同時(shí)提高了并發(fā)能力確實(shí)不賴。

一個(gè)大的分布式系統(tǒng)可以理解拆分之后的子服務(wù)使用集群化，一個(gè)個(gè)子服務(wù)之間使用類似于RPC的協(xié)議串聯(lián)，組成一個(gè)龐大的存儲(chǔ)和計(jì)算網(wǎng)絡(luò)。

如圖為簡(jiǎn)單的分布式系統(tǒng)結(jié)構(gòu)：

3.3 集群化遇到的問題

我們以分布式存儲(chǔ)系統(tǒng)為例子，來(lái)說(shuō)明一致性哈希算法的用武之地。

對(duì)于集群來(lái)說(shuō)，機(jī)器多了就不好管理，必然會(huì)有機(jī)器物理故障，業(yè)務(wù)擴(kuò)縮容也非常正常，機(jī)器的調(diào)整必然帶來(lái)數(shù)據(jù)的遷移。

如果存儲(chǔ)集群中有5臺(tái)機(jī)器，如果這時(shí)有讀寫請(qǐng)求，就需要考慮從哪臺(tái)機(jī)器操作數(shù)據(jù)，一般有幾種方法：

• 隨機(jī)訪問
• 輪詢策略
• 權(quán)重輪詢策略
• Hash取模策略
• 一致性哈希策略

各種方法都有各自的優(yōu)缺點(diǎn)：

• 隨機(jī)訪問可能造成服務(wù)器負(fù)載壓力不均衡；
• 輪詢策略請(qǐng)求均勻分配，但當(dāng)服務(wù)器有性能差異，無(wú)法按性能分發(fā)；
• 權(quán)值需要靜態(tài)配置，無(wú)法自動(dòng)調(diào)節(jié)；
• 哈希取模如果機(jī)器動(dòng)態(tài)變化會(huì)導(dǎo)致路由產(chǎn)生變化，數(shù)據(jù)產(chǎn)生大量遷移。

實(shí)際中對(duì)于規(guī)模較小的系統(tǒng)來(lái)說(shuō)，哈希取模策略應(yīng)用很廣泛，接下來(lái)重點(diǎn)介紹hash取模和一致性哈希的區(qū)別與聯(lián)系。

4. 哈希取模的原理和優(yōu)缺點(diǎn)

Hash取模策略是其中常用的一種做法，它可以保證相同請(qǐng)求相同機(jī)器處理，這是一種并行轉(zhuǎn)串行的方法，工程中非常常見。

如果數(shù)據(jù)相對(duì)獨(dú)立，就避免了線程間的通信和同步，實(shí)現(xiàn)了無(wú)鎖化處理，所以還是很有用的。

index = hash_fun(key) % N

從上面的普通hash取模公式可以看到，如果N不變或者可以自己主動(dòng)控制，就可以實(shí)現(xiàn)數(shù)據(jù)的負(fù)載均衡和無(wú)鎖化處理，但是一旦N的變化不被控制，那么就會(huì)出現(xiàn)問題。

來(lái)看看哈希取模策略是如何應(yīng)對(duì)擴(kuò)縮容問題的，特別注意，為了簡(jiǎn)化問題模型，接下來(lái)的例子不考慮實(shí)例的主從配置。

• 風(fēng)平浪靜 齊頭并進(jìn)

目前有N=4臺(tái)機(jī)器S1-S4，請(qǐng)求拼接key通過hash函數(shù)%N，獲取指定的機(jī)器序號(hào)，并將請(qǐng)求轉(zhuǎn)發(fā)至該機(jī)器。

• 磁盤故障 請(qǐng)求支援

S3機(jī)器因?yàn)榇疟P故障而宕機(jī)，這時(shí)代理層獲得故障報(bào)警調(diào)整N=3，這時(shí)就出現(xiàn)了問題，如果作為緩存使用，S3機(jī)器上的所有key都將出現(xiàn)CacheMiss。

原來(lái)存放在S1的key=abc使用新的N，被調(diào)整到S4，這樣abc也出現(xiàn)CacheMiss，因?yàn)樵赟4上找不到abc的數(shù)據(jù)。

這種場(chǎng)景就是牽一發(fā)而動(dòng)全身，在緩存場(chǎng)景中會(huì)造成緩存擊穿，如果量很大會(huì)造成緩存雪崩。

• 兄弟頂住 救兵來(lái)了

由于S3宕機(jī)了，因此管理員增加了一臺(tái)機(jī)器S5，代理層再次調(diào)整N=4，此時(shí)又將出現(xiàn)類似于階段二的數(shù)據(jù)遷移，仍然會(huì)出現(xiàn)CacheMiss的情況。

5.一致性哈希算法

先來(lái)看看維基百科的英文定義：

in computer science, consistent hashing is a special kind of hashing such that when a hash table is resized, only  K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots.

簡(jiǎn)單翻譯一下：

一致哈希 是一種特殊的哈希算法。  

在使用一致哈希算法后，哈希表槽位數(shù)（大小）的改變平均只需要對(duì)K/n 個(gè)關(guān)鍵字重新映射，其中 K是關(guān)鍵字的數(shù)量，n是槽位數(shù)量。  

在傳統(tǒng)的哈希表中，添加或刪除一個(gè)槽位的幾乎需要對(duì)所有關(guān)鍵字進(jìn)行重新映射。

從定義可以知道，一致性哈希是一種特殊的哈希算法，區(qū)別于哈希取模，這種特殊的哈希算法實(shí)現(xiàn)了少量數(shù)據(jù)的遷移，避免了幾乎全部數(shù)據(jù)的移動(dòng)，這樣就解決了普通hash取模的動(dòng)態(tài)調(diào)整帶來(lái)的全量數(shù)據(jù)變動(dòng)。

這個(gè)有點(diǎn)厲害了，趕緊看看是咋實(shí)現(xiàn)的。

5.1 一致性哈希算法思想

先不看算法的具體實(shí)現(xiàn)，先想想普通hash取模的問題根源是什么？

沒錯(cuò)！根源就在于N的變動(dòng)和數(shù)據(jù)歸屬問題。

• N的變動(dòng)

那么如果N被固定住呢？

如果讓N很大，那么每次被移動(dòng)的key數(shù)就是K_all/Slot_n，也就是有槽位的概念，或者說(shuō)是小分片的概念，直白一點(diǎn)就是雞蛋放到了很多很多的固定數(shù)量的籃子里：

Key_all 存儲(chǔ)的全部key的數(shù)量
Slot_n 總的槽位或者分片數(shù)
Min_Change 為最小移動(dòng)數(shù)量 
Min_change = Key_all/Slot_n
Min_change 也是數(shù)據(jù)的最小分片Shard

• 小分片的歸屬

這里還有一個(gè)問題要解決，將N固定且設(shè)置很大之后，數(shù)據(jù)分片shard變得非常小了，這時(shí)就有shard的所屬問題。

也就是比如N=100w，此時(shí)集群有10臺(tái)，那么每臺(tái)機(jī)器上理論上平均有10w，當(dāng)然可以根據(jù)機(jī)器的性能來(lái)做差異化的歸屬配置，性能強(qiáng)的多分一些shard，性能差的少分一些shard。

問題到這里，基本上已經(jīng)守得云開見月明了，不過還是來(lái)看看1997年麻省理工發(fā)明的一致性哈希算法原理吧。

5.2 Karger的一致性哈希算法

一致性哈希算法在1997年由麻省理工學(xué)院的Karger等人在解決分布式Cache中提出的，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot spot)問題，初衷和CARP十分類似。

一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來(lái)的問題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。

一起看看Karger的一致性哈希算法的基本原理以及如何應(yīng)對(duì)擴(kuò)縮容問題的。

• 哈希環(huán)分片

正如我們前面的思考，Karger的一致性哈希算法將N設(shè)置為2^32，形成了一個(gè)0~(2^32-1）的哈希環(huán)，也就是相當(dāng)于普通Hash取模時(shí)N=2^32。

在將數(shù)據(jù)key進(jìn)行hash計(jì)算時(shí)就落在了0~(2^32-1的哈希環(huán)上，如果總的key數(shù)量為Sum，那么單個(gè)哈希環(huán)的最小單位上的key數(shù)就是：

Unit_keys = Sum/2^32

由于N非常大所以哈希環(huán)最小單位的數(shù)據(jù)量unit_keys小了很多。

• 服務(wù)節(jié)點(diǎn)和哈希環(huán)分片

將服務(wù)器結(jié)點(diǎn)也作為一種key分發(fā)到哈希環(huán)上：

con_hash(ip_key)%2^32

一致性哈希算法使用順時(shí)針方法實(shí)現(xiàn)結(jié)點(diǎn)對(duì)哈希環(huán)shard的歸屬，但是由于服務(wù)器結(jié)點(diǎn)的數(shù)量相比2^32會(huì)少非常多，因此很稀疏，就像宇宙空間中的天體，你以為天體很多，但是相比浩渺的宇宙還是空空如也。

• 一致性哈希的不均衡

實(shí)體服務(wù)器結(jié)點(diǎn)少量相比哈希環(huán)分片數(shù)據(jù)很少，這種特性決定了一致性哈希的數(shù)據(jù)傾斜，由于數(shù)量少導(dǎo)致服務(wù)節(jié)點(diǎn)分布不均，造成機(jī)器負(fù)載失衡。

如圖所示，服務(wù)器1的負(fù)載遠(yuǎn)大于其他機(jī)器:

• 虛擬節(jié)點(diǎn)的引入

這個(gè)說(shuō)白了服務(wù)器結(jié)點(diǎn)不夠，就讓服務(wù)器的磁盤、內(nèi)存、CPU全去占位置，現(xiàn)實(shí)生活中也這樣：12306出來(lái)之前，火車站連夜排隊(duì)買票，這時(shí)什么書包、水杯、眼鏡都代表了張三、李四、王二麻子。

同樣的道理，將服務(wù)器結(jié)點(diǎn)根據(jù)某種規(guī)則來(lái)虛擬出更多結(jié)點(diǎn)，但是這些虛擬節(jié)點(diǎn)就相當(dāng)于服務(wù)器的分身。

比如采用如下規(guī)則在ip后綴增加#index，來(lái)實(shí)現(xiàn)虛擬節(jié)點(diǎn)的定位：

vnode_A_index = con_hash(ip_key_#A)%2^32
vnode_B_index = con_hash(ip_key_#B)%2^32
...
vnode_k_index = con_hash(ip_key_#k)%2^32

這是由于引入了虛擬節(jié)點(diǎn)，因此虛擬節(jié)點(diǎn)的分片都要實(shí)際歸屬到真實(shí)的服務(wù)節(jié)點(diǎn)上，因此在實(shí)際中涉及到虛擬節(jié)點(diǎn)和實(shí)體結(jié)點(diǎn)的映射問題。

• 新增服務(wù)器結(jié)點(diǎn)

當(dāng)管理員新增了服務(wù)器4時(shí)，原來(lái)在服務(wù)器3和服務(wù)器1之間分布的哈希環(huán)單元上的數(shù)據(jù)，將有一部分遷移到服務(wù)器4，當(dāng)然由于虛擬節(jié)點(diǎn)的引入，這部分?jǐn)?shù)據(jù)遷移不會(huì)很大。

并不是服務(wù)器4和服務(wù)器1之間的數(shù)據(jù)都要順時(shí)針遷移，因此這樣就實(shí)現(xiàn)了增加機(jī)器時(shí)，只移動(dòng)少量數(shù)據(jù)即可。

• 刪除服務(wù)器結(jié)點(diǎn)

當(dāng)服務(wù)器結(jié)點(diǎn)2發(fā)生宕機(jī)，此時(shí)需要被摘除進(jìn)行故障轉(zhuǎn)移，原來(lái)S2以及其虛擬節(jié)點(diǎn)上的數(shù)據(jù)都將進(jìn)行順時(shí)針遷移到下一個(gè)實(shí)體結(jié)點(diǎn)或者虛擬結(jié)點(diǎn)。

6. Redis的一致性哈希實(shí)現(xiàn)

Redis cluster 擁有固定的16384個(gè)slot，slot是虛擬的且被分布到各個(gè)master中，當(dāng)key 映射到某個(gè)master 負(fù)責(zé)slot時(shí)，就由對(duì)應(yīng)的master為key 提供服務(wù)。

每個(gè)Master節(jié)點(diǎn)都維護(hù)著一個(gè)位序列bitmap為16384/8字節(jié)，也就是Master使用bitmap的原理來(lái)表征slot的下標(biāo)，Master 節(jié)點(diǎn)通過 bit 來(lái)標(biāo)識(shí)哪些槽自己是否擁有，比如對(duì)于編號(hào)為1的槽，Master只要判斷序列的第二位是不是為1即可。

這樣就建立了分片和服務(wù)結(jié)點(diǎn)的所屬關(guān)系，所以整個(gè)過程也是兩個(gè)原則，符合上文的一致性哈希的思想。

hash_slot_index =CRC16(key) mod 16384

7. 思考和總結(jié)

通過前面的對(duì)比和理解，我們有必要思考一下，一致性哈希算法的精髓。

7.1 一致性哈希算法的兩個(gè)關(guān)鍵點(diǎn)

一致性哈希算法是一種特殊的哈希算法，特殊之處在于將普通哈希取模的N進(jìn)行固定，從而確保了相同的key必然是相同的位置，從而避免了牽一發(fā)而動(dòng)全身的問題，這是理解一致性哈希的關(guān)鍵。

一致性哈希算法的另外一個(gè)要點(diǎn)就是將N固定且設(shè)置很大之后，實(shí)際上就是進(jìn)行數(shù)據(jù)分片Sharding，分布的小片就要和實(shí)際的機(jī)器產(chǎn)生關(guān)聯(lián)關(guān)系，也就是哪臺(tái)機(jī)器負(fù)責(zé)哪些小分片。

但是一致性哈希算法并不是從徹底解決了由于動(dòng)態(tài)調(diào)整服務(wù)器數(shù)據(jù)產(chǎn)生的數(shù)據(jù)遷移問題，而是將原來(lái)普通哈希取模造成的幾乎全部遷移，降低為小部分?jǐn)?shù)據(jù)的移動(dòng)，是一種非常大的優(yōu)化。

個(gè)人認(rèn)為，一致性哈希算法的關(guān)鍵有兩點(diǎn)：

• 大量固定數(shù)量的小數(shù)據(jù)塊的分片
• 小分片的服務(wù)器歸屬問題

7.2 算法的其他工程版本

像Redis并沒有使用2^32這種哈希環(huán)，而是采用了16384個(gè)固定slot來(lái)實(shí)現(xiàn)的，然后每個(gè)服務(wù)器Master使用bitmap來(lái)確定自己的管轄slot。

管理員可以根據(jù)機(jī)器的配置和負(fù)載情況進(jìn)行slot的動(dòng)態(tài)調(diào)整，基本上解決了最開始的幾種負(fù)載均衡策略的不足。

所以假如讓你設(shè)計(jì)一個(gè)一致性哈希算法，只要把握兩個(gè)原則即可，并不是只有麻省理工Karger的一種哈希算法，它只是提供了一種思想和方向。

7.3 關(guān)于一致性哈希算法的命名

回到最初的疑問：為什么要用"一致性哈希算法" 這個(gè)名字。

英文原文是Consistent hashing，其中Consistent譯為"一致的，連貫的"，我覺得連貫的更貼切一些，以為這種特殊的哈希算法實(shí)現(xiàn)了普通哈希取模算法的平滑連貫版本，稱為連貫性哈希算法，好像更合適，一點(diǎn)愚見，水平有限，看看就完事了。