# 外部一貫性 ## 定義 外部一貫性(external consistency)とは、分散トランザクションにおける一貫性の保証のうち最も強いもので、**トランザクション T1 のコミットがトランザクション T2 の開始より実時間で先行するならば、T1 のコミットタイムスタンプは T2 のコミットタイムスタンプより小さい**ことを保証する性質である。 形式的には、コミットイベント `e1^commit` と T2 の開始イベント `e2^start` について: ``` tabs(e1^commit) < tabs(e2^start) ⟹ s1 < s2 ``` ここで `tabs(e)` はイベント e の絶対時刻、`si` はトランザクション Ti のコミットタイムスタンプを表す。 外部一貫性は線形化可能性(linearizability; Herlihy and Wing, 1990)と等価である。これはシリアライザビリティより強く、セッション一貫性・強い一貫性とも異なる。通常の「直列化可能性(serializability)」はトランザクションの実時間順序を保証しないが、外部一貫性はそれを保証する。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) ## 横断的知見 - **外部一貫性 vs 単一キー線形化可能性**: Spanner は commit wait で**厳密直列化可能性(strict serializability = 外部一貫性)**を実現する。CockroachDB は HLC + 不確実性区間 + Read Refresh で**単一キー線形化可能性のみ**を保証する。異なるゲートウェイノードを経由する因果依存トランザクションでは、スキューが max_offset を超えると陳腐化読み取りが起こりうる。外部一貫性には commit wait(コスト: ≥ 2ε ≈ 8ms の遅延)か専用ハードウェアが必要。(Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §4.2〜4.3, [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) - **外部一貫性が実際に問題になるケース**: CRDB 論文は「外部低レイテンシ通信チャネルがある場合を除き、多くのアプリケーションで外部一貫性の欠如は問題にならない」と述べる。一方、金融取引・分散ロックなど実時間因果関係が厳格に要求されるシステムでは Spanner 相当の保証が必要になりうる。(Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §4.2) - **クロックスキュー超過時の動作の違い**: Spanner は commit wait により、スキューを超えてもタイムスタンプ順序を保証し続ける。CRDB は直列化可能分離はリース保護機構(リース区間チェック + Raft ログシーケンス番号チェック)で維持されるが、単一キー線形化可能性はスキューが max_offset を超えると保証できなくなる。CRDB はノードが 80% 超過を検出すると自己終了してリスクを軽減する。(Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §4.3) ## 未解決の問い - ~~外部一貫性を保証しつつレイテンシを下げる手法として、Spanner の commit wait 以外にどのようなアプローチが提案されているか?~~ → CRDB が HLC + Read Refresh で commit wait を排除するアプローチを提示したが、保証レベルが下がる(単一キー線形化可能性)。保証を落とさずに commit wait を排除できるか? - GPS・原子時計を持たない環境(クラウド VM 等)での外部一貫性保証はどう近似されるか? AWS Time Sync Service (≤ 100µs) のような精度向上で実質的に外部一貫性に近づけるか? - 外部一貫性と因果一貫性(causal consistency)の実用上のトレードオフはどの文献で整理されているか? - 「単一キー線形化可能性では不十分で外部一貫性が必要」というケースの体系的な分類は存在するか? ## Spanner における実現方法 [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]は [[TrueTime]] を用いた **commit wait** によって外部一貫性を実現する。 **Commit Wait の論理**: ``` s1 < tabs(e1^commit) … commit wait により保証 tabs(e1^commit) < tabs(e2^start) … 仮定(T1 が T2 の開始前にコミット) tabs(e2^start) ≤ tabs(e2^server) … 因果関係 tabs(e2^server) ≤ s2 … Start ルール(s2 ≥ TT.now().latest) ∴ s1 < s2 … 推移律 ``` コーディネーターリーダーが `TT.after(s)` が真になるまでコミットを公開しないことで、`s < tabs(e^commit)` が保証される。期待待機時間は少なくとも 2ε(ε は TrueTime の誤差上界、通常 4〜7ms)。 ## 関連 - ソース: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] / [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] - 概念: [[TrueTime]] / [[ハイブリッド論理クロック]] / [[分散トランザクション]] / [[地理分散SQLデータベース]] - エンティティ: [[James C. Corbett]] / [[Jeffrey Dean]] / [[Google]] / [[CockroachDB]] ## 出典 - [[@2013__TOCS__Spanner - Google's Globally Distributed Database]](TOCS 2013 / OSDI 2012) - [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]](SIGMOD 2020 §4) - Gifford 1982 — external consistency の概念の初出 - Herlihy and Wing 1990 — linearizability の定義