Leaderless quorums

Leaderless replication has no single node in charge of ordering writes. Amazon's 2007 Dynamo paper popularized the design, and Cassandra, ScyllaDB and Riak use variants of it. The client, or a coordinator acting for it, sends each write to all N replicas that own the key. The write counts as successful once W of them acknowledge. A read asks replicas and waits for R answers, then keeps the newest version.

The big idea

If W + R > N, every set of W writes must overlap every set of R reads in at least one replica. So a read sees at least one copy of the latest successful write. That overlap is the whole guarantee.

N = 3, W = 2, R = 2
W + R = 4 > 3  → every read overlaps every successful write on at least one replica
Tolerates 1 unavailable replica for both reads and writes

N = 5, W = 3, R = 3
W + R = 6 > 5  → tolerates 2 unavailable replicas

The values of W and R set a trade-off. N = 3, W = 1, R = 3 makes writes fast but reads wait for every replica. N = 3, W = 3, R = 1 makes reads fast but fails writes when any replica is down.

Cassandra exposes this as per-query consistency levels: ONE, QUORUM (a majority of N), LOCAL_QUORUM (a majority within the local data center, a common choice for multi-region clusters) and ALL.

Walking through it

Quorums are not linearizable. Three things can break the "always fresh" feeling:

• Two concurrent writes can land on different subsets of replicas.
• A write that fails, with fewer than W acknowledgements, may still have reached some replicas. Later reads can see it.
• With last-write-wins, clock skew can make an older write win.

Treat W + R > N as "usually fresh", not "always correct".

Sloppy quorums and hinted handoff. Suppose two of a key's three home replicas are unreachable. A strict quorum with W = 2 fails. A sloppy quorum accepts the write on any reachable nodes, including ones that do not normally own the key. Each stand-in stores the write with a hint naming the real owner. When the owner recovers, the hint is delivered. This is hinted handoff. Cassandra keeps hints for 3 hours by default. A node down longer than that needs a full repair. Sloppy quorums raise write availability, but they weaken freshness, because a read quorum may no longer overlap the write.

Repair. Replicas drift through missed writes and expired hints. Two mechanisms bring them back.

• Read repair. When a read finds replicas that disagree, the coordinator writes the newest value back to the stale ones. It is cheap, but it fixes only keys that get read.
• Anti-entropy with Merkle trees. A background process compares replicas. Each leaf is a hash of a range of keys, and each parent is a hash of its children. Two replicas compare root hashes. If they match, the whole range is identical. If not, they descend only into the subtrees that differ. In a tree with 2^15 leaves, finding one differing range takes about 15 comparisons down one path, not a scan of every key.

Common mistakes

• Treating W + R > N as linearizable. It gives overlap, not a total order.
• Ignoring repair. Replicas drift apart without it, and reads return stale data.
• Forgetting that sloppy quorums weaken freshness. Write availability goes up, and read guarantees go down.

Check yourself

1. With N = 5, W = 3 and R = 3, how many replicas can be down while reads still succeed?

   Answer: 2. Three reachable replicas are enough for a read quorum.

2. What does hinted handoff do?

   Answer: a stand-in node stores the write along with a note naming its real owner, and delivers the write when the owner returns.

Key takeaways

• A leaderless store accepts writes on W of N replicas and reads from R, so W + R > N gives overlap.
• Quorums give tunable availability and freshness, but they are not linearizable.
• Sloppy quorums and hinted handoff raise write availability, at the cost of freshness.
• Read repair and Merkle-tree anti-entropy keep replicas in agreement.

Further learning

The Dynamo paper is the original design. Read it for the reasoning behind the trade-offs:

Kleppmann's follow-up lecture explains why W + R > N works and where it falls short:

Return to the replication overview for the full map.