コンシステントハッシュ法 - 分散キャッシュ・データベースの負荷分散

コンシステントハッシュ法（Consistent Hashing）は、分散キャッシュや分散データベースで、ノードの増減によるキーの移動範囲を抑えるための配置方法です。

この記事では、リング、仮想ノード、再配置、向かない用途の4点に絞って仕組みを説明します。

通常の剰余ハッシュの問題

キーを3台のノードへ振り分けるだけなら、次の式を使えます。

node = hash(key) % 3

しかし、ノードを1台追加すると式の末尾が % 4 に変わります。多くのキーで計算結果が変わるため、キャッシュミスや大量のデータ移動が発生します。

flowchart LR
  A["hash(key) % 3"] --> B["3台へ配置"]
  C["ノードを追加"] --> D["hash(key) % 4"]
  D --> E["多くのキーの配置先が変化"]

ノード数がほぼ変わらない小規模システムなら、この単純さは利点です。ノードが頻繁に増減する場合に、コンシステントハッシュを検討します。

ハッシュリングの仕組み

コンシステントハッシュでは、ハッシュ値の範囲を円環として扱います。ノードとキーを同じリング上に置き、キーの位置から時計回りに最初に見つかるノードを担当にします。

たとえば、キーuser:42のハッシュ値が35で、その先にある最初のノードがNode B: 50なら、担当はNode Bです。

0 ── Node A:20 ── key:35 ── Node B:50 ── Node C:80 ── 100
                           └─ 時計回りのNode Bへ

新しいノードをリングへ追加したとき、担当が変わるのは原則としてそのノードが受け持つ区間です。剰余ハッシュのように、ノード数の変更だけで広範囲の配置が変わることを避けられます。

ただし、これは「移動が無料」という意味ではありません。実際のシステムでは、データ転送、キャッシュの温め直し、レプリカの調整などが必要です。

ノード追加時に何が移動するか

次のようなリングを考えます。

Node A: 20 → Node B: 50 → Node C: 80 → 先頭へ戻る

この間の35へNode Dを追加すると、以前Node Bが担当していた区間の一部だけをNode Dが引き受けます。

変更前: (20, 50] → Node B
変更後: (20, 35] → Node D
        (35, 50] → Node B

削除時は逆で、削除したノードの担当区間を時計回りの次のノードが引き受けます。実装によってリングの向きや区間の端の扱いは異なりますが、隣接区間だけが変わるという考え方は同じです。

キャッシュなら、新担当がアクセスを受けた時点で値を取得する遅延移行も可能です。永続データでは、旧担当から新担当へコピーし、検証後に所有権を切り替える手順が必要です。移行中に両方へ書くのか、ルーティング情報の版をどうそろえるのかまで設計します。

仮想ノードで偏りを抑える

物理ノードをリング上に1点ずつ置くと、ノード間の区間が偶然広くなり、負荷が偏ることがあります。

そこで、1台の物理ノードを複数の**仮想ノード（virtual node）**としてリング上に配置します。

Physical A → A-1, A-2, A-3
Physical B → B-1, B-2, B-3
Physical C → C-1, C-2, C-3

仮想ノードには次の役割があります。

• 各物理ノードの担当区間を分散し、配置の偏りを小さくする
• 高性能なノードへ多めの仮想ノードを割り当て、重みを表現する
• ノード追加・削除時の移動先を複数ノードへ分散する

仮想ノード数に万能な正解はありません。増やすほど分布は滑らかになりやすい一方、リング情報、接続、移動計画、監視の負担も増えます。キー分布、ノード性能、障害復旧時間を測って決めます。

最小の割り当て処理

概念上の処理は、ソート済みのトークンからキー以上の最初の値を探すだけです。末尾を超えたらリングの先頭へ戻ります。

type Point = {
  token: number;
  nodeId: string;
};

function findOwner(points: Point[], keyToken: number): string {
  let low = 0;
  let high = points.length;

  while (low < high) {
    const middle = Math.floor((low + high) / 2);
    if (points[middle].token < keyToken) {
      low = middle + 1;
    } else {
      high = middle;
    }
  }

  return points[low % points.length].nodeId;
}

この例は仕組みを示すためのものです。本番では、ハッシュ関数、衝突、空リング、ノード状態、同時更新、永続化を別途設計します。

レプリケーションは別の仕組み

コンシステントハッシュが決めるのは、主に「どのノードがキーを担当するか」です。データを何個複製するか、どのノードへ複製するか、整合性をどう保つかは別の設計です。

たとえば、リング上で担当ノードから時計回りに異なる物理ノードを選び、複数のレプリカを置く方式があります。ただし、同じラックや障害領域へ複製が偏らないようにするには、トポロジーを考慮した選択が必要です。

使わないほうがよい場合

コンシステントハッシュは、すべての分散配置に適しているわけではありません。

人気キーの偏りには、複製、ローカルキャッシュ、リクエスト分散などが必要です。順序を保った分割には、レンジパーティショニングのほうが適する場合があります。

障害と計画変更を分ける

ノードへ一時的に到達できないたび、すぐリングから削除すると、短い通信障害でも大量の再配置が始まります。復旧すると再び元へ戻すことになり、障害中の負荷をさらに増やしかねません。

運用では、少なくとも次を区別します。

• 一時的な障害: レプリカや代替ノードへ読み書きを逃がし、復旧を待つ
• 計画的な追加・削除: 帯域と負荷を監視しながら段階的にデータを移す
• 恒久的な故障: 状態を確定してから所有権とレプリカを再構成する

複数のクライアントがリング情報を持つ方式では、更新の瞬間に新旧の配置が混在します。リングの世代番号、中央のメタデータ管理、再試行先などを決め、古い情報による誤配送を回復できるようにします。

分布を監視する

ハッシュ上の区間が均等でも、データサイズやアクセス頻度まで均等とは限りません。ノードごとに、キー数だけでなく、保存バイト数、リクエスト数、レイテンシ、CPU、ネットワーク転送量を監視します。

平均値だけを見ると、1つのホットキーや一部の大きな値を見逃します。上位キーの負荷、仮想ノード単位の担当量、再配置中の転送速度も確認します。偏りが見つかった場合は、仮想ノード数を増やす前に、原因がハッシュ区間、キーサイズ、アクセス集中、ノード性能差のどれかを切り分けます。

リングを変更すると再びデータ移動が起きるため、監視結果を見ながら一度に動かす量を制限します。

設計時の確認項目

導入前に、次を確認します。

1. ノード増減時に、どれだけのデータ移動を許容できるか
2. キーとアクセス頻度が偏っていないか
3. ノードごとの容量差をどう重みに反映するか
4. 障害中の担当変更と復旧後の再配置をどう行うか
5. レプリカを異なる障害領域へ置けるか
6. リング更新中に古い配置情報を持つクライアントをどう扱うか

コンシステントハッシュの価値は、リングそのものではなく、構成変更の影響範囲を予測しやすくすることにあります。

まとめ

• 剰余ハッシュは、ノード数が変わると多くのキーの配置先が変わる
• コンシステントハッシュは、キーとノードを同じリング上に置く
• ノード追加時の移動を、そのノードが受け持つ区間へ抑えられる
• 仮想ノードは分布と重み付けを改善するが、個数は実測で決める
• レプリケーション、整合性、ホットキー対策は別途必要
• 範囲検索や小規模な固定構成では、別方式のほうが単純な場合がある

参考リソース

• Consistent Hashing and Random Trees (Original Paper) - Karger et al. 1997
• A Fast, Minimal Memory, Consistent Hash Algorithm - Jump Hash
• Apache Cassandra - Dynamo

関連記事

• データベースシャーディング - 水平分割の設計方法
• 分散システムにおけるレプリケーション - 複製と整合性の考え方

×

PR

×

PR