The Algorithms Behind Consistent Distributed Databases

Consistency in distributed databases has traditionally meant a trade-off: stronger guarantees came at the cost of performance. This article examines a series of modern algorithms — Percolator, Spanner, Calvin, and FaunaDB's transaction protocol — that challenge that trade-off. Each takes a different technical approach to reducing latency while maintaining strong consistency.

Why Consensus Is Expensive

Distributed databases keep multiple replicas of data, both for redundancy and to serve users in different geographic regions. Because every replica should reflect the same state of the data, replicas must reach agreement on transactions. That's where the cost creeps in.

Cross-data-center communication is physically constrained: a round trip between New York and Paris takes roughly 40 milliseconds at the speed of light, and that's before protocol overhead. For a transaction to be confirmed across distant replicas, it traditionally requires multiple rounds of communication.

Most distributed databases use a two-phase commit, which needs two rounds: first a prepare phase, where every replica acknowledges it can commit the transaction and persists it to a transaction log; then a commit phase, where the results are calculated and stored. Improved consensus protocols like Paxos and Raft build on this foundation, but require only a majority of nodes to respond and automatically elect new leaders when a coordinator fails. Still, they face the same fundamental latency problem. Some databases require multiple consensus rounds — for example, Cassandra's light-weight transactions first reach consensus on reads, then consensus on writes, potentially adding 320ms or more in round trips.

Locks compound the expense. To prevent conflicting writes, most databases lock data for the duration of a transaction, forcing other transactions to wait. The duration of those locks significantly influences overall performance.

2010: Percolator

Google built Percolator on BigTable as an internal incremental processing engine for its search index, and released the paper in 2010. It proved influential enough to inspire FoundationDB, which Apple acquired and which published its own paper in 2019. Rather than accept weaker guarantees, Percolator implemented strong consistency using two ingredients: versioning and a Timestamp Oracle.

Versioning means every data change is stored as a new version rather than overwriting the previous state. This provides two key benefits. First, failure recovery becomes cheap: a node that comes back online after an outage can request only the changes made since its last checkpoint rather than copying an entire dataset. Second, it enables snapshot consistency, where a transaction reads from a fixed snapshot of the data at its start, works with that snapshot, then writes a new version at the end. Conflicts are handled by checking whether the snapshot's values changed before the write is committed; if so, the transaction rolls back and restarts.

The second ingredient solves a problem versioning introduces: coordinating time across machines. Local clocks can drift apart by hundreds of milliseconds, which is meaningful for correctly ordering transactions that span multiple nodes. Percolator's answer is the Timestamp Oracle, a central system that hands out monotonically increasing timestamps. But each transaction requires two calls to the Oracle — one to read a snapshot, one to tag the new version — and that adds latency if the Oracle sits far from the nodes making the calls.

2012: Spanner

Google's Spanner, first described in a 2012 paper and released to the public as Spanner Cloud in 2017, was the first globally distributed database with strong consistency. It keeps Percolator's versioning, which also allows developers to run fast "snapshot reads" with a configurable maximum age for data — effectively per-query consistency tuning.

Spanner replaces the Timestamp Oracle with the TrueTime API, which does not return a single timestamp but an interval in which the true current time is guaranteed to fall. TrueTime keeps clock drift to within 7 milliseconds by using time synchronization built on GPS and atomic clocks. The Commit-wait mechanism handles the residual uncertainty: before committing a write, Spanner simply waits to ensure the timestamp it assigns has already passed on all nodes. That guarantee requires specialized hardware — commodity servers with less accurate clocks would need a wait period of hundreds of milliseconds.

2012: Calvin

Calvin, published by researchers at Yale in 2012, takes a radically different architectural approach. It reduces the worst-case number of cross-datacenter messages to two, bringing latency for global transactions below 200 milliseconds and theoretically below 100. The key is a different way of handling ordering, enabled by deterministic transactions.

Calvin requires transactions to be deterministic: a transaction's outcome must be identical no matter which machine executes it. This means pre-computing values like the current time and disallowing interactive transactions, where user input arrives mid-transaction. In exchange, Calvin can separate the problem of ordering from the problem of execution.

In a typical database, locks are held until all nodes agree on what to write. Calvin only needs to hold a lock until the nodes agree on ordering. Once every node knows the global order, each replica can execute deterministic operations independently and arrive at the same result, since the order alone determines the outcome. This dramatically shortens lock duration and reduces the amount of communication across data centers — essentially only the ordering step requires coordination, and protocols like Raft handle that in two hops.

The original paper reports that Calvin sustains half a million transactions per second on commodity clusters, comparable to world-record results that had been achieved only with much higher-end hardware. Because Calvin doesn't rely on specialized time hardware, it can run on any cloud provider.

FaunaDB's Transaction Protocol

FaunaDB's protocol, introduced in 2014, shares Calvin's inheritance. Data is versioned, transactions are deterministic, and ordering is separated from execution. FaunaDB makes versioning a first-class user-visible feature: developers can run time-traveling queries against historical data, which is useful for recovering overwritten data, auditing changes, or building application features that depend on the past state of an entity.

The crucial difference from Calvin is that FaunaDB calculates each transaction only once — optimistically, in the node where the transaction arrives, before consensus on ordering. The node stores both the calculated result and the original input values in a transaction log. After the order is agreed upon, FaunaDB verifies that the inputs haven't changed (thanks to versioning). If a conflicting transaction changed them, the transaction aborts and restarts. Otherwise, the pre-calculated result is applied on all nodes without further computation. That's a distinct advantage: Calvin may execute the same transaction multiple times across nodes. FaunaDB salvages the result while still gaining the benefits of Calvin's reduced lock duration and communication overhead.

The Performance/Consistency Trade-Off Is Not Inevitable

Each generation of these systems — Percolator through FaunaDB's protocol — finds a different path around the classic trade-off between consistency and performance. Percolator centralizes time; Spanner distributes it with specialized hardware; Calvin reorders transactions deterministically first, avoiding expensive coordination; FaunaDB pre-calculates transactions once to economize on computation.

These systems show that developers no longer need to sacrifice correctness for speed. For teams evaluating databases today, "consistent" doesn't necessarily mean "centralized" or "slow" anymore. Consistent-by-default systems can serve low-latency, data-intensive applications without requiring special hardware or deep distributed-systems expertise.