圖解一致性哈希算法，全網（小區(qū)局域網）最通俗易懂

點擊上方藍色“后端技術學堂”關注后加個“星標”

最新分享第一時間看！

正文共 5558 字，預計閱讀時長 8?分鐘

好久不見小伙伴們，最近都快忙暈了，后端技術學堂差點停課，不過還是抽時間寫了這篇文章帶大家一起學習一致性哈希算法。

很多同學應該都知道什么是哈希函數，在后端面試和開發(fā)中會遇到「一致性哈希」，那么什么是一致性哈希呢？名字聽起來很厲害的樣子，其實原理并不復雜，這篇文章帶你徹底搞懂一致性哈希！

進入主題前，先來一場緊張刺激的模擬面試吧。

模擬面試

面試官：看你簡歷上寫參與了一個大型項目，用到了分布式緩存集群，那你說說你們是怎么做緩存負載均衡？

萌新 ：這個我知道，我們用的是輪詢方式，第一個key 給第一個存儲節(jié)點，第二個 key 給第二個，以此類推。

面試官：還有其他解決方案嗎？

萌新：可以用哈希函數，把請求打散隨機分配到緩存集群內機器。

面試官：考慮過這種哈希方式負載均衡的擴展性和容錯性嗎？

萌新：...

面試官：回去等通知吧。

以上如有雷同，算你抄我的。

什么是哈希

數據結構中我們學習過哈希表也稱為散列表，我們來回顧下散列表的定義。

散列表，是根據鍵直接訪問在指定儲存位置數據的數據結構。通過計算一個關于鍵的函數也稱為哈希函數，將所需查詢的數據映射到表中一個位置來訪問記錄，加快查找速度。這個映射函數稱做「散列函數」，存放記錄的數組稱做散列表。

散列函數能使對一個數據序列的訪問過程更加迅速有效，是一種空間換時間的算法，通過散列函數數據元素將被更快定位。

下圖示意了字符串經過哈希函數映射到哈希表的過程。沒錯，輸入字符串是用臉滾鍵盤打出來的：）

常見的哈希算法有MD5、CRC 、MurmurHash 等算法，簡單介紹一下。

MD5算法

MD5消息摘要算法（英語：MD5 Message-Digest Algorithm），一種被廣泛使用的密碼散列函數，可以產生出一個128位（16字節(jié)）的散列值（hash value），MD5算法將數據（如一段文字）運算變?yōu)榱硪还潭ㄩL度值，是散列算法的基礎原理。由美國密碼學家 Ronald Linn Rivest設計，于1992年公開并在 RFC 1321 中被加以規(guī)范。

CRC算法

循環(huán)冗余校驗（Cyclic Redundancy Check）是一種根據網絡數據包或電腦文件等數據，產生簡短固定位數校驗碼的一種散列函數，由 W. Wesley Peterson 于1961年發(fā)表。生成的數字在傳輸或者存儲之前計算出來并且附加到數據后面，然后接收方進行檢驗確定數據是否發(fā)生變化。由于本函數易于用二進制的電腦硬件使用、容易進行數學分析并且尤其善于檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。

MurmurHash

MurmurHash 是一種非加密型哈希函數，適用于一般的哈希檢索操作。由 Austin Appleby 在2008年發(fā)明，并出現了多個變種，與其它流行的哈希函數相比，對于規(guī)律性較強的鍵，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 選擇不好，容易產生沖突。

緩存系統(tǒng)負載均衡

在分布式集群緩存的負載均衡實現中，比如 memcached 緩存集群，需要把緩存數據的 key 利用哈希函數散列，這樣緩存數據能夠均勻分布到各個分布式存儲節(jié)點上，要實現這樣的負載均衡一般可以用哈希算法來實現。下圖演示了這一分布式存儲過程：

普通哈希算法負載均衡

前面我們介紹過各種散列方法，不管是選擇上述哪種散列方法，在這個應用場景下，都是要把緩存數據利用哈希函數均勻的映射到服務器集群上，我們就選擇簡單的「取模法」來說明這個過程。

假設有 3 個服務器節(jié)點編號 [0 - 2]，6 個緩存鍵值對編號 [1 - 6]，則完成哈希映射之后，三個緩存數據映射情況如下：

哈希計算公式：key %?節(jié)點總數?= Hash節(jié)點下標
1?%?3?=?1
2?%?3?=?2
3?%?3?=?0
4?%?3?=?1
5?%?3?=?2
6?%?3?=?0

每個連接都均勻的分散到了三個不同的服務器節(jié)點上，看起來很完美！

但是，在分布式集群系統(tǒng)的負載均衡實現上，這種模型有兩個問題：

1. 擴展能力差

為了動態(tài)調節(jié)服務能力，服務節(jié)點經常需要擴容縮容。打個比方，如果是電商服務，雙十一期間的服務機器數量肯定要比平常大很多，新加進來的機器會使原來計算的哈希值不準確，為了達到負載均衡的效果，要重新計算并更新哈希值，對于更新后哈希值不一致的緩存數據，要遷移到更新后的節(jié)點上去。

假設新增了 1 個服務器節(jié)點，由原來的 3 個服務節(jié)點變成 4 個節(jié)點編號 [0 - 3]，哈希映射情況如下：

哈希計算公式：key %?節(jié)點總數?= Hash節(jié)點下標
1?%?4?=?1
2?%?4?=?2
3?%?4?=?3
4?%?4?=?0
5?%?4?=?1
6?%?4?=?2

可以看到后面三個緩存 key ：4、5、6 對應的存儲節(jié)點全部失效了，這就需要把這幾個節(jié)點的緩存數據遷移到更新后的節(jié)點上 (費時費力) ，也就是由原來的節(jié)點 [1, 2, 0] 遷移到節(jié)點 [0, 1, 2]，遷移后存儲示意圖如下：

2. 容錯能力不佳

線上環(huán)境服務節(jié)點雖然有各種高可用性保證，但還是是有宕機的可能，即使沒有宕機也有縮容的需求。不管是宕機和縮容都可以歸結為服務節(jié)點刪除的情況，下面分析下服務節(jié)點刪除對負載均衡哈希值的影響。

假設刪除 1 個服務器節(jié)點，由最初的 3 個服務節(jié)點變成 2 個，節(jié)點編號 [0 - 1]，哈希映射情況如下：

哈希計算公式：key %?節(jié)點總數?= Hash節(jié)點下標
1?%?2?=?1
2?%?2?=?0
3?%?2?=?1
4?%?2?=?0
5?%?2?=?1
6?%?2?=?0

下圖展示普通哈希負載均衡算法在一個節(jié)點宕機時候，導致的的緩存數據遷移分布情況：

如圖所見，在這個例子中，僅僅刪除了一個服務節(jié)點，也導致了哈希值的大面積更新，哈希值的更新也是意味著節(jié)點緩存數據的遷移（緩存數據表示心好累）。

一致性哈希算法負載均衡

正是由于普通哈希算法實現的緩存負載均衡存在擴展能力和容錯能力差問題，所以我們引入一致性哈希算法，那么什么是一致性哈希呢？先來看下wiki上對一致性Hash的定義

一致哈希由 MIT 的 David Karger 及其合作者提出，現在這一思想已經擴展到其它領域。在這篇1997年發(fā)表的學術論文中介紹了一致哈希如何應用于用戶易變的分布式Web服務中。一致哈希也可用于實現健壯緩存來減少大型Web應用中系統(tǒng)部分失效帶來的負面影響。

這篇描述一致性哈希的論文發(fā)表于1997年，閱讀無障礙的同學可以直接看看大佬的論文理解更深刻，附上論文下載鏈接：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879

一句話概括一致性哈希：就是普通取模哈希算法的改良版，哈希函數計算方法不變，只不過是通過構建環(huán)狀的 Hash 空間代替普通的線性 Hash 空間。具體做法如下：

首先，選擇一個足夠大的Hash空間（一般是 0 ~ 2^32）構成一個哈希環(huán)。

然后，對于緩存集群內的每個存儲服務器節(jié)點計算 Hash 值，可以用服務器的 IP 或 主機名計算得到哈希值，計算得到的哈希值就是服務節(jié)點在 Hash 環(huán)上的位置。

最后，對每個需要存儲的數據 key 同樣也計算一次哈希值，計算之后的哈希也映射到環(huán)上，數據存儲的位置是沿順時針的方向找到的環(huán)上的第一個節(jié)點。下圖舉例展示了節(jié)點存儲的數據情況，我們下面的說明也是基于目前的存儲情況來展開。

原理講完了，來看看為什么這樣的設計能解決上面普通哈希的兩個問題。

擴展能力提升

前面我們分析過，普通哈希算法當需要擴容增加服務節(jié)點的時候，會導致原油哈希映射大面積失效。現在，我們來看下一致性哈希是如何解決這個問題的。

如下圖所示，當緩存服務集群要新增一個節(jié)點node3時，受影響的只有 key3 對應的數據 value3，此時只需把 value3 由原來的節(jié)點 node0 遷移到新增節(jié)點 node3 即可，其余節(jié)點存儲的數據保持不動。

容錯能力提升

普通哈希算法當某一服務節(jié)點宕機下線，也會導致原來哈希映射的大面積失效，失效的映射觸發(fā)數據遷移影響緩存服務性能，容錯能力不足。一起來看下一致性哈希是如何提升容錯能力的。

如下圖所示，假設 node2 節(jié)點宕機下線，則原來存儲于 node2 的數據 value2 和 value5 ，只需按順時針方向選擇新的存儲節(jié)點 node0 存放即可，不會對其他節(jié)點數據產生影響。一致性哈希能把節(jié)點宕機造成的影響控制在順時針相鄰節(jié)點之間，避免對整個集群造成影響。

一致性哈希優(yōu)化

存在的問題

上面展示了一致性哈希如何解決普通哈希的擴展和容錯問題，原理比較簡單，在理想情況下可以良好運行，但在實際使用中還有一些實際問題需要考慮，下面具體分析。

數據傾斜

試想一下若緩存集群內的服務節(jié)點比較少，就像我們例子中的三個節(jié)點，而哈希環(huán)的空間又有很大（一般是 0 ~ 2^32），這會導致什么問題呢？

可能的一種情況是，較少的服務節(jié)點哈希值聚集在一起，比如下圖所示這種情況 node0 、node1、node2 聚集在一起，緩存數據的 key 哈希都映射到 node2 的順時針方向，數據按順時針尋找存儲節(jié)點就導致全都存儲到 node0 上去，給單個節(jié)點很大的壓力！這種情況稱為數據傾斜。

節(jié)點雪崩

數據傾斜和節(jié)點宕機都可能會導致緩存雪崩。

拿前面數據傾斜的示例來說，數據傾斜導致所有緩存數據都打到 node0 上面，有可能會導致 node0 不堪重負被壓垮了，node0 宕機，數據又都打到 node1 上面把 node1 也打垮了，node1 也被打趴傳遞給 node2，這時候故障就像像雪崩時滾雪球一樣越滾越大。

還有一種情況是節(jié)點由于各種原因宕機下線。比如下圖所示的節(jié)點 node2 下線導致原本在node2 的數據壓到 node0 , 在數據量特別大的情況下也可能導致節(jié)點雪崩，具體過程就像剛才的分析一樣。

總之，連鎖反應導致的整個緩存集群不可用，就稱為節(jié)點雪崩。

虛擬節(jié)點

那該如何解決上述兩個棘手的問題呢？可以通過「虛擬節(jié)點」的方式解決。

所謂虛擬節(jié)點，就是對原來單一的物理節(jié)點在哈希環(huán)上虛擬出幾個它的分身節(jié)點，這些分身節(jié)點稱為「虛擬節(jié)點」。打到分身節(jié)點上的數據實際上也是映射到分身對應的物理節(jié)點上，這樣一個物理節(jié)點可以通過虛擬節(jié)點的方式均勻分散在哈希環(huán)的各個部分，解決了數據傾斜問題。

由于虛擬節(jié)點分散在哈希環(huán)各個部分，當某個節(jié)點宕機下線，他所存儲的數據會被均勻分配給其他各個節(jié)點，避免對單一節(jié)點突發(fā)壓力導致的節(jié)點雪崩問題。

下圖展示了虛擬節(jié)點的哈希環(huán)分布，其中左邊是沒做虛擬節(jié)點情況下的節(jié)點分布，右邊背景色綠色兩個的 node0 節(jié)點是 node0 節(jié)點的虛擬節(jié)點；背景色紅色的 node1 節(jié)點是 node1 的虛擬節(jié)點。

總結一下

本文首先介紹了什么是哈希算法和常見的哈希算法，以及常見散列方式，接著說明基于普通哈希算法的緩存負載均衡實現，并舉例說明普通算法的擴展性和容錯性方便存在的問題。

為了解決普通算法的擴展性和容錯性問題引入一致性哈希算法，圖解和舉例分析了一致性哈希是如何提高擴展性和容錯性。最后粗糙的一致性哈希算法也存在數據傾斜和節(jié)點雪崩的問題，講解了如何利用虛擬節(jié)點優(yōu)化一致性哈希算法，解決數據傾斜和雪崩問題。至此，一致性哈希你學會了嗎？

再聊兩句（求三連）

一致性哈希這個知識點不難，但是經常會考察到，就像布隆過濾器算法一樣，沒聽過的人覺得很高端，研究一下也就那么一回事，所以知識面要寬才能吊打面試官啊同學們！

感謝各位的閱讀，文章的目的是分享對知識的理解，技術類文章我都會反復求證以求最大程度保證準確性，若文中出現明顯紕漏也歡迎指出，我們一起在探討中學習。

如果覺得文章寫的還行，對你有所幫助，不要白票 lemon，動動手指點個「在看」或「分享」是對我持續(xù)創(chuàng)作的最大支持。

今天的技術分享就到這里，我們下期再見。

另外，我建了個學習交流群，群內不定期分享優(yōu)質技術文章，還有各路技術總監(jiān)大咖，一起學習一起進階，加下面我微信備注「進群」拉你加入

掃一掃，備注「進群」