# 分散コンセンサス回避 ## 定義 分散コンセンサス回避（Avoiding Distributed Consensus）とは、2PC（Two-Phase Commit）・Paxos・Raft 等の分散合意アルゴリズムを使わずに、分散ストレージシステムにおける書き込みの耐久性保証・コミット処理・メンバーシップ管理を達成する設計アプローチである。 分散コンセンサスは汎用的な合意メカニズムだが、リレーショナルデータベースの高スループット OLTP にとっては過剰な仕組みを持つ場合がある。「データベースは本来状態の管理者である」という観点から、ローカルな一時的状態と単調増加する整序（LSN）、エポックベースのフェンシングを組み合わせることで、多くの操作からコンセンサスを除去できる。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) Aurora の基本戦略: **「LSN 空間の単一割り当て者（データベースインスタンス）」という不変条件を利用する**。LSN は常に前進するのみ（never go back）であり、ストレージ層ではこの単調性を利用してローカルな一貫性ポイントを安全に計算できる。 ## コンセンサス回避の 3 領域 ### 1. 書き込みとコミット（SCL/PGCL/VCL 階層） 従来の分散コミット（2PC・Paxos Commit）では、すべての参加者が「コミット可能」に票を投じなければならない。Aurora はこれを以下で置き換える: - **SCL**（Segment Complete LSN）: 各ストレージノードが自セグメントチェインの連続した上限を局所計算。欠損検出・ゴシップ補充に使用。コンセンサス不要。 - **PGCL**（Protection Group Complete LSN）: DB インスタンスが 4/6 以上から SCL を受け取った最高水位を局所集計。コンセンサス不要。 - **VCL**（Volume Complete LSN）: 全 PG の PGCL が揃った最高水位。コミット応答の閾値。 - **VDL**（Volume Durable LSN）: VCL 以下の最後の Mini-Transaction 完了 LSN。レプリカの読み込みビューアンカー。 **コミット処理**: SCN（System Commit Number = コミット Redo LSN）が VCL を下回ることを確認するだけでコミット応答を返せる。2PC のラウンドトリップ・ロック・準備フェーズが不要。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) **なぜ可能か**: ストレージノードは書き込みを拒否できない（投票権がない）。ロック・制約・トランザクション管理はすべてデータベース層で解決済みでストレージ層に届く時点では確定している。ストレージノードはべき等な操作をローカル状態だけで実行できる。 ### 2. 読み込みのクォーラム増幅回避 通常のクォーラムシステムでは読み込みに Vr 件（Aurora では最低 3 件）の I/O が必要だが、Aurora はこれを回避する: VCL 管理により、DB インスタンスはどのセグメントが最新耐久バージョンを持つかを追跡している。読み込みは**1 セグメントへの直接要求**として発行し、ネットワーク増幅なしに最新データを取得する。 応答時間追跡による遅延対策: 遅延時は並行してバックアップ読み込みを発行し先着を採用する。ネットワーク I/O を増幅させずにテールレイテンシを制御。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) ### 3. メンバーシップ変更の非ブロッキング化（クォーラムセット） 従来の Paxos ベースのメンバーシップ変更は、変更中に I/O ストールが発生し、追加障害に非耐性で、フェンスアウトしたメンバーの再受け入れが困難。 **クォーラムセット**: Boolean 論理で表現した重複クォーラムの集合。F→G の置き換えを例に: - 直接遷移ではなく「ABCDEF と ABCDEG の両方を同時に満たすクォーラム」を中間状態として経由 - 書き込みは ABCD に送ればどちらのセットも満たす → I/O ストールなし - F が復帰すれば ABCDEF に戻れる（**可逆性**） - G が水和完了すれば ABCDEG のみに収束 **エポック**: メンバーシップエポック・ボリュームエポックの 2 種類。エポックインクリメントは対象 PG の書き込みクォーラムへの単一書き込みで完了。古いエポックからのリクエストは拒否（「鍵を取り替える」）。リース待ちが不要。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) ### 4. 不変条件の合流可能性による回避(RAMP・調整の回避) [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]]は、Aurora とは異なる回避戦略として「調整の回避(coordination avoidance)」を紹介する。**Invariant Confluence(I-Confluence)** とは、不変条件を保ちながら分岐した2つのデータベース状態を1つの有効な最終状態にマージできる特性である。操作がこの性質を持てば、追加の調整なしで実行できる。回避を成立させるシステムモデルは以下4特性を満たす必要がある: グローバルな有効性(マージ後・分岐後のいずれの状態でも不変条件を満たす)、可用性(コミット不変条件違反時のみ中断)、収束性(通信が十分あれば同じ状態に収束)、調整からの解放(ローカル実行が他ノードの状態から独立)。 実装例の **RAMP(Read-Atomic Multi-Partition)トランザクション**は、マルチバージョン同時実行制御と実行中操作のメタデータを用いて、分散ロックなしにアトミックな書き込みの可視性を提供する。同期化の独立性(他クライアントを停止・中断させない)とパーティションの独立性(無関係なパーティションに接続しない)を特徴とし、Read Atomic 分離レベル(実行中・未コミット・中断済みトランザクションの変更を一切見ない)を導入する。書き込みの適用・可視化には準備(可視化しない)／コミット・中断(公開)の2フェーズを使うが、これは Aurora のようにストレージノードから投票権を奪うのではなく、ツーフェーズコミット構造自体は残しつつ、その対象をロック取得ではなく「メタデータの伝播」に限定することで軽量化している。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.8) ## 横断的知見 - **RAMP と Aurora は「回避する対象」が異なる2つのコンセンサス回避パターンである**: Aurora の回避(§1-3節参照)は「ストレージノードに投票権を与えない」という不変条件によって 2PC・Paxos の合意ラウンド自体を不要にするのに対し、RAMP は 2PC 構造(準備／コミット・中断)自体は保持しつつ、その対象を「データのロック」から「書き込みメタデータの伝播」に縮小することで、クライアント間の相互ブロッキングだけを排除する。前者は「合意ラウンドの排除」、後者は「合意ラウンドが引き起こす相互待機の排除」という異なるレベルの回避であり、いずれも I-Confluence 的な発想(状態のマージ可能性を設計で保証する)を暗黙に前提とする点で共通する。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]], [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.8) - **Calvin の決定論的順序も広義のコンセンサス回避の一系統である**: [[Calvin]](→ [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.4)はシーケンサでバッチ全体の実行順序に一度だけ合意し、以後の実行フェーズではノード間通信を一切必要としない。これは Aurora が「LSN の単一割り当て者」という不変条件でコンセンサスを回避するのとは異なり、「合意のタイミングを実行前に前倒しする」ことで実行時の調整コストを消す戦略である。従来「未解決の問い」に挙げていた Calvin と Aurora の比較は、本章の ingest によって「前者は合意を前倒しする、後者は合意そのものを不要にする」という異なる軸の回避戦略だと整理できる。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]], [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.4) - **「分散コンセンサスの回避」は汎用性のトレードオフ**: 2PC/Paxos が汎用合意を提供する一方、Aurora のアプローチはシングルライターの OLTP という制約（LSN 単調性・書き込み拒否なし）に特化して成立する。マルチライター OLTP（複数ノードが独立してトランザクションを発行）では同じアプローチは直接適用できない。Aurora 2018 は「ライター間オーダリング + ジャーナル」での拡張可能性を示唆するが、詳細は公開されていない。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **コンセンサス回避のコアは「状態の境界を明確にすること」**: Aurora のアプローチが成立する理由は、「ストレージノードは書き込みを拒否しない」「LSN は単調増加」「読み込みに必要なデータの所在はインスタンスが追跡する」という 3 つの明確な境界設定による。分散コンセンサスの多くは「どのノードが最新値を持つか分からない」「誰かが拒否するかもしれない」という不確実性への対処である。不確実性を設計で除去できれば、コンセンサスは不要になる。 - **Raft のメンバーシップ変更との対比**: Raft のジョイントコンセンサス（Cold,new）もメンバーシップ変更中に通常処理を継続できる非ブロッキング設計を提供する。Aurora のクォーラムセット + エポックは Raft のジョイントコンセンサスよりも可逆性（古い設定への復帰）が高く、ストレージ特化（書き込み拒否なし）の制約下でよりシンプルに実装できる。汎用性（Raft）vs 特化（Aurora）の比較として捉えられる。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]], [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **単一書き込み者(classic Aurora)から複数書き込み者(Aurora DSQL)への回避戦略の一般化**: classic Aurora のコンセンサス回避は「LSN の単一割り当て者(DB インスタンス)」という不変条件、すなわち単一ライターに強く依存する。Aurora DSQL はこの前提を持たない(複数 Query Processor が並行して書き込む)にもかかわらず、「代表 Adjudicator の単一 Journal への単一アトミック書き込み」という別の不変条件でクロスノード合意を回避する。2018 年の Aurora 論文が示唆していた「ライター間オーダリング + ジャーナル」拡張の具体的な実現例が、8 年後の Aurora DSQL の Adjudicator + Journal 設計であると解釈できる。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]], [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]] §5.1, §5.1.1) - **「投票のアトミック性」と「コミットのアトミック性」を分離する新しい回避パターン**: classic Aurora はストレージノードに投票権を与えない(拒否できない)ことでコンセンサスを不要にするのに対し、Aurora DSQL の複数 Adjudicator 間プロトコルは Adjudicator に投票権を残しつつ、「投票フェーズ」自体は非アトミックな「コミット候補への合意」として扱い、実際のアトミック性は代表 Adjudicator の単一 Journal 書き込みだけに閉じ込める。フォールトトレラントなコーディネータやクロス Journal 協調が不要になる点は classic Aurora と同じ効果だが、到達方法が異なる。(Source: [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]] §5.1.1) - **Aurora のクォーラム設計(V=6, Vw=4, Vr=3)は「回避」だが、Flexible Paxos の Q1+Q2>N は「一般化」であり、両者は同じ数学的洞察の異なる応用である**: 本ページが記録する Aurora のクォーラム(§2節参照)は Vw + Vr > V の関係を保ちながら、読み取りをクォーラム収集なしの1セグメント直接要求に置き換えることで増幅を回避する。これに対し [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.7 が示す Flexible Paxos は、合意アルゴリズム自体のクォーラムを「過半数」から「$Q_1 + Q_2 > N$ を満たす任意の空でない集合」へ一般化し、第2フェーズ(Accept)のクォーラム $Q_2$ を縮小する代わりに第1フェーズ(リーダー選出)のクォーラム $Q_1$ を拡大する設計を許す。Aurora はこの一般化された関係(重複するノード集合が少なくとも1つ存在すればよい)を、合意アルゴリズムそのものではなく読み取り/書き込みクォーラムの設計に転用したものと解釈でき、「コンセンサスの回避」に見える Aurora の設計判断が、実は合意理論(クォーラムの重複性)の枠内にとどまっていることを示す。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.7, [[クォーラムベースレプリケーション]]) ## 未解決の問い - クォーラムセット + エポックの非ブロッキング性は理論的に証明されているが、多数の同時障害（E と F と G が同時に失われる等）での挙動は論文では限定的にしか述べられていない。実際の 64TB（38,400 セグメント）スケールでのメンバーシップ変更嵐（membership change storm）はどう処理されるか？ - PGMRPL が非常に遅いレプリカ（ネットワーク断等）で固着した場合、GC ポイントが前進できなくなりストレージが積み上がる。これに対する実装上の対処は公開されていない。 - ~~カルビン（[11] = Calvin）のような「決定論的トランザクション順序」アプローチとの比較: Calvin も 2PC を回避するが、Aurora とは直交する設計。それぞれが優位な workload 特性は何か？~~ → [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] の ingest により Calvin の設計(シーケンサでの事前合意)は判明した。ただし両者を同一ワークロードで比較した定量データはまだない: Calvin は read/write set が事前確定するワークロードに強く、Aurora は単一ライターの OLTP に強いという定性的な棲み分けまでしか言えない。 - RAMP の Read Atomic 分離レベルは、Aurora のコンセンサス回避が前提とする「単一 LSN 割り当て者」を持たないマルチライター環境でも成立する。RAMP のアプローチを Aurora のような単一ライターアーキテクチャに逆輸入する意義はあるか、それとも単一ライター前提のほうが常に効率的か。 - I-Confluence(不変条件の合流可能性)は RAMP の理論的基盤だが、詳説 データベース13章はどのような不変条件が実際に I-Confluent であるかの判定手続きを示さない。実務でこの判定はどう行われているか(COPS・Bloom 等の関連システムの文献を追加調査すべきか)。 - Aurora DSQL の代表 Adjudicator 選出プロトコルは、代表自身が障害を起こした場合(投票済みだが Journal 書き込み前 vs 書き込み後)で挙動が変わると論文は述べるが、大規模障害(複数 Adjudicator 同時喪失)下でのデッドロック率・リトライ嵐は定量化されていない。classic Aurora のクォーラムセット + エポックのような形式的な非ブロッキング性の証明は Aurora DSQL には提示されていない。 ## 関連 - [[クォーラムベースレプリケーション]] — Aurora のクォーラム設計の詳細（V=6, Vw=4, Vr=3, フル/テール分割） - [[Write-Ahead Logging (WAL)]] — SCL/PGCL/VCL は LSN/SCN の自然な拡張であり WAL の分散延長 - [[クラッシュリカバリ]] — コンセンサス回避とエポックフェンシングを組み合わせたリカバリ - [[コンピュートストレージ分離]] — コンセンサス回避が可能な前提条件（ストレージが汎用でなく Aurora 専用） - [[分散コンセンサス]] — 回避の対象となる汎用合意アルゴリズム（Raft・Paxos 等） - [[Aurora DSQL]] — 複数書き込み者環境での回避戦略の一般化事例 - [[分散トランザクション]] — RAMP・Calvin による回避と 2PC・3PC の対比 - [[Calvin]] — シーケンサによる事前合意でコンセンサスを回避する系統 - [[分散合意プロトコル]] — 回避の対象となる汎用合意アルゴリズムのクォーラム一般化(Flexible Paxos) ## 出典 - [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]（SCL/PGCL/VCL 階層・クォーラムセット・エポック・PGMRPL の詳細） - [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]（コンセンサス回避の全体的動機と高レベル設計） - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（Raft のジョイントコンセンサスとの比較対象） - [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]]（Adjudicator + Journal による複数書き込み者向けコンセンサス回避） - [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]]（I-Confluence・RAMP トランザクション・Calvin のシーケンサ設計） - [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.3.7(Flexible Paxos のクォーラム一般化 $Q_1+Q_2>N$)