Replication Strategies and Quorums

Three ways to keep copies

Replication keeps copies of the same data on several nodes. In single-leader replication, all writes go to one leader that streams changes to followers; it gives a clear order of writes but the leader is a bottleneck and must be replaced on failure, which is exactly where consensus comes in. Multi-leader replication accepts writes at several leaders (often one per data centre) and syncs them asynchronously, so concurrent writes conflict and need resolution. Leaderless replication (Dynamo-style, as in Cassandra) lets clients write to several replicas directly and uses quorums: with N replicas, a write waits for W acknowledgements and a read queries R replicas. If W + R > N, every read set overlaps every write set in at least one node, so a read can see the latest acknowledged write, though without consensus there are still edge cases (concurrent writes, sloppy quorums) where this is not linearizable.

Replication topologies

Single-leader funnels writes through one node; multi-leader accepts writes in several places; leaderless sends writes and reads to overlapping quorums.

Checking quorum overlap by brute force

Enumerate every possible write set and read set and check that they always intersect.

from itertools import combinations

def always_overlap(n, w, r):
    nodes = range(n)
    return all(set(ws) & set(rs)
               for ws in combinations(nodes, w)
               for rs in combinations(nodes, r))

for n, w, r in [(3, 2, 2), (3, 1, 1), (5, 3, 3), (5, 2, 3), (5, 4, 2)]:
    print(f"N={n} W={w} R={r}  W+R>N: {w + r > n!s:5}  overlap: {always_overlap(n, w, r)}")

Output:

N=3 W=2 R=2  W+R>N: True   overlap: True
N=3 W=1 R=1  W+R>N: False  overlap: False
N=5 W=3 R=3  W+R>N: True   overlap: True
N=5 W=2 R=3  W+R>N: False  overlap: False
N=5 W=4 R=2  W+R>N: True   overlap: True

Majority is a special quorum

Consensus protocols use majority quorums (more than N/2) for both phases. Any two majorities overlap, which is the single property Raft and Paxos lean on to make sure a new leader learns about every committed decision.

Quick check: With N = 5 replicas, which setting guarantees read and write quorums always overlap?

• W = 2, R = 2
• W = 1, R = 3
• W = 3, R = 3
• W = 2, R = 3