# 複製ステートマシン ## 定義 複製ステートマシン（Replicated State Machine, RSM）とは、複数のサーバーが同一のステートマシンの決定論的コピーを保ち、すべてのコピーが同一のコマンド列を同一順序で実行することで、一貫した状態と出力を保証する分散フォールトトレランス手法である。一部のサーバーがクラッシュしても稼働を継続できる。(Source: [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]) **複製ログによる実装**: 各サーバーは同一コマンド列を格納するログを保持し、それをステートマシンが順に実行する。コンセンサスモジュールがログを一貫させることで RSM の安全性を実現する（Figure 1）。 **使用例**（[[@2014__ATC__In Search of an Understandable Consensus Algorithm]] §2 より）: - **GFS・HDFS・RAMCloud** のリーダー選出・設定情報管理（単一クラスタリーダーを持つシステムがメタデータ管理に使用） - **Chubby**・**ZooKeeper**（分散ロックサービス・コーディネーション） ## 横断的知見 - **RSM の適用範囲**: データベース本体の全データには RSM を適用しないケースが多い。Amazon Aurora はデータ複製に Paxos/Raft ではなくクォーラムベースのログ複製を使い、RSM はメタデータ・リーダー選出に限定する設計をとる。コンセンサスのコストが全データ書き込みパスに乗ると OLTP スループットが制約される。(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]]) - **RSM は「共有ログ(shared log)」というより一般的な抽象化の応用事例として位置づけ直せる**: DDIA 2E 第10章は、複数ノードがエントリの追記を要求できる「共有ログ」(total order broadcast で実装される)を定義し、すべてのログエントリを決定論的ロジックで同一順序に適用すれば全レプリカが一貫した状態に収束する、という原理を RSM と呼ぶ。本ページがこれまで記録してきた「Raft のコンセンサスモジュールがログを一貫させることで RSM の安全性を実現する」という説明は、この共有ログ抽象化の具体的な一実装(Raft)にすぎない。DDIA は同じ原理が event sourcing(第3章で扱われた概念)や決定論的トランザクション実行(Calvin 型)にも直接応用できると位置づけ、RSM を「合意アルゴリズムの応用」というより広い枠組みで捉え直す視点を与える。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Shared logs as consensus", "Using shared logs") - **RSM が要求する「決定論的ロジック」という前提は、コーディネーションサービスがデータ本体でなくメタデータのみを扱う設計理由と直結する**: [[コーディネーションサービス]](ZooKeeper・etcd)がメモリに収まる小さく低頻度更新のデータに特化するのは、RSM の前提である「全ノードが同一コマンド列を同一順序で決定論的に適用する」ことを、大量データ・高頻度書き込みのワークロードで維持するコストが高いためである。Amazon Aurora が RSM をメタデータ・リーダー選出に限定する設計判断と、コーディネーションサービスがデータストレージ全般ではなく調整用の小さいデータに特化する設計判断は、同じ「RSM のコストは決定論的複製の範囲を絞ることで初めて実用的になる」という原則の異なる現れである。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]] "Coordination Services", [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **「ログエントリはリーダーからフォロワーへの一方向にのみ流れる」という Raft の RSM 実装原則は、Raft 論文とは独立な第二のソースでも同じ形で確認できる**: [[分散コンセンサス]]ページの比較表は Raft 論文由来の「ログエントリの流れ: 一方向(リーダー→フォロワー)」という特徴を記録済みだが、[[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.4.1 は独立に「もっとも新しい情報を持つ候補者だけがリーダーになれるので、フォロワーはリーダーを最新の状態にする必要がまったくない。ログエントリはリーダーからフォロワーへという方向でのみ送信され、その逆は行われない」と明記する。同一書籍の別章という独立ソース扱いの条件を満たしたうえで、Raft 論文(2014)と書籍(2021)という執筆時期・著者の異なる2つのソースが同じ設計原則に到達しており、この一方向性が RSM の安全性(コミット済みエントリは後続のリーダーのログにも保持される)を支える本質的な制約であることを裏づける。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.4.1, [[分散コンセンサス]]) ## 未解決の問い - RSM は「全ての入力が決定論的」という前提が必要だが、タイムスタンプ・乱数・外部 API 呼び出しを含むトランザクションを RSM 上で実行するためのベストプラクティスは確立されているか？ - RSM と Multi-Version Concurrency Control（MVCC）の組み合わせで、どの一貫性レベル（線形化可能性・シリアライザブル等）まで達成できるか？ ## 関連 - [[分散コンセンサス]] — RSM の複製ログを一貫させる根底メカニズム - [[リーダー選出]] — Raft において RSM 管理の責任を一点に集中させる仕組み - [[コーディネーションサービス]] — RSM を小規模・低頻度更新データに限定して実用化する実装パターン ## 出典 - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（RSM の定義・複製ログ実装・実用例） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 10 Consistency and Consensus]]（共有ログ/total order broadcast としての一般化・event sourcing との関連づけ） - [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.4.1(Raftのログ一方向性についての独立した確認)