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

コンシステントハッシュ法（Consistent Hashing）は、分散キャッシュや分散データベースにおいて、ノードの追加・削除時にデータの再配置を最小限に抑えながら、負荷を均等に分散する技術です。本記事では、従来のハッシュ法の課題から、コンシステントハッシュの仕組み、仮想ノードの役割、実装例までを体系的に解説します。

概要

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

1997年にDavid Karger らがMIT で発表したアルゴリズムで、分散システムにおけるデータ配置問題を解決します。従来のハッシュ法（hash(key) % N）では、ノード数Nが変わるとすべてのキーが再配置されますが、コンシステントハッシュでは平均で 1/N のキーだけが移動します。

flowchart TB
    subgraph Traditional["従来のハッシュ法"]
        T1["hash(key) % 3<br/>→ Node 0/1/2"]
        T2["ノード追加<br/>hash(key) % 4"]
        T3["<strong>全キーが再配置</strong>"]
        T1 --> T2 --> T3
    end

    subgraph Consistent["コンシステントハッシュ"]
        C1["ハッシュリング上に配置"]
        C2["ノード追加"]
        C3["<strong>隣接キーのみ移動</strong>"]
        C1 --> C2 --> C3
    end

主な利用場面

• 分散キャッシュ（memcached クラスタ、Redis Cluster）
• 分散データベース（Amazon DynamoDB、Apache Cassandra）
• CDN のコンテンツ配信
• 負荷分散装置（LB）のセッションアフィニティ

原則・定義

ハッシュリング（Hash Ring）

コンシステントハッシュでは、ハッシュ値を円環（リング）上の点として扱います。ハッシュ関数の出力空間（例: 0 〜 2^32 - 1）をリング状に繋げ、ノードとキーの両方をリング上に配置します。

graph TB
    subgraph Ring["ハッシュリング（0 ~ 2^32-1）"]
        direction LR
        N1["Node A<br/>hash=1000"]
        N2["Node B<br/>hash=5000"]
        N3["Node C<br/>hash=9000"]
        K1["Key X<br/>hash=3000"]
        K2["Key Y<br/>hash=7000"]
    end

    K1 -.時計回りで最初のノード.-> N2
    K2 -.時計回りで最初のノード.-> N3

配置ルール

1. ノードとキーそれぞれに同じハッシュ関数を適用
2. キーは時計回りで最初に見つかるノードに配置
3. ノード削除時、そのノードのキーは次のノードへ移動
4. ノード追加時、新ノードと次ノードの間のキーが新ノードへ移動

仮想ノード（Virtual Node / VNode）

1台の物理ノードを、複数のハッシュ値（例: hash(node_id + replica_index)）でリング上に配置します。これにより、キーがより均等に分散されます。

// 仮想ノード生成例
function generateVirtualNodes(nodeId: string, numVNodes: number): number[] {
  const vnodes: number[] = [];
  for (let i = 0; i < numVNodes; i++) {
    vnodes.push(hashFunction(`${nodeId}-vnode-${i}`));
  }
  return vnodes;
}

構成要素

主要コンポーネント

リバランスの最小化

ノード追加・削除時の影響範囲:

flowchart LR
    A["ノードA"] -->|キーの一部| B["ノードB"]
    B -->|キーの一部| C["ノードC"]
    C -->|キーの一部| A

    D["新ノードD<br/>追加"] -.一部のキーを引き継ぐ.-> B
    D -.一部のキーを引き継ぐ.-> C

    style D fill:#efe

従来のハッシュ法では全キーが再配置されますが、コンシステントハッシュでは新ノードの隣接範囲のキーだけが移動します。

実装例

1. 基本的なコンシステントハッシュ（TypeScript）

import crypto from "crypto";

class ConsistentHash {
  private ring: Map<number, string> = new Map(); // hash -> nodeId
  private sortedHashes: number[] = [];
  private virtualNodeCount: number;

  constructor(virtualNodeCount = 150) {
    this.virtualNodeCount = virtualNodeCount;
  }

  private hash(key: string): number {
    return parseInt(crypto.createHash("md5").update(key).digest("hex").substring(0, 8), 16);
  }

  addNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodeCount; i++) {
      const vnode = `${nodeId}-vnode-${i}`;
      const hashValue = this.hash(vnode);
      this.ring.set(hashValue, nodeId);
      this.sortedHashes.push(hashValue);
    }
    this.sortedHashes.sort((a, b) => a - b);
  }

  removeNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodeCount; i++) {
      const vnode = `${nodeId}-vnode-${i}`;
      const hashValue = this.hash(vnode);
      this.ring.delete(hashValue);
      const index = this.sortedHashes.indexOf(hashValue);
      if (index > -1) this.sortedHashes.splice(index, 1);
    }
  }

  getNode(key: string): string | undefined {
    if (this.sortedHashes.length === 0) return undefined;

    const hashValue = this.hash(key);
    // 二分探索で最初の大きいハッシュ値を探す
    let left = 0;
    let right = this.sortedHashes.length - 1;

    // 最大値より大きければ最初のノードに戻る
    if (hashValue > this.sortedHashes[right]) {
      return this.ring.get(this.sortedHashes[0]);
    }

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.sortedHashes[mid] < hashValue) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return this.ring.get(this.sortedHashes[left]);
  }

  // 統計情報
  getDistribution(keys: string[]): Record<string, number> {
    const dist: Record<string, number> = {};
    for (const key of keys) {
      const node = this.getNode(key);
      if (node) {
        dist[node] = (dist[node] ?? 0) + 1;
      }
    }
    return dist;
  }
}

// 使用例
const ch = new ConsistentHash(200);
ch.addNode("server-1");
ch.addNode("server-2");
ch.addNode("server-3");

console.log(ch.getNode("user:12345")); // → server-2
console.log(ch.getNode("session:abc")); // → server-1

// ノード追加しても大半のキーは変わらない
ch.addNode("server-4");
console.log(ch.getNode("user:12345")); // → 変わる可能性は 1/4

2. レプリケーション対応版

class ReplicatedConsistentHash extends ConsistentHash {
  getNodes(key: string, replicaCount: number): string[] {
    if (this.sortedHashes.length === 0) return [];

    const hashValue = this.hash(key);
    const nodes = new Set<string>();
    let index = this.sortedHashes.findIndex((h) => h >= hashValue);
    if (index === -1) index = 0;

    // リング上で時計回りに replicaCount 個の異なる物理ノードを取得
    let attempts = 0;
    while (nodes.size < replicaCount && attempts < this.sortedHashes.length) {
      const nodeId = this.ring.get(this.sortedHashes[index]);
      if (nodeId) nodes.add(nodeId);
      index = (index + 1) % this.sortedHashes.length;
      attempts++;
    }

    return Array.from(nodes);
  }
}

// Cassandra 風のレプリカ配置
const rch = new ReplicatedConsistentHash(200);
rch.addNode("node-A");
rch.addNode("node-B");
rch.addNode("node-C");

const replicas = rch.getNodes("partition-key-123", 3);
console.log(`Replicas: ${replicas}`); // → ["node-A", "node-C", "node-B"]

3. Python 実装例（Jump Consistent Hash）

Google が提案した Jump Consistent Hash は仮想ノード不要で高速です。

def jump_consistent_hash(key: int, num_buckets: int) -> int:
    """
    O(log num_buckets) で決定的にバケットを決定する。
    ノード数の変更時も最小限の移動で済む。
    """
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = ((key * 2862933555777941757) + 1) & 0xFFFFFFFFFFFFFFFF
        j = int((b + 1) * (float(1 << 31) / float((key >> 33) + 1)))
    return b

# 使用例
print(jump_consistent_hash(hash("user:12345"), 10))  # → 3
print(jump_consistent_hash(hash("session:abc"), 10))  # → 7

メリット・デメリット

メリット

1. リバランスの最小化: ノード増減時に 1/N のキーのみ移動
2. スケーラビリティ: ノード数に対して O(log N) の検索効率
3. 耐障害性: ノード障害時、そのノードのキーだけ再配置
4. 柔軟性: 異なる性能のノードに重み付け可能（仮想ノード数を調整）

デメリット

1. 完全な均等分散ではない: 仮想ノード数が少ないと偏る
2. 複雑性: 従来の hash % N より実装が複雑
3. メモリオーバーヘッド: 仮想ノード情報を保持する必要
4. ホットスポット: 特定キーへのアクセス集中は解決しない

ユースケース

1. 分散キャッシュ（memcached クラスタ）

memcached のクラスタリングでは、クライアント側で Consistent Hashing を実装します。サーバー追加時もキャッシュミス率を抑えられます。

# libmemcached の設定例
memcached --server=server1:11211 --server=server2:11211 --hash=consistent

2. Amazon DynamoDB

DynamoDB はパーティションキーを Consistent Hashing で物理ストレージノードに配置します。仮想ノードにより、ストレージ追加時の影響を最小化しています。

3. Apache Cassandra

Cassandra は各ノードにトークン範囲を割り当て、データを Consistent Hashing で配置します。num_tokens=256 がデフォルトで、これが仮想ノードに相当します。

4. CDN のオリジン選択

地理的に分散した複数のオリジンサーバーから、URL のハッシュ値で決定的にオリジンを選ぶことで、キャッシュヒット率を向上させます。

落とし穴

1. 仮想ノード数の不足

仮想ノード数が少ないと、負荷の偏りが発生します。特にノード数が少ない場合（3台以下）は仮想ノード数を増やす必要があります。

2. ハッシュ関数の選択

暗号学的ハッシュ関数（SHA-256）は計算コストが高いため、高速な MurmurHash3 や xxHash が推奨されます。

3. ノード障害時のカスケード

ノード障害時、そのキーが次のノードに集中します。次のノードが過負荷で障害を起こすと連鎖的に障害が広がる可能性があります。レプリケーションと組み合わせる必要があります。

4. データ偏り（Skewed Data）

ハッシュは均等でも、元データが偏っている場合（特定ユーザーへのアクセス集中等）は、アプリケーション層でのシャーディング戦略が必要です。

5. 同期的なリバランス

ノード追加時、データ移動が完了するまで一貫性が保てない場合があります。Cassandra は Streaming Protocol でバックグラウンド転送を行います。

比較表

ハッシュ法の比較

主要実装の仮想ノード数

ベストプラクティス

1. 仮想ノード数は 100〜256: 多すぎるとメモリ消費、少ないと偏る
2. 高速ハッシュ関数: MurmurHash3, xxHash, CityHash を推奨
3. レプリケーション併用: N=3（3台のノードにコピー）が一般的
4. 段階的ノード追加: 一度に大量追加すると負荷が集中
5. モニタリング: ノードごとのキー分布を監視
6. 重み付け: 高性能ノードには仮想ノード数を増やす
7. データ移行の非同期化: バックグラウンドで徐々に転送
8. Jump Consistent Hash の検討: ノード数が固定なら実装が簡単

まとめ

コンシステントハッシュ法は、分散システムにおけるデータ配置の標準技術です。従来のハッシュ法と比べて、ノードの増減時に再配置が必要なキーを1/N に抑えることができます。

• ハッシュリング: ノードとキーを円環上に配置し、時計回りで検索
• 仮想ノード: 負荷の均等化に不可欠（100〜256個が目安）
• リバランス最小化: 平均 1/N のキーだけが移動
• 実績: DynamoDB、Cassandra、memcached など多数の実装例
• 代替手法: Jump Consistent Hash はシンプルで高速

分散システムを設計する際、コンシステントハッシュの理解は必須です。

応用トピック

Rendezvous Hashing（HRW: Highest Random Weight）

各キーに対して全ノードでスコアを計算し、最高スコアのノードを選ぶ方式です。仮想ノードが不要で完全に均等ですが、O(N) の計算コストがかかります。

function rendezvousHash(key: string, nodes: string[]): string {
  let maxScore = -1;
  let selectedNode = nodes[0];

  for (const node of nodes) {
    const score = hash(`${key}:${node}`);
    if (score > maxScore) {
      maxScore = score;
      selectedNode = node;
    }
  }
  return selectedNode;
}

Bounded Load Consistent Hashing

Google が提案した拡張で、各ノードに負荷上限を設け、超過した場合は次のノードにフォールバックします。ホットスポット対策に有効です。

Multi-Probe Consistent Hashing

キーのハッシュ値に対して複数の探索点を設け、最も空いているノードを選ぶ方式です。負荷の均等化が向上します。

参考リソース

• Consistent Hashing and Random Trees (Original Paper) - Karger et al. 1997
• A Fast, Minimal Memory, Consistent Hash Algorithm - Jump Hash
• Cassandra Documentation - Virtual Nodes
• Amazon DynamoDB - Partitions and Data Distribution
• Designing Data-Intensive Applications - Chapter 6

関連記事

• データベースシャーディング - 水平分割の設計パターンとコンシステントハッシュの活用
• 分散システムにおけるレプリケーション - データ複製戦略と整合性モデル