一致性哈希是什么？為什么它是可擴(kuò)展的分布式系統(tǒng)架構(gòu)的一個(gè)必要工具

在本文中，我們將了解一致性哈希是什么、為什么它是可擴(kuò)展的分布式系統(tǒng)架構(gòu)中的一個(gè)必要工具。

此外，我們將探究可用于大規(guī)模實(shí)施該算法的數(shù)據(jù)結(jié)構(gòu)。最后，我們還將探究一個(gè)實(shí)際例子。

一致性哈希到底是什么？

還記得你在大學(xué)里學(xué)到的那種傳統(tǒng)的樸素哈希方法嗎？使用哈希函數(shù)，我們確保計(jì)算機(jī)程序所需的資源能夠高效地存儲在內(nèi)存中，從而確保內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)均勻地加載。

我們還確保該資源存儲策略同樣使得信息檢索更高效，因而使程序運(yùn)行起來更快。

經(jīng)典的哈希方法使用哈希函數(shù)來生成偽隨機(jī)數(shù)，然后除以內(nèi)存空間的大小，將隨機(jī)標(biāo)識符轉(zhuǎn)變成可用空間內(nèi)的一個(gè)位置。

結(jié)果看起來如下：location = hash(key)mod size。

圖 1

那么，我們?yōu)槭裁床皇褂猛环椒▉硖幚?a href="http://wenjunhu.com/v/tag/1722/" target="_blank">網(wǎng)絡(luò)上的請求？

在各種程序、計(jì)算機(jī)或用戶向多個(gè)服務(wù)器節(jié)點(diǎn)請求一些資源的場景下，我們需要一種機(jī)制將請求均勻地映射到可用的服務(wù)器節(jié)點(diǎn)，從而確保負(fù)載均衡，并且保持一致的性能。

我們不妨將服務(wù)器節(jié)點(diǎn)視為一個(gè)或多個(gè)請求可以映射到的占位符，現(xiàn)在不妨后退一步。

在經(jīng)典哈希方法中，我們總是假設(shè)：內(nèi)存位置的數(shù)量是已知的，而且這個(gè)數(shù)永遠(yuǎn)不變。

比如我們通常在一天內(nèi)擴(kuò)大或縮小集群規(guī)模，還要處理突如其來的故障。但是如果我們考慮上述場景，就無法保證服務(wù)器節(jié)點(diǎn)的數(shù)量保持不變。

如果其中一個(gè)突然出現(xiàn)故障，該怎么辦？使用樸素哈希方法，我們最終需要重新計(jì)算每一個(gè)鍵的哈希值，因?yàn)樾掠成湟蕾嚬?jié)點(diǎn)數(shù)量/內(nèi)存位置，如下所示：

圖 2：之前

圖 3：之后

只是重新計(jì)算哈希值的分布式系統(tǒng)（每個(gè)鍵的位置都移動(dòng)）存在一個(gè)問題，那就是每個(gè)節(jié)點(diǎn)上都存儲了狀態(tài)。

比如說，集群規(guī)模的微小變化可能導(dǎo)致大量的工作，以便重新調(diào)整集群內(nèi)的所有數(shù)據(jù)。

集群規(guī)模變大后，這就無以為繼，因?yàn)槊總€(gè)哈希變更（hash change）所需的工作量隨集群規(guī)模呈線性增長。這時(shí)，一致性哈希這個(gè)概念有了用武之地。

一致性哈希到底是什么？可以這樣來描述：

它表示某種虛擬環(huán)結(jié)構(gòu)（名為哈希環(huán)，HashRing）中的資源請求者（我們在本文中簡稱為“請求”）和服務(wù)器節(jié)點(diǎn)。

位置數(shù)量不再固定，但是環(huán)被認(rèn)為有無限數(shù)量的點(diǎn)，服務(wù)器節(jié)點(diǎn)可以放置在該環(huán)上的隨機(jī)位置。

當(dāng)然，再次選擇該隨機(jī)數(shù)可以使用哈希函數(shù)來完成，但是除以可用位置數(shù)量的第二步被跳過，因?yàn)樗辉偈且粋€(gè)有限數(shù)。

請求即用戶、計(jì)算機(jī)或無服務(wù)器程序，它們類似于經(jīng)典哈希方法中的鍵，也使用同樣的哈希函數(shù)放置在同一個(gè)環(huán)上。

圖 4

那么，如何決定哪個(gè)請求將由哪個(gè)服務(wù)器節(jié)點(diǎn)來處理？如果我們假設(shè)環(huán)是有序的，以便環(huán)的順時(shí)針遍歷與位置地址的遞增順序?qū)?yīng)，那么每個(gè)請求可以由最先出現(xiàn)在該順時(shí)針遍歷中的那個(gè)服務(wù)器節(jié)點(diǎn)來處理。

也就是說，地址高于請求地址的第一個(gè)服務(wù)器節(jié)點(diǎn)負(fù)責(zé)處理該請求。如果請求地址高于最高尋址節(jié)點(diǎn)，它由最小地址的服務(wù)器節(jié)點(diǎn)來處理，因?yàn)榄h(huán)遍歷以圓形方式進(jìn)行。如下圖所示：

圖 5

從理論上來說，每個(gè)服務(wù)器節(jié)點(diǎn)“擁有”哈希環(huán)的一個(gè)區(qū)間，進(jìn)入該區(qū)間的任何請求將由同一服務(wù)器節(jié)點(diǎn)來處理。

現(xiàn)在，如果其中一個(gè)服務(wù)器節(jié)點(diǎn)（比如節(jié)點(diǎn) 3）出現(xiàn)故障，下一個(gè)服務(wù)器節(jié)點(diǎn)的區(qū)間就變寬，進(jìn)入該區(qū)間的任何請求都將進(jìn)入到新的服務(wù)器節(jié)點(diǎn)，該怎么辦？

那就需要重新分配的是僅僅這一個(gè)區(qū)間（與出現(xiàn)故障的服務(wù)器節(jié)點(diǎn)對應(yīng)），哈希環(huán)的其余部分和請求/節(jié)點(diǎn)分配仍然不受影響。

這與經(jīng)典哈希技術(shù)形成了對比：哈希表大小的變更實(shí)際上干擾了所有映射。

由于一致性哈希，只有一部分請求（相對于環(huán)分配因子）會受到特定的環(huán)變更的影響。（之所以出現(xiàn)環(huán)變更，是由于添加或刪除節(jié)點(diǎn)導(dǎo)致一些請求/節(jié)點(diǎn)映射發(fā)生了變化。）

圖 6

如何高效地實(shí)施一致性哈希算法？

我們弄清楚了哈希環(huán)是什么，現(xiàn)在需要實(shí)施下列部分讓它發(fā)揮作用：

從我們的哈?？臻g到集群中節(jié)點(diǎn)的映射，讓我們得以找到負(fù)責(zé)某個(gè)請求的節(jié)點(diǎn)。

針對解析到某個(gè)節(jié)點(diǎn)的集群的那些請求的集合。之后，這將讓我們得以搞清楚哪些哈希值受到添加或刪除某個(gè)節(jié)點(diǎn)的影響。

映射

為了完成上面第一個(gè)部分，我們需要下列部分：

在給出請求標(biāo)識符的情況下，計(jì)算環(huán)中位置的哈希函數(shù)。

搞清楚哪個(gè)節(jié)點(diǎn)與哈希請求對應(yīng)的方法。

為了搞清楚與某個(gè)請求對應(yīng)的節(jié)點(diǎn)，我們可以使用一種簡單的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行表示，包括下列部分：

與環(huán)中節(jié)點(diǎn)對應(yīng)的哈希數(shù)組。

用于查找與某個(gè)請求對應(yīng)的節(jié)點(diǎn)的圖（哈希表）。

這實(shí)際上是有序圖的一種原始表示。想找到負(fù)責(zé)上述結(jié)構(gòu)中某個(gè)哈希值的節(jié)點(diǎn)，我們需要：

執(zhí)行修改后的二進(jìn)制搜索，查找數(shù)組中等于或大于（≥）所要查找的哈希值的第一個(gè)節(jié)點(diǎn)/哈希值。

查找與圖中已找到的節(jié)點(diǎn)/哈希值對應(yīng)的節(jié)點(diǎn)。

添加或刪除節(jié)點(diǎn)

正如我們在文章開頭看到，添加新節(jié)點(diǎn)時(shí)，必須將含有各種請求的哈希環(huán)的某些部分分配給該節(jié)點(diǎn)。

反過來，刪除節(jié)點(diǎn)時(shí)，已分配給該節(jié)點(diǎn)的請求需要由另外某個(gè)節(jié)點(diǎn)來處理。

我們?nèi)绾尾檎沂墉h(huán)變更影響的那些請求？一種解決方案是遍歷分配給節(jié)點(diǎn)的所有請求。

對于每個(gè)請求，我們確定它是否屬于已出現(xiàn)的環(huán)變更的范圍內(nèi)，必要時(shí)將它移到其他位置。

不過，執(zhí)行此操作所需的工作量隨分配給某個(gè)節(jié)點(diǎn)的請求數(shù)量的增加而增加。由于節(jié)點(diǎn)數(shù)量增加后，出現(xiàn)的環(huán)變更的數(shù)量往往增加，情況變得更糟。

在最糟糕的情況下，由于環(huán)變更常常與局部故障有關(guān)，因此與環(huán)變更相關(guān)的瞬時(shí)負(fù)載也可能加大其他節(jié)點(diǎn)同樣受影響的可能性，可能導(dǎo)致整個(gè)系統(tǒng)出現(xiàn)連鎖反應(yīng)問題。

為了解決這個(gè)問題，我們希望請求的重新定位盡可能高效。理想情況下，我們將所有請求存儲在這樣一種數(shù)據(jù)結(jié)構(gòu)中：便于我們找到受環(huán)上任何位置的單一哈希變更影響的那些請求。

高效地查找受影響的哈希值

往集群添加節(jié)點(diǎn)或從集群刪除節(jié)點(diǎn)將改變在環(huán)的一些部分分配請求，我們稱之為受影響的區(qū)間（affected range）。如果我們知道受影響區(qū)間的界限，就能夠?qū)⒄埱笠频秸_的位置。

想找到受影響區(qū)間的邊界，從已添加或已刪除的節(jié)點(diǎn)的哈希值 H 開始，我們就能從 H 開始沿環(huán)向后移動(dòng)（圖中逆時(shí)針），直至找到另一個(gè)節(jié)點(diǎn)。

不妨稱該節(jié)點(diǎn)的哈希值為 S（開始值）。該節(jié)點(diǎn)逆時(shí)針的請求將定位到它，那樣這些請求不會受影響。

請注意：這只是簡單描述了發(fā)生的情況；實(shí)際上，結(jié)構(gòu)和算法更加復(fù)雜，因?yàn)槲覀兪褂么笥?1 的復(fù)制因子和專門的復(fù)制策略（只有一小部分的節(jié)點(diǎn)適用于任何特定的請求）。

區(qū)間中的放置哈希值介于已找到的節(jié)點(diǎn)與已添加（或已刪除）的節(jié)點(diǎn)之間的請求是需要移動(dòng)的請求。

高效地查找受影響區(qū)間中的請求

一種解決方案就是遍歷與某個(gè)節(jié)點(diǎn)對應(yīng)的所有請求，并更新哈希值在該區(qū)間內(nèi)的請求。

在 JavaScript 中可能看起來像這樣：

for(constrequestofrequests){if(contains(S,H,request.hash)){/*therequestisaffectedbythechange*/request.relocate();}}functioncontains(lowerBound,upperBound,hash){constwrapsOver=upperBound=lowerBound;constbelowUpper=upperBound>=hash;if(wrapsOver){returnaboveLower||belowUpper;}else{returnaboveLower&&belowUpper;}}

由于環(huán)是圓形的，光查找 S <= r

只要請求數(shù)量比較少，或如果節(jié)點(diǎn)的添加或刪除比較少見，迭代某個(gè)節(jié)點(diǎn)上的所有請求就行。

不過，某個(gè)節(jié)點(diǎn)處的請求數(shù)量增加后，所需的工作量隨之增加；更糟糕的是，隨著節(jié)點(diǎn)數(shù)量增加，無論是由于自動(dòng)擴(kuò)展還是故障切換，環(huán)變更往往會更頻繁地出現(xiàn)，從而觸發(fā)系統(tǒng)上的同步負(fù)載重新均衡請求。

在最糟糕的情況下，與此相關(guān)的負(fù)載可能加大其他節(jié)點(diǎn)上出現(xiàn)故障的可能性，可能導(dǎo)致整個(gè)系統(tǒng)出現(xiàn)連鎖反應(yīng)問題。

為了應(yīng)對這種情況，我們還可以將請求存儲在與前面討論的數(shù)據(jù)結(jié)構(gòu)類似的單獨(dú)的環(huán)數(shù)據(jù)結(jié)構(gòu)中。在此環(huán)中，哈希直接映射到位于該哈希值的請求。

然后我們可以執(zhí)行下列操作，找到區(qū)間內(nèi)的請求：

找到區(qū)間開始值 S 后的第一個(gè)請求。

順時(shí)針迭代，直至找到哈希值超出區(qū)間的請求。

重新找到區(qū)間內(nèi)的那些請求。

針對特定的哈希更新而需要迭代的請求數(shù)量平均為 R/N，其中 R 是位于節(jié)點(diǎn)區(qū)間內(nèi)的請求數(shù)量，N 是環(huán)中哈希值的數(shù)量，假設(shè)請求均勻地分配。

下面用一個(gè)實(shí)際的例子來介紹上述解釋。

假設(shè)我們有一個(gè)集群含有兩個(gè)節(jié)點(diǎn)：A 和 B。不妨為這每個(gè)節(jié)點(diǎn)隨機(jī)生成一個(gè)“放置哈希值”(假設(shè)是 32 位哈希值）。

于是我們得到：

A：0x5e6058e5

B：0xa2d65c0

這將節(jié)點(diǎn)放在一個(gè)假想環(huán)上，其中數(shù)字 0x0、0x1、0x2......連續(xù)放置到 0xffffffff。

由于節(jié)點(diǎn) A 有哈希值 0x5e6058e5，因此它負(fù)責(zé)哈希進(jìn)入到區(qū)間 0xa2d65c0+1 直到 0xffffffff 以及從 0x0 直到 0x5e6058e5 的任何請求，如下所示：

圖 7

另一方面，B 負(fù)責(zé)區(qū)間 0x5e6058e5+1 直到 0xa2d65c0。因此，整個(gè)哈希空間是分布式的。

從節(jié)點(diǎn)到哈希的這種映射需要與整個(gè)集群共享，以便環(huán)計(jì)算的結(jié)果始終相同。因此，需要特定請求的任何節(jié)點(diǎn)都可以查明其所在位置。

假設(shè)我們想要查找（或創(chuàng)建）擁有標(biāo)識符“bobs.blog@example.com”的請求：

我們計(jì)算標(biāo)識符的哈希值 H，比如 0x89e04a0a。

我們查看環(huán)，找到哈希值大于 H 的第一個(gè)節(jié)點(diǎn)，這里恰好是 B。

因此 B 是負(fù)責(zé)該請求的節(jié)點(diǎn)。如果我們再次需要該請求，將重復(fù)上述步驟，再次登陸到同一個(gè)節(jié)點(diǎn)，它有我們所需的狀態(tài)。

這個(gè)例子有點(diǎn)過于簡單，實(shí)際上，每個(gè)節(jié)點(diǎn)有一個(gè)哈?？赡軙懿还降胤峙湄?fù)載。

你可能已注意到，在這個(gè)例子中，B 負(fù)責(zé)環(huán)的（0xa2d656c0-0x5e6058e5）/232 = 26.7%，而 A 負(fù)責(zé)其余部分。理想情況下，每個(gè)節(jié)點(diǎn)將負(fù)責(zé)環(huán)的相等部分。

讓這更公平的一種方法是，為每個(gè)節(jié)點(diǎn)生成多個(gè)隨機(jī)哈希值，如下所示：

圖 8

實(shí)際上，我們發(fā)現(xiàn)這個(gè)結(jié)果仍然不能令人滿意，于是我們將環(huán)分成 64 個(gè)大小同等的段，確保每個(gè)節(jié)點(diǎn)的哈希值放在每個(gè)段的某個(gè)位置；不過，這方面的細(xì)節(jié)不重要。

目的只是想確保每個(gè)節(jié)點(diǎn)負(fù)責(zé)環(huán)的同等部分，從而使負(fù)載均勻地分配。（每個(gè)節(jié)點(diǎn)有多個(gè)哈希值的另一個(gè)優(yōu)點(diǎn)是，可以逐漸將哈希值添加到環(huán)中或從環(huán)中移除，以免負(fù)載突然猛增。）

假設(shè)現(xiàn)在我們向環(huán)添加一個(gè)名為 C 的新節(jié)點(diǎn)，我們?yōu)?C 生成隨機(jī)哈希值：

A：0x5e6058e5

B：0xa2d65c0

C：0xe12f751c

0xa2d65c0+1 和 0xe12f751c（用于哈希到 A）之間的環(huán)空間現(xiàn)在被委托給 C。所有的其他請求將繼續(xù)哈希到與之前相同的那個(gè)節(jié)點(diǎn)。

為了處理這種權(quán)力轉(zhuǎn)移，該區(qū)間內(nèi)已經(jīng)在 A 上的所有請求都需要將其所有狀態(tài)轉(zhuǎn)移到 C。

圖 9

你現(xiàn)已了解了為什么分布式系統(tǒng)中需要哈希以均勻地分配負(fù)載。然而需要一致性哈希，確保一旦出現(xiàn)環(huán)變更，集群中只需要最小的工作量。

此外，節(jié)點(diǎn)需要存在于環(huán)上的多個(gè)位置，確保從統(tǒng)計(jì)學(xué)上來說負(fù)載更可能更均勻地分配。

為每個(gè)環(huán)變更迭代整個(gè)哈希環(huán)效率很低下。隨著分布式系統(tǒng)的規(guī)模不斷擴(kuò)大，勢必需要一種更高效的方法來查明什么發(fā)生了變更，從而盡可能減小環(huán)變更對性能帶來的影響。這就需要新的索引和數(shù)據(jù)類型來解決這個(gè)問題。