Quorum reads and writes (N, R, W): an interactive simulator

A quorum is how many replicas must take part for a read or a write to count. With N copies of each key, a write succeeds once W replicas have acknowledged it and a read returns once R replicas have answered. When R + W > N, the replicas a read hears from always include at least one that has the latest acknowledged write, so reads are not stale. Smaller R and W are faster and survive more failures, but let reads miss recent writes.

The playground keeps one key on three or five replicas, writes it every 50 ms and reads it every 20 ms or so for a minute. Choose W and R, make one replica fall behind, slow down or fail, and watch one read up close and the whole minute’s stale reads, latency and failures.

How quorum reads and writes work

1. Write: the coordinator sends the new value, with a version or timestamp, to all N replicas of the key.
2. Acknowledge: as soon as W replicas confirm they have stored it, the write succeeds. The others still get it, just later.
3. Read: the coordinator asks the replicas for the key and waits for R answers.
4. Pick the newest: it returns the value with the highest version among those R.
5. Repair: if some answers were older, it can write the newest value back to those replicas (read repair).

Why R + W > N means reads see the latest write

A successful write is on at least W of the N replicas. A read hears from R of them. If R + W > N, the two groups cannot avoid each other: there are not enough replicas for the read to pick R that all lack the write. With N = 3, W = 2 and R = 2, any two replicas a read asks include at least one of the two that took the write.

In the playground’s first preset, one of three replicas applies writes up to half a second late, and W = 1, R = 1. A third of reads are answered first by that replica, and 33.5% of reads return an older value than one that had already been acknowledged. Change only W and R to 2 and 2, and no read in the minute is stale. With all replicas healthy, W = 1 and R = 1 still return a stale value now and then, about 0.2% of reads, when a read lands just after a write on a replica it has not reached yet.

Choosing N, R and W

A majority quorum, W and R both more than N / 2, tolerates the most failures while keeping the overlap: with N = 3 it survives one replica down, with N = 5 two. The third preset shows the cost of waiting for everyone: with W = 3 and one slow replica, every write takes as long as that replica, 567 ms at p99, while reads at R = 1 take 5.6 ms at p99.

What a quorum does not guarantee

• Sloppy quorums break the overlap. When some of a key’s replicas are unreachable, Dynamo-style systems can accept the write on other nodes and hand it back later (hinted handoff). Writes stay available, but a read of the usual replicas can miss them.
• Failed writes are not rolled back. If fewer than W replicas acknowledge, the client gets an error, but the replicas that did store the value keep it, and later reads may return it.
• Concurrent writes need a rule. Two clients writing the same key at once leave different replicas with different values. Last write wins by timestamp silently drops one, and clock skew can make it the wrong one; version vectors keep both for the application to merge.
• It is not linearizable on its own. A read that overlaps an in-flight write can see the new value while a read just after it sees the old one, unless reads repair stale replicas before they return.

Where you meet quorums

Cassandra exposes them as consistency levels per request: ONE, QUORUM, ALL, and LOCAL_QUORUM, which counts only replicas in the local data centre so a request never waits on another region. QUORUM for both reads and writes gives R + W > N. Riak sets N, R and W per bucket. DynamoDB hides the numbers and offers eventually consistent or strongly consistent reads instead. Consensus protocols such as Raft use majority quorums too, but with a leader that orders every write, which is what makes them linearizable.

Quorum reads and writes in code

import concurrent.futures as cf

def write(replicas, key, value, version, w):
    pool = cf.ThreadPoolExecutor(len(replicas))
    calls = [pool.submit(r.put, key, value, version) for r in replicas]   # send to all N
    acks = 0
    try:
        for call in cf.as_completed(calls, timeout=0.5):
            if call.exception() is None:
                acks += 1
                if acks == w:
                    return True                # the slower replicas still get the write
    except cf.TimeoutError:
        pass
    raise WriteFailed(f"only {acks} of {w} acknowledged")   # not rolled back where it landed

def read(replicas, key, r):
    pool = cf.ThreadPoolExecutor(len(replicas))
    calls = [pool.submit(rep.get, key) for rep in replicas]               # ask all N
    answers = []
    try:
        for call in cf.as_completed(calls, timeout=0.5):
            if call.exception() is None:
                answers.append(call.result())  # (value, version)
                if len(answers) == r:
                    return max(answers, key=lambda a: a[1])   # newest version wins
    except cf.TimeoutError:
        pass
    raise ReadFailed(f"only {len(answers)} of {r} answered")

In a system design interview

State the numbers and what they buy: “Each key is on 3 replicas in different availability zones; we write and read at quorum, 2 and 2, so we survive one replica down and never read older than the last acknowledged write, at the cost of waiting for the second-fastest replica on every request.” Then expect the follow-ups: what happens with two replicas down, how concurrent writes are resolved, how replicas that missed writes catch up (read repair, hinted handoff and anti-entropy with Merkle trees), and what you would relax for data that can be a little stale.

Read the guide to quorums and leaderless replication, or watch a strong candidate design a distributed key-value store, where N, R and W are a central choice.

Questions people ask