# 分散トランザクション ## 定義 分散トランザクションとは、複数のデータパーティション・サーバー・データセンターにまたがる操作を ACID 特性(原子性・一貫性・独立性・永続性)で実行する仕組みである。単一ノードのトランザクションと異なり、参加ノード間の協調(コミットプロトコル、ロック管理)が必要になる。 主要な実現手法として二相コミット(2PC: Two-Phase Commit)が広く使われるが、コーディネーター障害時の可用性低下やレイテンシ増大が課題となる。Paxos などの複製ステートマシン上に 2PC を組み合わせることで可用性を改善できる。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]) ## 横断的知見 - **楽観的 vs 悲観的トランザクションの使い分け**: F1 はデフォルトで楽観的トランザクションを採用する。楽観的は「ロックを保持しない」「サーバー側でリトライ透過化」「サーバー障害後に別サーバーへ切り替え可能」などの利点がある一方、高競合シナリオ(共有カウンタ等)では失敗率が高くなる。Spanner 論文は悲観的(二相ロック + wound-wait)を基盤として提供し、F1 がその上に楽観的レイヤーを追加した。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]], [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]]) - **2PC 参加者数とレイテンシの実測**: Spanner 実測では参加者 50 まで mean 33.8ms / p99 62.4ms、100 参加者から顕著に増加(mean 55.9ms)。F1 では 1,000 行挿入でグローバルインデックスが 100 以上の 2PC 参加者を生み出す可能性があり、これが実用上のスキーマ設計制約になる。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] Table IV, [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]] §3.3) - **スナップショット読み取りの戦略的活用**: F1 の SQL クエリと MapReduce は**スナップショットトランザクション**をデフォルトで使用する。Spanner の global safe timestamp(現時刻より 5-10 秒古い)に読み取ることでロックフリー・任意のレプリカで実行できる。これにより OLTP と OLAP ワークロードを分離し、読み取り専用レプリカを OLAP に活用する。(Source: [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]] §5, §9) - **グローバルインデックス一貫性のコスト**: 分散トランザクション上で globally-consistent なセカンダリインデックスを維持するには、インデックス更新のたびに 2PC 参加者が増える。Megastore は非同期インデックス(一貫性を緩和)で解決、F1 はグローバルインデックスを最小限にして一貫性を優先した。(Source: [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]] §3.3) - **2PC コーディネーター障害と lead shard パターン**: Spanner は Paxos グループ上に 2PC を載せてコーディネーター(コーディネーターは Paxos グループ)の高可用性を確保する。Aurora Limitless は別解として「ステートレスなルータにコーディネーターを置かず、ステートフルな lead shard にトランザクション状態を永続化する」設計を採用する。ルータは standby を持たなくてよく、コスト削減になる。ルータ障害時も lead shard の状態を問い合わせて in-flight トランザクションを解決できる。(Source: [[@2026__SIGMOD Companion__Aurora PostgreSQL Limitless Database - Building a Highly Scalable OLTP Database]] §5.4) - **時刻ベース MVCC によるクロックスキュー対処**: Spanner は TrueTime の commit wait で外部一貫性を保証する。Aurora Limitless は HLC(Hybrid Logical Clock)でシャードの論理クロックを読み取り時刻に追いつかせ、従来方式のような余分な待機なしで整合的な読み取りを実現する。commit wait は書き込みコミット時のみに限定され、ストレージ書き込みと並行実行して影響を最小化する。(Source: [[@2026__SIGMOD Companion__Aurora PostgreSQL Limitless Database - Building a Highly Scalable OLTP Database]] §5.5, §5.6 vs [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] §4.2.2) - **commit wait を回避する楽観的アプローチ**: CockroachDB は HLC + **Read Refresh**(楽観的再検証)で commit wait を完全に回避する。トランザクションのタイムスタンプを進める必要が生じたとき、過去の読み取り集合を再スキャンしタイムスタンプ区間内に更新がないことを確認する。成功すれば新タイムスタンプで続行、失敗はリトライ。低コンテンション YCSB では Spanner を大幅に上回るスループット・低レイテンシを実現したが、高コンテンション(Workload A)ではスケールしない。(Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §3.4, §6.3) - **Parallel Commits: 2PC の追加ラウンドを staging で回避**: CRDB の Parallel Commits は「staging」トランザクションステータスを使い、コミットステータスの複製と全 write intent のレプリケーション確認を並列化する。これにより通常 2PC で必要な追加コンセンサスラウンドを不要にし、セカンダリインデックス付きで 72% スループット向上・47% レイテンシ削減を実現。TLA+ で安全性を形式検証済み。(Source: [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] §3.1) ## 未解決の問い - ~~Calvin・Percolator・CockroachDB など Spanner の同時代・後発の分散トランザクション実装と比べて、commit wait によるレイテンシ増大はどの程度の実用上の問題になっているか?~~ → CRDB SIGMOD 2020 §6.3 で YCSB ベンチマークにより実測。commit wait に起因するレイテンシが Spanner で顕著 - グローバルインデックスのスケーラビリティを一貫性を犠牲にせずに解決する汎用的なアプローチは存在するか? F1 は「最小化」で対処し CRDB は F1 方式オンラインスキーマ変更で対処したが、より原理的な解法はあるか? - 楽観的トランザクションが有利な条件(低競合・長い読み取りフェーズ)と悲観的が有利な条件(高競合カウンタ)の境界を、事前にワークロード分析で予測できるか? CRDB の高コンテンション YCSB Workload A でのスケール不良はこの問いを実証する - CRDB が悲観的読み取りロックを追加した後(v20.1 以降)、高コンテンション環境での性能はどう変わったか? ## Spanner における実現方法 [[@2013__TOCS__Spanner - Google's Globally Distributed Database]]は次の 3 種類の操作を提供する: | 操作種別 | 並行制御 | 実行レプリカ | |---|---|---| | 読み書きトランザクション(RW) | 悲観的(二相ロック + wound-wait) | リーダーのみ | | スナップショットトランザクション(RO) | ロックフリー | リーダーまたは十分更新済みのレプリカ | | スナップショット読み取り | ロックフリー | 十分更新済みのレプリカ | **読み書きトランザクションのフロー**: 1. クライアントが各 Paxos グループのリーダーに読み取りを発行(wound-wait によるデッドロック回避) 2. コミット時にコーディネーターグループを選択し、2PC を開始 3. 非コーディネーター参加者は準備タイムスタンプ(`s_prepare`)を Paxos で記録し、コーディネーターに通知 4. コーディネーターはすべての準備タイムスタンプ以上、かつ `TT.now().latest` 以上のコミットタイムスタンプ `s` を選択 5. `TT.after(s)` が真になるまで commit wait(待機時間 ≥ 2ε) 6. コミット通知後、全参加者が同一タイムスタンプで適用してロックを解放 2PC のスケーラビリティ実測: 参加者 50 まで mean 33.8ms / p99 62.4ms。100 参加者から顕著に増加(mean 55.9ms)。(Source: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] Table IV) **セーフタイム(tsafe)**: - 各レプリカが持つ「このタイムスタンプ以下の読み取りは確実に最新」という上限値 - `tsafe = min(tPaxos_safe, tTM_safe)` — Paxos セーフタイムと、準備中トランザクションが存在しない場合の ∞ との min **スナップショットトランザクションの利点**: - ロックなしで実行できるため、インフライトの書き込みをブロックしない - コミット時刻が確定した後は、どのレプリカでも実行可能 - Spanner では特定タイムスタンプでのデータベース全体の一貫スナップショット読み取りが可能(バックアップ・MapReduce に活用) ## F1 における分散トランザクションの実装 [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]]は Spanner の分散トランザクション基盤の上に SQL レイヤーを構築し、3 種類のトランザクションモデルを提供する: | 種別 | ロック | レイテンシ | 用途 | |---|---|---|---| | スナップショット | なし | 最低(ローカルレプリカ) | SQL クエリ・MapReduce(デフォルト) | | 悲観的 | Spanner 二相ロック(サーバー固定) | 中 | 高競合シナリオ | | 楽観的 | なし(読み取り)→短い書き込み | 可変(競合失敗あり) | デフォルト ORM | 楽観的トランザクションは各行に hidden lock column(最終更新タイムスタンプ)を持ち、コミット時に再読み取りして競合を検出する。 ## 関連 - ソース: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]], [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]], [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]] - 概念: [[外部一貫性]] / [[TrueTime]] / [[ハイブリッド論理クロック]] / [[地理分散SQLデータベース]] / [[分散SQLデータベース]] - エンティティ: [[Google]] / [[James C. Corbett]] / [[Jeffrey Dean]] / [[Jeff Shute]] / [[CockroachDB]] / [[Cockroach Labs]] ## 出典 - [[@2013__TOCS__Spanner - Google's Globally Distributed Database]](TOCS 2013 / OSDI 2012) - [[@2013__VLDB__F1 - A Distributed SQL Database That Scales]](VLDB 2013) - [[@2020__SIGMOD__CockroachDB - The Resilient Geo-Distributed SQL Database]](SIGMOD 2020)