プロトコル認識型決定論的シミュレーションテスト
Protocol-Aware Deterministic Simulation Testing (tigerbeetle.com)
要約
TigerBeetleは、データベースレベルだけでなく、個々のレプリカレベルで安全性とライブネスの不変条件をテストできるプロトコル認識型決定論的シミュレーターを開発しました。これは、従来のブラックボックステスト手法を超え、システム内部の深いレベルでの検証を可能にします。このアプローチにより、開発者はバグをより迅速かつ確実に発見・修正できるようになり、開発サイクルの高速化に貢献します。
全文翻訳
プロトコル認識型決定論的シミュレーションテスト
TigerBeetleの決定論的シミュレーターはプロトコルを認識するため、安全性とライブネスの不変条件をデータベースレベルだけでなく、個々のレプリカのレベルでもテストできます。
if (replica.status == .recovering_head) assert(fault);
この記事では、分散システムをテストする従来のブラックボックス手法(ジェネレーティブテストなど、例: Jepsen)や決定論的ハイパーバイザー(例: Antithesis)を超えて、プロトコル認識型DSTを使用して安全性とライブネスの不変条件を深くテストするメカニズム、方法、および利点について説明します。必要であれば、これらを含むさらに詳しい内容を説明した講演をご覧ください。
まず、安全性とライブネスの不変条件、合意プロトコル、および決定論的シミュレーションテストの背景について説明します。復習が必要ない方は、プロトコル認識型DSTまでスキップしてください!
複数のノードが相互作用するシステムである分散システムは、開発者が複数のマシン上での並行実行と、それらのインターリーブの広大な状態空間について推論する必要があるため、正しく実装するのが非常に困難であることが知られています。現在、このようなシステムをテストするには複数の角度からアプローチできますが、今日は不変条件から始めましょう。分散システムをテストする際には、2つの不変条件のセットを特定することが重要です。
- 安全性:これは、悪いことが決して起こらないことを意味します。例えば、2つのノードが同じリクエストに対して異なる結果を返すことはありません。
- ライブネス:これは、良いことが最終的に起こることを意味します。例えば、十分なノードがオンラインであれば、リクエストは最終的に応答されます。
その後、テストはシステムがこれらの安全性とライブネスの不変条件を維持しているかどうかを確認しようと試みる必要があります。
特定の分散システム、すなわち合意ベースのシステムを考えてみましょう。このシステムでは、合意プロトコルが耐久性を可用性に安全に変換する役割を果たします。簡単に言うと、合意プロトコルはシステムの冗長性を使用して、単一ノードの幻想を維持しながら耐障害性を提供します。高レベルでは、合意プロトコルは以下を保証します。
耐障害性
これは、プロセス障害、ネットワークパーティション、ストレージ破損などの障害が許容され、マスクされることを保証します。これは通常、レプリケーション、つまり冗長性のためにデータの複数のコピーを維持することによって達成されます。Viewstamped Replication系のアルゴリズムは、多数のレプリカがオンラインである限り、応答性を保証します。例えば、3つのレプリカを持つシステム(多数派は2つのレプリカ)では、最大1つの障害を許容できます。
これは合意プロトコルのライブネス不変条件です。
合意
これは、システム内のデータの複数のコピーがお互いに一貫していることを保証します。これを達成する1つの方法は、プライマリレプリカを選択することです。すべてのリクエストはプライマリを通過し、プライマリが操作を実行する順序はすべてのバックアップが従う順序であり、データの整合性を保証します。
これは合意プロトコルの安全性不変条件です。
TigerBeetleは、耐障害性と合意のためにVSRを使用する分散データベースです。すべてのリクエストをプライマリ経由でルーティングすることで、データベースが保証できる最も強力な分離レベルである厳密な直列化可能性を保証します。簡単に言うと、厳密な直列化可能性とは、ある操作が別の操作の開始前に完了した場合、データベースはその順序を反映しなければならないというものです。
したがって、テスト対象の分散データベースの安全性不変条件は厳密な直列化可能性であり、ライブネス不変条件は単にVSRのライブネス特性、つまり多数のノードがオンラインである限り応答性を維持することであると言えます。
[画像]
これらの不変条件をテストする1つの方法は、ブラックボックスジェネレーティブテストとフォールトインジェクションをJepsenスタイルで組み合わせることです。Jepsenは、システムの固有の非同期性と非決定性を受け入れ、ユーザー可視APIを通じてシステムを外部からテストします。これには以下が含まれます。
- 広大な状態空間をプローブするためのランダムな入力の生成
- システムへの障害の適用
- 安全性およびライブネスの不変条件が維持されているかどうかの確認
昨年、私たちは実際にそれを行い、Jepsenレポートからの抜粋は以下の通りです。
Flexible quorums and protocol-aware recovery with Viewstamped Replication integration does not appear to have compromised the key invariant of Strong Serializability.
これは素晴らしいニュースです!Jepsenの評価によると、私たちはユーザーへの保証を維持していました。これは、TigerBeetle上で開発される金融アプリケーションは、これらの強力な保証を想定して開発されているため、非常に重要です。これらのアプリケーションは、私たちが約束する厳密な直列化可能性に依存しています。
しかし、JepsenスタイルのジェネレーティブテストとAntithesisスタイルの決定論的ハイパーバイザーは、ユーザー可視APIを通じてシステムを外部からテストします。API境界で見えない不変条件についてはどうでしょうか?基盤となるインフラストラクチャについては、より良いテストを行う必要があります。外部から内部へだけでなく、内部から外部へもテストする必要があります。
TigerBeetleは、決定論的分散データベースとして明示的に設計されています。データベースにおける決定論的実行のアイデアは新しいものではありません。FoundationDBとDropboxの同期エンジンは、決定論的シミュレーションテストと並んで、その設計で決定論を利用していることが知られています。
したがって、FoundationDBのように、TigerBeetleは論理的決定論を持っています。すべてのデータベースコードは決定論的であり、制御プレーンではマルチスレッド並行処理が回避されます。
しかし、さらに進んで物理的決定論も保証します。これにより、TigerBeetleクラスター内のレプリカはバイト単位で同一の状態に収束します。つまり、クラスター内のすべてのレプリカで、同じ物理的な場所が同じコンテンツに対応します。
[画像]
この論理的および物理的決定論により、TigerBeetleは決定論的シミュレーションテストに適したものになります。これにより、実際の合意およびストレージエンジンのコードを、VOPRと呼ぶシミュレーターで実行できます。VOPR内では、ストレージやネットワークのような非決定的な物理的相互作用は制御可能なバージョンに置き換えられ、時間がシミュレートされます。これにより、単一のマシン上で、単一のプロセスで、数桁高速化された時間をかけて分散データベースを実行できます。
データベースの状態空間を探索するためにランダムなシナリオを生成します。ネットワークパーティション、ディスク破損、レプリカ障害などを、並行クライアント操作の存在下で発生させ、さまざまな安全性とライブネスの不変条件をテストします。
時間がシミュレートされるため、本番環境で発生するのに数ヶ月かかるシナリオを数分で探索できます。これにより、バグが隠れがちな微妙なイベントのインターリーブを迅速に見つけることができ、バグが見つかれば、繰り返し決定論的に再現できます。したがって、DSTにより開発者はより速くテストおよびデバッグできるようになり、その結果、より速く構築できるようになります。
しかし、今日はDSTの少し異なる側面について話したいと思います。私たちはDSTを使用してTigerBeetleを内部から外部へテストします。これは、各レプリカの合意およびストレージレベルの状態への完全な可視性を持つことを意味します。このプロトコル認識により、システムの内部を覗き込み、難しい質問を投げかけることができます。
[画像]
データベースレベルだけでなく、合意およびストレージレベルでも安全性不変条件を深くチェックできます。これらの安全性不変条件のテストは、安全性が階層的であるため重要です。合意またはストレージにおける安全性不変条件の違反は、最終的にデータベースが厳密な直列化可能性というコアの安全性不変条件を違反する可能性があります。
このため、本番環境とテストの両方でこれらの安全性不変条件を強制します。本番環境ではアサーションを有効にして実行し、違反が検出された場合はレプリカをクラッシュさせ、壊滅的な安全性違反を利用可能性違反にダウングレードします。しかし、本番環境でグローバルなクラスターレベルのコンテキストを収集するのはコストがかかる場合があるため、これらのコストのかかるチェックはプロトコル認識型DSTに任せています。
[画像]
合意の安全性
合意プロトコルにおける安全性不変条件は合意です。つまり、リクエストがすべてのレプリカ間で同じ順序でライトアヘッドログ(WAL)を通じてコミットされることを確認します。
本番環境では、バックアップがプライマリからコミットメッセージを受信したときにWALの一貫性を検証します。バックアップのWALがプライマリから逸脱していることを観察した場合、プロトコルの安全性不変条件を違反したことを意味するため、バックアップをクラッシュさせます。これは決して起こってはならないことなので、安全性違反を利用可能性違反にダウングレードします。
fn on_commit(self: *Replica, message: *const Message.Commit) void {
assert(message.header.command == .commit);
if (self.journal.header_with_op(message.header.commit)) |commit_entry| {
if (commit_entry.checksum == message.header.commit_checksum) {
log.debug("{}: on_commit: checksum verified", .{self.log_prefix()});
} else if (self.valid_hash_chain_between(message.header.commit, self.op)) {
@panic("commit checksum verification failed");
}
ただし、これはプライマリから受信した定期的なコミットメッセージによって駆動されるため、すべての一つのリクエストに対して一貫性をチェックする機会は提供されません。
プロトコル認識型DSTを使用すると、この不変条件をさらに深く検証できます。レプリカで新しいリクエストがコミットされるたびに、シミュレーターは、そのリクエストが別のレプリカでコミットされていた場合、それらのチェックサムは一致しなければならないとアサートします。実質的に、WAL内のコミットされたすべての一つのリクエストがすべてのレプリカ間で一貫していることを確認します。
assert((commit_a == commit_b) == (checksum_a == checksum_b));
ストレージの安全性
ストレージエンジンにおける安全性不変条件は、ストレージの決定論です。TigerBeetleクラスター内のレプリカは、バイト単位で同一の状態に収束しなければなりません。これは、各レプリカ上のLSMツリーが、コンパクションのようなサブプロトコルを全く同じように実行し、ディスク上に全く同じデータを生成することを意味します。物理ストレージの決定論は、本番環境でのオペレーターエクスペリエンスを向上させ、より高速な分散リカバリとレプリカ状態のオンライン検証を可能にします。
本番環境での実行時、プライマリレプリカのcheckpoint_id(インデックスデータ構造への参照のチェックサム)を使用して、ストレージが決定論的であるかどうかを論理的にチェックします。バックアップのcheckpoint_idがプライマリから逸脱していることを観察した場合、バックアップをクラッシュさせ、安全性違反を利用可能性違反にダウングレードします。
if (message.header.checkpoint_id != self.superblock.working.checkpoint_id() and
message.header.checkpoint_id !=
self.superblock.working.vsr_state.checkpoint.parent_checkpoint_id)
{
@panic("checkpoint diverged");
}
プロトコル認識型DSTを使用すると、これらのインデックスをさらに深く掘り下げることで、この論理チェックをさらに進めます。例えば、オンディスクLSMツリー上のインデックスであるManifestについては、すべてのレベルにわたるすべてのテーブルのメタデータをチェックサム化し、ツリーの構造がすべてのレプリカ間で完全に一貫していることをアサートします。
fn manifest_levels_checksum(forest: *const Forest) u128 {
var checksum_stream = vsr.ChecksumStream.init();
for (0..constants.lsm_levels) |level| {
checksum_stream.add(std.mem.asBytes(&level));
inline for (Forest.tree_id_range.min..Forest.tree_id_range.max + 1) |tree_id_u16| {
const tree_id: Forest.TreeID = @enumFromInt(tree_id_u16);
const tree_level = forest.tree_for_id_const(tree_id).manifest.levels[level];
var tree_tables = tree_level.tables.iterator_from_index(0, .ascending);
checksum_stream.add(std.mem.asBytes(&tree_id));
checksum_stream.add(std.mem.asBytes(&tree_level.table_count_visible));
while (tree_tables.next()) |tree_table| {
checksum_stream.add(std.mem.asBytes(&tree_table.encode(.{
.tree_id = tree_id_u16,
.event = .insert, // (Placeholder event).
.level = @intCast(level),
})));
}
}
}
return checksum_stream.checksum();
}
最後に、プロトコル認識型DSTを使用すると、ストレージが決定論的であるかどうかを物理的にもチェックします。これらのすべてのインデックスをウォークし、実際のデータ(スーパーブロック、グリッド、クライアント応答)をチェックサム化し、レプリカがバイト単位で同一であることをアサートします。
checkpoint.put(
.superblock_checkpoint,
vsr.checksum(std.mem.asBytes(&superblock.working.vsr_state.checkpoint)),
);
checkpoint.put(.client_replies, checker.checksum_client_replies(superblock));
checkpoint.put(.grid, checker.checksum_grid(Forest, forest, .free_set_from_disk));
システムのライブネス不変条件は、多数のレプリカがオンラインである限りユーザーリクエストに応答し続けることでした。しかし、このシステムレベルの可用性をテストするだけでは十分ではありません。多数のレプリカがあれば、可用性の幻想を提供できます。リクエストに応答するには十分ですが、残りは停止している可能性があります!
プロトコル認識型DSTを使用すると、システム全体に対するライブネス不変条件を定義する代わりに、より厳格なライブネス不変条件を定義し、個々のレプリカごとに強制できるようになります。つまり、レプリカが総順序を保証しながら、耐久性を可能な限り効率的に可用性に変換しているかどうかを確認できます。
ローカル耐久性から可用性へ
そのため、レプリカがローカル耐久性を効率的に使用しているかを確認します。例えば、レプリカがクラッシュして再起動した場合、クラスターとの調整が必要になることがあります。特に、WALの先頭に破損がある場合は調整が必要です。しかし、自身で回復できるだけのローカル耐久性がある場合、調整すべきではありません。
[動画]
そのため、WALに破損がない場合、レプリカは決して調整が必要な状態にならないことをアサートします。これは重要です。なぜなら、すべてのレプリカが同時にクラッシュして再起動し、不必要に調整するシナリオを想像してみてください。その場合、クラスターは停止してしまいます。これは深刻なライブネスの問題です!
if (replica.status == .recovering_head) {
// Even with faults disabled, a replica may wind up in
// status=recovering_head, in case of a header-prepare view mismatch.
assert(fault or header_prepare_view_mismatch);
}
グローバル耐久性から可用性へ
レプリカがクラスターのグローバル耐久性を効率的に使用しているかどうかも確認します。例えば、各レプリカが9ブロックのうち6ブロックを失っているが、集合的にすべてのブロックがクラスター内のどこかに存在するシナリオを考えてみましょう。
これは、ほとんどの合意プロトコル(オリジナルのVSRを含む)が、通常 想定しているリカバリは、正常なレプリカから完全な状態をコピーすることです。しかし、TigerBeetleのプロトコルは少し異なります。ブロックの残りがクラスター内に1つしかない場合でも、すべてのコピーを回復できます。各レプリカは物理的ストレージの決定論を利用し、状態全体をコピーするのではなく、他のレプリカから個々の正常なブロックのみを取得します。
[動画]
そして、プロトコル認識型DSTを使用すると、これらのシナリオでレプリカが回復できることをテストできます!つまり、各レプリカが他のレプリカ上の正常なコピーから失われたブロックを修復することをアサートできます。もしブロックが失われたままであれば、それはすべてのレプリカで失われている必要があります。
while (blocks_missing.next()) | block_missing | {
for (simulator.cluster.replicas) |replica| {
const storage = &simulator.cluster.storages[replica.replica];
if (storage.area_faulty(.{
.grid = .{ .address = block_missing.address },
})) continue;
const block = storage.grid_block(block_missing.address) orelse continue;
const block_header = schema.header_from_block(block);
if (block_header.checksum == block_missing.checksum) {
@panic("block found");
}
}
}
ここでも、DSTのプロトコル認識のおかげで、これらの安全性とライブネスの不変条件を深くテストできるのです。これは、単に決定論的に実行し(ハイパーバイザーのように)、システムレベルの不変条件の違反を見つける(Jepsenのように)だけではありません。
代わりに、私たちのDSTは実際にプロトコル自体を理解し、各レプリカのストレージと合意レベルの状態への可視性を持っています。繰り返しになりますが、基盤となるインフラストラクチャについては、外部から内部へだけでなく、内部から外部へもテストする必要があります。
この可視性により、安全性とライブネスの不変条件を深くテストする以上のことができます。例えば:
- 精密に手作業で作成されたシナリオのテストとデバッグ。プロトコルに対して「もし~だったらどうなるか?」という質問を30〜40行のコードで投げかけ、ミリ秒単位で明確な回答を得ることができます。
- ハードウェアでのベンチマークに伴うばらつきや複雑さなしに、プロトコルレベルの最適化を確実にベンチマークできます。
これらは、BugBash '26での私の講演でカバーされています。さらに深く掘り下げたい場合は、ぜひご覧ください!