Quorum Reads & Writes
You'll learn to
- -State the R + W > N rule and explain why it guarantees read/write overlap
- -Reason about the availability and consistency tradeoff as R and W change
- -Implement a basic quorum check for reads and writes
Vector clocks let you detect when two writes conflict; quorum reads and writes are a strategy for making conflicts rarer in the first place, by controlling exactly how many replicas must participate in every read and every write. Level 56 asks you to implement the rule that governs that: R + W > N.
N, W, and R
Say a piece of data is replicated across N nodes. A write is considered successful once it has been acknowledged by W of those nodes, not necessarily all N - waiting for every single replica would make the system unavailable the moment any one node is slow or down. A read is considered successful once it has collected responses from R nodes and returned the most recent value among them. N, W, and R are all configurable per system, and the relationship between them determines the system's consistency guarantees.
Why R + W > N Guarantees Freshness
If R + W > N, then any set of W nodes that accepted a write and any set of R nodes consulted on a subsequent read must share at least one node in common - you cannot pick W nodes and R nodes out of a pool of N that are entirely disjoint once their sizes add up to more than N. That overlapping node is guaranteed to have seen the latest write, so a quorum read is guaranteed to observe it, once the client compares the versions returned by the R nodes and picks the newest. This is a pigeonhole argument: you cannot split N nodes into two groups of size W and R with no shared member if W + R exceeds N.
The Tradeoff: Consistency vs Availability
Raising W and R closer to N strengthens consistency guarantees but weakens availability - a write or read now needs more nodes to be up and responsive, so any given request is more likely to fail during a partial outage. Lowering W and R, for example W=1, R=1, write to any one node and read from any one node, maximizes availability at the cost of consistency, since R + W will not exceed even a small N, so reads can easily miss the latest write. This is the same tension the CAP theorem describes at a higher level; quorum's N, W, R knobs are how a real system tunes exactly where on that spectrum it wants to sit, and different data in the same system often pick different tradeoffs.
A useful sanity check for an interview: with N=3, W=2, R=2 (a very common default in Cassandra/DynamoDB-style stores), R+W=4 > N=3, so you get the freshness guarantee while tolerating one node being down for either a read or a write.
You are designing a replicated key-value store with 5 replicas. How would you choose write and read quorum sizes to guarantee a read always sees the latest write, while tolerating some node failures?
"I'd write to all 5 and read from all 5 to be safe."
"Writing and reading from all N nodes maximizes consistency but means any single node failure blocks every operation - zero fault tolerance. Instead I'd pick W and R such that W + R exceeds N, for example W=3, R=3 with N=5: any write quorum and any read quorum are guaranteed to share at least one node, so a read always observes the most recent acknowledged write, while still tolerating up to two node failures on either path since I only need 3 out of 5, not all 5."
What does the R + W > N rule guarantee?
Level 56: Quorum Reads & Writes has you implement the W-acknowledgment and R-response logic and enforce R + W > N - the rule that lets a replicated store balance consistency against availability instead of choosing an all-or-nothing extreme.