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

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

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

一致性哈希到底是什么？

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

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

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

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

圖 1

那么，我們?yōu)槭裁床皇褂猛环椒▉硖幚砭W(wǎng)絡(luò)上的請求？

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

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

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

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

如果其中一個突然出現(xiàn)故障，該怎么辦？使用樸素哈希方法，我們最終需要重新計算每一個鍵的哈希值，因為新映射依賴節(jié)點數(shù)量/內(nèi)存位置，如下所示：

圖 2：之前

圖 3：之后

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

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

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

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

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

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

當然，再次選擇該隨機數(shù)可以使用哈希函數(shù)來完成，但是除以可用位置數(shù)量的第二步被跳過，因為它不再是一個有限數(shù)。

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

圖 4

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

也就是說，地址高于請求地址的第一個服務(wù)器節(jié)點負責處理該請求。如果請求地址高于最高尋址節(jié)點，它由最小地址的服務(wù)器節(jié)點來處理，因為環(huán)遍歷以圓形方式進行。如下圖所示：

圖 5

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

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

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

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

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

圖 6

如何高效地實施一致性哈希算法？

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

從我們的哈希空間到集群中節(jié)點的映射，讓我們得以找到負責某個請求的節(jié)點。

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

映射

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

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

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

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

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

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

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

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

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

添加或刪除節(jié)點

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

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

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

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

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

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

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

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

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

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

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

請注意：這只是簡單描述了發(fā)生的情況；實際上，結(jié)構(gòu)和算法更加復(fù)雜，因為我們使用大于 1 的復(fù)制因子和專門的復(fù)制策略（只有一小部分的節(jié)點適用于任何特定的請求）。

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

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

一種解決方案就是遍歷與某個節(jié)點對應(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é)點的添加或刪除比較少見，迭代某個節(jié)點上的所有請求就行。

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

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

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

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

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

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

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

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

下面用一個實際的例子來介紹上述解釋。

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

于是我們得到：

A：0x5e6058e5

B：0xa2d65c0

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

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

圖 7

另一方面，B 負責區(qū)間 0x5e6058e5+1 直到 0xa2d65c0。因此，整個哈?？臻g是分布式的。

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

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

我們計算標識符的哈希值 H，比如 0x89e04a0a。

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

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

這個例子有點過于簡單，實際上，每個節(jié)點有一個哈希可能會很不公平地分配負載。

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

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

圖 8

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

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

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

A：0x5e6058e5

B：0xa2d65c0

C：0xe12f751c

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

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

圖 9

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

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

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