Lesson 7 of 15 Data and Storage

CAP Theorem, Consistency and Quorums

The CAP theorem explained properly, PACELC, strong vs eventual consistency, and quorum reads and writes (R + W > N) with a Python simulation.

35-45 min intermediate 0/15 lessons done
Course contents Lesson 7 of 15 · 0 done
On this page (8 sections)
  1. What you will learn
  2. CAP, stated carefully
  3. PACELC
  4. Consistency levels
  5. Quorums: tunable consistency
  6. Key takeaways
  7. Exercises
  8. Quiz

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:

LevelGuaranteeFeels like
Linearizable (strong)Every read sees the latest completed writeOne copy of the data
Sequential / causalEveryone sees causally related writes in the same orderReplies never appear before the question
Read-your-writesYou always see your own writesYour post shows up immediately for you
EventualIf writes stop, replicas convergeLikes 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

  1. Classify these as CP or AP and justify: seat booking, a “who’s online” indicator, a feature-flag service, a URL shortener redirect.
  2. Extend quorum.py so one replica is “down” (never written or read). Which (N, W, R) settings still succeed?
  3. Explain in your own words why R + W > N guarantees overlap.

Quiz

  1. Why is “CA” not a realistic choice for a distributed database?
  2. With N = 5, what’s the smallest R if W = 3 and you want fresh reads?
  3. What does PACELC add to CAP?
Show answers
  1. 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.
  2. R = 3 (3 + 3 = 6 > 5).
  3. The trade-off when there’s no partition: lower latency versus stronger consistency.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).