コンシステントハッシュの設計

概要

この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。

本記事では、分散システムにおけるデータの分散配置に欠かせないコンシステントハッシュの設計について解説します。

コンシステントハッシュは、サーバーの追加・削除に伴うデータの再配置を最小限に抑えるための手法であり、分散キャッシュや分散データベースなど多くのシステムで採用されている。

ハッシュとリハッシュ問題

従来のハッシュ方式

N台のサーバーにリクエストやデータを均等に分散する最も単純な方法は、ハッシュ関数とモジュロ（剰余）演算を組み合わせる方法である。

サーバーインデックス = hash(key) % N

例えば、4台のサーバー（s0〜s3）にキーを分散する場合を考える。

キー	hash(key)	hash(key) % 4	割り当て先
key0	100	0	s0
key1	101	1	s1
key2	102	2	s2
key3	103	3	s3
key4	104	0	s0
key5	105	1	s1
key6	106	2	s2
key7	107	3	s3

この方法はサーバー数が固定されている場合はうまく動作する。

リハッシュ問題

しかし、サーバーの追加や削除が発生すると問題が生じる。例えば、サーバーs1が障害でダウンし、サーバー数が4から3に減った場合を考える。

キー	hash(key)	hash(key) % 3	割り当て先（変更後）	割り当て先（変更前）
key0	100	1	s1	s0
key1	101	2	s2	s1
key2	102	0	s0	s2
key3	103	1	s1	s3
key4	104	2	s2	s0
key5	105	0	s0	s1
key6	106	1	s1	s2
key7	107	2	s2	s3

サーバー数Nが変わると hash(key) % N の結果が大きく変わるため、ほとんどのキーが異なるサーバーに再配置される。これがキャッシュサーバーの場合、大量のキャッシュミスが同時に発生し、障害の連鎖（キャッシュストーム）を引き起こす可能性がある。

コンシステントハッシュは、このリハッシュ問題を解決するために設計された手法である。

コンシステントハッシュとは

コンシステントハッシュ（consistent hashing）とは、ハッシュテーブルのサイズが変更された場合に、平均で K/N 個のキーのみが再配置される特殊なハッシュ手法である（K: キーの数、N: サーバーの数）。従来の方式ではほぼすべてのキーが再配置されるのに対し、影響範囲を最小限に抑えることができる。

ハッシュリング

コンシステントハッシュの基本的な考え方は、ハッシュ空間を**リング（環状）**として扱うことである。

例えば、4台のサーバー（s0〜s3）と4つのキー（k0〜k3）を同じリング上に配置すると、次のようになる。

円（青）がサーバー、角丸（黄）がキー: サーバーもキーも同じハッシュ関数で同一リング上に配置される
左→右がリングを時計回りに辿った並び順: 右端の k3 まで進むと、点線のように一周して先頭の s0（0 / 2^32 の境界）へ戻る
各キーは時計回りで最初に出会うサーバーが担当: 例えば k0・k3 は s0、k1 は s1、k2 は s2 に割り当てられる

仕組みは以下の通りである。

ハッシュ空間をリングにする: ハッシュ関数の出力範囲（例: 0〜2^32-1）を円環上に並べる。最大値の次が最小値に繋がるイメージである
サーバーとキーを同じハッシュ関数でリング上に配置する: サーバー（IPアドレスやホスト名）もデータのキーも、同一の均一分散ハッシュ関数でリング上にマッピングする。同じハッシュ空間上に両者を配置することで、次のステップの割り当てが成立する
キーの割り当て先を決定する: キーの位置から時計回りにリングを辿り、最初に見つかるサーバーにそのキーを割り当てる

ポイント: 位置の計算にサーバー数 N が入らない

従来方式は hash(key) % N のようにサーバー数 N を法として割り当て先を決めるため、N が変わるとほぼ全キーの割り当てが変わる。一方コンシステントハッシュでは、キーの位置は hash(key) の値そのもの（固定サイズのリング上の点）で決まり、N を計算に含めない。そのため N が変化しても各キーの位置は動かず、影響が局所化される。

なお「リングが固定サイズ」とは 2^32 などの定数を法とする空間という意味であり、剰余演算そのものが消えるわけではない。従来方式との本質的な違いは、法がサーバー数 N ではなく固定値である点にある。

キーの割り当て例

上図のリング上の配置を直線に展開すると、次のようになる（右端の s0 に戻る が、リングを一周して先頭へ戻ることを表す）。

（時計回り →）

  s0 ─── k1 ─── s1 ─── k2 ─── s2 ─── s3 ─── k0 ─── k3 ───→ s0 に戻る

各キーは、自身の位置から時計回りに進んで最初に見つかるサーバーに割り当てられる。

キー	時計回りで最初のサーバー
k0	s0
k1	s1
k2	s2
k3	s0

サーバーの追加と削除

コンシステントハッシュの最大の利点は、サーバーの追加・削除時に影響を受けるキーが局所的であることである。

サーバーの追加

新しいサーバーs4がk1とs1の間に追加された場合、影響を受けるのはs4と反時計回りで隣接するサーバーの間にあるキーのみである。

（時計回り →）

  変更前: s0 ─── k1 ─── s1 ─── k2 ─── s2 ─── s3 ─── k0 ─── k3 ───→ s0 に戻る
                  │
                  ▼ k1の割り当て先が s1 → s4 に変更
  変更後: s0 ─── k1 ─── [s4] ─── s1 ─── k2 ─── s2 ─── s3 ─── k0 ─── k3 ───→ s0 に戻る

k1だけがs1からs4に再割り当てされる。それ以外のキー（k0、k2、k3）は影響を受けない。

サーバーの削除

サーバーs1がダウンした場合も、影響を受けるのはs1に割り当てられていたキーのみである。それらのキーは時計回りで次のサーバーに再割り当てされる。

（時計回り →）

  変更前: s0 ─── k1 ─── s1 ─── k2 ─── s2 ─── s3 ─── k0 ─── k3 ───→ s0 に戻る
                         │
                         ▼ s1 が削除され、k1の割り当て先が s1 → s2 に変更
  変更後: s0 ─── k1 ─── k2 ─── s2 ─── s3 ─── k0 ─── k3 ───→ s0 に戻る

k1がs1からs2に移動するだけで、他のキーは影響を受けない。

従来方式との比較: 従来のmodulo方式ではサーバー1台の追加・削除でほぼすべてのキーが再配置されるのに対し、コンシステントハッシュでは平均 K/N 個のキーのみが移動する。

基本アプローチの問題点

上述の基本的なコンシステントハッシュには、実用上2つの問題がある。

パーティションサイズの不均一

パーティションとは、リング上で隣接するサーバー間の区間のことであり、その区間に含まれるキーは手前のサーバーが担当する。パーティションサイズが不均一になるケースは主に2つある。

1. サーバーがリング上の不均一な位置にマッピングされた場合

ハッシュ関数の結果次第で、サーバーがリング上に偏って配置されることがある。

（時計回り →）

  s0 ──────────────────────────────── s1 ── s2 ───→ s0 に戻る
  │            s0の担当範囲            │    │
  ◄──────────── 広い ────────────────► ◄狭い►

2. サーバーの追加・削除が発生した場合

サーバーの増減により、リング上の間隔が変化する。

（時計回り →）

  均等時: s0 ──────── s1 ──────── s2 ──────── s3 ───→ s0 に戻る

  s1削除: s0 ───────────────────── s2 ──────── s3 ───→ s0 に戻る
          │    s0の担当範囲（2倍）   │
          ◄──────── 広い ──────────►

いずれの場合も、特定のサーバーに負荷が集中する原因となる。

キーの偏り

パーティションが不均一であるため、特定のサーバーに多くのキーが集中する可能性がある。これにより、一部のサーバーに負荷が偏り、分散の目的が達成できなくなる。

仮想ノード（Virtual Nodes）

仮想ノード（virtual node、vnode）は、基本アプローチの問題点を解決するための手法である。実際のサーバー1台に対して、リング上に複数の仮想的なノードを配置することで、データの分散を均一化する。

仕組み

例えば、サーバーs0とs1の2台構成で、各サーバーに3つの仮想ノードを割り当てる場合を考える。

リング上の配置:

    s0_0  s1_1  s0_2  s1_0  s0_1  s1_2
     │     │     │     │     │     │
     ▼     ▼     ▼     ▼     ▼     ▼
  ───●─────●─────●─────●─────●─────●───→ リング
     └─s0──┘     └─s0──┘     └─s0──┘
           └─s1──┘     └─s1──┘     └─s1─

s0_0、s0_1、s0_2はすべてサーバーs0を指す仮想ノードである。キーがこれらの仮想ノードに割り当てられた場合、実際にはサーバーs0に格納される。

仮想ノードによる均一化

仮想ノードを使うことで、各サーバーの担当範囲がリング上に分散される。

仮想ノード数	分散の均一性
少ない（例: 3個）	偏りが残る可能性がある
多い（例: 100〜200個）	非常に均一に分散される

仮想ノードの数を増やすほどデータ分散は均一になるが、各仮想ノードの情報を保持するためのメモリが増加する。このトレードオフを考慮して、システムの要件に応じた仮想ノード数を選定する必要がある。

ホットスポットの緩和

キーがリング全体へ均等に分散されることは、ホットスポット（特定サーバーへの負荷集中）の緩和にもつながる。アクセスの多い人気キーが複数存在しても、それらが特定のサーバーに固まりにくくなるためである。

ただし、これはあくまで「複数の人気キーが同一サーバーに集中する」ケースの緩和であることに注意する。単一の極端に人気なキーへアクセスが集中するケースでは、そのキーは1台のサーバーにハッシュされるため、コンシステントハッシュだけでは負荷集中を解消できない。この場合はキーの複製やキーの分割など、別の対策を併用する必要がある。

メリットとデメリット

メリット	デメリット
データ分散が均一になる	仮想ノードの情報を保持するためメモリが増加する
サーバーのスペックに応じて仮想ノード数を調整できる（高スペックなサーバーに多くの仮想ノードを割り当て）	仮想ノード数のチューニングが必要である

コンシステントハッシュの活用事例

コンシステントハッシュは多くの分散システムで採用されている。

システム	用途	参考
Amazon Dynamo	データのパーティショニングに仮想ノード付きコンシステントハッシュを使用	Dynamo論文（2007）
Apache Cassandra	クラスター内のデータ分散。Dynamoの設計を継承	公式ドキュメント
Discord	ギルド（サーバー）のノードへのルーティング	公式エンジニアリングブログ
Akamai CDN	コンテンツのキャッシュ分散。コンシステントハッシュはこのユースケースのために考案された	原論文（1997）
NGINX / HAProxy	ロードバランサーのバックエンド振り分けアルゴリズムとして搭載	NGINX公式ドキュメント

まとめ

コンシステントハッシュの設計で押さえるべきポイントを整理する。

リハッシュ問題: 従来のmodulo方式ではサーバー数の変更時にほぼ全キーが再配置される。コンシステントハッシュはこの問題を解決する
ハッシュリング: ハッシュ空間をリング状に扱い、キーを時計回りで最初のサーバーに割り当てる
局所的な影響: サーバーの追加・削除時に再配置されるキーは平均 K/N 個のみであり、影響が局所的である
仮想ノード: 実サーバーに複数の仮想ノードを割り当てることで、データ分散を均一化する。ノード数が多いほど均一だがメモリ消費が増えるトレードオフがある
ホットスポットの緩和: キーがリング上に均等分散されるため、人気キーが特定サーバーに集中しにくくなる（ただし単一の超人気キーへの集中は別途対策が必要）

参考文献

この記事は以下の情報を参考にして執筆しました。

「システム設計の面接試験」（Alex Xu 著 / インプレス）