Deterministic Simulation Testing

Deterministic Simulation Testing (DST)

Overview

DST collapses a multi-node distributed system into a single-threaded simulation where all non-determinism (network, disk, time, randomness) is controlled by a seeded PRNG. Same seed = same execution = perfect reproducibility.

Origin: FoundationDB — "We found all of the bugs in the database." Adopted by TigerBeetle, RisingWave, Dropbox, WarpStream, and others.

When to Use

• Building distributed systems, consensus protocols, sync engines, replicated state
• Code with network I/O, disk I/O, timers, or concurrency
• Flaky tests caused by race conditions or timing
• Need to find bugs that only manifest under rare failure combinations
• Want reproducible failure cases from randomized testing

When NOT to use:

• Pure computational code with no I/O or concurrency
• Simple CRUD apps without distributed state
• Performance benchmarking (simulation doesn't measure real performance)

The Three Pillars

1. I/O Abstraction

Every interaction with the outside world goes through an interface that can be swapped for simulation.

┌─────────────────────────────┐
│       Application Logic     │
├─────────────────────────────┤
│       I/O Interface Layer   │
├──────────┬──────────────────┤
│ Real I/O │ Simulated I/O    │
│ (prod)   │ (test)           │
└──────────┴──────────────────┘

What to abstract: Network (TCP/UDP/RPC), Disk (reads/writes/fsync), Time (clocks/timers/sleep), Random (all PRNG sources).

Go example:

// Interface that both real and simulated implementations satisfy.
type Network interface {
    Send(to NodeID, msg []byte) error
    Recv() (from NodeID, msg []byte, err error)
}

type Clock interface {
    Now() time.Time
    Sleep(d time.Duration)
    After(d time.Duration) <-chan time.Time
}

type Storage interface {
    Write(key string, data []byte) error
    Read(key string) ([]byte, error)
    Sync() error
}

2. Single-Threaded Deterministic Execution

All "concurrent" nodes run cooperatively in one thread. A scheduler decides which node runs next, controlled by the seed.

State machine pattern (from sled):

fn receive(msg, at) -> [(msg, destination)]  // Handle incoming message
fn tick(at) -> [(msg, destination)]           // Advance time step

Simulation loop:

type Simulator struct {
    rng     *rand.Rand       // Seeded PRNG — the ONLY source of randomness
    clock   *SimClock        // Virtual time
    network *SimNetwork      // In-memory message queues with fault injection
    storage *SimStorage      // In-memory disk with crash/corruption injection
    events  *PriorityQueue   // Ordered by virtual timestamp
    nodes   map[NodeID]*Node // All nodes in the simulation
}

func (s *Simulator) Run(seed int64, steps int) {
    s.rng = rand.New(rand.NewSource(seed))

    for i := 0; i < steps; i++ {
        event := s.events.Pop()
        s.clock.AdvanceTo(event.Time)

        // Deliver event to target node.
        responses := event.Node.Handle(event.Msg)

        for _, resp := range responses {
            // Network simulation: delay, reorder, drop.
            if s.shouldDeliver() {
                delay := s.randomDelay()
                s.events.Push(Event{
                    Time: s.clock.Now().Add(delay),
                    Node: resp.To,
                    Msg:  resp.Msg,
                })
            }
        }

        s.checkInvariants()
    }
}

3. BUGGIFY — White-Box Fault Injection

Black-box fault injection (network partitions, crashes) can't trigger higher-level distributed failures. BUGGIFY injects faults inside your own code to exercise rare paths.

Three rules:

1. Simulation-only — never fires in production
2. Deterministic per-run — each BUGGIFY site is enabled/disabled for the entire run (decided by seed)
3. Default 25% probability — customizable per site

Go implementation:

var simulationMode bool // Set by test harness, never in production.

// Buggify returns true with the given probability, but ONLY in simulation.
func Buggify(probability float64) bool {
    if !simulationMode {
        return false
    }
    return globalRng.Float64() < probability
}

// Usage in application code:
func (r *Replica) sendHeartbeat() error {
    if Buggify(0.1) {
        // 10% chance: delay heartbeat to test election timeout.
        simClock.Sleep(electionTimeout * 2)
    }
    if Buggify(0.05) {
        // 5% chance: skip heartbeat entirely.
        return nil
    }
    return r.network.Send(r.leader, heartbeatMsg)
}

func (s *Storage) writeBlob(key string, data []byte) error {
    if Buggify(0.02) {
        // 2% chance: partial write (test corruption recovery).
        data = data[:len(data)/2]
    }
    if Buggify(0.01) {
        // 1% chance: fsync failure (test durability guarantees).
        err := s.disk.Write(key, data)
        if err != nil { return err }
        return ErrSyncFailed
    }
    return s.disk.WriteAndSync(key, data)
}

Five BUGGIFY patterns:

Framework Quick Reference

Madsim (Rust) — Key APIs

// Swap deps via Cargo.toml:
// tokio = { version = "0.2", package = "madsim-tokio" }
// Build: RUSTFLAGS="--cfg madsim" cargo test

let mut rt = Runtime::with_seed_and_config(seed, config);
let node1 = rt.create_node().ip(addr1.ip()).build();

// Fault injection:
NetSim::current().clog_node(node_id);     // Disconnect node
NetSim::current().unclog_node(node_id);   // Reconnect
Runtime::check_determinism(seed, config, || async { ... }); // Verify determinism

Turmoil (Rust) — Key APIs

let mut sim = Builder::new()
    .simulation_duration(Duration::from_secs(60))
    .min_message_latency(Duration::from_millis(1))
    .max_message_latency(Duration::from_millis(100))
    .fail_rate(0.05)
    .build();

sim.host("server", || async { /* server code */ Ok(()) });
sim.client("client", async { /* test logic */ Ok(()) });

sim.partition("a", "b");  // Network partition
sim.repair("a", "b");     // Heal partition
sim.crash("server");       // Crash (lose unsynced data)
sim.bounce("server");      // Restart (keep synced data)
sim.run()?;

Go WASM Approach

# Compile to WASM for single-threaded deterministic execution:
GOOS=wasip1 GOARCH=wasm go test -run TestSimulation ./...

# Control seed:
GORANDSEED=12345 go test ...

# Use faketime for deterministic time:
import "github.com/polarsignals/faketime"
clock := faketime.NewClock()  // Controlled by simulator

Test Levels (from TigerBeetle VOPR)

Run simulations at escalating severity:

TigerBeetle achieves 1000x time compression (3.3s simulation = 39min real-world) and runs on 1024 cores continuously.

Invariant Checking

The simulation is only as good as your invariants. Check after every step:

func (s *Simulator) checkInvariants() {
    // Linearizability: every completed operation appears in a valid
    // sequential history.
    s.checkLinearizability()

    // Safety: no two nodes disagree on committed state.
    for i, n1 := range s.nodes {
        for j, n2 := range s.nodes {
            if i >= j { continue }
            assertConsistent(n1.CommittedState(), n2.CommittedState())
        }
    }

    // Liveness: if no faults are active, the system eventually converges.
    if !s.faultsActive && s.clock.Since(s.lastConvergence) > maxConvergenceTime {
        panic("liveness violation: system did not converge")
    }
}

CI/CD Integration

Run multiple seeds in parallel on every commit:

# GitHub Actions example:
strategy:
  matrix:
    seed: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
steps:
  - run: go test -run TestSimulation -seed=${{ matrix.seed }} -steps=100000

RisingWave runs 16 parallel seeds per CI run. WarpStream found bugs that evaded 10,000+ hours of traditional testing.

When a test fails: Log the seed. Reproduce with go test -run TestSimulation -seed=<FAILING_SEED>. Debug deterministically.

Structuring Code for DST

digraph dst_structure {
    rankdir=TB;
    "Application logic" [shape=box];
    "I/O interface" [shape=box];
    "Real I/O" [shape=box];
    "Simulated I/O" [shape=box];
    "Sim harness" [shape=box];

    "Application logic" -> "I/O interface";
    "I/O interface" -> "Real I/O" [label="production"];
    "I/O interface" -> "Simulated I/O" [label="test"];
    "Sim harness" -> "Simulated I/O" [label="controls"];
    "Sim harness" -> "Application logic" [label="drives"];
}

Step-by-step:

1. Define I/O interfaces for network, disk, time, random
2. Implement real versions for production
3. Implement simulated versions controlled by seeded PRNG
4. Structure logic as state machines — handle(msg) -> [actions]
5. Write simulation harness with priority-queue event loop
6. Add BUGGIFY sites at decision points in application code
7. Define invariants — safety, liveness, linearizability
8. Run many seeds — each seed explores a different path through the state space

Common Mistakes

Real-World Results

• FoundationDB: "Found all of the bugs in the database"
• TigerBeetle: 1000x time compression, 3 severity levels, runs continuously on 1024 cores
• WarpStream: Found critical data race in 233 seconds that evaded 10,000+ hours of traditional testing
• Dropbox: Millions of nightly simulation runs for sync engine
• RisingWave: 16 parallel seeds per CI run, 2+ months of debugging phase found entire bug categories
• MongoDB (via Antithesis): 75+ severe bugs that all other testing missed