一貫性ハッシュ：マシンを 1 台足してもほぼ全鍵を並べ直さない理由

分割の最初の思いつきは hash(key) % N です。均等で単純で、問題は 1 つだけ。N が変わるとほぼ全鍵が引っ越します。4 台から 5 台に増やすと、同じ添字に残る鍵は 5 分の 1 です。

ハッシュ空間を環にする

一貫性ハッシュは [0, 2^32) を環としてつなぎ、マシンも鍵もハッシュ値で環上に置き、各鍵を時計回りで最初に出会うマシンに割り当てます。

マシンを 1 台足すとき、移動が必要なのは「新しいマシン」と「反時計回りでその手前のマシン」の間にある鍵だけです。期待値は約 1/N で、他の鍵の持ち主は変わりません。

仮想ノードが偏りを直す

台数が少ないと、環上の位置はランダムなハッシュなので分布が目に見えて偏ります。1 台が環の半分を持つこともあります。標準的な対処が仮想ノードです。各物理マシンに環上の点を 100〜200 個置き、鍵はいったん仮想ノードに落としてから物理マシンに対応させます。

function buildRing(nodes, replicas = 120) {
  const points = [];
  for (const node of nodes) {
    for (let i = 0; i < replicas; i += 1) {
      points.push({ hash: hash32(node + '#' + i), node });
    }
  }
  points.sort((a, b) => a.hash - b.hash);
  return points;
}

function owner(points, key) {
  const h = hash32(key);
  let lo = 0;
  let hi = points.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (points[mid].hash < h) lo = mid + 1;
    else hi = mid;
  }
  return points[lo === points.length ? 0 : lo].node;
}

仮想ノードを増やすほど均等になり、代わりに環の配列が大きくなり構築も遅くなります。120 はよくある折衷案で、分布の標準偏差は十分小さく、検索は数回の二分探索で済みます。

使うべきでない場合

• データが静的：一度分けたら台数を変えないなら、移行量の利得はちょうどゼロで、仮想ノードと環の複雑さだけが残ります。整列したリストを切る方が簡単です。
• 厳密な均等が必要：仮想ノードは近似です。より単純な同等案はランデブーハッシュで、各候補について hash(key + node) を計算し最大を取ります。環も仮想ノードも不要で、代わりに 1 回の照会で N 個のハッシュを計算します。N が小さいほど有利です。

一貫性ハッシュが買うのはノード構成が変わるときの移行量。変わらないなら、その出費は無駄です。