Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 27

Quorum Reads and Writes

How leaderless databases like Cassandra and DynamoDB stay consistent without a leader: N replicas, W write acks, R read responses, why R + W > N means a read always overlaps the latest write, tuning for reads or writes, read repair, hinted handoff and the edge cases quorums do not cover.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 12

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

Leaderless

In leaderless replication, each key lives on N replicas, here three. A write is sent to all three in parallel, by the client or a coordinator node. There's no leader to fail over, which is the appeal. But some of those writes will be slow or fail. When is the write 'done'?

Leaderless replication
  • no leader, no failover
  • each key lives on N replicas
  • (here N = 3)
  • the client (or a coordinator)
  • sends the write to all N
  • in parallel
  • Dynamo, Cassandra, Riak

W

W is how many replicas must confirm before the write counts. With N three and W two, A and B say ok, and the client reports success even though C was down and still has the old value. W of one is fast but fragile; W equal to N is safest, but one dead replica blocks every write.

Write quorum W
  • wait for W acknowledgements
  • then tell the user "saved"
  • N = 3, W = 2:
  • A ok, B ok → success
  • C was down, still missing v2
  • W = 1: fast, fragile
  • W = N: safe, any failure blocks

R

R is how many replicas a read asks. With R two, the read happens to reach B and C. B has version two, C still has version one. Each value carries a version, so the client returns the newest, version two. The stale replica was outvoted.

Read quorum R
  • ask R replicas, take the
  • value with the newest version
  • N = 3, R = 2:
  • B says v2, C says v1
  • → return v2
  • versions: timestamps or
  • vector clocks (episode 32)

The overlap

Here's the whole trick. If R plus W is greater than N, any set of R replicas must share at least one member with any set of W replicas. Two plus two is four, more than three, so the read set always includes someone who saw the latest write. That one up-to-date replica is enough, because the newest version wins.

Why R + W > N works
N = 3   W = 2   R = 2

write set:  {A, B}
read set:   {B, C}
overlap:    {B}  ← has v2

R + W > N  ⇒  any read set
shares at least one replica
with the last write set

Tuning

Now you can tune. Two and two is the balanced default. Read-heavy? W three, R one: reads hit a single node, writes need everyone. Write-heavy? W one, R three. Or W one, R one: fastest, but no overlap, so you're back to eventual consistency. Cassandra lets you choose per query with levels like ONE, QUORUM and ALL.

Tuning N, W, R
  • N=3 W=2 R=2 balanced (common)
  • N=3 W=3 R=1 fast reads,
  • writes need all
  • N=3 W=1 R=3 fast writes,
  • reads ask all
  • N=3 W=1 R=1 fastest, no overlap
  • = eventual
  • Cassandra: QUORUM, ONE, ALL
  • per query

Read repair

What about C, still holding version one? Two repair mechanisms. Read repair: the read that noticed C was stale writes version two back to it. And anti-entropy: a background process compares replicas using hash trees and copies over any differences. Together, stale copies don't live forever.

Keeping replicas in sync
  • read repair: a read that sees
  • a stale replica writes the
  • newest value back to it
  • anti-entropy: background job
  • compares replicas (Merkle
  • trees) and copies differences
  • stale data does not live forever

Hinted handoff

When replicas are down, some systems use a sloppy quorum: another node temporarily stores the write for C with a hint, and hands it off when C comes back. That keeps writes available during outages. The catch: the W nodes that acknowledged may not be the key's usual replicas, so the overlap guarantee quietly disappears.

Sloppy quorum
  • C is down; to keep accepting
  • writes, another node stores
  • C’s copy with a "hint"
  • when C returns, the hint is
  • handed off to it
  • great availability, but W
  • nodes may not be the "home"
  • N, so overlap is not guaranteed

The limits

Be careful in interviews: quorums alone are not strong consistency. Two clients writing the same key at once can still conflict, and last-write-wins silently drops one. A write that failed on some replicas can still be read from others. Sloppy quorums break the overlap. And timestamp versions break when clocks drift.

What quorums do NOT give you
  • • concurrent writes to the same
  • key still conflict (last-write-
  • wins can drop one)
  • • a write that failed on some
  • replicas may still be read
  • • sloppy quorums break overlap
  • • clock skew breaks timestamps
  • ≠ linearizable by itself

Decision

Use quorum-based stores when you have heavy writes, several regions and don't want a single leader as a bottleneck: Cassandra, DynamoDB, Scylla. Tune per query: quorum for user-facing reads, one for analytics events. But if you need uniqueness or locks, you need consensus, which is episode thirty-one.

When to use quorums
  • high write volume, many
  • regions, no single leader
  • bottleneck: Cassandra,
  • DynamoDB, ScyllaDB, Riak
  • tunable per query:
  • QUORUM for profile reads,
  • ONE for analytics events
  • need uniqueness or locks?
  • → consensus (episode 31)

Say it like this

The interview answer. Each key on N replicas; writes wait for W acks, reads ask R replicas; with R plus W greater than N, a read always overlaps the latest write and the newest version wins. Stale copies heal through read repair, anti-entropy and hinted handoff. Then name the limits: concurrent conflicts and clock skew.

In the interview
  • "How do you keep replicas
  • consistent without a leader?"
  • N replicas, write to W,
  • read from R, R + W > N
  • → overlap, newest version wins
  • repair: read repair,
  • anti-entropy, hinted handoff
  • limits: conflicts, clocks

Interview questions

What do N, W and R mean?

N is the number of replicas that store each key, W is how many must acknowledge a write before it is considered successful, and R is how many replicas a read queries before returning.

Why does R + W > N give up-to-date reads?

Any set of R replicas and any set of W replicas must then share at least one replica, so every read reaches at least one node that has the latest successful write; returning the value with the newest version gives the latest data.

How would you tune N, W, R for a read-heavy workload?

Keep N = 3 and use W = 3, R = 1 so reads hit a single replica, accepting that every write needs all replicas; or keep W = 2, R = 2 for a balanced default that tolerates one failure on both paths.

What is read repair?

When a read sees replicas returning different versions, it writes the newest version back to the stale replicas, so frequently read data converges quickly.

What is a sloppy quorum and hinted handoff?

When some of a key’s home replicas are unreachable, the write is accepted by other nodes that store it with a hint and forward it once the home replica recovers. It improves write availability but breaks the guaranteed overlap between read and write sets.

Are quorum reads and writes linearizable?

Not by themselves. Concurrent writes can conflict and last-write-wins may drop one, partially failed writes can be observed, sloppy quorums remove the overlap, and clock skew can order timestamps wrongly.

Which databases use quorums?

Dynamo-style leaderless stores such as Amazon DynamoDB, Apache Cassandra, ScyllaDB and Riak. Cassandra exposes consistency levels like ONE, QUORUM, LOCAL_QUORUM and ALL per query.

What happens to a write with W = 2 if only one replica responds?

The write is reported as failed to the client, but the one replica that accepted it keeps the value, so later reads may or may not see it. Clients should retry idempotently.