Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Scaling Data

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.

Advanced 14 min Last reviewed

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

A leaderless write and read with N = 3, W = 2, R = 2 A client writes value v2 to three replicas; two acknowledge, so the write succeeds while the third replica still holds v1. A later read asks two replicas; because two plus two is greater than three, at least one of them has v2, and the client returns the newest value. ack ack lost Writer Reader Replica 1 v2 Replica 2 v2 Replica 3 v1 (missed write) newest wins: v2 Figure 1. With N = 3, the write succeeds after W = 2 acknowledgements. A read from any R = 2 replicas must include at least one that has v2, because 2 + 2 > 3. The overlap (glowing) is the whole trick.

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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. 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.
  2. Set W = 1, R = 1: very fast and available, but the worst-case read returns v1, stale data.
  3. 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

OptionWins whenLoses 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up