作者 |LemonCoder
來源 |後端技術學堂
很多同學應該都知道什麼是雜湊函式，在後端面試和開發中會遇到「一致性雜湊」，那麼什麼是一致性雜湊呢？名字聽起來很厲害的樣子，其實原理並不複雜，這篇文章帶你徹底搞懂一致性雜湊！
進入主題前，先來一場緊張刺激的模擬面試吧。
模擬面試
面試官：看你簡歷上寫參與了一個大型專案，用到了分散式快取叢集，那你說說你們是怎麼做快取負載均衡？
萌新 ：這個我知道，我們用的是輪詢方式，第一個key 給第一個儲存節點，第二個 key 給第二個，以此類推。
面試官：還有其他解決方案嗎？
萌新：可以用雜湊函式，把請求打散隨機分配到快取叢集內機器。
面試官：考慮過這種雜湊方式負載均衡的擴充套件性和容錯性嗎？
萌新：...
面試官：回去等通知吧。
以上如有雷同，算你抄我的。
什麼是雜湊
資料結構中我們學習過雜湊表也稱為雜湊表，我們來回顧下雜湊表的定義。
雜湊表，是根據鍵直接訪問在指定儲存位置資料的資料結構。透過計算一個關於鍵的函式也稱為雜湊函式，將所需查詢的資料對映到表中一個位置來訪問記錄，加快查詢速度。這個對映函式稱做「雜湊函式」，存放記錄的陣列稱做雜湊表。
雜湊函式能使對一個資料序列的訪問過程更加迅速有效，是一種空間換時間的演算法，透過雜湊函式資料元素將被更快定位。
下圖示意了字串經過雜湊函式對映到雜湊表的過程。沒錯，輸入字串是用臉滾鍵盤打出來的：）
雜湊示意圖.png
常見的雜湊演算法有MD5、CRC 、MurmurHash 等演算法，簡單介紹一下。MD5演算法
MD5訊息摘要演算法（MD5 Message-Digest Algorithm），一種被廣泛使用的密碼雜湊函式，可以產生出一個128位（16位元組）的雜湊值（hash value），MD5演算法將資料（如一段文字）運算變為另一固定長度值，是雜湊演算法的基礎原理。由美國密碼學家 Ronald Linn Rivest設計，於1992年公開並在 RFC 1321 中被加以規範。CRC演算法
迴圈冗餘校驗（Cyclic Redundancy Check）是一種根據網路資料包或電腦檔案等資料，產生簡短固定位數校驗碼的一種雜湊函式，由 W. Wesley Peterson 於1961年發表。生成的數字在傳輸或者儲存之前計算出來並且附加到資料後面，然後接收方進行檢驗確定資料是否發生變化。由於本函式易於用二進位制的電腦硬體使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。MurmurHash
MurmurHash 是一種非加密型雜湊函式，適用於一般的雜湊檢索操作。由 Austin Appleby 在2008年發明，並出現了多個變種，與其它流行的雜湊函式相比，對於規律性較強的鍵，MurmurHash的隨機分佈特徵表現更良好。
這個演算法已經被很多開源專案使用，比如libstdc++ (4.6版)、Perl、nginx (不早於1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop等。常見雜湊方法
直接定址法：取關鍵字或關鍵字的某個線性函式值為雜湊地址，這個線性函式的定義多種多樣，沒有標準。
數字分析法：假設關鍵字是以r為基的數，並且雜湊表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成雜湊地址。
平方取中法：取關鍵字平方後的中間幾位為雜湊地址。通常在選定雜湊函式時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關，由此使隨機分佈的關鍵字得到的雜湊地址也是隨機的，取的位數由表長決定。
摺疊法：將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為雜湊地址。
取模法：取關鍵字被某個不大於雜湊表表長 m 的數 p 除後所得的餘數為雜湊地址。即 hash(key) = key % p（p<= M），不僅可以對關鍵字直接取模，也可在摺疊法、平方取中法等運算之後取模。對 p 的選擇很重要，一般取素數或 m，若 p 選擇不好，容易產生衝突。
快取系統負載均衡
在分散式叢集快取的負載均衡實現中，比如 memcached 快取叢集，需要把快取資料的 key 利用雜湊函式雜湊，這樣快取資料能夠均勻分佈到各個分散式儲存節點上，要實現這樣的負載均衡一般可以用雜湊演算法來實現。下圖演示了這一分散式儲存過程：
分散式快取雜湊儲存示意圖
普通雜湊演算法負載均衡
前面我們介紹過各種雜湊方法，不管是選擇上述哪種雜湊方法，在這個應用場景下，都是要把快取資料利用雜湊函式均勻的對映到伺服器叢集上，我們就選擇簡單的「取模法」來說明這個過程。
假設有 3 個伺服器節點編號 [0 - 2]，6 個快取鍵值對編號 [1 - 6]，則完成雜湊對映之後，三個快取資料對映情況如下：
雜湊計算公式：key %節點總數= Hash節點下標1%3=12%3=23%3=04%3=15%3=26%3=0
快取雜湊例項
每個連線都均勻的分散到了三個不同的伺服器節點上，看起來很完美！
但是，在分散式叢集系統的負載均衡實現上，這種模型有兩個問題：1. 擴充套件能力差
為了動態調節服務能力，服務節點經常需要擴容縮容。打個比方，如果是電商服務，雙十一期間的服務機器數量肯定要比平常大很多，新加進來的機器會使原來計算的雜湊值不準確，為了達到負載均衡的效果，要重新計算並更新雜湊值，對於更新後雜湊值不一致的快取資料，要遷移到更新後的節點上去。
假設新增了 1 個伺服器節點，由原來的 3 個服務節點變成 4 個節點編號 [0 - 3]，雜湊對映情況如下：
雜湊計算公式：key %節點總數= Hash節點下標1%4=12%4=23%4=34%4=05%4=16%4=2
可以看到後面三個快取 key ：4、5、6 對應的儲存節點全部失效了，這就需要把這幾個節點的快取資料遷移到更新後的節點上 (費時費力) ，也就是由原來的節點 [1, 2, 0] 遷移到節點 [0, 1, 2]，遷移後儲存示意圖如下：
快取雜湊擴充套件性示意圖2. 容錯能力不佳
線上環境服務節點雖然有各種高可用性保證，但還是是有宕機的可能，即使沒有宕機也有縮容的需求。不管是宕機和縮容都可以歸結為服務節點刪除的情況，下面分析下服務節點刪除對負載均衡雜湊值的影響。
假設刪除 1 個伺服器節點，由最初的 3 個服務節點變成 2 個，節點編號 [0 - 1]，雜湊對映情況如下：
雜湊計算公式：key %節點總數= Hash節點下標1%2=12%2=03%2=14%2=05%2=16%2=0
下圖展示普通雜湊負載均衡演算法在一個節點宕機時候，導致的的快取資料遷移分佈情況：
快取雜湊容錯性示意圖
如圖所見，在這個例子中，僅僅刪除了一個服務節點，也導致了雜湊值的大面積更新，雜湊值的更新也是意味著節點快取資料的遷移（快取資料表示心好累）。
一致性雜湊演算法負載均衡
正是由於普通雜湊演算法實現的快取負載均衡存在擴充套件能力和容錯能力差問題，所以我們引入一致性雜湊演算法，那麼什麼是一致性雜湊呢？先來看下wiki上對一致性Hash的定義
一致雜湊由 MIT 的 David Karger 及其合作者提出，現在這一思想已經擴充套件到其它領域。在這篇1997年發表的學術論文中介紹了一致雜湊如何應用於使用者易變的分散式Web服務中。一致雜湊也可用於實現健壯快取來減少大型Web應用中系統部分失效帶來的負面影響。
這篇描述一致性雜湊的論文發表於1997年，閱讀無障礙的同學可以直接看看大佬的論文理解更深刻，附上論文下載連結：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879
一致性hash論文
一句話概括一致性雜湊：就是普通取模雜湊演算法的改良版，雜湊函式計算方法不變，只不過是透過構建環狀的 Hash 空間代替普通的線性 Hash 空間。具體做法如下：
首先，選擇一個足夠大的Hash空間（一般是 0 ~ 2^32）構成一個雜湊環。
一致性雜湊環
然後，對於快取叢集內的每個儲存伺服器節點計算 Hash 值，可以用伺服器的 IP 或 主機名計算得到雜湊值，計算得到的雜湊值就是服務節點在 Hash 環上的位置。
節點雜湊
最後，對每個需要儲存的資料 key 同樣也計算一次雜湊值，計算之後的雜湊也對映到環上，資料儲存的位置是沿順時針的方向找到的環上的第一個節點。下圖舉例展示了節點儲存的資料情況，我們下面的說明也是基於目前的儲存情況來展開。
image
原理講完了，來看看為什麼這樣的設計能解決上面普通雜湊的兩個問題。擴充套件能力提升
前面我們分析過，普通雜湊演算法當需要擴容增加服務節點的時候，會導致原油雜湊對映大面積失效。現在，我們來看下一致性雜湊是如何解決這個問題的。
如下圖所示，當快取服務叢集要新增一個節點node3時，受影響的只有 key3 對應的資料 value3，此時只需把 value3 由原來的節點 node0 遷移到新增節點 node3 即可，其餘節點儲存的資料保持不動。
一致性雜湊-擴充套件節點容錯能力提升
普通雜湊演算法當某一服務節點宕機下線，也會導致原來雜湊對映的大面積失效，失效的對映觸發資料遷移影響快取服務效能，容錯能力不足。一起來看下一致性雜湊是如何提升容錯能力的。
如下圖所示，假設 node2 節點宕機下線，則原來儲存於 node2 的資料 value2 和 value5 ，只需按順時針方向選擇新的儲存節點 node0 存放即可，不會對其他節點資料產生影響。一致性雜湊能把節點宕機造成的影響控制在順時針相鄰節點之間，避免對整個叢集造成影響。
一致性雜湊-刪除節點
一致性雜湊最佳化
存在的問題
上面展示了一致性雜湊如何解決普通雜湊的擴充套件和容錯問題，原理比較簡單，在理想情況下可以良好執行，但在實際使用中還有一些實際問題需要考慮，下面具體分析。資料傾斜
試想一下若快取叢集內的服務節點比較少，就像我們例子中的三個節點，而雜湊環的空間又有很大（一般是 0 ~ 2^32），這會導致什麼問題呢？
可能的一種情況是，較少的服務節點雜湊值聚集在一起，比如下圖所示這種情況 node0 、node1、node2 聚集在一起，快取資料的 key 雜湊都對映到 node2 的順時針方向，資料按順時針尋找儲存節點就導致全都儲存到 node0 上去，給單個節點很大的壓力！這種情況稱為資料傾斜。
一致性雜湊-資料傾斜節點雪崩
資料傾斜和節點宕機都可能會導致快取雪崩。
拿前面資料傾斜的示例來說，資料傾斜導致所有快取資料都打到 node0 上面，有可能會導致 node0 不堪重負被壓垮了，node0 宕機，資料又都打到 node1 上面把 node1 也打垮了，node1 也被打趴傳遞給 node2，這時候故障就像像雪崩時滾雪球一樣越滾越大。
還有一種情況是節點由於各種原因宕機下線。比如下圖所示的節點 node2 下線導致原本在node2 的資料壓到 node0 , 在資料量特別大的情況下也可能導致節點雪崩，具體過程就像剛才的分析一樣。
總之，連鎖反應導致的整個快取叢集不可用，就稱為節點雪崩。
一致性雜湊-節點雪崩虛擬節點
那該如何解決上述兩個棘手的問題呢？可以透過「虛擬節點」的方式解決。
所謂虛擬節點，就是對原來單一的物理節點在雜湊環上虛擬出幾個它的分身節點，這些分身節點稱為「虛擬節點」。打到分身節點上的資料實際上也是對映到分身對應的物理節點上，這樣一個物理節點可以透過虛擬節點的方式均勻分散在雜湊環的各個部分，解決了資料傾斜問題。
由於虛擬節點分散在雜湊環各個部分，當某個節點宕機下線，他所儲存的資料會被均勻分配給其他各個節點，避免對單一節點突發壓力導致的節點雪崩問題。
下圖展示了虛擬節點的雜湊環分佈，其中左邊是沒做虛擬節點情況下的節點分佈，右邊背景色綠色兩個的 node0 節點是 node0 節點的虛擬節點；背景色紅色的 node1 節點是 node1 的虛擬節點。
一致性雜湊-虛擬節點
總結一下
本文首先介紹了什麼是雜湊演算法和常見的雜湊演算法，以及常見雜湊方式，接著說明基於普通雜湊演算法的快取負載均衡實現，並舉例說明普通演算法的擴充套件性和容錯性方便存在的問題。
為了解決普通演算法的擴充套件性和容錯性問題引入一致性雜湊演算法，圖解和舉例分析了一致性雜湊是如何提高擴充套件性和容錯性。最後粗糙的一致性雜湊演算法也存在資料傾斜和節點雪崩的問題，講解了如何利用虛擬節點最佳化一致性雜湊演算法，解決資料傾斜和雪崩問題。至此，一致性雜湊你學會了嗎？
一致性雜湊這個知識點不難，但是經常會考察到，就像布隆過濾器演算法一樣，沒聽過的人覺得很高階，研究一下也就那麼一回事，所以知識面要寬才能吊打面試官啊同學們！
