Commentary: quorum-replication

Five replicas, tunable W and R, read-repair on the read path — Dynamo's shape. A write reaches one replica out of five and the client is told it FAILED. One read later that write is the value every possible read returns, forever. A study guide for quorum.py.

cd quorum-replication
python3 demo.py        # the aha (§6)
python3 test_quorum.py # pins every number this page claims

1. Orientation

This toy is a quorum-replicated register: five replicas, each holding one (version, value) pair per key, a coordinator that writes to as many replicas as it can reach and reports success only if at least W of them acknowledged, and a reader that asks R replicas and takes the newest answer. On the way out of every read it does read-repair: it writes the winning version back to the replicas that were behind.

There are no threads, no sockets, no wall clock and no random number generator. Which replicas a request reaches is an explicit list of ids — reach=[3], contact=[2, 3, 4] — so "the read that happened to touch the one stale replica" is a line of code rather than a lucky run.

That determinism buys the same thing the distributed-lock toy got from its schedule: the run can be audited. Cluster.told records the verdict handed to every client, and Cluster.read_sets re-derives, over every distinct R-sized set of replicas, what the cluster would answer. Putting those two side by side is the whole toy — what the system said, next to what the system is.

You will see one write reach exactly one replica out of five, be reported FAILED to its client, and then become the answer to all ten possible three-replica reads, permanently, without any client ever asking for it again.

By the end you should be able to:

• say why W + R > N does not make a failed write go away, and what it actually promises instead;
• point at the one line that makes the promotion irreversible, and the one line that performs it;
• explain why raising W makes failed-but-durable writes more common rather than less, and derive the direction of that from the code;
• say what turning read-repair off actually buys, and what it costs — both measured, not argued;
• name what it would take to make FAILED mean failed, and what that costs in round trips.

2. The problem this mechanism exists to solve

Put one copy of your data on one machine and you have a single point of failure. Put N copies on N machines and you have a new question: how many of them have to answer before you are allowed to call an operation done?

Answering "all of them" gives you consistency and no availability — one slow replica stalls every write. Answering "one of them" gives you availability and no consistency — a reader can talk to a replica that missed the last five writes. The quorum answer is to make the number a parameter: writes need W acknowledgements, reads need R responses, and if you choose them so that

then every read set and every write set must overlap in at least one replica, so a read is guaranteed to see the last successful write. That inequality is one of the genuinely beautiful results in distributed systems, it is three lines of arithmetic, and every vendor doc states it. DataStax's puts it as plainly as anyone: "Strong consistency can be guaranteed when the following condition is true: R + W > N."

Here is the competing goal that makes the design interesting, and the trap this toy is about. The overlap argument is a statement about successful writes. It says: if a write succeeded, a read will see it. It says nothing whatsoever about a write that failed, and in this protocol a failed write is not a rolled-back write. It is a write that reached some replicas and not enough of them.

There is nowhere in a quorum protocol for the undo to live. Undoing a partial write means getting agreement on the fact that it failed, and agreement is precisely the expensive thing the quorum design set out to avoid buying. So the coordinator does the only thing it can: it counts the acks, reports the bad news to the client, and leaves the partial write exactly where it landed.

Then the read path finds it. And the read path's job — repairing stale replicas so that reads stop flapping — is indistinguishable, from the replicas' point of view, from a client writing that value on purpose.

3. Background you need

4. The mental model

Five replicas, one key, one version number per copy. A write reaches the replicas in reach; a read contacts the replicas in contact.

The left-hand column is a failure. The right-hand column is a completely ordinary read, doing exactly the maintenance it was designed to do. Nothing in between them is a bug — and the value the client was told it had failed to write is now on a quorum of replicas, where it will stay.

The arithmetic that makes the second column permanent is the same overlap rule from §2, applied to the residue instead of to a successful write: three holders and a read quorum of three cannot avoid each other in a cluster of five.

5. Reading the source

5.1 Replica.put — the ratchet

def put(self, key, version, value, why):
    """THE RATCHET, and the load-bearing line in this file. A replica
    never moves to an older version, so once v2 is on a replica only v3
    displaces it: a partial write cannot be erased by writing around it,
    and read-repair is safe to run from any replica in any order.

    The `=` half of `>=` is the cheaper half -- it only makes a repeated
    put idempotent, which keeps `repaired` honest about what moved.
    Relaxing it to `>` changes that list and nothing else; see
    commentary 5.1."""
    cur = self.store.get(key)
    if cur is not None and cur[0] >= version:
        return False
    self.store[key] = (version, value)
    self.applied.append(dict(key=key, version=version, value=value, why=why))
    return True

Every replica is independent and unordered with respect to every other one, so the rule that decides which of two values wins has to be a property of the values, not of the order the messages arrived in. That is what the version comparison buys: put is commutative and idempotent, which is what lets read-repair fire from any replica, in any order, as many times as it likes, and still converge.

It also has a consequence nobody designs for. A store that never moves backwards cannot be corrected by writing around it. Once v2 is on r3, there is no v1 you can send to r3 to remove it — the only thing that displaces v2 is a v3, which is a new write by some other client, not an undo of this one.

The >= is a judgement call, so it is worth checking which half of it is load-bearing. Running the variant with > (the counterfactual lives in cf.py in the scratch directory, importing this same module):

The counts do not move. The = half only buys idempotence — with >, the repair re-applies v2 to the replica that already had it, so repaired reports three replicas instead of the two that actually changed, and the audit log grows a duplicate. The promotion is carried entirely by the > half. This is worth knowing before writing a paragraph claiming otherwise; the first draft of the docstring in this very file claimed the >= as a whole was what made the write permanent, and the counterfactual corrected it.

5.2 Cluster.write — the write with no abort path

def write(self, key, version, value, reach):
    """`reach` is the list of replica ids the request actually got to;
    every other replica is partitioned, down, or just slow, which are the
    same thing to a coordinator holding a timeout.

    Note what is missing: there is no else-branch. When the ack count
    falls short of W the client is told FAILED and the replicas in `reach`
    keep the value anyway. A quorum register has no abort path, because
    aborting would need agreement, which is the thing it declined to buy.
    """
    acked = [i for i in reach if self.rep(i).put(key, version, value, "write")]
    ok = len(acked) >= self.w
    self.told.append(dict(key=key, version=version, value=value, ok=ok,
                          acked=sorted(acked), reached=sorted(reach)))
    return dict(ok=ok, acked=sorted(acked))

The most important thing in this method is a line that is not there. ok is computed, recorded, and returned — and then nothing happens on the false branch, because there is no false branch. Every replica in reach has already applied the value by the time the count is taken; the count is a report, not a decision.

reach deserves a note too. Modelling failure as "the list of replicas the request got to" collapses partition, crash and slowness into one parameter, which is exactly the collapse a real coordinator is forced into: it is holding a timeout, and a timeout cannot distinguish a dead replica from a slow one from a healthy replica behind a broken link. Every one of those cases produces the same missing ack, and — this is the part that matters — in two of the three cases the write did land.

Note also that write takes the version from its caller. That is a simplification with teeth, and §8 owes you the real story.

5.3 Cluster.read — the read, and the repair

def read(self, key, contact):
    """`contact` is the list of replica ids that answer. The newest
    version among them wins, and then read-repair pushes that winner back
    to the contacted replicas that are behind.

    The repair is not a cache refresh. It is a *write*, issued by a reader,
    carrying a version the coordinator never decided to commit -- and it
    is the only line in this file that changes how many replicas hold a
    value without a client having asked for anything."""
    if len(contact) < self.r:
        return dict(ok=False, value=None, version=None, repaired=[])
    live = [(i, self.rep(i).get(key)) for i in contact]
    live = [(i, v) for i, v in live if v is not None]
    if not live:
        return dict(ok=True, value=None, version=None, repaired=[])
    best = max(v for _, v in live)
    repaired = []
    if self.repair:
        for i in contact:
            if self.rep(i).put(key, best[0], best[1], "read-repair"):
                repaired.append(i)
    return dict(ok=True, value=best[1], version=best[0],
                repaired=sorted(repaired))

best = max(...) is the read quorum doing its job: among the replicas that answered, the highest version is the freshest, and with W + R > N it is guaranteed to be at least as fresh as the last acknowledged write.

Then the if self.repair: block. Look at what it is: a call to the same put that a client write uses, with the same arguments shape and the same "why" slot filled in differently. The replicas cannot tell the difference, because there is no difference. Read-repair is a write issued by a reader, carrying a version that no coordinator ever decided to commit. The why field exists only so the audit log can tell you afterwards which writes came from a client and which the system did to itself.

It repairs the whole contact set rather than only the replicas it noticed were behind, and the ratchet makes that free: a put of the version a replica already holds returns False and changes nothing, so the loop is a no-op on the ones that were already current. That is the idempotence from §5.1 being spent.

5.4 Cluster.read_sets — the audit that proves permanence

def read_sets(self, key, r=None):
    """THE PERMANENCE AUDIT. Every distinct R-sized set of replicas, and
    the value a read from that set would return. Deliberately does not go
    through `read`: it must not repair, or the act of auditing would
    change the thing being audited."""
    r = self.r if r is None else r
    out = []
    for s in combinations(range(1, self.n + 1), r):
        vs = [self.rep(i).get(key) for i in s]
        vs = [v for v in vs if v is not None]
        out.append((list(s), max(vs)[1] if vs else None))
    return out

"The value is now permanent" is not a claim you can support by doing another read, because a single read only tells you what one set of replicas said. So this function enumerates all of them — all C(5, 3) = 10 three-replica subsets — and reports what each would return. When all ten agree, the value is not merely current, it is unavoidable.

The duplicated logic is deliberate. This function reimplements the "highest version wins" rule rather than calling read, because read repairs, and an audit that modifies the state it is auditing would turn 6/10 into 10/10 by the act of measuring it. test_quorum.py pins this with read_sets_does_not_mutate_the_cluster.

6. The demo, and what it proves

python3 demo.py. Five replicas, W = 3, R = 3, so W + R = 6 > 5 — the configuration every doc calls strongly consistent.

6.1 The staged run

Every number here derives.

Why FAILED at t1. The write reached one replica, so acked has length 1, and 1 >= 3 is false. The client is told the truth about the acks.

Why 6/10 at t1. Ten is C(5, 3), the number of distinct three-replica read sets. A read returns B exactly when its set contains r3, the only replica holding v2; the number of three-element sets containing a fixed element is C(4, 2) = 6. So before anyone reads, the value of this key is decided by routing: six of the ten possible reads return the write that failed, four return the write that succeeded.

Why t2 changes nothing. [1, 2, 4] is one of the four sets that miss r3. All three replicas hold v1, max picks v1, and read-repair puts v1 back onto replicas that already have v1 — which the ratchet rejects, so repaired is empty. A read that misses the residue cannot heal it and cannot erase it either.

Why t3 promotes it. [2, 3, 4] contains r3. max over {v1, v2, v1} is v2, so the client is handed 'B' — a value it, or another client, was told was not written. Then the repair loop puts v2 to all three contacted replicas; r3 already has it and is rejected, so repaired is [2, 4], and the holders become {2, 3, 4}.

Why 10/10 afterwards. Three replicas hold v2 and every read set has three replicas, out of five. 3 + 3 > 5, so no three-replica set can avoid all three holders — the same overlap arithmetic from §2, now working for the failed write instead of against it. All ten sets return B.

Why it is permanent. Because of §5.1. No read lowers a version, so no subsequent read can take v2 back off those replicas; only a v3 from a new client write displaces it. The counterfactual confirms the order does not matter either:

6.2 The same defect running backwards

Same partial write, same single replica. Set W = 1 and the identical event is reported as a success — and yet only one of the five single-replica reads returns it. The write that "succeeded" is invisible to four readers out of five.

Put §6.1 and §6.2 together and the shape of the thing is clear. ok is a function of the ack count and W. Durability is a function of which replicas hold the value. These are two different quantities, and W is the exchange rate between them, not a link. Neither report is a lie; they are answers to different questions, and only one of them is the question the client asked.

6.3 Does W + R > N prevent it?

The first fix every reader proposes. Sweep all 25 combinations:

Read this table down the columns, not across. For a fixed R, the two count columns are identical for all five values of W. W=3, R=3 satisfies the overlap rule and promotes the failed write 6/10 → 10/10; W=1, R=3 violates it and does exactly the same thing, to the digit. The W+R>N column flips from False to True in the middle of blocks of identical outcomes, five times. test_quorum.py::the_outcome_depends_on_r_alone_and_not_on_w_at_all asserts this as an invariant rather than leaving it to the eye.

The reason is structural. W appears in exactly one expression in this file — ok = len(acked) >= self.w — and ok is never read by anything except the client's report. Nothing downstream of the write branches on it. So W cannot possibly affect what the replicas hold, and the overlap rule, which is built out of W, cannot either.

The R column is where the behaviour actually lives, and it too derives. One repairing read leaves exactly R holders, because the repair writes to the whole contacted set. The promotion is unanimous when R + R > N: at R=3, 6 > 5 and all ten sets return B; at R=2, 4 < 5 and only 7 of 10 do, leaving three sets — the ones avoiding both holders — still returning the old value. At R=1 nothing spreads at all, which is §6.6.

6.4 Does turning read-repair off prevent it?

The second fix every reader proposes, and Cassandra ships it as a setting.

Turning read-repair off does not remove the failed write. It stays on r3, 6/10 read sets keep returning it, and the same client reading five times sees A B A A A — the value it was told failed, appearing and disappearing depending on which replicas answer. Read-repair does not create the problem; it converts a flapping problem into a permanent one. That is a real trade, and it is a trade in both directions: A B B B B is monotonic and wrong, A B A A A is non-monotonic and equally wrong.

This is not a toy-only artifact. Cassandra's own documentation describes its read_repair setting in exactly these terms: BLOCKING, the default, "[e]nsures monotonic quorum reads but may sacrifice write atomicity," while NONE "[p]rovides write atomicity at the partition level but not monotonic quorum reads." The sentence "may sacrifice write atomicity" is this toy's §6.1 written as a configuration note.

And switching it off only changes which mechanism does the promoting. The gossip pass above is anti-entropy — the background repair every eventually consistent store runs, and the same thing hinted handoff does when the partitioned replica comes back. One pair exchange takes it to 9/10 (holders {1, 3}, so only the set {2, 4, 5} still misses it), a second to 10/10, and by the end of the pass all five replicas hold the write that failed.

6.5 Does a higher W help?

The third fix, and the most interesting answer.

Each cell is the verdict the client got, then the value every R=3 read returns after one read touches the residue. Read the value half first: it is B in every row where the write reached at least one replica, in all five W columns. The residue does not care what W was.

Now read the verdict half. The FAILED region grows as W increases: at W=1 exactly one cell reports failure, at W=5 four of the five non-empty rows do. Counting cells with told = FAILED and value B — writes that failed and became permanent anyway — gives 0 at W=1, 1 at W=2, 2 at W=3, 3 at W=4, 4 at W=5.

6.6 Where the effect vanishes

Two boundaries, and a reader who cannot name them has not got the result.

A write that reached nobody. If the coordinator's request never left the building — the top row of the §6.5 grid — then FAILED means failed, and no amount of reading conjures a residue that does not exist. The effect needs a partial write, not a failed one; the two words are not synonyms, and this toy is entirely about the gap between them.

Read-one. At R=1 the read that touches r3 still returns 'B' to its client — the failed write is still handed out — but repaired is empty, because the only replica in the contacted set is the one that already has it. The count stays at 1/5 no matter how many times you read. Read-repair needs a read set wide enough to have somewhere to push. This is the boundary that maps to production: a store queried at consistency level ONE does not promote, and Cassandra's docs say the same thing from the other end — read repair does not run at ONE or LOCAL_ONE.

More generally, the residue spreads to exactly R replicas per repairing read, so the whole effect is governed by R, and it disappears at both ends: R = 1 (nowhere to push) and, in the other direction, an empty reach (nothing to push).

7. Design decisions and roads not taken

7.1 Rollback on failure — the road that looks obvious

If the coordinator knows the write failed, and it knows which replicas took it, why not put the old value back?

It works, when it runs. And it has two costs that are easy to miss.

The first is in the code: Cluster.rollback cannot use put. v1 < v2, so the ratchet rejects it, and a rollback written inside the protocol's own rules is a silent no-op. Running that variant:

So undoing requires Replica.force — a method that writes past the version ordering. The same rule that makes replicas converge without coordination is the rule the undo has to break, which is a fair summary of why eventually consistent stores do not offer one.

The second cost is the gap. The rollback is a second round of messages after the failure, and the coordinator has to be alive to send it. The crash=True row is a coordinator that died in the gap between the partial write and the undo — and the failed write is permanent again, on three replicas. Retrying the rollback later does not close the gap; it just makes the window smaller, and the window is where the failures live.

7.2 What would actually fix it: a consensus round

Making FAILED mean failed requires the decision "this write is committed" to be a durable, agreed-upon fact before any replica exposes the value — which is a transaction, or a consensus round: Paxos, Raft, or two-phase commit with a recoverable coordinator. Then a partial write is a prepared write, invisible to readers until it commits, and a coordinator crash leaves a state a successor can resolve rather than a value already visible to six read sets out of ten. The raft-toy in this repo is the same question answered the other way.

The cost is exactly what Dynamo declined to pay: a second round trip on every write, a leader (so a leader election, and unavailability during it), and liveness that depends on a majority being reachable — where a quorum register stays available for writes as long as any replica is. Cassandra offers both, and prices it honestly: its docs note that a conditional write "will incur a non-negligible performance cost, because Paxos is used."

The trade is real, and it is not obvious that consensus is the right side of it for a shopping cart. What is not defensible is buying the quorum register and believing you got the transaction.

7.3 Repairing the whole contacted set, not just the stale replicas

read calls put on every replica in contact, including the one it took the winning value from. It would be easy to compare versions first and skip the current ones. It would also be redundant: the ratchet already rejects them, returning False, so repaired reports only what actually moved. §5.1 shows what the alternative costs — the > variant reports [2, 3, 4] for two replicas' worth of change.

7.4 Explicit reach and contact lists instead of failure probabilities

The obvious alternative is to give each replica a failure probability and run a few thousand trials. That produces a statistic about how often the aha happens, which is a much weaker artifact than a schedule that demonstrates it happening. Worse, it makes the transcript unreproducible: the whole argument here is that the reader can run demo.py and get these exact digits. The sweeps recover what the random version would have offered — §6.5's grid is every reach from 0 to 5 — without giving up determinism.

7.5 Integer versions supplied by the caller

write takes version as an argument rather than allocating one. This is what makes the demo's v1 and v2 readable, and it keeps the conflict rule to one comparison. It is also the least faithful thing in the toy; see §8.

7.6 One key

The toy holds a dict per replica but the demo only ever touches "cart". Multiple keys would add per-key partitioning, which is the consistent-hashing toy's mechanism, not this one.

8. What's simplified vs. the real thing

Versions are integers, and conflicts are last-write-wins. This is the big one. Dynamo does not use a scalar version, because a scalar cannot represent "these two writes happened concurrently and neither is newer." It uses vector clocks, and when it finds two versions with no causal ordering it does not pick a winner at all — it returns both to the application as siblings and makes reconciling them the application's job, which is why the shopping cart is Dynamo's canonical example: merging two carts means unioning their contents. Cassandra does use last-write-wins, on wall-clock timestamps, which imports every clock-skew problem you would expect. This toy's integer version dodges all of that, and the dodge is doing real work: it makes the "newest wins" rule total, so max() always has an answer. The failed-write promotion in §6.1 does not depend on it — a vector-clock store would surface the residue as a sibling instead of as a winner, and the application would then be asked to merge in a value whose write was reported as failed.

One coordinator, one key, one client at a time. There is no concurrency here at all: no two writes in flight, no interleaving, no clock. Real coordinators handle thousands of concurrent operations per key, and the interesting failures compound — two partial writes to the same key, each promoted by a different reader. The toy's schedule is a single thread stepping through an explicit list, which is what makes it auditable.

reach is a fiction with no timeouts behind it. A real coordinator does not know what it reached. It knows what acknowledged before its timeout expired, which is a strict subset — a replica can apply the write and then have its ack lost, and that replica is in the residue while looking, to the coordinator, exactly like one that never got the message. The toy hands you reach directly because the point is what the residue does, not how hard it is to observe. If anything this understates the problem.

No hinted handoff, and anti-entropy is a hand-written pair list. Real systems drive anti-entropy off Merkle trees over key ranges (the merkle-tree toy is that mechanism) so two replicas can find their differences without shipping every key, and they run hinted handoff, where a replica that could not be reached has its writes buffered by a peer and delivered when it returns. Both are additional paths by which a partial write becomes permanent; §6.4 uses the simplest one to make the point that read-repair is not special.

No durability, no persistence, no failure of the replicas themselves. Replicas are dicts in one process. A real replica must fsync, and can lose the residue in a crash — which is one of the few things that genuinely does remove a failed write, unreliably and by accident.

No sloppy quorums. Dynamo writes to the first N healthy nodes on the preference list rather than the N nodes that own the key, so W acks can come from replicas that are not even the right ones. That makes availability better and the freshness guarantee weaker than the W + R > N arithmetic suggests — a second way the inequality promises less than it appears to.

9. Check yourself

1. At t1 in §6.1, six of the ten read sets return 'B'. Where does the six come from, and which four sets are the others?

2. The read at t3 reports repaired=[2, 4], but three replicas were contacted and all three hold v2 afterwards. Why isn't r3 in the list?

3. You set W = 5 on a 5-replica cluster, reasoning that a write is only "really" done when everyone has it. What happens to the number of writes that are reported failed and are permanent anyway?

4. A write reaches two replicas instead of one, [3, 5], and is still told FAILED at W = 3. How many of the ten read sets return it before anyone reads, and how many after one read at R = 3?

5. Three services share this cluster. One writes, is told FAILED, and compensates — refunds the charge, emails the customer. The other two only read. Which of the three is responsible for the bad state, and what would you find in the logs?

6. You read Cassandra's docs, see that read_repair: NONE buys "write atomicity at the partition level," and switch it on to stop this happening. What have you actually bought?

7. read_sets reimplements the "highest version wins" logic instead of calling read in a loop. Name the bug that would introduce.

10. Further reading

• Dynamo: Amazon's Highly Available Key-value Store — Werner Vogels' post, with the SOSP 2007 paper. The source of this toy's shape, including the sentence "Setting R and W such that R + W > N yields a quorum-like system." The hedge in "quorum-like" is load-bearing and mostly ignored by everyone who quotes the inequality. Read §4.5 for read-repair and §4.6 for hinted handoff; read §4.4 for the vector clocks this toy replaced with an integer, and the shopping-cart sibling-merge that motivates them.
• Cassandra: read repair — the best single confirmation that §6.4 is not a toy artifact. The BLOCKING default "[e]nsures monotonic quorum reads but may sacrifice write atomicity"; NONE "[p]rovides write atomicity at the partition level but not monotonic quorum reads." That is this page's central trade-off, shipped as a config value. Also the source for read repair not running at ONE or LOCAL_ONE, which is §6.6's boundary.
• DataStax: about data consistency — the plainest statement of the claim this toy tests: "Strong consistency can be guaranteed when the following condition is true: R + W > N." Worth reading precisely because it is correct and still leaves a reader believing something stronger than it says.
• Quorum (distributed computing) — the voting arithmetic, Vr + Vw > V and Vw > V/2. Note that it derives one-copy serializability from those rules, which a Dynamo-style register does not provide; the difference is that the classical formulation assumes a transaction manager underneath, and §7.2 is what that assumption costs.
• Cassandra: CQL data manipulation — the price list for §7.2, in the vendor's own words: a conditional write "will incur a non-negligible performance cost, because Paxos is used."
• Jepsen: consistency models — where to go once "is this consistent?" stops being a yes/no question. The map is the point: the property §6.1 violates has a name and a place on it, and it is not the same property W + R > N is about.
• raft-toy in this repo — the same problem solved by paying for consensus instead, and a good look at what the second round trip is actually doing.