I have been reading about deterministic simulation testing (DST) for a while, and in this post I summarize what DST is and how one can implement it.

The idea is not new, but the FoundationDB team made it widely known with Will Wilson’s talk at Strange Loop in 2014. Since then, many systems have adopted it.

In distributed production systems, a failure that requires three things to go wrong in the same millisecond happens once and never again. Debugging such issues is hard. And the reason is not complexity. It is not being able to reproduce the bug.

With DST, you run the whole distributed system in a simulation, where every random decision comes from one random number generator with a known seed. The same seed results in the same run, bit for bit. DST makes the entire execution of a distributed system a pure function of one number:

(code, seed) -> identical execution -> identical result

The run is still random: nodes crash, the network drops, reorders, or duplicates packets, and disks corrupt data. But every one of those decisions is drawn from a single seeded generator, so the run is reproducible.

This is the part I find most valuable. If a bug shows up under seed=0xC0FFEE, you replay 0xC0FFEE on your laptop and step through the identical execution in a debugger. You understand it, write a fix, and then run the same seed again to check that the fix holds.

Requirements

There are three requirements for a proper DST implementation.

Single Threaded Pseudo Concurrency

The simulation must look concurrent, running many nodes plus the network between them. However, it cannot actually be concurrent, because operating system threads are themselves a source of non-determinism.

Everything should run on one physical thread, and a scheduler you implement picks the next action.

The FoundationDB team built Flow, a compiler extension that turns actor-style code into single threaded callback state machines. Waiting means registering a continuation, never parking a thread.

Simulated Outside World

Every outside system (network, disk, clock) gets a simulated implementation behind the same interface as the real one.

For example, a simulated connection is just an object with buffers that waits for a seeded delay and copies bytes. A simulated disk read has a seeded chance of returning an error instead of the data.

As Wilson puts it in the talk, “all that randomness, all that entropy, needs to be randomness and entropy that you put there on purpose.”

Process Determinism

This requirement sounds free once you have the first two, but it is not.

Every random number must come from the seeded generator, so the seed becomes part of the program’s input.

For example, reading the system clock or checking free disk space in an if statement makes the program non-deterministic. Developers have to be trained to avoid such calls, and the FoundationDB team admits they still get it wrong. So they run a share of their simulations twice with the same seed and compare the results. If the two results differ, some code is still reading something it should not. And you will have to find and remove it.

Finding Bugs Faster Than Production

Users run your system on far more different setups than your test infrastructure covers, on hardware that fails in ways you never imagine. Between them, they explore much more of your system’s state space than your tests do.

The goal of DST is to reach parts of that state space that would take decades to hit in production. In his talk, Wilson frames this in one sentence: “you need to find more bugs per CPU hour than the real world, by many orders of magnitude.”

Three things make that possible:

  • Fail Often: A real disk fails every few years, a simulated disk fails every few minutes. The failure handling code runs thousands of times more often than it ever would in production.
  • Compress Time: The clock is virtual. When the cluster is idle or waiting out a recovery timeout, the simulator jumps straight to the next event, so simulated seconds pass much faster than wall-clock seconds.
  • More Runs: The FoundationDB team runs tens of thousands of simulations every night, each one injecting large numbers of component failures. They estimate the total so far as the equivalent of roughly one trillion CPU hours of testing.

DST in Java

The best known DST implementations are not on the JVM: FoundationDB is written in C++, TigerBeetle in Zig, and Turso Database in Rust. But the recipe is language agnostic. So I am building a new system in Java, a replicated log, with DST in mind from the start.

The core of the system touches time, network, disk and randomness only through interfaces handed to it at construction. The entry point decides those implementations:

// production gets the real world
Server prod = new Server(config, systemClock, tcpNetwork, fileStorage, secureRandom);

// simulation gets implementations derived from one seed
Simulation sim = new Simulation(seed);
Server simulated = new Server(
    config,
    sim.clock(),
    sim.network(),
    sim.storage(),
    sim.random()
);

The same server code runs in production and in simulation, only the injected implementations differ

The simulator behind those interfaces has four parts.

  • One Event Loop on One Thread: A priority queue of events keyed by (virtualTime, tieBreak, sequence). The tie-break is drawn from the seeded generator when the event is inserted, so events scheduled for the same instant run in a seeded random order. A different seed gives a different interleaving of the same workload.
  • Virtual Clock: Time is a long that jumps to the timestamp of the next event. There are no sleeps, so the cost of a run tracks the number of events it processes, not the span of time those events cover. A ten-second recovery timeout is one entry in a queue.
  • One Seeded Generator for Everything: All the main decisions draw from the seed: message delays, faults, tie breaks, and workload choices. The seed is printed on every run and on every failure.
  • Trace and a Determinism Test: Every externally visible action is appended to a trace with its virtual timestamp. One test runs the same seed twice and asserts the traces are identical. A second runs two different seeds and asserts the traces differ, which catches a harness that quietly ignores its seed.

That is the whole harness.

Java also helps with the third requirement. A banned-API check in the build fails the compilation when the core calls System.currentTimeMillis, java.util.Random, or Thread.sleep directly, so process determinism is enforced before the tests even run. I will describe that setup in later posts.

Conclusion

I am still early on this.

In this post we looked at what DST is, the three requirements for implementing it, and the possible harness snippet in Java.

The next posts will go into the details with an example replicated log project.

References