Leaderless Replication

Single-leader and multi-leader replication both treat write coordination as a routing problem: direct writes to a designated node, then propagate them to followers. Leaderless replication takes a different approach. Every replica can accept writes. There is no leader, no designated primary, no routing. The client writes directly to multiple replicas in parallel.

Amazon introduced this model in their 2007 Dynamo paper. Riak, Cassandra, and Voldemort all implement variants of it. The tradeoff is the same as multi-leader but taken further: without a single write authority, the database must have a principled way to handle stale reads and conflicting values.

---

Writing When a Node Is Down

In a leader-based system, a node failure is a crisis — if the leader goes down, writes block until a new leader is promoted. In a leaderless system, a node failure is a non-event. The client sends the write to all replicas in parallel. If one is down, the others still acknowledge. The write succeeds, and there is no failover because there was nothing to fail over.

The cost of that simplicity is deferred, not avoided. The node that missed the write comes back holding an old value, and it will happily serve that value to the next client that reads from it. Nothing in the write path corrected it, so something else has to.

---

Catching Up: Read Repair and Anti-Entropy

A replica that missed writes needs to catch up eventually. Dynamo-style databases use two mechanisms, and the difference between them matters more than it first appears.

Read repair. The client reads from several replicas in parallel. If the responses disagree — one returns version 7, another version 6 — the client takes the newer value and writes it back to the stale replica on the spot.

Read repair: client detects stale replica and writes back

▶ Run

This works well for frequently read data and does nothing at all for the rest. Repair only happens where a read happens, so a key nobody reads can stay stale indefinitely.

Anti-entropy. A background process on each node compares its data against other replicas and copies over whatever is missing or outdated.

Anti-entropy: background sync finds and fixes stale replicas

▶ Run

Unlike the replication log in leader-based systems, anti-entropy copies data in no particular order and with no timing guarantee — a value might take seconds or minutes to propagate, depending on when the job next runs.

Not every system ships both. Voldemort, for instance, has no anti-entropy process, which means read repair is the only mechanism it has — and therefore that rarely-read values are not merely stale but potentially ancient. That is a durability question as much as a consistency one: a value that exists on fewer replicas than you think is a value you are closer to losing.

---

Quorums for Reading and Writing

If a write is acknowledged by two of three replicas, at most one replica is stale. Read from two, and at least one of them must be current. That is the whole idea, and generalising it gives the condition the rest of this model rests on.

With n replicas, a write must be acknowledged by w of them and a read must query r of them. So long as

w + r > n

the read set and the write set cannot be disjoint. They share at least one node, and that node has the latest write.

Leaderless quorum: write, read, and repair

▶ Run

In Dynamo-style databases n, w and r are configurable. n is typically an odd number — 3 or 5 — with w and r both set to a majority. But they are separate knobs on purpose, and moving them independently biases the system toward reads or writes without giving up the overlap:

n	w	r	w + r > n	Tolerates	Biased toward
3	2	2	✓ (4 > 3)	1 node down	balanced
3	3	1	✓ (4 > 3)	0 nodes on write	fast reads
3	1	3	✓ (4 > 3)	0 nodes on read	fast writes
3	1	1	✗ (2 < 3)	2 nodes down	speed over freshness

Reads and writes are always sent to all n replicas regardless; w and r only control how many responses you wait for before calling the operation done. If fewer than w or r nodes respond successfully, the operation returns an error.

In Cassandra these are per-query consistency levels rather than a fixed cluster setting, so one application can pick a different point on the curve per statement:

-- Session default: overlapping read and write quorums (w + r > n).
CONSISTENCY QUORUM;
INSERT INTO orders (id, total) VALUES (7, 42.00);

-- A dashboard that would rather be fast than current opts out per read.
CONSISTENCY ONE;
SELECT total FROM orders WHERE id = 7;

The last row of the table is that CONSISTENCY ONE case — perfectly valid, and explicitly giving up the guarantee rather than misunderstanding it.

Which raises the obvious question: how much is that guarantee actually worth when you keep it? Rather less than the arithmetic suggests, and the next post is about the gap.

---

Key Takeaways

• Leaderless replication (Dynamo-style) sends every write to all n replicas in parallel and treats it as successful once w acknowledge. There is no leader, so there is no failover.
• A node that missed writes is corrected after the fact, not during the write — which is why repair mechanisms are part of the model rather than an add-on.
• Read repair fixes stale replicas inline during a read, so it only ever repairs data somebody reads. Anti-entropy sweeps in the background, in no particular order and with no timing guarantee.
• A system with read repair and no anti-entropy leaves rarely-read values stale indefinitely — a durability risk, not just a freshness one.
• The quorum condition w + r > n forces the read set and write set to overlap in at least one node.
• w and r are independent knobs: raising w favours durable writes, raising r favours fresh reads, and Cassandra exposes the choice per query.
• Reads and writes always go to all n replicas; w and r only decide how many responses you wait for.

---

References

• Martin Kleppmann, Designing Data-Intensive Applications, chapter 5 — the canonical treatment of replication this series works through.
• DeCandia et al. — Dynamo: Amazon’s Highly Available Key-value Store (SOSP 2007), the paper this model comes from.
• Apache Cassandra — Dynamo-style architecture, including tunable consistency levels.