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

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

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

一致性哈希算法簡介

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

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

其原理就是抽象出一個哈希環，把服務器節點的 id 通過哈希函數映射到這個哈希環上：

同時，把需要處理的數據也通過哈希函數映射到這個哈希環上，然后順時針找，遇到的第一個服務器節點來負責處理這個數據：

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

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

即某些服務器節點要負責的哈希環很長，而其他服務器負責的哈希環很短。這就會導致某些服務器負載很高，而其他的服務器負載很低，很不均衡。

而且，當某個服務器節點下線后，它的負載會順時針轉移到下一個節點上，那么某些特定的節點下線順序很可能導致某些服務器節點負責的哈希環不斷加長，負載不斷增加。專業點說，這就是「數據傾斜」。

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

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

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

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

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

比方說，應該用什么數據結構實現哈希環？如果哈希函數出現哈希沖突怎么辦？真正寫代碼的時候，這些細節問題都是要考慮的。

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

實際場景分析

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

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

官網的這幅圖比較好理解，圖中的K就是指消息的 key，V就是指消息的數據：

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

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

簡單總結就是：

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

2、如果有 consumer 加入或者離開，可以重新進行分配每個 consumer 負責的 key，要求盡量把 key 平均分配給 consumer，避免出現某些 consumer 負責過多 key 的情況導致數據傾斜。

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

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

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

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

結合我之前在學習開源項目的套路中介紹的查看源碼背景信息的技巧，可以發現 Pulsar 的 key_shared 模式的消費者實現其實是經歷了一些演進的。

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

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

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

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

如果有 consumer 下線，那么它負責的哈希區間會直接交給右側的 consumer。比如上例中C4下線，那么哈希區間就會變成這樣：

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

當然這里也有個特殊情況，就是下線的那個 consumer 右邊沒有其他 consumer 的情況，我們可以讓它左邊的 consumer 頂上來。比如現在的C1下線，那么就讓左邊的C2負責C1的區間：

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

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

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

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

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

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

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

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

一致性哈希算法的實現

結合我在本文開頭對一致性哈希算法的介紹，應該很容易想到優化思路。其實現在 Pulsar 就是使用一致性哈希算法來實現的 key_shared 訂閱。

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

哈希環我們一般用 TreeMap 實現，直接看 Pulsar 源碼中ConsistentHashingStickyKeyConsumerSelector的實現吧，我提取了其中的關鍵邏輯并添加了詳細的注釋：

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

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

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

當消息被發送過來后，Pulsar 可以通過select方法選擇對應的 consumer 來處理數據；當新的 consumer 上線時，可以通過addConsumer將它的虛擬節點放到哈希環上并開始接收消息；當有 consumer 下線時，可以通過removeConsumer將它的虛擬節點從哈希環上摘除，由其他 consumer 承擔它的工作。

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

審核編輯：劉清