Read/Write Quorums

## The two numbers A quorum system sits underneath most 'eventually consistent but tunable' replicated stores — Dynamo, Cassandra, Riak, and their descendants. Each logical record is copied onto N physical replicas (nodes). Instead of requiring every replica to participate in every operation, the system defines two smaller numbers: - **W, the write quorum.** A write is considered successful once W replicas have durably stored the new value and acknowledged it back to the coordinator; the client doesn't wait for the remaining N-W replicas, which receive the update asynchronously (or via background repair). - **R, the read quorum.** A read queries R replicas, collects their versions of the value, and — because different replicas can be at different points in their update history — reconciles the responses by picking whichever version is 'newest' according to some ordering mechanism: - a monotonically increasing version counter - a wall-clock timestamp (risky under clock skew) - a vector clock that can detect true concurrency versus a simple ordering ## Why the overlap is guaranteed The reason R + W > N matters is a direct application of the **pigeonhole principle**. Imagine the N replicas as N boxes: 1. A write touches W of them; a read touches R of them. 2. If R + W > N, then the two groups cannot be chosen disjointly — there literally aren't enough boxes left to keep them apart — so at least one replica must appear in both the write group and the read group. 3. That shared replica received the newest write (it was one of the W that acknowledged it) and it is also one of the R replicas the read consults, so its version is present among the values the read collects. 4. As long as the client correctly identifies 'newest' among what it received, it will surface that value. This is why R + W > N is often phrased as 'the read quorum and write quorum must overlap.' ## Why not full replication Why build systems this way instead of just replicating synchronously to every node (N-of-N) or accepting a single writer? - **Full replication (W = N)** gives strong consistency but means a single slow or down node stalls every write — poor availability and poor tail latency. - **A single copy (N=1)** is fast and simple but has no fault tolerance at all. Quorums let an operator dial in a position between those extremes: N is chosen for durability and fault tolerance (how many node failures you can absorb before losing data), while R and W are chosen per-operation-type to trade off latency, throughput, and consistency strength independently of N. A write only needs a majority-ish subset to succeed, so one lagging or crashed replica doesn't block the whole system, and a read likewise only needs enough replicas to guarantee it sees the newest data, not all of them. ## The trade-off in the numbers The trade-off is visible in the numbers themselves. - **Larger R or W** means more replicas have to respond before the client gets an answer, which raises latency (bounded by the slowest of the R or W replicas contacted, so tail latency worsens as the quorum size grows) and lowers availability (more replicas must be reachable, so the system tolerates fewer simultaneous failures before an operation can't be completed at all). - **Smaller R or W** is faster and more available but weakens the consistency guarantee — if R + W <= N, quorums can be chosen so they never overlap, and a read can return stale data even though a newer write already succeeded elsewhere. A very common balanced choice is **N=3 with R=W=2** (used as the default 'QUORUM' consistency level in systems like Cassandra), which tolerates one replica being down for either reads or writes while still guaranteeing R+W(=4) > N(=3). ## Failure modes at the edges Failure modes show up at the edges. If a network partition or node crash drops the number of reachable replicas below R (for a read) or below W (for a write), a strict-quorum implementation simply fails that operation — it will not proceed with fewer acks than the configured quorum, because doing so would break the overlap guarantee. That is a deliberate **CAP-theorem trade**: quorum systems configured with R+W>N lean toward consistency over availability during a partition. Some systems relax this with **'sloppy quorums'** that write to whatever healthy replicas are reachable and reconcile later — trading the R+W>N guarantee for higher availability. A concrete example: Amazon's Dynamo paper (2007) popularized N=3, R=2, W=2 for a shopping-cart-style key-value store, explicitly choosing that balance so a single node failure never blocks reads or writes, while still making stale reads rare in the common case.