Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Replication

Multi-Leader and Leaderless Replication

Learn how multi-leader and leaderless (Dynamo-style) replication handle concurrent writes: conflicts, last-write-wins, merging and anti-entropy, with simulations.

With one leader and several followers, life is simple: every write goes through a single node, so the writes have one order and conflicts cannot happen. The price is that the leader is a bottleneck, and that clients far away from it pay a long round trip for every write.

Two other designs let more than one node accept writes. Multi-leader replication has several leaders that copy each other's changes. Leaderless replication, popularized by Amazon's Dynamo paper, has no leader at all: a client writes to several replicas directly. Both are faster and more available, and both introduce the same new problem: two people can change the same data at the same moment on different nodes. This lesson shows where such write conflicts come from, the main ways to resolve them, and how replicas that missed a write catch up.

Where multiple leaders make sense

Why accept writes in many places?

Many data centers Each region has a local leader, so writes stay fast.
Offline devices A phone is a leader that syncs later.
Collaborative editing Every user edits a local copy.
Survives a region outage The other leaders keep accepting writes.

The price is conflicts, and you must decide how to resolve them.

1 / 2

Each leader applies a client's write locally, answers immediately, and sends the change to the other leaders asynchronously. Nobody waits for a distant data center. But between the local write and the arrival of the remote change, the leaders disagree.

Write conflicts

Imagine a shared document title stored in two regions. A user in Berlin renames it to "Q3 plan" while, at nearly the same moment, a user in Tokyo renames it to "Q3 budget". Both writes are accepted locally. When the leaders exchange changes, each one sees a write that is concurrent with its own: neither writer had seen the other's change (see vector clocks for how to detect this precisely).

sequenceDiagram
    participant B as Leader Berlin
    participant T as Leader Tokyo
    B->>B: title = "Q3 plan"
    T->>T: title = "Q3 budget"
    B->>T: replicate "Q3 plan"
    T->>B: replicate "Q3 budget"
    Note over B,T: Each leader now holds a different value unless a rule decides

Both leaders accepted a write, so each must decide what to do with the other's.

If each leader simply applies whatever arrives last, Berlin ends with "Q3 budget" and Tokyo ends with "Q3 plan". The replicas have diverged forever. The rule: every replica must converge to the same value, no matter in which order the writes arrive.

Strategy 1: avoid conflicts

The easiest conflict is the one that cannot happen. If all writes for one record always go through the same leader (for example, a user's profile is always written in the user's home region), then each record behaves as if it had a single leader. This works well until the home region fails or the user travels, and then you are back to needing a real resolution rule.

Strategy 2: last write wins

Last write wins (LWW) attaches a timestamp to every write and keeps the one with the highest timestamp. All replicas apply the same rule, so they converge. It is simple, and many databases offer it.

The catch: a concurrent write is silently thrown away. With skewed wall clocks the "last" write may even be the older one. LWW is acceptable for data where losing an update is harmless (a cache entry, a "last seen" time) and dangerous for anything else.

Strategy 3: merge the values

Instead of choosing one writer, combine them. If two users concurrently add different items to a shopping cart, the right answer is the union of the items. The system can keep both values (often called siblings) and let the application, or the next reader, merge them. Automatic merge rules built into the data type are the topic of CRDTs.

Let us compare LWW and merging in a simulation. Two replicas of a shopping cart each receive an update, then exchange them.

Python LWW loses an update, a merge keeps both

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both replicas agree in each case, which is what convergence demands. But LWW dropped the bread, while the merge kept both additions.

Leaderless replication

In a leaderless (Dynamo-style) design, a client sends each write to several replicas in parallel and considers it done when enough of them reply. Reads also ask several replicas. Quorums decide how many are enough. There is no failover, because there is no leader to fail; a replica that is down simply misses writes.

That means replicas will fall behind and need two repair mechanisms:

  • Read repair: when a read sees different versions from different replicas, the client writes the newest version back to the stale ones.
  • Anti-entropy: a background process compares replicas and copies missing data. Comparing every key would be expensive, so systems compare compact summaries (such as Merkle trees, trees of hashes) and only transfer the ranges that differ.
flowchart LR
    C["Client"] -->|"write v2"| R1["Replica 1: v2"]
    C -->|"write v2"| R2["Replica 2: v2"]
    C -.->|"lost"| R3["Replica 3: v1 (stale)"]
    R3 <-->|"anti-entropy: compare, copy v2"| R1

The write missed replica 3; the background anti-entropy exchange fixes it later.

Simulating anti-entropy

The simulation below has three replicas that each store a key with a (timestamp, value) pair. Writes land on random replicas (some are dropped), then rounds of pairwise anti-entropy exchange the newest version of every key. We count how many rounds it takes until all replicas are identical.

Python Anti-entropy brings replicas together

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the exchange is symmetric and the merge rule is deterministic. Those two properties are why the replicas can only move closer together, never apart.

Dynamo-style design in one page

The ideas above combine into the classic recipe:

  1. Spread keys over nodes with consistent hashing; each key is stored on N consecutive nodes.
  2. Write to W replicas and read from R replicas, with R + W > N for overlap.
  3. Tag versions with version vectors so that concurrent writes are detected instead of silently overwritten.
  4. Let the application (or a CRDT) merge siblings.
  5. Repair with read repair, anti-entropy and hinted handoff.

The result is a system that stays writable even when nodes fail, at the cost of eventual consistency (see consistency models) and of conflict handling that you must design on purpose.

Multi-leader setups are notorious for subtle bugs: auto-increment keys that collide, constraints that hold on each leader but not globally, triggers that fire twice. If you can get away with a single leader per record, do.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can write conflicts happen in multi-leader replication but not in single-leader replication?

    With a single leader, all writes are ordered at that node. With several leaders, concurrent writes to the same record can be accepted independently.
  2. 2. What is the main danger of last-write-wins?

    LWW does converge, which is its strength. The weakness is that a concurrent update is lost, and with skewed clocks the 'latest' write may not really be latest.
  3. 3. What does anti-entropy do in a leaderless system?

    Anti-entropy is a background repair process, often using Merkle trees to find differing key ranges cheaply.
  4. 4. Two users add different items to the same cart concurrently. Which resolution keeps both items?

    A merge rule combines both changes. LWW, rejection and node-ID tie-breaks all keep only one of them.

Summary

  • Multi-leader and leaderless replication improve write availability and latency but allow concurrent writes to the same data.
  • Conflicts can be avoided (route a record to one leader), resolved by LWW (simple, lossy) or merged (keeps all information, needs a merge rule).
  • Whatever the rule, it must be deterministic so that every replica converges.
  • Leaderless systems repair stale replicas with read repair and background anti-entropy (often with Merkle trees).
  • Dynamo-style stores combine consistent hashing, quorums, version vectors and merge logic.

Next: CRDTs: Conflict-Free Replicated Data Types, data types whose merge rules always converge.