TypeScriptでConsistent Hashingを実装する：仮想ノードと再配置量をテストする

参考資料：Dynamo: Amazon's Highly Available Key-value Store（Consistent Hashingの利用例）
https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/dynamo.pdf

この記事の結論

Consistent Hashing（コンシステントハッシュ）は、ノードの追加・削除時にキーの再配置を最小限にするためのアルゴリズムです。実装の要点は次の3つです。

• ハッシュ値を円環（ring）上の点として扱い、キーから時計回りに最初のノードを選ぶ
• 1台の物理ノードに複数の仮想ノードを割り当て、分布の偏りを抑える
• ハッシュ衝突、空のring、ノード削除後のwrap-aroundをテストで固定する

ノード数を N から N + 1 に変えるたびに全キーを再配置する単純な hash(key) % N と違い、理想的には追加・削除したノードの近傍だけが移動します。キャッシュ、シャードルーティング、分散キューの担当決定などで、面接でも説明しやすい設計です。

1. データ構造と不変条件

ring は Map<number, string> として持ち、キーは uint32 のハッシュ値、値は仮想ノードIDです。Map の反復順序に依存しないよう、参照時は必ずソート済みの配列を使います。

この記事の実装では、次の不変条件を守ります。

1. ringPoints は常に昇順である
2. ring の各ハッシュ値は1つの仮想ノードに対応する
3. 物理ノードの削除時、そのノードが所有する仮想ノードだけを消す
4. ring の末尾を越えた探索は先頭へwrap-aroundする

2. TypeScript実装

ハッシュ関数には、依存パッケージなしで再現できるFNV-1a（32-bit）を使います。実際の本番システムでは、ハッシュ関数の変更が全キーの移動につながるため、アルゴリズムとseedを固定してバージョン管理してください。

type PhysicalNode = string;

const encoder = new TextEncoder();

function fnv1a(input: string): number {
  let hash = 0x811c9dc5;
  for (const byte of encoder.encode(input)) {
    hash ^= byte;
    hash = Math.imul(hash, 0x01000193) >>> 0;
  }
  return hash;
}

export class ConsistentHashRing {
  private readonly ring = new Map<number, string>();
  private readonly pointsByNode = new Map<PhysicalNode, number[]>();
  private ringPoints: number[] = [];

  constructor(private readonly replicas = 128) {
    if (!Number.isInteger(replicas) || replicas < 1) {
      throw new RangeError("replicas must be a positive integer");
    }
  }

  addNode(node: PhysicalNode): void {
    if (this.pointsByNode.has(node)) {
      throw new Error(`node already exists: ${node}`);
    }

    const points: number[] = [];
    for (let replica = 0; replica < this.replicas; replica += 1) {
      const virtualId = `${node}#${replica}`;
      let point = fnv1a(virtualId);

      // 衝突時はring上の次の点を探索し、実際の点を削除用に記録する。
      while (this.ring.has(point)) {
        point = (point + 1) >>> 0;
      }

      this.ring.set(point, virtualId);
      points.push(point);
    }

    this.pointsByNode.set(node, points);
    this.rebuildPoints();
  }

  removeNode(node: PhysicalNode): void {
    const points = this.pointsByNode.get(node);
    if (!points) return;

    for (const point of points) this.ring.delete(point);
    this.pointsByNode.delete(node);
    this.rebuildPoints();
  }

  getNode(key: string): PhysicalNode {
    if (this.ringPoints.length === 0) {
      throw new Error("cannot route with an empty ring");
    }

    const target = fnv1a(key);
    let left = 0;
    let right = this.ringPoints.length;

    while (left < right) {
      const middle = (left + right) >>> 1;
      if (this.ringPoints[middle] < target) left = middle + 1;
      else right = middle;
    }

    const index = left === this.ringPoints.length ? 0 : left;
    const virtualId = this.ring.get(this.ringPoints[index]);
    if (!virtualId) throw new Error("ring invariant violated");
    return virtualId.slice(0, virtualId.lastIndexOf("#"));
  }

  private rebuildPoints(): void {
    this.ringPoints = [...this.ring.keys()].sort((a, b) => a - b);
  }
}

getNode は二分探索なので、仮想ノード数を V とするとルーティングは O(log V) です。ノード追加・削除は配列の再構築を含めて O(V log V)、メモリ使用量は O(V) になります。読み取りが多く、ノード変更が少ない用途では、このトレードオフは扱いやすいです。

3. ノード追加で本当に移動が少ないか

次のテストでは、1000個のキーを3台から4台へ移したときの担当ノードを比較します。単純な剰余方式ならほとんどのキーが移動しますが、ring方式では追加ノードの区間に入ったキーだけが移動します。

import { ConsistentHashRing } from "./consistent-hash-ring";

const keys = Array.from({ length: 1_000 }, (_, i) => `session-${i}`);

const before = new ConsistentHashRing(128);
for (const node of ["api-a", "api-b", "api-c"]) before.addNode(node);
const assignmentsBefore = new Map(keys.map((key) => [key, before.getNode(key)]));

before.addNode("api-d");
const moved = keys.filter((key) => assignmentsBefore.get(key) !== before.getNode(key));

console.log(`moved=${moved.length}/${keys.length}`);
if (moved.length >= keys.length * 0.6) {
  throw new Error("too many keys moved after adding one node");
}

const empty = new ConsistentHashRing();
try {
  empty.getNode("x");
  throw new Error("empty ring must throw");
} catch (error) {
  if (!(error instanceof Error) || !error.message.includes("empty ring")) throw error;
}

const ring = new ConsistentHashRing(4);
ring.addNode("only-node");
if (keys.some((key) => ring.getNode(key) !== "only-node")) {
  throw new Error("a one-node ring must route every key to that node");
}
ring.removeNode("only-node");

仮想ノード数が少ないと、ノードごとの担当区間が大きく偏ります。replicas を増やすと分布は安定しますが、ringの再構築コストとメモリは増えます。最適値はノード数、キー数、変更頻度を測って決めるべきで、128という値を盲目的に固定する理由はありません。

4. 面接で説明するときの注意点

「ハッシュが均等なら十分」ではない

ノード数を剰余に使う方式は、ノードが1台増えただけで割り当ての基準が変わります。Consistent Hashingの利点は、ハッシュ関数そのものではなく、ノード変更の影響範囲を区間に閉じ込めることです。

仮想ノードは負荷分散の近似である

仮想ノードを増やしても、キーのハッシュが偏る可能性は残ります。実運用では、ノードごとのリクエスト数・レイテンシ・エラー率を観測し、重み付き仮想ノードや再配置を検討します。

ringの変更とリクエストの整合性

複数プロセスが別々のringを持つ場合、更新タイミングがずれると同じキーが異なるノードへ送られます。ringを設定ストアからバージョン付きで配布し、リクエストにring versionを記録すると、切り替え中の追跡が容易です。

まとめ

Consistent Hashingは、分散システムのキー配置を「全体の再計算」から「変更区間だけの再配置」に変える設計です。TypeScriptでは、uint32のハッシュ、仮想ノード、ソート済み配列＋二分探索という小さな部品で実装できます。重要なのはアルゴリズム名を覚えることではなく、衝突・wrap-around・空ring・設定更新の整合性まで含めて不変条件を説明できることです。