一貫性ハッシュによるサーバー振り分けの数理

素朴なモジュロ分散がなぜ破綻するのか

複数のサーバーへリクエストや key を振り分ける最も単純な方法は、key をハッシュしてサーバー台数 N で割った剰余を使うことです。

index = H(key) mod N
server = servers[index]

同じ key は常に同じ index を得るので、特定の key を常に同じサーバーへ固定できます。これはキャッシュサーバー群やセッションストア、シャーディングされた DB のように「この key はあのノードが持っている」という対応を保ちたい場面で決定的に重要です。ハッシュさえ均等なら N 台へほぼ均等に散る点でも優秀です。

問題は N が変わった瞬間に起きます。剰余は N に強く依存するため、N が1増減しただけで大半の key の H(key) mod N が別の値に変わります。

ノードの追加・削除は故障や増設で日常的に起きるため、「N が変わるたびに全 key が引っ越す」性質は分散システムにとって致命的です。求められるのは、ノードが1台増減したときに動く key を最小限に抑える写像です。

リング上配置という発想の転換

一貫性ハッシュ（コンシステントハッシュ）の鍵は、key とノードを同じハッシュ空間に置くことです。ハッシュ関数の出力域、たとえば 0 から 2^32 − 1 を、端と端をつないだ環（リング）とみなします。

ノード配置: pos(node)  = H(node の識別子) を環上の点とする
key 配置:   pos(key)   = H(key) を環上の点とする
割り当て:   key から時計回りに進んで最初に出会うノードが担当

各ノードは、自分の手前のノードから自分までの円弧（区間）に落ちる key をすべて担当します。N で割る代わりに「環上で時計回りに最も近いノード」を選ぶこの方式は、ノード集合が変わっても各 key の担当を局所的にしか変えません。

この 1/N という移動量は、N が大きいほど1台の増減の影響が小さくなることを意味します。100台構成ならノード1台の故障で動くのは約1%の key だけで、残り99%は割り当てが保たれます。mod N が「ほぼ全滅」だったのと対照的です。

移動量が 1/N になる理由

なぜ移動量が 1/N に収まるのかは、環の幾何で説明できます。N 台のノードが環上にほぼ一様に散っているとき、環全体の長さを1に正規化すると各ノードが担当する区間の平均長は 1/N です。ノードを1台追加すると、その新ノードは既存のどれか1つの区間に割り込み、その区間の一部（時計回りに手前の側）だけを引き取ります。

追加前: 区間長の平均 = 1/N
追加後: 新ノードが1区間に割り込み、その区間内の key の一部だけが移動
移動する key ≈ 新ノードが引き取る弧の長さ ≈ 1/(N+1) 相当

引き取られるのは環全体のうち1区間ぶん、つまり全 key のおおよそ 1/N です。重要なのは、移動が新ノードと、その時計回りで次のノードとの間でしか起きないこと。それ以外のすべてのノード間の境界は不変なので、無関係な key は1つも動きません。これが mod N との決定的な差で、剰余では N が変わると全境界が一斉にずれるのに対し、環では増減点の周囲1か所しか境界が動きません。

仮想ノードで偏りを均す

素朴にノードを環上へ1点ずつ置くと、ハッシュのばらつきにより区間長が不均一になります。N が小さいと特に深刻で、たまたま近接して置かれたノードは小さな区間しか担当せず、逆に大きく間が空いたノードが過大な負荷を背負います。担当区間長の分散は、ノードがランダムに置かれる以上避けられません。

これを解くのが仮想ノード（virtual node、vnode）です。実ノード1台を、識別子に連番やソルトを付けた複数のハッシュ点として環上の多数の位置へ散らします。

実ノード A を V 個の仮想ノードとして配置:
  pos(A#0) = H("A#0")
  pos(A#1) = H("A#1")
  ...
  pos(A#(V−1)) = H("A#(V−1)")
A の総担当 = これら V 区間の合計

各実ノードが担当する総区間は V 個の独立な小区間の和になります。区間を多数に分割して平均すると、大数の法則により総担当長のばらつきが縮まります。担当割合の相対的な標準偏差はおおよそ 1/√V に比例して小さくなるため、V を増やすほど各ノードの負荷が均等値へ収束します。実装では V を100〜数百程度に取るのが一般的です。

実務での位置づけと限界

一貫性ハッシュは分散キャッシュ（memcached クライアントの ketama など）、分散 KVS や DB のシャーディング、L4/L7 のサーバー振り分けで広く使われます。プロキシとロードバランサがバックエンドを増減してもセッションアフィニティを保ちやすいのは、この写像の局所性のおかげです。同じ「最小移動量」の発想は、経路が増減しても既存フローを保ちたいECMP とフローハッシュでも、単純な mod の代替として採用されます。コンテンツを地理分散ノードへ振り分けるCDNのキャッシュ配置でも中核技術です。

ただし万能ではありません。ホットキー（特定 key への極端なアクセス集中）は、その key を持つ1ノードへ負荷が集まるため、ハッシュの均等性とは独立の問題として残ります。これには key 単位の複製や、人気 key だけ多重化するなどの別対策が要ります。また厳密な均等性を求める用途では、各ノードの実負荷を見て境界を動的調整する有界負荷付き一貫性ハッシュ（consistent hashing with bounded loads）のような拡張が使われます。基本形が解くのはあくまで「ノード増減時の再配置を最小化しつつ、統計的に均等へ寄せる」ことだと理解しておくと、適用範囲を見誤りません。