時間とクロック

システムには、少なくとも3つの異なる「時間」の問題が存在する：「現在の日付は何か」、「ある操作にどれだけの時間が経過したか」、そして「2つの分散イベント間に因果関係が存在するか否か」である。これらは、単一の生タイムスタンプでは解決できない。

壁掛け時計と単調クロック：日付と経過時間の分離測定

壁掛け時計（Wall Clock）は、ログの日付、ビジネスカレンダー、システム間のタイムスタンプに使用され、通常 UTC を基準とする。時刻同期や手動調整によりジャンプ（スキップ/巻き戻し）が発生するため、単一マシン上で連続して gettimeofday() を呼び出しても、経過時間を正しく測定できるとは限らない。

Linux において、CLOCK_MONOTONIC は壁掛け時計の離散的なジャンプの影響を受けず、ローカルな間隔や期限切れの測定に適している。ただし、漸進的な周波数調整の影響を受け、通常はシステムのサスペンド時間を含まない。CLOCK_BOOTTIME はサスペンド時間を含む。「タイムアウトにスリープ時間が含まれるべきか」によって選択が分かれる。これらの値を、異なるマシンの絶対時刻を直接比較するために使用することはできない。Linux clock_gettime マニュアル

ローカルの計測が信頼できても、プロセスは長時間サスペンドされた後に次の命令を実行する可能性がある。「リースまで残り1秒」という情報が、プロセスが次の外部書き込みを1秒以内に完了できることを保証するものではない。

Happens-before：プログラム順序とメッセージからの偏序の構築

a→b を以下のように定義する：a と b が同じプロセス内にあり、a が b より前に実行される；または、a がメッセージの送信であり、b がそれに対応する受信である；さらに推移関係を追加する。a→b も b→a も成り立たない場合、それらはこのモデルにおいて「並行（concurrent）」であるとみなす。

並行であることは、2つのイベントが物理的に同じナノ秒に発生したことを意味するものではなく、現在のモデルにおいて利用可能な因果順序が確立されていないことを意味する。モデルが外部の通信チャネルを見落としている場合、導き出された「因果関係なし」が、完全なシステムとは異なる結果になる可能性がある。

Lamport クロック：因果的先後はカウント的先後に包含される

各プロセスはカウント C を維持する。ローカルイベントと送信イベントでは、タイムスタンプを取得する前にカウントを増加させる。受信側は、タイムスタンプ m を含むメッセージを受信すると、max(C,m)+1 に更新する。送信側はその送信イベントに対して1回だけカウントを増加させ、「ローカルイベント」と「送信」の2つのルールで重複してカウントしてはならない。

性質として、a→b ⇒ C(a)<C(b) が成り立つが、逆は成り立たない。通信していない2つのプロセスは、それぞれ 100 と 3 に到達する可能性があるが、100 が相手の最初の3つのイベントを認識していることを意味するものでも、実際に後発生したことを意味するものでもない。

(C, process_id) を辞書式順序でソートすることで、因果の方向と互換性のある全順序をイベントに構築できる。これは決定論的なソート規則であり、数字から現実世界の唯一の完全な順序を復元するものではない。Lamport：Time, Clocks, and the Ordering of Events

ベクトルクロック：各プロセスの既知の進捗を保持

固定された N 個のプロセスにおいて、各プロセス i はベクトル V を保存する。ローカルイベントでは V[i] を増加させる。送信時はそのイベントのベクトルを添付する。受信時は、まず各コンポーネントについて最大値を取り、その後で自分のコンポーネントを増加させる。

2つのイベントベクトル v、w において、すべてのコンポーネントで vᵢ≤wᵢ かつ少なくとも1つが厳密に小さい場合、v<w と表記する。このイベントモデルと更新ルールを完全に遵守している場合、これは因果的先後に対応する。一部のコンポーネントが大きく、他が小さい場合、比較不能である。

例えば、[2,0] と [1,1] は比較不能である。[2,0] と [3,1] は比較可能である。合計値、最大コンポーネント、または辞書式順序では並行性を検出できない。それらの手法は、各プロセスの独立した履歴情報を失うためである。

オブジェクトのバージョンベクトルとイベントのベクトルクロックは密接に関連しているが、カウントの対象や因果的文脈が異なる可能性がある。オブジェクトストレージでは、新しいバージョンの生成、コンテキストのマージ、siblings の保持に関するルールを定義する必要があり、「古いコンテキストでの書き込みは拒否される」と単純化することはできない。競合解決 を参照。

2回のメッセージ伝播に沿って、既知の進捗がどのように増加するかを観察する

ベクトルのコンポーネントが順に A、B、C を表すと仮定する。A の2番目のイベント a2 が B にメッセージを送信する。B は b2 で受信し、その後 b3 で C にメッセージを送信し、C は c2 で受信する。この間、A では送信されなかったローカルイベント a3 が発生した。

c2 の最初のコンポーネントが 2 であることは、その因果的な過去が A の最初の2つのイベントをカバーしていることを示している。a3 はこのパスにメッセージによって取り込まれていない。C(a3)=3 < C(c2)=5 であるが、両者は依然として並行である。ベクトルを比較すると、a3 の A コンポーネントの方が大きく、c2 の B、C コンポーネントの方が大きいという違いが明確になる。

以下では、イベントグラフから祖先集合を求め、前駆のタイムスタンプに基づいて2つのクロックを計算し、すべてのイベントペアをチェックする。入力はトポロジカル順序でリストされるが、リスト上で先に現れることが因果エッジの存在を意味するものではない。明示的なプログラム順序とメッセージエッジのみが関係としてカウントされる。

events = [
    ("a1", 0, ()), ("a2", 0, ("a1",)), ("a3", 0, ("a2",)),
    ("b1", 1, ()), ("b2", 1, ("b1", "a2")), ("b3", 1, ("b2",)),
    ("c1", 2, ()), ("c2", 2, ("c1", "b3")),
]
vectors, lamport, ancestors, last = {}, {}, {}, {}
for name, process, parents in events:
    assert name not in vectors and all(p in vectors for p in parents)
    assert process not in last or last[process] in parents
    vector = [max((vectors[p][i] for p in parents), default=0) for i in range(3)]
    vector[process] += 1
    vectors[name] = tuple(vector)
    lamport[name] = max((lamport[p] for p in parents), default=0) + 1
    ancestors[name] = set(parents)
    for parent in parents:
        ancestors[name].update(ancestors[parent])
    last[process] = name

def vector_before(a, b):
    return all(x <= y for x, y in zip(a, b)) and a != b

for a in vectors:
    for b in vectors:
        causally_before = a in ancestors[b]
        assert vector_before(vectors[a], vectors[b]) == causally_before
        if causally_before:
            assert lamport[a] < lamport[b]
assert vectors["c2"] == (2, 3, 2)
assert lamport["a3"] < lamport["c2"]
assert "a3" not in ancestors["c2"] and "c2" not in ancestors["a3"]

ここでは、固定された3つのアイデンティティを持ち、カウント状態を失わないプロセスをシミュレートしているのみである。再起動後に A のカウントをリセットし、古いアイデンティティを再利用すると、「コンポーネントがそのアイデンティティの完全な接頭辞を表す」という解釈が壊れる。動的メンバーシステムでは、アイデンティティの世代、状態の復元、メタデータの回収を定義する必要があり、単に配列を拡張または切り詰めるだけでは問題は解決しない。

メッセージには送信時の知識が含まれる

ベクトルの各コンポーネントには固有の帰属があり、合計値のみを見てはならない。最も識別力のある操作は、A が送信した後にローカルイベントが発生し、その後で以前のメッセージを B に配信することである。B が得るのは送信時のスナップショットであり、A のその後のイベントは、過去のメッセージと一緒に伝播しない。両側のベクトルを照合することで、「数値が大きいこと」と「関連する履歴をより多く知っていること」の違いが直接わかる。

$$V_j\leftarrow \max (V_j,V_{\mathrm{msg}}),V_j[j]\leftarrow V_j[j]+1$$

論理排他：ソートはプロトコルの一部に過ぎない

Lamport の古典的な排他アルゴリズムは、信頼できる FIFO チャネルなどの仮定の下、タイムスタンプ付きの要求キューを使用する。要求者は REQUEST をブロードキャストする。受信者は要求をキューに追加し、応答を返す。要求者は、自分の要求がキューの先頭にあり、他のプロセスからの対応するメッセージを受信したことを確認してから、クリティカルセクションに入る。退出時は RELEASE をブロードキャストし、各キューからその要求を削除させる。

これは、「優先度に基づいて応答を遅らせ、退出後に補完する」他の排他アルゴリズムとは異なる。遅延応答ルールと Lamport の RELEASE キューフローを無秩序に組み合わせることはできない。全メンバーの待機を必要とするソリューションでは、メンバーの障害も処理する必要がある。そうでなければ、永久に応答しないメンバーが進行を妨げることになる。

物理時間の不確実区間

イベント A の実際の時間が [10,12] にあり、イベント B が [13,15] にあることがわかっている場合、A が B より先であると判断できる。B が [11,14] にある場合、区間が重なり合い、これらの境界のみでは判断できない。

NTP、PTP の精度は、同期元、パスの非対称性、ハードウェアタイムスタンプ、負荷、および失联時間に依存し、「固定 1ms」や「固定 100ns」という普遍的な値は存在しない。ソフトウェアが信頼できる境界を提供できるかどうかは、システムが遅延、発振器ドリフト、および障害に対して持つ仮定に依存する。「ソフトウェアは常に境界を確立できない」と一般化してはならない。

同期停止後、誤差予算は最後の測定で停止しない

最後の同期が信頼できる ±2 ms の境界を与えたと仮定する。その後、発振器の理想時間に対する最大周波数誤差が 200 ppm（1秒経過するごとに最大 0.2 ms の誤差が追加蓄積）であるとすると、再キャリブレーションがなく、ジャンプがなく、これらの境界が常に成立している場合、失联 Δt 秒後の保守的な境界は以下のようになる：

ε(Δt) = 2 ms + 0.2 ms/s × Δt。

したがって、30秒後には ±8 ms、10分後には ±122 ms となる。これらは人為的に与えられた仮定に基づく計算例であり、NTP や特定の水晶発振器のデフォルト性能ではない。2台のマシンがそれぞれ ±8 ms の誤差を持つ場合、2つのクロックの差が 10 ms であっても、実際の先後を確定することはできない。両方の不確実性を考慮に入れる必要がある。

from fractions import Fraction

def error_ms(elapsed_s):
    assert elapsed_s >= 0
    return Fraction(2) + Fraction(200, 1000) * elapsed_s

def definitely_before(a_center, a_error, b_center, b_error):
    return a_center + a_error < b_center - b_error

assert error_ms(30) == 8
assert error_ms(600) == 122
assert not definitely_before(100, 8, 110, 8)  # [92,108] と [102,118] が重なる
assert not definitely_before(100, 8, 116, 8)  # 境界が接触しているため、厳密な先行を証明できない
assert definitely_before(100, 8, 117, 8)

誤差の上界とタイムスタンプの表示精度は異なる：ナノ秒単位で印刷することは、数値形式が細かく設定されていることを示すだけであり、実際の時刻の誤差が小さいことを意味するものではない。失联、温度変化、または同期元異常により元の仮定が無効になった場合、システムは境界を拡大するか、その境界に依存した決定論的判断を停止する必要がある。古い ±2 ms をそのまま使い続けるべきではない。

TrueTime は、時間の不確実性を [earliest,latest] として明示的に公開する。その保証が成立する条件下では、システムは earliest がコミットタイムスタンプを超えるまで待機することで、コミットのリアルタイム順序が目標とするトランザクションセマンティクスを満たすようにする。待機とレプリケーション、トランザクションの並行制御は連携して機能しており、原子時計が単独で全ての一貫性問題を解決するものではない。Spanner と TrueTime

地理的に分散していること自体が、「線形一貫性よりも強い」定義を意味するものではない。Spanner の外部一貫性は通常、トランザクションレベルでのリアルタイム直列順序について議論される。保証を比較する際は、オブジェクトとトランザクションのスコープを一致させる必要がある。

混合論理クロック（HLC）と選択クイックリファレンス

混合論理クロック（HLC）は、物理時間に近いコンポーネントと論理カウントを組み合わせ、因果の方向を保持しつつ、タイムスタンプを物理時間に関連付けやすくする。HLC は、グローバルな実時間の厳密な誤差境界を自動的に提供するものではなく、コンセンサスやトランザクション分離を代替するものでもない。

参考

• Lamport 1978 論文。
• Linux clock_gettime。
• Spanner：TrueTime と外部一貫性。

Keywords: wall clock, monotonic clock, Lamport clock, vector clock, happens-before, TrueTime, HLC