# リーダーレスレプリケーション ## 定義 リーダーレスレプリケーション(leaderless replication)とは、リーダーという概念を排し任意のレプリカが直接クライアントからの書き込みを受け付ける方式である。初期の複製データシステムの一部はリーダーレスだったが、リレーショナルデータベースの時代に廃れ、2007年にAmazonが社内システムDynamoで採用したことで再び脚光を浴びた。RiakやApache Cassandra、ScyllaDBはDynamoに着想を得たOSS実装であり、この系統は Dynamo-style と呼ばれる。実装によってはクライアントが直接複数レプリカへ書き込む場合と、コーディネータノードが代行する場合があるが、コーディネータはリーダーと異なり書き込み順序を強制しない。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Leaderless Replication") ## ノード障害時の挙動と修復メカニズム リーダーレス構成にはフェイルオーバーという概念が存在しない。クライアントは書き込みをn個のレプリカ全てへ並列送信し、あらかじめ決めた数(w)の確認が得られれば成功とみなす。オフラインだったレプリカが復帰すると古い値を返しうるため、読み取りも複数レプリカへ並列送信し(r個)、バージョン番号/タイムスタンプで最新値を判定する。復帰後のレプリカを最新化する仕組みは3種類ある。(1) read repair: 読み取り時にstaleな応答を検出し新しい値を書き戻す。頻繁に読まれる値に有効。(2) hinted handoff: 利用不能なレプリカ宛の書き込みを別レプリカが「ヒント」として一時保持し、復帰時に転送する。読まれない値もカバーする。(3) anti-entropy: バックグラウンドでレプリカ間差分を検出しコピーする処理。順序を保証せず遅延が生じうる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Writing to the Database When a Node Is Down", "Catching up on missed writes") ## クォーラムと並行書き込みの検知 n個のレプリカに対しw個の書き込み確認・r個の読み取り確認を要求し、w + r > nを満たせば読み取りは最新の書き込みを含むレプリカを必ず1つ以上含む。この量的トレードオフの詳細は [[クォーラムベースレプリケーション]] に委ねる。リーダーレス特有の課題として、順序を強制するリーダーが存在しないため並行書き込みの衝突検知が必須になる。happens-before関係(操作Bが操作Aを知っている・依存しているならAはBに先行する)に基づき、単一レプリカではバージョン番号、複数レプリカでは version vector(レプリカごとのバージョン番号の集合。dotted version vectorはRiak 2.0で採用)を用いてどの値が上書きされ、どの値がsiblingsとして残すべきかを判定する。version vectorはvector clockと呼ばれることもあるが、レプリカ状態の比較にはversion vectorが正しいデータ構造とされる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Using quorums for reading and writing", "Detecting Concurrent Writes", "The happens-before relation and concurrency", "Version vectors") ## 単一リーダーとの性能比較 単一リーダー方式はリーダーから読めば常に最新値を得られる代わりに、リーダーの処理能力が読み取りスループットの上限になり、リーダー障害時はフェイルオーバー完了まで応答時間が悪化し、リーダーの性能問題がシステム全体に即座に波及する。リーダーレス方式は「通常時と障害時を区別しない」ことに強靭性の本質がある。フェイルオーバーが存在せず、複数レプリカへ並列リクエストを送るため、1レプリカの低速化・利用不能はレスポンスタイムへの影響が小さい(最速の応答を使う request hedging)。これは、完全に停止してはいないが異常に遅い gray failure への対応で特に有利に働く。一方でレプリカ数が増えるほどクォーラムのサイズが大きくなり待つべき応答数が増える、大規模ネットワーク分断でクォーラムを構成できなくなる(その緩和策として任意の到達可能なレプリカへ書き込む sloppy quorum / consistency level ANY がある)といった弱点も持つ。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Single-Leader Versus Leaderless Replication Performance") ## 横断的知見 - **DDIAが概念レベルで並列に挙げるread repair・hinted handoff・anti-entropyの3機構は、Database Internals 12章では実装アルゴリズムのレベルまで分解される**: DDIAはread repairを「staleな応答を検出し新しい値を書き戻す」、hinted handoffを「利用不能なレプリカ宛の書き込みを別レプリカが一時保持し復帰時に転送する」と1〜2文で定義するに留まる。[[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]]は同じ2機構を、read repairについてはブロッキング/非同期の実装差(ブロッキングはクォーラム読み取りの読み取り単調性を保証する代わりに可用性を犠牲にする)、hinted handoffについてはsloppy quorumとの組み合わせ(ターゲットレプリカでない代替ノードをクォーラムに算入し、ヒントが復旧先で再生されるまでの具体的な手順)まで踏み込んで説明する。DDIAが「何をするか」を述べるのに対し、Database Internalsは「どう実装するか、その結果どんな整合性保証を得るか」を述べており、両者は入門的分類と実装詳細という異なる抽象度で同じ主題を扱っている(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]] "Catching up on missed writes", [[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]] §12.1, §12.3)。 - **DDIAのversion vectorとDatabase Internalsのビットマップバージョンベクトルは、同じ「並行書き込みの因果関係を追跡する」問題への異なる符号化である**: DDIAのversion vectorはレプリカごとのバージョン番号の集合として並行書き込みを検出するが、切り捨て時の正確性への影響が未解決の問いとして残っていた(下記参照)。12章のビットマップバージョンベクトルは、各書き込みをdot (i, n)(ノードローカルなシーケンス番号とそれを調整したノードの組)として表現し、連続した書き込みまでを1つの数値に圧縮しつつ、それ以降の欠落をビットマップでエンコードする。この設計は「どこまで連続して見たか」と「どの欠落した点を個別に見たか」を分離して記録することで、version vectorの単純な切り捨てが持つ精度低下の問題を軽減する具体的な符号化例になっている(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]] §12.5)。 - **anti-entropyという1機構は、Database Internalsではさらにダイジェスト読み取り・Merkleツリー・ゴシップという複数の下位機構に分岐する**: DDIAは「anti-entropy: バックグラウンドでレプリカ間差分を検出しコピーする処理」とひとまとめに述べるが、12章はこれを、問い合わせのたびに全データではなくハッシュだけを比較するダイジェスト読み取り(read repairの効率化版)、データセット全体を階層ハッシュで比較するMerkleツリー(積極的に照会されないデータの不整合検出)、クラスタ全体のメタデータ伝播を担うゴシップ(→[[ゴシッププロトコル]])という異なる目的の機構に分けて論じる。DDIAのanti-entropyという語は、この複数機構をまとめて指す上位カテゴリ名として理解する必要がある(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]] §12.2, §12.4, §12.6、詳細は [[アンチエントロピー]])。 ## 未解決の問い - read repair・hinted handoff・anti-entropyの3機構は復旧速度と負荷増大のトレードオフをそれぞれ持つが、実運用でどの機構がどの程度の割合で修復を担っているかの定量データはDDIA本文にはない。既存の [[Dynamo]] エンティティページが持つ本番実績データとの突き合わせが有効か。 - version vectorの切り捨て(閾値超過時に最古エントリを除去)は [[結果整合性]] concept で「調整の正確性への影響」として既に問いが立っている。DDIAのdotted version vector(Riak 2.0)はこの問題にどう対処しているか、原論文(Preguiça 2010)への遡及が必要。Database Internals 12章のビットマップバージョンベクトル([[アンチエントロピー]]参照)が同種の切り捨て問題(ノードが長時間停止するとログを切り詰められない)を持つことが分かっており、両者の切り捨て戦略を比較する価値がある。 - sloppy quorum(consistency level ANY)は「書き込みが必ずしも通常のnレプリカに届かない」ため、後続の読み取りがその値を見る保証がない。この設計とクォーラム条件w+r>nの整合性(あるいは非整合性)はどのように運用上扱われているか。 - ブロッキング読み取り修復が保証する読み取り単調性(Database Internals 12章)は、DDIAが定義する monotonic reads([[レプリケーションラグと読み取り整合性]])と同じ保証を指すのか、それとも別物か。前者はクォーラム読み取りに限定された保証、後者は単一リーダー方式のフォロワールーティングに関する保証であり、適用文脈が異なるため単純に同一視してよいか要検証。 ## 関連 - [[単一リーダーレプリケーション]] — フェイルオーバー概念の有無で対照的な設計 - [[マルチリーダーレプリケーション]] — 書き込み衝突という共通課題を持つもう一つの代替アーキテクチャ - [[クォーラムベースレプリケーション]] — w/r/nパラメータによる整合性・可用性制御の詳細 - [[結果整合性]] — リーダーレス方式が前提とする整合性モデル - [[アンチエントロピー]] — read repair・hinted handoff・anti-entropyを統合する上位概念、実装詳細の集約先 - [[ゴシッププロトコル]] — anti-entropyの下位機構の1つ(クラスタ全体のメタデータ伝播) - [[Dynamo]] — リーダーレスレプリケーションを再興した原点システム - [[Apache Cassandra]] / [[Riak]] — Dynamo型レプリケーションのOSS実装例 ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 6 Replication]](リーダーレスレプリケーションの定義・ノード障害時の修復機構・クォーラム・並行書き込み検知・性能比較の詳細) - [[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]](read repairのブロッキング/非同期実装差・sloppy quorum・ビットマップバージョンベクトルによるdot表現)