[譯] 我們是如何高效實現一致性哈希的

來自專欄掘金翻譯計劃2 人贊了文章

• 原文地址：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 為例吧，這個時候下一個伺服器節點在環上的地址範圍就會擴大，並且映射到這個範圍的任何請求會被分派給新的伺服器。僅此而已。只有對應到故障節點的區間範圍內的哈希需要被重新分配，而哈希環上其餘的部分和請求 - 伺服器的分配仍然不會受到影響。這跟傳統的哈希技術正好是相反的，在傳統的哈希中，哈希表大小的變化會影響 全部 的映射。因為有了 一致性哈希，只有一部分（這跟環的分布因子有關）請求會受已知的哈希環變化的影響。（節點增加或者刪除會導致環的變化，從而引起一些請求 - 伺服器之間的映射發生改變。）

一種高效的實現方法

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

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

1. 一個從哈希空間到集群上所有伺服器節點之間的映射，讓我們能找到可以服務指定請求的節點。
2. 一個集群上每個節點所服務的請求的集合。在後面，這個集合可以讓我們找到哪些哈希因為節點的增加或者刪除而受到了影響。

映射

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

• 一個哈希函數，用來計算已知請求的標識（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 的範圍。如此，整個哈希空間都被劃分了。

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

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

1. 我們計算這個標識的哈希 H ，比如得到的是 0x89e04a0a
2. 我們在環上尋找擁有比 H 大的哈希值的第一個節點。這裡我們找到了 B。

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

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

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

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

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

A:0x5e6058e5

B:0xa2d65c0

C:0xe12f751c

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

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

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

構建分散式系統是很難的事情。但是我們熱愛它並且我們喜歡談論它。如果你需要依靠一種分散式系統的話，選擇 Ably。如果你想跟我們談一談的話，聯繫我們！

在此特別感謝 Ably 的分散式系統工程師 John Diamond 對本文的貢獻。

Srushtika 是 Ably Realtime的軟體開發顧問

感謝 John Diamond 和 Matthew ORiordan。

如果發現譯文存在錯誤或其他需要改進的地方，歡迎到 掘金翻譯計劃 對譯文進行修改並 PR，也可獲得相應獎勵積分。文章開頭的 本文永久鏈接 即為本文在 GitHub 上的 MarkDown 鏈接。

掘金翻譯計劃 是一個翻譯優質互聯網技術文章的社區，文章來源為 掘金 上的英文分享文章。內容覆蓋 Android、iOS、前端、後端、區塊鏈、產品、設計、人工智慧等領域，想要查看更多優質譯文請持續關注 掘金翻譯計劃、官方微博、知乎專欄。

推薦閱讀：