一致性哈希演算法原理詳解

一、普通 hash 演算法 (取模演算法)：

在了解一致性哈希演算法之前，我們先了解一下快取中的一個應用場景，了解了這個應用場景之后，再來理解一致性哈希演算法，就容易多了，也更能體現出一致性哈希演算法的優點，那么，我們先來描述一下這個經典的分布式快取的應用場景，

1、普通 hash演算法 與 使用場景描述：

假設我們有三臺快取服務器，用于快取圖片，我們為這三臺快取服務器編號為 0號、1號、2號，現在有3萬張圖片需要快取，我們希望這些圖片被均勻的快取到這3臺服務器上，以便它們能夠分攤快取的壓力，也就是說，我們希望每臺服務器能夠快取1萬張左右的圖片，那么我們應該怎樣做呢？常見的做法是對快取項的鍵進行哈希，將hash后的結果對快取服務器的數量進行取模操作，通過取模后的結果，決定快取項將會快取在哪一臺服務器上

我們舉例說明，以剛才描述的場景為例，假設圖片名稱是不重復的，那我們就可以使用圖片名稱作為訪問圖片的key，使用如下公式，計算出圖片應該存放在哪臺服務器上，

hash（圖片名稱）% N

當我們對同一個圖片名稱做相同的哈希計算時，得出的結果應該是不變的，如果我們有3臺服務器，使用哈希后的結果對3求余，那么余數一定是0、1或者2；如果求余的結果為0， 就把當前圖片快取在0號服務器上，如果余數為1，就快取在1號服務器上，以此類推；同理，當我們訪問任意圖片時，只要再次對圖片名稱進行上述運算，即可得出圖片應該存放在哪一臺快取服務器上，我們只要在這一臺服務器上查找圖片即可，如果圖片在對應的服務器上不存在，則證明對應的圖片沒有被快取，也不用再去遍歷其他快取服務器了，通過這樣的方法，即可將3萬張圖片隨機的分布到3臺快取服務器上了，而且下次訪問某張圖片時，直接能夠判斷出該圖片應該存在于哪臺快取服務器上，我們暫時稱上述演算法為 HASH 演算法或者取模演算法，取模演算法的程序可以用下圖表示：

2、普通 hash 演算法的缺陷：

上述HASH演算法時，會出現一些缺陷：如果服務器已經不能滿足快取需求，就需要增加服務器數量，假設我們增加了一臺快取服務器，此時如果仍然使用上述方法對同一張圖片進行快取，那么這張圖片所在的服務器編號必定與原來3臺服務器時所在的服務器編號不同，因為除數由3變為了4，最終導致所有快取的位置都要發生改變，也就是說，當服務器數量發生改變時，所有快取在一定時間內是失效的，當應用無法從快取中獲取資料時，則會向后端服務器請求資料；同理，假設突然有一臺快取服務器出現了故障，那么我們則需要將故障機器移除，那么快取服務器數量從3臺變為2臺，同樣會導致大量快取在同一時間失效，造成了快取的雪崩，后端服務器將會承受巨大的壓力，整個系統很有可能被壓垮，為了解決這種情況，就有了一致性哈希演算法，

二、一致性哈希演算法：

1、什么是一致性 hash 演算法：

一致性哈希演算法也是使用取模的方法，但是取模演算法是對服務器的數量進行取模，而一致性哈希演算法是對 2^32 取模，具體步驟如下：

• 步驟一：一致性哈希演算法將整個哈希值空間按照順時針方向組織成一個虛擬的圓環，稱為 Hash 環；
• 步驟二：接著將各個服務器使用 Hash 函式進行哈希，具體可以選擇服務器的IP或主機名作為關鍵字進行哈希，從而確定每臺機器在哈希環上的位置
• 步驟三：最后使用演算法定位資料訪問到相應服務器：將資料key使用相同的函式Hash計算出哈希值，并確定此資料在環上的位置，從此位置沿環順時針尋找，第一臺遇到的服務器就是其應該定位到的服務器

下面我們使用具體案例說明一下一致性哈希演算法的具體流程：

（1）步驟一：哈希環的組織：

我們將 2^32 想象成一個圓，像鐘表一樣，鐘表的圓可以理解成由60個點組成的圓，而此處我們把這個圓想象成由2^32個點組成的圓，示意圖如下：

圓環的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4、5、6……直到2^32-1,也就是說0點左側的第一個點代表2^32-1，我們把這個由 2^32 個點組成的圓環稱為hash環，

（2）步驟二：確定服務器在哈希環的位置：

哈希演算法：hash（服務器的IP） % 2^32

上述公式的計算結果一定是 0 到 2^32-1 之間的整數，那么上圖中的 hash 環上必定有一個點與這個整數對應，所以我們可以使用這個整數代表服務器，也就是服務器就可以映射到這個環上，假設我們有 ABC 三臺服務器，那么它們在哈希環上的示意圖如下：

（3）步驟三：將資料映射到哈希環上：

我們還是使用圖片的名稱作為 key，所以我們使用下面演算法將圖片映射在哈希環上：hash（圖片名稱） % 2^32，假設我們有4張圖片，映射后的示意圖如下，其中橘黃色的點表示圖片：

那么，怎么算出上圖中的圖片應該被快取到哪一臺服務上面呢？我們只要從圖片的位置開始，沿順時針方向遇到的第一個服務器就是圖片存放的服務器了，最終，1號、2號圖片將會被快取到服務器A上，3號圖片將會被快取到服務器B上，4號圖片將會被快取到服務器C上，

2、一致性 hash 演算法的優點：

前面提到，如果簡單對服務器數量進行取模，那么當服務器數量發生變化時，會產生快取的雪崩，從而很有可能導致系統崩潰，而使用一致性哈希演算法就可以很好的解決這個問題，因為一致性Hash演算法對于節點的增減都只需重定位環空間中的一小部分資料，只有部分快取會失效，不至于將所有壓力都在同一時間集中到后端服務器上，具有較好的容錯性和可擴展性，

假設服務器B出現了故障，需要將服務器B移除，那么移除前后的示意圖如下圖所示：

在服務器B未移除時，圖片3應該被快取到服務器B中，可是當服務器B移除以后，按照之前描述的一致性哈希演算法的規則，圖片3應該被快取到服務器C中，因為從圖片3的位置出發，沿順時針方向遇到的第一個快取服務器節點就是服務器C，也就是說，如果服務器B出現故障被移除時，圖片3的快取位置會發生改變，但是，圖片4仍然會被快取到服務器C中，圖片1與圖片2仍然會被快取到服務器A中，這與服務器B移除之前并沒有任何區別，這就是一致性哈希演算法的優點，

3、hash 環的傾斜與虛擬節點：

一致性哈希演算法在服務節點太少的情況下，容易因為節點分部不均勻而造成資料傾斜問題，也就是被快取的物件大部分集中快取在某一臺服務器上，從而出現資料分布不均勻的情況，這種情況就稱為 hash 環的傾斜，如下圖所示：

hash 環的傾斜在極端情況下，仍然有可能引起系統的崩潰，為了解決這種資料傾斜問題，一致性哈希演算法引入了虛擬節點機制，即對每一個服務節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛擬節點，一個實際物理節點可以對應多個虛擬節點，虛擬節點越多，hash環上的節點就越多，快取被均勻分布的概率就越大，hash環傾斜所帶來的影響就越小，同時資料定位演算法不變，只是多了一步虛擬節點到實際節點的映射，具體做法可以在服務器ip或主機名的后面增加編號來實作，加入虛擬節點以后的hash環如下：

參考文章：https://www.zsythink.net/archives/1182