如果你有 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