一致性雜湊：讓節點上下線只搬必要的資料

為什麼普通 modulo sharding 在擴縮容時會失控，而 hash ring 可以把搬遷限制在局部。

最直覺的 sharding 做法是把資料鍵做 hash，再用節點數取餘數：hash(key) % N。問題在於 N 一變，幾乎每個 key 的目標節點都會改變。對 cache 來說這會造成大量 miss；對 storage 來說這代表昂貴的 data migration；對 online service 來說，擴容本來是為了降載，卻可能先製造一波重分片風暴。

一致性雜湊不是讓資料永不移動，而是讓移動範圍與變動節點相關，而非與整個叢集規模相關。

把節點與 key 映射到同一個環，使用 successor rule 決定 owner。

一致性雜湊通常把 hash space 視為一個首尾相連的範圍，例如 0..359 或 0..2^32-1。每台節點先用 node id 做 hash 放上 ring；每個資料鍵也做 hash 放上 ring。查詢時從 key 的位置順時針走，遇到的第一個節點就是負責該 key 的 owner。

當新增節點 D 時，它只會接手自己與前一個節點之間的 key；當節點 B 掛掉時，原本屬於 B 的 key 會順時針交給下一個節點。其他 ring 區間不需要搬動。

function lookup(key, sortedRing) {
  const point = hash(key);
  const owner = sortedRing.find(node => node.point >= point);
  return owner || sortedRing[0]; // wrap around
}

用多個虛擬節點攤平負載，也讓不同容量的機器可以用權重參與分配。

Virtual Node（vnode）是把一台實體節點映射成多個 ring 上的位置，例如 A#1、A#2、A#3。key lookup 仍然找到第一個 vnode，但實際請求會送到該 vnode 背後的實體節點。vnode 越多，隨機 hash 造成的不均就越容易被平均掉。

vnode 數不是越多越好。太少會負載不均；太多會增加 routing table、membership gossip、rebalance plan 的成本。常見做法是按服務規模選一個足以平滑分布的 vnode 數，再用容量權重微調。

一致性雜湊降低 remapping，但 production 還要處理資料搬遷、複本與 membership 一致性。

在真實系統裡，ring 變更不是單純把節點加入陣列。資料或 cache entry 需要搬遷，client 需要拿到同一版 ring，replica placement 不能把多個複本放在同一故障域，否則一次 rack failure 仍然可能打掉多份資料。

1. Membership change：控制面確認節點健康、容量與版本，再產生新的 ring version。
2. Data movement：新 owner 從舊 owner backfill key range；過程中可能需要 dual read 或 forwarding。
3. Traffic cutover：client 或 gateway 切到新 ring version，必要時保留短暫相容窗口。
4. Replica awareness：第二、第三複本通常取後續不同 failure domain 的節點，而不是只看下一個 vnode。

切換情境，觀察新增或移除節點時哪些 key 真的需要 remap。

下方模擬器用簡化的 0..359 ring 展示 4 個實體節點與 12 個 key。切換情境後，受影響的 key 會被標記出來；你可以直觀看到一致性雜湊的核心價值：不是零搬遷，而是只搬必要的一小段。

回答題目時要把 ring、vnode、replica 與 operational safety 一起講清楚。

面試中提到一致性雜湊時，不要只畫一個環。更完整的回答應該說明它解決了什麼、沒有解決什麼，以及你如何把它放進可運維的系統裡。