五張圖理解一致性Hash原理

啥是Hash值?

hash(散列，雜糅)函數，是將任意長度的數據映射到有限長度的域上。直觀解釋起來，就是對一串數據m進行雜糅，輸出另一段固定長度的數據h，作為這段數據的特徵(指紋)。

如何保證無論數據塊m多大，其輸出值h為固定長度?

將m分成固定長度(如128位)，依次進行hash運算，然後用不同的方法迭代即可(如前一塊的hash值與後一塊的hash值進行異或)。如果不夠128位用0補全或者用1補全隨意，演算法中約定就可以了。

為了解決什麼問題?

分散式系統中實現負載均衡，常常需要將同一個客戶端發送的請求指定到同一個伺服器端來做處理，包括緩存，Session持久等場景。

Hash取模方式

最開始的方式是通過對客戶端某特徵的Hash值取模，例如：對客戶端IP地址Hash後取模，根據模尋找伺服器。

Hash取模方式的弊端

這種方式在伺服器個數固定不變時沒有問題。如果需要彈性擴容或故障停機的情況下，原來的取模公式就會發生變化：Hash(IP) % 4會變成Hash(IP) % ?。此時IP地址經過取模運算的結果將發生很大變化，根據模值獲取的伺服器也會變得不可控。

一致性Hash的原理

為避免上述Hash取模方式的問題，提出一致性Hash解決方案。目的是當伺服器個數發生變動時，儘可能少的影響客戶端到伺服器的映射關係。

環形Hash空間

通常的Hash演算法都是將value映射為一個32位的key值，也即是0 ~ 2^32-1的數值空間。我們可以將這個空間想像成一個首尾相連的環。

把伺服器映射到環形空間上

利用伺服器的某特徵的Hash值，將伺服器映射到環形空間上。伺服器與伺服器的間隔即是各伺服器的管理區域。

把客戶端映射到環形空間

將客戶端映射到環形空間，形成伺服器和客戶端Hash值的交替出現情況。

客戶端逆時針(順時針也行，只要保證規則一致即可)找到離自己最近的伺服器Hash值，算作客戶端與此伺服器建立映射關係。

添加伺服器節點

Server#4為新增伺服器節點，將原來Server#3到Server#0管轄的區域分割成兩部分，受影響的客戶端只有Client#2。它由原來與Server#0建立的映射關係變成與Server#4建立映射關係。

同理，刪除伺服器節點也只會影響部分節點。

一致性Hash就是將原來點到點的映射關係變成點到線的映射關係，從而減少因伺服器個數變化引起的映射關係變化。

一致性Hash的優化

為了盡量實現各伺服器的負載均衡，在上述基礎上，將同一台伺服器影分身成多個虛擬節點來達到負載均衡的目的。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！