分散データベースと時刻 - 因果順序の保証と論理時計の設計

グローバル時刻の不可能性 - なぜ分散システムで時刻は難しいのか

単一のサーバーでは、すべてのイベントに一意のタイムスタンプを付与し、発生順序を確定できます。しかし分散システムでは、物理的に離れた複数のノードが独立した時計を持ち、ネットワーク遅延が不確定であるため、「どちらのイベントが先に起きたか」を正確に判定することが原理的に困難です。

NTP で同期しても数ミリ秒〜数十ミリ秒の誤差が残ります。ノード A で 12:00:00.005 に発生したイベントとノード B で 12:00:00.008 に発生したイベントがあった場合、NTP の誤差範囲内では実際の発生順序を確定できません。この不確実性が、分散データベースのトランザクション整合性に根本的な課題をもたらします。

Lamport 時計 - 因果関係の部分順序

1978 年に Leslie Lamport が提案した論理時計は、物理時刻に依存せずにイベント間の因果関係 (happened-before 関係) を追跡する仕組みです。各ノードはカウンターを持ち、ローカルイベントごとにインクリメントし、メッセージ送信時にカウンター値を添付し、受信時に自身のカウンターと受信値の大きい方 +1 に更新します。

Lamport 時計は「イベント A がイベント B の原因であれば、A のタイムスタンプは B より小さい」ことを保証します。ただし逆は成り立ちません。タイムスタンプが小さいからといって因果関係があるとは限らず、並行 (concurrent) なイベントを区別できないという限界があります。この限界を克服するのがベクトル時計です。

ベクトル時計 - 並行性の検出

ベクトル時計は、N ノードのシステムで各ノードが N 次元のベクトル (各ノードのカウンター値) を維持する方式です。2 つのイベントのベクトルを比較し、一方が他方のすべての要素以上であれば因果関係があり、そうでなければ並行であると判定できます。Amazon の Dynamo (2007 年の論文) はベクトル時計を使って書き込みの競合を検出していました。

ベクトル時計の欠点は、ノード数に比例してベクトルのサイズが増大することです。数千ノードのシステムでは、各メッセージに数千要素のベクトルを添付する必要があり、帯域とストレージのオーバーヘッドが無視できなくなります。この問題に対処するため、実用的なシステムではベクトルの刈り込みや、後述する HLC のような代替手法が使われます。

Google Spanner の TrueTime - 物理時計の不確実性を明示する

Google の Spanner (2012 年) は、物理時計の不確実性を API レベルで明示するという独自のアプローチを取りました。TrueTime API は現在時刻を単一の値ではなく区間 [earliest, latest] として返します。GPS 受信機と原子時計を各データセンターに配備し、不確実性を通常 7 ミリ秒以下に抑えています。

Spanner のトランザクションは、コミット時に TrueTime の不確実性区間が経過するまで待機 (commit-wait) することで、外部整合性 (linearizability) を保証します。不確実性が 7 ミリ秒であれば、各トランザクションに 7 ミリ秒の待機が追加されます。この設計は、専用ハードウェア (GPS + 原子時計) への投資と引き換えに、分散トランザクションの強い整合性を実現しています。

Hybrid Logical Clock - 実用的な妥協点

Hybrid Logical Clock (HLC) は、物理時計と論理時計を組み合わせた実用的な手法です。タイムスタンプは (物理時刻, 論理カウンター) のペアで構成され、通常は物理時刻が支配的ですが、同一物理時刻内のイベント順序は論理カウンターで区別されます。CockroachDB はこの HLC を採用し、専用ハードウェアなしで強い整合性を提供しています。

HLC の利点は、NTP 同期された一般的なサーバーで動作し、タイムスタンプが人間可読な物理時刻に近い値を保つことです。Spanner の TrueTime ほどの厳密さはありませんが、NTP の誤差範囲内で実用的な整合性を提供し、不確実性区間内の競合はリトライで解決します。多くの分散データベースにとって、この妥協点が最も現実的な選択肢です。