Protocol-Aware Deterministic Simulation Testing

Systems Distributed '26 in Boston

Get Tickets ↓

-->

TigerBeetle’s deterministic simulator is protocol-aware, which<br>enables us to test safety and liveness invariants not just at the<br>database level, but also at the level of each individual<br>replica.

if (replica.status == .recovering_head) assert(fault);

In this post, we cover the mechanics, method, and merits of going<br>beyond traditional, black-box methods of testing distributed<br>systems – generative testing (for example, Jepsen), and deterministic hypervisors<br>(for example, Antithesis)<br>– to deeply test safety and liveness invariants using protocol-aware<br>DST. If you prefer, watch a<br>talk<br>in which I cover this and more.

Invariants

To begin, some background on safety and liveness invariants,<br>consensus protocols, and deterministic simulation testing. For those who<br>don’t require a refresher, feel free to jump to Protocol-Aware DST!

Distributed systems, i.e. systems with multiple interacting nodes,<br>are notoriously hard to get right, as they require developers to reason<br>about concurrent execution on multiple machines, and the state space of<br>their interleavings is vast. Now, we can attack testing such a system<br>from multiple angles, but today, let’s start with invariants.<br>While testing your distributed system, it is crucial you identify two<br>sets of invariants:

Safety: which means nothing bad ever happens. For example,<br>two nodes never return different results for the same request.

Liveness: which means something good eventually happens.<br>For example, a request will eventually be responded to provided enough<br>nodes are online.

Your testing must then attempt to ascertain whether your system<br>upholds these safety and liveness invariants.

Let us consider a specific distributed system: a consensus-based<br>system. In this system, a consensus protocol is what turns durability<br>into availability, safely. Put simply, a consensus protocol uses the<br>redundancy in the system to provide fault tolerance, while maintaining<br>the illusion of a single node. At a high level, a consensus protocol<br>guarantees the following:

Fault Tolerance

This entails ensuring that faults like process crashes, network<br>partitions, and storage corruptions are tolerated and masked. This is<br>typically achieved via replication, i.e. maintaining multiple copies of<br>the data for redundancy. Algorithms of the Viewstamped<br>Replication flavor guarantee responsiveness as long as a majority of<br>replicas are online. For example, in a system with 3 replicas (where the<br>majority is 2 replicas), they can tolerate up to 1 fault.

This is the liveness invariant of a consensus protocol.

Agreement

This entails ensuring that the multiple copies of the data in the<br>system are consistent with one another. One way to achieve this is by<br>electing a primary replica. All requests flow through the primary, and<br>the order in which the primary executes operations is the order all<br>backups follow, ensuring data consistency.

This is the safety invariant of a consensus protocol.

TigerBeetle is a distributed database that uses VSR for fault<br>tolerance and agreement. Routing all requests through the primary<br>guarantees strict<br>serializability, which is the strongest level of isolation a<br>database can guarantee. Simply put, strict serializability posits that<br>if one operation completes before another begins, the database must<br>reflect that order.

Therefore, we can say that the safety invariant of our distributed<br>database under test is strict serializability, and the liveness<br>invariant is simply the liveness property of VSR, i.e. staying<br>responsive as long as a majority of nodes are online.

Testing From The Outside In

Now, one way to test these invariants is using black-box generative<br>testing, coupled with fault injection, Jepsen-style. Jepsen tests the<br>system from the outside in, using user-visible APIs, embracing the<br>inherent asynchrony and non-determinism in the system. This<br>involves:

Generating random inputs to probe the vast state space

Subjecting the system to faults

Asserting whether the safety and liveness invariants are upheld

Last year, we did do that, and here is an excerpt from our Jepsen<br>report:

Integrating Viewstamped Replication with flexible quorums and<br>protocol-aware recovery does not appear to have compromised the key<br>invariant of Strong Serializability.

That’s wonderful news! As per our Jepsen evaluation, we were still<br>upholding our guarantees to our users, which is crucial because the<br>financial applications that are typically developed on top of<br>TigerBeetle are developed assuming these strong guarantees. These<br>applications rely on the strict serializability we promise them.

However, Jepsen-style generative testing and Antithesis-style<br>deterministic hypervisors test the system from the outside in, via<br>user-visible APIs. What about the invariants that aren’t visible at the<br>API boundary? For foundational infrastructure, we must do better. We<br>must test not only from the...