ベクタークロックと因果順序

定義

ベクタークロック（Vector Clock）：分散システムで複数のノードが生成するイベントの「因果的な順序関係」を追跡するアルゴリズム。物理的な時刻を使わず、論理的な「どちらが先か」を判断できる。

問題：物理クロックは使えない

[分散システムの問題](./concepts_ddia_distributed_problems.md)で述べた通り:

ノードA: 10:00:00.000 → イベント発生
ノードB: 10:00:00.003（Aより3ms進んでいる）→ イベント発生

タイムスタンプだけではAとBのどちらが「先」かを正確に判断できない
NTPの誤差が原因で順序が逆転することがある

Lamportクロック（論理クロック）

Leslie Lamport（1978）が提案した最もシンプルな論理クロック。

ルール

各ノードはカウンターtを持つ

1. イベント発生時: t = t + 1
2. メッセージ送信時: メッセージにtを付与
3. メッセージ受信時: t = max(自分のt, 受信したt) + 1

例

ノードA (t=0)    ノードB (t=0)    ノードC (t=0)
    │                │                │
t=1 ● a1            │                │
    │                │                │
    │────[t=1]──→   ● b1 (t=2)       │
    │                │                │
t=2 ● a2            │────[t=2]──→   ● c1 (t=3)
    │                │                │

限界

a1 → b1（a1が因果的にb1より前）の場合:
  a1のt=1 < b1のt=2 → ✅ 因果順序と一致

しかし逆は成立しない:
  a2のt=2 = b1のt=2 であっても、a2とb1に因果関係はない
  
「t(a) < t(b) ならa→b（aはbの前）」は正しい
「t(a) < t(b) ならa→b」の逆（t(a) >= t(b) ならb→a）は成立しない

Lamportクロックは「前後関係の確認」はできるが「同時性の検出」はできない。

ベクタークロック

各ノードが「全ノードのカウンター配列」を持つことで、Lamportクロックの限界を解決。

ルール

Nノードのシステムで、各ノードiはV[i]というベクターを持つ（初期値はすべて0）

1. ノードiでイベント発生: V[i] = V[i] + 1
2. メッセージ送信時: 現在のVをメッセージに付与、V[i] = V[i] + 1
3. メッセージ受信時: 
   各要素をmax取り: V[j] = max(V[j], 受信したV[j]) for all j
   V[i] = V[i] + 1

例（ノードA, B, C）

            ノードA        ノードB        ノードC
初期:       [0,0,0]        [0,0,0]        [0,0,0]

a1発生:     [1,0,0]
  A→Bへ送信:               [1,1,0]（受信してV[B]++）

b1発生:                    [1,2,0]
  B→Cへ送信:                              [1,2,1]

a2発生:     [2,0,0]

イベント a2 と c1:
  a2: V=[2,0,0]
  c1: V=[1,2,1]
  
比較:
  a2[A]=2 > c1[A]=1  → a2の方が進んでいる要素あり
  a2[B]=0 < c1[B]=2  → c1の方が進んでいる要素あり
  
  → どちらの要素も一方が大きいとは言えない
  → a2とc1は「同時発生（concurrent）」と判断できる！

因果関係の比較規則

V(a) ≤ V(b) （aはbの前、または同時）:
  V(a)[i] ≤ V(b)[i]  が全てのiで成立

a → b（aはbの直接的・間接的な原因）:
  V(a) < V(b)（V(a) ≤ V(b) かつ V(a) ≠ V(b)）

a ∥ b（同時発生、因果関係なし）:
  V(a) < V(b) でも V(b) < V(a) でもない

バージョンベクター（Version Vector）

ベクタークロックをレプリカ間のデータ競合検出に応用したもの。Amazon Dynamoが採用。

ノードA, B, Cがkey="shopping_cart"を管理

初期: [A:0, B:0, C:0] = []

ユーザーがノードAに「りんご追加」:
  A書き込み: value=["りんご"], version=[A:1, B:0, C:0]

ユーザーがノードBに「バナナ追加」（Aの更新が届く前に）:
  B書き込み: value=["バナナ"], version=[A:0, B:1, C:0]

2つのバージョン:
  [A:1, B:0] = ["りんご"]
  [A:0, B:1] = ["バナナ"]

バージョンベクターの比較:
  [A:1, B:0] と [A:0, B:1] → どちらも相手より大きい要素と小さい要素がある
  → 競合（Concurrent writes）を検出！

競合の解決

競合を検出した後の解決策:

1. Last Write Wins（Dynamo のデフォルト）
   → タイムスタンプで最後を選ぶ（精度問題あり、データロス）

2. アプリケーションで解決
   → 「りんご」と「バナナ」の両方をクライアントに返す
   → ユーザーかアプリが正しいマージを決定

3. CRDT（自動マージ）
   → セット型CRDTなら「りんご + バナナ」を自動的に正解とする
   → [CRDT](./concepts_ddia_crdt.md)を参照

ドットバージョンベクター

実際のDynamoDB系では、「誰が書いたか」の情報をより精密に管理するドットバージョンベクターを使うことが多い。詳細は省略するが、基本思想は同じ。

ベクタークロックの限界

ノード数Nに比例してベクターサイズが増える
→ N=1000のクラスターでは1000要素のベクター

対策:
  - ノード数が増えたら古いエントリを刈り込む
  - CassandraはHybrid Logical Clock（HLC）でサイズ問題を軽減
  - Riak, AmazonDynamoはバージョンベクターを採用

まとめ

方式	判定できること	限界
物理クロック	大まかな前後	NTP誤差で逆転しうる
Lamportクロック	因果的な前後	同時発生を検出できない
ベクタークロック	因果関係 + 同時発生の検出	ノード数でサイズ増大

出典・参考文献

Leslie Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) — Communications of the ACM
Colin Fidge, “Timestamps in Message-Passing Systems” (1988)
Amazon Dynamo Paper — DeCandia et al. (2007)
Martin Kleppmann, Designing Data-Intensive Applications (2017) Chapter 8-9

定義