時計と順序 — 「どっちが先？」を作る技術
分散システムには、全員に共通の「今」がありません。各サーバの物理時計は少しずつずれ、そのタイムスタンプを信じると後から書いたデータが消える事故すら起きます。時計のずれを体感したあと、数を数えるだけで「前後」を作り出すラムポート時計とベクトル時計を動かして理解します。
1. 物理時計は必ずずれる
サーバの時計は水晶発振子の振動を数えて動いています。振動数には個体差や温度による変化があり、典型的には数十 ppm（1日あたり数秒）ずれていきます。これをクロックドリフトと呼びます。
NTP などの時刻同期でずれは補正できますが、同期した次の瞬間からまたずれ始めます。下のデモで「NTP 同期」を押しても、すぐに2台の時計が離れていく様子を見てください。
2台のサーバの時計がずれていく
青＝サーバA（進みがち）、緑＝サーバB（遅れがち）。下のグラフは「真の時刻とのずれ」。NTP 同期でずれは一瞬ゼロになりますが、またすぐ開いていきます。見えるようにドリフトを実機の約2000倍に誇張しています（実機の数十 ppm は1秒あたり数十マイクロ秒）。
2. ずれた時計で順序を決めると事故る — LWW の罠
複数のレプリカが同じキーに別々の値を持ってしまったとき、「タイムスタンプが新しい方を残す」という単純な解決策を LWW（Last-Write-Wins）と呼びます。分散KVSで実際に広く使われている方式です。
ところが時計がずれていると、実際には後に行われた書込が古いタイムスタンプを押されてしまい、比較に負けて静かに消えます。下のデモでサーバBの時計のずれを動かして、事故が起きる条件を確かめてください。
タイムスタンプの逆転 — 後の書込が LWW で消える
x=1 を先に、x=2 を後に書いています。Bの時計が遅れていると、後に書いた x=2 のタイムスタンプの方が古くなり、統合時に捨てられます。ずれを 0 にすると正しい結果になることも確認を。
注意 — 物理時計のタイムスタンプで順序を決めてはいけない
NTP で同期しても LAN で数ミリ秒、インターネット越しでは数十ミリ秒以上ずれることは普通にある。仮想マシンの一時停止やうるう秒で秒単位で飛ぶことも。書込が数ミリ秒間隔で来るシステムでは、この程度のずれでも LWW の逆転事故は現実に起きる。
3. ラムポート時計 — 数えるだけの「論理時計」
そこで発想を変えます。「何時何分」を諦めて、出来事の前後関係だけを数字にするのです。各ノードがカウンタ L を1個持ち、次の3つのルールで更新します。
- イベントが起きたら L を +1 する
- メッセージを送るとき L を +1 して、その値をメッセージに添付する
- 受信したら max(自分の L, 届いた L) + 1 にする
受信時: L ← max(L自分, Lメッセージ) + 1
発生・送信時は L ← L + 1。これだけで「a が b の原因になり得るなら L(a) < L(b)」が必ず成り立つ
ラムポート時計の伝播 — ステップ実行で追いかける
横軸＝時間、横線＝各ノード。●の中の数字がカウンタ L。青＝ローカルイベント、オレンジ＝送信、緑＝受信。メッセージ（✉）が届くたびに max+1 で大きい値が伝染していくのがポイント。
POINT — happened-before（→）関係
「a → b（a は b より前）」と言えるのは3つの場合だけ。①同じノード内で a が先 ②a が送信で b がその受信 ③a → c → b とたどれる（推移）。どれでもなければ a と b は並行（∥）。ラムポート時計は「a → b ならば L(a) < L(b)」を保証するが、逆は言えない — L(a) < L(b) でも実は並行かもしれない。並行かどうかまで見分けたいときに使うのが次のベクトル時計。
4. ベクトル時計 — 「並行」まで見分ける
ベクトル時計では、各ノードがノード数ぶんのカウンタの配列 [a, b, c] を持ちます。自分のイベントでは自分の成分だけ +1、受信時は自分の成分を +1 したうえで成分ごとの max を取ります。つまりベクトルは「各ノードの出来事をどこまで知っているか」の記録です。
VC(a) < VC(b) ⟺ すべての成分で ≤ かつ 少なくとも1成分で <
どちら向きにも成り立たなければ a ∥ b（並行）。「相手の知らない出来事を互いに持っている」状態がベクトルの形でそのまま見える
ベクトル時計 — 前後と並行を判定する
各イベントの下の [a,b,c] がベクトル時計。ボタンでイベントペアを切り替えると、下の欄で成分ごとの比較と判定（前後 or 並行）が見られます。オレンジの輪＝ペアの1つ目、紫の輪＝2つ目。
一歩先へ — 物理と論理のハイブリッド
Google Spanner の TrueTime は原子時計と GPS で「今はこの区間のどこか」という不確かさ付きの時刻を返し、区間が過ぎるのを待ってからコミットすることで地球規模の順序保証を実現している。また HLC（ハイブリッド論理時計）は物理時計に近い値を保ちながらラムポート時計の性質も持つ折衷案で、CockroachDB などが採用。ベクトル時計は Amazon Dynamo 系のデータストアで並行更新の検出に使われてきた。
5. まとめ
- 物理時計は必ずずれる。NTP で補正しても、同期の合間にはずれがある。
- LWW ＋ ずれた時計は「後の書込が消える」事故を起こす。タイムスタンプの大小 ≠ 実際の順序。
- ラムポート時計：カウンタ1個。a → b なら L(a) < L(b)。ただし並行は見分けられない。
- ベクトル時計：ノード数ぶんの配列で「前後」と「並行」を完全に判定できる。そのぶんサイズはノード数に比例。