如果你有 n 個快取服務器，一個常見的負載均衡方式是使用以下的哈希方法：

服務器索引 = 哈希(鍵) % N，其中 N 是服務器池的大小，

讓我們通過一個例子來說明這是如何作業的，如表5-1所示，我們有4臺服務器和8個字串鍵及其哈希值，

為了獲取存盤某個鍵的服務器，我們執行模運算 f(鍵) % 4，例如，哈希(鍵0) % 4 = 1 意味著客戶端必須聯系服務器1來獲取快取的資料，圖5-1展示了基于表5-1的鍵的分布，

當服務器池的大小固定且資料分布均勻時，這種方法作業得很好，然而，當新的服務器被添加，或者現有的服務器被移除時，就會出現問題，例如，如果服務器1離線，服務器池的大小就變成了3，使用相同的哈希函式，我們得到的鍵的哈希值是相同的，但是應用模運算會因為服務器數量減少了1而得到不同的服務器索引，我們應用 哈希 % 3 得到的結果如表5-2所示：

圖5-2展示了基于表5-2的新鍵分布，

如圖5-2所示，大多數鍵都被重新分配了，而不僅僅是那些最初存盤在離線服務器（服務器1）中的鍵，這意味著，當服務器1離線時，大多數快取客戶端將連接到錯誤的服務器來獲取資料，這導致了一場快取未命中的風暴，一致性哈希是一種有效的技術來緩解這個問題，

一致性哈希

參考自維基百科："一致性哈希是一種特殊的哈希，使得當哈希表大小改變且使用一致性哈希時，平均只有 k/n 個鍵需要被重新映射，其中 k 是鍵的數量，n 是槽位的數量，相比之下，在大多數傳統哈希表中，陣列槽位數量的變化導致幾乎所有的鍵都需要被重新映射[1]”，

哈希空間和哈希環

現在我們理解了一致性哈希的定義，讓我們了解它是如何作業的，假設使用SHA-1作為哈希函式f，哈希函式的輸出范圍是：x0, x1, x2, x3, ..., xn，在密碼學中，SHA-1的哈希空間從0到2^160 - 1，也就是說，x0 對應0，xn 對應2^160 - 1，所有其他的哈希值都落在0和2^160 - 1之間，圖5-3展示了哈希空間，

通過連接兩端，我們得到一個如圖5-4所示的哈希環：

哈希服務器

使用相同的哈希函式f，我們根據服務器的IP或名字將服務器映射到環上，圖5-5顯示了4臺服務器被映射到哈希環上，

哈希鍵

值得一提的是，這里使用的哈希函式與“重哈希問題”中的不同，并且沒有模運算，如圖5-6所示，4個快取鍵（key0，key1，key2和key3）被哈希到哈希環上，

服務器查找

為了確定一個鍵存盤在哪個服務器上，我們從環上的鍵位置順時針方向進行尋找，直到找到一個服務器，圖5-7解釋了這個程序，順時針方向，key 0 存盤在 server 0上；key1 存盤在 server 1 上；key2 存盤在 server 2 上；key3 存盤在 server 3 上，

添加服務器

使用上述邏輯，添加新服務器只需要重新分配一部分鍵，

在圖5-8中，新增 server 4 后，只有 key0 需要被重新分配，k1, k2, 和 k3 仍然在相同的服務器上，讓我們仔細看看這個邏輯，在 server 4 添加之前，key0 存盤在 server 0 上，現在，key0 將存盤在 server 4 上，因為 server 4 是它從環上的 key0 位置順時針方向遇到的第一個服務器，其他的鍵根據一致性哈希演算法不需要重新分配，

移除服務器

當服務器被移除時，只有少部分的鍵需要通過一致性哈希進行重新分配，在圖5-9中，當 server 1 被移除時，只有 key1 必須被映射到 server 2，其余的鍵不受影響，

基本方法中的兩個問題

一致性哈希演算法是由MIT的Karger等人提出的[1]，基本步驟如下：

• 使用均勻分布的哈希函式將服務器和鍵映射到環上，
• 要找出鍵映射到哪個服務器，從鍵位置開始順時針方向找到環上的第一個服務器，

這種方法存在兩個問題，首先，考慮到服務器可能會被添加或移除，不可能在環上為所有服務器保持相同大小的磁區，磁區是相鄰服務器之間的哈希空間，每個服務器被分配到的環上的磁區大小可能非常小或者相當大，在圖5-10中，如果s1被移除，s2的磁區（雙向箭頭高亮表示）就是s0和s3磁區的兩倍大，

第二，環上的鍵分布可能非均勻，例如，如果服務器映射到圖5-11中列出的位置，大部分的鍵都存盤在server 2上，然而，server 1 和 server 3 沒有任何資料，

一種被稱為虛擬節點或副本的技術被用來解決這些問題，

虛擬節點

虛擬節點是指實際節點，每個服務器在環上都由多個虛擬節點表示，在圖5-12中，server 0 和 server 1 都有3個虛擬節點，這個3是隨意選擇的；在實際系統中，虛擬節點的數量要多得多，我們不再使用 s0，而是使用 s0_0, s0_1 和 s0_2 來在環上表示 server 0，同樣，s1_0, s1_1 和 s1_2 在環上表示 server 1，有了虛擬節點，每個服務器就負責多個磁區，標簽為 s0 的磁區（邊）由 server 0 管理，另一方面，標簽為 s1 的磁區由 server 1 管理，

要找出一個鍵存盤在哪個服務器上，我們從鍵的位置順時針方向去找環上遇到的第一個虛擬節點，在圖5-13中，要找出k0存盤在哪個服務器上，我們從k0的位置順時針方向找到虛擬節點s1_1，它指向server 1，

隨著虛擬節點數量的增加，鍵的分布變得更加均衡，這是因為隨著虛擬節點數量的增加，標準差變得更小，導致資料分布均衡，標準差衡量了資料的分散程度，在線研究的一項實驗結果[2]表明，當有一百或兩百個虛擬節點時，標準差在均值的5%（200個虛擬節點）到10%（100個虛擬節點）之間，當我們增加虛擬節點數量時，標準差會變小，然而，我們需要更多的空間來存盤虛擬節點的資料，這是一個權衡，我們可以調整虛擬節點的數量以適應我們的系統需求，

找到受影響的鍵

當添加或移除一個服務器時，部分資料需要被重新分布，我們如何找到受影響的范圍以重新分配鍵呢？

在圖5-14中，server 4被添加到環中，受影響的范圍從s4（新添加的節點）開始，逆時針移動到找到一個服務器（s3），因此，位于s3和s4之間的鍵需要被重新分配給s4，

當一個服務器（s1）如圖5-15所示被移除時，受影響的范圍從s1（被移除的節點）開始，逆時針繞環移動到找到一個服務器（s0），因此，位于s0和s1之間的鍵必須被重新分配給s2，

總結

在這一章，我們深入討論了一致性哈希，包括為什么需要它以及它是如何作業的，一致性哈希的好處包括：

• 當服務器被添加或移除時，最小化鍵的重新分布，
• 因為資料更均勻地分布，所以易于橫向擴展，
• 緩解熱點鍵問題，過度訪問特定的分片可能導致服務器過載，想象一下，Katy Perry、Justin Bieber和Lady Gaga的資料全部都在同一個分片上，一致性哈希通過更均勻地分布資料來緩解這個問題，

一致性哈希在現實世界的系統中被廣泛應用，包括一些著名的系統：

• Amazon的Dynamo資料庫的磁區組件 [3]
• Apache Cassandra中跨集群的資料磁區 [4]
• Discord聊天應用 [5]
• Akamai內容分發網路 [6]
• Maglev網路負載均衡器 [7]

恭喜你走到這一步！現在給自己一個贊，干得好！

參考資料

[1] 一致性哈希：https://en.wikipedia.org/wiki/Consistent_hashing

[2] 一致性哈希：

https://tom-e-white.com/2007/11/consistent-hashing.html

[3] Dynamo：亞馬遜的高可用鍵值存盤：
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[4] Cassandra - 一個去中心化的結構化存盤系統：

http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF

[5] 如何將Discord Elixir擴展到500萬并發用戶：
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b

[6] CS168：現代演算法工具箱第一課：簡介和一致性哈希：http://theory.stanford.edu/~tim/s16/l/l1.pdf

[7] Maglev：一個快速可靠的軟體網路負載均衡器：
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf

標籤：其他

上一篇：什么是一致性哈希？一致性哈希是如何作業的？如何設計一致性哈希？

下一篇：返回列表