論理クロック入門 - Lamport クロックとベクタークロックで分散システムの順序を理解する

複数のサーバのログを集めて時刻順に並べたら、レスポンスがリクエストより前に記録されていた。分散システムを触っていると、一度はこの手の現象に出会います。原因は単純で、それぞれのサーバが別々の時計を持っているからです。そして、この問題に対する答えは「時計をもっと正確に合わせる」ではありません。Leslie Lamportが1978年に示した答えは、物理的な時刻を一切使わずに「前後」を定義するというものでした。この記事では、happens-before関係から出発して、Lamportクロック、ベクタークロック、バージョンベクタ、ハイブリッド論理クロック、そしてGoogle SpannerのTrueTimeまでを、実際にpython3で動かして出力を確認したコードとともに追います。

CAP定理で扱った「分断時に一貫性と可用性のどちらを取るか」という問いの、さらに手前にある「そもそも2つの書き込みのどちらが後なのか」を決める話だと思ってください。

なぜ分散システムで「時刻」が難しいのか

1台のマシンの中なら、順序は自明です。同じCPUの上で命令が順番に実行され、同じ時計を読むのですから、AとBのどちらが先かで悩むことはありません。

ところが分散システムでは、この前提が3つとも崩れます。

• 時計が複数ある: ノードAの「12:00:00.000」とノードBの「12:00:00.000」は、同じ瞬間ではありません。
• メッセージ遅延が予測できない: 送信から受信までの時間は一定ではなく、上限もありません。
• 観測者がいない: 全体を上から眺めて「こちらが先」と裁定できる存在がいません。

Lamportの論文は冒頭でこう定義しています。メッセージ伝送遅延が、1つのプロセス内のイベント間の時間に比べて無視できないほど大きければ、そのシステムは分散システムである。つまり「地理的に離れているかどうか」ではなく「遅延が無視できるかどうか」が分散システムの定義だ、というわけです。

この状況で素朴に物理時刻を信じると、何が起きるか。ノードBの時計が3ミリ秒遅れているだけで、「Bで後から起きた更新」が「Aで先に起きた更新」より小さいタイムスタンプを持ちます。last-write-winsで解決するシステムなら、後から書いたはずの値が黙って消えます。ログの時刻が前後する程度なら読みにくいだけですが、データが消えるとなると話は別です。

タイムゾーンやオフセットの扱いは日時とタイムゾーンの扱いで整理しましたが、ここでの問題はもっと根が深いところにあります。フォーマットや変換ではなく、そもそも複数の時計を完全には合わせられないという物理の問題です。

物理時計の限界 — NTP・クロックスキュー・うるう秒

まず、物理時計をどこまで信頼できるのかを数字で押さえます。

Lamportの論文は、物理時計Ci(t)が満たすべき条件をこう書いています。PC1は|dCi(t)/dt - 1| < κ、つまり時計の進む速度が正しい速度からどれだけずれるかの上限です。そして論文は典型的な水晶発振式の時計ではκは10^-6以下と述べています。100万分の1です。小さく見えますが、1日は86400秒なので、単純に掛け算すると1日あたり約86ミリ秒。何も補正しなければ、この程度は勝手にずれていきます。

だから定期的に合わせるわけですが、その同期にも限界があります。NTPv4の仕様であるRFC 5905は、達成できる精度をこう記述しています。

• 現代的なマシンを使う典型的な一次サーバは、数十マイクロ秒の精度
• 高速LAN上の典型的な二次サーバとクライアントは、ポーリング間隔1024秒までで数百マイクロ秒
• NTPv4では、ポーリング間隔36時間までで数十ミリ秒の精度

つまり条件が良ければマイクロ秒、条件が悪ければ数十ミリ秒。マルチリージョン構成のパブリッククラウドで、数ミリ秒から数十ミリ秒のずれを常に想定しておくのは、けっして悲観的すぎる見積もりではありません。

さらに厄介なのが、時計が単調に進むとは限らないことです。NTPがずれを検出して時刻をステップ調整すると、システムクロックが巻き戻ります。「同じ時刻が2回現れる」「未来の時刻が過去になる」という状況が実際に起きます。

うるう秒も同種の問題を生みます。Googleは2008年以降、うるう秒をステップ調整で適用するのではなく、前後の時間に「スミア（smear）」して分散させています。公式ドキュメントが推奨する標準はUTCの正午から正午までの24時間リニアスミアで、周波数変化は約11.6 ppm、スミア中の1秒はSI秒より約11.6マイクロ秒長くなります。ドキュメントはこの値について、多くのマシンの水晶発振子の製造誤差や熱誤差の範囲内であり、NTPの最大スルーレートである500 ppmを十分下回ると説明しています。

注意すべきなのは、スミアしているサーバとしていないサーバを混在させると、最大0.5秒近い食い違いが生じる点です。同じクラスタ内でNTPの参照先が揃っていないと、うるう秒の日に静かにデータが壊れます。

物理時計の危険を整理すると次のようになります。

Apache Cassandraの公式ドキュメントは、この点を率直に書いています。Cassandraは全てのミューテーション（削除を含む）にタイムスタンプを付け、最新のものを勝たせるlast-write-winsモデルを採るため、Cassandraの正しさはこれらの時計に依存しており、NTPのような適切な時刻同期プロセスを走らせることを確実にせよ、と明記しています。裏を返せば、時計が狂えばデータの正しさも狂う、ということです。

happens-before 関係 — 時刻を使わずに順序を定義する

Lamportの発想の転換はここにあります。物理時計が信用できないなら、物理時計を使わずに順序を定義してしまえばよい。

論文の定義はこうです。イベントの集合上の関係->（happens-before、「happened before」と読む）は、次の3条件を満たす最小の関係である。

1. aとbが同じプロセス内のイベントで、aがbより先に来るなら、a -> b
2. aがあるプロセスによるメッセージ送信で、bが別のプロセスによる同じメッセージの受信なら、a -> b
3. a -> bかつb -> cなら、a -> c（推移律）

そして、a -> bでもb -> aでもない2つの相異なるイベントを「並行（concurrent）」と呼ぶと定義しています。

この定義には物理時刻がまったく出てきません。出てくるのは「同じプロセス内の順番」と「メッセージの送受信」だけです。論文はこの関係を「a -> bは、イベントaがイベントbに因果的に影響を与え得ることを意味する」と言い換えています。並行というのは「同時に起きた」ではなく「互いに影響を与え得なかった」という意味です。

具体的なイベント列で見てみます。3つのプロセスP、Q、Rがあり、Pのp2からQのq2へ、Qのq3からRのr3へメッセージが飛んでいるとします。

時間 ->
 
P   p1 ----- p2 ------------------------------- p3
                \
                 \  (message)
                  \
Q   q1 ----------- q2 ----- q3
                              \
                               \  (message)
                                \
R   r1 ----- r2 ----------------- r3

この図から読み取れる関係を整理します。

重要なのは、この関係が全順序ではなく半順序だということです。並行なペアが存在するので、すべてのイベントを一列に並べることはできません。論文は「分散システムでは、2つのイベントのどちらが先に起きたかを言うことが不可能な場合がある」と述べ、この事実に十分自覚的でないために問題が生じる、と続けています。

Lamport クロックの実装と、その限界

半順序を定義したところで、次はそれを数値で表現します。論文が求める条件はClock Conditionと呼ばれ、次のとおりです。

任意のイベントa、bについて、a -> bならばC(a) < C(b)。

そして論文は、この条件を満たすための実装規則を2つだけ挙げています。

• IR1: 各プロセスPiは、連続する2つのイベントの間でCiをインクリメントする。
• IR2: (a) イベントaがプロセスPiによるメッセージmの送信なら、mはタイムスタンプTm = Ci(a)を含む。(b) メッセージmを受信したプロセスPjは、Cjを現在の値以上かつTmより大きい値に設定する。

これだけです。Pythonにすると数十行で収まります。

class LamportProcess:
    def __init__(self, name):
        self.name = name
        self.clock = 0          # Ci
 
    def local(self, label):
        self.clock += 1                       # IR1
        return self.clock
 
    def send(self, label):
        self.clock += 1                       # IR1
        return self.clock                     # IR2(a): Tm = Ci(a)
 
    def recv(self, label, tm):
        # IR2(b): 自分の値と Tm の大きいほうを取り、さらに +1
        self.clock = max(self.clock, tm) + 1
        return self.clock

先ほどの図と同じイベント列を流した実行結果です。

  p1: C = 1
  p2: C = 2
  p3: C = 3
  q1: C = 1
  q2: C = 3
  q3: C = 4
  r1: C = 1
  r2: C = 2
  r3: C = 5
 
Clock Condition の確認 (a -> b ならば C(a) < C(b))
  p1 -> p2: C(p1)=1 < C(p2)=2 -> True
  p2 -> q2: C(p2)=2 < C(q2)=3 -> True
  q2 -> q3: C(q2)=3 < C(q3)=4 -> True
  q3 -> r3: C(q3)=4 < C(r3)=5 -> True
 
逆は成り立たない (C(a) < C(b) でも a -> b とは限らない)
  C(r1)=1 < C(q2)=3 だが r1 と q2 は並行
  C(p1)=1 < C(r2)=2 だが p1 と r2 は並行

因果関係のあるペアでは、必ず数値が増えています。Qの時計はq1の時点で1でしたが、p2のタイムスタンプ2を受け取って3に飛んでいます。メッセージが時計を引き上げる、というのがIR2の働きです。

論文はさらに、このCにプロセスの任意の全順序をタイブレークとして加えれば、すべてのイベントを1つの全順序に並べられると示しています。そして「論理クロックを正しく実装する理由は、まさにこの全順序を得ることにある」と述べ、応用例として分散相互排除アルゴリズムを構成してみせます。同じ番号付けの発想はRaft合意アルゴリズムのtermにも生きていて、物理時計を一切使わずに古い情報を機械的に捨てられるのは、この単調増加カウンタのおかげです。

ただし、上の実行結果の最後の3行が示すとおり、Clock Conditionの逆は成り立ちません。C(r1)=1はC(q2)=3より小さいのに、r1とq2は並行です。論文自身がこの点を明示しており、逆が成り立つとすれば「並行な2イベントは必ず同じ時刻に起きなければならない」ことになって矛盾する、と説明しています。

これはLamportクロックの決定的な限界です。2つのタイムスタンプを見比べても、因果関係があるのか並行なのかを区別できません。全順序を作りたいだけなら問題ありませんが、「この2つの更新は衝突しているのか」を判定したい場面ではまったく使えません。

ベクタークロック — 因果関係を判定できる時計

1つの整数で足りないなら、ノードごとにカウンタを持てばいい。この発想がベクタークロックです。

提案者としてはColin FidgeとFriedemann Matternの名前が挙げられます。Fidgeの論文は "Timestamps in message-passing systems that preserve the partial ordering"、Matternの論文は "Virtual time and global states of distributed systems" で、いずれも1988年前後とされています。ただし正確な収録先とページ番号については、今回一次資料そのものを確認できませんでした（未確認）。また、両者以前にも同種の仕組みが独立に何度か発明されていたという指摘があり、たとえばParkerらが1983年の論文で「バージョンベクタ（version vector）」という用語を導入していた、という整理です。この点も二次資料に基づくので要確認としておきます。

アルゴリズム自体は単純です。ノード数をNとして、各ノードは長さNのベクタを持ちます。

1. ローカルイベントまたは送信時: 自分の成分を1つ増やす
2. 受信時: 各成分について自分の値と受信したベクタの値のmaxを取り、そのあとで自分の成分を1つ増やす

実装は次のとおりです。

NODES = ["P", "Q", "R"]
 
 
class VectorProcess:
    def __init__(self, name):
        self.name = name
        self.vc = {n: 0 for n in NODES}
 
    def _tick(self):
        self.vc[self.name] += 1
        return dict(self.vc)
 
    def local(self, label):
        return self._tick()
 
    def send(self, label):
        return self._tick()
 
    def recv(self, label, msg_vc):
        # 受信側: 各成分の max を取ってから自分の成分を +1
        for n in NODES:
            self.vc[n] = max(self.vc[n], msg_vc[n])
        return self._tick()
 
 
def compare(a, b):
    le = all(a[n] <= b[n] for n in NODES)
    ge = all(a[n] >= b[n] for n in NODES)
    if le and ge:
        return "同一"
    if le:
        return "a は b より前 (a happens-before b)"
    if ge:
        return "b は a より前 (b happens-before a)"
    return "並行 (concurrent)"

判定ルールはcompareが示すとおりです。全成分が以下ならhappens-before、全成分が以上なら逆向き、どちらでもなければ並行。これだけで因果関係が完全に判定できます。

Lamportクロックとまったく同じイベント列を流した実行結果です。

  p1: [P:1, Q:0, R:0]
  p2: [P:2, Q:0, R:0]
  p3: [P:3, Q:0, R:0]
  q1: [P:0, Q:1, R:0]
  q2: [P:2, Q:2, R:0]
  q3: [P:2, Q:3, R:0]
  r1: [P:0, Q:0, R:1]
  r2: [P:0, Q:0, R:2]
  r3: [P:2, Q:3, R:3]
 
因果関係の判定
  p1 [P:1, Q:0, R:0] vs p2 [P:2, Q:0, R:0] -> a は b より前 (a happens-before b)
  p2 [P:2, Q:0, R:0] vs q2 [P:2, Q:2, R:0] -> a は b より前 (a happens-before b)
  q3 [P:2, Q:3, R:0] vs r3 [P:2, Q:3, R:3] -> a は b より前 (a happens-before b)
  r1 [P:0, Q:0, R:1] vs q2 [P:2, Q:2, R:0] -> 並行 (concurrent)
  p1 [P:1, Q:0, R:0] vs r2 [P:0, Q:0, R:2] -> 並行 (concurrent)
  p3 [P:3, Q:0, R:0] vs r3 [P:2, Q:3, R:3] -> 並行 (concurrent)
  q1 [P:0, Q:1, R:0] vs r1 [P:0, Q:0, R:1] -> 並行 (concurrent)

Lamportクロックでは区別できなかったr1とq2が、はっきり「並行」と判定されています。r1は[P:0, Q:0, R:1]、q2は[P:2, Q:2, R:0]。R成分はr1のほうが大きく、P成分とQ成分はq2のほうが大きい。どちらの向きにも包含関係がないので並行、という理屈です。

「Pはp3を実行したが、その情報はまだRに届いていない」という状態が、そのままベクタに現れているわけです。

代償は明確です。タイムスタンプのサイズがノード数Nに比例します。Lamportクロックが整数1個で済むのに対し、ベクタークロックはN個。ノードが動的に増減するシステムでは、成分の追加・削除をどう扱うかという問題も生じます。この「安いが情報が少ない」対「高いが正確」というトレードオフが、以降のすべての手法の背景にあります。

バージョンベクタと衝突検出 — Dynamo と Riak

ベクタークロックを実データの衝突検出に使った有名な例が、AmazonのDynamoです。SOSP 2007の論文 "Dynamo: Amazon's Highly Available Key-value Store"（DeCandiaら）は、こう書いています。Dynamoはベクタークロックを、同じオブジェクトの異なるバージョン間の因果関係を捉えるために使う。ベクタークロックは実質的に(node, counter)のペアのリストである。

論文が挙げる例が分かりやすいので、そのまま実装してみます。ノードSxがオブジェクトを書き、[(Sx, 1)]というクロックが付く。同じノードが更新すると[(Sx, 2)]になり、これは前者の子孫なので上書きしてよい。別のノードSyが更新すると[(Sx, 2), (Sy, 1)]になる、という流れです。

def descends(a, b):
    """a が b の子孫（b 以降）なら True"""
    return all(a.get(k, 0) >= v for k, v in b.items())
 
 
def concurrent(a, b):
    return not descends(a, b) and not descends(b, a)
 
 
class Store:
    def __init__(self):
        self.versions = []      # [(vv, value)]
 
    def put(self, node, value, context):
        vv = dict(context)
        vv[node] = vv.get(node, 0) + 1
        # context の子孫になっている既存版は捨てる（syntactic reconciliation）
        kept = [(v, val) for (v, val) in self.versions if not descends(vv, v)]
        kept.append((vv, value))
        self.versions = kept
        return vv

ショッピングカートを題材に動かした実行結果です。

=== 1. Sx が2回書き込む（因果関係あり）===
  D1 vv={'Sx': 1} value={'cart': ['milk']}
  D2 vv={'Sx': 2} value={'cart': ['milk', 'eggs']}
  保持されている版の数: 1 (D2 が D1 を上書き)
 
=== 2. ネットワーク分断中に Sy と Sz が並行に書き込む ===
  vv={'Sx': 2, 'Sy': 1} value=['milk', 'eggs', 'butter']
  vv={'Sx': 2, 'Sz': 1} value=['milk', 'eggs', 'flour']
  保持されている版の数: 2
  D3 と D4 は並行か: True
  D3 は D2 の子孫か: True
 
=== 3. 読み取り時に意味的マージ（カートは和集合）===
  マージ後の context: {'Sx': 2, 'Sy': 1, 'Sz': 1}
  vv={'Sx': 3, 'Sy': 1, 'Sz': 1} value=['butter', 'eggs', 'flour', 'milk']
  保持されている版の数: 1
 
=== 4. もし物理時刻の last-write-wins で解決していたら ===
  D3 (butter) と D4 (flour) のうち片方が消える -> 商品がカートから消失

因果関係のある更新は自動的に1本にまとまり（構文的マージ）、並行な更新は2つとも保持されてアプリケーションに判断が委ねられます（意味的マージ）。カートなら和集合を取るのが正しく、その結果、butterもflourも失われません。物理時刻のlast-write-winsなら、どちらかが黙って消えていたところです。

ベクタークロックのサイズ問題は、Dynamoでも現実の課題でした。論文はクロック切り詰め（clock truncation）の仕組みを説明しています。各(node, counter)ペアに最終更新時刻を保存しておき、ペア数がしきい値（論文は「たとえば10」と書いています）に達したら最も古いペアを削除する。論文自身が「この切り詰めは子孫関係を正確に導出できなくなるので非効率を生じ得る」と認めたうえで、「本番では表面化していないため十分に調査していない」と正直に付記しています。

対照的なのがCassandraです。Cassandraはベクタークロックを使わず、CQLの行ごとにLWW-Element-Set CRDTを用いるlast-write-winsモデルを採ります。公式ドキュメントは、CQLパーティション内の全ての行の全ての列に個別のミューテーションタイムスタンプを適用し、その値はクライアントの時計か、指定がなければコーディネータノードの時計から得ると説明しています。シンプルな設計ですが、その代わり時計の正しさに全面的に依存します。

なお、混同しやすい点を1つ。今日のAmazon DynamoDB（マネージドサービス）は、2007年のDynamo論文のシステムとは別物です。USENIX ATC 2022の論文 "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service" は、パーティションのレプリケーショングループがリーダー選出と合意にMulti-Paxosを用い、書き込みと強一貫性読み取りはリーダーレプリカのみが処理すると記述しています。ベクタークロックによるリーダーレスな衝突検出という話ではありません。データをどのノードに配置するかというコンシステントハッシュ法の系譜はDynamo論文から続いていますが、順序の付け方は別の道を歩んでいます。

ハイブリッド論理クロック（HLC）と CockroachDB

ここまでで、2つの世界が見えてきました。論理クロックは因果を正しく捉えるが、物理時刻と結びついていない。物理時計は「先週の月曜のスナップショットが欲しい」に答えられるが、因果を保証しない。

この2つを1つのタイムスタンプに畳み込んだのがハイブリッド論理クロック（HLC）です。Sandeep Kulkarni、Murat Demirbasらによる論文で、テクニカルレポート版のタイトルは "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases"、会議版は "Logical Physical Clocks" として OPODIS 2014 に収録されています。要旨によれば動機は、理論の分散システムが時間の概念を避けて「因果追跡」という抽象を導入した一方、実務のシステムは物理時刻（NTP）をベストエフォートで使ってきた、という理論と実務のギャップを埋めることにあります。

HLCの狙いは明快で、論理クロックと同様の一方向の因果検出を提供しつつ、クロック値を常に物理時刻の近くに保つこと。そして64ビットのNTPタイムスタンプ形式に収まり、NTPの癖や不確実性に対して耐性があるという性質を持ちます。

タイムスタンプは(l, c)の2成分です。lが物理時刻に近い成分、cが同じlを持つイベントを区別する論理成分です。論文のFigure 5のアルゴリズムをそのまま実装します。

class HLC:
    def __init__(self, name):
        self.name = name
        self.l = 0      # 物理時刻に近い成分
        self.c = 0      # 同一 l を区別する論理成分
 
    def now(self, pt):
        """送信またはローカルイベント"""
        l_prev = self.l
        self.l = max(l_prev, pt)
        if self.l == l_prev:
            self.c += 1
        else:
            self.c = 0
        return (self.l, self.c)
 
    def update(self, pt, m):
        """受信イベント。m は受信したメッセージの (l, c)"""
        l_prev, (l_m, c_m) = self.l, m
        self.l = max(l_prev, l_m, pt)
        if self.l == l_prev == l_m:
            self.c = max(self.c, c_m) + 1
        elif self.l == l_prev:
            self.c += 1
        elif self.l == l_m:
            self.c = c_m + 1
        else:
            self.c = 0
        return (self.l, self.c)

ノードBの物理時計が3ミリ秒遅れている状況で動かした結果です。

=== 1. 物理時刻が進んでいる間は l が物理時刻に追随する ===
  A local  pt=10 -> (10, 0)
  A local  pt=11 -> (11, 0)
  A send   pt=12 -> (12, 0)
 
=== 2. B の物理時計が 3ms 遅れている（pt=9）===
  B recv   pt=9  m=(12, 0) -> (12, 1)
  物理時刻は巻き戻っているが、HLC は l=12 を引き継ぐので単調増加を保つ
  B local  pt=9  -> (12, 2)   (l が動かないので c が増える)
  B local  pt=9  -> (12, 3)
  B send   pt=13 -> (13, 0)   (物理時刻が追いつくと c は 0 に戻る)
 
=== 3. 因果関係は (l, c) の辞書式比較で判定できる ===
  A の送信 (12, 0) < B の送信 (13, 0): True
 
=== 4. 物理時刻の last-write-wins との比較（時計が 3ms 遅れた B）===
  A: x=1 pt=12 HLC=(12, 0)
  B: x=2 pt=9  HLC=(12, 1)   (A の書き込みを読んだ後の因果的な更新)
  物理時刻 LWW の勝者: A の x=1  -> 後から書いた B の更新が黙って消える
  HLC LWW の勝者:      B の x=2  -> 因果順どおり B が勝つ

第2節が本質です。Bの物理時刻は9で、受け取ったメッセージのlは12。HLCはmaxを取るのでlは12のまま維持され、時刻の巻き戻りが吸収されます。そのあいだイベントを区別するのはcの役割で、cが2、3と増えていく。物理時刻が13に追いつくとlが更新され、cは0にリセットされます。cが伸び続けるのは時計がずれているあいだだけで、同期が正常ならcはほとんど0のままです。

第4節は、時計のずれがそのままデータ損失になる場面を並べたものです。Aの書き込みを読んでからBが書いた、という明確な因果関係があるのに、物理時刻だけで比べるとAが勝ってしまいます。HLCなら(12, 1)が(12, 0)に勝つので、因果順が保たれます。

このHLCを本番で採用している代表例がCockroachDBです。公式ドキュメントは、CockroachDBが「物理成分（常にローカルの壁時計に近い）と論理成分（同じ物理成分を持つイベントを区別するために使う）から成るハイブリッド論理クロック（HLC）」を使うと説明し、ゲートウェイノードが各トランザクションにHLCでタイムスタンプを割り当て、それをMVCCによる値のバージョン管理とトランザクション分離保証の両方に用いる、としています。

そのうえで、CockroachDBは時計のずれに上限を仮定します。公式FAQは最大オフセットの既定値は500ミリ秒であり、ノードが「クラスタ内の他のノードの少なくとも半数と、許容される最大オフセットの80パーセントぶんずれている」と検出した場合、そのノードは自ら停止すると述べています。既定値なら400ミリ秒が閾値ということになります。ドキュメントは、設定されたクロックオフセットの範囲を超えるずれは「因果的に依存するトランザクション間の単一キー線形化可能性の違反につながり得る」と明記しています。

さらにCockroachDBには不確実性区間（uncertainty interval）という概念があります。読み取りが自分より新しいタイムスタンプの値に遭遇したとき、クロックスキューのせいでそれが本当に未来なのか過去なのか判断できない、という状況です。公式ブログはこれを「不確実性リスタート」で処理し、暫定コミットタイムスタンプを遭遇した値のすぐ上に押し上げると説明しています。リスタートが複数回起きることはあり得るものの、不確実性区間より長く続くことはない、とも書かれています。分離レベルの話はトランザクションとACID・分離レベルで扱いましたが、地理分散環境ではその保証を支える土台に時計が入り込んでくるわけです。

TrueTime と Spanner — 不確実性を隠さず露出する

もう1つのアプローチが、Google SpannerのTrueTimeです。OSDI 2012の論文 "Spanner: Google's Globally-Distributed Database" が提示した発想は、逆転していて面白い。時計の不確実性を減らすのではなく、APIとして露出してしまうのです。

TrueTimeのAPIはこうなっています。

通常の時刻APIが1つの値を返すのに対し、TrueTimeは区間を返します。論文は「TrueTimeは時刻を明示的にTTintervalとして表現する。これは有界な時刻不確実性を持つ区間であり、クライアントに不確実性の概念をまったく与えない標準的な時刻インタフェースとは異なる」と説明しています。TT.now()が返す区間は、その呼び出しが行われていた絶対時刻を含むことが保証されます。区間幅の半分をε（イプシロン）と呼びます。

実装は、データセンタごとのタイムマスタ群と、マシンごとのタイムスレーブデーモンから成ります。マスタの多くは専用アンテナを備えたGPS受信機を持ち、残りは原子時計を積んだArmageddonマスタと呼ばれるものです。2種類の参照源を使うのは、GPSと原子時計で故障モードが異なるからだと論文は説明しています。GPSはアンテナや受信機の故障、電波干渉、うるう秒の誤処理やなりすましに弱く、原子時計はGPSとは無相関に故障し、長期的には周波数誤差でドリフトする。デーモンは複数のマスタをポーリングし、Marzulloのアルゴリズムの変種で「嘘つき」を検出・排除します。

肝心の数字です。論文は本番環境について、εは時間に対して典型的にはのこぎり波状で、各ポーリング間隔で約1ミリ秒から7ミリ秒のあいだを変動する。したがって平均は大半の時間で4ミリ秒であると書いています。そしてデーモンのポーリング間隔は現在30秒、適用しているドリフト率は毎秒200マイクロ秒。この2つを掛けると30秒 × 200マイクロ秒/秒 = 6ミリ秒で、のこぎり波の振れ幅とちょうど整合します。論文全体としては、不確実性を「一般に10ミリ秒未満」に保っていると要約しています。

では、この区間をどう使うのか。答えがcommit wait（コミット待ち）です。論文はこう書いています。「コーディネータリーダーは、TT.after(si)が真になるまで、クライアントがトランザクションTiのコミットしたデータを見られないようにする。コミット待ちはsiがTiの絶対コミット時刻より小さいことを保証する」。

要するに、コミットタイムスタンプが確実に過去になるまで、意図的に待つのです。論文の要旨も「不確実性が大きければ、Spannerはその不確実性を待ち切るために減速する」と述べています。時計の精度に金と手間をかける理由がここにあります。εが小さいほど、待ち時間が短くなるからです。

Google Cloudの公式ドキュメントは、TrueTimeを「Googleの全サーバ上のアプリケーションに提供される、高可用な分散クロック」であり「単調増加するタイムスタンプの生成を可能にする」と説明し、Spannerが提供する保証を外部一貫性（external consistency）と呼んでいます。実際には複数サーバにまたがって実行されているにもかかわらず、すべてのトランザクションが順番に実行されたかのように振る舞う、という保証です。なお、この公式ページにはεの具体的な数値やコミット待ちの説明は載っていませんでした。数値が必要ならOSDI 2012の論文にあたるのが確実です。

なお論文は、TrueTimeの時刻エポックについて「うるう秒スミアリングを伴うUNIX時刻に類似している」と書いています。前半で見たGoogleのリープスミアが、ここで効いてくるわけです。

実務でどう選ぶか

ここまでの手法を、実務の判断軸で並べます。

選び方の目安は次のようになります。

単に一意で単調な順番が欲しいだけなら、論理クロックは要りません。単一ノードのシーケンスや、UUIDとULIDのような時刻ソート可能な識別子で足りることがほとんどです。ここに分散の道具を持ち込むのは過剰です。

複数のレプリカが独立に書き込みを受け付けるなら、バージョンベクタを検討します。物理時刻のlast-write-winsは実装が簡単ですが、並行更新が「衝突」なのか「片方が古い」のかを区別できません。カートや集合のようにマージ規則が定義できるデータなら、衝突を検出してアプリで解決する価値があります。逆に「最新の値だけ分かればよい」センサ値のようなデータなら、last-write-winsで十分です。

地理分散のトランザクションDBを自前で作るなら、HLCが現実解です。TrueTimeは専用のGPS受信機と原子時計を前提とするため、汎用のクラウドやオンプレでは再現できません。CockroachDBがHLCを選んだのは、まさにその制約からでした。ただしHLCも「時計のずれに上限がある」という仮定の上に立っています。この仮定が破れると単一キーの線形化可能性が壊れ得るからこそ、CockroachDBはずれの大きいノードを自ら落とす設計にしています。

どの方式でも、時刻同期の運用からは逃げられません。クラスタ内でNTPの参照先を揃える。うるう秒のスミア方式を揃える。時刻同期の状態を監視項目に入れる。ノードの時計が飛んだときの挙動を決めておく。ここを疎かにすると、平常時は何も起きず、忘れた頃に再現不能なデータ破損として噴き出します。

最後に、実装レベルの注意を1つ。経過時間の測定に壁時計を使わない。タイムアウトやリース期限のような「どれだけ経ったか」の判定は、NTPの調整やうるう秒で巻き戻り得る壁時計ではなく、単調時計（Pythonならtime.monotonic()、Goならtime.Since、JavaScriptならperformance.now()）を使うべきです。この使い分けはローカルの1プロセス内でも効く話で、分散システムに限りません。

まとめ

分散システムの「時刻」は、精度の問題ではなく順序の問題です。要点を振り返ります。

• 物理時計は同期しきれない。RFC 5905はNTPv4の精度を、条件が良ければ数十マイクロ秒、ポーリング間隔が長ければ数十ミリ秒と記述している。さらにステップ調整で時刻は巻き戻る。
• Lamportは1978年のCACM論文（Vol 21, No 7, pp. 558-565）で、物理時刻を使わずに順序を定義するhappens-before関係を示した。同一プロセス内の順序、メッセージの送受信、推移律の3条件だけで定義され、どちらでもないペアを「並行」と呼ぶ。
• Lamportクロックは整数1個でa -> bならばC(a) < C(b)を保証する。実装規則はIR1（イベント間でインクリメント）とIR2（送信時にタイムスタンプを載せ、受信時にmaxを取る）の2つだけ。ただし逆は成り立たず、衝突検出には使えない。
• ベクタークロックはノードごとにカウンタを持ち、全成分の大小比較で因果関係を完全に判定できる。代償はノード数に比例するサイズ。
• Dynamo論文はベクタークロックを(node, counter)のペアのリストとして使い、並行バージョンをアプリに返して意味的マージを委ねた。サイズ対策としてペア数が「たとえば10」に達したら古いものを捨てる切り詰めも行っている。
• Riakはシブリングとドット付きバージョンベクタでこれを継承。Cassandraは対照的にLWW-Element-Set CRDTによるlast-write-winsを採り、公式ドキュメントで時刻同期の必要性を明記している。
• HLC（OPODIS 2014）は物理成分lと論理成分cを組み合わせ、64ビットのNTPタイムスタンプ形式に収まりながら因果を保つ。CockroachDBが採用し、既定の最大クロックオフセットは500ミリ秒、その80パーセントを超えたノードは自ら停止する。
• SpannerのTrueTimeは不確実性を区間として露出し、GPSと原子時計でεを約1ミリ秒から7ミリ秒に抑え、コミット待ちで外部一貫性を実現する。ポーリング間隔30秒、ドリフト率毎秒200マイクロ秒。

「分散システムに正確な現在時刻は存在しない」という前提を受け入れると、設計の見通しが一気に良くなります。必要なのは正確な時刻ではなく、正しい順序です。この記事のコードは全部で200行に満たないので、手元で書き換えて、メッセージの順番を入れ替えたり時計をずらしたりしてみてください。ベクタークロックが「並行」を返す瞬間を自分の目で見ると、なぜこの仕組みが必要なのかが腑に落ちます。

参考リンク

• Time, Clocks, and the Ordering of Events in a Distributed System - Leslie Lamport (CACM 1978)
• Leslie Lamport の論文一覧（掲載巻号と本人による注記）
• Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)
• Spanner: Google's Globally-Distributed Database (OSDI 2012)
• Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (University at Buffalo TR 2014-04)
• Logical Physical Clocks - OPODIS 2014 版
• CockroachDB Documentation: Transaction Layer（HLC とクロックスキュー）
• CockroachDB Documentation: Operational FAQs（最大オフセットの既定値）
• Apache Cassandra Documentation: Dynamo（last-write-wins と時刻同期）
• Riak KV Documentation: Causal Context
• Google Public NTP: Leap Smear
• RFC 5905: Network Time Protocol Version 4
• Cloud Spanner: TrueTime and external consistency
• Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (USENIX ATC 2022)