exploring dst: building deterministic simulation testing from scratch

distributed systems bugs are the worst kind. a message could get lost at the wrong time, a test could fail once in a thousand runs, and you can never make it happen again, leading to the whole "it works on my machine, but i cant repro" dilemma

deterministic simulation testing or DST in short fixes exactly that. FoundationDB made it famous, TigerBeetle lives by it, and a whole company (Antithesis) sells it. i had the weekend to myself and wanted to dive into a new rabbit hole, so i built a small one from scratch in rust :)

code: github.com/bit2swaz/exploring-dst

the core idea in short

take everything in your system that depends on luck (technical: non-deterministic):

• the clock
• the network (lost, late, duplicated, reordered messages)
• the disk (writes lost or torn on a crash)
• random numbers

and put all of it behind something you control, and drive all of it from one number, the seed

this seed is a number such that the same seed = same run = same bug. every single time

now you just run thousands of seeds, check your rules after every step, and when a rule breaks, you replay that seed and watch the exact same failure until you fix it. not so hard is it?

the fake world (simulation)

the whole thing is just a few small pieces:

1. a seeded rng: (splitmix64 algo, ~10 lines). every random choice in the simulation comes from it
2. a fake clock: it never reads real time. it moves only when the simulator tells it to
3. a fake network: send gives each message a random arrival time, or drops it, or puts two copies on the wire. the simulator delivers messages in order of arrival time (fun fact: reordering needs zero extra code since random delays already shuffle everything)
4. a toy system to test with: typical distributed system: 3 nodes and a tiny replicated key-value store. a client sends puts to the leader and the leader forwards them to 2 followers. this is made naive on purpose with no retries, no acks, and no order numbers

the trick that makes it all work is that a node never touches the network or the clock. it just gets one message and returns the messages it wants to send. thats it. the simulator does everything else:

while let Some((at, env)) = net.next() {
    clock.advance(at - clock.now());
    for (to, msg) in nodes[env.to].on_message(env.msg) {
        send(&mut net, &mut rng, &clock, &mut log, env.to, to, msg);
    }
    checker.after_step(&nodes)?;    // check the rules after every step
}

single-threaded, no real time and no real sockets. the simulator decides what happens next and the seed decides the "luck"

click to zoom

rules / invariants

as Phil Eaton said in this write-up, a simulator is only as good as the invariants it sets. for my mini DST, i used 3:

1. no made up values: a node only holds values the client actually sent
2. no going back: a key never goes back to an older value
3. everyone agrees: when no messages are left, all 3 stores are the same

one key lesson to take here is to check after every step, not only at the end. the initial naive design broke rule 2 on all 100 "bad network" seeds :/ that's because the bad network reorders messages, due to which an older Replicate can land after a newer one and overwrite it, so a key goes back in time, and hence rule 2 gets broken

but if i checked only at the end, 7 of those 100 passed because the stores happened to agree by pure luck. the bug was obviously still there. its just that somehow the end-only check didnt see it

hunting

here's the fun part. cargo run -- hunt lossy runs 10,000 seeds on a network that keeps order but loses 1% of messages:

555 of 10000 seeds failedfirst failure: seed=15: rule 3: node1 has {"b": 8 ...}, but the leader has {"b": 9 ...}replay it: cargo run -- 15 lossy ops=10

10,000 full runs take about 0.3 seconds because there is no real waiting. the fake clock just jumps

and heres a subtle thing i learnt from this part: a lost Put does no harm. since the leader never got it, nobody has it, and everyone still agrees. only a lost Replicate breaks things. this is something that wouldve probably never hit me had it not been for the simulator

replay && shrink

every run writes an event log, and every log gets a fingerprint (a tiny fnv-1a hash). the hunter and the replay print the same fingerprint so you know the replay is the exact same story

the seed 15 failure was about 60 log lines long, which is pretty hard to read, because imagine having to read 60 lines just to find that one specific line where something broke

so, to work around this, the simulator shrinks it: try 1 put on every seed, then 2, and so on, until it finds the shortest run that breaks the same rule

thanks to shrinking, the 60 lines became 10:

t=0ms send Put { key: "a", val: 0 } 99->0t=1ms deliver Put { key: "a", val: 0 } 99->0t=1ms send Replicate { key: "a", val: 0 } 0->1t=1ms send Replicate { key: "a", val: 0 } 0->2  copies=0                                    <- this one got lostt=2ms deliver Replicate { key: "a", val: 0 } 0->1VIOLATION: rule 3: node2 has {}, but the leader has {"a": 0}

one put, one lost message, one sad follower, and thats it. thats the whole bug

click to zoom

try it yourself

this is the same simulator, running in your browser. seed 117 on the lossy network is the 10-line bug from above. run it, run it again, then try a few seeds of your own:

the HashMap trap

i swapped one BTreeMap for a HashMap to see what happens. seed 15 gave 5 different fingerprints in 5 runs

this is because rust's HashMap picks a new random order in every process, so one HashMap where order actually matters and boom... determinism is gone. the scariest part is that absolutely nothing crashes. your replays just quietly stop being replays, until you find out on your own

time for real code: turmoil

milestones 1 through 6 were my own toy world. for milestone 7 i wrote a tiny real async service (leader + 2 followers over UDP with the same naive design as earlier) and ran it under turmoil which simulates hosts, time and the network for real tokio code

the service doesnt know its in a simulation, and the only change is the import:

use turmoil::net::UdpSocket; // instead of tokio::net::UdpSocket

on a bad network (5% link breaks, 1 - 100ms latency), 147 of 200 seeds failed. out of these, my favorite one was seed 0, where a follower apparently ended up more correct than the leader even tho both got the puts out of order and they disagreed in opposite directions

(in short, the leader got put 9 before put 6 so it ended on the older a=6. the follower on the other hand got those two replicates the other way around so it ended on a=9, the newest one, hence why the follower was more correct)

i also used UDP on purpose since turmoil doesnt re-send lost TCP segments so TCP faults there dont behave like real TCP

the disk: why fsync is important

last milestone, and this one was a bonus. i built a fake disk with 2 layers: the page cache (write) and the durable disk (fsync). on a power cut, every write that wasnt fsync'd is randomly lost, torn, or kept. in our simulator, the seed picks when the power goes out

on top of it, a tiny write-ahead log: 10-byte records with a 1-byte checksum. after a crash, recovery reads records until the first bad checksum. and there's only two rules: every put that returned "ok" must survive, and every recovered record must be one we actually wrote

the no-fsync bug can never show up without a crash, so normal tests would pass forever. our simulator finds it on the first seed tho :P

what i learnt

• DST is a design choice. the code has to take its clock, network and disk as inputs. once it does, testing it this way is almost free
• check rules after every step. the end state can look alright while the history could be very wrong
• shrinking is underrated. a 10-line failure explains itself (self explanatory?)
• determinism is fragile. one HashMap, one thread_rng(), one real sleep, and its all gone to dust, and you wont even know about it

and the limitations:

• it doesnt test the real edge cases like a cloud provider or a third party API would
• its only as good as your test suite and your invariants. weak invariants only lead to false confidence
• a seed only replays on the same code. change the code and old seeds mean nothing

from all this, i think it's pretty obvious that DST doesnt replace testing in prod. it just finds the logic bugs before deploy, and every bug it finds comes with a perfect replay. and i think that in itself is pretty huge, however not enough all by itself

so, to conclude: control the luck factor with one seed and "cant repro" just stops being a thing ^^

read before starting: Phil Eaton, "What's the big deal about Deterministic Simulation Testing?"