AdvancedSystem Design · Lesson 13 of 19 · Updated ·
Consistency Models and Quorums — Strong vs Eventual, R + W > N and PACELC
The databases lesson introduced replication and the CAP theorem. This lesson goes one level deeper and answers the question interviewers follow up with: "If you have three copies of the data, what exactly does a read return?" The answer depends on the consistency model you choose, and with leaderless databases, on simple arithmetic: R + W > N.
1. Why replicas disagree
A replica is a copy of the data on another machine. Copying takes time — milliseconds normally, seconds or more when a network link is slow or a machine is overloaded. During that gap, different replicas hold different versions.
Example: Asha changes her display name from "asha_k" to "Asha Kumari". Replica 1 has the new name; replicas 2 and 3 have not received it yet. Her friend's app reads from replica 3 and still sees "asha_k". Whether that is acceptable depends on the feature.
2. Consistency models, from strongest to weakest
A consistency model is a promise about what reads may return while copies are catching up.
| Model | Promise | Good for |
|---|---|---|
| Strong (linearizable) | every read sees the latest completed write, as if there were one copy | bank balances, seat booking, stock at checkout |
| Read-your-writes | you always see your own changes; others may lag | editing your profile or a post |
| Monotonic reads | once you have seen a value, you never see an older one later | refreshing a feed should not go back in time |
| Causal | if B depends on A, everyone sees A before B | a reply never appears before the message it answers |
| Eventual | if writes stop, all copies become the same eventually | like counts, view counts, "last seen" |
Stronger models need more coordination between replicas: more waiting, and more requests refused during network problems. Weaker models are faster and stay available, but users may see stale data for a while.
Read-your-writes in practice: after a user updates something, send that user's reads to the leader (primary) for a short time, say 10 seconds, or until the replica has caught up to the version the user wrote.
3. Leader-based and leaderless replication
- Leader-based (MySQL, PostgreSQL, MongoDB replica sets): all writes go to one leader, which copies them to followers. Reading from the leader is strongly consistent; reading from followers is eventually consistent.
- Leaderless (Cassandra, Amazon Dynamo and similar designs): the client — or a coordinator node acting for it — sends a write to several replicas at once and reads from several at once. There is no single leader to fail. Consistency then comes from quorums.
4. Quorums: R + W > N
Three numbers describe a leaderless setup:
- N — how many replicas store each item (often 3).
- W — how many replicas must confirm a write before it counts as successful.
- R — how many replicas a read asks before answering.
If R + W > N, every read set overlaps every write set in at least one replica — so every read reaches at least one replica that has the latest write. Each value carries a version (or timestamp), and the read returns the newest version among the replies.
We do not have to trust the rule — we can check every possible combination of replicas:
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), (3, 3, 1), (3, 1, 3), (5, 3, 3), (5, 2, 3)]:
rule = "R+W>N " if r + w > n else "R+W<=N"
print(f"N={n} W={w} R={r} {rule} every read sees the write: {always_overlap(n, w, r)}")
N=3 W=2 R=2 R+W>N every read sees the write: True
N=3 W=1 R=1 R+W<=N every read sees the write: False
N=3 W=3 R=1 R+W>N every read sees the write: True
N=3 W=1 R=3 R+W>N every read sees the write: True
N=5 W=3 R=3 R+W>N every read sees the write: True
N=5 W=2 R=3 R+W<=N every read sees the write: False
Every configuration with R + W > N passes; every one without it fails. With N=5, W=2, R=3, some read of 3 replicas can miss both replicas that got the write.
Now a read in action, including read repair — when a read notices a stale replica, it writes the newest value back to it:
replicas = {"A": (1, "asha_k"), "B": (1, "asha_k"), "C": (1, "asha_k")} # (version, value)
def write(nodes, version, value):
for n in nodes:
replicas[n] = (version, value)
def read(nodes):
replies = [replicas[n] for n in nodes]
newest = max(replies) # highest version wins
for n in nodes: # read repair
if replicas[n] < newest:
replicas[n] = newest
return newest[1]
write(["A", "B"], 2, "Asha Kumari") # W = 2: C missed the write
print("read B, C ->", read(["B", "C"])) # R = 2 overlaps at B
print("after repair:", replicas)
read B, C -> Asha Kumari
after repair: {'A': (2, 'Asha Kumari'), 'B': (2, 'Asha Kumari'), 'C': (2, 'Asha Kumari')}
5. Tuning R and W
| Setting (N = 3) | Effect |
|---|---|
| W = 2, R = 2 | balanced: consistent reads, survives one replica being down for both reads and writes |
| W = 3, R = 1 | very fast reads, but a write fails if any one replica is down |
| W = 1, R = 3 | very fast writes, slow reads that fail if any replica is down |
| W = 1, R = 1 | fastest and most available, but eventual only — reads may be stale |
Cassandra lets you choose per query (consistency levels such as ONE, QUORUM, ALL), so a payment table and a page-view counter can live in the same cluster with different guarantees.
Quorums are not magic: concurrent writes to the same key still need a rule to pick a winner (often "last write wins" by timestamp, which can silently drop one write), and failed writes that reached fewer than W replicas can leave partial data behind. That is why money still lives in databases with transactions.
6. PACELC: the part CAP leaves out
CAP only talks about what happens during a network Partition: choose Availability or Consistency. But partitions are rare. PACELC adds: Else (normal operation), choose between Latency and Consistency.
- Waiting for 3 replicas in two data centres to confirm makes every request slower, even on a perfect day.
- Dynamo-style systems are usually tuned PA/EL: stay available in a partition, prefer low latency otherwise.
- A traditional single-leader SQL setup with synchronous replicas is closer to PC/EC.
Saying "this also costs latency on normal days" shows deeper understanding than reciting CAP.
Common mistakes
- Saying "we'll use eventual consistency" for seat booking or wallet balances.
- Reading from a follower immediately after the user's own write, so the user thinks the save failed.
- Thinking R + W > N alone prevents all conflicts — concurrent writes still need a resolution rule.
- Choosing W = N for "safety" and then being surprised that one slow replica blocks every write.
Quick recap
- Replicas lag, so reads can be stale; a consistency model says how stale is allowed.
- Strong → read-your-writes → monotonic → causal → eventual: weaker is faster and more available.
- Leaderless quorum: write to W, read from R of N replicas; R + W > N means every read overlaps the latest write.
- Read repair fixes stale replicas during reads.
- PACELC: in a partition choose A or C; otherwise choose latency or consistency.