# 外部一貫性 ## 定義 外部一貫性(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) - **本ページが扱う「外部一貫性」は、DDIA 2E が定義する一般的な線形化可能性のトランザクション拡張である**: DDIA 2E 第10章は線形化可能性を「レジスタ(単一キー)の読み書きが1つのコピーであるかのように振る舞う」という単一操作単位の一般的な一貫性モデルとして定義し、external consistency をその別名の1つとして挙げる。本ページがこれまで蓄積してきた Spanner/CockroachDB の「コミットタイムスタンプの実時間順序保証」という定義は、この一般的な線形化可能性を複数キーにまたがるトランザクションのコミット時点に適用したものであり、DDIA が示す Attiya and Welch の不可能性結果(線形化可能な読み書きの応答時間はネットワーク遅延の不確実性に本質的に比例する)は、Spanner の commit wait コスト(≥2ε)や CockroachDB が commit wait を回避するために単一キー限定に妥協した設計判断の理論的根拠を与える。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Linearizability", "The Cost of Linearizability", [[線形化可能性]]) - **詳説 データベース(2019年原著)は Spanner 原論文の外部一貫性の定義を、後発の DDIA(2026年版)と同一の因果構造で独立に要約する**: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]]は「T1 が T2 の開始前にコミットされた場合、T1 のタイムスタンプは T2 のタイムスタンプより小さくなる」と述べ、これは本ページが既に記録する Spanner 原論文の形式的定義(`tabs(e1^commit) < tabs(e2^start) ⟹ s1 < s2`)をそのまま踏襲する。DDIA(2026)が示す一般的な線形化可能性の定義とあわせ、原論文発表(2012/2013)・教科書(2019 詳説 データベース)・教科書(2026 DDIA)という 3 世代にわたって外部一貫性の因果構造の理解が一貫していることを示す。詳説 データベースは「外部一貫性は線形化可能性と同等のリアルタイム特性を持つ」と明記しており、本ページが既に記録する Herlihy and Wing の同値関係の理解とも一致する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.5, [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) ## 未解決の問い - ~~外部一貫性を保証しつつレイテンシを下げる手法として、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]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] - 概念: [[TrueTime]] / [[ハイブリッド論理クロック]] / [[分散トランザクション]] / [[地理分散SQLデータベース]] / [[線形化可能性]] - エンティティ: [[James C. Corbett]] / [[Jeffrey Dean]] / [[Google]] / [[CockroachDB]] / [[Spanner]] ## 出典 - [[@2013__TOCS__Spanner - Google's Globally Distributed Database]](TOCS 2013 / OSDI 2012) - [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]](SIGMOD 2020 §4) - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]](線形化可能性の一般定義とコストの理論的根拠) - [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]](§13.5 Spanner の外部一貫性の独立要約) - Gifford 1982 — external consistency の概念の初出 - Herlihy and Wing 1990 — linearizability の定義