S070 · CAP & PACELC — the Actual Trade-Offs

Module M08: Distributed Systems · Session 70 of 130 · Track: SYS ⚖️

What you'll be able to do after this session

• Explain CAP & PACELC to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S042 — Transactions & ACID — Isolation Levels, MVCC

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · CAP Theorem Explained (ByteByteGo) — the sharpest 8-minute explainer, correctly noting that "pick 2 of 3" is a lie.
• 🎥 Deep dive (30–60 min) · Distributed Systems 1.1: CAP + FLP (Martin Kleppmann, Cambridge) — the author of DDIA teaching it properly.
• 🎥 Hands-on demo (10–20 min) · Consistency Models Visualised (Jepsen / Aphyr talk excerpt) — see how Jepsen breaks "consistent" databases in real tests.
• 📖 Canonical article · Daniel Abadi — Problems with CAP, and Yahoo's little-known NoSQL system (2010) — the essay that introduced PACELC.
• 📖 Book chapter / tutorial · Designing Data-Intensive Applications — Ch. 9 "Consistency and Consensus" (Kleppmann) — the canonical modern treatment.
• 📖 Engineering blog · Jepsen analyses (various DBs) — Kyle Kingsbury's legendary tear-downs of Cassandra, MongoDB, CockroachDB, etc. Pick any one.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Beyond the meme, what CAP really means.

You have a database, and you want to run it in more than one data centre for reliability. The moment you have two copies of the data, you have a problem: what happens when a write hits copy A but not copy B, and then the network between them breaks? Do you (a) refuse reads on copy B until the network heals, or (b) let both copies keep serving traffic and reconcile later? You cannot have both "always available" and "every read sees the latest write" during a network partition. Physics won't let you.

That's the essence of the CAP theorem (Eric Brewer, 2000, formally proved by Gilbert & Lynch, 2002). Given three properties — Consistency (every read sees the latest write), Availability (every request gets a response), Partition tolerance (system keeps working when messages between nodes are dropped) — a distributed system can guarantee at most two of three during a partition. Since in the real world networks do partition (routers die, cables get cut, GC pauses look like partitions), you don't really get to "give up P". The real choice is CP vs AP: during a partition, do you refuse to serve (CP: PostgreSQL primary/replica with synchronous replication, HBase, MongoDB configured strict) or serve possibly-stale data (AP: Cassandra, DynamoDB, Riak)?

But that's only the partition case. The rest of the time — 99.99% of it! — the interesting trade-off is latency vs consistency. This is what PACELC (Daniel Abadi, 2010) captures: If a Partition, Availability vs Consistency; Else, Latency vs Consistency. A system like Cassandra is AP/EL — favours availability under partition, favours latency the rest of the time (weak consistency for fast reads). A system like BigTable/Spanner is CP/EC — always consistent, at latency cost. Two AP databases can differ hugely on the ELSE-clause; PACELC gives you the full picture.

Forever-gotcha: "C" in CAP is not the C in ACID. CAP's C is linearizability (a very strong notion: reads see the latest write globally, instantaneously). ACID's C is integrity constraints (no foreign-key violation, no negative balance). A DB can be ACID and AP at the same time. Don't let the letters trick you into thinking Cassandra "isn't consistent" — it just isn't linearizable, and it is eventually consistent.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Real systems classified (PACELC):

Consistency ladder — from weakest to strongest:

Worked example — a partition in a 3-node Cassandra cluster:

1. Cluster has nodes N1, N2, N3. Key user:42 is replicated to all three.
2. Client A writes name=Alice at consistency level ONE. It hits N1, N1 acks immediately, N2/N3 will hear about it soon.
3. Network between N1 and partitions.
4. Client B (talking to N2) reads user:42 at ONE. Sees old value name=Bob. Stale read — but the system is available. This is the "PA/EL" trade-off in action.
5. Network heals. Cassandra's hinted-handoff / read-repair converges the value. Timestamps break ties (last-write-wins).
6. If instead the client had used QUORUM reads and writes, step 4 would have blocked until 2 of 3 nodes could be reached — that's effectively shifting Cassandra toward CP on that query.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

We'll use a single-machine Cassandra Docker container to see eventual consistency, tunable consistency levels, and how they change the picture. If Cassandra is heavy, the same principles apply to Redis Cluster or Postgres async replicas.

# Run a 3-node Cassandra cluster with docker-compose
mkdir cap-demo && cd cap-demo
cat > docker-compose.yml <<'EOF'
version: "3"
services:
  n1:
    image: cassandra:4.1
    environment:
      - CASSANDRA_CLUSTER_NAME=demo
      - CASSANDRA_SEEDS=n1
      - MAX_HEAP_SIZE=512M
      - HEAP_NEWSIZE=128M
    ports: ["9042:9042"]
  n2:
    image: cassandra:4.1
    environment:
      - CASSANDRA_CLUSTER_NAME=demo
      - CASSANDRA_SEEDS=n1
      - MAX_HEAP_SIZE=512M
      - HEAP_NEWSIZE=128M
    depends_on: [n1]
  n3:
    image: cassandra:4.1
    environment:
      - CASSANDRA_CLUSTER_NAME=demo
      - CASSANDRA_SEEDS=n1
      - MAX_HEAP_SIZE=512M
      - HEAP_NEWSIZE=128M
    depends_on: [n1]
EOF
docker compose up -d
echo "Wait ~90s for cluster to form…"
sleep 90
docker compose exec n1 nodetool status
 
# Create a keyspace with RF=3 and a table
docker compose exec n1 cqlsh -e "
CREATE KEYSPACE IF NOT EXISTS demo
  WITH REPLICATION = {'class':'SimpleStrategy','replication_factor':3};
USE demo;
CREATE TABLE IF NOT EXISTS users (id int PRIMARY KEY, name text);
"
 
# Write at CL=ONE, read at CL=ONE
docker compose exec n1 cqlsh -e "
CONSISTENCY ONE;
INSERT INTO demo.users (id, name) VALUES (42, 'Alice');
SELECT * FROM demo.users WHERE id=42;
"
 
# Simulate a partition: cut n2 off from n1 & n3
docker network disconnect cap-demo_default cap-demo-n2-1 2>/dev/null ||   docker network disconnect cap-demo_default $(docker ps -q --filter name=n2)
 
# Write at CL=ONE (n1 alone answers) — succeeds
docker compose exec n1 cqlsh -e "
CONSISTENCY ONE;
UPDATE demo.users SET name='Bob' WHERE id=42;
SELECT * FROM demo.users WHERE id=42;
"
 
# Read from n2 while partitioned — get the stale value (AP behaviour)
docker compose exec n2 cqlsh -e "
CONSISTENCY ONE;
SELECT * FROM demo.users WHERE id=42;
"
 
# Now try CL=QUORUM writes on n1 — needs 2/3, still succeeds (n1+n3)
docker compose exec n1 cqlsh -e "
CONSISTENCY QUORUM;
UPDATE demo.users SET name='Carol' WHERE id=42;
"
 
# But CL=ALL should fail (n2 unreachable)
docker compose exec n1 cqlsh -e "
CONSISTENCY ALL;
UPDATE demo.users SET name='Dave' WHERE id=42;
" || echo "CL=ALL correctly failed under partition (CP behaviour)"
 
# Heal the partition
docker network connect cap-demo_default $(docker ps -q --filter name=n2)
sleep 10
docker compose exec n2 cqlsh -e "
CONSISTENCY ONE;
SELECT * FROM demo.users WHERE id=42;
"  # eventually converges to 'Carol'
 
docker compose down -v

Checklist — what to observe:

1. nodetool status shows 3 UN (Up/Normal) nodes when healthy. That means the cluster formed.
2. CONSISTENCY ONE write on n1 succeeds instantly — n1 alone acknowledged. Fast, AP-flavoured.
3. During partition, n2 returns the stale value at ONE. It never blocks. This is availability winning over consistency.
4. CONSISTENCY QUORUM still works during a 1-node partition because 2 of 3 nodes are reachable. Increase to ALL and it fails — that's CP behaviour on demand.
5. After healing, hinted handoff replays queued writes to n2, and eventually all replicas agree — the "eventually" in eventual consistency.

Try this modification: rerun the whole test with RF=3, CL=QUORUM for both reads and writes. You now get linearizable-ish behaviour (R + W > N), at the cost of higher latency and no availability during a 2-node partition. This is the PACELC trade-off you actually tune in production.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

War story #1 — MongoDB and lost writes. In early versions with default write-concern w=1, a primary would ack a write, then crash before replicating. Failover to a secondary lost the write. Jepsen tests exposed this repeatedly. Modern default: w=majority + readConcern=majority. Users switching to strict settings often didn't know they had a data-loss window.

War story #2 — Cassandra "last-write-wins" surprise. LWW resolves conflicts by timestamp. If two writes happen within the same millisecond (or the clocks are skewed), one silently disappears. Twitter famously ran into this with following counts. Fix: design data models to be commutative (CRDTs — counters, sets, LWW-registers with client-supplied logical clocks). Or move that data to a CP store.

War story #3 — the sync-replica outage. A PostgreSQL setup with synchronous replication guarantees no data loss. But it also means: if the replica dies, the primary can't commit any new writes. Under load spike + brief network hiccup, the "highly available" DB stopped serving writes because it was too consistent. Rule: know exactly what "sync" means in your DB's docs; often you want quorum, not strict-sync.

Common gotchas & how top teams handle them:

• Read-your-writes without linearizability. After a POST, the immediate GET goes to a replica and returns the old value. Users see "I just saved it, why is it gone?". Fix: route reads to the primary for a short window (session stickiness) or add causality tokens.
• Time is a lie. NTP-synced clocks can drift 10-100 ms. Anything using "server timestamp" for ordering has bugs waiting to happen. Google Spanner solved this with TrueTime (uncertainty-bounded clocks); most teams tolerate the mess.
• Multi-region writes. Cross-region latency (100+ ms) means any strong consistency = 100+ ms per write. Real global apps segment users by region (each user writes to their home region) or accept eventual consistency (DynamoDB Global Tables).
• Read-repair storms. Cassandra's background repair can 3x your read latency during business hours. Tune to run off-peak.
• Not everything is a CAP problem. A single-region single-primary Postgres is not distributed enough for CAP to matter. Only when you have replicas, multi-primary, or sharding does the trade-off bite.

The industry has moved to a nuanced view: modern databases (Spanner, CockroachDB, FoundationDB, YugabyteDB) push consistency + availability further via clever consensus + clocks. Meanwhile, apps like S3 quietly moved from "eventually consistent" to "strongly consistent" once engineering caught up. The Kleppmann book (DDIA) is the modern canon and every senior engineer should have read Chapters 5-9 twice.

(e) Quiz + exercise · 10 min

1. State CAP correctly — including the crucial "during a partition" caveat that popular explanations often skip.
2. What does PACELC add beyond CAP, and why does it matter for latency-sensitive apps?
3. Give a real example of when eventual consistency is fine, and one where it's dangerous.
4. Why is CAP's "C" different from ACID's "C"?
5. Cassandra with R + W > N gives you strong-ish consistency. What are you giving up to get it?

Stretch problem (connects to S063 — Caching): a CDN cache is a distributed system too. Classify a typical CDN's behaviour in PACELC terms: what happens on partition (say, edge cache can't reach origin)? What happens in the normal case (edge serves stale-while-revalidate)? Which of the consistency-ladder levels from the Visual section best describes a CDN's guarantee to end users? ~10 lines.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is CAP & PACELC? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S071): Replication — Leader/Follower, Multi-Leader, Leaderless
• Previous (S069): Infrastructure as Code — Terraform / Bicep Basics
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.