クォーラムベースレプリケーション

# クォーラムベースレプリケーション ## 定義クォーラムベースレプリケーション（Quorum-Based Replication）は、レプリケートされたデータシステムにおいて、読み込み・書き込み操作のそれぞれに一定数以上のレプリカからの承認（クォーラム）を要求することで、整合性と可用性のトレードオフを制御する手法である。データの V コピーが存在する場合、書き込みクォーラム Vw 票と読み込みクォーラム Vr 票を設定し、(1) Vr + Vw > V（読み込みが最新書き込みを必ずカバー）、(2) Vw > V/2（書き込み間の競合を防止）の 2 条件を満たす組み合わせを選ぶ。(Source: [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) 一般的な 3 コピー構成（V=3, Vw=2, Vr=2）は単一ノード障害に耐えるが、クラウド規模の相関障害（AZ 全体の喪失）には不十分。Aurora は V=6, Vw=4, Vr=3 の設計で AZ+1 障害耐性を実現する（各 AZ に 2 コピーずつ配置）。(Source: [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) ## ウィットネスレプリカクォーラムによる読み取りの一貫性は可用性を向上させるが、レプリケーションファクタ分だけデータのコピーを格納するためストレージコストが増大する。**ウィットネスレプリカ**は、レプリカを実際にデータレコードを保持する**コピーレプリカ**と、通常は書き込み操作が行われた事実のみを記録する**ウィットネスレプリカ**に分割することでこのコストを削減する手法である。コピーレプリカの障害・タイムアウト時には、ウィットネスレプリカを一時的に昇格させてレコードを格納し、コピーレプリカの回復後に修復できる。n 個のコピーレプリカと m 個のウィットネスレプリカがあると、(1) 読み書き操作を過半数(N/2+1)で実行する、(2) クォラム中の少なくとも1つのレプリカが必ずコピーレプリカである、という2条件のもとで n + m 個のコピーがあるのと同じ可用性が保証される。Spanner や Apache Cassandra に実装例がある。(Source: [[@2021__OReillyJapan__詳説データベース - Chapter 11 レプリケーションと一貫性]] §11.9) ## 横断的知見 - **AZ 障害は相関障害であり非相関の個別ノード障害とは本質的に異なる扱いが必要**: 個別ノード障害は独立だが、AZ 障害は同一 AZ 内の全ディスク・ノードを同時に失う。したがって「3 コピー 2/3 クォーラム」は AZ 障害 + 別 AZ の独立障害が同時発生した場合にクォーラムを失う。Aurora の 6 コピー 4/6 設計はこの組み合わせを明示的に考慮した設計であり、セグメント修復 MTTR（10 秒）と組み合わせることで実用的な耐久性を実現する。クォーラム設計の前提をクラウド環境の障害モデルに合わせることが重要。(Source: [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) - **クォーラムセット（Boolean 論理の重複クォーラム）によりメンバーシップ変更を非ブロッキック・リバーシブルに実現できる**: 従来の単一クォーラムセットでは、F を G で置き換える場合に ABCDEF→ABCDEG の直接遷移（Paxos Membership Change 等）が必要で I/O ストールが生じる。Aurora 2018([[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]])はクォーラムセットを Boolean 論理で組み合わせ、中間状態（ABCDEF と ABCDEG の両方が有効）を経由する。ABCD への書き込みが両方のセットを満たすため I/O が止まらず、F が復帰すれば ABCDEF に戻れる。エポックインクリメント 1 回で移行・フェンシング・再受け入れを処理できる。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **フルセグメント 3 本 + テールセグメント 3 本の非対称設計でコスト増幅を 6× から約 3× に削減できる**: 6 ウェイレプリケーションではデータブロックを 6 コピー保持することになるが、Aurora 2018 は各 PG をデータブロックを持つ「フルセグメント」3 本と Redo のみの「テールセグメント」3 本に分ける。書き込みクォーラムは 4/6 の任意セグメントで、読み込みはフルセグメントから直接行う。Redo ログの増幅は 6× だが、データブロックの増幅は約 3× に抑えられる。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **イレイジャーコーディングを「可用性」ではなく「レイテンシ分散」の最適化として使う設計**: classic Aurora の V=6, Vw=4, Vr=3 クォーラムはコピーそのものを複製するのに対し、Aurora DSQL は Journal 間で 2-of-3 のイレイジャーコード(単純な XOR)を適用し、任意の 2 つの Journal から復元可能にする。論文は「イレイジャーコーディングは可用性のための技術として広く使われるが、レイテンシのための技術としてはもっと広く使われるべきだ」と位置づけており、base availability 99.99% を k=2, M=3 の設定で 7.5 桁以上の可用性に引き上げられると報告する。クォーラムによる複製(コピーの冗長性)とイレイジャーコーディング(演算による冗長性)は、いずれも「1 ノードの不可用性を許容しつつテールレイテンシを制御する」という同じ目的を異なる手段(複製 vs 符号化)で達成する。(Source: [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]] §5.4, Figure 8) - **ClickHouseはクォーラムを既定挙動ではなくオプトインの例外として位置づけ、Aurora系のV/Vw/Vr三変数設計とは対照的な「単一しきい値+既定結果整合性」というより単純なモデルを採る**: [[ClickHouse]]([[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]])のレプリケーションは、Raftベースの調整サービスKeeperを介した状態遷移ログ(挿入・マージ・ミューテーション/DDL)のアクティブアクティブ複製であり、既定は結果整合性(クエリが直後にレプリカ間で一時的に古いデータを返しうる)である。強い保証が必要な場合のみセッションレベルの`insert_quorum`設定で書き込みクォーラムを強制でき、クォーラムに達しない場合はINSERTが失敗し挿入済みブロックが全レプリカから削除される。Auroraが読み書き双方に対しVr/Vwという2つのクォーラム変数を常時適用し「読み込みが最新書き込みを必ずカバーする」ことを構造的に保証するのに対し、ClickHouseは読み込み側のクォーラムという概念を持たず(クエリは単一レプリカのローカル状態を読む)、書き込みクォーラムのみを必要な場面で選択的に有効化する非対称設計である。これは、OLTP(Aurora)では強整合性がデフォルト要件であるのに対し、追記専用でイベント単位の整合性要求が緩いオブザーバビリティ向けOLAP(ClickHouse)では結果整合性がデフォルトで許容され、クォーラムはコストを伴うオプトイン機能として扱われるという、ワークロード特性による設計分岐を示す。(Source: [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]], [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]) - **DDIAのn/w/r表記とAuroraのV/Vw/Vr表記は同じ数理(w + r > n)を指すが、前者はDynamo/Cassandra/Riak等の[[リーダーレスレプリケーション]]でレプリケーション方式そのものの根幹をなすのに対し、後者はセグメント化ストレージ層の一部品としてOLTPトランザクション処理の外側で使われる**: DDIA([[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]])は、w+r>nが成立していても、リバランシング中の読み書き集合の不一致・部分的にしか成功しなかった書き込みのロールバック省略・実クロックタイムスタンプに依存するLWWでの書き込み消失など、クォーラム条件だけでは救えない実運用上の落とし穴を列挙する。Auroraのクォーラムセット(Boolean論理による重複クォーラム)は、まさにこの「メンバーシップ変更中の不一致」問題への解答になっている。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Using quorums for reading and writing", "Understanding the limitations of quorum consistency", [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **クォーラム構成の典型値n=3・過半数w=r=(n+1)/2は複数ソースで共有される設計原則だが、非対称構成(w=n, r=1 等)を選ぶ余地もシステム依存で残る**: DDIAは「w=n, r=1」(読み取りは高速だが1ノード障害で全書き込みが失敗する)のような非対称構成も選択可能だとし、多くのDynamo-styleシステムはn=3または5でw=r=過半数を選ぶと述べる。Auroraのn=6, w=4, r=3という非対称な多数決クォーラムは、DDIAが言う「過半数(n/2超)を選べばw+r>nを満たしつつn/2台の障害まで許容できる」という一般原則の一実装であり、両者はクォーラムサイズの絶対値こそ違えど同じ設計原則(過半数クォーラム)に従っている。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Using quorums for reading and writing", [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) - **w + r > n というクォーラム条件は「読み取りが最新書き込みを必ず含む」ことしか保証せず、[[線形化可能性]]を保証しない**: DDIA 2E 第10章は、n=3, w=3 の書き込みが進行中に、2クライアントがそれぞれ r=2 のクォーラム読み取りを行う具体例(図10-6)を示し、w+r>n の条件が数学的に成立していても、後発の読み取りが先発の読み取りより古い値を返す非線形化可能な実行が起こりうることを証明する。これは本ページが列挙してきた「w+r>nでも救えないDDIAの実運用上の例外」のリストに、リバランシング中の不整合・並行書き込み衝突などと並ぶ、理論的に避けられない根本原因(クォーラムの読み書きの重なりだけでは操作の実時間順序を保証できない)を1件追加するものである。線形化可能にするには、読み取り時の同期的 read repair と、書き込み前の quorum read によるタイムスタンプ確認という追加コストが必要になる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Implementing Linearizable Systems", [[線形化可能性]]) - **詳説データベースのN/W/R表記はDDIA/Auroraのn/w/rやV/Vw/Vrと同一の数理を指すレプリケーション方式非依存の一般形であり、ウィットネスレプリカは「コピーの複製コスト」を「過半数条件」から切り離す独立した最適化軸を示す**: 本ページは既にDDIAのn/w/rとAuroraのV/Vw/Vrが同じw+r>nの数理を共有することを確認しているが、詳説データベース11章のN/W/R表記もこれと同一である。加えて同章が導入するウィットネスレプリカは、Aurora DSQLのイレイジャーコーディング(演算による冗長性)やAuroraのクォーラムセット(Boolean論理による重複クォーラム)と並ぶ第3の「複製コストを削減する」設計軸であり、「クォラム中に少なくとも1つのコピーレプリカが必要」という制約だけを守れば、コピーの実体を持たない軽量なウィットネスで過半数クォーラムを構成できる。これはAurora DSQLのイレイジャーコーディングが「任意の2つのJournalから復元可能にする」演算的冗長性であるのに対し、ウィットネスレプリカは「書き込み事実の記録のみ」という更に軽量な冗長性であり、両者は「複製コストとクォーラム可用性のトレードオフ」という同じ問題に異なる解を与える。(Source: [[@2021__OReillyJapan__詳説データベース - Chapter 11 レプリケーションと一貫性]] §11.9, [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]] §5.4) - **クォーラム合意プロトコルは「レプリカ障害の独立性」という耐久性の前提そのものを密結合にしうるという、統計的AZ相関とは異なる種類のリスクを『SREの探求』17章が指摘する**: 本ページが既に記録するAurora論文の知見(横断的知見冒頭)は、AZ障害という物理的な相関障害に対してクォーラム設計(V=6, Vw=4, Vr=3)がどう耐えるかを論じるのに対し、[[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]]は物理的相関とは別の経路——「Zookeeperのようなクォーラム合意プロトコルは、耐久性の観点から密結合であるだけでなく、可用性の観点からも密結合である」——を指摘する。同章はレプリケーション一般について「プライマリデータベースから発行されたデータが壊れていてもレプリカはそのまま保存する」と述べており、クォーラムによる過半数合意はデータが壊れていないことを検証するものではなく、あくまで「過半数のレプリカが同じ(壊れているかもしれない)値を持つこと」を保証するに過ぎない。これは、Auroraの6ウェイクォーラムのようなAZレベルの物理的分離を徹底しても、論理的な(データ内容レベルの)結合が残る限り耐久性の独立性の前提は満たされないことを示唆し、[[分散ストレージ]]・[[データ耐久性]]が扱う「論理的分離」という設計軸がクォーラム設計そのものにも及ぶべきであることを補強する。(Source: [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] §17.3.2, [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) ## 未解決の問い - 書き込みクォーラム Vw=4/6 はレイテンシジッターにどの程度影響するか？最速の 4 台から ACK が返れば完了するため、残り 2 台の遅延は無視できる。クラウドの「背景ノイズ」ノードに対してこの設計がどの程度有効かの実測データは本論文では限定的。 - セグメントサイズ（10GB）の最適値はネットワーク帯域・MTTR・クォーラム設計の組み合わせで決まるが、どのようなトレードオフ空間があるか？ - Bigtable（[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]）や分散 PostgreSQL など他の分散ストレージがどのようなクォーラム設計を採用し、Aurora と比較してどのようなトレードオフを選んでいるか？ - クォーラムセットの非ブロッキング性は Boolean 論理で証明されているが、64TB（38,400 セグメント）スケールで多数のメンバーシップ変更が同時発生するとき（AZ 全体の障害等）の実運用挙動は？ - Aurora DSQL の Journal 間イレイジャーコーディング(2-of-3)は classic Aurora の 6 ウェイクォーラムと比べてどの程度ストレージコストを削減しているか。両者のコスト・可用性・レイテンシのトレードオフを同一条件で比較したデータは論文にはない。 - ClickHouseの`insert_quorum`はAuroraのVw(過半数超クォーラム)とどこまで数学的に同型か。ClickHouseのドキュメント・書籍本文には読み込みクォーラムVrに相当する概念が明記されておらず、クォーラム書き込み後の読み込み一貫性がどう保証される(あるいは保証されない)かは本章の記述からは確認できない。 - DDIAが列挙する「w+r>nでも救えない」実運用上の例外(リバランシング中の不整合・部分成功書き込み・並行読み書き・実クロックLWW・並行書き込み衝突)は、Auroraのクォーラムセット設計やClickHouseの`insert_quorum`はそれぞれどこまでカバーしているか、あるいは同じ弱点を共有しているか。 ## 関連 - [[分散ストレージ]] — クォーラムが解決する可用性・整合性問題の文脈 - [[コンピュートストレージ分離]] — Aurora でクォーラムが適用されるストレージ層の設計 - [[クラッシュリカバリ]] — クォーラム設計がリカバリ高速化にどう寄与するか - [[分散コンセンサス回避]] — Aurora がクォーラムを活用しつつ 2PC/Paxos を不要にする設計原則 - [[Amazon Aurora (Database)]] — クォーラムベースレプリケーションの実装例 - [[Aurora DSQL]] — イレイジャーコーディングによるレイテンシ・可用性最適化の実装例 - [[ClickHouse]] — `insert_quorum`によるオプトイン書き込みクォーラムの実装例 - [[リーダーレスレプリケーション]] — n/w/rクォーラムがレプリケーション方式そのものの根幹をなすDynamo-styleアーキテクチャ - [[結果整合性]] — クォーラム条件が確率的にしか整合性を保証しない場合に生じる整合性モデル - [[線形化可能性]] — w+r>nのクォーラム条件だけでは保証されない、より強い一貫性モデル - [[Spanner]] — ウィットネスレプリカの実装例 - [[CAP定理]] — クォーラムが選び取る「ベストエフォートの一貫性/可用性」の理論的背景 - [[データ耐久性]] — クォーラム合意プロトコルの論理的密結合が耐久性に与えるリスク ## 出典 - [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]（V=6, Vw=4, Vr=3 クォーラム設計の詳細・AZ 障害モデル・セグメント化 MTTR との組み合わせ） - [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]（クォーラムセット + エポックによる非ブロッキックメンバーシップ変更・フル/テールセグメント非対称設計） - [[@2026__arXiv__Aurora DSQL - Scalable, Multi-Region OLTP]]（Journal 間イレイジャーコーディングによるレイテンシ・可用性最適化） - [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]（Keeper経由のアクティブアクティブ複製と`insert_quorum`によるオプトインクォーラム書き込み） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]]（n/w/rクォーラム条件の一般定義・Dynamo-styleでの適用・限界となる実運用上の例外の列挙） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]]（w+r>nを満たしても線形化可能性は保証されないことの具体例と、線形化可能にするための追加コスト） - [[@2021__OReillyJapan__詳説データベース - Chapter 11 レプリケーションと一貫性]] §11.8 調整可能な一貫性（N/W/Rの一般形）, §11.9 ウィットネスレプリカ（コピーレプリカとウィットネスレプリカの分離によるストレージコスト削減） - [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] §17.3.2(クォーラム合意プロトコルの論理的密結合というリスク)