Quorum reads and writes

A key-value store copies each key to N replicas. A write succeeds once W of them acknowledge. A read returns once R of them respond. You choose N, R and W, and that choice sets the trade-off between freshness, latency and availability.

The big idea

Think of a committee of N members. A decision needs W signatures. To check the latest decision, you must ask R members. If R + W is more than N, your group of askers must include at least one member who signed. That member has the latest decision.

This overlap is a pigeonhole argument. The picture breaks down when a write did not reach W replicas, or when two writers race each other.

Walking through it

With N = 3, these settings are common.

The overlap check is simple arithmetic.

W = 2, R = 2:  2 + 2 = 4 > 3   reads overlap every write
W = 1, R = 1:  1 + 1 = 2 <= 3  a read can miss the write entirely

Here is N = 3, W = 2, R = 2 in practice. A put goes to replicas A, B and C. A and B acknowledge, and the write returns. A later get asks two replicas. It hears B's new value and C's old value. The versions disagree, so the system repairs C.

Latency is set by the slowest replica you wait for. That is why R = N on a large cluster hurts reads.

Common mistakes

• Treating R + W > N as linearizable. Racing writers and sloppy quorums can still show stale values. See consistency.
• Using W = 1 for important data. If that one node crashes before it copies the write, the data is gone.
• Setting R = N on a large cluster. The read waits for the slowest node every time.

Check yourself

1. With N = 5 and W = 3, what is the smallest R that guarantees overlap? 3. Since R + W must exceed 5, R must be at least 3.
2. Why is R = N costly? The read waits for the slowest of all replicas, so one slow node slows every read.

Key takeaways

• N copies, W acknowledgements for writes, R responses for reads.
• R + W > N makes every read overlap every successful write.
• The overlap is a guarantee of freshness, not a proof of linearizability.
• Latency follows the slowest replica you wait for.

Further learning

Next, see what happens when the replicas you want are down, in sloppy quorums and hinted handoff.

For the same overlap idea applied to consensus, see majority quorums.