---
title: 一貫性ハッシュ
url: https://doc.liz6.com/ja/distributed-systems/04-partitioning-and-routing/01-consistent-hashing
locale: ja
area: distributed-systems
tags:
- distributed-systems
- partitioning-and-routing
date: 2026-06-30
modified: 2026-07-16
description: ノード数が変化した際、できるだけ少ないデータ移行で済ませるには？一貫性ハッシュはノードとデータを同じリング上にマッピングし、各キーは時計回りに最も近いノードを探す——ノードの増減は隣接する区間にのみ影響する。バーチャルノードは負荷をさらに均等にするが、ルーティングテーブルが大きくなるという代償がある。
---

# 一貫性ハッシュ

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

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

通常の `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` を用いた一貫性のある負荷分散)。

## 比較

| | Hash Ring + Vnodes | Jump Hash | Rendezvous |
|---|---|---|---|
| メモリ | O(V * N) | O(1) | ノードごとに O(1)、計算に O(N) |
| 検索 | O(log(V*N)) + ring 上のバイナリサーチ | O(log N) | キーごとに O(N) |
| 移行 | ~1/N のキー | ~1/N のキー | ~1/N のキー |
| 重み付け | 可能 (vnode 数で調整) | 不可 | ネイティブ対応 |
| 適用 | N があまり変わらない場合、任意の node_id が必要 | N が頻繁に変化する場合、メモリが限られている場合 | N が小さい場合 (< 1000) |

## 参考文献

- **論文**: "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*