Skills101

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.

A spectrum from strong consistency on the left (bank balance, seat booking) through read-your-writes (profile edits) and causal (chat replies) to eventual consistency on the right (like counts, view counts); stronger means slower and less available, weaker means faster and more available

ModelPromiseGood for
Strong (linearizable)every read sees the latest completed write, as if there were one copybank balances, seat booking, stock at checkout
Read-your-writesyou always see your own changes; others may lagediting your profile or a post
Monotonic readsonce you have seen a value, you never see an older one laterrefreshing a feed should not go back in time
Causalif B depends on A, everyone sees A before Ba reply never appears before the message it answers
Eventualif writes stop, all copies become the same eventuallylike 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.

Three replicas A, B and C: a write with W = 2 reached A and B; a read with R = 2 asked B and C; B is in both sets, so the read sees version 2 and C is repaired

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 = 2balanced: consistent reads, survives one replica being down for both reads and writes
W = 3, R = 1very fast reads, but a write fails if any one replica is down
W = 1, R = 3very fast writes, slow reads that fail if any replica is down
W = 1, R = 1fastest 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.

Practice what you learned

📝 Quiz: Consistency and Quorums5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →