Replication: Single-Leader, Multi-Leader, Leaderless, and Three Replication-Lag Anomalies

· tech

#distributed-systems#book-notes#replication

📑 Contents

Into Part II, and data starts crossing machines. The first move is replication: the same data on several nodes, for three reasons — serve on when one machine dies (high availability), keep data close to users (low latency), spread read traffic (read scaling). If data never changed, replication would be copy-paste; all the difficulty is in “data changes” — how does a change reach every replica? I took apart one flavour of this (single-leader, asynchronous) in practice in the Redis replication post; this one climbs to DDIA’s altitude: every replication scheme in the world is one of three topologies, and what distinguishes them is “where you handle write conflicts”.

Three topologies: conflicts don’t disappear, they move

Single-leader Leader follower follower all writes conflicts: killed at source (one writer) price: failover is hard (who takes over?) MySQL / Postgres / Redis / Kafka Multi-leader Leader A Leader B datacenter 1datacenter 2 both edit the same row → conflict! gain: write locally, survive a netsplit price: resolve write conflicts later multi-DC / offline editing / collaborative docs Leaderless replica replica replica client writes n copies at once quorum: w + r > n gain: no leader, no failover price: complex paths, read repair Dynamo / Cassandra Three answers to one question: block conflicts at the source, resolve later, or reconcile on read?
Single-leader: all writes go through the one leader — conflicts are eliminated at the source (one write point); the price is that failover when the leader dies is hard (who notices, who takes over, how do you avoid split brain). Multi-leader: each datacenter has its own leader accepting local writes, and they sync with each other — you can write through a network partition, but when both sides edit the same row the conflict has to be resolved afterwards (who wins? how do you merge?). Leaderless: no leader; clients write to several replicas at once and read from several, relying on the overlap of w + r > n to guarantee they see the new value — no failover, but the read/write paths get complicated (a stale read triggers read repair to write the new value back). Conflicts don't disappear, they move — the three topologies are a choice of where they go

The leaderless quorum deserves one more line: with n replicas, a write needs w acknowledgements and a read asks r replicas; as long as w + r > n (say n=3, w=2, r=2), the read set and write set must overlap, so you’re guaranteed to hit at least one replica with the latest value (and pick the newest among them). The maths is beautiful — but DDIA honestly lists the edges: ordering concurrent writes is hard, a partially failed write isn’t rolled back, and sloppy quorums loosen the guarantee. It’s a probabilistically strong engineering guarantee, not an absolute mathematical proof — a distinction we’ll return to in the consensus chapter.

Three replication-lag anomalies: name them, then prescribe for them

As long as replication is asynchronous (nearly all of it is, for the trade-offs in the Redis post), replicas are always half a beat behind, and all sorts of “what the hell” read results appear. DDIA’s most valuable contribution is giving these anomalies names — three diseases, three prescriptions:

① Can't read your own write read-your-writes I comment → written to leader ✓ refresh → comment is gone?! (hit a replica that hasn't caught up) cure: own data → read the leader ② Time goes backwards monotonic reads 1st read: see comment (fresh replica) 2nd read: comment gone (stale replica) (two reads hit replicas at different progress) cure: pin each user to one replica ③ Causality reversed consistent prefix observer first sees: "A: No" then sees: "Q: Have you eaten?" (Q and A on different partitions, lag differs) cure: causal writes → same partition The anomalies are physics, you can't remove them — but each has a cheap targeted cure, no full strong consistency needed
Three anomalies, three prescriptions: ① read-your-writes — you just commented, refreshed, and it's gone (you read a lagging replica); the cure is "read your own data from the leader, everyone else's from anywhere". ② monotonic reads — two reads hit replicas at different progress, things appear then vanish, like time going backwards; the cure is "pin each user to the same replica" (pick the replica by user id, say). ③ consistent prefix — question and answer go to different partitions replicating at different speeds, so an observer sees the answer before the question; the cure is "causally related writes go to the same partition". Note that each prescription treats only that disease, at low cost — that's the spirit of tiered consistency: prescribe on demand, rather than reaching for the most expensive strong consistency because of an anomaly

The three prescriptions together are the folk version of causal consistency: don’t chase “the whole world in sync”, just guarantee that “the part that concerns you and is causally connected looks right”. That’s what most products actually want — and it’s vastly cheaper than strong consistency.

Reflections

Three topologies are three choices of where to put the conflict

Having read the chapter, I compress the three topologies into one line: write conflicts don’t disappear, they move — you’re only choosing where they go. Single-leader kills conflicts at the source (one write point) and moves the difficulty to failover (who notices, who takes over, how do you avoid split brain); multi-leader lets every site write and moves the difficulty to after-the-fact conflict resolution (LWW silently drops data; merge logic is the application’s pain); leaderless skips leaders and moves the difficulty into every read and write path (quorums, read repair). This “conservation of difficulty” lens is the same thinking as “there’s no truly stateless system, only systems that push state elsewhere” from the infra series. So when choosing a replication scheme my question changed from “which is best” to “which of these three pains can my team swallow best?” — for most teams the answer is single-leader, because the failover pain is carried for you by Sentinel, K8s and managed services, while the conflict-resolution pain you can only swallow yourself.

Naming the anomalies is this chapter’s most underrated contribution

read-your-writes, monotonic reads, consistent prefix — on first read they look like academic vocabulary, but once you’ve been in the trenches you know: these names are handles that turn superstition into tickets. A user reports “my comment disappeared, then reappeared on refresh” — someone who hasn’t read this chapter treats it as a haunting and restarts the service; someone who has says at once “that’s monotonic reads broken, pin the user to one replica” — a disease with a name has a prescription, and a price estimate. It’s the same power as the “state → cause” lookup table in K8s troubleshooting: a big part of engineering ability is having a “symptom → disease → cure” dictionary in your head. This chapter is the few pages of that dictionary for replication lag; memorise it and it repays the whole book’s price.

Consistency is a menu, not a switch

The most practical mindset this chapter taught me: consistency isn’t on/off, it’s a tiered menu — everything (strong consistency) is the most expensive, nothing (eventual consistency) is the cheapest but anomaly-ridden, and in between sits a row of “single-point cures”: own data from the leader, one user pinned to one replica, causal writes in the same partition. Most products don’t want “the whole world consistent in real time”, they want “the part that concerns me looks right” — two or three cheap prescriptions cover that, no need to upgrade the whole system to synchronous replication or distributed consensus. It’s a brake I hit often in architecture reviews: someone meets a lag anomaly and shouts “go strongly consistent”, and I first ask — which of the three diseases are your users actually hitting? Prescribe for that one and the cost is often a tenth. Scenarios that truly need strong guarantees wait for the consensus chapter later; until then, remember this: buying consistency is like buying insurance — buy the items you need, not the full package.