Distributed Databases — CAP, Replication and Consensus

The moment you add a second copy of your database, a brand-new question appears: which copy is right? Replication, quorums, CAP, two-phase commit, Raft and eventual consistency — from zero assumed knowledge down to the parameters you actually set in PostgreSQL and Cassandra.

In Search of an Understandable Consensus Algorithm (Raft) — Diego Ongaro

The metaphor: the same ledger in three branch offices

Imagine a firm that keeps an identical ledger in Tokyo, Osaka and Singapore. Any branch can read a balance, any branch can write one, and if a building burns down the books survive.

The trouble starts when the line between branches goes down. A customer walks into Tokyo and asks to withdraw $1,000. The Tokyo ledger says the money is there. But what if the same customer is standing in Osaka withdrawing at the same moment? With the link down, Tokyo has no way to find out.

Two roads out. Refuse — "I can't confirm this right now, so I can't serve you" — or pay out on the assumption that it's probably fine, and reconcile later. The first stops business; the second accepts that a balance may go negative.

Nearly all of distributed database theory is a restatement of that choice. What happens inside a single machine is covered in Database Internals and Transactions and ACID; here we only chase what newly breaks once there is more than one machine.

Why not just keep one machine

Three reasons to add machines. Things break — disks die, power fails, data centres flood. A single-box system is exactly as available as that box. Things don't fit — one machine has a ceiling on disk and RAM. Things are far away — asking a Tokyo server from Tokyo takes milliseconds; asking it from the other side of the planet costs close to 100 ms round trip on the speed of light alone. You can pay for better links, but you cannot negotiate with physics.

There are two answers. Breakage is met with replication (keep the same data on several machines); capacity is met with sharding (split the data across machines). Real systems stack both — cut the data into a hundred pieces, keep three copies of each piece. This article is about the first one: when several copies of the same data exist, which one counts as the truth?

Replication — who writes, who copies

There are three ways to hold the copies.

Single-leader picks one machine to accept writes; the rest only copy. This is the default shape of PostgreSQL, MySQL and MongoDB, and it is easy to reason about because "who is right" is settled by definition. The price is that when the leader dies, writes stop until a successor is chosen.

Multi-leader allows several machines to accept writes. You can put a write endpoint in each region, so writes are close and fast. The price is that the same row can be written in two places at once, and you now owe an answer to "how do conflicts get resolved?"

Leaderless has clients write to several machines directly and read from several directly. Amazon's 2007 Dynamo paper is the origin of the style; Cassandra is the best-known descendant. There is no single point of failure, but you have to decide for yourself how many replies count as success.

Two of the three go to the trouble of appointing a leader, and there is a reason. With $n$ machines, a leader fanning writes out to everyone grows in proportion to $n$, while everyone checking with everyone grows as $n^2$. That difference decides whether the machines you added for durability quietly turn into latency.

To wait or not to wait

After the leader has written to its own disk, does it return success after confirming that a copy landed elsewhere, or before? That is the first fork in the road.

Not confirming (asynchronous) is fast. But if the leader dies immediately afterwards, writes that nobody else had yet received are gone. You told the client "committed" and then lost it — that is the defining property of the configuration, not a bug in it. Confirming (synchronous) loses nothing, but one slow replica is enough to drag every write down to its speed.

In PostgreSQL you choose the depth with synchronous_commit (local means your own disk; remote_apply means waiting until the standby has applied the change and can serve it to readers). The trap is one step further out. Semi-synchronous implementations almost always carry a timeout, and when the standby stops answering they silently fall back to asynchronous. Availability is preserved, but the system you believe is synchronous is now not. If nobody watches for that transition, you find out at the next failover, when data disappears.