For the first 18 months, FoundationDB’s team developed the database entirely in simulation, before it sent its first real network packet. The database code was running. The machines, network, disks, and passage of time were controlled by a simulator.
That is an unusual place to start building a database.
It also makes sense once you consider what makes distributed systems difficult to debug. The problem is often not a function producing the wrong answer for a particular input. It is several individually reasonable actions happening in an order nobody anticipated.
A write completes just before a timeout. A process restarts while another still believes it is alive. A delayed response arrives after the operation that created it has already been retried.
FoundationDB’s approach was to make those executions reproducible.
Instead of waiting for an unlucky sequence of events to happen again, the engineering team could recreate the environment that produced it, inspect the execution, and investigate the failure.
The important idea is not simply to inject more failures. It is to take control of the things that make a failure difficult to repeat.
01The bug is often in the ordering
Consider a hypothetical replicated database.
A client submits a write. The leader sends it to two replicas. One replica responds, the other is slow, and the leader returns success. Shortly afterward, a machine restarts.
There are several questions hidden inside that description.
What did the replica’s response actually mean? Had it received the write, applied it in memory, or made it durable? Was the response associated with the current request or an earlier retry? What state survived the restart?
Changing one of those details can turn the same sequence of API calls from a valid execution into a data-loss bug.
The FoundationDB paper describes this problem directly: combinations of failures, restarts, and message ordering can expose defects that are difficult to reproduce even with end-to-end tests.
A test that says “write a value, restart a node, read the value” specifies very little about the execution between those steps.
For a reproducible test, we need to specify more than what the client did. We need control over when the system was allowed to make progress.
02Run the database. Replace its environment.
The central box in the architecture is the most important one: database code.
FoundationDB’s simulation does not substitute a simplified database implementation and then assume the production implementation behaves similarly. It runs the database software against simulated implementations of its external interfaces. Its engineering documentation describes replacing physical interfaces with shims and replacing the normal event loop with a time-based simulation.
For a small implementation, the boundary might look conceptually like this:
1interface Runtime {
2 now(): number
3 random(): number
4 send(message: Message): void
5 schedule(delay: number, event: Event): void
6 append(record: LogRecord): void
7 sync(requestId: string): void
8}This is an illustrative interface, not FoundationDB’s actual API.
The database asks the runtime to send a message. In production, that request eventually reaches a real transport. In simulation, it schedules a delivery event.
The database requests a storage operation. The simulator decides when that operation completes, whether it fails, and what survives a subsequent restart.
This boundary is useful because it keeps the algorithm under test intact. Replication decisions, retry handling, and recovery logic remain in the database. The simulator supplies the environment in which those decisions execute.
It is worth qualifying the diagram’s phrase “never knows which world.” FoundationDB deliberately includes simulation-aware hooks that make unusual behavior more likely during testing. The architectural goal is to exercise the production logic, not to prohibit every piece of test instrumentation.
03How an entire cluster fits into one thread
FoundationDB’s simulator can execute an entire logical cluster within a single thread. Each simulated process has its own state, but the simulator controls when its work runs.
The original implementation made this practical through Flow, which added actor-style asynchronous programming to C++. An actor could wait for a future without blocking other actors. Flow compiled those asynchronous functions into ordinary C++ code with the machinery needed to suspend and resume execution.
Think of three logical nodes, A, B, and C.
A starts a replication operation and waits for a response. While A is waiting, B receives the request and starts a storage operation. C can process another message before B’s storage operation completes.
The simulator does not need those actions to execute simultaneously on separate CPU cores. It needs to represent the ordering and overlap of the operations at the boundaries relevant to the protocol.
For our small implementation, those boundaries would be explicit events: message delivery, storage completion, timeout, crash, and restart.
There is still concurrency in the system being modeled. Multiple operations are in progress. There is simply one place deciding which runnable action executes next.
That distinction matters. We are not removing the distributed interactions we want to test. We are removing the operating system’s control over their scheduling.
04Virtual time makes waiting cheap
Suppose our simulator has these pending events:
t=120 deliver replication request to B
t=125 complete storage operation on C
t=500 fire client timeoutIt processes the event at 120, then the event at 125. Assuming nothing else becomes runnable, it advances directly to 500.
There is no reason to wait through the intervening milliseconds.
A conventional discrete-event scheduler can implement this with a priority queue ordered by scheduled time. Equal timestamps need a deterministic tie-breaker, such as a monotonically increasing event ID. SimPy documents this approach as tuples containing time, event ID, and the event itself.
For our implementation, I would make that ordering explicit:
scheduled time
then scheduler priority, if used
then insertion sequenceLeaving ties unspecified would undermine the entire replay mechanism.
Virtual time also needs to be distinguished from the clocks visible to individual nodes. To test clock skew, I would give each node a configurable view of time while keeping the scheduler’s own timeline monotonic. Making a node believe its clock moved backward should not require rewinding the simulator.
There is an important performance qualification here. Skipping an idle interval is cheap. Executing a million protocol events is still work.
FoundationDB’s documentation describes roughly a trillion CPU-hours of equivalent testing, based on testing volume and the increased intensity of simulated failures. That is the team’s stress-testing estimate, not a measurement of a trillion physical processor-hours consumed or a universal simulation speedup.
05Randomness becomes an input
A seeded pseudorandom generator produces a reproducible sequence when its algorithm, initial state, and use remain compatible. That is different from obtaining fresh randomness from the operating system on each run.
In our simulator, that sequence would drive decisions such as which operation to issue next, how long a message takes to arrive, and when a node fails.
The slogan is:
same seed, same bugThe engineering contract needs to be more precise.
For a replay artifact, I would record the database build, simulator version, complete configuration, initial state, workload definition, and seed. The execution environment should also be pinned wherever platform or runtime differences could affect determinism.
Conceptually:
execution = simulate(
database build,
simulator build,
configuration,
initial state,
seed
)The seed is only one input.
There is also a coupling problem worth designing around. Suppose network delays and workload generation consume values from the same random stream. Adding one new random choice to the workload shifts every subsequent network decision.
For FaultSeed, I would derive separate deterministic streams for workloads, network behavior, storage behavior, and faults. This would make changes easier to reason about, although it would not guarantee identical execution after an arbitrary code change.
The goal is to make the sources of variation explicit enough that a failed run can be reconstructed.
06The disk model is where a convincing demo becomes a useful test
A simulated disk that immediately saves every write into a persistent map is easy to build.
It also eliminates an important class of failures before testing begins.
A real durability boundary is more demanding than “the write function returned.” On Linux, fsync() is the operation that requests synchronization of modified file state to storage and waits for the device to report completion. File data and directory-entry durability also have distinct requirements.
For an educational simulator, I would start with two explicit states:
pending writes
durable recordsAppending creates a pending write. A successful synchronization event moves the relevant records into durable state. Under the chosen fault model, a simulated machine power loss may discard pending writes but must preserve successfully synchronized records.
This gives us a useful place to introduce a legitimate bug.
Consider a hypothetical three-node store with a fixed leader. Its contract says that an acknowledged write survives machine restarts, provided durable storage is not destroyed. There are no later writes or deletes to the key in this example.
The faulty implementation counts a replica’s “received” response as evidence that the write is durable. Neither the leader nor that replica has completed synchronization.
An illustrative execution could be:
001 client sends PUT x=5 to A
002 A appends x=5 to its pending buffer
003 A sends the record to B
004 B appends x=5 to its pending buffer
005 B acknowledges receipt before synchronization
006 A returns success to the client
007 replication to C has not completed
008 simulated power loss restarts all database machines
009 pending writes and in-flight messages are discarded
010 A recovers from its durable records
011 client reads x
012 A returns missingThis is a teaching example, not a reported FoundationDB incident.
No durable disk was erased. The simulator removed only state that the test contract explicitly allowed power loss to remove.
The database nevertheless lost an acknowledged write.
That makes the failure actionable. The implementation confused receipt with persistence. The correction is to make the acknowledgement path enforce the promised durability boundary.
For this particular fixed-leader example, that means waiting for the required successful synchronization completions before returning success. Adding leader replacement would introduce further obligations around recovery and which node is allowed to serve requests.
The simulator does not make those protocol obligations disappear. It gives us a way to expose violations of them.
07A failure generator needs a definition of correctness
Random faults are not enough.
A simulator can generate thousands of dramatic executions without detecting that the database returned the wrong answer. It needs a test oracle: some independent way to decide whether an observed execution violated the contract.
FoundationDB uses assertions within the implementation and checks embedded in synthetic workloads. Its paper also describes testing recovery by restoring an environment in which progress should be possible and verifying that the database recovers.
For our store, I would separate safety from recovery.
A safety check asks whether something forbidden happened. In the previous example, a completed write disappeared after an allowed restart.
A recovery check asks whether the system can resume useful work once the environment permits it. Permanently partitioning every node and then complaining that writes stopped would not be a meaningful test of recovery.
The test therefore needs a recovery phase. Stop injecting faults, restore the required connectivity, restart eligible nodes, and let the system run for a bounded amount of virtual time.
The oracle also needs to match the workload.
“Every acknowledged value must still exist” is not correct for a database that permits overwriting or deleting keys. For a simple durability test, I would use unique keys written once. For more general workloads, I would record operation histories and validate them against the consistency model being claimed.
For example, linearizability concerns whether operations can be explained by a legal sequential execution that respects the real-time ordering of non-overlapping operations. It is a stronger claim than replicas eventually containing the same data.
FoundationDB’s testing documentation gives another useful example: transactions modify key-value pairs arranged as a ring while preserving the ring’s integrity. The workload creates a property whose violation reveals an isolation problem.
The quality of the oracle determines how much a passing simulation actually tells us.
08Making rare states common
A completely random fault generator is not necessarily a productive one.
Imagine that our workload needs a node to recover halfway, receive an old response, and then process a new request before another recovery step completes. Randomly killing machines might eventually create that situation, but much of the test budget could be spent elsewhere.
FoundationDB addresses this with higher-level fault injection through BUGGIFY. These hooks deliberately make unusual but permitted behavior more common, such as delaying an operation or exercising an error-handling path. The purpose is to steer testing toward difficult states rather than relying entirely on low-level network failures to produce them indirectly.
For FaultSeed, I would use a few carefully chosen hooks.
One could delay a storage completion after a request has been accepted. Another could hold a response long enough for a retry to begin. A recovery hook could pause a node between rebuilding its durable state and accepting new work.
Each hook should have a clear explanation of what real behavior it represents.
The goal would not be to make every operation fail. A test that never gets past startup cannot tell us much about replication during recovery.
I would want runs that build useful state, disturb it, and then give the system a chance to repair itself. The interesting result is often what happens during the transition back to normal operation.
09Replay changes the debugging process
Suppose a run using seed 8412 violates an invariant at a particular event.
With the original build and complete run configuration preserved, we can rerun that execution and inspect the state immediately before the violation.
Was the record still pending when the acknowledgement was sent? Which request did the response belong to? Did recovery restore the record but fail to expose it to reads?
FoundationDB’s engineering documentation explicitly describes reproducing problems and adding instrumentation afterward.
For our simulator, I would keep diagnostic logging observational. It must not consume simulation randomness, schedule additional protocol work, or modify database state.
Adding logs will naturally change the textual output. It should not change the sequence of modeled database actions.
That suggests maintaining two separate artifacts: a canonical execution trace used for determinism checks, and richer diagnostic output used during investigation.
There is another distinction that matters after fixing a bug.
Replaying the old build demonstrates reproducibility. Running the corrected build checks the fix. Those are different experiments.
A fix may introduce a new message or change when the program consumes randomness. The same seed can then generate a different execution. A passing result is useful, but it does not by itself prove that the corrected code encountered the original failure conditions.
For a durable regression test, I would also preserve a small explicit scenario capturing the causal sequence. In our example, delay synchronization, allow receipt acknowledgements, interrupt the machines, and verify the durability contract.
The random search finds the scenario. The regression test preserves what we learned.
10The simulator is only as good as its model
Determinism guarantees that we can repeat the execution we modeled. It does not establish that the model includes every behavior the real system will encounter.
The FoundationDB paper acknowledges limitations involving performance testing, dependencies outside its simulation framework, and mismatches between assumed and actual operating-system contracts.
This is why the abstraction boundary deserves careful review.
Take networking. TCP provides a reliable, in-order byte stream. A simulator that claims to model a TCP connection but arbitrarily reorders bytes delivered to the application is testing a different transport contract.
For our store, I would distinguish message ordering across connections, retries that duplicate application requests, connection failure, and byte ordering within one established connection.
Storage needs the same discipline. Process termination, machine power loss, and permanent disk destruction should not silently mean the same thing.
A process-only crash model might preserve operating-system buffers. A power-loss model might discard them. Permanent disk loss removes data the other two models were required to preserve.
Those are design choices for the simulator, but they must be stated explicitly. Otherwise, a failure could indicate either a database defect or an impossible expectation in the test.
Simulation should sit alongside tests of the real adapters and real hardware behavior. FoundationDB’s documented testing approach combines simulation with live performance testing and hardware-based failure testing.
11What I would build in FaultSeed
The useful prototype is much smaller than FoundationDB.
I would build a three-node replicated key-value store with one database implementation and an injectable runtime. The first version would use a fixed leader, explicit storage synchronization, and a clearly documented restart contract.
I would leave automatic leader election out until the simulator and durability checks were trustworthy. Adding a hand-waved election mechanism would create more ambiguity than insight.
The simulator would own every state-changing event. Nodes would process events synchronously and return effects for the scheduler to execute. Real timers, network calls, and filesystem operations would stay outside that core.
Each node would also have an incarnation identifier. When a node restarts, a completion belonging to its previous incarnation must not accidentally mutate the new node. That rule would make crash behavior explicit rather than relying on object cleanup to happen correctly.
The first demonstration would be the premature-acknowledgement bug.
A normal no-fault test would pass. A generated failure schedule would expose the lost write. Replaying the saved run would reproduce it. A focused regression scenario would then verify that the corrected acknowledgement path waits for durability.
Only after that would I add broader workload generation, replica catch-up, more fault types, and scenario reduction.
The success criterion would not be an impressive count of simulated years. It would be a small, inspectable failure that ordinary tests missed, together with enough evidence to explain exactly why it happened.
12The architectural lesson
The most useful part of FoundationDB’s approach is that testability influenced the architecture from the beginning.
For FaultSeed, that would mean treating every direct dependency on time, storage, scheduling, or randomness as a decision about what the test harness can control.
A simulated execution is still only one execution. Passing many of them is not a proof that the system is correct.
But when one fails, it can become a concrete engineering artifact rather than an incident that somebody remembers happening once.
You can inspect the state, change the instrumentation, and test an explanation against the same execution.
That is what makes “same seed, same bug” valuable. It turns a rare failure into something an engineer can sit down and work on.
