決定論的シミュレーション（Deterministic Simulation）は、システムテストにおいて非常に強力な手法であり、分散システムの安定性と信頼性を大幅に向上させることができます。この手法では、システム全体のコンポーネントを単一スレッドのシミュレーター上で実行することにより、決定論的な実行とバグの一貫した再現が可能になります。特に注目すべき利点は、現実世界での長時間にわたる動作を短時間でシミュレートできる点にあり、システム内の潜在的な問題を効率的に発見できるツールとなっています。
多くの分散システムがすでに決定論的シミュレーションを活用しており、中でも著名な例がFoundationDBです。RisingWave はクラウドネイティブな分散型データベースであり、同様に高い正確性と信頼性が求められるため、我々はこの手法を RisingWave に導入し、Madsim と呼ばれる決定論的テストフレームワークを開発しました。このフレームワークは、RisingWave に対して継続的なエンドツーエンドのシミュレーションテストを行うために使用され、開発初期段階における並行性やリカバリに関する多くの潜在的問題を検出・排除するのに貢献しています。
本記事では、決定論的シミュレーションの背景と原理を解説し、我々のテストフレームワークである Madsim を紹介し、さらに RisingWave における実際の適用経験についても共有します。
並行性バグ（Concurrency Bugs）
現実世界で稼働している分散システムは、遅延・ロス・順序が乱れたメッセージ、スレッドの実行順の不確定性、乱数の結果といった数多くの不確実性に直面します。並行性に関する問題は、特定の実行順序でのみ発生することがあり、その発見と排除は非常に困難です。これらの問題はシステムの安定性に深刻なリスクをもたらし、バグが「出たり消えたり」する現象を引き起こすため、デバッグ作業も難航します。
この問題に対し、学術界および業界の双方から様々な解決策が提案されています。学術的アプローチでは、形式的検証や全状態空間の完全列挙などが主流ですが、これは小規模なシステムにしか通用せず、大規模システムでは状態爆発により実用に耐えません。
一方で、業界ではできる限り多くのケースを網羅する広範なテストに重きを置いており、Chaos Engineering（カオスエンジニアリング）が代表的な手法です。カオスエンジニアリングは現実環境下でのシステム挙動を検証するには効果的ですが、不確実性を制御したり、100%の問題再現性を保証したりすることはできず、開発やデバッグの難易度を上げる要因となります。
決定論的シミュレーション（Deterministic Simulation）
原理と利点
決定論的シミュレーションは、システム内の不確実性を排除することで、問題の安定した再現を可能にし、先述の2つの手法のギャップを埋めるソリューションを提供します。以下に挙げるような不確実性の各要因をどのように排除するかを見ていきましょう：
- 単一スレッドで乱数を生成する場合、初期の乱数シードを固定するだけで十分です。
- 複数スレッドのスケジューリング順序に関しては、それらすべてを単一スレッド上で実行することで制御可能です。
- オペレーティングシステムやネットワークといった外部要因が引き起こす不確実性については、包括的なシミュレーターを構築してその挙動を決定論的に模倣できます。さらに、エラーやランダム性も制御された方法で導入することで、「決定論的カオスエンジニアリング」が実現可能となります。
以上が決定論的シミュレーションの基本原理です。ここで重要なのは、「時間」もまたシミュレートされた変数であるという点です。システム内の各イベントには決定論的な発生時刻が割り当てられ、シミュレーターはそれらを時間順に処理します。システム時間は連続的なタイムライン上の離散点の集合として表現されるため、この手法は 離散イベントシミュレーション（Discrete-event Simulation） とも呼ばれます。
離散イベントシミュレーションでは、時間加速効果を生み出すことが可能です。2つのイベントの間に他のイベントが存在しない場合、それらが数年離れていたとしても、シミュレーターは瞬時に次のタイムポイントへジャンプできます。この機能により、実際には長期間にわたるシステムの挙動を短時間で再現することができ、唯一の制約は単一CPUの計算能力となります。このため、本手法は I/O 集約型アプリケーションに対して非常に有効ですが、計算集約型アプリケーションにはあまり向いていません。
結論として、決定論的シミュレーションの主な利点は 決定性（Determinism） と 高速実行 であり、問題の特定と解決の効率を飛躍的に高めることができます。しかし、こうした利点があるにもかかわらず、この手法はまだ広く普及していません。その主な理由は、高い侵襲性（intrusiveness） と 工学的複雑さ にあります。
課題と機会
すべての不確実性の要因を排除するためには、システムが依存しているあらゆる外部環境に対してシミュレーターを構築する必要があります。これは非常に手間のかかる作業であり、ランダム性の要因を一つでも見落とすと、システム全体の決定性が損なわれてしまいます。内部でランダム性を持つサードパーティライブラリは使用できませんし、すべてのノードのコードを単一スレッド上で実行する必要があります。これを実現するには、状態機械とイベントループを設計するか、コルーチン（coroutine）を導入する必要がありますが、いずれにしても大きなチャレンジを伴います。
FoundationDB チームは10年前に決定論的シミュレーターの構築を開始しました。当時の C++ には言語レベルでのコルーチンのサポートがなく、Rust のようなモダンなシステムプログラミング言語も存在しませんでした。彼らは独自の Flow 言語を開発し、これは C++ にアクター（Actor）ベースのスタックレス・コルーチン構文を追加したものでした。そして、この Flow 言語の上にシミュレーターとデータベースを構築しました。両者が密接に結合しているため、FoundationDB のテストフレームワークを他のプロジェクトが再利用することはできませんでした。
現在では、Rust のようにコルーチンをネイティブサポートし、非同期プログラミングのための成熟したエコシステムを持つ言語が登場しています。しかしながら、Tokio のように広く利用され、十分にテストされた決定論的テストフレームワークはまだ存在していません。
コミュニティによる試みとしては、Tokio コミュニティによる "turmoil" プロジェクトがありますが、こちらはまだ実験段階です。したがって、RisingWave の実践的なニーズに基づいてインキュベートできる、オープンで汎用的な決定論的テストフレームワークが求められており、それは開発者自身のみならずコミュニティにとっても有益となるはずです。
Madsim プロジェクト
Rust の非同期プログラミングエコシステムに基づいて構築された分散システム用決定論的シミュレーター、Madsim プロジェクトを紹介します。Madsim は Tokio のような非同期ランタイムに似ていますが、Madsim ではすべての挙動が決定論的であり、ネットワークのような環境もシミュレートされています。
Madsim の内部構造は次の図に示されています：
図：Madsim のアーキテクチャ（内部構造）
Madsim のアーキテクチャはボトムアップ方式で、以下の4つのモジュールで構成されています：
-
グローバル擬似乱数生成器（Global Pseudo-Random Number Generator）
決定論的シミュレーションの中核をなすのが、グローバルで決定論的な乱数生成器です。この生成器は、システム内のすべてのランダム要素（乱数、遅延、エラーなど）を生成します。同じ乱数シードを使用すれば、同じ実行シーケンスが再現されます。 -
タイマー（Timer）
タイマーは、システム内のすべてのイベントの発生源です。本質的にはタイムスタンプでソートされた優先度付きキューです。シミュレーターは実行中にキューから最も早いイベントを取り出して、イベントをトリガーしタスクを起こします。タスクは実行中に新しいタイマーイベントを作成し、それによってイベントループが形成されます。 -
タスクスケジューラ（Task Scheduler）
タスクスケジューラは、すべての実行準備ができているタスクをキューとして管理します。分散システムをシミュレートするランタイムとして、タスクは異なる論理ノードから来る可能性がありますが、すべて一つのキューに統一されてスケジューリングされます。このキューは FIRO（First-In-Random-Out：先入れランダム出し）方式で設計されており、並行性バグの探索を支援します。 -
環境シミュレーター（Environment Simulator）
ネットワークシミュレーターやディスクシミュレーターなど、非同期実行環境に基づいてさまざまなシミュレーターを構築できます。これらのシミュレーターはメモリ上のストレージを使用し、非同期に通信します。
開発者が Madsim を簡単に使えるようにするために、その機能は Tokio と完全に互換性のある API にラップされています。既存プロジェクトでは、わずかな設定変更だけでコードを変更することなく Madsim を導入できます。Madsim は gettimeofday、clock_gettime、getrandom、sysconf などの libc 関数をオーバーロードすることで、シミュレーション環境における決定論的な時間、乱数、システム設定を提供し、標準ライブラリやサードパーティライブラリ経由で現実世界にアクセスしてしまうことによる不確実性の漏れを防ぎます。こうした手法では決定論化できないライブラリについては、手動でのパッチ適用や Cargo.toml の [patch] 機能を用いたコード置換で対応可能です。これにより、既存プロジェクトのシームレスな移行と即時利用が可能となります。
Cargo.toml に以下を追加してください：
[dependencies]
madsim = "0.2"
プロジェクトで以下のクレートを使用している場合は、Madsim のシミュレータに置き換えてください：
[dependencies]
tokio = { version = "0.2", package = "madsim-tokio" }
tonic = { version = "0.2", package = "madsim-tonic" }
etcd-client = { version = "0.2", package = "madsim-etcd-client" }
[dev-dependencies]
tonic-build = { version = "0.2", package = "madsim-tonic-build" }
依存関係グラフに以下のクレートが含まれている場合、パッチ済みバージョンに置き換えてください：
[patch.crates-io]
quanta = { git = "https://github.com/madsim-rs/quanta.git", rev = "a819877" }
getrandom = { git = "https://github.com/madsim-rs/getrandom.git", rev = "cc95ee3" }
tokio-retry = { git = "https://github.com/madsim-rs/rust-tokio-retry.git", rev = "95e2fd3" }
tokio-postgres = { git = "https://github.com/madsim-rs/rust-postgres.git", rev = "1b392f1" }
シミュレーター上でコードを実行するには、madsim コンフィグを有効にしてください：
RUSTFLAGS="--cfg madsim" cargo test
RisingWave はクラウドネイティブな分散データベースであり、内部通信・制御・ストレージ・ストリームデータの送受信に gRPC、etcd、S3、Kafka を使用しています。これらのサービスはネットワーク上でのメッセージ送信を前提としており、これがなければ RisingWave は完全なシステムとして動作しません。Madsim のコア機能を土台として、ネットワークシミュレーター上におけるこれらのサードパーティサービスの決定論的シミュレーションが実装され、tonic、etcd-client、rust-rdkafka、aws-sdk-s3 などのコミュニティライブラリが提供するインターフェースにラップされています。
図：ネットワークシミュレーターを土台としたサービス構造図
ネットワークシミュレーターは、これらのサービスに共通する基盤として機能します。IP アドレスに基づいてネットワーク層のトポロジーを構築し、仮想ネットワーク上でのパケットのルーティング、遅延、パケットロスをシミュレートします。そして、信頼性のある転送やデータグラムの転送といった通信プリミティブを提供します。上位層のサービスは、これらのプリミティブを使って RPC サービスを構築し、サービスインターフェースのセマンティクスを実装するだけで済みます。
特筆すべきは、etcd、Kafka、S3 のシミュレーターは実物と比べてはるかに簡略化されており、単一スレッド上で逐次的に実行されるため、並行性、コンセンサス、フォールトトレランスなどを考慮する必要がありません。送信されるメッセージはシリアライズさえ不要で、メモリ上でオブジェクトポインタとして直接伝達することができます。
Madsim は各レイヤーでシミュレーションの挙動を制御したり、システム情報を取得したり、手動でエラーを注入したりするための制御用インターフェースも提供しています。たとえば、ノードをブロック・強制終了したり、ネットワークリンクの接続状態を操作することが可能です。これらの API 定義は Madsim の API ドキュメント にて確認できます。
決定論的シミュレーションは、分散システムの安定性と信頼性を向上させる強力なシステムテスト技術です。本記事では、決定論的シミュレーションの原理と利点を概説し、テストフレームワーク Madsim を紹介してその仕組みを解説しました。次回の記事では、RisingWave における具体的な応用事例や実際の体験・考察について取り上げていきます。