Cypherlite 3: Testing distributed

I wanted to make Cypherlite a real database: replication, Raft, parallel write transactions with snapshot isolation. There's more of this blog series to come, but first things first — distributed systems are hard. Multiple concurrent writers plus hardware faults are almost guaranteed to ruin years of your life. It is the reason people trust databases that have been in production for years, and distrust the ones that have not.

I first heard about deterministic simulation testing at EuroRust, in this talk. Later I heard ThePrimeagen talk about it while binging tech videos on my YouTube feed.

And since Cypherlite is my excuse to dive into exotic tech, I really wanted to give this a shot.

So I built it. It has run for weeks now, and it has not found a single product bug.

I would build it again tomorrow.

That is not a joke, and it is not a confession dressed up as a lesson. It is the argument. Deterministic simulation testing is the most theoretically compelling testing technique I know of, it is genuinely worth the cost, and in this project it produced two negative results and zero bugs — while a much less glamorous technique found eleven. Both of those facts are true at once, and holding them together is the whole point of this post.

Why the technique is compelling

The problem a database has is that its state space is not enumerable. Concurrency alone gets you there: two writers, a handful of statements each, and the number of interleavings is already past what you would write down by hand. Add faults and it stops being a counting problem at all. A leader loses quorum while it is halfway through applying a committed entry, and a follower's disk is full at that moment. That is a real bug shape. You cannot ask for it on purpose. You cannot even easily describe the timing that produces it.

Deterministic simulation attacks this by removing every source of non-determinism except one number. The whole cluster runs in a single process, on a single thread, on a virtual clock. Network drops, message delays, election jitter, crash timing, per-node clock skew — all of it derives from a seed. Same seed, same run, byte for byte.

That buys two separate things, and they are worth separating because most write-ups collapse them.

The first is reachability. A virtual clock means time is free. A 30-second election timeout costs no wall-clock seconds at all; you advance the clock and the timers fire. So you can run thousands of distinct schedules in the time one real cluster would take to hold one election. Rare interleavings stop being rare, because you are not waiting for the universe to produce them — you are enumerating them at machine speed.

The second is reproducibility, and this is the one that changes how the job feels. A cluster bug found in production is one log line and a shrug. The same bug found under a seed is a permanent artifact: rerun the seed, get the same failure, forever, with a debugger attached if you like. That turns debugging from archaeology into engineering. It is hard to overstate how much of distributed-systems work is currently archaeology.

There is a third thing, less discussed: determinism is a precondition for a whole class of fault injection you otherwise cannot do at all. Once storage goes through an injectable backend, you can stage a genuine power loss — un-synced writes vanish, which a SIGKILL does not do, because the OS page cache flushes behind you. A disk that returns out-of-space on demand. A disk that lies about fsync. A torn writeback, where the last commit only partially lands: the newest superblock written over a data tail that reverted to the previous checkpoint. You cannot buy a disk that does that on cue. You can only model one.

FoundationDB built its reputation on this. TigerBeetle is built on it. Antithesis sells it as a product. The idea is good. I want to be unambiguous about that before I tell you what it did for me.

What it produced here

Two results. Both negative.

The storage engine's crash atomicity holds. I built an injector specifically to break it: a deliberately torn image, 60 KiB to 1 MiB reverted across a node's files, newest superblock sitting over a reverted data tail. On reopen it recovered a clean, consistent prefix every time. No phantom key, no garbage record, nothing out of order. I tried every disk-fault shape I could model — power loss, disk-full, torn writeback — and nothing surfaced a defect.

A lying disk makes consensus stop rather than diverge. If a disk loses acknowledged, fsync-durable data, the precondition consensus is built on has been violated and nothing downstream is obliged to be correct. What actually happens is that the layer notices a follower's log has gone backwards and halts, defensively, instead of quietly accepting a node whose history rewound. Refuse loudly rather than proceed into silent divergence. That is the right behaviour, and it is observable no other way.

Neither of those is a bug report. Both cost real evenings to produce. I would spend them again, and here is the defence.

You are not buying bug reports. You are buying the right to stop worrying about a specific class. The storage engine survives a torn write is a sentence you either have evidence for or you are guessing about — and every other test in the suite silently assumes it. Every crash test, every durability assertion, every replication invariant is conditioned on the storage layer not lying to you under a partial write. Before the injector existed, that condition was an assumption inherited from a dependency's README. After it, it is a measured property of this system on this disk model. The value of a negative result is that it converts an unexamined assumption into a checked one, and unexamined assumptions are precisely where the expensive failures live.

A suite that only ever reports its successes is a suite you should not trust. A suite that reports a clean negative on a thing you actively tried to break is telling you something.

What actually found the bugs

Across this project's history — roughly 182 distinct issue numbers and about 3,900 tests — the technique breakdown is not what I would have predicted when I started.

Adversarial code review is the highest-yield technique, by a wide margin. Eleven findings are explicitly credited to it in the project's own engineering notes. I want to hedge that number honestly: it comes from counting where credit was written down, not from a rigorous census, so treat it as attribution rather than measurement. But the shape is unmistakable, because these are the deep ones. A torn write that gets fossilised across a crash — the write lands, no log entry is ever recorded, and a later durable commit makes it permanent. Read faults laundered into silence, where a corrupt record was swallowed as absent and quietly corrupted an index. Isolation-level holes in the concurrency-control path. Tears in the apply loop. These are not typos. They are missing invariants.

Fuzzing found an entire class at once. Every length-prefixed decoder in the system trusted an attacker-controlled length and pre-allocated on it. A handful of crafted bytes claiming gigabytes, and the process is gone. That is a class, not a bug, and fuzzing is extremely good at classes — it is a machine for finding the input you did not think to write.

A crash-recovery harness with 26 distinct kill-points proves the durability seams. Each kill-point is a place a process can die mid-write; the harness re-executes the binary as a child, aborts it exactly there, reopens, and asserts the graph and the write-ahead log still agree. That is not exploratory testing. It is a proof obligation, discharged 26 times.

Property-based differential testing found a real traversal bug. Two antiparallel edges between the same pair of nodes were being treated as the same edge by the relationship-uniqueness check, so valid paths silently vanished from results. Hand-written tests had covered traversal for months and never produced that graph shape. A generator produced it in seconds.

The compatibility suite found nothing, and was never supposed to. Running the openCypher TCK gives you a gap report — which parts of the language you do not implement — and that is a genuinely useful artifact. It is not a bug finder.

The uncomfortable ranking is that the human reading code carefully beat the elaborate machine. I think the honest explanation is structural rather than embarrassing. A simulator can only ever check invariants somebody already wrote down. It is a machine for exploring the space of executions against a fixed set of assertions. A reviewer reading for intent is doing something categorically different: noticing the invariant that is missing. This function distinguishes a decode error from an absent record — does its caller? is not a question you can generate schedules to answer. Nobody wrote the assertion, so nobody's simulator was checking it.

At a previous job I worked with two people, Stepan and Marian, who were the craziest testers I have ever watched work. Neither of them ever thought inside a box. Their instinct on meeting any input field was never what is this for — it was what happens if. Of course you paste an image into a name field. Of course you then paste the Bible into it. Not to be difficult. To find out.

Stepan's signature was appearing in your office doorway, already laughing, with: Do you still need this PC? I have something AMAZING to show you!!! You learned, over time, to save your work before answering.

Stepan once took down an NVIDIA driver through a message box. He found a path where user text reached a dialog with no newlines anywhere in it. That dialog was, for reasons nobody ever satisfactorily explained, rendered through OpenGL as a texture. No newlines means no wrapping; no wrapping means the texture just keeps getting wider; and past a certain width you are asking the graphics driver for an allocation it is not permitted to make. The driver went down and took the session with it.

There is no specification anywhere stating that a dialog box must not exceed the maximum texture width of the GPU. No property test generates that input, because writing the generator requires already knowing that a message box is secretly a texture. The bug lived in the seam between four systems, none of which was wrong on its own — and it was found by someone who simply wanted to see what a very long line would do.

I have never managed to encode that instinct into a generator. When I write a workload I write what the system is for: insert some things, read them back, contend on a counter. It takes a particular kind of person to sit down in front of a system and write what it is emphatically not for, without needing a theory first about why that would be interesting.

So when I design tests for something complicated now, what is the specified behaviour is only half the question. The other half is: what would Stepan or Marian do, alone in a server room with this cluster and a free afternoon + a six-pack of beer? It sounds like a joke. It is the more productive of the two questions, and it is precisely the one my simulator is structurally incapable of asking — because every schedule it explores is a schedule I told it about.

The caveats, which are the reason this post exists

A simulator explores what your workloads generate, and nothing else. Mine were insert-only, list-append, and hot-counter read-modify-write — homogeneous batches. Which is to say: I wrote the workloads that the person who built the thing would write. The apply-path tear above needs a mixed batch: a write, then a delete, then a write to something concurrently deleted. That was not a rare interleaving of a shape I generated. It was a shape I never generated at all. Stepan would have deleted something mid-write on his first afternoon, and never once called it a workload.

Worse, the failure it causes is convergent. Every replica applies the same committed entry in the same order against the same prior state, so every replica fossilises the same partial write. All three nodes end byte-identical. The cross-node divergence check passes, correctly, because there is nothing to find. Every node is wrong in exactly the same way. Determinism makes what your suite covers reproducible; it says precisely nothing about what your suite covers, and those two are routinely run together in the pitch — including in mine, until recently.

Your oracle is software too. My one long heavy-soak campaign reported 20 anomalies. All 20 were false positives — a pivot-guard bug in the consistency checker itself, in the logic classifying which dependency cycles are permitted under snapshot isolation. Nothing was wrong with the database. Telling an oracle bug from a real anomaly is its own skill, it is not obviously easier than the debugging you built the oracle to avoid, and it cost real days.

It degrades silently in operation. Three findings, compressed. Parallel soak shards were re-simulating identical seeds — twice the machine time, one shard's coverage — and the only tell was per-suite wall times matching to within about 1% (8301s against 8286s; two different workloads do not cost the same by accident). One seed knob was applied per test across ten serial tests at a measured 2.3 seconds per seed, which put suite one of eleven at roughly 64 hours, meaning no soak run had ever finished. And the first run that did finish immediately failed a test that had been broken since the evening it was written — verified at its own default of 4 seeds, run in anger at 2000, and seed 11 was the one that broke it. None of these were visible in code review. All were visible in numbers nobody treated as test results.

It is expensive. A virtual clock forces single-threaded simulation by construction. You buy coverage with wall-clock hours and machine cores, and you keep buying.

Databases are hard, and here is the shape of it

The final tally: about 182 issues, about 3,900 tests, 26 crash-recovery kill-points, 11 simulation suites, a formal consistency oracle, a fuzzing corpus, property-based differentials, and a compatibility suite. Not one of those techniques found more than a fraction of the bugs. The simulator found zero and I am keeping it. Review found eleven and cannot be automated. Fuzzing found a class no human would have enumerated and cannot find an isolation-level hole.

The conclusion is not that DST is overrated. It is that correctness in a system like this is a portfolio problem, and portfolios do not have a best asset. Every technique has a blind spot that is invisible from inside that technique, which is exactly why you need the others — and why the most dangerous thing you can own is a single testing method you have grown to trust.

If your test suite has never told you something you did not want to hear, it is not testing. It is agreeing with you.