為了達成水平擴展，將請求或資料有效率且平均地分散到各伺服器是很重要的。一致性雜湊（consistent hashing） 是達成這個目標的常用技術。但首先，讓我們深入看看這個問題。

重新雜湊問題（The rehashing problem）#

如果你有 n 台快取伺服器，平衡負載的常見方式是使用以下雜湊方法：

serverIndex = hash(key) % N，其中 N 是伺服器池的大小。

讓我們以一個範例來說明它如何運作。如表 1 所示，我們有 4 台伺服器與 8 個字串鍵及其雜湊值。

Table 1

要取得鍵儲存在哪一台伺服器，我們執行模數運算 f(key) % 4。例如，hash(key0) % 4 = 1 表示用戶端必須聯絡 server 1 來取得快取資料。圖 1 顯示根據表 1 的鍵分布。

當伺服器池大小固定且資料分布均勻時，這種方法運作良好。然而，當新增伺服器或移除既有伺服器時，問題就出現了。

例如，如果 server 1 離線，伺服器池大小變為 3。使用相同的雜湊函數，我們對某個鍵會得到相同的雜湊值。但套用模數運算後，由於伺服器數量減少了 1，會得到不同的伺服器索引。套用 hash % 3 後得到表 2 的結果：

Table 2

圖 2 顯示根據表 2 的新鍵分布。

如圖 2 所示，大部分的鍵都被重新分布了，而不只是原本儲存在離線伺服器（server 1）上的鍵。這意味著當 server 1 離線時，大多數快取用戶端會連到錯誤的伺服器去取資料，這會引發大量的快取未命中。

一致性雜湊是緩解此問題的有效技術。

一致性雜湊（Consistent hashing）#

引述自 Wikipedia：「一致性雜湊是一種特殊的雜湊方式，當雜湊表被重新調整大小且使用一致性雜湊時，平均只需要重新映射 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 之間。圖 3 顯示雜湊空間。

將兩端連接起來，我們得到一個雜湊環，如圖 4 所示：

雜湊伺服器#

使用同一個雜湊函數 f，我們根據伺服器的 IP 或名稱將伺服器映射到環上。圖 5 顯示了 4 台伺服器映射到雜湊環上。

雜湊鍵#

值得一提的是，這裡使用的雜湊函數與「重新雜湊問題」中的雜湊函數不同，且沒有模數運算。

如圖 6 所示，4 個快取鍵（key0、key1、key2 與 key3）被雜湊到雜湊環上。

伺服器查詢#

要決定一個鍵儲存在哪一台伺服器上，我們從鍵在環上的位置順時針走，直到找到一台伺服器為止。圖 7 說明了這個過程。

順時針走，key0 儲存在 server 0；key1 儲存在 server 1；key2 儲存在 server 2；key3 儲存在 server 3。

新增伺服器#

使用上述邏輯，新增一台伺服器只需要重新分布一小部分的鍵。

在圖 8 中，新增 server 4 之後，只有 key0 需要被重新分布。k1、k2 與 k3 仍維持在相同的伺服器上。讓我們仔細看看這個邏輯。在 server 4 加入之前，key0 儲存在 server 0。現在，key0 將儲存在 server 4，因為從 key0 在環上的位置順時針走時，server 4 是它遇到的第一台伺服器。其他鍵則不會根據一致性雜湊演算法被重新分布。

移除伺服器#

當移除一台伺服器時，使用一致性雜湊只有一小部分的鍵需要重新分布。在圖 9 中，當 server 1 被移除時，只有 key1 必須重新映射到 server 2。其餘的鍵不受影響。

基本方法的兩個問題#

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

• 使用均勻分布的雜湊函數，將伺服器與鍵映射到環上。
• 要找出一個鍵被映射到哪台伺服器，從鍵的位置順時針走，直到找到環上的第一台伺服器。

這個方法存在兩個問題。

首先，考慮到伺服器可以被新增或移除，要讓所有伺服器在環上的分區大小保持相同是不可能的。分區是相鄰伺服器之間的雜湊空間。指派給每台伺服器的分區大小有可能非常小或相當大。在圖 10 中，如果 s1 被移除，s2 的分區（以雙向箭頭標示）會是 s0 與 s3 分區的兩倍大。

其次，環上可能會有不均勻的鍵分布。例如，如果伺服器被映射到圖 11 列出的位置，大部分的鍵會儲存在 server 2，但 server 1 與 server 3 沒有任何資料。

一種稱為**虛擬節點（virtual node）或副本（replica）**的技術被用來解決這些問題。

虛擬節點#

虛擬節點指的是真實節點，每台伺服器在環上由多個虛擬節點代表。在圖 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 管理。

要找出某個鍵儲存在哪台伺服器上，我們從鍵的位置順時針走，找到環上遇到的第一個虛擬節點。在圖 13 中，要找出 k0 儲存在哪台伺服器上，我們從 k0 的位置順時針走，找到虛擬節點 s1_1，它指的是 server 1。

隨著虛擬節點數量增加，鍵的分布變得更均衡。這是因為虛擬節點越多，標準差越小，導致資料分布更均衡。標準差衡量資料的離散程度。

線上研究 [2] 所做的實驗結果顯示，使用一兩百個虛擬節點時，標準差介於平均值的 5%（200 個虛擬節點）到 10%（100 個虛擬節點）之間。當我們增加虛擬節點數量時，標準差會更小。然而，需要更多空間來儲存有關虛擬節點的資料。這是一種權衡，我們可以調整虛擬節點數量以符合系統需求。

找出受影響的鍵#

當伺服器被新增或移除時，需要重新分布一部分資料。我們如何找出受影響的範圍以重新分布鍵？

在圖 14 中，server 4 被加入到環上。受影響範圍從 s4（新加入的節點）開始，逆時針沿環移動，直到找到一台伺服器（s3）。因此，位於 s3 與 s4 之間的鍵需要被重新分布到 s4。

當 s1 伺服器被移除時，如圖 15 所示，受影響範圍從 s1（被移除的節點）開始，逆時針沿環移動，直到找到一台伺服器（s0）。因此，位於 s0 與 s1 之間的鍵必須被重新分布到 s2。

Wrap up#

在本章中，我們深入討論了一致性雜湊，包括為什麼需要它以及它如何運作。一致性雜湊的好處包括：

• 當伺服器被新增或移除時，重新分布的鍵數量被最小化。
• 由於資料分布更均勻，水平擴展變得容易。
• 緩解熱點鍵（hotspot key）問題。對特定 shard 的過度存取可能導致伺服器過載。想像 Katy Perry、Justin Bieber 與 Lady Gaga 的資料全部都在同一個 shard 上。一致性雜湊透過更均勻地分布資料來幫助緩解這個問題。

一致性雜湊在實際系統中被廣泛使用，包括一些著名的系統：

• Amazon Dynamo 資料庫的分區元件 [3]
• Apache Cassandra 跨叢集的資料分區 [4]
• Discord 聊天應用程式 [5]
• Akamai 內容傳遞網路 [6]
• Maglev 網路負載平衡器 [7]

恭喜你看到這裡！現在給自己拍拍背，做得好！