Read and write quorum simulator

Each card is a replica, showing the version and value it stores. A write goes to every replica that is up; the first W to store it make it succeed, and the copies to the others stay in flight until you deliver them. A read asks R replicas at random and returns the highest version it sees. The side panel counts, from the current state, how many of the possible read sets would miss the last acknowledged write.

• Set R = 1 and W = 1, write, and read a few times without delivering the copies: some reads return the old value.
• Set R = 2 and W = 2 with three replicas: no read set misses the write, whichever replicas the write reached first.
• Take a replica down and write: it misses the write and stays behind after it comes back until a read repair or anti-entropy fixes it.
• Send a write that fails part-way and read repeatedly with read repair off: the reads flip between the old value and the one the client was told had failed.

A quorum is the number of replicas that must take part in an operation for it to count. In leaderless replication each item is stored on N replicas; a client, or a coordinator node acting for it, sends every write to all of them and treats it as successful once W confirm it, and sends a read to R of them and keeps the newest answer. No replica is in charge, so any of them can accept writes, and a few can be slow or down without stopping the system.

R and W trade against each other. A small W makes writes fast and available; a small R does the same for reads. How small they can be before reads start returning old data depends on N.

If R + W > N, a read set and a write set cannot be disjoint: together they would need more than N distinct replicas. So every read reaches at least one replica that stored the last successful write, and choosing the highest version returns it. If R + W ≤ N, there is a read set that misses it entirely. The model was checked by trying every pair of subsets for N up to 7.

Settings and what they cost, for replicas that are each up 99% of the time, independently. "Stale" is the chance that a read issued just after a write was acknowledged, before any further copies arrive, misses it; it equals C(N − W, R) / C(N, R), and the simulated column comes from running the model:

With R + W ≤ N the system is eventually consistent: the write keeps spreading after it is acknowledged, so the chance of a stale read falls quickly with time. Peter Bailis and colleagues called this probabilistically bounded staleness and measured it with latency distributions from production systems. The same calculation with a made-up distribution, each copy arriving after an exponentially distributed delay averaging 10 ms, gives the chance that a read t milliseconds after the acknowledgement returns the new value, with N = 3:

R + W > N is about the overlap of sets, not about atomicity. Several things still go wrong:

• Failed writes are not rolled back. A write that reached fewer than W replicas is reported as failed but stays on the replicas it reached, and a later read may return it. With N = 3 and R = W = 2, after a write that reached one replica, twelve reads in the model returned versions 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2: a value the client was told had failed, appearing and disappearing.
• Read repair settles it, one way. With read repair, the first read that sees the newer version writes it to the replica it asked, and from then on every read set overlaps with it: the same twelve reads returned 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2. The failed write has quietly succeeded.
• Concurrent writes conflict. Two clients writing at once may each reach a different W replicas. Last write wins by timestamp keeps one and silently drops the other; Dynamo instead keeps both as siblings tagged with vector clocks and lets the application merge them.
• Sloppy quorums break the overlap. If the home replicas are unreachable and the write is accepted by stand-in nodes, a read of the home replicas can miss it until hinted handoff delivers it.
• Reads are not linearizable. A read concurrent with a write can return the new value while a later read returns the old one. Making quorum reads linearizable requires the reader to finish read repair before returning, and even then writes need more than last write wins.

Amazon's 2007 Dynamo paper describes N, R and W as configurable per application, with (3, 2, 2) as the common choice, a sloppy quorum over the first N healthy nodes on the consistent-hash ring, hinted handoff and Merkle-tree anti-entropy. Apache Cassandra and Riak follow the same design. Cassandra lets each request choose a consistency level, ONE, QUORUM (a majority, n/2 + 1, of the replicas), ALL or LOCAL_QUORUM for a majority within one datacenter, and its documentation describes this as a version of Dynamo's R + W > N mechanism.

Consensus protocols use quorums too, but differently. Paxos and Raft need a majority to accept each entry and a majority to elect a leader, so any two majorities overlap and a new leader always knows about every committed entry. Flexible Paxos (Howard, Malkhi and Spiegelman, 2016) showed that only the election and replication quorums need to intersect, not two replication quorums, which allows smaller replication quorums in exchange for larger election quorums.

David Gifford introduced quorum-based replication in "Weighted Voting for Replicated Data" at SOSP in 1979, from work at Xerox PARC: each copy of a file holds a number of votes, a read must collect r votes and a write w votes, and r + w greater than the total number of votes ensures every read sees the latest write. Robert Thomas published a majority-consensus approach the same year. The idea returned to prominence in 2007 with Amazon's Dynamo, which used it for availability rather than correctness, and in 2012 Bailis and colleagues quantified how stale partial quorums are in practice.