When R + W ≤ N the read set may be drawn entirely from nodes the write never reached, and the probability of that is a ratio of combinations: C(N − W, R)/C(N, R). At N = 3 with R = W = 1 it is exactly 2/3 — two reads in three see the old value. And R + W = N, which reads like the boundary of the guarantee, is 1/3 at three nodes: one read in three, for a system that has paid for three replicas.
Core ideas
A counting argument, the assumption it rests on, and the reason the near-miss configuration is the worst place to stand.
The write reached W nodes and left N − W without it. The read misses exactly when all R of its nodes come from those N − W, and the number of such read sets is C(N − W, R) out of C(N, R) in total. Every quantity in that ratio is a combination, so the probability is an exact fraction rather than an estimate.
The formula counts read sets as equally likely, which is what a coordinator picking R nodes at random does. A coordinator that always prefers the same nodes — the nearest, the least loaded, the first in a list — has a miss probability that is not this number and may be 0 or 1 depending on where the write landed. The formula is the random-placement case, and real systems are often less random than that.
It is one short of a guarantee and it is paying the full price of N replicas. At N = 3 it misses one read in three; at N = 5 it misses one in ten. It never misses zero, and the single node that would fix it — one more in R or in W — is nearly always cheaper than the incident it prevents.
The material
Where the ratio of combinations comes from, what it says at three nodes and at five, and what a miss does and does not mean.
A configuration with R + W ≤ N is a sloppy quorum: it has no overlap guarantee. If the read's R nodes are drawn uniformly from the N, the probability that the read set contains no node the write reached — the miss probability — is C(N − W, R) / C(N, R).
The counting is direct. There are C(N, R) possible read sets. A read set misses precisely when it avoids all W nodes the write reached, which means choosing all R of its members from the remaining N − W, and there are C(N − W, R) ways to do that.
That last remark is worth keeping: the overlap theorem and this formula are the same statement. When R + W > N there are no read sets that miss, so the numerator is zero; when R + W ≤ N there are some, and the formula says how many.
Two patterns come out of the table. The R + W = N rows are never zero and they get better as N grows — one third at three nodes, one tenth at five — which is why the configuration survives in production long enough to be believed in. And the step from the last sloppy row to the first overlapping one is always one node, on either path.
The fastest possible configuration on three replicas: write to one node, read from one node. Both operations wait for a single machine, so both are as quick as the medium allows, and two reads in three that immediately follow a write return the old value. Note what this is not: the write is not lost. It is on a node, background repair will spread it, and a read a second later will very likely find it. The 2/3 is the probability at the moment before that happens — the same moment that “Replication Lag and Stale Reads” priced from the other direction.
So a sloppy quorum is a bet that reads rarely follow writes closely. That bet is sometimes right — an analytics store, a feed nobody re-reads immediately — and it is catastrophic for anything a user writes and then looks at. The number that decides it is this one, multiplied by how often your reads really do chase your writes.
Interactive
C(N − W, R) ÷ C(N, R), and why R + W = N buys nothing
Method
Three of the four steps are arithmetic. The fourth is the one that decides whether the arithmetic applies to your system at all.
If R + W > N the miss probability is zero and the question is the overlap question instead. The formula returns zero in that case too, because C(N − W, R) is C of a number below R.
Keep them as exact integers. These are small numbers and there is no reason to let a decimal in: C(2,1)/C(3,1) is 2/3, not 0.67, and the exact form is what makes the comparison with the neighbouring configuration obvious.
Raise R by one, then W by one, and compute both. One of them usually costs less than the other on your workload, and one of them is usually enough to reach R + W > N.
If reads are routed by locality, by load or by a fixed preference list, the read set is not uniform and this probability is the wrong one. It may be better — a coordinator that reads and writes the same preferred node never misses — or much worse, and either way the formula is describing a system you have not got.
A key-value store is configured for speed: three replicas, write acknowledged by one, read served by one. Users report that a value they just saved sometimes comes back as it was. The question is how often “sometimes” is, and what the cheapest fix costs.
The first repair halves the problem and does not solve it, which is exactly the trap: it will look like a fix in a test that issues ten reads, and it leaves a third of them wrong. R + W = N is not a weaker version of the guarantee, it is the absence of one with better odds.
The second repair costs the write an order statistic — the second fastest of three rather than the first — and that was priced at 8 ms at the p99 on the distribution this course has been using. Eight milliseconds on the write path to remove two thirds of a correctness problem is not a close call.
For a faded rehearsal, the same store is moved to five replicas and somebody proposes R = 2, W = 2 as a compromise. The supplied first move is C(3,2) = 3 and C(5,2) = 10. Compute the miss probability, then find every configuration on five nodes with R + W = 6 and say which of them you would choose for a workload whose reads outnumber its writes nine to one.
You should be able to compute C(N − W, R)/C(N, R) as an exact fraction, state it for the common small configurations without looking them up, name the cheapest change that reaches R + W > N, distinguish a miss from a lost write, and check the uniform-draw assumption against your own coordinator.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.