Published on

[系統設計筆記] 一致性哈希（Consistent Hashing）

Authors
  • avatar
    Name
    Vic Chen
    Twitter

前言

在分散式系統中，當我們要將資料或請求分配到多台伺服器時，最直覺的做法是用 取餘數（mod hashing）。
例如：hash(key) % N，其中 N 是節點數量。

但這樣有一個大問題：當節點數量改變時，幾乎所有的 key 都要重新映射，導致大量資料需要搬移。
這在實際系統中幾乎不可行。

為了解決這個問題，就出現了 一致性哈希（Consistent Hashing） 的設計。

為什麼需要一致性哈希？（例子）

1. 最直覺的做法：hash(key) % N

一切看起來很合理。

但當流量增加，我們新增第 4 台伺服器 D：

  • 哈希公式變成 hash(key) % 4
  • 結果是 幾乎所有 key 的位置都會變動
  • 意味著 cache hit rate 幾乎歸零，所有資料都要重新搬

這就是傳統 hash 分配的痛點。

2. 一致性哈希的解法

一致性哈希的核心做法是 把節點和 key 都放到一個環形哈希空間（hash ring），key 順時針找到第一個節點。

  • 新增 D 後，只有 300~400 範圍的 key 需要搬到 D，其餘 key 保持不動。
  • 好處：大部分的 cache 還是有效的，不需要大規模搬移資料

3. 負載不均的問題

如果環上節點分布不均，可能出現某一台伺服器負責了過半數的 key，造成負載不平衡。

解法是引入 虛擬節點（Virtual Nodes, vNodes）：

  • 每個實體節點不只映射到一個位置，而是映射到環上的多個位置
  • key 的分布更平均，避免某個節點過熱

一致性哈希的基本概念

一致性哈希的核心想法是把 節點和資料都映射到一個環形的哈希空間（hash ring）：

  1. 將哈希函數的輸出視為一個環（0 到 2³² - 1）。
  2. 每個節點根據其 ID（例如 IP 或名稱）經過哈希，放到環上的一個位置。
  3. 每個 key 也經過哈希，放到環上。
  4. key 沿著環 順時針 找到的第一個節點，就是它應該存放的節點。

好處

  • 當 節點數量改變（新增或刪除伺服器）時，只有少部分 key 需要重新分配。
  • 避免了 mod hashing 幾乎全量搬移的問題。

Virtual Nodes（虛擬節點）

在實務上，如果每個節點只出現一次，分布可能會不均勻： 有些節點負責的範圍大，有些小 → 負載不均。

為了解決這個問題，一致性哈希引入了 虛擬節點（Virtual Nodes, vNodes）：

  1. 每個實體節點會被映射成多個 vnode（例如 A#1、A#2、A#3…）。
  2. key 映射到環上後，先找到對應的 vnode，再由 vnode 映射到實體節點。
  3. 這樣能讓分布更平均，降低「某節點負載過大」的問題。

舉例

假設有三個節點：A、B、C。

  • key1=60 → A#1 → 實體節點 A
  • key2=130 → B#1 → 實體節點 B
  • key3=250 → A#2 → 仍是實體節點 A，但落在另一個 vnode
  • key4=400 → B#2 → 仍是實體節點 B，但落在另一個 vnode

新增或刪除節點時，只影響該節點的 vnodes 對應範圍，讓搬遷更平滑。

優缺點整理

優點

  • 減少節點增減時的資料搬遷範圍。
  • 支援大規模分散式系統（例如分布式 cache、NoSQL 資料庫）。
  • 搭配虛擬節點後，負載更平均。

缺點

  • 實作相對複雜，需要維護 hash ring 與 vnodes 的映射關係。
  • 節點數量太少時，仍可能負載不均。
  • 在極大規模下，需要設計額外的協調與監控機制。

一致性哈希實際應用

雖然範例側重於資料庫擴展，但一致性哈希適用於任何 Server cluster 之間任何分發資料的場景。可以是資料庫、快取、訊息代理...等，甚至只是一組 Application Server。

可以看到一致性哈希在許多高度依賴可擴展系統中得到應用，例如：

  • Apache Cassandra：使用一致性哈希在環上分發數據
  • Amazon DynamoDB：底層使用了一致性哈希
  • Content Delivery Networks (CDNs)：使用一致性哈希來決定哪個 edge server 應該快取內容

總結

一致性哈希是一個解決 動態節點變化 下資料分配問題的經典方法。 它透過「環狀映射」與「虛擬節點」機制，有效地降低了 cache 失效與資料搬遷成本。

這個概念廣泛應用在：

  • 分布式快取（如 Memcached、Redis Cluster）：用來決定某個 key 存在哪個節點。
  • 分布式儲存（如 Dynamo、Cassandra）：負責將資料分片（sharding）到不同的節點。
  • 分布式任務分配

面試常見考點

  1. 為什麼不用 hash(key) % N？

    • 節點數量改變時，需要全量搬移，代價過高。

  2. 一致性哈希如何解決？

    • 透過 hash ring，節點新增/刪除時，只有部分 key 搬移。

  3. 虛擬節點的作用？

    • 解決節點分佈不均，讓負載更平均。