プロトコル認識型決定論的シミュレーションテスト

TigerBeetleの決定論的シミュレーターはプロトコルを認識するため、データベースレベルだけでなく、個々のレプリカレベルで安全性とライブネスの不変条件をテストできます。 if (replica.status == .recovering_head) assert(fault); この記事では、分散システムのテストにおける、従来のブラックボックス手法（例: Jepsenのようなジェネレーティブテスト）や決定論的ハイパーバイザー（例: Antithesis）を超えて、プロトコル認識型DSTを使用して安全性とライブネスの不変条件を深くテストするメカニズム、方法、および利点について説明します。 不変条件 まず、安全性とライブネスの不変条件、コンセンサスプロトコル、および決定論的シミュレーションテストに関する背景知識を説明します。 分散システム、つまり複数のノードが相互作用するシステムは、開発者が複数のマシン上での並行実行について推論する必要があり、そのインターリーブの状態空間は広大であるため、正しく実装するのが非常に困難であることが知られています。 テストはさまざまな角度から行うことができますが、ここではまず不変条件から始めましょう。分散システムをテストする際には、2つの不変条件のセットを特定することが重要です。 安全性: 何も悪いことが決して起こらないことを意味します。例えば、2つのノードが同じリクエストに対して異なる結果を返すことはありません。 ライブネス: 適切な数のノードがオンラインであれば、リクエストは最終的に応答されることを意味します。 テストは、システムがこれらの安全性とライブネスの不変条件を維持していることを確認しようとする必要があります。 コンセンサスベースのシステムを考えてみましょう。このシステムでは、コンセンサスプロトコルが耐久性を可用性に安全に変換します。簡単に言えば、コンセンサスプロトコルは、システムの冗長性を使用して耐障害性を提供し、単一ノードの幻想を維持します。 高レベルでは、コンセンサスプロトコルは以下を保証します。 耐障害性: プロセスのクラッシュ、ネットワークパーティション、ストレージの破損などの障害が許容され、マスクされることを保証します。これは通常、データの複数のコピーを冗長性のために維持すること、つまりレプリケーションによって達成されます。Viewstamped Replication のアルゴリズムは、過半数のレプリカがオンラインである限り、応答性を保証します。例えば、3つのレプリカを持つシステム（過半数は2つのレプリカ）では、最大1つの障害を許容できます。これはコンセンサスプロトコルのライブネス不変条件です。 合意: システム内のデータの複数のコピーが互いに一貫していることを保証します。これを達成する1つの方法は、プライマリレプリカを選択することです。すべてのリクエストはプライマリを通過し、プライマリが操作を実行する順序は、すべてのバックアップが従う順序であり、データの整合性を保証します。これはコンセンサスプロトコルの安全性不変条件です。 TigerBeetleは、耐障害性と合意のためにVSRを使用する分散データベースです。すべてのリクエストをプライマリにルーティングすることで、厳密な直列化可能性が保証されます。これはデータベースが保証できる最も強力な分離レベルです。簡単に言えば、厳密な直列化可能性は、ある操作が別の操作を開始する前に完了した場合、データベースはその順序を反映しなければならないと述べています。したがって、テスト対象の分散データベースの安全性不変条件は厳密な直列化可能性であり、ライブネス不変条件はVSRのライブネス特性、つまり過半数のノードがオンラインである限り応答性を維持することであると言えます。 外部からのテスト これらの不変条件をテストする1つの方法は、Jepsenスタイルで、フォールトインジェクションと組み合わせたブラックボックスジェネレーティブテストを使用することです。 Jepsenは、システムの固有の非同期性と非決定性を受け入れ、ユーザー可視APIを使用して外部からシステムをテストします。これには以下が含まれます。 広大な状態空間を調査するためのランダムな入力の生成 システムへのフォールトの適用 安全性とライブネスの不変条件が維持されているかの確認 昨年、私たちはそれを行い、Jepsenレポートからの抜粋は以下の通りです。 柔軟なクォーラムとプロトコル認識型リカバリを備えたViewstamped Replicationの統合は、Strong Serializabilityの主要な不変条件を損なうことはないようです。それは素晴らしいニュースです！ Jepsen評価によると、私たちはユーザーへの保証を維持していました。これは、TigerBeetle上で開発される金融アプリケーションがこれらの強力な保証を前提として開発されているため、非常に重要です。これらのアプリケーションは、私たちが約束する厳密な直列化可能性に依存しています。 しかし、JepsenスタイルのジェネレーティブテストとAntithesisスタイルの決定論的ハイパーバイザーは、ユーザー可視APIを介して外部からシステムをテストします。API境界で可視化されない不変条件はどうでしょうか？基盤となるインフラストラクチャについては、もっと改善する必要があります。外部からだけでなく、内部からもテストする必要があります。 内部からのテスト TigerBeetleは、決定論的な分散データベースとして明示的に設計されています。データベースにおける決定論的実行のアイデアは新しいものではありません。FoundationDBとDropboxのSync Engineは、決定論的シミュレーションテストと並んで、その設計で決定論を利用していることが知られています。 したがって、FoundationDBのように、TigerBeetleは論理的な決定論を備えています。すべてのデータベースコードは決定論的であり、制御プレーンではマルチスレッドの並行処理が回避されます。しかし、私たちはさらに進んで、物理的な決定論も保証します。これにより、TigerBeetleクラスタ内のレプリカは、バイト単位で同一の状態に収束します。言い換えれば、クラスタ内のすべてのレプリカ間で、同じ物理的な場所が同じコンテンツに対応します。 この論理的および物理的な決定論により、TigerBeetleは決定論的シミュレーションテストに適したものになります。これにより、実際のコンセンサスおよびストレージエンジンコードを、VOPRと呼ぶシミュレーターで実行できます。VOPR内では、ストレージやネットワークなどの非決定的な物理的相互作用は制御可能なバージョンに置き換えられ、時間はシミュレートされます。これにより、単一のマシン上で、単一のプロセスで、生産よりも何桁も速い速度で分散データベースを実行できます。 ネットワークパーティション、ディスク破損、レプリカクラッシュなど、さまざまなシナリオを、並行クライアント操作の存在下で生成し、さまざまな安全性とライブネスの不変条件をテストします。時間はシミュレートされるため、本番環境で数ヶ月かかるシナリオを数分で探索できます。これにより、バグが隠れがちなイベントの微妙なインターリーブを迅速に見つけることができ、バグが見つかると、繰り返し決定論的に再現できます。したがって、DSTにより開発者はより速くテストおよびデバッグできるようになり、その結果、より速く構築できるようになります。 プロトコル認識型DST しかし今日、私はDSTの少し異なる側面について話したいと思います。私たちはDSTを使用してTigerBeetleを内部からテストします。これは、各レプリカのコンセンサスおよびストレージレベルの状態を完全に可視化できることを意味します。このプロトコル認識により、システムの内部を覗き込み、難しい質問を投げかけることができます。 ディープな安全性不変条件のチェック データベースレベルだけでなく、コンセンサスおよびストレージ全体で、安全性不変条件を深くチェックできます。これらの安全性不変条件のテストは、安全性が階層的であるため重要です。コンセンサスまたはストレージでの安全性不変条件の違反は、最終的にデータベースが厳密な直列化可能性というコアの安全性不変条件を違反する可能性があります。このため、本番環境とテストの両方でこれらの安全性不変条件を強制します。本番環境ではアサーションを有効にして実行し、違反が検出された場合にレプリカをクラッシュさせることで、壊滅的な安全性違反を利用可能性違反にダウングレードします。しかし、本番環境でグローバルなクラスタレベルのコンテキストを収集するのはコストがかかるため、これらのコストのかかるチェックはプロトコル認識型DSTに任せています。 コンセンサス安全性 コンセンサスプロトコルにとって、安全性不変条件は合意、つまり、