FoundationDB: A Distributed Unbundled Transactional Key Value Store

In one breath — the whole paper, compressed

Cloud services needed a store that scaled like NoSQL yet still offered multi-key ACID transactions, and nothing on offer gave both without special hardware or pervasive locking. FoundationDB unbundles the database into a control plane of Paxos Coordinators plus a data plane split three ways: a stateless transaction system, a log system of replicated sharded queues, and a storage system of SQLite-backed StorageServers, so read capacity and write capacity scale independently. Strict serializability comes from combining MVCC read versions handed out by a single Sequencer with optimistic concurrency control run on range-partitioned Resolvers, where the commit version doubles as the log sequence number and thereby defines the serial order outright. Instead of masking failures with quorums, FDB detects any failure in the transaction system, proactively tears the whole thing down, and rebuilds it in a new epoch, which lets it tolerate f failures with f+1 replicas and finish recovery in a median of 3.08 seconds. Every feature is exercised inside a deterministic discrete-event simulator with randomized fault injection, which is why CloudKit ran FDB for more than 0.5M disk years without a single data corruption event.

Before this paper — the world it landed in

By the late 2000s the scalable storage tier under a cloud service was almost always a NoSQL store - Bigtable, Dynamo, PNUTS, Cassandra, MongoDB, CouchDB. To reach billions of users these systems gave up transactional semantics and offered eventual consistency instead, which handed every application developer the job of reasoning about interleavings of updates from concurrent operations. The alternative, a real database, bundled a storage engine, a data model, and a query language together, forcing users to choose all three or none, while layered efforts such as Percolator, Tephra and Omid bolted transactional APIs onto key-value stores but only reached snapshot isolation. The systems that did offer distributed transactions - Spanner with TrueTime, CockroachDB with hybrid-logical clocks, and unbundled designs like Deuteronomy - all established the serial order at the moment locks were acquired, and paid for fault tolerance with 2f+1 replicas. Meanwhile everyone tested distributed systems with non-deterministic fault injection, which is precisely the technique that cannot reproduce the deep bug it just found, and model checking could verify a protocol but not the implementation that shipped.

The problem — what was actually breaking

NoSQL systems bought scale by sacrificing transactional semantics, offering only eventual consistency and forcing application developers to reason about the interleavings of updates from concurrent operations.
Most databases bundle a storage engine, a data model, and a query language, forcing users to choose all three or none; features that help some applications force everyone who does not need them, or needs a slightly different form of them, to work around them.
Masking failures with quorums, the standard approach in distributed databases, requires 2f+1 replicas to tolerate f failures, which is a large resource multiplier at petabyte scale.
Trying to fix every distinct failure scenario inside the transaction path multiplies rarely executed error-handling code, and code that rarely runs is code that is rarely correct.
Recovery in the ARIES tradition depends on periodic checkpoints and on replaying redo and undo log records, so recovery time grows with the log size at exactly the moment clients are waiting for the database to come back.
Unexpected process and network failures, message reorderings and other sources of non-determinism expose subtle bugs that are extremely difficult to reproduce or debug, and because a database is stateful such a bug can produce corruption that is not discovered for months; deep bugs that need a particular sequence of crashes defeat ordinary end-to-end testing, and model checking verifies a model rather than the actual implementation.

Core ideas — the contributions, and why they work

Unbundled control plane and data plane

FDB splits the cluster into a control plane that persists critical system metadata on Coordinators forming an Active Disk Paxos group, and a data plane that does the actual work. The data plane is itself unbundled three ways: a transaction system of Sequencer, Proxies and Resolvers that is entirely stateless and does in-memory transaction processing, a log system of LogServers that hold the write-ahead log, and a storage system of StorageServers that hold the data and serve reads. Every role is a separate process type, so an operator provisions and scales each one independently, and can even place heterogeneous roles on different server instance types to optimize for cost. This works because the singletons - ClusterController, Sequencer, DataDistributor, Ratekeeper - only perform limited metadata operations and never sit on the data path, so they never become bottlenecks.

A deliberately minimal feature set, with layers above

FDB offers only get, set, getRange and clear over an ordered key space, with no structured semantics, no query language, no data model or schema management, and no secondary indices. The argument is not that these features are useless but that offering them would benefit some applications while forcing all the others - those that do not need them, or need a slightly different form - to work around them. Everything richer is built as a layer: a stateless application on top that supplies a data model, and which inherits FDB's transactions for free. The evidence for the bet is the breadth of what got built - the FoundationDB Record Layer for relational structure and indexes, the Document Layer, a JanusGraph storage adapter for graphs, and CouchDB being re-implemented as an FDB layer in its newest release.

Serializable snapshot isolation from OCC plus MVCC

A transaction gets a read version guaranteed to be no less than any commit version issued before it started, reads a consistent MVCC snapshot at that version, and buffers writes on the client. At commit it gets a commit version larger than any existing read or commit version, and that single number both defines the serial history and serves as the Log Sequence Number for the rest of the system. Because the transaction observes the results of all previously committed transactions and is ordered after them, the result is strict serializability rather than mere serializability. Conflict detection is then a pure read-write check on Resolvers with no locks anywhere, which greatly simplifies the interaction between the transaction system and the storage system; the price is keeping recent commit history in Resolver memory and accepting that a transaction is not guaranteed to commit.

Version assignment before conflict detection

Unlike write-snapshot isolation, which assigns the commit timestamp only after checking the read set, FDB decides the commit version first and resolves afterwards. This inversion is what makes batching possible: a Proxy can group many client transactions, ask the Sequencer for one commit version for the whole batch, and send the batch to Resolvers as a unit, so both version assignment and conflict detection are amortized. The Sequencer advances the version at one million versions per second, and batching lets Proxies commit tens of thousands of transactions per second without stressing it. The batch degree is adjusted dynamically - smaller when the system is lightly loaded to keep commit latency low, larger when it is busy to sustain throughput.

Make failure a common case

FDB does not attempt to survive failures in place. The Sequencer monitors Proxies, Resolvers and LogServers, and on any failure - or any configuration change - it simply terminates; the ClusterController notices, recruits a new Sequencer, and the whole transaction management system is rebuilt in a new epoch. All failure handling therefore collapses into one recovery operation, which becomes a common and well-tested code path instead of a thicket of rarely exercised special cases. The strategy is only sound if recovery is fast, which is why FDB attacks Mean-Time-To-Recovery so hard, and it pays for itself twice: normal transaction processing gets simpler, and because failures are recovered from rather than masked, FDB needs only f+1 replicas rather than 2f+1 to tolerate f failures.

Recovery with no redo and no undo

Recovery is made deliberately cheap: there is no checkpoint and no log replay. The insight is that redo log processing is the same as the normal log forward path - StorageServers are always pulling logs from LogServers and applying them in the background - so redo is decoupled from recovery entirely rather than being work recovery has to do. Recovery therefore only needs to determine where the redo log ended, and the new transaction system can start accepting transactions before the old LogServers have been fully drained. Undo is equally cheap because only mutations that have left the five-second MVCC window are written to the SQLite B-tree, so rolling back means discarding in-memory multi-versioned data. The consequence is that recovery time is bounded by system metadata size rather than by data or log size.

Deterministic simulation before the database

Before writing the database, the team wrote a deterministic discrete-event simulator that runs many FDB servers inside a single physical process with a simulated network, disk, clock and random number generator. To make this possible all database code is deterministic and multithreaded concurrency is avoided outright - one database node is deployed per core - with concurrency expressed instead through Flow, a syntactic extension to C++ providing async/await-style actors. The value is not just that faults can be injected but that every bug found is exactly reproducible, so adding logging does not perturb the event ordering and the same failure can be replayed until it is understood. Simulation also runs faster than real time by fast-forwarding the clock whenever CPU utilization is low, which is precisely the situation in the long quiet stretches where distributed systems bugs hide.

How it works — the mechanism, concretely

End-to-end commit path

A client contacts a Proxy for a read version; the Proxy asks the Sequencer for a version no less than any previously issued commit version and returns it. The client then reads directly from StorageServers at that version and buffers its writes locally, with read-your-writes served by merging look-up results with the uncommitted local writes. At commit the client ships the read set and write set, as key ranges, to a Proxy, which obtains a commit version from the Sequencer, sends the transaction to the range-partitioned Resolvers, and on unanimous admission broadcasts the log message to LogServers. The transaction is committed once all designated LogServers report durability; the Proxy then reports the committed version back to the Sequencer, so that later read versions are ordered after it, and only then answers the client. Read-only transactions never take this path at all - they are serializable at their read version and the client commits them locally without contacting the cluster.

Resolver conflict detection

Each Resolver keeps lastCommit, a map from recently modified key range to the commit version that modified it, implemented as a version-augmented probabilistic SkipList. For a transaction Tx, every range in the read set Rr is intersected against lastCommit, and if any intersecting entry has a commit version greater than Tx's read version the transaction aborts; because the check is over ranges rather than individual keys it also prevents phantom reads. Otherwise every range in the write set Rw is stamped with Tx's commit version and the transaction is admitted. The key space is divided across Resolvers so this runs in parallel, and a transaction commits only if all Resolvers admit it - which means a transaction rejected by one Resolver may already have polluted lastCommit on another, producing false-positive conflicts for later transactions. In practice this is tolerable because a transaction's ranges usually fall inside one Resolver and stale entries expire out of the five-second MVCC window; Resolver range boundaries are also adjusted dynamically to balance load.

Logging protocol and mutation tagging

The Proxy consults its in-memory shard map to find which StorageServers own the modified key range, and attaches those StorageServer tags to the mutation. Each tag has a preferred LogServer, so the mutation body is sent only to those preferred LogServers plus however many extra are needed to meet the replication degree; every other LogServer still receives the message but with an empty body, so all of them stay in LSN order. The header carries the LSN, the previous LSN, and the Proxy's Known Committed Version, and a Proxy advances its KCV to an LSN once all replica LogServers have acknowledged that it is durable. Shipping the redo log onward from LogServers to StorageServers is not part of the commit path: StorageServers pull aggressively, even before the data is durable on the log system, which keeps multi-version reads fast but means semi-committed updates may later need rollback. Because durability already lives on the LogServers, StorageServers can buffer in memory and write batches to disk with a longer delay, coalescing updates for I/O efficiency.

Determining the Recovery Version

The Sequencer of a new epoch reads the previous transaction system state from Coordinators and locks it so no other Sequencer can recover concurrently, then stops the old LogServers. Each LogServer replies with two numbers: its Durable Version, the maximum LSN it has persisted, and the maximum Known Committed Version it received from any Proxy. With m old LogServers and replication degree k, once more than m-k have replied the Sequencer takes the maximum of the KCVs as the Previous Epoch's End Version, since everything below it is fully replicated, and the minimum of the DVs as the Recovery Version. The new epoch starts at PEV+1, and logs in the range PEV+1 through RV are copied from the old LogServers to the new ones to heal the replication degree - only a few seconds of data, so the copy is cheap. The first transaction of the new epoch is a special recovery transaction that tells StorageServers the RV, and they roll back by discarding in-memory multi-versioned data above it, then resume pulling from the new LogServers.

Reconfiguration, epochs and bootstrapping

FDB depends on no external service. All user data and most system metadata, under the 0xFF key prefix, live in StorageServers; the metadata about StorageServers lives in LogServers; and the configuration of the log system lives in every Coordinator. Servers use the Coordinators as a disk Paxos group to elect a ClusterController when none exists, and that ClusterController recruits a Sequencer, which reads the old log system configuration from Coordinators, spawns a new transaction system and log system, has Proxies recover the system metadata from the old log system, and finally writes the new log system configuration back to the Coordinators before accepting transactions. Each such generation is an epoch, identified by its unique Sequencer process. Because Proxies and Resolvers are stateless their recovery is free; the entire cost is in stopping and draining the old LogServers correctly.

Replication and fault-domain-aware teams

Three different replication strategies coexist. Control plane metadata sits on Coordinators under Active Disk Paxos and survives as long as a majority is live. Log records are replicated synchronously to k = f+1 LogServers, and the Proxy only answers the client once all k have persisted, so a single LogServer failure triggers a full transaction system recovery. Shards are replicated asynchronously to k = f+1 StorageServers forming a team, with each StorageServer hosting many shards so its data spreads across many teams, and DataDistributor migrating shards away from any team that loses a process. Placement is more sophisticated than Copysets: FDB builds replica sets at both host and process level so that a replica group never puts two processes in the same fault domain, meaning data loss requires simultaneous failure of every host in a selected host group.

The simulator and its fault injection

The simulator spawns many FDB servers communicating over a simulated network inside one discrete-event simulation, with the production build being a thin shim over the same interfaces to real system calls. Workloads, also written in Flow, drive the servers and carry fault injection instructions, mock applications, configuration changes and direct internal invocations, and they are composable so test cases can be assembled from pieces. Faults injected include machine, rack and data-center fail-stop failures and reboots, network partitions and latency problems, disk misbehaviour such as corruption of unsynchronized writes on reboot, and randomized event times, with injection rates tuned so an excessive fault rate does not collapse the reachable state space. On top of that sits buggification: at many points in the code base the simulation may inject unusual but contract-preserving behaviour such as an unnecessary error return, an injected delay, or an odd tuning parameter, which also guarantees no particular tuning value silently becomes necessary for correctness. Swarm testing randomizes cluster size, configuration, workloads, fault parameters, tuning parameters and which buggification points are enabled, while conditional coverage macros let a developer assert that a rare condition is actually being reached across simulation runs.

What the paper showed — measurements and proofs

The production geo-replicated Apple cluster measured has 58 machines (25 in each of the primary and remote data centers, 4 in each of two satellites), 862 FDB processes plus 55 spares, and 292 TB of data on 464 SSDs; over a month it averaged 390.4K read operations per second, 138.5K write operations per second and 1.467M keys read per second.
On that cluster, read latency averaged about 1 ms with a 99.9 percentile of about 19 ms, and commit latency averaged about 22 ms with a 99.9 percentile of about 281 ms - the commit average sits below the 60.6 ms inter-region WAN latency precisely because cross-region replication is asynchronous. The average transaction conflict rate over the month was 0.73 percent.
Scaling from 4 to 24 machines (2 to 22 Proxies and LogServers, replication degree 3), write throughput grew from 67 to 391 MBps (5.84X) at 100 operations per transaction and from 73 to 467 MBps (6.40X) at 500; read throughput grew from 2,946 to 10,096 MBps (3.43X) and from 5,055 to 21,830 MBps (4.32X); a 90/10 read-write mix grew from 593k to 2,779k operations per second (4.69X). LogServers saturate CPU at peak write, StorageServers at peak read, and Resolvers plus Proxies on the mixed workload.
On a 24-machine configuration with 2 Resolvers, 22 Proxies, 22 LogServers and 336 StorageServers, mean latencies below 100k operations per second were about 0.35 ms to read a key, 1 ms to get a read version and 2 ms to commit; at 2m operations per second Resolvers and Proxies saturate and commit latency spikes to 368 ms.
Across 289 reconfiguration traces from production clusters hosting hundreds of TBs, the median recovery took 3.08 seconds and the 90th percentile 5.28 seconds, because recovery time depends on system metadata size rather than data or log size; the measured production cluster had exactly one recovery in August 2020, lasting 8.61 seconds, which corresponds to five 9s of availability, and client reads were unaffected throughout since StorageServers keep serving.
Supporting measurements: a single-threaded Resolver sustains 280K transactions per second in a microbenchmark; StorageServer lag behind LogServers over 12 production hours had a 99.9 percentile of 3.96 ms for average lag and 208.6 ms for maximum lag; and CloudKit has deployed FDB for more than 0.5M disk years without a single data corruption event, with continuous replica comparison never finding an inconsistent replica.

Limits and trade-offs — conceded and discovered

Conceded by the paper: optimistic concurrency control does not guarantee that a transaction will ever commit, and Resolvers must retain recent commit history in memory. Worse, a transaction aborted by one Resolver may already have been admitted by others that then stamped their lastCommit, causing false-positive conflicts for unrelated transactions. FDB argues this is acceptable only because its multi-tenant production conflict rate is under 1 percent.
Conceded by the paper: the five-second MVCC window is a hard ceiling on transaction duration, chosen to bound memory in Resolvers and StorageServers, and it comes with 10 KB keys, 100 KB values and 10 MB transactions. Long-running work must be manually decomposed into many small transactions, a pattern FDB had to package as an abstraction called TaskBucket for its own backup system.
Conceded by the paper: simulation cannot reliably detect performance issues such as an imperfect load balancing algorithm, cannot test third-party libraries or any first-party code not written in Flow, and is blind to bugs in dependencies - several FDB bugs came from the true operating system contract being weaker than the team believed it to be. This forced FDB to avoid external dependencies, including deleting its Zookeeper dependency and writing its own Paxos in Flow.
Conceded by the paper: because log records must reach all k = f+1 LogServers before a commit is acknowledged, any single LogServer failure triggers a full transaction system recovery, and the whole no-quorum stance is stated to be best suited for local or metro area deployments. A manual cross-region failover after a simultaneous total region failure gives A, C and I of ACID but potentially exhibits a Durability failure.
Partly conceded, partly exposed later: the write path is the real ceiling, since every read version and commit version comes from one Sequencer advancing at a million versions per second, and the paper's own scaling test shows Resolvers and Proxies saturating while commit latency spikes to 368 ms. Section 6 already lists the mitigations underway - splitting Proxies into a get-read-version proxy and a commit proxy, adding a storage cache - and later FDB releases continued down that road, as they did in replacing the modified SQLite B-tree engine with RocksDB.

What it became — the systems that inherited it

Apple open-sourced FoundationDB in 2018, and the architecture in this paper is still what ships: Coordinators, Sequencer, Proxies (since split into get-read-version and commit proxies exactly as Section 6 anticipated), Resolvers, LogServers, StorageServers, with RocksDB eventually joining the modified SQLite engine. The layer thesis was vindicated by what got built on it - the FoundationDB Record Layer, which gives CloudKit relational structure, indexes and a query planner over the same key-value core; the Document Layer; the JanusGraph storage adapter; CouchDB rebuilding its newest line as an FDB layer; and later Deno KV and Tigris Data. Snowflake uses FoundationDB as its transactional metadata store, so the same substrate sits under a cloud data warehouse and under a mobile sync service, which is roughly the argument the paper was making. Its most transferable idea turned out to be the testing methodology: three of this paper's authors carry the antithesis.com affiliation, having founded Antithesis to sell deterministic simulation testing as a service, and TigerBeetle, RisingWave, Convex and the Rust madsim and turmoil ecosystems all build simulators in FDB's image, with the swarm testing harness open-sourced as Joshua. The unbundled shape - a stateless transaction tier over a replicated log over a storage tier that tails that log - is the same decomposition that cloud-native storage-compute separation converged on, and the f+1 recover-rather-than-mask stance remains the sharpest counter-example to the assumption that fault tolerance requires quorum agreement on the commit path.

In the paper’s words — verbatim

“FoundationDB adopts an unbundled architecture that decouples an in-memory transaction management system, a distributed storage system, and a built-in distributed configuration system.”

Abstract

“instead of fixing all possible failure scenarios, the transaction system proactively shuts down when it detects a failure. As a result, all failure handling is reduced to a single recovery operation, which becomes a common and well-tested code path.”

§2.1

“In FDB, the recovery is purposely made very cheap—there is no checkpoint, and no need to re-apply redo or undo log during recovery.”

§2.4.4

Vocabulary — as this paper uses it

Unbundled architecture: A database split so that the transaction component and the data component are separate systems, following Lomet et al. In FDB the split goes further: the transaction system, the log system and the storage system are three independently scalable tiers, and transaction logging is decoupled from the transaction component as well.
Layer: A stateless application built on top of FDB that supplies a data model, query capability or other database features that FDB deliberately omits. Layers inherit FDB's strictly serializable transactions, which is what lets a relational store, a document store and a graph store all sit on the same key-value core.
Sequencer: The singleton process that assigns every transaction its read version and its commit version, advancing versions at one million per second. Its commit versions define the serial history of the database and are used directly as Log Sequence Numbers.
Resolver: A stateless process that performs FDB's optimistic concurrency control by checking a transaction's read ranges against a history of recently modified key ranges. The key space is partitioned across Resolvers and a transaction commits only if every Resolver admits it.
LogServer: A member of the log system, acting as a replicated, sharded, distributed persistent queue that stores write-ahead log data for particular StorageServers. A commit is acknowledged only after all k = f+1 designated LogServers report the record durable.
Storage team: The group of k = f+1 StorageServers that asynchronously replicate a given shard. A StorageServer belongs to many teams so its data spreads widely, and DataDistributor moves shards off any team that loses a process.
Known Committed Version (KCV): The maximum LSN a given Proxy has confirmed committed, meaning every replica LogServer acknowledged it durable. Proxies piggyback their KCV on log messages, and recovery takes the maximum KCV across LogServers as the previous epoch's end version.
Recovery Version (RV): The chosen end of the redo log for a failed epoch, computed as the minimum Durable Version across the old LogServers. Any data above the RV in old LogServers and StorageServers is discarded, which is FDB's entire substitute for undo log processing.
Buggification: A fault injection technique in which the code base itself offers the simulator opportunities to inject unusual but contract-preserving behaviour, such as returning an error from an operation that normally succeeds, delaying a fast operation, or picking an odd tuning parameter. It makes rare states common and ensures no tuning value quietly becomes necessary for correctness.

On the timeline — where this sits in the story

Year2009; open-sourced 2018

MilestoneFoundationDB as a layered distributed transaction substrate

Problem solvedMany distributed databases need serializable transactions, but building reliable transaction infrastructure repeatedly is hard.

How it solved itFoundationDB separated a transactional core from higher-level layers and storage abstractions.

Why it matteredShowed a layered path for building multiple data models over a strong distributed transaction substrate.

DDIACh. 8: Transactions Ch. 10: Consistency & Consensus

View on the timeline