Quorums
Reading and writing enough copies that the two always overlap.
01The intuition
The problem it solves
A notice is kept in three copies, one in each of three classrooms, so that if one room is locked the notice can still be read. The head teacher updates it. If she updates only one copy and a student reads another, the student gets the old notice. If she must update all three before anyone may read, a locked room blocks every update. Three copies were meant to make things more available, and now any one room can stop the whole thing.
A replicated key-value store has the same choice. With N = 3 copies of each key, how many must a write reach before it is acknowledged, and how many must a read consult before it answers? Writing to all and reading from one is fast to read but fragile to write; writing to one and reading from all is the reverse. A quorum is the rule that picks the two numbers so that a read always meets at least one copy that has the latest write, without needing every copy to be alive.
Build it one piece at a time
Step 1: name the numbers. N copies, a write succeeds when W copies acknowledge, a read asks R copies and takes the newest answer it gets. Each stored value carries a version number so "newest" is well defined.
Step 2: make them overlap. Choose W + R > N. With N = 3, W = 2 and R = 2: any two copies that acknowledged a write and any two copies a reader asks share at least one copy, and that copy holds the write.
| Step | Copy 1 | Copy 2 | Copy 3 | Result |
|---|---|---|---|---|
| write v2, W = 2 | v2 | v2 | v1 (slow, not waited for) | acknowledged after copies 1 and 2 |
| read, R = 2, asks copies 2 and 3 | — | v2 | v1 | returns the newest: v2 |
| read, asks copies 1 and 3 | v2 | — | v1 | v2 again; every pair contains a v2 |
Step 3: tune for the workload. Reads outnumber writes a hundred to one in most products, so pick W = 3, R = 1: writes wait for all copies, reads ask one. Or W = 1, R = 3 for a write-heavy log where reads are rare. The overlap rule is the only constraint.
Step 4: repair the stragglers. Copy 3 is still at v1. When a read notices copies disagree, it writes the newest version back to the stale copy: read repair. In the background, copies also compare summaries of their data (Merkle trees) and exchange what differs: anti-entropy. Over time all copies converge even without reads.
Step 5: handle a dead copy on write. If copy 3 is down and W = 2, writes still succeed. If two are down and W = 2, writes fail. A sloppy quorum lets a different, healthy machine take the write temporarily and hand it to copy 3 when it returns: a hinted handoff. It keeps writes available at the cost of weakening the overlap guarantee until the hint is delivered.
Why it works, with the numbers
The overlap is pigeonhole counting:
W + R > N means the write set and the read set together exceed N, so they share at least one copy
Availability: with N = 3 and W = R = 2, the store survives any one copy being down for both reads and writes; with N = 5 and quorums of 3, any two. Latency: a write waits for the second-fastest copy, not the slowest, which trims tail latency. The guarantee is that a read sees a value at least as new as the latest acknowledged write, provided the version numbers are comparable; concurrent writes to different copies produce sibling versions that need the vector-clock treatment. The failure modes: sloppy quorums serving stale data while hints are pending, writes that reached only one copy before failing and later "resurrect", and clocks used as version numbers.
The trade-off you must say out loud
Consistency against latency and availability, set by two integers. Say your N, W, R and why, what a client sees during a partition, and how stale copies are repaired. Say that a quorum does not give you transactions or a single leader, only a read-your-latest-write promise per key. The follow-up is "why not just use a leader", and the answer is that a leaderless quorum stays writable through a leader's worth of failures and across regions, at the price of version conflicts the application must resolve.
Where it shows up in the 100 Google problems
- Distributed key-value store: N = 3, W = R = 2 with read repair and hinted handoff is the standard Dynamo-style deep dive.
- Object storage: a write is acknowledged when enough replicas or erasure fragments are durable, the same counting in a different form.
- User preferences across products: a settings store that must read the latest write per key in every region uses a quorum per region.