What you will learn
- What the CAP theorem actually says (and what it doesn’t).
- PACELC: the trade-off that applies even when nothing is broken.
- The common consistency levels in plain words.
- How quorums let you tune consistency, demonstrated in code.
CAP, stated carefully
In a distributed data store, a network partition (some nodes can’t reach others) will eventually happen. During a partition you must choose:
- Consistency (C): every read sees the latest write, so a node that can’t confirm it’s up to date refuses to answer; or
- Availability (A): every node keeps answering, even if its answer might be stale.
So the real choice is CP or AP during a partition. “CA” isn’t a real option for a distributed system, because you can’t opt out of partitions.
- CP examples: a bank ledger, a lock service (etcd, ZooKeeper), leader election. Better to return an error than a wrong answer.
- AP examples: a shopping cart, social likes, DNS. Better to show something slightly stale than nothing.
PACELC
Partitions are rare; latency is constant. PACELC adds: Else (no partition), you trade Latency against Consistency. Waiting for several replicas to agree makes every request slower. Cassandra and DynamoDB default to lower latency (PA/EL); Spanner-like systems choose consistency (PC/EC).
Consistency levels
From strongest to weakest:
| Level | Guarantee | Feels like |
|---|---|---|
| Linearizable (strong) | Every read sees the latest completed write | One copy of the data |
| Sequential / causal | Everyone sees causally related writes in the same order | Replies never appear before the question |
| Read-your-writes | You always see your own writes | Your post shows up immediately for you |
| Eventual | If writes stop, replicas converge | Likes count catches up in a few seconds |
Pick per feature, not per company: the same app can use strong consistency for payments and eventual consistency for view counts.
Quorums: tunable consistency
Leaderless stores keep N replicas of each key. A write succeeds after W replicas acknowledge; a read asks R replicas and takes the newest version. If R + W > N, every read set overlaps every write set in at least one replica, so the read sees the latest write.
"""Quorum reads and writes over N replicas: why R + W > N gives fresh reads."""
import random
class Replica:
def __init__(self):
self.value, self.version = None, 0
def write(replicas, value, version, w):
# Only W replicas acknowledge before we return (the rest are slow or down).
for r in random.sample(replicas, w):
r.value, r.version = value, version
def read(replicas, r):
# Ask R replicas and keep the answer with the highest version.
answers = random.sample(replicas, r)
best = max(answers, key=lambda rep: rep.version)
return best.value
def stale_rate(n, w, r, trials=10_000):
stale = 0
for t in range(1, trials + 1):
replicas = [Replica() for _ in range(n)]
write(replicas, "old", 1, n) # everyone has the old value
write(replicas, "new", 2, w) # the new value reaches only W
if read(replicas, r) != "new":
stale += 1
return stale / trials
if __name__ == "__main__":
random.seed(7)
for n, w, r in [(3, 1, 1), (3, 2, 1), (3, 2, 2), (3, 3, 1), (5, 3, 3)]:
print(f"N={n} W={w} R={r} R+W>N={r + w > n!s:5} stale reads: {stale_rate(n, w, r):.1%}")
N=3 W=1 R=1 R+W>N=False stale reads: 66.3%
N=3 W=2 R=1 R+W>N=False stale reads: 34.5%
N=3 W=2 R=2 R+W>N=True stale reads: 0.0%
N=3 W=3 R=1 R+W>N=True stale reads: 0.0%
N=5 W=3 R=3 R+W>N=True stale reads: 0.0%
The simulation writes a new version to only W random replicas, then reads from R random replicas. Whenever R + W > N, the stale rate drops to zero.
Common settings for N = 3:
- W=2, R=2: balanced; tolerates one slow or failed replica for both reads and writes.
- W=3, R=1: fast reads, but a write fails if any replica is down.
- W=1, R=1: fastest and most available, eventually consistent.
Real systems add repair mechanisms so replicas converge: read repair (fix stale replicas seen during a read), hinted handoff (another node holds writes for a down replica), and anti-entropy (background comparison using Merkle trees). And quorums alone aren’t fully linearizable in edge cases (concurrent writes, failed partial writes); systems that need that use consensus protocols such as Raft or Paxos.
Key takeaways
- CAP: during a partition, choose consistency (refuse) or availability (answer, maybe stale).
- PACELC: without a partition, you still trade latency for consistency.
- Choose consistency per feature: strong for money and locks, eventual for counters and feeds.
- With N replicas, R + W > N makes reads overlap the latest write.
Exercises
- Classify these as CP or AP and justify: seat booking, a “who’s online” indicator, a feature-flag service, a URL shortener redirect.
- Extend
quorum.pyso one replica is “down” (never written or read). Which (N, W, R) settings still succeed? - Explain in your own words why R + W > N guarantees overlap.
Quiz
- Why is “CA” not a realistic choice for a distributed database?
- With N = 5, what’s the smallest R if W = 3 and you want fresh reads?
- What does PACELC add to CAP?
Show answers
- Network partitions can’t be prevented in a distributed system, so you must decide what happens during one: give up C or give up A.
- R = 3 (3 + 3 = 6 > 5).
- The trade-off when there’s no partition: lower latency versus stronger consistency.