一貫性ハッシュとリングによる負荷分散

剰余ハッシュが破綻する理由

キーをノードに振り分ける最も素朴な方法は、ハッシュ値をノード数で割った剰余を使う node = hash(key) % N です。N が固定なら均等で速い。問題は N が変わった瞬間 です。

# N=4 → N=5 にしただけで割り当てがほぼ総入れ替え
hash(key)=100 : 100 % 4 = 0  →  100 % 5 = 0   (同じ)
hash(key)=101 : 101 % 4 = 1  →  101 % 5 = 1   (同じ)
hash(key)=102 : 102 % 4 = 2  →  102 % 5 = 2   (同じ)
hash(key)=103 : 103 % 4 = 3  →  103 % 5 = 3   (同じ)
hash(key)=104 : 104 % 4 = 0  →  104 % 5 = 4   (移動)

剰余は除数が変わると全体の周期がずれるため、平均すると (N-1)/N、すなわちほぼ全キーが別ノードへ移る。これがキャッシュサーバーやシャードに対して致命的です。ノードを1台足しただけでキャッシュがほぼ全滅し、バックエンドDBへリクエストが殺到する（キャッシュスタンピード／メタステーブル障害 の典型的な引き金）。一貫性ハッシュ（consistent hashing）は、この「再配置を最小化する」ことだけを狙った仕組みです。

リングという発想：移動を K/N に抑える

一貫性ハッシュは、ハッシュの出力空間を 円環（リング） とみなします。例えば 0 から 2^32 − 1 を端で繋いだ環です。

1. 各ノードを hash(node_id) でリング上の点に置く。
2. 各キーも hash(key) でリング上の点に置く。
3. キーは、自分の位置から 時計回りに最初に出会うノード が担当する。

ノードが N 台、キーが K 個でリング上に一様分布していれば、1台の増減で移動するキーは平均 K/N 個。N=100 なら全体の約1%で済みます。剰余の「ほぼ100%移動」と比べると桁違いです。これがCDN、分散キャッシュ（memcached の ketama、Amazon Dynamo、Cassandra の旧来パーティショナ）、L4/L7ロードバランサのバックエンド選択などで広く使われる理由です。

仮想ノードで偏りを均す

素朴なリングには弱点があります。ノードをリング上のたった1点に置くと、区間の長さがばらつく。たまたま2ノードが近接すれば、その手前の区間が長くなり、1台に負荷が集中します。ノード数が少ないほどこの偏りは深刻で、3台程度だと最悪で理論均等の2倍近い負担差が出ることもあります。

解決策が 仮想ノード（virtual node, vnode） です。物理ノード1台を、hash(node_id + "#0"), hash(node_id + "#1"), … と添字を変えて リング上の多数の点に分身させる。例えば各物理ノードを150個の vnode に分けると、リング上に物理3台×150＝450点がばらまかれ、区間長が平均化されます。

# vnode数を増やすほど区間長の分散（ばらつき）が縮む
# 標準偏差は概ね vnode数の平方根に反比例して小さくなる
vnode  16 : 負荷のばらつき 大
vnode 100 : 負荷のばらつき 中
vnode 500 : 負荷のばらつき 小（実用上ほぼ均等）

bounded-load：偏りに上限を課す

vnode で平均化しても、特定キーへのアクセス集中（ホットキー） は均せません。リング上の割り当てがどれだけ均等でも、1個の人気キーが特定ノードを焼き切ることはあります。これに対し consistent hashing with bounded loads は、各ノードに 許容上限 を設けます。

考え方は単純です。全体の平均負荷を avg とし、上限を (1 + ε) * avg とする（ε は許容余裕、例 0.25 なら平均の1.25倍まで）。キーを時計回りで割り当てる際、最初に出会ったノードが既に上限に達していれば、さらに時計回りに進んで空きのある次のノードへ送る。

理論上、ε を固定したとき1キーの移動が触れるノード数は定数に抑えられ、最大負荷が平均の (1+ε) 倍を超えないことが保証されます。均一性の上限保証が欲しいときの選択肢です。

rendezvousハッシュ（HRW）：リングを捨てる

もう一つの系統が rendezvous hashing（別名 HRW: Highest Random Weight） です。リングを一切持ちません。各キーについて、全ノードとの組み合わせでスコアを計算し、最大スコアのノードを選ぶだけです。

# 各キーごとに全ノードのスコアを出し、最大を担当に選ぶ
def pick(key, nodes):
    best, best_node = -1, None
    for n in nodes:
        s = hash(key + n.id)        # キーとノードを混ぜた擬似乱数スコア
        if s > best:
            best, best_node = s, n
    return best_node

ノードを1台足すと、各キーは「新ノードのスコアが既存の最大を上回るか」だけを再判定する。上回ったキー（平均で全体の K/N）だけが移動し、それ以外は不変。一貫性ハッシュと同じ最小移動性を、リングや vnode のデータ構造なしで得られます。

rendezvous は N が小さければ O(N) 走査でも十分速く、しかも vnode を持たずに均等性が出る。Kubernetes の一部や分散キャッシュのクライアント側選択でよく使われます。一方 N が数千を超えると毎回の全走査が重く、リング＋vnode の O(log V) 探索が有利になります。

まとめ

• 剰余ハッシュ hash(key) % N は N の増減で ほぼ全キーが移動 し、キャッシュ総崩れと メタステーブル障害 を招く。一貫性ハッシュはこの再配置最小化が目的。
• リングは時計回り最初のノードへ割り当て、ノード増減の影響を1区間に局所化する。移動キーは平均 K/N 個。
• 仮想ノード（vnode） は物理ノードを多数点に分身させ、区間長のばらつきを縮める。重み付けと、ダウン時の肩代わり分散も同時に実現する。
• bounded-load は各ノードに (1+ε)*avg の上限を課し、超過時は次ノードへ送って最大負荷を保証する。ただし負荷状態を持つLBが前提。
• rendezvous（HRW） はリングを捨て、キーごとに全ノードのスコア最大を選ぶ。最小移動性を保ちつつ実装が単純で、中規模なら有力。詳しい遅延の見方は テール遅延の統計 も参照。