How Multivergence Was Tested With a Thousand Crashes and 86 Million Reads

A state engine for branching futures makes a handful of promises. A write to one branch never shows up in another. A promote happens completely or not at all, even if the process dies halfway. The same calls always give the same weights. Deadlines and constraints fire exactly when they should. And several processes can share one store without losing anything. Each of those got its own test, aimed at breaking it.

Every figure here comes from the files in the repository’s test/results folder, which one script writes: sh scripts/record-tests.sh. They were recorded on Linux x86-64 with 2 CPUs. The isolation, crash, replay and multi-process tests ran at ten times the size CI runs them at.

The figures from test/results, drawn together.

Branches Stay Apart

The obvious way to give each branch its own state is to copy everything. It’s slow and wasteful, but it’s easy to get right, which makes it a good referee. The isolation test runs random writes, deletes, forks from the trunk and from other branches, facts, discards and promotes against the engine and against a model that does copy everything. After every single change it reads every key of every branch from both and compares them, then does it again after closing and reopening the file.

Across 80 runs that was 66,618 changes and 86.8 million reads, with no difference. Compaction was set to random small sizes in each run, so the file was being rewritten into fresh snapshots throughout.

A Promote Can’t Be Half Done

The crash test starts a real process that opens a store file and works through a random script of 400 changes: writes, forks, constraints, deadlines, observations, discards and plenty of promotes, about one change in seven. After each change returns, it reports the change’s number. The test kills it with SIGKILL at a random moment, the hardest stop there is, with no chance to clean up. Then it opens the file and compares its state with two candidates computed independently in memory: the state after the last change the process confirmed, and the state after the change it was in the middle of.

It did that 1,000 times, and in a quarter of the runs every change was synced to disk before it returned. 106 kills landed with a promote in flight; in 33 of them the promote had reached the file, and in 73 it hadn’t, and in every case the file held one whole state or the other. Compaction was set to run every 2 KB, so kills also landed in the middle of rewriting the file; 9 left an unfinished compaction file behind, which the next open cleaned up. Across all 1,000, 629 files reopened at the last confirmed change and 371 with the change in flight completed. None held anything else, and after each crash the store took more changes and another promote.

The Same Calls Give the Same Weights

The engine never decides how likely anything is, but it does multiply and renormalise. Floating-point arithmetic gives different answers if you add the same numbers in a different order, so the engine fixes the order and records the time each change used. The replay test runs the same random script in memory, into a file with compaction at varying sizes, into the file again after reopening, and through a reader that takes no lock. It compares a digest of everything: the data, every weight’s exact bits, the constraints, the deadlines and how each branch died. 300,000 changes over 200 runs, every one of which compacted, gave the same digest and the same history, event for event, every time.

Deadlines and Constraints Fire on Time

The schedule test runs 30 simulated days. Branches are forked with deadlines from a minute to three days out and with constraints on a value that drifts as facts arrive, and a separate model works out when each branch should die. After every change, every branch is checked against it: alive if it should be, dead if it should be, for the right reason at the right moment. A branch past its deadline must also read as dead straight away, before any change has recorded it.

Of 2,990 branches, 1,152 expired and 609 broke a constraint. All 1.4 million checks agreed with the model. None died early and none late.

Many Processes, One File

Eight writer processes each opened the same store 500 times, read a counter, wrote it back plus one and closed the file. Every tenth time they also forked a branch, wrote to it and promoted it. Three reader processes read the file the whole time without taking the lock, while compaction renamed it under them every few kilobytes. The counter ended at exactly 4,000, so no update was lost. The readers made 41,135 reads, and none of them saw a damaged file or the counter going backwards.

What a Branch Costs

On a trunk of 10,000 keys with 100-byte values, a branch that changes 3 keys added about 3.9 KB of memory, measured after garbage collection. One full copy of the same trunk took 2.1 MB. With 1,000 such branches the maps share 52,886 nodes, where full copies would hold over 10 million, and the compacted file is 5.9 MB where writing each branch in full would take 1.1 GB.

The cost that does grow is time. Each change copies the engine’s table of branches, so a write took about 3.8 µs with 10 live branches and about 70 µs with 1,000. For agents, whose tool calls take milliseconds or seconds, that’s small.

From Another Language

A Python script drives the multivergence command through the whole trip from the demo, with a fixed clock, and works out every probability itself before comparing it with the engine’s: 26 checks, all passing. It also runs as part of the release smoke check, on every binary on its own kind of machine.

CI runs all of these on Linux, macOS and Windows on every push, with Go’s race detector on Linux.