IT 技書の森

コンシステントハッシュ

ノードの追加・削除時にデータの再配置を最小限に抑える分散ハッシュアルゴリズム

分散システムアルゴリズム

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

コンシステントハッシュ (Consistent Hashing) は、ノードの追加・削除時にデータの再配置を最小限に抑える分散ハッシュアルゴリズムである。1997 年に David Karger らが提案した。DynamoDB、Cassandra、Redis Cluster、CDN のルーティングで使われている。

通常のハッシュの問題

ノード = hash(key) % N

N=3 の場合: hash("user:1") % 3 = 1 → ノード 1
N=4 に増設: hash("user:1") % 4 = 2 → ノード 2 (移動!)

ノード数 N が変わると、ほぼ全てのキーの割り当て先が変わる。キャッシュサーバーの増設でキャッシュヒット率が一時的に 0% になる。

コンシステントハッシュの仕組み

        ノード A (0°)
       /            \
  ノード D (270°)    ノード B (90°)
       \            /
        ノード C (180°)

キー "user:1" → ハッシュ値 45° → 時計回りで最初のノード B に割り当て
  1. ノードとキーを同じハッシュリング (0〜2^32) 上に配置
  2. キーは時計回りで最初に見つかるノードに割り当て
  3. ノード追加時: 新ノードの直前のキーだけが移動 (全体の 1/N)
  4. ノード削除時: 削除ノードのキーが次のノードに移動

仮想ノード (Virtual Nodes)

物理ノードが少ないとデータが偏る。各物理ノードに複数の仮想ノードを割り当てて均等に分散する。

物理ノード A → 仮想ノード A-1 (30°), A-2 (120°), A-3 (250°)
物理ノード B → 仮想ノード B-1 (60°), B-2 (180°), B-3 (300°)

DynamoDB は各パーティションに複数の仮想ノードを割り当て、データを均等に分散している。

DynamoDB のパーティショニング

DynamoDB はコンシステントハッシュでパーティションキーのハッシュ値に基づいてデータを分散する。

パーティションキー "user:123" → ハッシュ → パーティション B
パーティションキー "user:456" → ハッシュ → パーティション A

パーティションキーの設計が偏ると (例: 日付をキーにする)、特定パーティションにアクセスが集中する「ホットパーティション」問題が発生する。

他の分散システムでの利用

システム 用途
DynamoDB パーティションキーによるデータ分散
ElastiCache (Redis Cluster) キャッシュデータのシャーディング
CloudFront オリジンサーバーへのルーティング
Cassandra データのレプリケーション先の決定

現場での応用を知るには関連書籍も役立つ。

関連用語