Replication and quorums
Read and write a majority of replicas so that every read overlaps the latest write.
On this page
Dictionaries, tuples, and itertools.
- Read and write a majority of replicas so that every read overlaps the latest write.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
To survive machine failures, distributed systems keep several copies, called replicas, of the same data. Replication brings consistency problems: if a write reaches only some replicas, readers may see stale data. A quorum system controls this by requiring a write to be acknowledged by W of the N replicas and a read to consult R replicas.
If R + W > N, every read set and every write set must share at least one replica, because together they would otherwise need more than N distinct nodes. A reader that takes the value with the newest version among the replicas it asks is therefore guaranteed to see at least one copy of the latest completed write. Dynamo-style stores use this idea with tunable R and W. With N = 3, choosing W = 2 and R = 2 satisfies R + W > N and still tolerates one failed replica for both reads and writes.
The example keeps three replicas, writes version 1 to two of them, and reads from two others. The read overlaps the write at replica 1 and returns the new value. Reading only replica 2 returns the stale None. The final lines test every combination of read and write sets exhaustively: overlap holds with R = 2, W = 2, and fails with R = 1. Overlap alone is not full linearizability, and the CAP theorem reminds us that during a network partition a system must give up either consistency or availability.
Code example
from itertools import combinations
N = 3
replicas = [{"version": 0, "value": None} for _ in range(N)]
def write(value, version, targets):
for i in targets:
replicas[i] = {"version": version, "value": value}
def read(targets):
return max((replicas[i] for i in targets), key=lambda r: r["version"])["value"]
write("v1", 1, [0, 1])
print(read([1, 2]))
print(read([2]))
def always_overlap(w, r):
return all(set(ws) & set(rs) for ws in combinations(range(N), w) for rs in combinations(range(N), r))
print(always_overlap(2, 2))
print(always_overlap(2, 1))v1 None True False
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
from itertools import combinations N = 3replicas = [{"version": 0, "value": None} for _ in range(N)] def write(value, version, targets): for i in targets: replicas[i] = {"version": version, "value": value} def read(targets): return max((replicas[i] for i in targets), key=lambda r: r["version"])["value"] write("v1", 1, [0, 1])print(read([1, 2]))print(read([2])) def always_overlap(w, r): return all(set(ws) & set(rs) for ws in combinations(range(N), w) for rs in combinations(range(N), r)) print(always_overlap(2, 2))print(always_overlap(2, 1))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| A write to two of three replicas (W = 2): replica 2 has not received it yet. | replicas: v1, v1, none | — | |
| A read of two replicas includes replica 1, which has version 1, so the newest version is returned. | replicas: v1, v1, none | v1 | |
| Reading only the stale replica returns None: with R = 1 the read missed the write. | replicas: v1, v1, none | v1 None | |
| Every possible pair of write replicas and pair of read replicas intersect, since 2 + 2 > 3. | replicas: v1, v1, none | v1 None True | |
| With R = 1 some read sets miss the write set entirely, since 2 + 1 is not greater than 3. | replicas: v1, v1, none | v1 None True False |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
A quorum operation contacts R or W replicas in parallel, so latency is that of the slowest replica in the quorum, while message count is O(R) or O(W).
- R + W > N guarantees overlap, not linearizable behavior. Concurrent writes, failures, and sloppy quorums need extra mechanisms such as read repair and versioning.
- Higher R and W give stronger consistency but lower availability and higher latency.
- Replica versions must be ordered correctly. Using unsynchronized wall-clock timestamps can pick the wrong winner.
Try it yourself
With N = 5, which (W, R) pairs guarantee overlap and tolerate two failed replicas for both reads and writes?
Reveal answer and reasoning
W = 3 and R = 3. They overlap since 3 + 3 > 5, and each quorum can still be formed from the 3 replicas that remain after two failures.