FoundationDB
A deterministic distributed key-value store proven by simulation before it ever ships.
FoundationDB is an unbundled distributed key-value store: a transaction system, a distributed log, and stateless storage engines, each tested separately. Every feature is validated in a deterministic simulation environment where injected faults run thousands of times faster than real time — the reason its correctness claims carry unusual weight.
Deterministic simulation
A single-threaded deterministic core means any bug reproduces exactly. Simulation injects disk failures, network partitions, and reboots at millions-of-times speed — features ship only after surviving it.
Unbundled architecture
GrvProxy (transactions), TLog (durable log), StorageServer (data): independent processes scaled independently. The commit path is a distributed log, storage is an LSM.
Strictly serializable MVCC
Reads use a cached version guaranteeing a consistent snapshot; writes conflict-detect at commit via a dependency-tracking log prefix.
Layers on a small core
The core is deliberately tiny (ordered KV, watch, transactions). Document stores, queues, indexes — everything else is a layer built on that API.
Simulation before implementation
FoundationDB legacy design runs the entire cluster in a single process with deterministic execution: same inputs, same decisions, same bugs — reproducibly. Fault injection then explores failure space orders of magnitude faster than real time.
The famous result: when Apple acquired the company, the database survived a datacenter migration with no data loss — correctness claims backed by the simulation record.
// Layer example: a document store on the KV API
SET ("doc/42/title", "LSM trees")
SET ("doc/42/tags", ["lsm", "storage"])
GET ("doc/42/") // range read: all keys under doc/42
The commit path
A transaction reads at a grv version, buffers writes, then commits: the sequencer assigns a commit version, the mutation lands in the distributed TLog, storage servers pull mutations from the log. Durability = log quorum; storage catches up asynchronously.
The walkthrough below shows the same MVCC commit/crash loop on a single node — FDB distributes that exact rule across its log and storage processes.
Diagrams
[caption] Unbundled: proxies, logs, and storage scale independently.
Transactions read at a cluster-managed version, buffer mutations, and commit through the distributed transaction log; storage servers apply mutations asynchronously.
| visible after recovery | v2 (balance 250) |
| v1 (100) | dead tuple — reclaimed by VACUUM |
| WAL replay stop point | A’s flushed commit record |
| durability rule | commit waits for WAL flush |
All steps
- Tx A: UPDATE balance 100 → 250 — A new version (v2, xmin = 100) is written and chained; v1 is marked dead-upon-A’s-commit. Nothing in place is overwritten — writers never block readers.
- Reader B (old snapshot) still sees 100 — B’s snapshot was taken before A ran. xmin = 100 is in progress ⇒ v2 is invisible to B; it follows the chain to v1 (100). Repeatable reads in action.
- A commits — WAL flushed first — The commit record is appended and flushed to WAL; only then does the client get acknowledgment. Data pages may not even be written yet.
- Crash after the commit — The process dies before any checkpoint. The WAL is the truth: committed work survives, uncommitted tails are discarded.
- Recovery replays to the commit record — Replay restores v2 (250). A committed transaction cannot be lost — this is the durability half of ACID, paid for at commit latency.
- Reader C (new snapshot) sees 250 — Snapshots taken after the commit see v2; v1 is now a dead tuple that VACUUM will reclaim later.
Transaction visibility, the WAL commit boundary, and crash recovery — PostgreSQL-flavored. Simplified: xmin-only version chains, no xmax/clog details; the durable rule shown here is exact: a transaction exists only once its commit record is flushed to WAL.
Single-node trace of a distributed rule: FDB runs it per TLog with deterministic recovery.
[caption] Single-node trace of a distributed rule: FDB runs it per TLog with deterministic recovery.
Version visibility, the durable commit boundary, and replay — the exact rule FoundationDB enforces across its distributed log.