一致性雜湊 (Consistent Hashing)
為什麼需要 Consistent Hashing
分散式系統常把資料分散到多台節點上。最直觀作法是 簡單模數雜湊：
server = hash(key) % N # N = 節點數
簡單 hash 的致命缺陷
當 N 改變（加入或移除節點），幾乎所有 key 的位置都會變動：
| N | key → node 對應 |
|---|---|
| N = 3 | 1,4,7→N1; 2,5,8→N2; 3,6,9→N0 |
| N = 4 | 1,5,9→N1; 2,6→N2; 3,7→N3; 4,8→N0 |
| 結果 | 9 個 key 有 7 個要搬（只剩 1、2 不動）— 大量搬遷 |
後果
大規模重新分配 → 暫時效能崩塌、快取全 miss、系統不穩定
Consistent Hashing 的核心價值
節點數變動時，只搬動一小部分資料，其他 key 保留在原節點。
運作原理
(a) Hash Ring（雜湊環）
把所有可能的 hash 值映射到一個圓環上（0 → MAX_HASH）。
- 每個節點用 hash 函數映射到環上某個位置
- 每筆資料也用
hash(key)計算位置 - 規則：資料順時針找到第一個節點，就交給它
0 / MAX
▲
│
D(900) ●─────┼─────● A(250)
\ │ /
\ │ /
順時針 \ │ /
\ │ /
\│/
C(750) ●────┼────● B(500)
│
(假設 hash=200 → 順時針碰到 A → 存 A)
(假設 hash=400 → 順時針碰到 B → 存 B)
(b) 新節點加入
假設新節點 E 落在 150
→ 只有「D(900) 與 E(150) 之間」的 key（0~150, 900~1024）
需從 A 搬到 E
→ 其餘資料完全不動
(c) 節點移除
假設 A(250) 下線
→ 原屬 A 的 key 順時針移到下一個節點 B(500)
→ 其他節點不受影響
Virtual Nodes（虛擬節點）
為什麼需要
基本版的 Consistent Hashing 有兩個問題：
| 問題 | 說明 |
|---|---|
| 資料分佈不均 | 節點少時 hash 環上位置可能集中，某些節點吃到一半以上的流量 |
| 忽略硬體差異 | 強機和弱機都只拿到一個區間，沒辦法「按能力分配」 |
例如移除節點 A 後，下游節點 B 要獨自扛下 A 的所有 key → 負載翻倍。
vNodes 做法
每個實體節點對應到 多個虛擬節點，分散在環上：
Physical Nodes → Virtual Nodes on Ring
A A1(250), A2(580), A3(920)
B B1(500), B2(830), B3(80)
C C1(750), C2(160), C3(420)
D D1(1024), D2(330), D3(660)
- 資料依舊「順時針找最近 vNode」
- vNode → 實體節點的對應關係由 routing table 維護
vNodes 的好處
| 好處 | 機制 |
|---|---|
| 分佈更均勻 | 每個節點有多個隨機位置，分散到整個環上 |
| 按能力分配 | 強機多放 vNodes（如 50 個），弱機少放（如 20 個） |
| 搬遷粒度細 | 節點變動時影響的 vNode 是多個小區段 → 負載變化更平滑 |
演算法複雜度
| 操作 | 複雜度（N=節點數, V=每節點 vNodes 數） |
|---|---|
| 查詢某 key 落點 | O(log(N·V))（環上二分搜） |
| 新增節點 | O(V·log(N·V)) |
| 移除節點 | O(V·log(N·V)) |
| 搬遷資料量 | O(K/N)（K=總 key 數）而非 O(K) |
Simplification-with-exceptions
邊界情況
- 並非所有分散式系統都用 consistent hashing — 例如 Elasticsearch 用
hash(shard_key) % num_shards 配合 shard 總數不常改，反而沒有環結構。 - Jump Hash / Rendezvous Hash 是較新的替代方案，記憶體佔用更低；但
consistent hashing 仍是面試常見答案。 - Hot key 問題 — 若單一 key 本身流量極大，換節點也救不了；需額外做 key-level
replication 或快取前置。 - Virtual Nodes 數量要取平衡 — 太少分佈不均；太多 routing table 大、查找
變慢（典型設定每節點 100~200 個 vNode）。
在 System Design Interview 的應用
記憶口訣：
「變動的節點 + 需要穩定歸屬 + 想少搬家」 → 用 consistent hashing
常見觸發場景
| 場景 | 說明 |
|---|---|
| Distributed Cache | Memcached / Redis 分片，避免 key % N 帶來的大規模失效 |
| Storage Sharding | Cassandra、DynamoDB 的 partition routing |
| Sticky Connections | 聊天室 / 即時服務，同 user 或 room 路由到固定節點 |
| API Gateway / Session | 減少跨節點 session 同步 |
| Rate Limiting | user_id / api_key 穩定分到對應節點做限流統計 |
| Metrics / Aggregation | (user_id, feature) 聚到同節點做累加 |
| CDN / Edge Routing | URL / 內容 ID 穩定映射到 edge 節點做快取 |
與其他概念的串連
流量大 → 需要 Horizontal Scaling（加節點）
→ 資料要分片到多節點（Sharding）
→ 節點會變動（擴縮容、故障）
→ 用 Consistent Hashing 讓搬遷最小化
→ vNodes 讓分佈更均勻
Related Notes
- 02-Distributed-Systems/03-Scalability — 水平擴展後的資料分片策略
- 02-Distributed-Systems/02-CAP-Theorem — 多節點系統的一致性取捨
- 01-Networking/06-Load-Balancing（01-Networking）— 客戶端 LB 也常用 consistent hashing
- 02-Distributed-Systems/Practice-Distributed-Systems