分散システムにおける論理時計(Logical Clock)

1. 概要

A. 定義

論理時計(Logical Clock)とは、物理的な時刻(wall-clock)に依存せず、イベント間の発生順序と因果関係(causality)を追跡するために、各プロセスが保持する単調増加カウンタ(またはカウンタのベクトル)によってイベントに論理タイムスタンプを付与する仕組みである。1978年にLeslie Lamportが「Time, Clocks, and the Ordering of Events in a Distributed System」で示した先行関係(happens-before, →)の定義を根拠に、物理時刻がずれていても「何が何より先に起きたか」を計算で決定できるようにする。

論理時計は分散システム理論の最も基礎的な道具であると同時に、今日でもデータベース複製・メッセージブローカ・協調編集器・分散トレーシングなど実務の随所で正確性を支える概念である。Cassandraの競合解決、DynamoDB・Riakのバージョン管理、CockroachDB・YugabyteDBのトランザクション順序決定、Kafkaのパーティションオフセット、CRDTの因果性追跡は、いずれも論理時計系のアイデアの上に成り立っている。

B. 登場背景と必要性

単一のコンピュータでは一つのクロックがすべてのイベントに大域順序を与えるため、「先か後か」は自明である。しかし複数のノードがネットワークで協調する分散システムでは、大域的に共有される単一の時刻が存在しない。各ノードの物理時計(quartz oscillator)は温度・電圧によってわずかに速くなったり遅くなったりするドリフト(drift)を被り、NTPで周期的に合わせてもネットワーク遅延の非対称性のためノード間に数ミリ秒から数十ミリ秒の時計誤差(clock skew)が常在する。

この小さな誤差が正確性を崩す理由は、分散システムで「誰が最新値か」「このイベントがあのイベントの原因か」を物理時刻の大小比較で判定した瞬間、因果関係が逆転しうるからである。たとえばノードAが12:00:00.030に記事を書き、そのメッセージを受け取ったノードBが12:00:00.020(時計が10ms遅い)に返信すると、物理タイムスタンプだけを見れば原因(記事)より結果(返信)が先に起きたと記録される。LWW(Last-Write-Wins)方式がこうした状況で後から書いた値を音もなく捨てる更新喪失(lost update)を起こす根本原因がここにある。論理時計は物理時刻を信頼せず、プロセス内部の順序とメッセージ送受信という実際の因果連鎖のみで順序を定義してこの問題を回避する。

C. 主要な特徴

論理時計の性質は三つに要約される。第一に、因果性の保存——イベントaがbの原因であれば(a → b)、必ずタイムスタンプC(a) < C(b)が成り立つ(時計条件、clock condition)。第二に、物理時刻からの独立——正確な時刻同期なしにカウンタ増加とメッセージ交換だけで順序を定める。第三に、半順序(partial order)の表現——因果的に無関係な二つのイベントは「同時(concurrent)」のまま残し、無理に全順序を強要しない。特にスカラLamport時計は「a → b ⇒ C(a) < C(b)」のみを保証しその逆は成り立たない一方、ベクトル時計は逆方向まで満たして同時性まで正確に判別するという点が両系統を分ける決定的な差である。

2. 物理時計の限界と先行関係(happens-before)

論理時計を理解する出発点はLamportが定義した先行関係→である。これは三つの規則で定義される半順序である。①同一プロセス内でaがbより先に実行されればa → b、②aがメッセージ送信でbがそのメッセージの受信であればa → b、③推移性(a → b、b → cならばa → c)。どの規則によっても互いに結ばれない二つのイベントは同時(a ∥ b)であり、これは「同じ時刻に起きた」ではなく「互いに影響を与えられなかった」という因果的独立を意味する。

ここで注目すべきは、先行関係が物理時刻をまったく参照しないという点である。もっぱらプロセス内部の実行順序とメッセージ送受信という観測可能な事実のみで定義されるため、時計がどれほどずれていても無関係に成立する。論理時計とは結局、この抽象的な先行関係をプログラムが扱える整数(または整数ベクトル)タイムスタンプへ符号化(encoding)する装置である。したがって良い論理時計は「a → bならばタイムスタンプもその順序を反映する(時計条件)」を必ず守らねばならず、さらにその逆まで成り立てば同時性判別というより強い能力を得る。

flowchart TB
    subgraph Problem["物理時計の限界"]
      D["時計ドリフト(drift)"] --> SK["ノード間の時計誤差(skew)"]
      NTP["NTP同期<br/>(ネットワーク遅延の非対称)"] --> SK
      SK --> INV["因果関係の逆転<br/>(原因より結果が先に記録)"]
      INV --> LU["更新喪失(LWW lost update)"]
    end
    subgraph Solve["論理時計の解法"]
      HB["先行関係 happens-before(→)"] --> SC["時計条件: a→b ⇒ C(a)<C(b)"]
      SC --> L["Lamportスカラ時計<br/>(全順序、同時性判別不可)"]
      SC --> V["Vector Clock<br/>(半順序、同時性判別可)"]
      SC --> H["Hybrid Logical Clock<br/>(物理+論理の結合)"]
    end
    INV -.代替.-> HB

物理時計がなぜ危険かはCAP・複製の文脈でより明確になる。地理的に離れた二つのデータセンタがそれぞれ書き込みを受け付け後で併合するとき、「タイムスタンプが大きい方が勝つ」という規則を使うと、時計が少し速いノードの書き込みが常に勝ち、正常な最新の更新が過去の値に上書きされる異常が発生する。実際にCassandra初期の運用では、ノード間の時計が合わずに書いたばかりのデータが消える事故が繰り返し報告され、このためCassandraはNTP厳格同期を必須の運用要件として明記した。論理時計はこうした物理時刻依存を取り除き、実際にやり取りされたメッセージの因果連鎖のみを根拠に順序を立てるという点で根本的に安全である。

3. Lamportスカラ論理時計

最も単純な論理時計は、各プロセスが整数カウンタ一つだけを保持するLamport時計である。規則は三つで非常に簡潔である。①プロセスは内部イベントが起きるたびに自分のカウンタを1増やす。②メッセージを送るとき現在のカウンタ値を一緒に載せて送る。③メッセージを受け取ると自分のカウンタをmax(ローカル, 受信値) + 1に更新する。このmax + 1規則が核心であり、受信プロセスの時計がどれほど遅かったとしても、「メッセージを受け取った事象」のタイムスタンプが必ず「メッセージを送った事象」より大きくなるよう強制して因果性を保存する。

sequenceDiagram
    participant P1 as プロセス P1
    participant P2 as プロセス P2
    participant P3 as プロセス P3
    Note over P1,P3: 各自カウンタ=0から開始
    P1->>P1: 内部イベント → C=1
    P1->>P2: メッセージ送信(ts=2), C=2
    P2->>P2: 受信 → C=max(0,2)+1=3
    P2->>P3: メッセージ送信(ts=4), C=4
    P3->>P3: 受信 → C=max(0,4)+1=5
    Note over P1,P3: C(P1送信)=2 < C(P2受信)=3 < C(P3受信)=5

こうして得たスカラ値は時計条件(a → b ⇒ C(a) < C(b))を満たす。しかし決定的な限界がある。逆は成り立たない。すなわちC(a) < C(b)だからといってaがbの原因である保証はない。互いに無関係に進んだ二つのプロセスのイベントも偶然に一方のカウンタが大きくなりうるからである。ゆえにLamport時計だけでは「この二つのイベントが因果的に関連するのか、それとも同時なのか」を区別できない。

この限界にもかかわらずLamport時計は実務で非常に有用である。異なるプロセスのタイムスタンプが等しいときプロセスIDで任意のtie-breakを適用すれば、因果性と矛盾しない全順序(total order)を作れる。この全順序の上ですべてのノードが要求を同じ順序で処理するようにするのがLamportの分散相互排除(mutual exclusion)アルゴリズムであり、これは後に状態機械複製(state machine replication)の理論的土台となった。たとえば複数のノードが共有資源のロックを要求するとき、(タイムスタンプ, ノードID)順にキューを整列すれば、物理時計なしにすべてのノードが同一の順序に合意できる。

全順序を得るということの実務的含意は決定性(determinism)である。複製された状態機械が同一の初期状態から出発し同一の命令を同一の順序で実行すれば必ず同一の最終状態に到達するが、Lamport全順序は物理時計がずれていてもその「同一の順序」をノードごとに独立に再現させてくれる。Raft・Paxosが合意でログ順序を確定するのも結局はこの決定性を得るためであり、Lamport時計はその前世代に「合意なしでも順序を合わせる」軽量な代替を提示したという点で理論的意義が大きい。ただしLamport全順序は因果性と矛盾しないだけであり、実際の因果関係を復元はしない——互いに無関係な二つのイベントにも無理に前後を付けるため、同時性を知る必要がある競合検出には次節のベクトル時計が必要である。

4. ベクトル時計(Vector Clock)

Lamport時計の「同時性を区別できない」という弱点を解決したのがベクトル時計である。N個のプロセスからなるシステムで各プロセスは長さNの整数ベクトルを保持し、V[i]は「プロセスiでこれまで起きたと自分が知るイベント数」を意味する。規則は①内部イベント/送信時に自分の項目V[self]を1増加、②メッセージにベクトル全体を載せて送信、③受信時に項目ごとにV[k] = max(ローカル V[k], 受信 V[k])を取った後、自分の項目を1増加させる。

二つのベクトルの大小は項目ごとの比較で定義する。すべての項目でV(a) ≤ V(b)であり少なくとも一つの項目で<であればa → b(aが因果的に先行)である。どちらも相手を包含できなければ(ある項目はaが大きく別の項目はbが大きければ)、二つのイベントは同時(concurrent)と判定される。ベクトル時計はこうして「a → b ⇔ V(a) < V(b)」という双方向の同値を満たすため、Lamport時計が取り逃した同時性を正確に捉える。

規則が実際にどう同時性を捉えるかを数字で追ってみよう。プロセスA・B・Cがすべて[0,0,0]から出発する。Aがイベントを起こせば[1,0,0]、もう一度なら[2,0,0]となり、この状態を載せたメッセージをBが受け取ればBは項目ごとの最大値[2,0,0]を取った後、自分の項目を上げて[2,1,0]となる。一方、CがA・Bと無関係に独立に一度イベントを起こせば[0,0,1]である。ここでAの[2,0,0]とCの[0,0,1]を比較すると、第一項目はAが大きく第三項目はCが大きいのでどちらも相手を包含できない——規則により二つのイベントは「同時」と判定される。逆に[2,0,0]と[2,1,0]は、すべての項目で前者が後者以下であり第二項目で小さいので、前のイベントが後のイベントの原因(→)であることが機械的に確定する。このようにベクトル時計は人の判断や物理時刻なしに比較演算だけで因果・同時を区別する。

flowchart LR
    subgraph P1["プロセス A"]
      A1["e1: [1,0,0]"] --> A2["e2: [2,0,0]"]
    end
    subgraph P2["プロセス B"]
      B1["e3: [2,1,0]<br/>(Aのe2受信後)"] --> B2["e4: [2,2,0]"]
    end
    subgraph P3["プロセス C"]
      C1["e5: [0,0,1]<br/>(独立に進行)"]
    end
    A2 -->|"メッセージ"| B1
    A2 -. "e2[2,0,0] vs e5[0,0,1]:<br/>互いに包含できず → 同時(concurrent)" .- C1

この同時性判別能力は実務で決定的に重要である。Amazon Dynamo(およびその系譜のRiak・Voldemort)はベクトル時計でオブジェクトの複数バージョンを追跡し、あるバージョンが別のバージョンを因果的に包含すれば自動的に最新のものだけを残し、互いに同時のバージョンは競合(sibling)として保存してアプリケーションやユーザーが解消するよう委ねる。たとえばショッピングカートを二つの端末でオフラインで同時に修正すると、ベクトル時計がこれを「同時」と判別して二つのバージョンを両方生かしておき、併合時に二つのカートの和集合を取って入れた商品が消えないようにする。物理時刻基盤のLWWであれば一方の修正が丸ごと失われていた状況を、ベクトル時計が救うのである。

ベクトル時計の代償はメタデータの大きさである。ベクトル長がプロセス(ノード)数Nに比例するため、ノードが数千個の大規模システムでは、すべてのメッセージ・オブジェクトに付くベクトルが負担になる。さらにクライアントが直接書き込みを起こすシステムでは、ベクトル項目がノードではなくクライアント数だけ増えて無限に膨張する危険がある。そこで実務では古い項目を切り捨てるプルーニング(pruning)、項目ごとにタイムスタンプを付けて最も古いものから捨てる手法、あるいはサーバノード単位でのみベクトルを保持する折衷を用いる。下の表は二つの時計系統の違いを整理したものである。

区分	Lamportスカラ時計	ベクトル時計(Vector Clock)
データ構造	整数1個	長さN整数ベクトル
時計条件(a→b⇒C(a)<C(b))	満たす(一方向)	満たす
逆方向(C(a)<C(b)⇒a→b)	満たさない	満たす(同値)
同時性判別	不可	可能
メタデータ大きさ	O(1)	O(N)
代表的用途	全順序・相互排除	バージョン管理・競合検出

5. 比較——物理時計・Lamport・ベクトル・ハイブリッド

三つの系統の違いは「何を正確に知りたいか」と「どれだけの費用を払うか」の均衡に要約される。物理時計(+NTP/PTP)は実際の壁時計時刻を与えるためログ相関・失効(TTL)・人が読む時刻には必須だが、ノード間誤差のため因果順序の根拠としては危険である。Lamport時計はO(1)の費用で因果性と矛盾しない全順序を与えるが同時性を区別できない。ベクトル時計はO(N)の費用で同時性まで完璧に判別するが規模が大きくなるとメタデータが負担になる。すなわち費用と情報量が正比例し、システムが「順序だけ必要か、因果関係まで必要か、壁時計時刻も必要か」によって選択が分かれる。

このトレードオフを数字で感覚化するとこうなる。ノードが3個の協調システムではベクトル時計は項目3個(数十バイト)で十分だが、クライアントが各自書き込みを起こす大規模サービスでアクティブクライアントが数万なら、理論上ベクトル長も数万に達し、更新一つごとに数百KBのメタデータが付きうる。そこで実務システムはベクトルをサーバノード単位(通常数十~数百)でのみ保持するか、先に述べたプルーニングで古い項目を切ってこの費用を定数水準に抑える。一方Lamport時計は規模と無関係に項目が常に1個であるため、「同時性判別が本当に必要か」という問いへの答えがそのまま数万倍のメタデータの差を左右する。

近年は物理時刻の有用性と論理時計の因果性保証を結合したハイブリッド論理時計(HLC, Hybrid Logical Clock)が注目される。HLCは各タイムスタンプを(物理時刻成分, 論理カウンタ成分)の対で表現し、おおむね実際の壁時計に近く流れつつ(それゆえログ・TTLにそのまま使える)、因果性が要求されれば論理成分を増加させて時計条件を常に満たす。CockroachDBとMongoDB(clusterTime)がトランザクション・複製順序決定にHLCを採用した。一方Google SpannerのTrueTimeは別のアプローチで、GPS・原子時計で誤差範囲(uncertainty interval)を数ミリ秒以内に狭めた後、その不確実性の分だけ意図的に待機(commit-wait)して物理時刻のみで外部一貫性(external consistency)を達成する——すなわちハードウェアに投資して物理時計を「十分に正確に」した事例である。このように論理時計と精密物理時計は排他的な関係ではなく、要求される一貫性水準とインフラ投資の余力による選択肢である。

6. 深化——実務適用と予想出題方向

論理時計は理論にとどまらず現代の分散インフラ全般に染み込んでいる。分散データベースでは先に見たHLC(CockroachDB・MongoDB)とベクトル時計(Dynamo・Riak)がトランザクション順序と競合解決の根幹である。CRDT(協調編集器Yjs・Automerge、Redis Active-Active)はベクトル時計の変種であるバージョンベクトル(Version Vector)・ドット(dot)で、どの更新が因果的に先行するか、どの更新が同時で併合規則(add-wins等)を適用すべきかを判別する。分散トレーシング(OpenTelemetry)でもスパン間の親子因果関係を記録するアイデアが先行関係と接している。Kafka・Pulsarのようなログ基盤ブローカのオフセットも「パーティション内部のLamport式全順序」と見ることができる。

バージョンベクトルとベクトル時計の微妙な違いも実務で重要である。ベクトル時計が個々のイベントごとに因果関係を追跡するなら、バージョンベクトルは複製本(replica)単位で「どの複製本の更新まで反映したか」だけを追跡してデータオブジェクトのバージョン系譜を管理する。目的が「イベント順序」から「データバージョン収束」に変わることで項目数もイベントではなく複製本数に制限され、実用性が高まったのである。これらの変種の共通の根が1978年Lamportの先行関係であるという点が、論理時計概念の持続的な影響力を示す。

一つのよくある誤解は「NTPをよく合わせれば論理時計は不要だ」という考えである。しかしNTP・PTPがどれほど精密でも誤差範囲が0になることはなく、二つのイベントの時間間隔がその誤差より小さければ物理時刻だけでは順序を信頼できない。SpannerのTrueTimeが誤差範囲を認めてその分だけ待機(commit-wait)するのも、「物理時刻は根本的に区間であって点ではない」という事実を正面から受け入れた設計である。結局、精密物理時計にハードウェアを投資できない大多数のシステムでは、順序・因果関係の根拠を論理時計に置き、物理時刻は補助情報としてのみ使うのが安全な基本戦略になる。

情報管理技術士の観点の予想出題方向としては、①物理時計の限界と先行関係(happens-before)の定義を論じよ、②Lamport時計とベクトル時計を比較し各々の時計条件の充足可否を説明せよ、③ベクトル時計の同時性判別原理とDynamo系システムの競合解決適用を述べよ、④HLC・TrueTime等の物理・論理結合方式の必要性とトレードオフを論じよ、などが有力である。答案は「物理時計の限界 → happens-before → Lamport → Vector → ハイブリッド/実務」の順に展開すれば理論と適用を共に盛り込める。特にLamportとベクトルの違いを問うときは「時計条件の逆方向の成立可否(同時性判別)」と「メタデータ費用O(1) vs O(N)」という二つの軸を明示的に対比し、それぞれが実際のシステム(相互排除・状態機械複製 vs Dynamo・CRDT)でどう使われるかを事例で結べば答案の深みが大きく上がる。結論部では必ず「論理時計は順序・因果性を扱う道具にすぎず、合意・強一貫性を代替しない」という境界を明確にして、概念の位置を正確に規定することが高得点のポイントである。

7. 考慮事項および示唆点

順序要求の強度をまず規定せよ。システムが必要とするものが単純な全順序なのか、因果関係の保存なのか、同時性検出なのか、それとも壁時計時刻自体なのかをまず定義してこそ、時計方式を正しく選べる。要求を超える時計(例:順序だけ必要なのにベクトル時計)を導入すると、不要なメタデータ費用を常時支払うことになる。
物理時計と論理時計は役割が異なるので併行せよ。因果順序は論理時計で保証しつつ、ログ相関・TTL失効・監査・人が読むイベント時刻には物理時刻がなお必要である。HLCのように両者を一つのタイムスタンプに結合するか、物理時刻と論理カウンタを共に保存する設計が実務的に堅牢である。NTP/PTP同期は正確性の根拠ではなく観測・運用の利便として位置づけるべきである。
メタデータ膨張を寿命周期の観点で管理せよ。ベクトル・バージョンベクトルはノード・クライアント数に比例して大きくなり、古い項目・トゥームストーンが累積する。プルーニング・圧縮・複製本単位の縮約といった整理戦略と、項目増加率を追跡する観測性を設計段階で必ず含めてこそ、長期運用で性能が崩れない。
同時性は「エラー」ではなく「設計対象」である。ベクトル時計が二つの更新を同時と判別したとき、これを何で解消するか(自動併合・多値保存・ユーザー選択)は業務の意味に懸かっている。データ構造水準の順序だけでは「どの値が業務的に正しいか」に答えられないので、競合解決方針とUXを上位層で共に設計しなければならない。
実装・標準の相互運用性を事前に確認せよ。論理時計は概念は一つだが、符号化・項目管理・プルーニング方針がシステムごとに異なる。異なるデータストア・ライブラリを連携またはマイグレーションするとき、一方のベクトル・バージョンベクトル・HLC表現が他方と互換せず因果関係情報が失われうる。異種システムをつなぐパイプラインでは、時計メタデータの変換・保存経路をアーキテクチャ設計段階で明示的に確保しなければならない。
セキュリティ・信頼境界では時計自体を検証対象とせよ。論理時計は参加ノードが規則を正直に従うことを前提とする。悪意のノードがカウンタを任意に膨らませたり偽造したベクトルを載せて送ると順序・因果関係の判定が歪みうるので、信頼境界を越える区間ではタイムスタンプに対する署名・認証と異常値(outlier)検出を上位層に置かねばならない。ブロックチェーンが純粋な論理・物理時計の代わりに別途の順序合意メカニズムを置く理由も、この信頼前提の不在にある。
強一貫性が必要なら時計だけでは不足する。論理時計は順序・因果関係を追跡するだけで、複数のノードが一つの値に必ず合意するよう強制はできない。線形化可能性(linearizability)や大域不変式が必要な領域では、Paxos・Raftのような合意アルゴリズムやTrueTime式の精密時計投資と結合せねばならず、論理時計はその上で順序・競合検出を担う補完要素として配置するのが望ましい。

参考資料

Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", CACM 21(7), 1978. https://lamport.azurewebsites.net/pubs/time-clocks.pdf
DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007. https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
Kulkarni et al., "Logical Physical Clocks (HLC)", 2014. https://cse.buffalo.edu/tech-reports/2014-04.pdf
Corbett et al., "Spanner: Google's Globally-Distributed Database", OSDI 2012. https://research.google/pubs/pub39966/

一言まとめ: 論理時計は物理時刻のドリフト・誤差を信頼せず、プロセスカウンタとメッセージ交換だけでイベントの先行関係(happens-before)を追跡する道具であり、全順序を与えるLamportスカラ時計と同時性まで判別するベクトル時計、そして物理・論理を結合したHLCへと発展し、分散DB・CRDT・複製システムの順序決定と競合解決を支える。