論理時計：Lamportタイムスタンプとベクタークロック

なぜ物理時計では順序を決められないのか

分散システム（/devops/microservices/）で「イベントAとBはどちらが先に起きたか」を判定したくなる場面は多い。たとえば同じデータへの2つの更新が競合したとき、どちらを最終値にするかを決めるには順序が要る。素朴には各ノードの壁時計（wall clock）のタイムスタンプを比較すればよさそうに見えるが、これは破綻する。

理由は2つ。第一に、ノードごとの物理時計は 必ずずれる（clock skew）。NTP で同期しても数ミリ秒〜数十ミリ秒の誤差は残り、その間に起きた2イベントの大小はあてにならない。第二に、物理時計は 巻き戻る。NTP の補正やうるう秒で時刻が後退すると、「後のイベントの方が小さいタイムスタンプ」という逆転が起きる。

happened-before 関係：因果の定義

そこで Lamport（1978）は、物理時刻を捨て、イベント間の因果関係そのもの を定義した。これが happened-before 関係（記号 →）である。次の3条件で定める。

1. 同一ノード内：同じプロセス内でイベント a が b より前に実行されたなら a → b。
2. メッセージ：a が「送信」、b がその「受信」なら a → b（送る前に受け取ることはない）。
3. 推移律：a → b かつ b → c なら a → c。

この → が「a は b に影響を与ええた」という因果の可能性を表す。重要なのは、a → b でも b → a でもないペアが存在することだ。これを 並行（concurrent、記号 a ∥ b） と呼ぶ。並行とは「互いに情報が伝わっていない＝どちらが先と言う意味がない」状態であり、矛盾ではなく 分散系の本質 である。→ は全順序ではなく 半順序（partial order） になる。

Lamport タイムスタンプ：半順序を数値に埋め込む

Lamport 時計は、各ノードが整数カウンタ C を1つ持ち、次の規則で更新する。

# 各ノードはローカルカウンタ C を持つ（初期値 0）
# 1) ローカルイベントが起きるたび:
C = C + 1

# 2) メッセージ送信時: まず C をインクリメントし、その値を添付して送る
C = C + 1
send(msg, timestamp = C)

# 3) メッセージ受信時: 自分の C と受信値の大きい方を取り、さらに +1
C = max(C, msg.timestamp) + 1

この規則が保証するのは 時計条件（clock condition）：

a → b  ならば  C(a) < C(b)

つまり因果があれば必ずタイムスタンプは増える。受信時に max を取るのが肝で、これにより送信イベントの値が受信側へ「伝播」し、因果の鎖に沿って単調増加する。

実用では、(C, ノードID) の辞書順で全順序（total order）を作れる。同じ C 値のときノードIDで決着をつける手法で、これを Lamport 全順序 と呼ぶ。分散ロックやトランザクションの順序付けに使えるが、あくまで「一貫した任意の順序」であって因果を完全に反映するわけではない点に注意する。

ベクタークロック：並行性を検出する

「因果あり」と「並行」を厳密に判定したいなら ベクタークロック（vector clock） を使う。N ノードの系で、各ノードは長さ N の整数配列 V（各要素が各ノードでの観測カウント）を持つ。

# ノード i の配列を V_i とする（初期は全要素 0）
# 1) ローカルイベント: 自分の要素だけ +1
V_i[i] = V_i[i] + 1

# 2) 送信時: 上記で +1 した後、配列 V_i 全体を添付して送る
# 3) 受信時: 要素ごとに max を取り、最後に自分の要素を +1
for k in 0..N-1:
    V_i[k] = max(V_i[k], msg.V[k])
V_i[i] = V_i[i] + 1

比較規則は次の通り。2つのベクタ VA と VB について、

VA ≤ VB  ⇔  すべての k で VA[k] ≤ VB[k]
VA < VB  ⇔  VA ≤ VB かつ ある k で VA[k] < VB[k]

これを使うと因果関係が 過不足なく 判定できる。

Lamport 時計との決定的な違いは、並行を「どちらにも ≤ が成り立たない」状態として明示的に検出できる ことだ。たとえば VA = (2,1,0)、VB = (1,2,0) は、1要素目は A が大きく2要素目は B が大きいので、どちらの方向にも < が成り立たない。これが並行の数学的なシグネチャである。

どちらを使うか：コストと用途

ベクタークロックは万能に見えるが、配列がノード数 N に比例して大きくなる。ノードが動的に増減する系（メッセージ1本ごとに N 要素を運ぶコスト）では重い。一方 Lamport 時計は整数1つで済むが並行を見分けられない。

実務での使い分けは明確だ。全順序のチケット番号 が欲しい（分散ロック、ログのシーケンス付け）だけなら Lamport で十分。競合を検出して両方残したい（Dynamo 系 KVS の兄弟バージョン、CRDT、Git のマージ判定）ならベクタークロックが要る。

まとめ

• 物理時計はずれと巻き戻りのため、分散環境のイベント順序付けには使えない。代わりに 因果（happened-before, →） を直接定義し、論理時計で表す。
• Lamport 時計 は整数1つで a → b ⇒ C(a) < C(b) を保証するが逆は成り立たず、並行を区別できない。(C, ノードID) で全順序は作れる。
• ベクタークロック は長さ N の配列で a → b ⇔ VA < VB を双方向に保証し、並行（どちらにも ≤ が立たない）を厳密に検出 できる。コストは O(N)。
• 全順序のシーケンスが欲しいなら Lamport、競合検出が要るならベクタークロック。観測（/devops/observability/）やログ突き合わせ（/devops/log-aggregation/）でも、物理時刻の限界を意識することが正確な因果分析の前提になる。