System Design HLD-07.03
Multi-leader and leaderless replication
Writes accepted in several places: conflicts and how to resolve them, Dynamo-style quorums with N, R and W, hinted handoff, read repair and Merkle trees.
The big idea
With a single leader, every write in the world travels to one machine. That is a latency problem for users far away, and an availability problem whenever the leader or the path to it is down. The alternative is to accept writes in more than one place. In multi-leader replication, each region has its own leader, and leaders exchange changes asynchronously. In leaderless replication, popularized by Amazon's Dynamo, there is no leader at all: the client writes to several replicas directly and reads from several replicas, and overlap between the two sets provides consistency.
Both buy availability and low write latency, and both pay with the same new problem: two places can accept conflicting writes to the same data at the same time, and someone has to decide what the final value is.
Think of two branches of a shop sharing one stock spreadsheet that syncs each night. Each branch can sell immediately without phoning the other, but on a busy day both may sell the "last" item, and the nightly sync has to sort it out.
How it works
Step 1: Conflicts and how to resolve them
When two leaders, or two leaderless replicas, accept different writes to the same key concurrently, the system must converge on one value. Options:
- Last write wins (LWW): attach a timestamp and keep the latest. Simple and widely used, but it silently discards the other write, and clocks on different machines disagree ( Time and clocks ).
- Application merge: keep both versions ("siblings") and let the application combine them. Amazon's shopping cart merges by taking the union of items, which can resurrect a deleted item but never loses an added one.
- CRDTs: conflict-free replicated data typesConflict-free replicated data types: data structures such as counters, sets and text whose concurrent updates always merge to the same result, regardless of order., such as counters and sets designed so concurrent updates merge automatically and deterministically. Collaborative editors and distributed counters use them.
- Avoid conflicts: route all writes for a given record (a user's data, say) to one "home" leader, so conflicts only happen during failover.
Step 2: Leaderless quorums
Each key has N replicas. A write is successful once W of them acknowledge; a read queries R of them and takes the newest version it gets (using version numbers or vector clocks). If R + W > N, every read set overlaps every write set in at least one replica, so reads see the latest acknowledged write. A common setting is N = 3, W = 2, R = 2: it tolerates one replica being down for both reads and writes.
Try it
Try this:
- Start at N = 3, W = 2, R = 2. Then fail one node: still consistent and available. Fail two: neither reads nor writes can reach a quorum.
- Set W = 1, R = 1: very fast and available, but the worst-case read returns v1, stale data.
- Set W = 3, R = 1: reads are cheap and always fresh, but a single failed node blocks all writes.
Step 3: Repairing replicas
Replicas that missed writes must catch up:
- Read repair: when a read sees a stale replica, it writes the newest value back to it.
- Hinted handoff: if a replica is down during a write, another node temporarily stores the write with a "hint" and delivers it when the replica returns. Accepting writes on substitute nodes is called a sloppy quorumAccepting writes on whatever healthy nodes are reachable, even if they are not the key's usual replicas, and handing them back later.: more available, but R + W > N no longer guarantees overlap with the usual replicas.
- Anti-entropy: a background process compares replicas and fixes differences. To avoid comparing every key, replicas compare Merkle treesA tree of hashes where each parent is the hash of its children, so two replicas can find which ranges differ by comparing a few hashes. and only descend into ranges whose hashes differ.
Going deeper
Quorums are not linearizability
Even with R + W > N, edge cases (concurrent writes, sloppy quorums, a write that succeeded on fewer than W nodes and was not rolled back) mean leaderless systems do not give the strongest guarantees. Treat them as highly available, eventually consistent stores with tunable staleness, and use consensus-based systems ( Consensus: Raft ) when you need strict guarantees.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Single leader | Simple ordering and no write conflicts | Write latency far from the leader and availability during failover |
| Multi-leader | Multi-region writes with local latency; offline-capable clients | Conflict resolution, which is easy to get subtly wrong |
| Leaderless quorums | High availability and tunable consistency per request (N, R, W) | Strict consistency, plus the cost of repair mechanisms |
Common mistakes
- Using last-write-wins for data where losing a concurrent write matters, such as counters or carts.
- Choosing R + W less than or equal to N and expecting reads to see recent writes.
- Running multi-leader replication without a plan for conflicts, then discovering them in production.
- Forgetting anti-entropy, so rarely read keys stay inconsistent for a long time.
In the wild
Amazon
Dynamo: Amazon's highly available key-value store (opens in a new tab)The 2007 Dynamo paper (Werner Vogels and colleagues) explains a store built so that customers "should be able to view and add items to their shopping cart even if disks are failing, network routes are flapping, or data centers are being destroyed by tornados". It uses consistent hashing with virtual nodes, quorums with tunable N, R and W (a common configuration being N = 3, R = 2, W = 2), hinted handoff when replicas are unreachable, vector clocks to track versions with the application reconciling conflicts, and Merkle trees for anti-entropy. It also measures performance at the 99.9th percentile rather than the average.
Check yourself
-
With N = 5, which R and W guarantee that reads overlap the latest write?
Show answer
B. R = 3, W = 3 Overlap requires R + W > N: 3 + 3 = 6 > 5. The others sum to 5 or less.
-
What is the main new problem with multi-leader replication?
Show answer
B. Conflicting concurrent writes that must be resolved Two leaders can accept different writes to the same data at the same time.
-
What does last-write-wins risk?
Show answer
B. Silently discarding one of two concurrent writes Only the write with the later timestamp survives; the other is lost without notice.
-
What do Merkle trees help with?
Show answer
B. Finding which key ranges differ between replicas without comparing every key Comparing hashes top-down quickly narrows down the ranges that need repair.
Recap
- Multi-leader and leaderless replication accept writes in several places for availability and latency.
- Concurrent writes conflict: resolve with LWW, application merge or CRDTs, or avoid by routing.
- Leaderless quorums: write to W of N, read from R; R + W > N makes them overlap.
- Read repair, hinted handoff and Merkle-tree anti-entropy bring replicas back in sync.
- Quorums give tunable, not strict, consistency.
Next up
- Crack the system design round learning path