Simcraft
Open web IDE

Deterministic simulation testing of a simulation engine#

Deterministic simulation testing (DST) runs a program inside a simulator that controls time, scheduling, and randomness. Every choice the environment would make comes from one seeded generator, so a seed reproduces a whole run, including the failure you are looking for. FoundationDB made the approach well known. TigerBeetle and Resonate build on it, and recent write-ups by Dominik Tornow and Unmesh Joshi explain it in depth.

Those projects wrap a simulator around a database or a runtime. A simulation engine starts from the other end. It already has a virtual clock, an event calendar, and seeded randomness, because a modeler expects the same seed to give the same run. Most of what DST asks for is part of the product. This post describes how Simcraft keeps that property and what we test with it.

The inputs to a run#

A run can differ from its replay in three places: the clock, the order of work, and the random draws. A distributed system adds the network and the disk. Inside a Simcraft run there is no network and no disk, so the engine only has to control those three.

documentexperimentparametersseedenginecalendar: (time, phase, sequence)virtual clockone thread per runseeded stream per componentresultsevent stream
The same five inputs give byte-identical results and events. The fifth input, external inputs, is left out here.

The OSDL specification states this as a contract: a run is a pure function of the document, the experiment, the parameter overrides, the seed, and any external inputs the run accepts. Within one engine version, a replay of that tuple is bit-exact.

Time and order#

The engine keeps its own clock and never reads the wall clock during a run. The clock jumps from one scheduled entry to the next, so a quiet stretch of simulated time costs nothing to run.

Order comes from the calendar. Each entry sorts by time, then by phase, then by a counter that goes up by one for each entry scheduled:

rust
impl Ord for Entry {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.time
            .total_cmp(&other.time)
            .then(self.phase.cmp(&other.phase))
            .then(self.sequence.cmp(&other.sequence))
    }
}

Work at the same time runs in three phases: drive, act, and record. Within a phase, entries run first in, first out. Models cannot set a priority, so there is no second ordering rule to get wrong. The kernel runs one entry at a time on one thread.

Randomness#

An experiment can sweep several sets of parameter values, called scenarios, and run each one several times. Each of those runs is a replication.

Each component draws from its own random stream. The engine hashes the root seed, the scenario index, and the replication number into a replication seed. It then hashes that seed with each component id to seed a PCG generator:

rust
let replication_seed = fnv1a(&[
    &self.experiment.root_seed.to_le_bytes(),
    &scenario_seed_index.to_le_bytes(),
    &(u64::from(replication)).to_le_bytes(),
]) & ((1u64 << 53) - 1);

// One stream per component, keyed by the component id.
Pcg64Mcg::new(fnv1a(&[&seed.to_le_bytes(), label.as_bytes()]) as u128 | 1)
root seedscenario 0 · rep 0scenario 0 · rep 1scenario 1 · rep 0arrivalsteller……
No stream depends on another stream's draws, or on which thread runs the replication.

Two results follow. Adding a component does not shift the draws of the others. And replications can run on any number of threads: each has its own seed, engines share no state, and the runner delivers events in replication order. One test runs a parameter sweep on 1, 2, 3, 4, and 16 threads and requires equal results and equal event streams.

The samplers are fixed as well. The specification names the algorithm for each distribution, including how many draws it uses, so a dependency update cannot change a normal or gamma sample. The engine writes golden vectors, a committed list of its expected draws. The reference machine must reproduce them bit for bit. It is an executable version of the specification, written in Lean.

Seeds in the browser#

The model below is the M/M/1 queue from the OSDL examples: one server, random arrivals, and random service times. It has three experiments, Seed 1, Seed 2, and Seed 3, which differ only in their seed. The run happens in your browser, on the WebAssembly build of the engine.

Run Seed 1, reset, and run it again. The queue takes the same path both times, and over 150 time units it holds 5.14 customers on average. Choose Seed 2 in the Experiment list and the queue takes a different path, with an average of 7.45.

What the tests check#

The tests use replay in two ways. They check that a run still replays exactly, and they search for bugs, knowing that any failure they find will run again from its seed. The engine's property tests use proptest, a Rust library for property-based testing. For each case, proptest generates a model and a seed. One property varies the patient count of the hybrid clinic example, which combines discrete-event, agent-based, and system dynamics parts:

rust
let (first_result, first_events) = run_recorded(&doc, seed, EventVerbosity::Trace);
let (second_result, second_events) = run_recorded(&doc, seed, EventVerbosity::Trace);
prop_assert_eq!(&first_result, &second_result);
prop_assert_eq!(&first_events, &second_events);

let without_observer = run_unobserved(&doc, seed, EventVerbosity::Trace);
let (lifecycle, _) = run_recorded(&doc, seed, EventVerbosity::Lifecycle);
prop_assert_eq!(&first_result, &without_observer);
prop_assert_eq!(&first_result, &lifecycle);

The last two assertions matter more in a simulation engine than in a database. Recording is part of the engine. If a recorder drew a random number or scheduled an entry to sample state, opening a chart would change the run on the chart. The test makes that a failure.

Other properties check conservation. Entities created equal entities disposed plus entities still in the model. An agent that leaves its population and comes back is never lost or copied. A closed loop of stocks and flows keeps its total. Each component library also has its own exact-replay properties.

When a property fails, proptest shrinks the case to the smallest model and seed that still fail, and saves it to a file in the repository. Every later run replays the saved cases first.

generatemodel + seedrun 3 waystwice, unobservedcompare+ invariantspass: nextfailshrink, commit seedregressions filereplayed first on every run
A bug that exploration finds becomes a fixed regression case.

Agreement with other implementations#

A run that agrees with itself can still be wrong. Determinism also makes it possible to compare one implementation with another by their traces. A trace is the full list of events a run emits. Without determinism, two traces can differ by chance. With it, any difference is a bug in one of the implementations.

ComparisonWhat must match
Engine and reference machineThe recorded results and events of each conformance case. For the cases that pin down the engine's internal order, every state change too, with numbers compared bit for bit.
Components built into the engine, and the same components loaded as WebAssembly pluginsThe events and the outcome of each test case.
Browser engine and server engineThe event stream for the same seed, with run ids removed.
One worker thread and severalResults and the event stream.

Limits#

Bit-exact replay holds within one engine version. A change to the engine can change a trace. The conformance cases define which changes break compatibility.

Proptest only builds the kinds of model we wrote generators for. It cannot find a bug that only appears in another kind of model. In CI, each property runs 24 to 64 cases. A deeper run, such as PROPTEST_CASES=512, is manual.

DST tests the engine and nothing around it. It does not test the server, the connection between the browser and the server, or the IDE. TigerBeetle makes the same point about its simulator and tests the full system from outside with Vortex. The comparison between the browser and server engines is our first step in that direction.

The IDE is tested in a similar way, with Bombadil from Antithesis, a company that runs whole systems in a deterministic hypervisor. Bombadil explores the built IDE in a real browser with random clicks and keystrokes, and checks properties such as "the canvas, the code view, and the document agree". Those runs are not deterministic: a failure leaves a trace to inspect, not a seed to replay.

A simulation engine gets most of DST for free. Keeping it takes care in a few places: the engine never reads the wall clock, components never share a random stream, and recording never changes the run.