Consistency models & CAP / PACELC
Lesson 06 made copies. Now the hard question: when a client reads X, which of the several values floating across your replicas is it allowed to see — and what does pinning that answer down cost you in latency and availability?
The instant data is replicated (08) or partitioned (07), "the value of X" stops being a single fact. Replica A may have committed X=5 while replica B still serves X=4 because the write is in flight. A consistency model is the contract that tells a reader which of those in-flight values it may observe. Stronger contracts behave like a single machine and are trivial to reason about — but they demand coordination across replicas, and coordination is latency and lost availability. It is a continuous spectrum, not a binary "consistent vs. not."
1 · Why there is more than one value at all
Picture three replicas of a key X currently holding 4. A client issues write(X,5). The leader applies it locally at t=0, then ships the update to followers over a network with one-way delay ≈ 0.5–50 ms (LAN to cross-region). For that window, a read can legitimately return 4 or 5 depending on which replica answers. There is no physics that forces one answer; the only thing that constrains the read is the contract you chose.
possible reads during propagation = { last value, any value at or after the write started }
Every consistency model is just a different rule for narrowing that set. Linearizability narrows it to exactly one (the latest). Eventual consistency barely narrows it at all. The cost of narrowing is paid in round-trips.
2 · The consistency ladder
Read this top-to-bottom as strong / slow / coordinated → weak / fast / available. "Strong consistency" colloquially means linearizable; everything below it relaxes some guarantee to buy latency or availability.
| Model | Guarantees | Costs | Concrete example |
|---|---|---|---|
| Linearizability (strong) |
Every read sees the latest completed write, in real-time order. The system behaves as one copy on one machine. | Read & write paths need cross-replica coordination (quorum / leader confirm). Highest latency; cannot serve from a lone stale replica. | "Did my payment go through?", unique-username claim, distributed lock, leader election. |
| Sequential | One global order that respects each client's own program order — but not necessarily wall-clock/real-time order. | Still needs agreement on a single order; a write may appear "late" vs. real time but never out of a client's own sequence. | Replicated state machine where total order matters but external timing does not. |
| Causal | Operations that are causally related (A happened-before B) are seen in that order by everyone; concurrent ops may be ordered differently per replica. | Track causality (vector clocks / dependencies). The strongest model still achievable while staying available under partition. | Comment threads (reply never appears before its parent), collaborative editing. |
| Session (RYW / monotonic / consistent-prefix) |
Within one client's session: you read your own writes; reads never go backwards; you never see writes out of submission order. | Cheap — sticky routing or a client-held version token. Fixes the jarring anomalies from 06 without global coordination. | "I edited my bio and it reverted" / "my post vanished on refresh" fixes. |
| Eventual (weak) |
If writes stop, all replicas converge to the same value. A read may return any recent value meanwhile. | Cheapest, most available — but offers the fewest guarantees; readers can see stale or non-monotonic values. | Like-counts, view counts, feed ordering, DNS, cached profile data. |
Client-1 issues write(x,1) and the write returns. Now client-2 reads x.
- Linearizable: because client-1's write completed before client-2's read began, the read must return
1— real-time order is respected, as if there were one copy on one machine. - Sequential: all clients only agree on some single order of operations, which need not match wall-clock. The read is permitted to fall before client-1's write in that agreed order, so client-2 might still read the old value for a while — even though, by the clock on the wall, the write already finished.
The difference is precisely whether real-time order across different clients is honoured.
These are distributed consistency models — about which replica's value a read may see. Their single-node cousins are transaction isolation levels (read-committed, snapshot, serializable), which are about how concurrent transactions on one database interleave. Newcomers conflate the two; they answer different questions and compose independently.
3 · CAP, stated precisely (and the lazy version debunked)
The folklore — "pick 2 of 3: Consistency, Availability, Partition-tolerance" — is wrong in a way that misleads design decisions. Pin the terms down:
- C = linearizability specifically (not "data integrity," not "ACID").
- A = every non-failing node returns a non-error response.
- P = the system keeps operating despite the network dropping arbitrary messages between nodes.
Here is the correction: P is not a choice. Real networks partition — NICs flap, switches reboot, cross-region links drop packets. A distributed system will experience partitions, so you cannot "give up P." What CAP actually says is narrow and conditional:
During a partition, the two sides cannot coordinate, so you must choose: keep C (the minority/uncertain side refuses or errors so it never returns a stale answer) or keep A (every side keeps answering with possibly-stale data and you reconcile later). It is a choice made only when partitioned, not a permanent "2 of 3."
4 · PACELC — the refinement that actually guides design
CAP only describes failure. PACELC (Abadi) adds the case that dominates your uptime — normal operation:
if (Partition) then choose A or C ELSE choose L or C
The "ELSE" is the load-bearing part. Even with nothing broken, a linearizable read must take a quorum round-trip (or confirm with the leader) to prove it is not stale. So strong consistency taxes the happy path too — not just the rare partition. You trade Latency against Consistency every single request.
| System | Partition behavior | Normal behavior | Class |
|---|---|---|---|
| etcd / ZooKeeper / Spanner | refuse on minority (consistent) | pay quorum latency for consistency | PC/EC |
| Cassandra / Dynamo (default) | stay available (stale) | serve local for low latency | PA/EL |
| MongoDB (majority writes) | refuse on minority | tunable; default leans latency | PC/EL |
| Cassandra at QUORUM R+W>N | refuse if quorum unreachable | pay quorum latency | PC/EC |
Note the last two rows: PACELC class is configurable per query, not a fixed property of the database brand. Which leads to the senior move.
5 · The senior move: choose consistency per operation
Junior framing: "pick a CP database or an AP database." Staff framing: most products need both, on different fields, in the same request. Tag each operation by what an anomaly would cost in money or trust:
Buying strong-ish reads with quorums (tie to 06)
06 gave you the lever: with N replicas, write to W and read from R, then
W + R > N ⟹ read and write quorums overlap by ≥ 1 ⟹ a read sees the latest write
With N=3, choosing W=2, R=2 guarantees overlap and gives near-linearizable single-key reads — at the cost of waiting for 2 replicas on both paths (the EC tax). Drop to R=1 and reads are local and fast but may be stale (EL). The quorum knob is the PACELC L-vs-C dial, per query.
The canonical “choose consistency per request” API is DynamoDB’s ConsistentRead=true flag: set it on the reads that must be fresh (and pay the latency), leave it off for the cheap eventual reads — the same operation-by-operation decision, exposed right in the request. Designing such per-request knobs into your own API is an 03 concern.
CRDTs: convergence without coordination
For certain data types you can have AP and conflict-free convergence: a CRDT (counters, grow-only sets, last-writer-wins registers) defines a merge that is commutative, associative, and idempotent, so replicas that received the same set of updates in any order reach the same state. A like-count as a PN-counter never needs a lock and never loses an increment under partition. This is how you get cheap availability without the "lost update" anomaly — for the subset of operations that fit a CRDT.
And forward to 08: how do you actually implement a linearizable write across replicas? You run a consensus protocol (Raft / Paxos) to agree on one order. CAP/PACELC tell you when to pay for that; 08 is the machinery that delivers it.
Three replicas, one per region, inter-region one-way delay ≈ 30 ms. A client in region 1 reads a key.
- Eventual (R=1, local): answer from the local replica — ≈ 1 ms. May be ~30 ms stale.
- Linearizable (R=2 quorum, leader in region 2): request must reach a second replica and back — ≈ 30 + 30 = 60 ms added. ~60× slower, but guaranteed fresh.
That 60 ms is paid on every consistent read, partition or not — the "ELSE" of PACELC made concrete. If the balance must be correct, you pay it; if it is a like-count, paying it is malpractice.
6 · Model + partition explorer
Slide along the ladder and toggle a partition. Watch how relative read-latency, availability on the minority side, and the "behaves like one machine?" flag move together — and read the diagnosis for the anomaly prevented, the cost, and a fitting use case.
Interview prompts you should be ready for
- State CAP precisely and explain why "pick 2 of 3" is misleading. (senior answer: C is linearizability, A is every non-failing node answers, P is tolerating dropped messages. P is not optional — networks partition — so the real statement is conditional: during a partition you choose C or A; the rest of the time CAP says nothing. PACELC fills that gap.)
- What does PACELC add, and why is the "ELSE" the important half? (senior answer: it covers normal operation, which is >99% of uptime. A linearizable read needs a quorum round-trip even with nothing broken, so strong consistency is a latency tax on the happy path, not just a partition behavior. PC/EC vs PA/EL classifies a system on both axes.)
- Difference between linearizable, sequential, and causal consistency? (senior answer: linearizable = single global order matching real time; sequential = single global order respecting each client's program order but not wall clock; causal = only causally-related ops are ordered, concurrent ops may differ. Causal is the strongest you can keep while staying available under partition.)
- A user edits their profile, refreshes, and sees the old value. Which guarantee fixes it, cheaply? (senior answer: read-your-writes — a session guarantee. Achieve it with sticky routing to the replica that took the write, or a client-held version token the read must meet. No global coordination needed; this is the cheap rung, not full linearizability.)
- How do quorums relate to CAP/PACELC? (senior answer: W+R>N forces read/write quorums to overlap, giving near-linearizable single-key reads at the cost of waiting on multiple replicas — that wait is the EC/PC latency price. R=1 is local and fast but stale (EL/PA). The quorum config is literally the per-query L-vs-C dial.)
- When is eventual consistency the right answer? (senior answer: when a stale or out-of-order read costs nothing in money or trust — like-counts, view counts, feed ranking, DNS, cached bios. Pair with a CRDT (e.g. PN-counter) to get convergence without lost updates, and avoid paying any coordination latency.)
- Design the consistency model for a money-transfer feature. (senior answer: per-operation. The debit/credit and the idempotency/uniqueness check are linearizable (consensus-backed, refuse on partition — CP); the transaction-history feed and notification counters can be eventual. Don't make the whole system CP to protect one field.)
- Why does a CP system become unavailable on the minority side during a partition? (senior answer: to stay linearizable it must never return a value it can't prove is latest. The minority can't reach a quorum, so it can't prove freshness, so it must error rather than risk a stale answer. Availability is sacrificed deliberately to preserve correctness.)
Consistency is a spectrum of contracts about which in-flight value a read may see, and stronger contracts cost coordination = latency + lost availability. CAP is a conditional choice during partitions only; PACELC reminds you that strong consistency also taxes the happy path. The staff-level move is to choose the weakest rung that still satisfies each operation — linearizable for balances and uniqueness, sessions to kill replication-lag anomalies, eventual + CRDTs for counts — and use the W+R>N quorum knob as the per-query dial between latency and freshness. Consensus (10) is how you actually buy the linearizable rung.