跳轉到

9.2 分散式雜湊與一致性雜湊#

概念說明#

把 N 筆鍵值資料分散到 S 台伺服器，最直覺的做法是 hash(key) mod S。問題在於節點增減：S 從 10 變 11 時，幾乎所有鍵的落點都改變，需要搬移 ~N 筆資料——叢集伸縮瞬間變成全量重組。

一致性雜湊（consistent hashing，1997）把鍵與節點都映射到同一個環狀空間（如 0 ~ 2^32）：

  1. 每個節點依其位址（或多個虛擬節點）雜湊到環上。
  2. 鍵的擁有者 = 環上順時針第一個遇到的節點。
  3. 新增節點時，只有「落在它與前一節點之間」的鍵需要搬移——平均只動 N/S 筆（1/S 的資料）。

純一致性雜湊的缺點是負載不均：節點少時，各段弧長差異可能達數倍。解法是虛擬節點（vnode）：每台實體機器掛 100~1000 個環上點，負載標準差降到個位數百分比。

有界載入（bounded loads）是另一個加強：給定環分配後，若某節點負載超過平均 ×(1+ε)，就把超出部分順時針讓給下一節點，保證負載偏差有上界。

演算法步驟#

  1. ring = sorted(各虛擬節點的雜湊值)，附節點標籤。
  2. 查詢鍵 k：h = hash(k)，在 ring 中二分搜尋第一個 ≥ h 的點；環尾回繞到開頭。
  3. 新增節點：計算其 vnode 雜湊值插入 ring；搬移範圍 = 新點到「其順時針前一點」之間的鍵。
  4. 移除節點：從 ring 刪除其 vnode；其鍵由順時針下一節點接管。

Python 範例#

import bisect, hashlib

def h(s):
    return int(hashlib.md5(s.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, vnodes=100):
        self.ring, self.nodes, self.vnodes = [], {}, vnodes

    def add_node(self, name):
        for i in range(self.vnodes):
            key = h(f"{name}#v{i}")
            bisect.insort(self.ring, key)
            self.nodes[key] = name

    def remove_node(self, name):
        dead = [k for k, v in self.nodes.items() if v == name]
        for k in dead:
            self.nodes.pop(k)
            self.ring.remove(k)

    def get_node(self, key):
        if not self.ring: return None
        pos = bisect.bisect_left(self.ring, h(key)) % len(self.ring)
        return self.nodes[self.ring[pos]]

ring = ConsistentHashRing(vnodes=50)
for n in ["A", "B", "C"]:
    ring.add_node(n)

keys = [f"key{i}" for i in range(3000)]
before = [ring.get_node(k) for k in keys]
from collections import Counter
print("3 節點負載:", dict(Counter(before)))

ring.add_node("D")                       # 擴容
after = [ring.get_node(k) for k in keys]
moved = sum(b != a for b, a in zip(before, after))
print("加入節點 D 後搬移比例:", f"{moved/len(keys):.1%}",
      "（naive mod 將搬移 ~75%）")
print("4 節點負載:", dict(Counter(after)))

複雜度與 I/O 成本分析#

  • 查詢定位：O(log V)（V 為環上虛擬節點總數，記憶體二分搜尋，0 次磁碟 I/O）。
  • 擴縮容搬移：N/S 筆（理論），虛擬節點使其更平滑；對比 naive mod 的 ~N 筆。
  • 副本放置：沿環順時針再取 2~3 個「不同機房」的節點，同時滿足負載與容錯。
  • 與 9.3 節 erasure coding 搭配：環決定「誰負責」，編碼決定「存什麼」。

練習#

  1. 把 vnodes 從 50 降到 5，觀察負載標準差與搬移比例的變化。
  2. 證明或說明：加入一個節點時，需搬移的鍵期望數為 N/(S+1)。
  3. 實作 bounded-loads：負載超過平均 1.25 倍時順時針讓渡，重測負載分布。