Celld における決定論的シミュレーションテスト

Celld における決定論的シミュレーションテスト 実行順序を調査し、バグを再現する Yusuke Tanaka · 2026年10月2日 私たちは celld を開発しています。これは、Cloudflare Workers および Durable Objects アプリケーションを自身のマシン上で実行するためのランタイムです。外部サービスへの依存は S3互換オブジェクトストアのみで実行可能です。celld は分散システムです。分散システムの信頼性を確保することは困難です。その一因として、私たちは実際には当てはまらない前提に意図せず依存してしまうことがあります。たとえその落とし穴を知っていてもです。Peter Deutsch の「分散コンピューティングの8つの誤謬」には、「ネットワークは信頼できる」や「レイテンシはゼロ」といった8つの誤謬が挙げられています。バグは、遅延したメッセージ、失敗した書き込み、ノードの再起動といった特定の順序に依存する可能性があります。これらのイベントは、次のテスト実行では異なる順序で発生する可能性があり、その失敗の再現を困難にします。原因を調査し、提案された修正が本当に問題を解決するかどうかを確認するために、失敗した実行を繰り返せる必要があります。だからこそ、私たちは決定論的シミュレーションテスト（DST）を使用しています。私たちのシミュレータはまだ開発中であり、celld の公開リポジトリには含まれていませんが、すでに未知のバグを発見しています。この記事では、celld で DST がどのように機能し、それがどのようにしてバグを発見、再現、修正するのに役立ったかを説明します。 celld で DST がどのように機能するか DST は celld の本番コードをシミュレータによって制御される環境で実行します。celld のセルはアプリケーションコードを実行し、独自の SQLite データベースを持っています。セルが作業を行うにつれて、celld は受信リクエスト、完了したストレージ操作、タイマーの発火などのイベントを処理します。次のイベントを選択するコードは、それを処理するコードとは分離されています。これにより、シミュレータはイベントの順序を制御しながら、本番環境と同じイベント処理コードを実行できます。シミュレータは非同期タスクの実行時期やオブジェクトストアの応答も制御します。書き込みを遅延させたり、失敗させたりすることができます。実際の時間を待たずにシミュレートされた時間を進めることができます。私たちはこの制御を使用して、リトライやアラームなどの時間依存の動作が他のイベントとどのように相互作用するかをテストします。シミュレータが探索できるリクエストと障害を構成します。それらの制限内で、ランダムな選択を使用してリクエストを生成し、次に何を実行するかを選択し、ストレージ操作が成功するか失敗するかを決定し、どの障害が発生し、いつ発生するかを選択します。シードは乱数ジェネレータの開始値です。同じコード、設定、シードを使用すると、同じシーケンス、中間状態、および結果が得られます。シードを変更することで異なる実行を探索し、失敗した実行を繰り返してどこで問題が発生したかを追跡できます。各アクションの後、チェッカーは観測された応答と保存されたデータを使用して不変条件をテストします。これは、システムが実行中に維持しなければならないと定義した条件です。テストは、シミュレートされた環境で celld を初期化し、設定された制限までアクションを探索します。疑似コードで示すと次のようになります。 const simulation = createSimulation({ settings, seed }); for (let step = 0; step < settings.maxActions; step++) { const candidates = simulation.availableActions(); if (candidates.length === 0) { checkCompletion(simulation); break; } const action = simulation.choose(candidates); simulation.run(action); checkInvariants(simulation); } ここで、アクションとはシミュレータが進めることができるものです。リクエストの配信、タスクの実行、シミュレートされたクロックの進行、またはストレージ操作の完了などです。アクションが利用できない場合、テストはその完了条件をチェックします。例えば、計画されたすべてリクエストが完了したかどうかなどです。 以下の単純化されたリプレイは、セル A が SQLite に行を挿入した後から始まります。データが celld が確認を受け取る前にオブジェクトストアに保存される様子をご覧ください。他のリクエストやバックグラウンドタスクが、celld がクライアントに成功を返信するのを待っている間に、そのギャップで実行される可能性があります。これらの操作が予期しない方法でインターリーブされると、バグが発生する可能性があります。シミュレータはこれらのステップを個別に制御するため、異なる実行順序を探索し、バグを露呈するものをリプレイできます。 「次へ」を押して、アクションの選択、アニメーション化、結果の表示を進めてください。 Candidates SQLite の変更を送信します。オブジェクトストアがそれらを受信するようにします。 →Chosen Client▶celld▶S3-compatible storage▶simulated Cell A Cell B SQLite Cell C SQLite SQLite Waiting for data◷ Waiting Insert row new row DB changesⅡ Response Client▶celld▶S3-compatible storage▶simulated Cell A Cell B SQLite Cell C SQLite SQLite Waiting for data◷ Waiting Insert row new row DB changesⅡ Response 1Choose2Run3Result Starting state The row is in SQLite. The client is still waiting for success. ←Next→ Step 0 / 12 上記のリプレイは成功したリクエストを示しています。次に、celld のバグを露呈した実行順序を見てみましょう。 アラームレースをシミュレータが発見 アラームは、指定された時間にセルのアプリケーションコードを実行するようにスケジュールします。セルは、その時までメモリ内に留まる必要はありません。celld は、他のセルにスペースを作るためにアイドル状態のセルをアンロードし、アラームを実行する時間になると再度ロードできます。アラームのスケジュール時刻は、セルの SQLite データベースに保存されます。セルがアンロードされている場合、SQLite のみからアラームを見つけるには、データベースを再度開く必要があります。セルごとにそれを行うのはコストがかかるため、celld は代わりにオブジェクトストアのウェイクエントリをスキャンします。各エントリはセルを識別し、いつ再アクティブ化するかを示します。セルがアクティブになったら、celld は SQLite からスケジュール時刻を読み取り、アラームを実行するまで待ちます。このバグを見つけたとき、celld はオブジェクトストアへの書き込み回数を減らすためにウェイクエントリを再利用していました。たとえば、アプリケーションは 10:00 のアラームを削除してから、10:05 の新しいアラームを設定できます。10:00 のウェイクエントリがまだ存在する場合、celld はそれを使用してセルを 10:00 に再アクティブ化し、新しいアラームを実行するのに十分な時間を与えることができます。セルがアクティブになると、celld は SQLite から 10:05 を読み取り、アラームを実行するまでその時間まで待ちます。 10:00 のアラームを削除すると、そのスケジュール時刻が SQLite からクリアされます。その変更がオブジェクトストアに保存されると、celld はクライアントに成功を返します。後で別のクリーンアップタスクが 10:00 のウェイクエントリを削除するため、クライアントは追加のストレージ操作を待つ必要がありません。したがって、クライアントは古いクリーンアップが実行されるのを待っている間に、10:05 のアラームを設定できます。celld が 10:05 のアラームが設定されたことを確認した後、アラームが実行されるかキャンセルされるまでセルを再アクティブ化できるウェイクエントリが残っている必要があります。シミュレータは、アラームが実行されるかキャンセルされるまで、これが真であり続けることをチェックします。下の図は、新しい 10:05 のアラームが設定された後に古いクリーンアップが実行された場合に、この不変条件がどのように侵害されるかを示しています。 Candidates セル A の 10:00 アラームを削除します。 →Chosen Client▶celld▶S3-compatible storage▶simulated ▶Cell A Alarm in SQLite 10:00 Waiting task Delete 10:00 wake entry▶ 10:00 wake entry Present Delete 10:00 alarm Deleted Delete 10:00 Client▶celld▶S3-compatible storage▶simulated ▶Cell A Alarm in SQLite 10:00 Waiting task Delete 10:00 wake entry▶ 10:00 wake entry Present Delete 10:00 alarm Deleted Delete 10:00 1Choose2Run3Result4Check Starting state Cell A has a 10:00 alarm in SQLite and a 10:00 wake entry in object storage. ←Next→ Step 0 / 21 この実行では、10:00 のアラームの削除と新しい 10:05 のアラームの設定の両方が成功を返しましたが、古いクリーンアップは待機していました。シミュレータが最終的にそのクリーンアップを進めると、新しいアラームが必要としていた 10:00 のウェイクエントリが削除されました。チェッカーは不変条件の違反を報告しました。10:05 のアラームは SQLite に設定されたままでしたが、セルを再アクティブ化するためのウェイクエントリは残っていませんでした。ノードが 10:05 より前に再起動した場合、ウェイクエントリが失われていると、以前の成功応答にもかかわらず、アラームが実行されない可能性があります。シミュレータは、リクエストと保留中の作業を探索することで、この失敗する順序を発見しました。私たちはこのシーケンスを指定するテストを書いていませんでした。 レースの再現と修正 同じコード、設定、シードを使用して失敗をリプレイしました。各実行により、失敗する順序を再度探すことなく、古いクリーンアップが必要なウェイクエントリを削除した瞬間を検査できました。それ以来、ウェイクエントリの設計を変更しました。新しいアラーム設定ごとに、オブジェクトストアに独自の新しいエントリが作成されます。古いアラームの遅延削除は