一口氣講透一致性雜湊(Hash)，助力「碼農變身」

如今雲計算、大資料、物聯網、AI的興起，使得分佈系統得到了前所未有的廣泛應用，然而由於分散式系統具有極高的複雜度，帶來了許多難題，一致性雜湊就是為了解決分散式難題之一應運而生的，本篇主要圖示講解一致性雜湊的原理及其應用，助力碼農變身。

簡而言之，一致性雜湊（Consistent Hash）是為了解決由於分散式系統中節點的增加或減少而帶來的大量失效問題，它可以有效地降低這種失效影響，從而提高分散式系統的效能和可用性。

什麼是Hash

在深入探討之前，我們先了解下什麼是hash：雜湊（hash）簡單理解就是將任意長度的輸入透過雜湊演算法轉換成固定長度的輸出，這個輸出一般稱之為雜湊碼或雜湊值。雜湊是一種對映思想，雜湊演算法即是一種函式，對比數學函式可以表示如下

f（x）=y → f（輸入）=雜湊碼

經過計算輸出的雜湊碼一般用正整數表示，它比輸入要簡短的多，因此你會遇到有些朋友會說雜湊是一種壓縮，但溫馨提醒的是這種壓縮是不可逆的，也就是說沒辦法解壓縮，所以建議把雜湊理解成對映會更妥當些。

比如把“碼農神說”作為輸入，經過雜湊演算法計算處理，輸出對應的雜湊碼“30”，也就是說雜湊碼30是原始輸入“碼農神說”的對映，這種對映關係是一一對應的（雜湊碰撞的特殊情況可暫時忽略，因為自然碰撞的機率極低），使用雜湊碼透過這種對映關係可以找到對應的原始輸入，雜湊處理及對映關係如下圖

雜湊碼是原始輸入的摘要，計算機處理摘要這種短資料比處理原始輸入的長資料更容易些、效能也更高，所以雜湊的用途十分廣泛，如安全加密、唯一標識、資料校驗等，常見的雜湊演算法有MD4、MD5、SHA等。

取餘%

在計算機中的取餘（%）操作除了判斷奇偶數等常規用途外，還可以把目標對映在一個區間範圍內，比如對5取餘，相當於把目標對映在［0，5）開閉區間內，接著上例的圖示進一步取餘如下圖示

從圖中看得出也是一種對映，但這種對映不同於雜湊對映，它並非一對一。

取餘的應用場景不僅在演算法上用途較多，在分散式系統中也廣泛應用，它進一步縮小了範圍能夠讓計算機處理更集中、狀態更一致，比如有狀態的服務叢集、快取的服務叢集等等，這些場景都需要把同一個客戶的請求定址傳送到同一個固定的節點上，這樣不僅達到了負載分散也做到了儲存狀態一致，避免了資料的複製。常見的作法比如對使用者IP進行雜湊，再以叢集中節點數量作為基數取餘，從而可以定址到已經排了序的節點並與其繫結。假想一個如下分散式快取的例子

很完美吧≧≦！但是！！

分散式系統中橫向伸縮或節點故障等，會形成節點的自動增加或刪除。比如節點B如果故障，會自動從叢集中被剔除，那麼取餘基數則變成了2，當請求過來時新的雜湊過程就會變更如下

這就比較尷尬了，使用者D和E的繫結節點變更可以理解，但使用者B和F繫結的節點也需要變更，導致之前的資料失效。那麼如果增加了一個節點D排序為4呢，你猜會怎樣

增加一個基點導致幾乎所有的繫結失效，大量失效會造成了某個時間點的網路抖動和效能急劇下降。

一致性Hash演算法

一致性hash演算法就是為了解決上述大量失效問題，失效的最主要原因是取餘的基數是根據叢集中的節點數動態變化的！一致性hash演算法把取餘的基數固定為一個常數2^32，這樣可以做到以不變應萬變。一致性hash演算法把雜湊碼對2^32取餘從而把範圍控制在［0，2^32-1］的區間範圍內，並把這個區間按照順時針的方向均勻分佈在一個圓環上，稱之為HASH環。hash環正上方的點代表0，按順時針依次是1、2、3……2^32-1。

依舊使用上述分散式快取的例子，我們首先把叢集的節點根據IP或節點名進行HASH得到雜湊碼並取餘後分布在hash環上，同時也把使用者請求根據IP地址Hash取餘分佈在hash環上，如下圖

hash環上的使用者以順時針方向尋找環上最近的節點，則此使用者的請求就繫結到該節點上，繫結對應如下圖，比如使用者A、B、C按順時針在hash環上繫結到節點A上

如果此時節點B出現了故障，則B會被從叢集中剔除，剔除後按照一致性hash演算法後繫結如下圖

可以觀察到，只會影響到D、E使用者的節點繫結，對比發現繫結的失效量相對較少，如果增加一個節點D呢，只用影響到使用者A的節點繫結，大大降低了失效率

所以一致性hash不管是在叢集中剔除節點還是增加節點，對比直接hash取餘都會降低失效率，充分體現了一致性hash演算法的優勢。

虛擬節點

如果叢集中的節點太少，則會造成資料傾斜問題，就是負載不均衡，導致有些節點超負荷

此時使用虛擬節點，透過對同一個節點使用不同雜湊演算法得到不同的雜湊碼，儘量在hash換上分佈均勻，就可以緩解資料傾斜問題，如下

不適合做什麼

一致性hash只能把失效率降到最低，但無法完全避免，它最初是針對分散式cache設計的，那麼Cache失效後畢竟資料來源裡還有資料，大不了再拿一次，資料不會丟失。但如果是有狀態服務叢集，比如session狀態，一旦丟失將會導致大面積使用者重新登入，給使用者體驗帶來極不痛快的體驗。這種問題只能透過高可用的其他方案進行彌補。

「漫畫」架構設計中的那些事

Java中異常處理的9個最佳實踐

Intellij IDEA必備外掛，提高效率的“七種武器”

接住嘍，送你個裝逼技能：JDK動態代理