一致性 Hash 算法原理和應用梳理

前幾天在技術羣裏，看到有小夥伴在討論一致性 hash 算法的問題，正好今天以這個爲話題，簡單介紹下它的原理。下邊我們以分佈式緩存中經典場景舉例，面試中也是經常提及的一些話題，看看什麼是一致性 hash 算法以及它有那些過人之處。

一、背景

考慮這麼一種場景：我們有三臺緩存服務器編號 node0、node1、node2，現在有 3000 萬個 key，希望可以將這些個 key 均勻的緩存到三臺機器上，你會想到什麼方案呢？

我們可能首先想到的方案是：取模算法 hash（key）%N，即：對 key 進行 hash 運算後取模，N 是機器的數量。

這樣，對 key 進行 hash 後的結果對 3 取模，得到的結果一定是 0、1 或者 2，正好對應服務器 node0、node1、node2，存取數據直接找對應的服務器即可，簡單粗暴，完全可以解決上述的問題。

取模算法雖然使用簡單，但對機器數量取模，在集羣擴容和收縮時卻有一定的侷限性：因爲在生產環境中根據業務量的大小，調整服務器數量是常有的事**，而****服務器數量 N 發生變化後 hash（key）%N 計算的結果也會隨之變化**！

比如：一個服務器節點掛了，計算公式從 hash（key）% 3 變成了 hash（key）% 2，結果會發生變化，此時想要訪問一個 key，這個 key 的緩存位置大概率會發生改變，那麼之前緩存 key 的數據也會失去作用與意義。

大量緩存在同一時間失效，造成緩存的雪崩，進而導致整個緩存系統的不可用，這基本上是不能接受的。爲了解決優化上述情況，一致性 hash 算法應運而生~

二、一致性 Hash 算法原理

一致性哈希算法在 1997 年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠儘可能小地改變已存在的服務請求與處理請求服務器之間的映射關係；

一致性哈希解決了簡單哈希算法在分佈式哈希表（Distributed Hash Table，DHT）中存在的動態伸縮等問題。微信搜索公衆號：Java 後端編程，回覆：java 領取資料 。

一致性 hash 算法本質上也是一種取模算法。不過，不同於上邊按服務器數量取模，一致性 hash 是對固定值 2^32 取模。

IPv4 的地址是 4 組 8 位 2 進制數組成，所以用 2^32 可以保證每個 IP 地址會有唯一的映射。

我們可以將這 2^32 個值抽象成一個圓環⭕️，圓環的正上方的點代表 0，順時針排列，以此類推：1、2、3… 直到 2^32-1，而這個由 2 的 32 次方個點組成的圓環統稱爲 hash 環。

在對服務器進行映射時，使用 hash（服務器 ip）% 2^32，即：使用服務器 IP 地址進行 hash 計算，用哈希後的結果對 2^32 取模，結果一定是一個 0 到 2^32-1 之間的整數。

而這個整數映射在 hash 環上的位置代表了一個服務器，依次將 node0、node1、node2 三個緩存服務器映射到 hash 環上。

在對對應的 Key 映射到具體的服務器時，需要首先計算 Key 的 Hash 值：hash（key）% 2^32。

注：此處的 Hash 函數可以和之前計算服務器映射至 Hash 環的函數不同，只要保證取值範圍和 Hash 環的範圍相同即可（即：2^32）

將 Key 映射至服務器遵循下面的邏輯：

從緩存對象 key 的位置開始，沿順時針方向遇到的第一個服務器，便是當前對象將要緩存到的服務器。

假設我們有 “semlinker”、“kakuqo”、“lolo”、“fer” 四個對象，分別簡寫爲 o1、o2、o3 和 o4。

首先，使用哈希函數計算這個對象的 hash 值，值的範圍是 [0，2^32-1]：

圖中對象的映射關係如下：

hash(o1) = k1; hash(o2) = k2;
hash(o3) = k3; hash(o4) = k4;

同時 3 臺緩存服務器，分別爲 CS1、CS2 和 CS3：

則可知，各對象和服務器的映射關係如下：

K1 => CS1
K4 => CS3
K2 => CS2
K3 => CS1

即：

以上便是一致性 Hash 的工作原理。

可以看到，一致性 Hash 就是：將原本單個點的 Hash 映射，轉變爲了在一個環上的某個片段上的映射！

三、服務器擴縮容應用場景

下面我們來看幾種服務器擴縮容的場景：

假設 CS3 服務器出現故障導致服務下線，這時原本存儲於 CS3 服務器的對象 o4，需要被重新分配至 CS2 服務器，其它對象仍存儲在原有的機器上：

此時受影響的數據只有 CS2 和 CS3 服務器之間的部分數據！

假如業務量激增，我們需要增加一臺服務器 CS4，經過同樣的 hash 運算，該服務器最終落於 t1 和 t2 服務器之間，具體如下圖所示：

此時，只有 t1 和 t2 服務器之間的部分對象需要重新分配。

在以上示例中只有 o3 對象需要重新分配，即它被重新到 CS4 服務器。

在前面我們已經說過：如果使用簡單的取模方法，當新添加服務器時可能會導致大部分緩存失效，而使用一致性哈希算法後，這種情況得到了較大的改善，因爲只有少部分對象需要重新分配！

四、數據偏斜與平衡問題

在上面給出的例子中，各個服務器幾乎是平均被均攤到 Hash 環上。

但是在實際場景中很難選取到一個 Hash 函數這麼完美的將各個服務器散列到 Hash 環上。

此時，在服務器節點數量太少的情況下，很容易因爲節點分佈不均勻而造成數據傾斜問題。

如下圖被緩存的對象大部分緩存在 node-4 服務器上，導致其他節點資源浪費，系統壓力大部分集中在 node-4 節點上，這樣的集羣是非常不健康的：

同時，還有另一個問題：

在上面新增服務器 CS4 時，CS4 只分擔了 CS1 服務器的負載，服務器 CS2 和 CS3 並沒有因爲 CS4 服務器的加入而減少負載壓力；如果 CS4 服務器的性能與原有服務器的性能一致甚至可能更高，那麼這種結果並不是我們所期望的。

針對上面的問題，我們可以通過：引入虛擬節點來解決負載不均衡的問題：即將每臺物理服務器虛擬爲一組虛擬服務器，將虛擬服務器放置到哈希環上，如果要確定對象的服務器，需先確定對象的虛擬服務器，再由虛擬服務器確定物理服務器。

如下圖所示：

在圖中：o1 和 o2 表示對象，v1~v6 表示虛擬服務器，s1~s3 表示實際的物理服務器。

虛擬節點的 hash 計算通常可以採用：對應節點的 IP 地址加數字編號後綴 hash（10.24.23.227#1) 的方式；

舉個例子，node-1 節點 IP 爲 10.24.23.227，正常計算 node-1 的 hash 值：

假設我們給 node-1 設置三個虛擬節點，node-1#1、node-1#2、node-1#3，對它們進行 hash 後取模：

注意：

五、一致性 Hash 算法使用場景

一致性 hash 在分佈式系統中應該是實現負載均衡的首選算法，它的實現比較靈活，既可以在客戶端實現，也可以在中間件上實現，比如日常使用較多的緩存中間件 memcached 和 redis 集羣都有用到它。

memcached 的集羣比較特殊，嚴格來說它只能算是僞集羣，因爲它的服務器之間不能通信，請求的分發路由完全靠客戶端來的計算出緩存對象應該落在哪個服務器上，而它的路由算法用的就是一致性 hash。

還有 redis 集羣中 hash 槽的概念，雖然實現不盡相同，但思想萬變不離其宗，看完本篇的一致性 hash，你再去理解 redis 槽位就輕鬆多了。

其它的應用場景還有很多：

六、總結

本文拋磚引玉的講解了一致性 Hash 算法的原理及應用場景介紹。

Hash 算法作爲一種活動開發經常遇到的算法，我們在使用中不僅僅要知道這種算法背後真正的原理，纔可以在使用上做到有的放矢。Hash 的相關知識還有很多，有興趣的同學可以繼續深入研究。

大家在實際使用時，可以根據需要，搭配實際的組件！

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

猜你喜歡