Leaderless replication and quorums
Replication with no leader at all: writing to several replicas, reading from several, and the arithmetic that makes the two overlap.
6 minute lesson
Nobody is in charge
A leader is convenient, and it is a single machine that every write depends on. Leaderless stores do without. Every replica accepts writes. A write is sent to all of them, and it counts as soon as enough have answered. A read asks several and takes the newest answer.
- NReplicas that hold each value
- WReplicas that must confirm a write
- RReplicas that are asked on a read
- replica
- One of several copies of the same data, each kept on a different machine.
- quorum
- A majority of the replicas. Waiting for a quorum, not for all replicas, is a middle way between speed and consistency.
Key terms
Three replicas and two answers
- Write
N is 3 and W is 2. The write x = 7 is sent to all three replicas. Replica C is busy and misses it. A and B confirm, and that is enough.
- Ax = 7
- Bx = 7
- Cx = 5
- Read
R is 2. A read asks two replicas, say B and C. It gets 7 from B and 5 from C. Each value carries a version, and the read returns the newer one: 7.
- From B and C7 and 5
- Returned7
- Why it works
Two replicas have the write, and two are read. Out of three, those two pairs must share at least one replica. So every read meets the latest write.
- W + R2 + 2 = 4
- N3
A leaderless store keeps each value on N = 5 replicas. Writes wait for W = 3 confirmations. Reads ask R = 3 replicas.
Is a read certain to see the latest confirmed write?
- Yes: 3 + 3 is more than 5, so the groups overlap
- No: 3 is fewer than 5, so a read can miss them
- Yes: every read in such a store is up to date
- No: that would need W and R to be 5 each
Show the answer
- Yes: 3 + 3 is more than 5, so the groups overlap
Three replicas have the write, and three are read. Five replicas cannot hold two groups of three that have nothing in common: at least one replica is in both. That one returns the latest value, and the read picks it by its version. W + R = 6 is greater than N = 5.
W + R > N: the write group and the read group share a replica, so the read sees the write.
The rule and its dial
If W + R is greater than N, every read overlaps every confirmed write. A group of replicas large enough for that is a quorum. Within the rule, and outside it, the three numbers are a dial.
- W = 2, R = 2Consistentone replica may fail
- W = 1, R = 1Fastestreads can miss the latest write
- W = 3, R = 1Fast readsone failed replica stops all writes
A leaderless store runs with N = 3, W = 2 and R = 2.
How many replicas can be down while both reads and writes still work?
- 0
- 1
- 2
- 3
Show the answer
- 1
A write needs two confirmations and a read needs two answers. With one replica down, two are left, which is exactly enough for both. With two down, only one remains, and neither a write nor a read can gather its two. So the store survives the loss of one replica without anyone noticing, and with no failover.
A quorum store tolerates N − W failed replicas for writes and N − R for reads.
How a replica catches up
- During a read. A read that gets an old value from one replica writes the newer value back to it.
- After an outage. Another replica keeps the writes that a failed one missed and hands them over when it returns.
In a leaderless store, what do N, W and R mean, and which rule makes a read see the latest write?
Show the answer
N is the number of replicas that hold each value, W the number that must confirm a write, and R the number asked on a read. If W + R is greater than N, the replicas that confirmed the write and the replicas that are read share at least one member, so the read sees the newest value. With N = 3, W = 2 and R = 2 that holds, and one replica may be down.
Recap
- Leaderless stores send writes to all replicas and count them once W have confirmed.
- With W + R greater than N, every read overlaps the latest write.
- Lower W and R for speed, at the price of stale reads. Replicas catch up on reads and after outages.