一貫性ハッシュ

ノード数が変化した際、できるだけ少ないデータ移行で済ませるには？一貫性ハッシュはノードとデータを同じリング上にマッピングし、各キーは時計回りに最も近いノードを探す——ノードの増減は隣接する区間にのみ影響する。バーチャルノードは負荷をさらに均等にするが、ルーティングテーブルが大きくなるという代償がある。

問題: ノード数変更時のデータ移行の最小化

通常の hash(key) % N：N 個のノード → ノードの増減 → すべてのキーのマッピングが変更 → 全データの移行が必要。一貫性ハッシュはこれを解決し、ノードの増減時に K/N のキーのみ移行すればよい⁠（K はキーの総数）。

Hash Ring + バーチャルノード (Chord/Dynamo 方式)

アルゴリズム

1. 各ノードに対して: hash(node_id) を計算 → ring [0, 2^32) 上にマッピング
2. 各キーに対して: hash(key) を計算 → ring 上にマッピング
3. キーの割り当て: キーの位置から時計回りに進み、最初に遭遇したノード

ノードの増減:
  - ノード追加: 新しいノードと、その反時計回りの直前のノードの間のキーのみを新しいノードに移行
  - ノード削除: そのノードのキーを時計回りの次のノードに移行

バーチャルノード (Vnodes)

物理ノード数が少ない場合（例: 5 個）、ring 上のノード分布が偏り → データの偏り発生。バーチャルノード: 各物理ノードに対して V 個のバーチャルノード（通常 100〜200 個）を ring 上にランダムに配置。

• 各物理ノードの Vnodes 数が多いほど → 負荷が均等化
• Vnode 数は物理ノード数と無関係 → 物理ノード追加時は、一部の vnodes のみを新しい物理ノードに再割り当てするだけでよい

Dynamo/Cassandra: 各物理ノードは ring 上に 256 個の vnodes を持つ。

Jump Hash (Google 方式)

ring 構造を保持する必要がなく、O(log N) でキーがどのバケットに属するかを計算:

int jump_consistent_hash(uint64_t key, int num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        double r = random_next(key, j);  // 決定論的 PRNG
        j = floor((b + 1) / r);
    }
    return b;
}

性質: 各バケットに等確率 (1/num_buckets) で割り当てられる。バケットの増減時には 1/num_buckets のキーのみ移行が必要。ring データ構造は不要。

制限: バケットは連続した番号 (0..N-1) でなければならない。任意の node_id はサポートしない。重み付けはサポートしない（すべてのバケットの重みは同一）。

Google はこれを CDN キャッシュシャーディングやストレージバケットの割り当てに使用している。

Rendezvous Hash (HRW: Highest Random Weight)

各キーに対して各ノードのスコアを計算し、最高スコアのノードを選択:

各ノード N に対して:
    score = hash(key, node_id)
キーの割り当て: 最高スコアのノード

ノードの増減: スコアが最高となるノードが変更されたキーのみ影響を受ける。Jump Hash との重要な違い: ノード数が変化したとしても、⁠元々そのノードに割り当てられていたキーのみが影響を受ける⁠——他のキーの勝者は変わらない。

特性: 重み付けをネイティブにサポート (score = hash(key, node_id) / weight)。グローバル状態を一切必要としない。

応用: Apache Ignite, HAProxy (balance url_param を用いた一貫性のある負荷分散)。

比較

参考文献

• 論文⁠: "Consistent Hashing and Random Trees" (Karger et al, 1997)
• 論文⁠: "A Fast, Minimal Memory, Consistent Hash Algorithm" (Lamping & Veach, 2014 — jump hash)
• Dynamo: "Dynamo: Amazon's Highly Available Key-value Store" (2007, section 4.5)

キーワード: 一貫性ハッシュ, hash ring, バーチャルノード, vnodes, jump hash, rendezvous hash, highest random weight