一貫性ハッシュ｜分散システム

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：パーティショニング／シャーディング　|　関連：ゴシップ・反エントロピー・故障検出（SWIM）・分散コンピューティングの誤謬（8つの誤謬）

要点（BLUF）

一貫性ハッシュは、ノードとキーを**同じハッシュ空間（リング）**に置き、各キーを「リング上で時計回りに最初に出会うノード」に割り当てる方式。
利点はノード増減時の再配置が最小：hash(key) mod N はノード数変化でほぼ全キーが動くが、一貫性ハッシュは約 1/(N+1) しか動かない。
ノードごとの偏り（負荷ムラ）は仮想ノード（virtual node）——1物理ノードをリング上の多数の点として配置——で平準化する。Dynamo・Cassandra・memcached・CDN で広く使われる。

問題設定 ── ノード追加で全移動は困る

パーティショニング／シャーディングで mod N ハッシュを使うと、ノードを1台足して N→N+1 になった瞬間、ほとんどのキーの割り当て先が変わる。再配置でデータ大移動が起き、キャッシュは総ミス、可用性が落ちる（分散コンピューティングの誤謬（8つの誤謬）の「トポロジは変わらない」が破れる場面）。

アルゴリズム ── リングと時計回り

flowchart LR
    K["キー hash（key）"] -->|"リング上で時計回り"| N["最初に出会うノードが担当"]
    ADD["新ノード追加"] -->|"その区間のキーだけ"| MOVE["新ノードへ移動（他は不動）"]

ハッシュ空間を**円環（0〜2^m−1 を環状）**とみなす。
各ノードを hash(node) でリング上に配置。
キー hash(key) から時計回りに最初のノードが担当。
ノード追加時、影響を受けるのは追加点とその直前ノードの間のキーだけ。他は不動。

仮想ノード：物理ノード1台を hash(node#0), hash(node#1), … と多数の点で配置。これで各物理ノードの担当区間が細かく分散し、負荷が平準化し、ノード故障時の引き継ぎも複数ノードに分散される。

具体例 ── 移動キー数を実測（実機）

ラボ 06-04_consistent_hashing.py。1万キーを5ノードに配置し、6ノードへ1台追加したときの移動キー数を、素朴な mod-N と一貫性ハッシュで比較：

== ノード追加時に再配置されるキーの割合 (キー総数 10000) ==

素朴な mod-N (5->6):
  移動したキー: 8361 / 10000 = 83.6%
  -> ほぼ全キーが再配置される(剰余が総入れ替え)

一貫性ハッシュ (5->6, 仮想ノード100):
  移動したキー: 1476 / 10000 = 14.8%
  -> 理論値 1/(N+1)=1/6=16.7% 近傍。追加ノードの担当ぶんだけ動く

mod-N は83.6%（ほぼ全移動）。一貫性ハッシュは14.8%——理論値 1/(N+1)=1/6=約16.7% の近傍に収まり、移動するのは新ノードが引き受ける区間のキーだけ。スケール変更の衝撃が桁違いに小さいことが定量的に確認できます。

正しさ/性質の観点

再配置の局所性：ノード追加/削除で動くキーは期待値 K/N（K=総キー数）程度。mod N の全移動と対照的。
負荷の均等性：仮想ノードを V 個にすると、担当区間のばらつきが減り、負荷の標準偏差が下がる（V を増やすほど均等、ただしメタデータ増）。
故障時の引き継ぎ分散：仮想ノードにより、1物理ノードの故障分が複数ノードに分散して引き継がれる（1台に集中しない）。

他手法との比較

方式	ノード追加時の移動	負荷均等	レンジ検索
mod N ハッシュ	ほぼ全部（83.6%実測）	良	不可
一貫性ハッシュ	約 1/(N+1)（14.8%実測）	仮想ノードで良	不可
固定数パーティション	パーティション単位で移動	設計依存	範囲分割なら可

なぜ分散だと難しいか（直観）

分散ハッシュテーブルの肝は「ノード集合が動的に変わる」こと。mod N は N に全キーが依存するので N が変わると総崩れ。一貫性ハッシュは「キーの居場所をN に依存させず、リング上の相対位置で決める」ことで、変化の影響を局所に閉じ込めます。変化に強い割り当てという発想が、動的クラスタの前提に噛み合っています。

⚠️ よくある誤解・落とし穴

「仮想ノードは飾り」→ 無いと担当区間が偏り、負荷ムラと故障時の引き継ぎ集中が起きる。実用ではほぼ必須。
「一貫性ハッシュなら一貫性（consistency）が上がる」→ 名前が紛らわしいが、CAPの一貫性とは無関係。「割り当てが安定（consistent）」の意味。
「移動ゼロにできる」→ ゼロは無理。追加ノードが担当ぶんを引き受ける以上、その区間は必ず動く。最小化が目的。
「レンジ検索もできる」→ ハッシュ系なので連続キーは散る。範囲検索が要るなら範囲分割（パーティショニング／シャーディング）。

対応ラボ

distributed-systems-study/labs/06-04_consistent_hashing.py（5→6ノードで mod-N が83.6%移動、一貫性ハッシュが14.8%移動を確認済み）。