SD7.4 · LESSON 4 OF 6

Quorum overlap

Compare consistency contracts and distribute data while tracing stale reads, partitions and hot keys.

THE IDEA

Quorum overlap

If a write goes to W of N replicas and a read asks R of them, the two sets must share at least R + W − N replicas. For N = 5 and R = W = 3 that is 1, so every read set contains a replica that took part in every completed write, and a read that returns the highest version it sees finds the latest completed write. For R = W = 2 the bound is 0 and a read can miss it. But this is only one condition: a write that fails after reaching 2 replicas can be seen by one reader and missed by the next.

replicas N5read set R3write set W3

smallest possible overlap = max(0, R + W − N) = max(0, 3 + 3 − 5) = 1 every read set shares at least 1 replica with every completed write set, so a read that picks the highest version sees the latest completed write number of 3-member write sets: 10

but R + W > N is only one condition: a write that FAILED after reaching 2 of 5 replicas can be seen by one read set and missed by a later one, so reads can go backwards concurrent writers, version rules and read repair are part of the protocol too

Change N, R and W.

Predict first. Does R + W > N alone prove a service is linearizable?

Chapter context

Replication copies data for resilience or read capacity; partitioning assigns different data to different owners. Both introduce coordination and failure behavior that an application must explicitly account for.

TRY IT YOURSELF

Part 1. Do it hands-on

Compute overlaps by hand, then verify them by enumeration and find the partial-write anomaly.

replicas N5read set R3write set W3

min overlap, N=5 R=3 W=3 R=2 W=2 N=5 3-member sets of 5 R + W > N proves linearizability? (yes/no)

To do: N = 5 replicas, write set size W = 3, read set size R = 3. Smallest possible overlap between any read set and any write set (R + W − N)?
To do: With R = 2 and W = 2 on N = 5 (smallest overlap, never below 0)?
To do: How many different 3-member sets can be chosen from 5 replicas?
To do: Does R + W > N alone prove a service is linearizable? Type yes or no

Part 2. Do it in code

overlap_min(r, w, n): the smallest possible intersection of an r-member read set and a w-member write set among n replicas: max(0, r + w − n).
all_overlap(r, w, n): True if EVERY r-set intersects EVERY w-set (check by enumerating combinations, not by the formula).
n_sets(n, k): how many k-member sets can be chosen from n replicas.
read_latest(replicas, read_set): replicas is a list of {"version", "value"}; return the value with the highest version among the read set's replicas.
complete_write(replicas, write_set, version, value): set those replicas to the new version/value.
partial_write_anomaly(n, w, reached): a write that reached only `reached` replicas (fewer than w, so it failed) can still be read by some read sets. Return True if there exist a read set that sees the new value AND a later read set that does not, for R = w (sets of size w), i.e. the reads go backwards.

import itertools
from math import comb

def overlap_min(r, w, n):
    pass

def all_overlap(r, w, n):
    pass

def n_sets(n, k):
    pass

def read_latest(replicas, read_set):
    pass

def complete_write(replicas, write_set, version, value):
    pass

def partial_write_anomaly(n, w, reached):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does R+W>N alone prove a service is linearizable?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For fixed sets over N replicas, $|R\cap W|\ge |R|+|W|-N$ . Thus R=W=3 with N=5 forces at least one shared member. This is a set fact, not a complete consistency proof. Shard and replication counts describe different dimensions of the layout.

Worked example

Five replicas use read sets and write sets of size three. The lower bound on overlap is 3+3−5=1. Enumerating all three-member sets confirms every pair overlaps. A read still needs the right version-selection and concurrency rules; intersection alone does not tell which stored value is newest or committed.

Reference code

The following example uses the Python standard library and does not call a remote service.

from itertools import combinations
replicas=set(range(5))
sets=[set(x) for x in combinations(replicas,3)]
assert min(len(r&w) for r in sets for w in sets) == 1
assert 3+3-5 == 1
assert all(r&w for r in sets for w in sets)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Quorum arithmetic does not establish a full consistency contract. Sharding is not replication. CAP availability is a precise failure-model property, not the same as an ordinary monthly uptime percentage.