背景：分散式雜湊表#

**Distributed Hash Table（DHT）**是分散式可擴展系統中的基礎元件。雜湊表需要鍵（Key）、值（Value）和雜湊函數（Hash Function），其中雜湊函數將鍵映射到儲存值的位置：

index = hash_function(key)

假設我們正在設計一個分散式快取系統，有 n 台快取伺服器，直覺的雜湊函數是 key % n。這種方式簡單且常用，但有兩個主要缺點：

1. 無法水平擴展：每當新增一台快取伺服器，所有現有的映射都會失效。如果快取系統包含大量資料，維護將變得非常困難，幾乎不可能排程停機來更新所有快取映射
2. 負載不均衡：實際上，資料分佈通常不是均勻的。這會導致某些快取過熱飽和，而其他快取則閒置且幾乎為空

在這類情境下，Consistent Hashing 是改善快取系統的好方法。

什麼是 Consistent Hashing#

Consistent Hashing 是一種非常實用的分散式快取系統與 DHT 策略。它允許以最小化重組的方式在叢集中分配資料——當新增或移除節點時，只需搬移少量資料，使快取系統更易於擴展或縮減。

• 在 Consistent Hashing 中，當雜湊表大小改變（例如新增一台快取伺服器）時，只需要重新映射 k/n 個鍵（k 為總鍵數，n 為總伺服器數）
• 相比之下，使用 mod 作為雜湊函數時，所有鍵都需要重新映射

基本特性#

• 物件盡可能映射到同一台主機
• 當移除一台主機時，該主機上的物件會分配給其他主機
• 當新增一台主機時，它會從少數幾台主機中取得其份額，而不影響其他主機的資料

運作原理#

Consistent Hashing 將鍵映射到一個整數。假設雜湊函數的輸出範圍為 [0, 256)，將這些整數放置在一個**環（Ring）**上，值首尾相連。

運作步驟如下：

1. 給定一組快取伺服器，將它們雜湊到環上的整數位置
2. 要將一個鍵映射到伺服器時：
   • 將鍵雜湊為一個整數
   • 在環上順時針移動，直到找到第一台快取伺服器
   • 該伺服器即為存放此鍵的目標

新增與移除節點#

• 新增伺服器（例如伺服器 D）：原本映射到伺服器 C 的部分鍵會轉移到 D，其餘鍵不受影響
• 移除伺服器（例如伺服器 A 故障）：原本映射到 A 的所有鍵會落入 B，其他鍵不受影響

虛擬節點（Virtual Replicas）#

實際資料分佈往往不均勻，可能導致各快取伺服器的負載不平衡。

解決方法是為每台快取伺服器建立多個虛擬節點。不再將每台伺服器映射到環上的單一點，而是映射到多個點，使每台伺服器關聯環上的多個區段。

如果雜湊函數的分散性良好，隨著虛擬節點數量增加，鍵的分佈將更加均衡。