# 分散コンセンサス回避 ## 定義 分散コンセンサス回避（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]]) ## 横断的知見 - **「分散コンセンサスの回避」は汎用性のトレードオフ**: 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]]) ## 未解決の問い - クォーラムセット + エポックの非ブロッキング性は理論的に証明されているが、多数の同時障害（E と F と G が同時に失われる等）での挙動は論文では限定的にしか述べられていない。実際の 64TB（38,400 セグメント）スケールでのメンバーシップ変更嵐（membership change storm）はどう処理されるか？ - PGMRPL が非常に遅いレプリカ（ネットワーク断等）で固着した場合、GC ポイントが前進できなくなりストレージが積み上がる。これに対する実装上の対処は公開されていない。 - カルビン（[11] = Calvin）のような「決定論的トランザクション順序」アプローチとの比較: Calvin も 2PC を回避するが、Aurora とは直交する設計。それぞれが優位な workload 特性は何か？ ## 関連 - [[クォーラムベースレプリケーション]] — Aurora のクォーラム設計の詳細（V=6, Vw=4, Vr=3, フル/テール分割） - [[Write-Ahead Logging (WAL)]] — SCL/PGCL/VCL は LSN/SCN の自然な拡張であり WAL の分散延長 - [[クラッシュリカバリ]] — コンセンサス回避とエポックフェンシングを組み合わせたリカバリ - [[コンピュートストレージ分離]] — コンセンサス回避が可能な前提条件（ストレージが汎用でなく Aurora 専用） - [[分散コンセンサス]] — 回避の対象となる汎用合意アルゴリズム（Raft・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 のジョイントコンセンサスとの比較対象）