最近有一位讀者跟我交流，說除了算法題之外，系統(tǒng)設(shè)計題是一大痛點。算法題起碼有很多刷題平臺可以動手實踐，但系統(tǒng)設(shè)計類的題目一般很難實踐，所以看一些教程總結(jié)也只是一知半解，遇到讓寫代碼實現(xiàn)系統(tǒng)的就懵了。

比如他最近被問到一個大型爬蟲系統(tǒng)的設(shè)計題，讓手寫一致性哈希算法，加上一系列 follow up，就被難住了。

說實話這個算法的實現(xiàn)并不難，所以本文就結(jié)合一致性哈希算法在工程中的應(yīng)用場景介紹一下這個算法算法，并給出代碼實現(xiàn)，避免大家重蹈覆轍。

一致性哈希算法簡介

這個名詞大家肯定不陌生，應(yīng)該也大概理解這個算法的邏輯，不過我這里還是要再介紹一下。

一致性哈希主要解決把數(shù)據(jù)平均分配到多個節(jié)點上的問題，并且某些節(jié)點上線/下線后依然能夠做到自動負(fù)載均衡。

其原理就是抽象出一個哈希環(huán)，把服務(wù)器節(jié)點的 id 通過哈希函數(shù)映射到這個哈希環(huán)上：

同時，把需要處理的數(shù)據(jù)也通過哈希函數(shù)映射到這個哈希環(huán)上，然后順時針找，遇到的第一個服務(wù)器節(jié)點來負(fù)責(zé)處理這個數(shù)據(jù)：

這樣一來，我們其實已經(jīng)提供了一種機(jī)制將若干數(shù)據(jù)分布在若干服務(wù)節(jié)點上了，不妨稱它為 V1 版本的一致性哈希算法。

但 V1 版本的算法還有問題：負(fù)載分布很可能不均衡。由于哈希函數(shù)的結(jié)果是難以預(yù)測的，所以可能出現(xiàn)這種情況：

即某些服務(wù)器節(jié)點要負(fù)責(zé)的哈希環(huán)很長，而其他服務(wù)器負(fù)責(zé)的哈希環(huán)很短。這就會導(dǎo)致某些服務(wù)器負(fù)載很高，而其他的服務(wù)器負(fù)載很低，很不均衡。

而且，當(dāng)某個服務(wù)器節(jié)點下線后，它的負(fù)載會順時針轉(zhuǎn)移到下一個節(jié)點上，那么某些特定的節(jié)點下線順序很可能導(dǎo)致某些服務(wù)器節(jié)點負(fù)責(zé)的哈希環(huán)不斷加長，負(fù)載不斷增加。專業(yè)點說，這就是「數(shù)據(jù)傾斜」。

如何解決數(shù)據(jù)傾斜的問題呢？可以給每個服務(wù)器節(jié)點添加若干「虛擬節(jié)點」分布在哈希環(huán)上，我們不妨稱其為 V2 版的一致性哈希算法：

上圖給每個 Node 設(shè)置了 4 個虛擬節(jié)點，這樣一來，由于哈希函數(shù)的隨機(jī)性，每個服務(wù)器節(jié)點的虛擬節(jié)點能夠平均分布在哈希環(huán)上，那么數(shù)據(jù)就能夠比較均勻地分配到所有服務(wù)器節(jié)點上。

如果某個服務(wù)器節(jié)點下線，那么該服務(wù)器節(jié)點的所有虛擬節(jié)點都會從哈希環(huán)上摘除，它們的負(fù)載會遷移到順時針的下一個服務(wù)器節(jié)點上。

和 V1 版算法不同的是，因為虛擬節(jié)點有多個，它們的下一位不太可能是同一臺服務(wù)器的虛擬節(jié)點，所以它們的負(fù)載大概率會均分到多臺服務(wù)器的虛擬節(jié)點上。

綜上，V2 版算法通過虛擬節(jié)點的方式完美解決了數(shù)據(jù)傾斜的問題，是不是很巧妙？不過俗話說，紙上得來終覺淺，絕知此事要躬行，我們需要實踐才能真正寫出正確的一致性哈希算法。

比方說，應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)哈希環(huán)？如果哈希函數(shù)出現(xiàn)哈希沖突怎么辦？真正寫代碼的時候，這些細(xì)節(jié)問題都是要考慮的。

下面我們就結(jié)合代碼和實際場景來看看一致性哈希算法的真實應(yīng)用。

實際場景分析

就以消息隊列的消費模型為例吧，我在前文用消息隊列做一個聯(lián)機(jī)游戲介紹過 Apache Pulsar 的消費模型，Pulsar 通過 subscription 的抽象提供多種訂閱模式，其中 key_shared 模式比較有意思：

每條消息會有一個 key，Pulsar 可以根據(jù)這個 key 分發(fā)消息，保證帶有相同 key 的消息分發(fā)到同一個消費者上。

官網(wǎng)的這幅圖比較好理解，圖中的K就是指消息的 key，V就是指消息的數(shù)據(jù)：

通過某些算法，所有的消息都會有消費者去處理，比如上圖就是consumerA負(fù)責(zé)處理key=K3的消息，consumerB負(fù)責(zé)處理key=K1的消息，consumerC負(fù)責(zé)處理key=K2的消息。

當(dāng)然，如果有 consumer 加入或者離開，消息的分配會重置。比如consumerA下線，那么key=K3的消息會被分配給其他消費者消費；如果有新的消費者consumerD加入，那么當(dāng)前的分配方案也可能會改變。

簡單總結(jié)就是：

1、在沒有 consumer 加入或者離開的前提下，保證 key 相同的消息都會分配到固定的 consumer，不能一會兒分配到consumerA，一會兒分配給consumerB。

2、如果有 consumer 加入或者離開，可以重新進(jìn)行分配每個 consumer 負(fù)責(zé)的 key，要求盡量把 key 平均分配給 consumer，避免出現(xiàn)某些 consumer 負(fù)責(zé)過多 key 的情況導(dǎo)致數(shù)據(jù)傾斜。

3、以上兩個操作，尤其是給 consumer 重新分配 key 的操作，效率要盡可能高。

對于上述場景，你如何設(shè)計分配算法，把這些帶有 key 的消息高效地、均勻地分配給所有 consumer 呢？

我們來看看 Pulsar 是如何做的，官網(wǎng)對這部分的實現(xiàn)原理描述的比較清楚，參考鏈接如下：

https://pulsar.apache.org/docs/next/concepts-messaging/#key_shared

結(jié)合我之前在學(xué)習(xí)開源項目的套路中介紹的查看源碼背景信息的技巧，可以發(fā)現(xiàn) Pulsar 的 key_shared 模式的消費者實現(xiàn)其實是經(jīng)歷了一些演進(jìn)的。

最開始的默認(rèn)實現(xiàn)方式叫做 Auto-split Hash Range，即抽象出來一個[0, 65535]的哈希區(qū)間，讓每個 consumer 負(fù)責(zé)這個區(qū)間的一部分。比如有C1~C44 個 consumer，那么它們會平分整個哈希區(qū)間：

016,38432,76849,15265,536
|-------C3------|-------C2------|-------C4------|-------C1------|

然后我們可以對每條消息的 key 計算哈希值并求模映射到[0, 65535]的區(qū)間中，這樣我們就可以選出負(fù)責(zé)處理這條消息的 consumer 了，而且 key 相同的消息總會分配到這個 consumer 上。

那么如果有 consumer 上線或者下線怎么處理呢？

如果有 consumer 下線，那么它負(fù)責(zé)的哈希區(qū)間會直接交給右側(cè)的 consumer。比如上例中C4下線，那么哈希區(qū)間就會變成這樣：

016,38432,76865,536
|-------C3------|-------C2------|----------------C1---------------|

當(dāng)然這里也有個特殊情況，就是下線的那個 consumer 右邊沒有其他 consumer 的情況，我們可以讓它左邊的 consumer 頂上來。比如現(xiàn)在的C1下線，那么就讓左邊的C2負(fù)責(zé)C1的區(qū)間：

016,38465,536
|-------C3------|--------------------------C2-----------------------|

如果有 consumer 上線，那么算法可以把最長的哈希區(qū)間平分，分一半給新來的 consumer。比如此時C5上線，我們就可以把C2負(fù)責(zé)的一半哈希區(qū)間分給C5：

016,38440,96065,536
|-------C3------|-----------C5-----------|----------C2----------|

這就是 Auto-split Hash Range 的方案，不算復(fù)雜，具體的實現(xiàn)可以看 Pulsar 源碼中HashRangeAutoSplitStickyKeyConsumerSelector這個類，我在這里就不列舉了。

這個方案的問題主要還是數(shù)據(jù)傾斜，比如上面的例子出現(xiàn)的這種情況，C2的負(fù)載顯然比C3多很多：

016,38465,536
|-------C3------|--------------------------C2-----------------------|

按照這個算法邏輯，一些 consumer 下線后很容易產(chǎn)生這種數(shù)據(jù)傾斜的情況，所以這個解決方案并不能均勻地把 key 分配給 consumer。

那么如何優(yōu)化這個算法呢？就要用到一致性哈希算法了。

一致性哈希算法的實現(xiàn)

結(jié)合我在本文開頭對一致性哈希算法的介紹，應(yīng)該很容易想到優(yōu)化思路。其實現(xiàn)在 Pulsar 就是使用一致性哈希算法來實現(xiàn)的 key_shared 訂閱。

首先抽象出一個值在[0, MAX_INT]的哈希環(huán)，然后給每個 consumer 分配 100 個虛擬節(jié)點映射到這個哈希環(huán)上。接下來，我們把 key 的哈希值放在哈希環(huán)上，順時針方向找到最近的 consumer 虛擬節(jié)點，也就找到了負(fù)責(zé)處理這個 key 的 consumer。

哈希環(huán)我們一般用 TreeMap 實現(xiàn)，直接看 Pulsar 源碼中ConsistentHashingStickyKeyConsumerSelector的實現(xiàn)吧，我提取了其中的關(guān)鍵邏輯并添加了詳細(xì)的注釋：

classConsistentHashingStickyKeyConsumerSelector{
//哈希環(huán)，虛擬節(jié)點的哈希值->consumer列表
//因為存在哈希沖突，多個虛擬節(jié)點可能映射到同一個哈希值，所以值為List類型
NavigableMap>hashRing=newTreeMap<>();
//每個consumer有100個虛擬節(jié)點
intnumberOfPoints=100;

//將該consumer的100個虛擬節(jié)點添加到哈希環(huán)上
publicvoidaddConsumer(Consumerconsumer){
for(inti=0;i());
hashRing.get(hash).add(consumer);
}
}

//在哈希環(huán)上刪除該consumer的所有虛擬節(jié)點
publicvoidremoveConsumer(Consumerconsumer){
for(inti=0;i>ceilingEntry=hashRing.ceilingEntry(hash);
ListconsumerList;
if(ceilingEntry!=null){
consumerList=ceilingEntry.getValue();
}else{
//哈希環(huán)順時針轉(zhuǎn)一圈，回到開頭尋找第一個節(jié)點
consumerList=hashRing.firstEntry().getValue();
}
//保證相同的key都會分配到同一個consumer
returnconsumerList.get(hash%consumerList.size());
}
}

當(dāng)消息被發(fā)送過來后，Pulsar 可以通過select方法選擇對應(yīng)的 consumer 來處理數(shù)據(jù)；當(dāng)新的 consumer 上線時，可以通過addConsumer將它的虛擬節(jié)點放到哈希環(huán)上并開始接收消息；當(dāng)有 consumer 下線時，可以通過removeConsumer將它的虛擬節(jié)點從哈希環(huán)上摘除，由其他 consumer 承擔(dān)它的工作。

因為每個 consumer 有 100 個虛擬節(jié)點，所以在 consumer 下線時，負(fù)載其實是均勻地分配給了其他 consumer，因此一致性哈希算法能夠解決之前 Auto-split Hash Range 方案數(shù)據(jù)傾斜的問題。

審核編輯：劉清