Replication & Quorums
1 / 30
“Replication means copies.”
The hard part is not making copies. The hard part is deciding which copies matter when they disagree.
N: number of replicas for a keyR: responses required for read successW: acknowledgments required for write successA quorum is a success threshold over a replica set.
A = old
B = old
C = old
Write new reaches A and B.
A = new
B = new
C = old
A read from C alone is stale.
Write acknowledgments: {A, B}
Read responses: {B, C}
Intersection: {B}
The overlap is where the read can discover the write.
R + W > N
If the sum is bigger than the universe, disjoint sets are impossible.
N=3, R=1, W=1
Write succeeds on {A}
Read succeeds on {C}
No overlap. The read can miss the write.
W + W > N
If two write quorums can be disjoint, two writes can both succeed without any replica seeing both.
Read survives N - R replica failures
Write survives N - W replica failures
Increasing consistency thresholds usually reduces availability.
N=3, R=2, W=2
Balanced, not free.
N=3, R=1, W=3
N=3, R=3, W=1
R live responsesA -> value=a, ts=1
B -> value=b, ts=3
C -> value=a, ts=2
Return b. Repair A and C.
Responsible replicas: {A, B, C}
B is down.
Write to D with a hint:
D stores value, hintFor=B
Later D replays to B.
Hinted handoff improves availability. It does not erase the distinction between responsible replicas and temporary holders.
Strict quorum:
write only to responsible replicas
Sloppy quorum:
write to fallback nodes if responsible replicas are down
Different consistency implications.
A quorum applies to a concrete replica set.
Before asking “does R intersect W?” ask:
Which nodes are responsible for this key?
0 ---- A ---- B ---- C ---- D ---- max
Key hash chooses the next token. Additional replicas are the next unique nodes around the ring.
One physical node may own multiple tokens.
Replica selection must avoid returning the same physical node twice.
“Highest timestamp wins” is simple.
It can also lose data when writes are concurrent or clocks drift.
X = {A:2, B:1}
Y = {A:1, B:1}
X dominates Y.
X = {A:1}
Y = {B:1}
Concurrent conflict.
The non-dominated versions are the frontier.
One frontier value: no conflict. Multiple different frontier values: conflict.
Read repair heals hot keys. Anti-entropy heals cold keys.
Compare summaries, find divergence, copy newer versions.
Read-your-writes:
After writing v5, do not read v4.
Monotonic reads:
After reading v5, do not later read v4.
Responses:
[8ms, 12ms, 40ms, 120ms, timeout]
R=1 returns after 8ms. R=3 returns after 40ms. R=5 fails or waits for timeout.
Build a small Dynamo-style key-value simulator.
Must support:
A learner should be able to explain stale reads, conflict creation, and repair behavior from an actual event timeline.