一致性哈希算法原理解析

0 前言

本期和大家一起分享一個設計思路非常巧妙的負載均衡策略——一致性哈希算法.

本系列分爲理論篇和實戰篇兩部分：

本期理論篇的分享大綱如下：

1 問題背景

在正式開講一致性哈希算法之前，我們先從一個場景問題開始切入.

1.1 狀態服務

首先，我們需要先理清楚兩個概念——何謂 ”有狀態服務 “，何謂” 無狀態服務“？

對於這類無狀態服務而言，一筆請求被分發到哪個節點並不重要，因爲執行邏輯都是相同的. 因此無狀態服務集羣倘若需要執行橫向擴縮容操作，是很靈活自由的.

針對於這類服務，由於其存儲了狀態數據，因此在對集羣進行橫向分治（爲防止單點故障而對數據進行冗餘備份）時，需要考慮數據的一致性問題；在對集羣進行縱向分治（爲提高集羣整體性能上限，不同節點各自分擔部分數據存儲工作，共同構成全集）時，需要明確數據與所從屬節點之間的映射關係.

針對於無狀態服務，對應的負載均衡流程是要簡單很多的. 比如我們可以採用輪詢算法（RR，Round Robin）、加權輪詢算法（WRR，Weighted Round Robin）、平滑加權輪詢算法（SWRR，Smoth Round Robin）實現集羣內各節點對請求流量的平均分配.

然而對於有狀態服務而言，倘若存在縱向分治策略，那麼我們就需要維護好狀態數據與所從屬之間的映射關係. 一旦集羣發生擴縮容，節點數量發生變更，對應的映射關係就需要發生變化，對應的狀態數據就要發生遷移，這會是一個很複雜且笨重的流程. 而咱們今天所探討的一致性哈希算法，且核心價值正是爲了有效地降低有狀態服務集羣擴縮容流程的數據遷移成本.

有關於這一點，我們下面先從普通的負載均衡策略開始探討，理清其中存在的侷限性後，再引入一致性哈希算法進行對比分析.

1.2 縱向分治

我們來聊一聊有關” 縱向分治 “的問題.

我們知道，對於單個服務節點而言，受限於自身的硬件條件，會存在對應於某個水平的性能瓶頸. 倘若完全侷限於單兵作戰的思路，那麼這個節點本身的瓶頸就會成爲整個系統的天花板.

但是倘若我們引入了縱向分治的策略，那麼這塊天花板就還能有提高的空間.

打個比方，已知總工作量爲 100，倘若我們只讓一個人參與工作，那麼這個人需要承擔的工作量就是 100；倘若我們讓 10 個人參與協作，對工作進行平均拆分，每個人負責其中的一小部分，那麼每個人需要承擔的工作量就大約是 100/10 = 10.

當然，在真實場景中，這種縱向分治的策略無法在性能上帶來這種線性的提升效率，因爲在多人協作時，難免在邊界分配、交接工作、結果聚合等環節會存在效率的損耗. 但即便如此，這種縱向擴容分治的思路也能在很大程度上減輕每個獨立節點所需要承擔的工作強度，因此能夠提高整個系統的性能上限.

我們可以通過哈希散列的方式實現數據的縱向分治，基於哈希函數的離散性，保證每個節點分配的數據量均可能趨於平均：

1.3 帶權分治

在實際場景中，不同節點的性能可能存在差距. 我們希望做到能者多勞，讓性能好的節點多完成一些任務，性能差的節點少承擔一些工作. 此時，我們可以給每個節點設置一個權重值，用於反映其性能水平的強弱.

接下來我們可以設置一條水平軸，每個節點根據其權重值大小在軸上佔據對應的比例分區. 接下來每當有數據到來，我們都會根據數據的 key 取得 hash 值並對水平軸的總長度取模，找到其在水平軸上的刻度位置，再根據該刻度所從屬的分區，推斷出這筆數據應該從屬於哪一個節點.

1.4 數據遷移

下面我們來聊一聊，有狀態服務所存在的痛點問題：集羣擴縮容時存在的數據遷移流程.

通過 1.2 小節介紹的縱向分治流程，我們明白每條數據和所從屬的節點之間會一個明確且穩定的映射關係. 以我們通常採用的哈希散列的方案爲例，數據所從屬的節點 index 會與集羣節點的總數有關（ 節點 index = 數據 hash 值 % 節點個數），所以這個映射關係能生效的前提是，集羣節點的數量需要維持不變.

換言之，一旦集羣需要執行擴縮容流程，集羣節點數量變更後，原有的映射關係就會被破壞. 爲了繼續維護這份映射規則，我們需要執行數據遷移操作，將舊數據遷移到能夠滿足新映射關係的對應位置. 這必然會是一個很重的遷移流程，涉及影響的範圍是全量的舊節點.

2 一致性哈希

梳理完傳統負載均衡方案的流程以及存在的痛點後，下面引入我們今天的主題——一致性哈希算法.

2.1 哈希環

2.1.1 哈希環構造

現在，我們需要打破固有的數據與節點之間的點對點映射關係.

我們首先構造出一個哈希環（Hash Ring）：

哈希環的構造圖如下所示：

2.1.2 節點入環

接下來，每個節點需要在哈希環中找到找到屬於自己的位置. 入環的方式是，針對於節點的標識鍵 index 取 hash 值，然後使用該 hash 值對 2^32 取模，最後得到的結果就是該節點在哈希環上對應的位置.

遵循上述流程，我們可以依次把集羣中的各個節點加入哈希環中.

2.1.3 數據出 / 入環

在讀數據與寫數據的流程中，核心是要找到與這筆數據所歸屬的節點 index，這裏我們採取的方式是：

這裏需要注意的是，哈希環是首尾相連的，因此倘若來到 2^32 - 1 的位置都沒找到目標節點，則需要從 0（2^32）開始接着向後檢索.

按照上述流程，只要在哈希環中至少存在一個節點，難麼就一定能爲每筆數據找到在哈希環中所應從屬的節點.

2.2 數據遷移

引入哈希環之後，在數據與節點映射規則上沒有傳統方案來得那麼直觀，但是在數據遷移流程中，這種環狀結構的優勢就能體現出來了.

2.2.1 新增節點

以下圖對應的新增節點的場景爲例，我們對集羣擴容的流程加以梳理：

背景： 原本集羣存在存在 A、B、C、D、E、F 六個節點，已分別添加到哈希換中，位置如下圖所示.

變量： 此時需要新增一個節點 G，經過哈希散列和取模運算後，節點 G 在哈希環上的位置位於 B 與 C 之間，我們把位置關係記爲 B-G-C

下面是對新增節點流程的梳理：

至此，新增節點場景下的數據遷移動作完成.

2.2.2 刪除節點

刪除節點時的處理思路與新增節點流程相類似，我們也梳理一下：

背景： 原本集羣中存在 A、B、C、D、E、F、G 七個節點，均已添加到哈希環中

變量： 現在需要刪除其中的節點 G，且節點 G 在哈希環上位於節點 B、C 之間.

下面是刪除節點的執行流程：

至此，刪除節點場景下的數據遷移操作完成.

我們將 2.2 小節中一致性哈希算法下的數據遷移操作與 1.4 小節中的方案就行對比，可以很直觀地感受到前者的核心優勢，這本質上是因爲這種環狀結構加 ceiling（向上開放尋址） 的方式，使得數據所從屬的節點 index 不再與集羣的節點總數強相關，而僅僅取決於數據與節點在哈希環上的拓撲結構，最終因節點變更而引起數據遷移時，也僅僅需要對局部位置進行變更即可，而不需要將影響面放大到全局.

2.3 負載均衡

那麼聊到這裏方案是否就已經嚴絲合縫，不存在任何問題了呢？答案是否定的.

在 2.1 小節中我們提到，每個節點進入哈希環時，所屬的位置是根據節點 index 取哈希，並進一步對哈希環長度（2^32） 取模後得到的.

我們知道，哈希具有離散的性質，能保證在輸入內容不同時，輸出結果會均勻地散佈在輸出域範圍之內. 然而這種所謂的 “離散” 和“均勻”是建立在數據樣本足夠大的情況下，倘若集羣節點數量很少，那麼就很可能出現節點位置分佈不均勻的情況.

如下圖所示，倘若在哈希環中僅存在 A、B、C 三個節點，其中 A-B、C-A 的相對距離都很短，但是 B-C 的相對距離則很遠. 在這種情況下就會導致，在節點 A 和節點 B 中只能分配到少陵的數據，而絕大部分的數據都會被集中分配到節點 C 中.

產生上述問題的根本原因在於，各個節點分配到的數據量，其實取決於其和上一個節點之間相對距離的長短.

2.4 虛擬節點

2.4.1 誤差彌合

針對於 2.3 小節中提出的負載均衡問題，在一致性哈希算法中給出的應對策略是虛擬節點路由的方案.

前面我們提到，哈希散列本身是具有離散性的，節點數據分配不均的問題通常只會發生在集羣節點數量較少的情況下. 那麼，倘若我們採用某種手段，將節點數量放大，那麼更大的數據樣本就自然而然地能夠彌合或者縮小這部分誤差所產生的影響，進一步突顯出哈希函數的離散性質.

虛擬節點策略正是這樣來做的：

基於以上流程，只要我們合理設置好真實節點到虛擬節點之間數量的放大倍數，那麼最終位於哈希環上的代理節點的數量就會足夠多，這一系列節點在哈希環上的位置就會越均勻，負載均衡的效果就會越好.

2.4.2 帶權分治

此外，這種虛擬節點的技術方案還存在另一個優勢，就是能夠支持 1.3 小節中所提到的帶權分治的訴求.

我們可以根據各個節點的性能水平，爲其設置一個不同的權重值，最終這個權重值會作用在真實節點與虛擬節點之間的數量放大過程中，這樣我們就能保證性能強的節點擁有更高數量的虛擬節點，未來就有能力搶佔到更多的數據.

3 總結

本期和大家一起探討了一致性哈希的技術原理，涉及的技術要點如下

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/NZNVCZF8jiiPTAQ8Ievyrg

猜你喜歡