# 複製ステートマシン ## 定義 複製ステートマシン（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 は「全ての入力が決定論的」という前提が必要だが、タイムスタンプ・乱数・外部 API 呼び出しを含むトランザクションを RSM 上で実行するためのベストプラクティスは確立されているか？ - RSM と Multi-Version Concurrency Control（MVCC）の組み合わせで、どの一貫性レベル（線形化可能性・シリアライザブル等）まで達成できるか？ ## 関連 - [[分散コンセンサス]] — RSM の複製ログを一貫させる根底メカニズム - [[リーダー選出]] — Raft において RSM 管理の責任を一点に集中させる仕組み ## 出典 - [[@2014__ATC__In Search of an Understandable Consensus Algorithm]]（RSM の定義・複製ログ実装・実用例）