Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 ยท Replication

Quorums and Tunable Consistency

Learn quorum replication: N, W and R, why R + W > N guarantees overlap, sloppy quorums, hinted handoff and read repair, with a runnable quorum store.

A single leader is a bottleneck and a single point of failure. Quorum replication removes the leader: any replica can take a write, and the client (or a coordinator) decides how many replicas must agree before an operation counts as successful. Systems in the Dynamo family, such as Cassandra, Riak and DynamoDB's original design, work this way.

The beauty of quorums is a bit of arithmetic. With three numbers, N, W and R, you can slide smoothly between "fast but possibly stale" and "slower but fresh". This lesson explains the arithmetic, tests it by simulation, and then covers the real-world repairs that keep replicas in step: read repair, sloppy quorums and hinted handoff.

N, W and R

  • N is the replication factor: how many replicas hold each piece of data.
  • W is the write quorum: how many replicas must acknowledge a write before it succeeds.
  • R is the read quorum: how many replicas are asked on a read; the newest version among their answers wins.

The write is sent to all N replicas, but the client returns as soon as W have acknowledged. The reads ask R replicas and compare versions (timestamps or version vectors).

The overlap rule: R + W > N

If R + W > N, then any set of R replicas you read from must share at least one replica with any set of W replicas that acknowledged the write. That shared replica holds the latest value, so the read sees it. This is the quorum overlap.

Overlap with N = 3

W = 2 Two of three replicas have the write.
R = 2 Any two replicas include at least one of them.
2 + 2 > 3 A read always meets a fresh copy.

With R + W <= N a read can land entirely on stale replicas.

1 / 2

Majorities are a special case: with N = 2f + 1 and W = R = f + 1, the system keeps working while f replicas are down, and any read overlaps any write.

Measuring staleness

A write that reaches only W replicas leaves the other N - W replicas stale. A read of R randomly chosen replicas is stale when all of them are among the stale ones. We can compute the probability and also check it by simulation. N is 5 below.

Python How often is a read stale?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row where R+W>N is True shows exactly 0 staleness, while every row with False has a real chance of stale reads. For example W=1, R=1 is stale most of the time, because the single read hits the single fresh replica only one time in five.

R + W > N does not make the system linearizable. Concurrent writes, a write that fails halfway (it may be visible on some replicas, and later "appears"), clocks used for versions, and sloppy quorums can all still produce odd results. It is a freshness aid, not a full consistency guarantee. See Consistency Models.

Availability: why not always W = N?

Writing to all replicas (W = N) and reading from one (R = 1) satisfies the overlap, but a single dead replica blocks all writes. Majority quorums tolerate failures: with N = 3 and W = R = 2, one replica can be down and both reads and writes still succeed. This is the central trade-off: higher W or R means fresher data but less tolerance for slow or dead nodes, and higher latency (you wait for the slowest of the W or R replies).

Read repair

When a read contacts R replicas and sees that some have an older version, the coordinator already has the new value in hand. Read repair simply writes that newer value back to the stale replicas. Data that is read often heals quickly, at no extra cost. Data that is never read stays stale, which is why systems also run background anti-entropy scans (comparing replicas with hash trees); see Multi-Leader and Leaderless Replication.

Sloppy quorums and hinted handoff

Strict quorums have an annoying property: the N replicas for a key are fixed. If two of three are unreachable (a network problem, say), writes to that key fail even though plenty of other nodes are healthy.

A sloppy quorum relaxes the rule. When a home replica is down, the write is accepted by another reachable node instead, which holds the data on the home replica's behalf with a hint ("this belongs to node B"). When B comes back, the stand-in forwards the data. That last step is hinted handoff.

The effect is higher write availability. The cost: until the handoff happens, the home replicas do not have the value, so a read from them can be stale even when R + W > N. A sloppy quorum is an availability feature that gives up the overlap guarantee.

sequenceDiagram
    participant Cl as Client
    participant A as Node A (home)
    participant D as Node D (stand-in)
    participant B as Node B (home, down)
    Cl->>A: write x=1
    Cl->>D: write x=1 (hint: for B)
    Note over B: B is down
    B->>B: B recovers
    D->>B: hinted handoff: x=1

The stand-in stores the write with a hint and hands it to the real owner when it returns.

A quorum store simulation

Here is a small cluster with home replicas A, B, C and stand-ins D, E. First we compare a strict and a sloppy quorum while B and C are down, then we read stale data right after they recover, and then hinted handoff fixes it.

Python Sloppy quorum and hinted handoff

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The strict quorum rejects the write (only A is reachable). The sloppy quorum accepts it, with acknowledgments from A and from the two stand-ins. Right after B and C come back, a read of ["B", "C"] still returns version 0, which means "nothing": that is the price of sloppiness. After handoff() the same read returns (1, 'book').

Now let's see read repair heal a replica set.

Python Read repair

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first read asked only stale replicas and returned old data, with nothing to repair, because read repair can only spread what the read has seen. The second read touched A, noticed B was behind, and fixed it. Now every later read that includes B is fresh. C stayed stale until the last read paired it with the repaired B, and that read healed it too (or anti-entropy would have caught it).

Putting it together

Mechanism What it does Cost
R + W > N Reads overlap the latest write Less availability, higher latency
Read repair Heals stale replicas on read Only fixes data that is read
Hinted handoff Delivers writes missed by down nodes Stale reads before delivery; hints can be lost
Anti-entropy Background comparison of replicas Extra network and CPU

Next you will see how leaderless designs deal with the hardest remaining question, two writes at once, in Multi-Leader and Leaderless Replication.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With N = 5, which setting guarantees that a read overlaps the latest successful write?

    3 + 3 = 6 > 5, so any read set shares a replica with any write set. 2 + 2 = 4 and 1 + 4 = 5 do not exceed N, and a sloppy quorum gives up the overlap.
  2. 2. What does a larger W do?

    More acknowledgments mean more replicas have the data, but the write waits for more (and slower) nodes and fails if too few are reachable.
  3. 3. What is hinted handoff?

    The stand-in keeps a hint naming the intended owner and delivers the data once the owner is back.
  4. 4. Why can a sloppy quorum return stale data even if R + W > N?

    The overlap argument assumes reads and writes use the same N home replicas. With stand-ins holding the write, a read of the home replicas can miss it until handoff.

Summary

  • N replicas hold each item; a write needs W acknowledgments and a read asks R replicas, taking the newest version.
  • R + W > N makes read and write sets overlap, so reads see the latest successful write; it is a freshness guarantee, not full linearizability.
  • Raising W or R trades availability and latency for freshness; majorities (W = R = f + 1 for N = 2f + 1) tolerate f failures.
  • Read repair fixes stale replicas that a read discovers; anti-entropy fixes the rest in the background.
  • Sloppy quorums accept writes on stand-in nodes during failures (higher availability) and use hinted handoff to deliver them later, at the cost of the overlap guarantee.

Next: Multi-Leader and Leaderless Replication