如果你有 *n* 個緩存伺服器，一個常見的負載均衡方式是使用以下的哈希方法： *伺服器索引 = 哈希(鍵) % N*，其中 *N* 是伺服器池的大小。讓我們通過一個例子來說明這是如何工作的。如表5-1所示，我們有4台伺服器和8個字元串鍵及其哈希值。 ![image-2023052022160981 ...

如果你有 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個虛擬節點）之間。當我們增加虛擬節點數量時，標準差會變小。然而，我們需要更多的空間來存儲虛擬節點的數據。這是一個權衡，我們可以調整虛擬節點的數量以適應我們的系統需求。