コンシステントハッシュ法

ノードとキーを同じ円形 token 空間へ置き、時計回りで最初の活動ノード token を所有者とする。一 token の追加・削除は隣接区間だけを変えるため、隣接区間の外のキーはすべて元の所有者を保つ。物理ノードが複数の仮想 token を持てば、その加入・離脱は各 token の複数区間に関わる。

本課の環は 360 目盛りで、359 の後は 0 に戻る。キー点はハッシュ位置、ノード印は所有の境界で、最後のバケットはない。

仕組み

右端を含む後続規則を使う。キー以上の最初の活動 token を選び、キー 260 とノード 260 が一致すればそのノードが持つ。以上の候補がなければ最小 token に戻る。

キー token と所有者は別だ。K5 は 155 にハッシュされ、ノードの変化で再ハッシュしない。変わるのは固定した 155 から最初に出会う活動後続だけ。

N1@20、N2@140、N3@280 なら、担当は次の区間になる。

• N1：ゼロをまたぐ (280,20]。
• N2：(20,140]。
• N3：(140,280]。

左を除き右を含めることで境界の所有者は一人となり、以上を探す検索と一致する。

ステップ実行

Node joins は K0–K11 を 10,35,60,95,125,155,185,205,235,260,310,345 に固定する。

1. 三ノード環を作り、N1、N2、N3 の負荷は 3、4、5 キー。
2. K11@345 の折り返しを確認する。345 以上の活動 token がなく、359 と 0 を越えて N1@20 に着く。所有表示は変わっても点は 345 のまま。
3. N2@140 と旧後続 N3@280 の間に N4@220 を準備する。まだ所有は変えない。
4. N4 を挿入し、一境界を増やす。
5. 元 N3 の (140,220] を N4 が受け持つ。
6. K5 は 155 に残り、後続だけ N3 から N4 へ変わる。
7. K6@185、K7@205 も同区間なので N4 へ移る。
8. 区間外の K0–K4、K8–K11 は九つとも元の所有者を保つ。
9. N1=3,N2=4,N3=5 が N1=3,N2=4,N3=2,N4=3 になる。三キー移動、九キー維持で、全ハッシュ位置は同じ。

Node leaves は N1@20、N2@140、N4@220、N3@280 から N2 を外す。旧区間 (20,140] は次の活動 N4 に移り、K1、K2、K3、K4 だけが変わる。環順 N1/N2/N4/N3 の 3/4/3/2 は、残る N1/N4/N3 の 3/7/2 となり、他八キーは不変。

仮想ノードと偏り

局所的な移動は均等負荷を保証しない。Virtual nodes の初期 N1@20、N2@80、N3@300 では、N3 が長い (80,300] を持ち 7 キー、N1 は 3、N2 は 2。最大最小差は 5 だ。

各物理ノードに三位置を与える。

• N1：20、140、260。
• N2：80、200、320。
• N3：100、240、300。

九印で大きい隙間を割り、K4、K5、K6、K9、K10 の五キーが物理所有者を変える。最終 N1=4,N2=5,N3=3 で差は 2 に縮む。

仮想ノードは位置であり機械ではない。N1 の三 token は同じ物理 N1 を指す。位置を増やすと偶然の大区間の分散を減らし、容量の重みも表せるが、有限サンプルの完全な均等は保証しない。

剰余分割より移動が少ない理由

V 個の活動 token を整列すれば、後続二分探索は O(log V)、末尾から先頭への折り返しは定数だ。これは与えられたキー token の検索費用で、ハッシュ計算は別にある。メンバー変更は token を挿入・削除し隣接区間を移す。整列配列と木では更新費用が違い、搬送量は区間内のキー数による。

独立一様ハッシュ、等重み、十分なキー数なら、既存 N 物理ノードへ一つ加える平均移動範囲は約 1/(N+1)。固定デモは局所性の証明であり、毎加入の厳密な割合ではない。

hash(key)%serverCount の剰余分割は、台数変更が全配置の除数を変える。Modulo contrast は同じ十二ハッシュを三台から四台へ変え、十キーが動く。残るのは K2@60、K7@205 だけ。環への N4 追加は三キーで済む。

用途と代替

メンバーが変わり移動が高価なキャッシュクラスタ、アプリ分割、オブジェクトストア、ルーターで役立つ。安定したキーのハッシュ、共有するメンバーのビュー、実データ移送が必要だ。

環は配置を選び、バイトを複製しない。レプリカ、障害検出、環バージョン展開、新所有者へのストリーミングは別プロトコル。大きい機械へ多くの token を与える重みも、分布、メタデータ、移動費用で測る。

ホットキーは仮想位置を増やしても一所有者へ向かう。複製、リクエストの集約、アプリ側の分割などが必要になる。整列済みの環を持ちたくなければ rendezvous hashing で各候補を採点して最大を選べる。台数固定なら剰余が簡単で、DB が再分割と複製を提供するなら既存の管理機構をまず使う。

境界ケース

• K11@345 は N1@20 へ戻る必要があり、忘れると環末尾が無担当になる。
• 仮想例の K9@260 は N1@260 に属する。右端は含む。
• 離脱区間は次の時計回り token へ移り、前のノードや全体への均等分散ではない。
• 間隔の偏りは大きい担当弧を作る。均衡と低移動は別の性質だ。
• ホットキーの要求量は仮想ノード数だけでは分割されない。
• 活動一台なら全キー、二台から一台失えば生存者が全部を持つ。ゼロ台なら所有者を選べず、実システムで処理が必要だ。
• ノード token 衝突には決定的な順位・重複処理が必要。キーとノードの一致は右端規則で扱う。画面は意図した K9 境界以外を固定の異なる位置にする。

よくある間違い

• メンバー変更でキーを再ハッシュする。token は活動一覧から独立し、点は動かさない。
• 反時計回りへ探し、時計回り用の区間を使う。
• 離脱者の区間を前のノードへ渡す。
• [a,b] と [b,c] の両端を含め、b を二者に持たせる。ここは (a,b]。
• 仮想ノードを追加サーバーと数える。
• 重み、token 数、ハッシュ、実サンプルを無視して完全均衡を約束する。
• 配置を複製・整合性プロトコルと同一視する。画面は一所有者のみを選ぶ。

モデルの範囲

0–359 の環、固定ノード、固定十二キー、各一コピー。複製、容量重みの運用、同時メンバー変更、転送費用、障害検出、ストリーム移動、ホットキー対策は省く。仮想ノードは一ステップで現れ、メンバー管理プロトコルは再現しない。キーのハッシュを固定し、token 境界の隣接区間だけを再配分する制約を示す。