Consistency Models Beyond CAP: Linearizability, Causal, and Session Guarantees

Somewhere between "CAP theorem" flashcards and production incidents lies a vocabulary most engineers never acquire: the actual spectrum of consistency models. It matters because the two poles are both lies — nobody runs a fully linearizable system for everything (too slow), and nobody means "anything goes" by eventual (your users would riot). Real systems live in the middle, and the middle has precise names. Interviews at the staff level increasingly probe exactly this: not "strong or eventual?" but "which guarantee does this operation need, and what does it cost?"

The spectrum, top to bottom

Linearizability (single-object "strong"): every operation appears to take effect atomically at some instant between its start and end, consistent with real time. If your write completes and then anyone starts a read, they see it. The cost is coordination on the critical path — consensus rounds or leader reads (Raft/Paxos), cross-region round trips if replicas span regions. (Distinct from serializability, which orders multi-object transactions but says nothing about real time; Spanner's "external consistency" = both at once.)

Sequential consistency: all clients see operations in the same order, but that order need not match real time. Weaker than it sounds useful — the gap between "one agreed order" and "the real-time order" is exactly the anomaly window most products can't articulate, so in practice you're choosing between linearizable and the causal family.

Causal consistency: operations that are causally related — you read X, then wrote Y — are seen in that order by everyone; concurrent operations may be seen in different orders. This is the sweet spot the industry quietly converged on for geo-replicated data: it's the strongest model achievable without giving up availability during partitions (a real theorem, not folklore), and it matches human intuition — a reply never appears before the comment it answers.

Eventual consistency: replicas converge if writes stop. It is a liveness promise with no safety content — it forbids nothing at any moment. Every useful "eventually consistent" system actually ships something stronger and unnamed; your job is to name it.

Session guarantees: the practical middle

The four session guarantees (from the Bayou work) are how causal-ish behavior gets delivered per-client, and they're the vocabulary that most directly fixes real bugs:

Guarantee	Promise	The bug it kills
Read-your-writes	Your reads see your own earlier writes	Post a comment, refresh, it's gone
Monotonic reads	Your reads never go backwards	Inbox shows 5 messages, then 3
Monotonic writes	Your writes apply in the order you issued them	Profile update #2 lost to replayed #1
Writes-follow-reads	Writes causally after what you read	Reply ordered before the post you replied to

Implementation is unglamorous and cheap: session tokens carrying version vectors/LSNs — client presents the last version it wrote/read; the serving replica either has caught up to it or the request waits/routes elsewhere. Sticky routing (pin a session to a replica) gets you most of it for free until failover, which is why "sticky + token fallback" is the standard production recipe. This is the answer to the most common consistency bug in industry — read-after-write against a lagging replica — and it costs microseconds, not consensus.

Choosing per operation

The senior framing: consistency is not a system property, it's an operation property, and one product uses several models at once.

uniqueness claims (username, seat, payment)  -> linearizable (CAS on a leader)
social graph, comments, likes                -> causal + session guarantees
counters, view counts, presence              -> eventual + convergence (CRDT/LWW)
analytics reads                              -> snapshot at a timestamp (stale but consistent)

Two adjacent tools worth naming: bounded staleness (reads lag by at most T seconds/K versions — an SLA on inconsistency, what Azure Cosmos DB sells) for "eventual, but promise me a bound"; and snapshot reads — a consistent view that is allowed to be old, which is what most dashboards actually need instead of freshness.

Cost intuition to close the loop: linearizability ≈ a quorum/leader round-trip per operation (and unavailability for the minority side of a partition — that's where CAP actually bites, one row of your API at a time, not "the system"); causal ≈ metadata propagation (vectors/timestamps) with local reads; session ≈ token plumbing; eventual ≈ free until the anomaly bill arrives as a support ticket.

Interview probe	Answer sketch
"We need strong consistency everywhere"	Translate to operations; usually 2-3 truly need linearizable CAS, the rest wants session guarantees — 100× cheaper
Read-your-writes across devices?	Session tokens don't travel between your phone and laptop — you need causal with per-user vectors, or route the user's reads to their write region
Quorums R+W>N give linearizability?	Not by themselves (sloppy quorums, no read-repair ordering) — needs read-repair-before-return or leader leases; cite Dynamo's design as intentionally weaker
How do you test this?	Jepsen-style: record operation histories, check against the model (linearizability checking is NP-hard in general but tractable per-key) — anomalies are found, not reasoned away

The one-sentence takeaway: "strong vs eventual" compresses a five-notch dial into a coin flip — and the two notches that matter most in practice, causal and session guarantees, are the ones the flashcards skip.