• 原文地址：How we implemented consistent hashing efficiently
• 原文作者：Srushtika Neelakantam
• 譯文出自：掘金翻譯計劃
• 本文永久鏈接：https://github.com/xitu/gold-miner/blob/master/TODO1/how-to-implement-consistent-hashing-efficiently.md
• 譯者：yqian1991
• 校對者：Starrier

Ably 的實時平臺分布在超過 14 個物理數據中心和 100 多個節點上。為了保證負載和數據都能夠均勻并且一致的分布到所有的節點上，我們采用了一致性哈希算法。

在這篇文章中，我們將會理解一致性哈希到底是怎么回事，為什么它是可伸縮的分布式系統架構中的一個重要工具。然后更進一步，我們會介紹可以用來高效率規模化實現一致性哈希算法的數據結構。最后，我們也會帶大家看一看用這個算法實現的一個可工作實例。

再談哈希

還記得大學里學的那個古老而原始的哈希方法嗎？通過使用哈希函數，我們確保了計算機程序所需要的資源可以通過一種高效的方式存儲在內存中，也確保了內存數據結構能被均勻加載。我們也確保了這種資源存儲策略使信息檢索變得更高效，從而讓程序運行得更快。

經典的哈希方法用一個哈希函數來生成一個偽隨機數，然后這個偽隨機數被內存空間大小整除，從而將一個隨機的數值標識轉換成可用內存空間里的一個位置。就如同下面這個函數所示：

location=hash(key)mod size

既然如此，我們為什么不能用同樣的方法來處理網絡請求呢？

在各種不同的程序、計算機或者用戶從多個服務器請求資源的場景里，我們需要一種機制來將請求均勻地分布到可用的服務器上，從而保證負載均衡，并且保持穩定一致的性能。我們可以將這些服務器節點看做是一個或多個請求可以被映射到的位置。

現在讓我們先退一步。在傳統的哈希方法中，我們總是假設：

• 內存位置的數量是已知的，并且
• 這個數量從不改變

例如，在 Ably，我們一整天里通常需要擴大或者縮減集群的大小，而且我們也要處理一些意外的故障。但是，如果我們考慮前面提到的這些場景的話，我們就不能保證服務器數量是不變的。如果其中一個服務器發生意外故障了怎么辦？如果繼續使用最簡單的哈希方法，結果就是我們需要對每個哈希鍵重新計算哈希值，因為新的映射完全決定于服務器節點或者內存地址的數量，如下圖所示：

節點變化之前

節點變化之后

在分布式系統中使用簡單再哈希存在的問題 — 每個哈希鍵的存放位置都會變化 — 就是因為每個節點都存放了一個狀態；哪怕只是集群數目的一個非常小的變化，都可能導致需要重新排列集群上的所有數據，從而產生巨大的工作量。隨著集群的增長，重新哈希的方法是沒法持續使用的，因為重新哈希所需要的工作量會隨著集群的大小而線性地增長。這就是一致性哈希的概念被引入的場景。

一致性哈希 — 它到底是什么？

一致性哈希可以用下面的方式描述：

• 它用虛擬環形的結構來表示資源請求者（為了敘述方便，后文將稱之為“請求”）和服務器節點，這個環通常被稱作一個?hashring。
• 存儲位置的數量不再是確定的，但是我們認為這個環上有無窮多個點并且服務器節點可以被放置到環上的任意位置。當然，我們仍然可以使用哈希函數來選擇這個隨機數，但是之前的第二個步驟，也就是除以存儲位置數量的那一步被省略了，因為存儲位置的數量不再是一個有限的數值。
• 請求，例如用戶，計算機或者無服務（serverless）程序，這些就等同于傳統哈希方法中的鍵，也使用同樣的哈希函數被放置到同樣的環上。

那么它到底是如何決定請求被哪個服務器所服務呢？如果我們假設這個環是有序的，而且在環上進行順時針遍歷就對應著存儲地址的增長順序，每個請求可以被順時針遍歷過程中所遇到的第一個節點所服務；也就是說，第一個在環上的地址比請求的地址大的服務器會服務這個請求。如果請求的地址比節點中的最大地址還大，那它會反過來被擁有最小地址的那個服務器服務，因為在這個環上的遍歷是以循環的方式進行的。方法用下圖進行了闡明：

理論上，每個服務器‘擁有’哈希環（hashring）上的一段區間范圍，任何映射到這個范圍里的請求都將被同一個服務器服務。現在好了，如果其中一個服務器出現故障了怎么辦，就以節點 3 為例吧，這個時候下一個服務器節點在環上的地址范圍就會擴大，并且映射到這個范圍的任何請求會被分派給新的服務器。僅此而已。只有對應到故障節點的區間范圍內的哈希需要被重新分配，而哈希環上其余的部分和請求 - 服務器的分配仍然不會受到影響。這跟傳統的哈希技術正好是相反的，在傳統的哈希中，哈希表大小的變化會影響?全部?的映射。因為有了?一致性哈希，只有一部分（這跟環的分布因子有關）請求會受已知的哈希環變化的影響。（節點增加或者刪除會導致環的變化，從而引起一些請求 - 服務器之間的映射發生改變。）

一種高效的實現方法

現在我們對什么是哈希環已經熟悉了...

我們需要實現以下內容來讓它工作：

一個從哈?？臻g到集群上所有服務器節點之間的映射，讓我們能找到可以服務指定請求的節點。

一個集群上每個節點所服務的請求的集合。在后面，這個集合可以讓我們找到哪些哈希因為節點的增加或者刪除而受到了影響。

映射

要完成上述的第一個部分，我們需要以下內容：

• 一個哈希函數，用來計算已知請求的標識（ID）在環上對應的位置。
• 一種方法，用來尋找轉換為哈希值的請求標識所對應的節點。

為了找到與特定請求相對應的節點，我們可以用一種簡單的數據結構來闡釋，它由以下內容組成：

• 一個與環上的節點一一對應的哈希數組。
• 一張圖（哈希表），用來尋找與已知請求相對應的服務器節點。

這實際上就是一個有序圖的原始表示。

為了能在以上數據結構中找到可以服務于已知哈希值的節點，我們需要：

• 執行修改過的二分搜索，在數組中查找到第一個等于或者大于（≥）你要查詢的哈希值所對應的節點 — 哈希映射。
• 查找在圖中發現的節點 — 哈希映射所對應的那個節點。

節點的增加或者刪除

在這篇文章的開頭我們已經看到了，當一個節點被添加，哈希環上的一部分區間范圍，以及它所包括的各種請求，都必須被分配到這個新節點。反過來，當一個節點被刪除，過去被分配到這個節點的請求都將需要被其他節點處理。

如何尋找到被哈希環的改變所影響的那些請求？

一種解決方法就是遍歷分配到一個節點的所有請求。對每個請求，我們判斷它是否處在環發生變化的區間范圍內，如果有需要的話，把它轉移到其他地方。

然而，這么做所需要的工作量會隨著節點上請求數量的增加而增加。讓情況變得更糟糕的是，隨著節點數量的增加，環上發生變化的數量也可能會增加。最壞的情況是，由于環的變化通常與局部故障有關，與環變化相關聯的瞬時負載也可能增加其他受影響節點發生故障的可能性，有可能導致整個系統發生級聯故障。

考慮到這個因素，我們希望請求的重定位做到盡可能高效。最理想的情況是，我們可以將所有請求保存在一種數據結構里，這樣我們能找到環上任何地方發生哈希變化時受到影響的請求。

高效查找受影響的哈希值

在集群上增加或者刪除一個節點將改變環上一部分請求的分配，我們稱之為?受影響范圍（affected range）。如果我們知道受影響范圍的邊界，我們就可以把請求轉移到正確的位置。

為了尋找受影響范圍的邊界，我們從增加或者刪除掉的一個節點的哈希值 H 開始，從 H 開始繞著環向后移動（圖中的逆時針方向），直到找到另外一個節點。讓我們將這個節點的哈希值定義為 S（作為開始）。從這個節點開始逆時針方向上的請求會被指定給它（S），因此它們不會受到影響。

注意：這只是實際將發生的情況的一個簡化描述；在實踐中，數據結構和算法都更加復雜，因為我們使用的復制因子（replication factors）數目大于 1，并且當任意給定的請求都只有一部分節點可用的情況下，我們還會使用專門的復制策略。

那些哈希值在被找到的節點和增加（或者刪除）的節點范圍之間的請求就是需要被移動的。

高效查找受影響范圍內的請求

一種解決方法就是簡單的遍歷對應于一個節點的所有請求，并且更新那些哈希值映射到此范圍內的請求。

在 JavaScript 中類似這樣：

for (const request of requests) {if (contains(S, H, request.hash)) {/* 這個請求受環變化的影響 */request.relocate();} } function contains(lowerBound, upperBound, hash) {const wrapsOver = upperBound < lowerBound;const aboveLower = hash >= lowerBound;const belowUpper = upperBound >= hash;if (wrapsOver) {return aboveLower || belowUpper;} else {return aboveLower && belowUpper;} }

?

由于哈希環是環狀的，僅僅查找 S <= r < H 之間的請求是不夠的，因為 S 可能比 H 大（表明這個區間范圍包含了哈希環的最頂端的開始部分）。函數?contains()?可以處理這種情況。

只要請求數量相對較少，或者節點的增加或者刪除的情況也相對較少出現，遍歷一個給定節點的所有請求還是可行的。

然而，隨著節點上的請求數量的增加，所需的工作量也隨之增加，更糟糕的是，隨著節點的增加，環變化也可能發生得更頻繁，無論是因為在自動節點伸縮（automated scaling）或者是故障轉換（failover）的情況下為了重新均衡訪問請求而觸發的整個系統上的并發負載。

最糟的情況是，與這些變化相關的負載可能增加其它節點發生故障的可能性，有可能導致整個系統范圍的級聯故障。

為了減輕這種影響，我們也可以將請求存儲到類似于之前討論過的一個單獨的環狀數據結構中，在這個環里，一個哈希值直接映射到這個哈希對應的請求。

這樣我們就能通過以下步驟來定位受影響范圍內的所有請求：

• 定位從 S 開始的第一個請求。
• 順時針遍歷直到你找到了這個范圍以外的一個哈希值。
• 重新定位落在這個范圍之內的請求。

當一個哈希更新時所需要遍歷的請求數量平均是 R/N，R 是定位到這個節點范圍內的請求數量，N 是環上哈希值的數量，這里我們假設請求是均勻分布的。

---

讓我們通過一個可工作的例子將以上解釋付諸實踐：

假設我們有一個包含節點 A 和 B 的集群。

讓我們隨機的產生每個節點的 ‘哈希分配’：（假設是32位的哈希），因此我們得到了

A:0x5e6058e5

B:0xa2d65c0

在此我們將節點放到一個虛擬的環上，數值?0x0、?0x1?和?0x2... 是被連續放置到環上的直到?0xffffffff，就這樣在環上繞一個圈后?0xffffffff?的后面正好跟著的就是?0x0。

由于節點 A 的哈希是?0x5e6058e5，它負責的就是從?0xa2d65c0+1?到?0xffffffff，以及從?0x0?到?0x5e6058e5?范圍里的任何請求，如下圖所示：

另一方面，B 負責的是從?0x5e6058e5+1?到?0xa2d65c0?的范圍。如此，整個哈?？臻g都被劃分了。

從節點到它們的哈希之間的映射在整個集群上是共享的，這樣保證了每次環計算的結果總是一致的。因此，任何節點在需要服務請求的時候都可以判斷請求放在哪里。

比如我們需要尋找 （或者創建）一個新的請求，這個請求的標識符是 ‘bobs.blog@example.com’。

我們計算這個標識的哈希 H ，比如得到的是?0x89e04a0a

我們在環上尋找擁有比 H 大的哈希值的第一個節點。這里我們找到了 B。

因此 B 是負責這個請求的節點。如果我們再次需要這個請求，我們將重復以上步驟并且又會得到同樣的節點，它會包含我們需要的的狀態。

這個例子是過于簡單了。在實際情況中，只給每個節點一個哈?？赡軐е仑撦d非常不均勻的分布。你可能已經注意到了，在這個例子中，B 負責環的?(0xa2d656c0-0x5e6058e5)/232=26.7%，同時 A 負責剩下的部分。理想的情況是，每個節點可以負責環上同等大小的一部分。

讓分布更均衡合理的一種方法是為每個節點產生多個隨機哈希，像下面這樣：

事實上，我們發現這樣做的結果照樣令人不滿意，因此我們將環分成 64 個同樣大小的片段并且確保每個節點都會被放到每個片段中的某個位置；這個的細節就不是那么重要了。反正目的就是確保每個節點能負責環上同等大小的一部分，因此保證負載是均勻分布的。（為每個節點產生多個哈希的另一個優勢就是哈?？梢栽诃h上逐漸的被增加或者刪除，這樣就避免了負載的突然間的變化。）

假設我們現在在環上增加一個新節點叫做 C，我們為 C 產生一個隨機哈希值。

A:0x5e6058e5

B:0xa2d65c0

C:0xe12f751c

現在，?0xa2d65c0+1?和?0xe12f751c?（以前是屬于A的部分）之間的環空間被分配給了 C。所有其他的請求像以前一樣繼續被哈希到同樣的節點。為了處理節點職責的變化，這個范圍內的已經分配給 A 的所有請求需要將它們的所有狀態轉移給 C。

現在你理解了為什么在分布式系統中均衡負載是需要哈希的。然而我們需要一致性哈希來確保在環發生任何變化的時候最小化集群上所需要的工作量。

另外，節點需要存在于環上的多個地方，這樣可以從統計學的角度保證負載被均勻分布。每次環發生變化都遍歷整個哈希環的效率是不高的，隨著你的分布式系統的伸縮，有一種更高效的方法來決定什么發生了變化是很必要的，它能幫助你盡可能的最小化環變化帶來的性能上的影響。我們需要新的索引和數據類型來解決這個問題。

總結

以上是生活随笔為你收集整理的[译] 我们是如何高效实现一致性哈希的的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。