ベクタークロック - 分散システムの因果順序と論理時刻

ベクタークロック（Vector Clock）は、分散システムにおいて、物理時刻の同期なしにイベントの因果関係を判定するための論理時刻です。各ノードがベクトル形式の時刻を保持し、メッセージ交換時に更新することで、「AがBより前に起きた」「AとBは並行」といった関係を正確に判定できます。本記事では、Lamport Clock、Vector Clock、Hybrid Logical Clock の原理と実装を体系的に解説します。

概要

分散システムにおける時刻の問題

分散システムでは、各ノードの物理時刻（システムクロック）がずれているため、タイムスタンプだけではイベントの順序を正しく判定できません。

sequenceDiagram
    participant A as Node A<br/>(clock: 10:00:00)
    participant B as Node B<br/>(clock: 9:59:55, 5秒遅れ)

    A->>A: Event E1 at 10:00:00
    A->>B: Message M (timestamp: 10:00:00)
    B->>B: Event E2 at 9:59:58
    B->>B: Receive M at 10:00:03 (local clock)

    Note over A,B: E1 は E2 より前だが、<br/>B の時刻では E2 が先に見える!

Happens-Before 関係

Leslie Lamport が定義した「happens-before」関係（→）は、分散システムにおける因果関係の基礎です。

1. 同じプロセス内で、A が B より前に実行された → A → B
2. A がメッセージ送信、B がその受信 → A → B
3. A → B かつ B → C なら A → C（推移律）

AとBのどちらでもない場合、AとBは並行（concurrent）です。

原則・定義

Lamport Timestamp（ランポートタイムスタンプ）

ルール

1. 各プロセスは整数カウンター L を持つ（初期値0）
2. 内部イベント発生時: L = L + 1
3. メッセージ送信時: L = L + 1 してタイムスタンプを添付
4. メッセージ受信時: L = max(L_local, L_message) + 1

class LamportClock {
  private time = 0;

  tick(): number {
    return ++this.time;
  }

  update(receivedTime: number): number {
    this.time = Math.max(this.time, receivedTime) + 1;
    return this.time;
  }

  getValue(): number {
    return this.time;
  }
}

// 使用例
const nodeA = new LamportClock();
const nodeB = new LamportClock();

const t1 = nodeA.tick(); // A: 1
const t2 = nodeA.tick(); // A: 2

// A が B にメッセージ送信
const messageTime = nodeA.tick(); // A: 3

// B がメッセージ受信
nodeB.update(messageTime); // B: 4

限界

Lamport Clock では L(A) < L(B) でも A → B とは限りません（並行の可能性）。因果関係の逆方向は判定できません。

Vector Clock（ベクタークロック）

ベクタークロックは、全ノードの時刻をベクトルで保持することで、因果関係の双方向判定を可能にします。

ルール

1. N個のノードがある場合、各ノードは長さNのベクトル V[1..N] を持つ
2. ノードiの内部イベント: V[i] = V[i] + 1
3. メッセージ送信時: 現在の V を添付
4. メッセージ受信時: V[j] = max(V[j], V_message[j]) for all j、その後 V[i] = V[i] + 1

class VectorClock {
  private vector: Record<string, number> = {};

  constructor(private readonly nodeId: string, nodeIds: string[]) {
    for (const id of nodeIds) {
      this.vector[id] = 0;
    }
  }

  tick(): Record<string, number> {
    this.vector[this.nodeId]++;
    return { ...this.vector };
  }

  update(receivedVector: Record<string, number>): Record<string, number> {
    for (const id in receivedVector) {
      this.vector[id] = Math.max(this.vector[id] ?? 0, receivedVector[id]);
    }
    this.vector[this.nodeId]++;
    return { ...this.vector };
  }

  // A → B (A happens-before B) かを判定
  happensBefore(other: Record<string, number>): boolean {
    let strictlyLess = false;
    for (const id in this.vector) {
      const a = this.vector[id] ?? 0;
      const b = other[id] ?? 0;
      if (a > b) return false; // どれか1つでも大きければ false
      if (a < b) strictlyLess = true;
    }
    return strictlyLess; // 全て <= で、少なくとも1つが <
  }

  // 並行（concurrent）かを判定
  isConcurrent(other: Record<string, number>): boolean {
    return !this.happensBefore(other) && !this.happenedAfter(other);
  }

  private happenedAfter(other: Record<string, number>): boolean {
    const otherClock = new VectorClock("temp", Object.keys(this.vector));
    otherClock.vector = other;
    return otherClock.happensBefore(this.vector);
  }
}

// 使用例
const nodeA = new VectorClock("A", ["A", "B", "C"]);
const nodeB = new VectorClock("B", ["A", "B", "C"]);

nodeA.tick(); // A: { A:1, B:0, C:0 }
nodeA.tick(); // A: { A:2, B:0, C:0 }

const message = nodeA.tick(); // A: { A:3, B:0, C:0 }

nodeB.update(message); // B: { A:3, B:1, C:0 }
nodeB.tick(); // B: { A:3, B:2, C:0 }

構成要素

Vector Clock の比較演算

flowchart TB
    VA["Vector A<br/>{A:2, B:1, C:0}"]
    VB["Vector B<br/>{A:3, B:2, C:1}"]
    VC["Vector C<br/>{A:1, B:3, C:0}"]

    VA -->|A → B| VB
    VA -.A ‖ C.-> VC
    VB -.B ‖ C.-> VC

Dotted Version Vector（DVV）

Riak 2.0 以降で採用された改良版で、ベクタークロックの肥大化を抑えます。

interface DottedVersionVector {
  dots: Record<string, number>; // アクティブなノードのみ
  context: Record<string, number>; // 全ノードの最大値
}

実装例

1. 完全な Vector Clock 実装（TypeScript）

class DistributedVectorClock {
  private vector: Map<string, number> = new Map();

  constructor(
    private readonly nodeId: string,
    nodeIds: string[],
  ) {
    for (const id of nodeIds) {
      this.vector.set(id, 0);
    }
  }

  increment(): Map<string, number> {
    this.vector.set(this.nodeId, (this.vector.get(this.nodeId) ?? 0) + 1);
    return new Map(this.vector);
  }

  merge(other: Map<string, number>): Map<string, number> {
    for (const [id, count] of other) {
      const current = this.vector.get(id) ?? 0;
      this.vector.set(id, Math.max(current, count));
    }
    this.increment(); // マージ後にインクリメント
    return new Map(this.vector);
  }

  compare(other: Map<string, number>): "before" | "after" | "concurrent" | "equal" {
    let allLessOrEqual = true;
    let allGreaterOrEqual = true;
    let strictlyLess = false;
    let strictlyGreater = false;

    const allKeys = new Set([...this.vector.keys(), ...other.keys()]);

    for (const key of allKeys) {
      const a = this.vector.get(key) ?? 0;
      const b = other.get(key) ?? 0;

      if (a > b) {
        allLessOrEqual = false;
        strictlyGreater = true;
      }
      if (a < b) {
        allGreaterOrEqual = false;
        strictlyLess = true;
      }
    }

    if (allLessOrEqual && allGreaterOrEqual) return "equal";
    if (allLessOrEqual && strictlyLess) return "before";
    if (allGreaterOrEqual && strictlyGreater) return "after";
    return "concurrent";
  }

  toString(): string {
    const entries = Array.from(this.vector.entries())
      .map(([k, v]) => `${k}:${v}`)
      .join(", ");
    return `{${entries}}`;
  }
}

// 使用例: 競合検出
const replica1 = new DistributedVectorClock("R1", ["R1", "R2", "R3"]);
const replica2 = new DistributedVectorClock("R2", ["R1", "R2", "R3"]);

replica1.increment(); // {R1:1, R2:0, R3:0}
replica1.increment(); // {R1:2, R2:0, R3:0}

replica2.increment(); // {R1:0, R2:1, R3:0}

// 競合検出
console.log(replica1.compare(replica2.vector)); // "concurrent"

2. Amazon Dynamo 風の競合解決

interface VersionedValue {
  value: any;
  vector: Map<string, number>;
}

class DynamoStyleKVStore {
  private data = new Map<string, VersionedValue[]>();

  put(key: string, value: any, clientVector: Map<string, number>): void {
    const existing = this.data.get(key) ?? [];

    // 古いバージョン（因果関係があるもの）を削除
    const survivors = existing.filter((v) => {
      const cmp = this.compareVectors(v.vector, clientVector);
      return cmp === "concurrent" || cmp === "after";
    });

    // 新バージョンを追加
    survivors.push({ value, vector: new Map(clientVector) });
    this.data.set(key, survivors);
  }

  get(key: string): VersionedValue[] {
    return this.data.get(key) ?? [];
  }

  private compareVectors(a: Map<string, number>, b: Map<string, number>): string {
    // 簡略化: 上記の compare と同じロジック
    return "concurrent";
  }
}

// 使用例
const store = new DynamoStyleKVStore();

const clock1 = new Map([["A", 1], ["B", 0]]);
const clock2 = new Map([["A", 0], ["B", 1]]);

store.put("key1", { name: "Alice" }, clock1);
store.put("key1", { name: "Bob" }, clock2); // 競合!

const siblings = store.get("key1");
console.log(`Siblings: ${siblings.length}`); // 2（競合している）

3. Hybrid Logical Clock（HLC）

物理時刻と論理時刻を組み合わせ、タイムスタンプの比較可能性とストレージ効率を両立します。

class HybridLogicalClock {
  private logicalTime = 0;
  private lastPhysicalTime = 0;

  now(): { physical: number; logical: number } {
    const physical = Date.now();

    if (physical > this.lastPhysicalTime) {
      this.lastPhysicalTime = physical;
      this.logicalTime = 0;
    } else {
      this.logicalTime++;
    }

    return { physical: this.lastPhysicalTime, logical: this.logicalTime };
  }

  update(remote: { physical: number; logical: number }): { physical: number; logical: number } {
    const physical = Date.now();
    const maxPhysical = Math.max(physical, remote.physical, this.lastPhysicalTime);

    if (maxPhysical === physical && physical === remote.physical) {
      this.logicalTime = Math.max(this.logicalTime, remote.logical) + 1;
    } else if (maxPhysical === physical) {
      this.logicalTime = this.logicalTime + 1;
    } else if (maxPhysical === remote.physical) {
      this.logicalTime = remote.logical + 1;
    } else {
      this.logicalTime = Math.max(this.logicalTime, remote.logical) + 1;
    }

    this.lastPhysicalTime = maxPhysical;
    return { physical: this.lastPhysicalTime, logical: this.logicalTime };
  }

  compare(a: { physical: number; logical: number }, b: { physical: number; logical: number }): number {
    if (a.physical !== b.physical) {
      return a.physical - b.physical;
    }
    return a.logical - b.logical;
  }
}

// 使用例（CockroachDB 風）
const hlc = new HybridLogicalClock();

const t1 = hlc.now(); // { physical: 1700000000000, logical: 0 }
const t2 = hlc.now(); // { physical: 1700000000000, logical: 1 }

// リモートから受信
const remote = { physical: 1700000000100, logical: 5 };
const t3 = hlc.update(remote); // { physical: 1700000000100, logical: 6 }

メリット・デメリット

Lamport Clock のメリット

1. シンプル: 単一の整数カウンター
2. 省メモリ: 8バイト程度
3. 全順序: 全イベントに順序を付けられる

Lamport Clock のデメリット

1. 因果関係の一方向のみ: A → B の判定が不完全
2. 並行判定不可: 並行イベントを検出できない

Vector Clock のメリット

1. 完全な因果関係: happens-before と concurrent を正確に判定
2. 競合検出: 分散データベースの必須機能
3. 理論的に正確: 形式的に証明された正しさ

Vector Clock のデメリット

1. メモリ消費: ノード数 × 8バイト（100ノードなら800バイト）
2. 肥大化: ノードの増減でベクトルサイズが変化
3. 実装複雑: Lamport より複雑

HLC のメリット

1. 省メモリ: 16バイト（physical + logical）
2. 物理時刻に近い: 範囲クエリが可能
3. NTPと併用可: 時刻同期があればさらに正確

HLC のデメリット

1. 完全な因果関係ではない: 物理時刻のずれで順序が狂う可能性
2. NTP依存: 時刻同期が必要

ユースケース

1. Amazon Dynamo / Riak（競合検出）

Dynamo は Vector Clock で競合を検出し、アプリケーション層で解決します。

// Riak の Vector Clock 例
{
  "vclock": "a85hYGBgzGDKBVIcR4M2cgczH7HPYEpkzGNlsP/VfYYvCwA=",
  "values": [
    { "data": "Alice" },
    { "data": "Bob" }  // 競合（siblings）
  ]
}

2. CockroachDB（HLC によるタイムスタンプ）

CockroachDB は HLC で全トランザクションにタイムスタンプを付与し、MVCC を実現します。

3. Apache Cassandra（Lamport Timestamp）

Cassandra は Last-Write-Wins で競合解決し、タイムスタンプに Lamport Clock を使います。

4. 分散トレーシング（因果関係追跡）

Jaeger や Zipkin は、分散トレースのスパン間の因果関係を Vector Clock で追跡します。

落とし穴

1. Vector Clock の肥大化

ノード数が増えるとベクトルが巨大化します。Dotted Version Vector や Interval Tree Clock で緩和できます。

2. クロックの削除

古いノードがクラスタから離脱しても、ベクトルに残り続けます。ガベージコレクションが必要です。

3. 物理時刻との混同

Vector Clock は「実時間」ではなく「論理的順序」です。タイムスタンプとして人間に見せる場合、誤解を招きます。

4. 競合解決の複雑性

Vector Clock は競合を検出しますが、解決はアプリケーション層の責任です。Last-Write-Wins、CRDTs、手動マージなどが必要です。

5. NTPのずれ（HLC）

HLC は物理時刻に依存するため、NTPが大きくずれると因果関係が狂います。

比較表

論理時刻の比較

主要分散DBの時刻管理

ベストプラクティス

1. ノード数に応じて選択: 小規模なら Vector Clock、大規模なら HLC
2. ガベージコレクション: 古いノードのクロックを定期削除
3. 競合解決戦略を明確に: Last-Write-Wins、CRDTs、手動マージ
4. 物理時刻と併用: HLC で人間に読みやすいタイムスタンプ
5. 監視: ベクトルサイズ、競合発生率を追跡
6. テスト: ネットワーク分断・時刻ずれのシミュレーション
7. ドキュメント化: クロックの仕様をチームで共有
8. NTP設定: HLC を使う場合、時刻同期を必ず有効化

まとめ

ベクタークロック・Lamport Clock・HLC は、分散システムにおける因果関係の判定に不可欠な技術です。

• Lamport Timestamp: シンプル、一方向の因果関係のみ
• Vector Clock: 完全な因果関係・並行検出、メモリ消費大
• Hybrid Logical Clock: 物理時刻と論理時刻の融合、省メモリ
• 採用例: Riak（VV）、CockroachDB（HLC）、Cassandra（Lamport）
• 選択: ノード数・要件に応じて適切な方式を選ぶ

分散システムでは、物理時刻だけに頼らず、論理時刻で因果関係を管理することが重要です。

応用トピック

Interval Tree Clock（ITC）

ノードの動的な追加・削除に対応した改良版 Vector Clock で、クロックを木構造で管理します。

Causal Consistency の実装

Vector Clock を使って、因果関係のある操作だけを順序保証する一貫性モデルを実現できます。

class CausalConsistentStore {
  private data = new Map<string, any>();
  private clock: VectorClock;

  async write(key: string, value: any, clientClock: Map<string, number>): Promise<void> {
    // クライアントのクロックが古い場合は待機
    // ... 実装省略
    this.clock.merge(clientClock);
    this.data.set(key, value);
  }
}

Session Guarantees with Vector Clocks

Read-Your-Writes、Monotonic Reads などのセッション保証を Vector Clock で実装できます。

Conflict-free Replicated Data Types（CRDTs）との組み合わせ

CRDTs は Vector Clock を内部で使い、競合解決を自動化します。

参考リソース

• Time, Clocks, and the Ordering of Events in a Distributed System - Leslie Lamport (1978)
• Vector Clocks - Wikipedia
• Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (HLC)
• Dynamo: Amazon’s Highly Available Key-value Store
• CockroachDB: Hybrid Logical Clocks
• Designing Data-Intensive Applications - Chapter 9

関連記事

• 結果整合性 - Vector Clock を使った競合検出と解決
• 合意アルゴリズム - 分散合意における論理時刻の役割