很多同學(xué)應(yīng)該都知道什么是哈希函數(shù)，在后端面試和開(kāi)發(fā)中會(huì)遇到「一致性哈?！?，那么什么是一致性哈希呢,？名字聽(tīng)起來(lái)很厲害的樣子,，其實(shí)原理并不復(fù)雜，這篇文章帶你徹底搞懂一致性哈希,！

進(jìn)入主題前,，先來(lái)一場(chǎng)緊張刺激的模擬面試吧。

模擬面試

面試官：看你簡(jiǎn)歷上寫(xiě)參與了一個(gè)大型項(xiàng)目，用到了分布式緩存集群,，那你說(shuō)說(shuō)你們是怎么做緩存負(fù)載均衡,？

萌新 ：這個(gè)我知道，我們用的是輪詢(xún)方式,，第一個(gè)key 給第一個(gè)存儲(chǔ)節(jié)點(diǎn),，第二個(gè) key 給第二個(gè)，以此類(lèi)推,。

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

萌新：可以用哈希函數(shù)，把請(qǐng)求打散隨機(jī)分配到緩存集群內(nèi)機(jī)器,。

面試官：考慮過(guò)這種哈希方式負(fù)載均衡的擴(kuò)展性和容錯(cuò)性嗎,？

萌新：...

面試官：回去等通知吧。

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

什么是哈希

數(shù)據(jù)結(jié)構(gòu)中我們學(xué)習(xí)過(guò)哈希表也稱(chēng)為散列表，我們來(lái)回顧下散列表的定義,。

散列表,，是根據(jù)鍵直接訪(fǎng)問(wèn)在指定儲(chǔ)存位置數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。通過(guò)計(jì)算一個(gè)關(guān)于鍵的函數(shù)也稱(chēng)為哈希函數(shù),，將所需查詢(xún)的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄,，加快查找速度。這個(gè)映射函數(shù)稱(chēng)做「散列函數(shù)」,，存放記錄的數(shù)組稱(chēng)做散列表,。

散列函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪(fǎng)問(wèn)過(guò)程更加迅速有效，是一種空間換時(shí)間的算法,，通過(guò)散列函數(shù)數(shù)據(jù)元素將被更快定位,。

下圖示意了字符串經(jīng)過(guò)哈希函數(shù)映射到哈希表的過(guò)程。沒(méi)錯(cuò),，輸入字符串是用臉滾鍵盤(pán)打出來(lái)的：）

哈希示意圖.png

常見(jiàn)的哈希算法有MD5,、CRC 、MurmurHash 等算法,，簡(jiǎn)單介紹一下,。

MD5算法

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

CRC算法

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

MurmurHash

MurmurHash 是一種非加密型哈希函數(shù),，適用于一般的哈希檢索操作。由 Austin Appleby 在2008年發(fā)明,，并出現(xiàn)了多個(gè)變種,，與其它流行的哈希函數(shù)相比，對(duì)于規(guī)律性較強(qiáng)的鍵,，MurmurHash的隨機(jī)分布特征表現(xiàn)更良好,。

這個(gè)算法已經(jīng)被很多開(kāi)源項(xiàng)目使用，比如libstdc++ (4.6版),、Perl,、nginx (不早于1.0.1版)、Rubinius,、 libmemcached,、maatkit、Hadoop等,。

常見(jiàn)散列方法

• 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線(xiàn)性函數(shù)值為散列地址,，這個(gè)線(xiàn)性函數(shù)的定義多種多樣，沒(méi)有標(biāo)準(zhǔn),。

• 數(shù)字分析法：假設(shè)關(guān)鍵字是以r為基的數(shù),，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址,。

• 平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址,。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適,，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān),，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的，取的位數(shù)由表長(zhǎng)決定,。

• 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）,，然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。

• 取模法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為散列地址,。即 hash(key) = key % p（p<= M）,，不僅可以對(duì)關(guān)鍵字直接取模,，也可在折疊法,、平方取中法等運(yùn)算之后取模,。對(duì) p 的選擇很重要，一般取素?cái)?shù)或 m,，若 p 選擇不好,，容易產(chǎn)生沖突。

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

在分布式集群緩存的負(fù)載均衡實(shí)現(xiàn)中,，比如 memcached 緩存集群,，需要把緩存數(shù)據(jù)的 key 利用哈希函數(shù)散列，這樣緩存數(shù)據(jù)能夠均勻分布到各個(gè)分布式存儲(chǔ)節(jié)點(diǎn)上,，要實(shí)現(xiàn)這樣的負(fù)載均衡一般可以用哈希算法來(lái)實(shí)現(xiàn),。下圖演示了這一分布式存儲(chǔ)過(guò)程：

分布式緩存散列存儲(chǔ)示意圖

普通哈希算法負(fù)載均衡

前面我們介紹過(guò)各種散列方法，不管是選擇上述哪種散列方法,，在這個(gè)應(yīng)用場(chǎng)景下,，都是要把緩存數(shù)據(jù)利用哈希函數(shù)均勻的映射到服務(wù)器集群上，我們就選擇簡(jiǎn)單的「取模法」來(lái)說(shuō)明這個(gè)過(guò)程,。

假設(shè)有 3 個(gè)服務(wù)器節(jié)點(diǎn)編號(hào) [0 - 2],，6 個(gè)緩存鍵值對(duì)編號(hào) [1 - 6]，則完成哈希映射之后,，三個(gè)緩存數(shù)據(jù)映射情況如下：

緩存哈希實(shí)例

每個(gè)連接都均勻的分散到了三個(gè)不同的服務(wù)器節(jié)點(diǎn)上,，看起來(lái)很完美！

但是,，在分布式集群系統(tǒng)的負(fù)載均衡實(shí)現(xiàn)上,，這種模型有兩個(gè)問(wèn)題：

1. 擴(kuò)展能力差

為了動(dòng)態(tài)調(diào)節(jié)服務(wù)能力，服務(wù)節(jié)點(diǎn)經(jīng)常需要擴(kuò)容縮容,。打個(gè)比方,，如果是電商服務(wù)，雙十一期間的服務(wù)機(jī)器數(shù)量肯定要比平常大很多,，新加進(jìn)來(lái)的機(jī)器會(huì)使原來(lái)計(jì)算的哈希值不準(zhǔn)確,，為了達(dá)到負(fù)載均衡的效果，要重新計(jì)算并更新哈希值,，對(duì)于更新后哈希值不一致的緩存數(shù)據(jù),，要遷移到更新后的節(jié)點(diǎn)上去。

假設(shè)新增了 1 個(gè)服務(wù)器節(jié)點(diǎn),，由原來(lái)的 3 個(gè)服務(wù)節(jié)點(diǎn)變成 4 個(gè)節(jié)點(diǎn)編號(hào) [0 - 3],，哈希映射情況如下：

哈希計(jì)算公式：key % 節(jié)點(diǎn)總數(shù) = Hash節(jié)點(diǎn)下標(biāo)
1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0
5 % 4 = 1
6 % 4 = 2

緩存哈希擴(kuò)展性示意圖

2. 容錯(cuò)能力不佳

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

假設(shè)刪除 1 個(gè)服務(wù)器節(jié)點(diǎn)，由最初的 3 個(gè)服務(wù)節(jié)點(diǎn)變成 2 個(gè),，節(jié)點(diǎn)編號(hào) [0 - 1],，哈希映射情況如下：

哈希計(jì)算公式：key % 節(jié)點(diǎn)總數(shù) = Hash節(jié)點(diǎn)下標(biāo)
1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1
6 % 2 = 0

緩存哈希容錯(cuò)性示意圖

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

一致性哈希算法負(fù)載均衡

正是由于普通哈希算法實(shí)現(xiàn)的緩存負(fù)載均衡存在擴(kuò)展能力和容錯(cuò)能力差問(wèn)題，所以我們引入一致性哈希算法,，那么什么是一致性哈希呢,？先來(lái)看下wiki上對(duì)一致性Hash的定義

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

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

一致性hash論文

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

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

一致性哈希環(huán)

然后,，對(duì)于緩存集群內(nèi)的每個(gè)存儲(chǔ)服務(wù)器節(jié)點(diǎn)計(jì)算 Hash 值，可以用服務(wù)器的 IP 或 主機(jī)名計(jì)算得到哈希值,，計(jì)算得到的哈希值就是服務(wù)節(jié)點(diǎn)在 Hash 環(huán)上的位置,。

節(jié)點(diǎn)哈希

最后，對(duì)每個(gè)需要存儲(chǔ)的數(shù)據(jù) key 同樣也計(jì)算一次哈希值,，計(jì)算之后的哈希也映射到環(huán)上,，數(shù)據(jù)存儲(chǔ)的位置是沿順時(shí)針的方向找到的環(huán)上的第一個(gè)節(jié)點(diǎn)。下圖舉例展示了節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)情況,，我們下面的說(shuō)明也是基于目前的存儲(chǔ)情況來(lái)展開(kāi),。

image

原理講完了,，來(lái)看看為什么這樣的設(shè)計(jì)能解決上面普通哈希的兩個(gè)問(wèn)題。

擴(kuò)展能力提升

前面我們分析過(guò),，普通哈希算法當(dāng)需要擴(kuò)容增加服務(wù)節(jié)點(diǎn)的時(shí)候,，會(huì)導(dǎo)致原油哈希映射大面積失效。現(xiàn)在,，我們來(lái)看下一致性哈希是如何解決這個(gè)問(wèn)題的,。

如下圖所示,，當(dāng)緩存服務(wù)集群要新增一個(gè)節(jié)點(diǎn)node3時(shí),，受影響的只有 key3 對(duì)應(yīng)的數(shù)據(jù) value3，此時(shí)只需把 value3 由原來(lái)的節(jié)點(diǎn) node0 遷移到新增節(jié)點(diǎn) node3 即可,，其余節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)保持不動(dòng),。

容錯(cuò)能力提升

普通哈希算法當(dāng)某一服務(wù)節(jié)點(diǎn)宕機(jī)下線(xiàn)，也會(huì)導(dǎo)致原來(lái)哈希映射的大面積失效,，失效的映射觸發(fā)數(shù)據(jù)遷移影響緩存服務(wù)性能,，容錯(cuò)能力不足。一起來(lái)看下一致性哈希是如何提升容錯(cuò)能力的,。

如下圖所示,，假設(shè) node2 節(jié)點(diǎn)宕機(jī)下線(xiàn)，則原來(lái)存儲(chǔ)于 node2 的數(shù)據(jù) value2 和 value5 ,，只需按順時(shí)針?lè)较蜻x擇新的存儲(chǔ)節(jié)點(diǎn) node0 存放即可,，不會(huì)對(duì)其他節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生影響。一致性哈希能把節(jié)點(diǎn)宕機(jī)造成的影響控制在順時(shí)針相鄰節(jié)點(diǎn)之間,，避免對(duì)整個(gè)集群造成影響,。

一致性哈希-刪除節(jié)點(diǎn)

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

存在的問(wèn)題

上面展示了一致性哈希如何解決普通哈希的擴(kuò)展和容錯(cuò)問(wèn)題，原理比較簡(jiǎn)單,，在理想情況下可以良好運(yùn)行,，但在實(shí)際使用中還有一些實(shí)際問(wèn)題需要考慮，下面具體分析,。

數(shù)據(jù)傾斜

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

可能的一種情況是，較少的服務(wù)節(jié)點(diǎn)哈希值聚集在一起,，比如下圖所示這種情況 node0 ,、node1、node2 聚集在一起,，緩存數(shù)據(jù)的 key 哈希都映射到 node2 的順時(shí)針?lè)较?，?shù)據(jù)按順時(shí)針尋找存儲(chǔ)節(jié)點(diǎn)就導(dǎo)致全都存儲(chǔ)到 node0 上去,，給單個(gè)節(jié)點(diǎn)很大的壓力！這種情況稱(chēng)為數(shù)據(jù)傾斜,。

一致性哈希-數(shù)據(jù)傾斜

節(jié)點(diǎn)雪崩

數(shù)據(jù)傾斜和節(jié)點(diǎn)宕機(jī)都可能會(huì)導(dǎo)致緩存雪崩,。

拿前面數(shù)據(jù)傾斜的示例來(lái)說(shuō)，數(shù)據(jù)傾斜導(dǎo)致所有緩存數(shù)據(jù)都打到 node0 上面,，有可能會(huì)導(dǎo)致 node0 不堪重負(fù)被壓垮了,，node0 宕機(jī)，數(shù)據(jù)又都打到 node1 上面把 node1 也打垮了,，node1 也被打趴傳遞給 node2,，這時(shí)候故障就像像雪崩時(shí)滾雪球一樣越滾越大。

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

總之,，連鎖反應(yīng)導(dǎo)致的整個(gè)緩存集群不可用,，就稱(chēng)為節(jié)點(diǎn)雪崩。

一致性哈希-節(jié)點(diǎn)雪崩

虛擬節(jié)點(diǎn)

那該如何解決上述兩個(gè)棘手的問(wèn)題呢,？可以通過(guò)「虛擬節(jié)點(diǎn)」的方式解決,。

所謂虛擬節(jié)點(diǎn)，就是對(duì)原來(lái)單一的物理節(jié)點(diǎn)在哈希環(huán)上虛擬出幾個(gè)它的分身節(jié)點(diǎn),，這些分身節(jié)點(diǎn)稱(chēng)為「虛擬節(jié)點(diǎn)」,。打到分身節(jié)點(diǎn)上的數(shù)據(jù)實(shí)際上也是映射到分身對(duì)應(yīng)的物理節(jié)點(diǎn)上，這樣一個(gè)物理節(jié)點(diǎn)可以通過(guò)虛擬節(jié)點(diǎn)的方式均勻分散在哈希環(huán)的各個(gè)部分,，解決了數(shù)據(jù)傾斜問(wèn)題,。

由于虛擬節(jié)點(diǎn)分散在哈希環(huán)各個(gè)部分，當(dāng)某個(gè)節(jié)點(diǎn)宕機(jī)下線(xiàn),，他所存儲(chǔ)的數(shù)據(jù)會(huì)被均勻分配給其他各個(gè)節(jié)點(diǎn),，避免對(duì)單一節(jié)點(diǎn)突發(fā)壓力導(dǎo)致的節(jié)點(diǎn)雪崩問(wèn)題。

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

一致性哈希-虛擬節(jié)點(diǎn)

總結(jié)一下

本文首先介紹了什么是哈希算法和常見(jiàn)的哈希算法,，以及常見(jiàn)散列方式，接著說(shuō)明基于普通哈希算法的緩存負(fù)載均衡實(shí)現(xiàn),，并舉例說(shuō)明普通算法的擴(kuò)展性和容錯(cuò)性方便存在的問(wèn)題,。

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

一致性哈希這個(gè)知識(shí)點(diǎn)不難，但是經(jīng)常會(huì)考察到,，就像布隆過(guò)濾器算法一樣,，沒(méi)聽(tīng)過(guò)的人覺(jué)得很高端，研究一下也就那么一回事,，所以知識(shí)面要寬才能吊打面試官啊同學(xué)們,！

感謝各位的閱讀，文章的目的是分享對(duì)知識(shí)的理解,，技術(shù)類(lèi)文章我都會(huì)反復(fù)求證以求最大程度保證準(zhǔn)確性,，若文中出現(xiàn)明顯紕漏也歡迎指出,，我們一起在探討中學(xué)習(xí),。

如果覺(jué)得文章寫(xiě)的還行，對(duì)你有所幫助,，不要白票 lemon,，動(dòng)動(dòng)手指點(diǎn)個(gè)「在看」或「分享」是對(duì)我持續(xù)創(chuàng)作的最大支持。

今天的技術(shù)分享就到這里,，我們下期再見(jiàn),。