Leaderless Replication (Dynamo-Style)

Any replica takes reads and writes, and quorums decide success. How W + R > N works, how stale replicas catch up, how concurrent writes are handled, and where quorums fall short.

Overview

In leaderless replication there is no leader to order writes. A write is sent to several replicas at once, and it succeeds when enough of them confirm. A read also asks several replicas and takes the newest answer. Amazon's Dynamo paper (2007) described this design, and Apache Cassandra follows the same model.

Without a leader there is no failover: when a replica is down, the others keep answering. The price is that replicas can disagree for a while, and the system needs extra machinery to find the newest value and to repair the copies that fell behind.

Quorums: W + R > N

Each key is stored on N replicas. A write succeeds when W of them confirm it. A read asks the replicas and waits for R answers. If W + R > N, every read set shares at least one replica with every write set, so at least one of the answers comes from a replica that has the latest successful write. The reader uses version numbers or timestamps to pick it.

The Dynamo paper reports (N, R, W) = (3, 2, 2) as a common setting. The latency of an operation is set by the slowest of the W or R replicas it waits for, which is why W and R are usually below N. You can check the overlap rule by brute force.

3, 2, 2 — 1 replica down — 1 replica down — A balanced default
3, 3, 1 — 0 down — 2 down — Read-heavy data, rare writes
3, 1, 3 — 2 down — 0 down — Write availability first
3, 1, 1 — 2 down — 2 down — Speed; reads may be stale (no overlap)

Catching up replicas that missed writes

A replica that was down or slow misses writes. Three mechanisms bring it back in line.

Read repair — During a read that sees different versions — Keys that are read; the stale replica gets the newest value
Anti-entropy repair — In the background, or when an operator runs it — Every key, including ones never read
Hinted handoff — When the missed replica comes back — Writes that another node held for it

Anti-entropy has to compare large data sets cheaply. Dynamo and Cassandra use Merkle trees: a tree of hashes where each parent hashes its children. Two replicas compare the root hashes first and walk down only the branches that differ, so they transfer only the keys that are out of sync.

Sloppy quorums and hinted handoff

If some of a key's N home replicas are unreachable, a strict quorum would refuse the write. Dynamo instead uses a sloppy quorum: it writes to the first N healthy nodes it can reach, even if some are not the key's home. A node that stands in keeps the write with a hint naming the intended replica, and hands it over when that replica recovers.

This keeps writes available but weakens the quorum promise: the W nodes that took the write may not overlap with the R home nodes a read asks. Cassandra's quorums stay strict: a stored hint does not count toward the consistency level, except at the special write level ANY. Cassandra keeps hints for a node that has been down up to max_hint_window (3 hours by default). A node down longer stays out of sync until read repair or anti-entropy repair reaches it.

Concurrent writes

Two clients can write the same key at nearly the same time, and replicas may receive the writes in different orders. The replicas must still end up equal.

Last write wins — Highest timestamp wins — Cassandra, per column — Concurrent writes are silently dropped; depends on clocks
Version vectors (vector clocks) — Keep both if neither version saw the other — Dynamo — Clients must merge siblings

Dynamo attaches a vector clock, a list of (node, counter) pairs, to each version. If one clock is at least as large as the other in every entry, the larger version replaces the smaller. If each is ahead somewhere, the writes were concurrent, and both versions are kept for the client to merge. Cassandra does not use vector clocks: it timestamps every write, including deletes, and keeps the newest value for each column.

Where quorums fall short

W + R > N makes stale reads unlikely, not impossible. Leaderless quorums do not give linearizability, the guarantee that every read sees the latest completed write as if there were one copy.

Sloppy quorum — The write landed on stand-in nodes outside the read set
Concurrent writes with last write wins — The losing write disappears, even though it succeeded
Read during a write — The write has reached some replicas, so reads may return the old or the new value
Write failed on most replicas — Replicas that did apply it are not rolled back
Replica restored from an old copy — The number of replicas holding the new value falls below W

What you will be able to do

Explain why W + R > N makes reads and writes overlap, and choose N, W and R for a workload.
Compare read repair, anti-entropy with Merkle trees, and hinted handoff.
Explain sloppy quorums and what they give up.
Tell last write wins from version vectors when writes are concurrent.
List the cases where a quorum read is still stale.

Key concepts

N, W, R: N replicas per key; a write needs W confirmations, a read needs R answers.
Quorum overlap: With W + R > N, every read set shares at least one replica with every successful write set.
Read repair: A read that sees an older version on some replica writes the newest value back to it.
Anti-entropy repair: A background process that compares replicas, usually with Merkle trees, and copies over missing data.
Merkle tree: A tree of hashes. Comparing roots, then only the differing branches, finds out-of-sync keys cheaply.
Sloppy quorum: Writing to the first N reachable nodes even if some are not the key's home replicas. More available, less consistent.
Hinted handoff: A stand-in node keeps a write with a hint and delivers it to the home replica when it returns.
Vector clock: A list of (node, counter) pairs on each version; it shows whether one version supersedes another or they are concurrent.
Last write wins: Resolve concurrent writes by keeping the highest timestamp. Cassandra does this per column.

When to use it

Explaining how Cassandra or a Dynamo-style store reads and writes.
Choosing consistency levels (ONE, QUORUM, LOCAL_QUORUM, ALL) for a workload.
Designing for writes that must keep working while nodes fail, without a failover step.
Discussing why quorums alone do not give strong consistency.

Interview questions

In Cassandra, what is the difference between consistency levels ONE, QUORUM, and ALL?
Why does W + R > N not guarantee strong consistency?
How do replicas that missed writes catch up?
Two clients write the same key at the same moment. What happens?
How would you choose N, W and R for a service?