Replication & Quorums
22 min
A replicated system doesn't have to write to (or read from) every
single replica to stay correct — it just needs enough OVERLAP between
who received a write and who's consulted on a read. This is the
quorum model: a write succeeds once w replicas acknowledge it, a
read succeeds once r replicas respond. The classic guarantee —
w + r > n — comes straight from the pigeonhole principle: if those two
groups are drawn from the same n replicas and their sizes sum to more
than n, they MUST share at least one replica in common.
def has_strong_consistency(w, r, n):
return w + r > n
w=r=1 with n=3 (has_strong_consistency returns False) is exactly how an eventually-consistent system like DynamoDB can be CONFIGURED to behave -- fast, cheap reads/writes, but no guarantee a read sees the latest write. The SAME replicas, with w=2, r=2, become strongly consistent -- consistency here is a tunable knob, not a fixed property of the system.
When a read quorum's r replicas don't all agree (because a write is
still propagating), the client needs a way to pick the "right" answer.
The simplest rule is last-write-wins: attach a timestamp to every
write, and on a read, take whichever contacted replica has the highest
timestamp.
Write `has_strong_consistency(w, r, n)`: given a replicated system with `n` total replicas, a write quorum of `w`, and a read quorum of `r`, return whether the system guarantees strong consistency (every read sees the latest write) — true exactly when `w + r > n`.
Write `read_latest(contacted_replicas)`: `contacted_replicas` is a list of `(value, timestamp)` pairs from the replicas actually contacted during a read. Return the `value` with the highest `timestamp` (a 'read repair' style latest-write-wins resolution).
Why does `w + r > n` guarantee that a read quorum always overlaps with the most recent write quorum?
You can reason about quorum-based consistency guarantees via the pigeonhole overlap argument, and resolve conflicting replica reads with last-write-wins.