時間とクロック

分散システムにはグローバルクロックが存在しない——2つのノード上のタイムスタンプを直接比較することはできない。Lamport論理クロック（happens-before）からベクトルクロック（並行性の検出）、そしてTrueTime（GPS＋原子時計）に至るまで、それぞれの「クロック」は、一見単純な「イベントの先后」という問題を、異なるコストのトレードオフの中で追求している。

問題: グローバルクロックの欠如

単一マシン上では gettimeofday() を用いて、イベントAとBの先后を比較できる。しかし分散システムでは、Aがノード1で 12:00:00.000 に発生し、Bがノード2で 12:00:00.001 に発生した場合——Aが先であると確定できるだろうか？できない。なぜなら、2つのノードのクロックが完璧に同期することは不可能だからだ。NTPによる同期精度は約1msであり、1ms以内のイベント順序は物理時間だけでは判断できない。

Lamport論理クロック (1978)

Leslie Lamportの洞察：因果関係を判断するために物理時間が必要なのではない——重要なのは、happens-before関係がタイムスタンプに反映されることを保証することだ。

アルゴリズム

各ノードは整数のカウンター C を維持し、初期値は0とする：

1. ローカルイベントが発生（メッセージ送信を含む）：C = C + 1、イベントのタイムスタンプ = C
2. メッセージを送信する際、自身の現在の C を添付する
3. メッセージを受信（タイムスタンプ = C_msg）：C = max(C, C_msg) + 1、受信イベントのタイムスタンプ = C

性質：a が b より前に発生する場合 (a happens-before b)、C(a) < C(b) となる。しかし逆は成り立たない——C(a) < C(b) であっても a → b とは限らない（並行イベントがたまたま異なるカウンター値を持つ可能性がある）。

分散排他制御アルゴリズム (Lamport Mutex)

論理クロックを用いて、セントレス（中央ノードなし）の排他制御を実現する：

1. ノード i が臨界領域に入る場合：全ノードに REQUEST(ts_i, i) を送信
2. リクエストを受信したノード j：臨界領域にいない、かつ入る予定もない場合、REPLY を返信 臨界領域にいる、または自分のリクエストの優先度が高い場合 (ts_j < ts_i) → 返信を遅延させる
3. ノード i が全 REPLY を受信後 → 臨界領域に入る
4. 臨界領域から退出 → 全ノードに RELEASE を送信

利点：単一障害点がなく、完全に分散されている。欠点：3(N-1) 件のメッセージが必要であり、単一ノードの障害がシステム全体のブロックを引き起こす可能性がある。

ベクトルクロック

Lamportクロックの限界：C(a) < C(b) から a → b を逆推論できない。ベクトルクロックはこの問題を解決する。

データ構造

各ノードは長さ N のベクトル V[1..N] を維持する。V[i] は、ノード i が何回イベントを発生させたか、そのノードが把握している値である。

V_a = [3, 5, 2]  意味: ノード1は、自身で3つのイベント、ノード2で5つ、ノード3で2つのイベントが発生したことを知っている

アルゴリズム

1. ノード i でイベントが発生：V[i] = V[i] + 1
2. メッセージを送信する際、現在の V を添付する
3. メッセージを受信（添付された V_msg）：V[k] = max(V[k], V_msg[k]) for all k、その後 V[i] = V[i] + 1

比較ルール

• V(a) < V(b) (a が b より前に発生): V(a) の各要素が V(b) の対応する要素以下であり、かつ少なくとも1つが厳密に小さい
• V(a) と V(b) は比較不可：k, j に対して V(a)[k] < V(b)[k] かつ V(a)[j] > V(b)[j] となる場合 → 並行イベント

実践的な応用

Dynamo/Riak KV はベクトルクロックを用いて競合を検出する：get(key) がベクトルクロック V_old を返す際、クライアントが修正後 put(key, value, V_old) を実行する。サーバー上の現在のバージョンが V_cur の場合、V_cur と V_old を比較する：

• V_cur < V_old: 直接上書き（クライアントが現在のバージョンを確認して修正した）
• V_cur > V_old: 拒否（クライアントが古いバージョンに基づいて修正した）→ read-modify-write が必要
• 比較不可: 並行修正 → 競合解決が必要（アプリケーション層でのマージ、または複数のバージョン（sibling）の保持）

Google TrueTime (Spanner)

最も過激な産業実践：原子時計とGPSを用いて、グローバルなデータセンターに有界なクロックの不確実性区間を提供する。

TT.now() は区間 [earliest, latest] を返す

保証：真の時間は必ずこの区間に含まれる。区間の幅は通常約1〜7ms（GPS/原子時計の同期状態による）。

Spanner の外部一貫性

Spanner のトランザクションは、TrueTime を用いて最も強力な外部一貫性（linearizability よりも強い——データセンター間のリアルタイム順序）を保証する：

コミット待機: トランザクションのコミットタイムスタンプ = TT.now().latest
              トランザクションがレプリカで有効になる前、TT.after(commit_ts) = True となるまで待機
              → 全ノードが見るコミット順序が真の時間と一致することを保証

なぜハードウェアが必要なのか

ソフトウェアでは、有界な誤差を持つクロックを提供することは不可能である——NTP は誤差を見積もるのみであり、ネットワーク遅延の非対称性とジッターにより、誤差の境界は不明瞭になる。TrueTime の保証は、GPS/原子時計の物理的特性に由来する：原子時計の周波数誤差は 10^-13 未満である。

NTP/PTP の実践

NTP (Network Time Protocol): UDPパケットの交換を通じてサーバーとの時間偏差を見積もる。精度は約1ms（LAN）、約10ms（WAN）。課題：

• ジャンプ⁠: NTP が大きな偏差を突然補正 → クロックが巻き戻る → CLOCK_MONOTONIC はこのジャンプを露呈するが、壁掛け時計の時間は遡る
• 振動⁠: NTP が継続的に補正 → クロックの周波数が継続的に微小に変化 → 単調時間を依存するPrometheus TSDB が影響を受ける可能性がある（ただしPrometheusはスクレイピングタイミングに CLOCK_MONOTONIC を使用）
• 同期失敗⁠: NTPサーバーに到達不可 → クロックのドリフトが蓄積 → 数時間〜数日後には誤差が秒単位になる

PTP (Precision Time Protocol, IEEE 1588): データセンターレベルの時間同期、精度は約100ns。ハードウェアサポート（NICのタイムスタンプ機能）が必要。金融取引（MiFID II 準拠）や Spanner の代替クロックソースに使用される。

参考

• 論文⁠: "Time, Clocks, and the Ordering of Events in a Distributed System" (Lamport, 1978)
• 論文⁠: "Spanner: Google's Globally-Distributed Database" (2012, TrueTime セクション)
• 論文⁠: "Virtual Time and Global States of Distributed Systems" (Mattern, 1989 — ベクトルクロック)

Keywords: Lamport clock, vector clock, happens-before, TrueTime, Spanner, NTP, PTP, logical time