Deterministic simulation testing

Deep dive

How it works

Parts:

• Seeded PRNG — the only randomness; every fault decision draws from it.
• Virtual clock — a counter that jumps to the next event time; now() never reads the OS.
• Event queue — min-heap on (time, id); a discrete-event simulation core.
• Simulated network and disk — the PRNG decides drop, delay, reorder, duplicate, corrupt, partition.
• Nodes — production logic behind traits (Clock, Network, Storage, Rng).
• Checkers — safety invariants after every event; liveness (progress once faults stop).

1. Pick a seed; derive fault rates from it (calm and nasty runs are both useful).
2. Build N nodes on simulated I/O; seed the queue with client operations.
3. Pop the earliest event, set the clock to it, run the handler; handlers only enqueue events.
4. Faults are events too: crash node k at t, partition {1,2}|{3} until t+d, corrupt a read.
5. Run the checkers after each event; on a violation print the seed and commit.
6. Replay with the same seed and commit; shrink by cutting inputs.

seed ─► PRNG ─► fault plan ─► ┌──── event queue (time, id) ────┐
                              │ deliver · timer · crash · heal │
                              └───────┬──────────────┬─────────┘
                              nodes 0..N (real code)  checkers ─► fail ⇒ print seed

What must be deterministic: time (no Instant::now), I/O (all through the simulator), randomness (one seeded stream, no thread_rng), thread scheduling (one thread, or a PRNG-driven scheduler), and hash-map iteration order (Rust's HashMap seeds its hasher per process: use BTreeMap, a fixed hasher, or sort first).

Fault injection. FoundationDB's docs call swizzle-clogging the champion pattern: pick a random subset of nodes, stop their network connections one by one over a few seconds, then restore them in random order. Buggification (BUGGIFY in FoundationDB) places hooks inside production code; in simulation each site is activated per run with probability 0.25 and then fires with 0.25 (flow/Buggify.h defaults), forcing rare paths such as early timeouts and tiny buffers.

Shrinking. There is no general automatic minimiser. Keep the seed and cut inputs (fewer operations, nodes or fault events), keeping the last version that still fails. Cutting changes how the PRNG stream is consumed, so use separate streams for workload and faults, or log decisions and replay them.

Versus neighbours. Model checking explores a model exhaustively for small state spaces; DST samples the real code randomly at scale and proves nothing. Jepsen-style testing is black-box: real processes and network, a nemesis, a history checker; no code changes, but runs do not repeat. Fuzzing mutates inputs, DST the schedule; record-replay captures one real execution, DST generates them.

Code

A 3-node ping/counter protocol on a priority-queue event loop. Node 0 sends Inc(seq) to followers 1 and 2 and retries until acked; the seed decides drops and delays. Planted bug: with bug set, followers apply retransmissions again.

use std::cmp::Reverse;
use std::collections::{BTreeSet, BinaryHeap};

struct Rng(u64); // splitmix64: one u64 of state, any seed (including 0) is fine
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }
    fn below(&mut self, n: u64) -> u64 { self.next() % n }
}

// Event = (time, id, kind, to, seq); `id` breaks time ties.
const INC: u64 = 0; const ACK: u64 = 1; const ISSUE: u64 = 2; const RETRY: u64 = 3;
type Ev = (u64, u64, u64, u64, u64);

struct Sim {
    now: u64, next_id: u64, rng: Rng, q: BinaryHeap<Reverse<Ev>>,
    trace: u64, // FNV-1a hash of every event handled
}
impl Sim {
    fn at(&mut self, delay: u64, kind: u64, to: u64, seq: u64) {
        self.next_id += 1;
        self.q.push(Reverse((self.now + delay, self.next_id, kind, to, seq)));
    }
    /// The only way nodes talk: the seed decides drop (10 %) and delay (1..=8).
    fn send(&mut self, kind: u64, to: u64, seq: u64) {
        if self.rng.below(10) == 0 { return; }
        let d = 1 + self.rng.below(8);
        self.at(d, kind, to, seq);
    }
}

/// Leader 0 sends Inc(seq) to followers 1 and 2, retries until acked.
/// `bug`: followers apply every Inc they receive, with no duplicate check.
fn run(seed: u64, ops: u64, bug: bool) -> (u64, Result<(), String>) {
    let mut s = Sim { now: 0, next_id: 0, rng: Rng(seed), q: BinaryHeap::new(), trace: 0xcbf2_9ce4_8422_2325 };
    let mut counter = [0u64; 3];                  // followers' counters (index 0 unused)
    let mut seen: [BTreeSet<u64>; 3] = Default::default();
    let mut acked: BTreeSet<(u64, u64)> = BTreeSet::new();
    let mut issued = 0;
    for i in 1..=ops { s.at(10 * i, ISSUE, 0, i); }
    while let Some(Reverse((t, id, kind, to, seq))) = s.q.pop() {
        s.now = t;
        for x in [t, id, kind, to, seq] { s.trace = (s.trace ^ x).wrapping_mul(0x100_0000_01b3); }
        match kind {
            ISSUE => { issued += 1; for f in 1..=2 { s.send(INC, f, seq); s.at(20, RETRY, f, seq); } }
            RETRY if !acked.contains(&(to, seq)) => { s.send(INC, to, seq); s.at(20, RETRY, to, seq); }
            INC => {
                if bug || seen[to as usize].insert(seq) { counter[to as usize] += 1; }
                s.send(ACK, 0, seq * 10 + to);   // pack (follower, seq) into one u64
            }
            ACK => { acked.insert((seq % 10, seq / 10)); }
            _ => {}
        }
        // invariant, checked after every event: no follower is ahead of the leader
        for f in 1..=2 {
            if counter[f] > issued { return (s.trace, Err(format!("t={t}: follower {f} counter {} > issued {issued}", counter[f]))); }
        }
        if s.now > 10_000 { break; } // cap runaway retries
    }
    (s.trace, Ok(()))
}

fn main() {
    // 1. same seed, identical trace; 2. different seeds, different traces
    for seed in 0..50 { assert_eq!(run(seed, 5, true), run(seed, 5, true)); }
    let distinct: BTreeSet<u64> = (0..1000).map(|s| run(s, 5, false).0).collect();
    assert!(distinct.len() > 900);
    assert!((0..1000).all(|s| run(s, 5, false).1.is_ok())); // correct version never fails
    // 3. the planted bug is found by some seed
    let fails = |s: &u64| run(*s, 5, true).1.is_err();
    let seed = (0..1000).find(fails).expect("bug not found");
    println!("{} distinct traces; first failing seed {seed}; {}/1000 fail",
             distinct.len(), (0..1000).filter(fails).count());
    // 4. replay is exact
    let (h1, e1) = run(seed, 5, true);
    assert_eq!((h1, &e1), (run(seed, 5, true).0, &run(seed, 5, true).1));
    println!("replay seed {seed}: {:?} trace {h1:016x}", e1.unwrap_err());
    // 5. shrink: fewest operations that still fail
    println!("shrunk to {:?} ops", (1..=5).find(|&n| run(seed, n, true).1.is_err()));
}

Run (release): 1000 seeds give 1000 distinct trace hashes; the buggy version first fails at seed 1 and fails for 649 of 1000; the replay prints the identical violation and hash; the seed shrinks to 2 operations; the correct version never fails.

Complexity and constants

• Per event: one heap push and pop, O(log n) in pending events; the handler dominates.
• Virtual time: waits cost nothing. TigerBeetle states one minute of VOPR time equals days of real-world testing (docs).
• All N nodes live in one process, so cluster size is bounded by RAM.

Efficiency

• Cost: CPU of the code under test plus a heap operation per event; no real network, disk or waiting. Bound: one core per seed. Scale comes from seeds in parallel (FoundationDB runs "tens of thousands of simulations every night", docs).
• Levers:
  • virtual clock — idle waits and timeouts cost nothing (FDB docs) — timeout-heavy protocols
  • stop at the first violation, keep seed and commit — cheap triage (VOPR docs) — always
  • assertions on in tests — catch what checkers miss (TigerBeetle even in production, VOPR docs) — always
• Naive → standard → state of the art:
  • chaos tests on a real cluster · wall-clock, not repeatable
  • in-process simulator with injected traits · virtual time, repeatable by seed
  • deterministic hypervisor (Antithesis) · no code changes, hosted service

Implementation notes

• One World owns clock, queue and RNG; no globals to forget. Break time ties with an increasing id.
• Separate RNG streams (network, disk, workload) from the seed, so a new disk fault does not reshuffle network decisions.
• Hash the trace per event; run each seed twice in CI and compare: the first divergence is the leak.
• Lamport, vector and hybrid logical clocks run on virtual time unchanged; test leases by skewing node clock rates.

Pitfalls

• One Instant::now(), thread_rng(), HashMap iteration or stray thread breaks replay; the bug "disappears".
• Too gentle finds nothing; too hostile (always partitioned) never reaches deep states.
• Checking only at the end misses transient violations.
• Simulated disks must lose unsynced writes and tear writes.

Variants and alternatives

In production

FoundationDB (database), TigerBeetle (financial ledger; VOPR), RisingWave (stream processing; via madsim) and Antithesis (hosted platform).

Implementations

Sources

• FoundationDB docs, Simulation and Testing. docs
• Will Wilson, Testing Distributed Systems w/ Deterministic Simulation, Strange Loop 2014. talk
• TigerBeetle, Deterministic Simulation Testing. docs · live simulator
• Antithesis. site
• Burckhardt et al., A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs, ASPLOS 2010 (PCT, used by Shuttle). paper
• Jepsen. site · code