一致性雜湊#

當系統要把資料或請求分散到 N 台伺服器時，最直覺的做法是 hash(key) % N。但只要 N 一變動（擴容、宕機），幾乎所有 key 都要重新分配，造成大規模快取失效與資料搬遷。一致性雜湊 (Consistent Hashing) 就是為了解決這個 rehash 問題而生，是分散式儲存做資料分片的基礎。

本節是 鍵值儲存 的前置元件；分片的整體策略取捨見 分散式系統 — 效能設計 / 資料分片。

傳統 hash % N 的問題#

serverIndex = hash(key) % N 在伺服器數固定時運作良好，但一旦 N 改變：

• 不只是壞掉那台的 key 要搬，幾乎所有 key 都會被映射到不同伺服器。
• 對快取系統而言意味著大規模 cache miss（風暴打到後端資料庫）。

舉例：4 台伺服器用 hash % 4，當 1 台下線、N 變成 3，8 個 key 中有 6 個被重新映射（75% 搬遷，而非預期的 25%）。

雜湊環#

把雜湊輸出空間（例如 SHA-1 的 0 到 2^160 − 1）首尾相接成一個環 (ring)：

flowchart TB
    subgraph Ring["雜湊環 (順時針)"]
        S0(("S0"))
        S1(("S1"))
        S2(("S2"))
        S3(("S3"))
        S0 --> S1 --> S2 --> S3 --> S0
    end
    K1["key1"] -.順時針找到.-> S1
    K2["key2"] -.順時針找到.-> S2

• 伺服器映射：用 IP 或名稱雜湊，落在環上某點。
• key 映射：用同一雜湊空間（不取模）落在環上。
• 查找規則：從 key 的位置順時針走，遇到的第一台伺服器就是負責節點。

增刪節點的最小遷移#

維基百科定義：一致性雜湊在表大小改變時，平均只有 k/n 個 key 需要重新映射（k = 總 key 數，n = 節點數）。

• 新增節點：只有「新節點與前一節點之間（順時針方向）」的 key 需要搬到新節點，其餘 key 不動。
• 移除節點：只有「該節點上的 key」搬到順時針的下一台，其餘不動。

虛擬節點與均衡#

基本一致性雜湊有兩個分布不均的問題：

1. 分區大小不均：相鄰節點間的弧長（分區）在增刪後變得不一致，有些節點分到的環段可能是別人的 2 倍。
2. key 分布不均：key 雜湊後可能擠在某一段，造成某台滿載、某台空轉。

解法是虛擬節點 (Virtual Nodes / Replicas)：每台實體伺服器在環上對應多個虛擬點（s0_0、s0_1、s0_2 …）。

• 虛擬節點越多 ➡️ 分布越均勻 ➡️ 標準差越小。
• 量化：約 100 個虛擬節點時標準差約為平均的 10%，提升到 200 個時降到約 5%。
• 查找時若遇到屬於同一實體伺服器的虛擬節點，要略過，只選不同實體節點。

虛擬節點數是一個權衡。 越多越均衡，但要維護的中繼資料（環上的點與對應關係）也越多，記憶體與查找成本上升。實務上依叢集規模選一個讓標準差可接受的數量即可，並非越多越好。

實際應用#

• Amazon Dynamo：資料分片的核心元件。
• Apache Cassandra：叢集間的資料分區。
• 其他：Discord、Akamai（CDN）、Maglev（負載平衡器）。

虛擬節點還帶來異質性 (heterogeneity)：容量大的伺服器可分配更多虛擬節點，自然承擔更多資料。

小結#

一致性雜湊本身只解決「key ➡️ 節點」的映射。要做成可用的分散式儲存，還需要在它之上加複製、Quorum、衝突解決——這正是下一節 鍵值儲存 的主題。