Replication and Quorums

The first time I set up database replication for a project, I thought of it as a backup that also took read traffic. Copy the data to a second machine, point the reports there, done.

Then the first failover happened. The primary’s disk died, we promoted the replica, and everything came back in two minutes. Great. Except the replica had been 4 seconds behind, so the last 4 seconds of orders, about 300 of them, existed only on the dead disk. Customers had paid and received confirmation SMS for orders that no longer existed in our database. We spent two days reconstructing them from payment gateway reports.

Replication is one of the most useful tools in distributed systems, and every form of it comes with a catch. This lesson is about knowing which catch you’ve signed up for.

Why Replicate?

We keep copies of the same data on multiple machines for three reasons:

1. Availability: if one machine dies, another has the data and can take over.
2. Read scaling: spread read traffic across many copies.
3. Latency: keep a copy close to users (a replica in Mumbai for Indian users, one in Frankfurt for European users).

If the data never changed, replication would be trivial: copy it once. All the difficulty comes from changes. How does a write reach every copy, and what happens to readers and writers while it’s on the way?

There are three basic answers.

Single-Leader Replication

One node is the leader (primary). All writes go to it. It records each change in a log and sends the log to followers (replicas), which apply the changes in the same order. Reads can go to the leader or to followers.

This is how Postgres, MySQL, MongoDB replica sets, Redis replication, and each Kafka partition work. It’s by far the most common setup, because it has one huge advantage: there’s only one place where writes happen, so there are no write conflicts. The leader’s log defines the order.

Synchronous vs asynchronous

The big decision is when the leader says “OK” to the client:

• Asynchronous: as soon as the leader has the write. Followers catch up shortly after. Fast, and a slow follower doesn’t slow down writes. But if the leader dies, writes that hadn’t reached a follower are lost when you promote that follower. That was my 300 lost orders.
• Synchronous: only after at least one follower also has it. No data loss on failover (as long as you promote the in-sync follower). But every write pays a network round trip, and if the synchronous follower is down or slow, writes stall.

Most production setups use a mix: one synchronous follower in another availability zone (so a single failure never loses data), and the rest asynchronous. Postgres calls this synchronous_standby_names = 'ANY 1 (a, b)'; MySQL has semi-synchronous replication; managed services like RDS Multi-AZ do it for you. (The Database Internals course shows real Postgres replication lag numbers and the replica problems that come with it.)

Failover is harder than it looks

When the leader dies, someone has to:

1. Detect that it’s dead. But “dead” and “slow” look the same from outside. Too sensitive, and a GC pause triggers an unnecessary failover. Too relaxed, and you’re down for minutes.
2. Choose a new leader, ideally the most up-to-date follower.
3. Reconfigure clients to send writes to the new leader.
4. Make sure the old leader stops. If the old leader was only slow, not dead, it might come back and keep accepting writes. Now you have two leaders, each accepting different writes. This is called split brain, and it’s one of the worst things that can happen to a database.

Doing this correctly needs the nodes to agree on who the leader is, which is exactly the consensus problem we’ll solve with Raft in Lesson 6. That’s why tools like Patroni (for Postgres) use etcd or Consul under the hood: they borrow a consensus system to make the leader decision safely.

Multi-Leader Replication

Sometimes one leader isn’t enough. If your users are in India and Europe, sending every European write to a leader in Mumbai adds 120-150 ms per write. With multi-leader replication, each region has its own leader that accepts writes locally and replicates them to the other leaders asynchronously.

Other places multi-leader shows up, sometimes without people realising it:

• Offline-first mobile apps: each phone is effectively a leader while offline, and syncs later.
• Collaborative editing (Google Docs style): every user’s browser is a leader for their own edits.
• Calendar or notes apps syncing across devices.

The price is write conflicts. If a user changes their delivery address in Mumbai and the support team changes it in Frankfurt at the same moment, both leaders accept the write, and when they sync, they disagree.

Ways to deal with conflicts, from simplest to most robust:

• Avoid them: route all writes for one user to one “home” leader. Conflicts become rare (only during failover). This is the most practical approach in most systems.
• Last-write-wins: pick the write with the later timestamp. Simple, but as we saw in Lesson 3, it silently loses data when clocks disagree.
• Merge: keep both versions and combine them with application logic (union of cart items, for example), using version vectors to detect concurrency.
• CRDTs: data types designed so that merging always gives the same answer regardless of order (counters, sets, text sequences). Used by collaborative editors and some databases (Riak, Redis Enterprise’s active-active).

My honest advice: avoid multi-leader replication for your core data unless you really need it. If you do, make conflict handling an explicit part of the design, not an afterthought.

Leaderless Replication and Quorums

Amazon’s Dynamo paper (2007) popularised a third approach: no leader at all. The client (or a coordinator node acting for it) sends each write to several replicas at once, and reads from several replicas at once. Cassandra, ScyllaDB and Riak work this way, and DynamoDB’s design is inspired by it.

Three numbers control it:

• N: how many replicas hold each piece of data (often 3).
• W: how many replicas must confirm a write before it’s considered successful.
• R: how many replicas must respond to a read.

With N = 3, W = 2 and R = 2, a write succeeds when 2 of the 3 replicas have it, and a read asks 2 replicas and takes the newest value it gets.

Why W + R > N works

If W + R > N, the set of replicas you wrote to and the set you read from must overlap in at least one replica. And that replica has the latest write.

To make this concrete, I wrote a small simulation. Three replicas; each receives a write after a random delay averaging 20 ms; the client reads 10 ms after its write was acknowledged. For each setting I ran 20,000 write-then-read pairs and counted reads that returned the old value:

W=1 R=1  (W+R <= N): stale reads 40.84%
W=2 R=1  (W+R <= N): stale reads 20.22%
W=1 R=2  (W+R <= N): stale reads 12.45%
W=2 R=2  (W+R >  N): stale reads  0.00%
W=3 R=1  (W+R >  N): stale reads  0.00%
W=1 R=3  (W+R >  N): stale reads  0.00%

The numbers depend on my made-up delays, but the pattern doesn’t: once W + R > N, the stale reads go to zero. Below that line, staleness depends entirely on luck and timing.

You can choose the trade-off per use case:

• W = N, R = 1: fast reads, slow and fragile writes (one dead replica blocks writes).
• W = 1, R = N: fast writes, slow reads.
• W = R = 2 with N = 3 (Cassandra’s QUORUM): balanced; tolerates one replica down for both reads and writes.
• W = 1, R = 1 (Cassandra’s ONE): fastest, but eventually consistent. Fine for view counts or activity feeds, not for balances.

How stale replicas catch up

Since there’s no leader pushing a log, leaderless systems repair stale replicas in two ways:

• Read repair: when a read gets different versions from different replicas, the client writes the newest version back to the stale ones.
• Anti-entropy: a background process compares replicas (using Merkle trees, so it doesn’t have to compare every row) and copies missing data.

Also, hinted handoff: if a replica is down during a write, another node stores the write as a “hint” and delivers it when the replica comes back.

Quorums are not magic

It’s tempting to think W + R > N gives you strong consistency. It doesn’t, quite. Some ways it falls short:

• Sloppy quorums. When some of the “home” replicas for a key are unreachable, some systems accept the write on other nodes temporarily (with hinted handoff) to stay available. The write “succeeded” with W = 2, but the 2 nodes aren’t the ones a later read will ask. The overlap guarantee is gone until the hints are delivered.
• Concurrent writes. Two clients writing the same key at the same time still conflict. The replicas need a way to decide, usually last-write-wins with timestamps, with all the clock problems from Lesson 3.
• Failed writes aren’t rolled back. If a write reached only 1 of the required 2 replicas, the client gets an error. But that 1 replica keeps the value, and read repair may spread it to the others later. So a “failed” write can appear in later reads. Sound familiar? It’s Lesson 2’s “timeout means unknown” again.
• A read during a write can see the new value from one replica and then, on a second read, the old value from another. Reads aren’t guaranteed to be monotonic without extra work.

For strict guarantees (like “a username can only be taken once”), leaderless stores offer extra mechanisms (Cassandra’s lightweight transactions use Paxos under the hood) at a significant latency cost.

Choosing a Replication Style

Pitfalls to Avoid

1. Treating async replicas as zero data loss. A failover can lose the last few seconds of writes.
2. A single synchronous replica. If it goes down, writes stall. Use “any 1 of 2”.
3. Home-grown failover scripts. They’re where split brain comes from. Use a consensus-backed tool.
4. Multi-leader without a conflict strategy. Conflicts will happen; decide in advance how they’re resolved.
5. Assuming W + R > N means strongly consistent. Sloppy quorums, concurrent writes and partial failures still leak through.
6. Using consistency level ONE for data that needs correctness, because it was fastest in a benchmark.
7. Forgetting that a failed quorum write may still appear later.

Quick Recap

• Replication gives availability, read scaling and lower latency, and all the difficulty is in handling changes.
• Single-leader: simple, no conflicts; async replicas can lose recent writes on failover, and failover itself needs consensus to avoid split brain.
• Multi-leader: local writes everywhere, but you must handle conflicts. Avoid it for core data if you can.
• Leaderless: write to W of N, read from R. In the simulation, W + R > N took stale reads from 40.8% to zero.
• Quorums still have gaps: sloppy quorums, concurrent writes, and “failed” writes that survive.

Next lesson: what “consistent” actually means. The spectrum from linearizable to eventual, CAP and PACELC in plain words, and a real etcd test showing both sides of the trade-off.