Lamportの論理クロック：分散システムに「時間」を定義した論文

この論文が解いた問題

横にスクロール

分散システムでは、複数のコンピュータがネットワークを介して協調する。ここで根本的な難問になるのが「どのイベントが先に起きたのか」という問いだ。1台のマシンなら内蔵時計を見れば順序は明らかに思える。だが複数のマシンが関わった途端、この直感は崩れる。

各マシンの物理時計は、水晶振動子の個体差でわずかにずれ続ける。ネットワーク越しに時刻を合わせても、通信の遅延そのものが一定しないため、完全には同期できない。結果として、マシンAが「10時00分00.100秒」と記録したイベントと、マシンBが「10時00分00.090秒」と記録したイベントのどちらが本当に先だったのかは、時計の数値だけでは判断できない。BのイベントがAへのメッセージを引き起こしていたとしても、時計のずれ次第で数値は逆転しうるからだ。

Leslie Lamportが1978年に発表した「Time, Clocks, and the Ordering of Events in a Distributed System」は、この問題に発想の転換で答えた。分散システムで本当に必要なのは「何時何分に起きたか」という絶対時刻ではなく、「どちらが原因でどちらが結果か」という因果の順序だ、と見抜いたのである。物理時刻を捨て、イベント間の関係だけから順序を定義する。それがこの論文の出発点だ。

この論文は分散システム分野で最も引用される古典の1つとなり、後続の理論と実装の土台になった。同じ系譜の題材は論文で辿るシリーズからも辿れる。

核心アイデア

happens-before という半順序

Lamportはまず、イベント間の「happens-before（先行）」関係を、記号「→」で定義した。a→b は「aがbより前に起きた」と読む。この関係は、次の3つの規則だけで決まる。

1. 同一プロセス内の順序: 同じプロセスの中でaがbより先に実行されたなら、a→b。
2. 送信と受信: aがメッセージの送信、bがその受信なら、a→b。
3. 推移律: a→b かつ b→c なら、a→c。

この3規則の巧妙さは、物理時計をまったく使っていない点にある。プロセス内の実行順と、メッセージが送られてから受け取られるという因果の連鎖だけで、順序を組み立てる。メッセージは必ず送信が受信に先立つ——この当たり前の事実こそが、離れたマシンのイベント同士を繋ぐ唯一の糸になる。

重要なのは、これが全順序ではなく半順序だという点だ。2つのイベントaとbについて、a→bでもb→aでもない場合がありうる。互いにメッセージの連鎖で繋がっていない、独立したイベントである。これらをLamportは「並行（concurrent）」と呼んだ。並行なイベントには、本質的に前後が存在しない。どちらが先かを問うこと自体が無意味なのだ。

論理クロックで順序を数値にする

半順序の定義はできた。だが実装では、各イベントに具体的な数値を振れると扱いやすい。そこでLamportは「論理クロック」を導入する。各プロセスがカウンタ C を1つ持ち、次の規則で更新する。

初期値: C = 0

規則1: イベントを起こすたびに C を1増やす
規則2: メッセージ送信時、現在の C を timestamp としてメッセージに載せる
規則3: メッセージ受信時、
        C = max(自分のC, 受信した timestamp) + 1

この単純な規則が、次の性質を保証する。もし a→b なら、先に起きたイベントのカウンタは必ず後のイベントより小さくなる。なぜ効くのかは規則をたどれば分かる。同一プロセス内ではカウンタが単調に増えるので順序は保たれる。メッセージをまたぐ場合は、受信側が「送信時の timestamp より必ず大きい値」を採るよう規則3が強制する。だから因果の連鎖に沿って、カウンタは必ず増加していく。

ただし逆は成り立たない。カウンタが小さいからといって、そのイベントが原因の側だとは限らないのだ。並行なイベントにも、カウンタはたまたま大小の付いた数値を与えてしまうからである。論理クロックが表せるのは「因果があれば数値も順序どおり」という一方向の含意だけであって、数値の大小から因果を復元することはできない。ここは誤解しやすい要注意点だ。

全順序への拡張

論理クロックの値が等しいイベントは、複数ありうる。だが分散システムでは、全プロセスが1つの順序に合意したい場面もある。そこでLamportは、カウンタの値が等しいときはプロセスIDの大小でタイブレークする方法を示した。これで任意の2イベントに必ず前後が付き、半順序を全順序へと拡張できる。

この全順序化は、単なる整理術ではない。Lamportは同じ論文の中で、これを使って複数のプロセスが「同じ操作を同じ順序で適用する」仕組み——後に状態機械複製（state machine replication）と呼ばれる技法——を構築した。全プロセスが操作を同一順序で処理すれば、初期状態が同じである限り、以後の状態も常に一致する。これは分散合意（コンセンサス）の理論的な土台であり、Lamport自身が後年に生み出すPaxosへと繋がっていく着想でもあった。

その後の影響

論理クロックの「因果を数値で近似する」という発想は、その後の分散システムの広い範囲に浸透した。

第一に、ベクタークロックへの発展だ。Lamportクロックは因果があれば数値が増えることは保証するが、数値だけを見て2つのイベントが因果関係にあるのか並行なのかを判定することはできなかった。この限界を埋めるため、各プロセスの論理時刻を要素ごとに束ねた「ベクタークロック」が考案された。ベクタークロックは、2つのイベントが因果で繋がっているか、それとも並行かを完全に判定できる。Lamportクロックが残した問いへの、直接の回答である。

第二に、分散データベースの因果整合性だ。地理的に分散したデータベースでは、すべての更新に厳密な全順序を課すと性能が犠牲になる。そこで「因果関係のある更新の順序だけは守る」という因果整合性が採られる。この考え方の骨格は、まさにhappens-beforeに由来する。AmazonのDynamoが採用したバージョニングは、ベクタークロックで更新の因果を追跡し、並行に起きた競合を検出してアプリケーション側に解決を委ねる。これも系譜をたどればLamportの論文に行き着く。

第三に、分散デバッグとオブザーバビリティだ。複数のサーバーにまたがる処理を追うとき、ログを物理時刻で並べると時計のずれで順序が乱れてしまう。論理クロックやその発展形で因果順にイベントを並べ替えれば、原因と結果を正しく辿れる。分散トレーシングが親子関係でスパンを繋いでいく発想も、この延長線上にある。

まとめ

Lamportの1978年の論文は、「分散システムに絶対時刻は要らない。必要なのは因果の順序だ」という一点を、明快に示した。happens-beforeという半順序でイベントの前後を定義し、論理クロックでそれを単調増加のカウンタへ写し取る。因果があれば数値も順序どおりになる——ただし逆は言えず、並行なイベントには本質的に前後がない。

この単純で強靭なアイデアは、ベクタークロック、因果整合性、状態機械複製、そして分散デバッグへと枝分かれし、現代の分散システムの基礎語彙になった。時間という当たり前のものを疑うことから、これほど広い理論が育った。分散システムを学ぶ者が、最初に読むべき一本である。