12. Consistency Models, CAP, PACELC

In a distributed system, "consistency" isn't binary. It's a spectrum. Knowing where your system sits — and where you want it to sit — is core to every design.

12.1 The consistency spectrum

From strongest to weakest:

Linearizability (strict consistency)
Sequential consistency
Causal consistency
Read-your-writes
Monotonic reads
Eventual consistency

Stronger = easier to reason about for the app, harder/slower to implement.

Linearizability

Every operation appears to happen instantaneously, at some point between its start and finish, and all clients see the same global order.

Example: if T1 writes X=1 and finishes, every read started after must see X=1 (or a later value).

The "C" in CAP is linearizability.

Examples of linearizable systems:

Single-leader DB if you read from the leader
Spanner (uses TrueTime)
etcd, ZooKeeper
Most consensus-backed systems

Cost: writes need consensus (Paxos/Raft); reads either go to the leader or use a quorum.

Sequential consistency

All operations appear in some total order that respects each client's program order. Weaker than linearizability — clients may not agree on real-time order between unrelated ops.

Causal consistency

Operations causally related are seen in causal order; concurrent (independent) ops can be seen in any order. Captures the intuition: "if A happened-before B, everyone sees A first."

Implementations track causality via vector clocks (chapter 14).

Read-your-writes

After you write X=1, your subsequent reads see X=1. Other clients may not yet.

Implemented by: routing your reads to leader for a window post-write, or session tokens (LSN-based).

Monotonic reads

You don't go back in time. If you read X=2, your next read sees X=2 or later, not X=1.

Implemented by: sticky session — same client, same replica.

Eventual consistency

"All replicas converge to the same value if writes stop." Says nothing about when. The weakest useful guarantee. Default in Cassandra (without quorum), DynamoDB (default reads), most CDN caches.

12.2 The CAP theorem

Eric Brewer, 2000. Formalized 2002. Cannot have all three of: Consistency, Availability, Partition tolerance.

But this framing is misleading. Real systems must tolerate partitions (networks fail) — so the real choice is CP vs AP during a partition.

CP: refuse writes (or some operations) on the minority side of a partition to keep consistency. Examples: ZooKeeper, etcd, single-leader Postgres on the minority side.
AP: keep accepting writes everywhere; resolve conflicts later. Examples: Dynamo, Cassandra (with weak quorum), CouchDB.

When there is no partition (most of the time), most systems are both consistent and available. CAP is a partial-failure framing.

Common misuses

"We chose AP over CP." → Probably true 1% of the time (when partitioned). The real question is your normal-case consistency level.
"MongoDB is CP, Cassandra is AP." → Imprecise; depends on configuration.

What CAP actually means at design time

Every cross-node operation has a failure mode.
You must decide: under partial failure, do I prefer to refuse the request (preserve C) or serve a possibly-stale answer (preserve A)?

For a banking app: refuse (CP). For a social feed: serve (AP).

12.3 PACELC

Daniel Abadi's improvement on CAP:

If there is a Partition (P), trade off Availability (A) vs Consistency (C); else (E), trade off Latency (L) vs Consistency (C).

Two trade-offs, not one. Even when the network is fine, you're trading latency for consistency (a quorum read is slower than a single replica read).

System	Partition	Normal
Spanner	PC (refuses writes)	EC (waits for TrueTime)
Dynamo	PA (eventual)	EL (low latency, eventual)
Single-leader Postgres	PC (minority can't write)	EC (synchronous to leader)
Cassandra (QUORUM)	PA / PC depending on quorum reach	EL or EC depending on quorum

PACELC is the better mental model.

12.4 Why "strong consistency" is expensive

Linearizability requires either:

A single sequencer (leader) that all writes go through. Limits throughput; failover is risky.
Consensus on every write (Raft/Paxos). Round trips per write.
Synchronous physical clocks (TrueTime / Spanner). Need uncertainty bound; wait it out.

Each costs latency. In wide-area networks (50+ ms RTT), strong consistency is a huge tax.

Spanner's trick

TrueTime is an API: now() → [earliest, latest]. The uncertainty is bounded (~1-7 ms in Google DCs, via GPS + atomic clocks).

For a write at TT=t, Spanner waits out the uncertainty before acknowledging — guaranteeing that any later transaction sees this write. This makes globally consistent reads possible without coordination.

Cost: every write pays "commit wait" of ~uncertainty (~7 ms). Worth it for global consistency.

12.5 Consistency at different layers

Don't conflate. A system can be:

Strongly consistent at the DB layer (Postgres) but eventually consistent at the cache layer (Redis with TTL) → app sees eventual consistency overall.
Eventually consistent at the replica layer (Cassandra) but linearizable at the partition level (Cassandra single-row CAS via Paxos).

Always ask: "consistency of what?"

12.6 Choosing your level

Default: Read Committed (DB) + cache TTL of 30-300s + accept eventual consistency at boundaries.

Strengthen when:

Money / inventory / quotas: serializable transactions, no caching of mutable values, idempotency keys.
Authorization / sessions: linearizable reads (or a short cache TTL with explicit invalidation).
User-visible "did I save it?": read-your-writes.

Weaken when:

Likes, view counts, popularity rankings: eventual is fine.
Search index, recommendations: eventual is fine (lag of seconds to minutes).
Analytics: eventual is fine (lag of minutes to hours).

12.7 Anti-patterns

Banking on BEGIN; ... COMMIT; across multiple databases without a distributed transaction. Doesn't atomic; you've reinvented dual-write inconsistency.
Read-your-writes without thought: app reads from a follower right after writing to leader, sees old data, "is this a bug?"
Trusting timestamps for ordering without a clock model: physical clocks drift; logical clocks needed (chapter 14).
Strong consistency where eventual is fine: huge performance loss for no business benefit.

12.8 The CAP/PACELC interview answer

When asked "is this CP or AP?":

Reframe as PACELC.
State normal case trade-off (latency vs consistency).
State partition case trade-off (availability vs consistency).
Justify per-operation: "writes go through Raft for linearizability; reads of the home feed are served from cache (eventual)."

Junior candidates pick a label. Senior candidates pick per operation and explain why.

12.9 Strong eventual consistency (CRDTs)

Special case: data structures that, regardless of merge order, converge to the same value. Eventual consistency + determinism = "strong" eventual consistency.

Examples:

G-Counter (grow-only counter): each replica increments its own slot; merge = max per slot, sum across.
LWW-Register (last-writer-wins with timestamps).
OR-Set (observed-remove set).

Used in: Riak (CRDT data types), Redis CRDT module, Yjs / Automerge (collaborative editing).

When CRDTs work, they're magic. They don't fit every problem.

12.10 Linearizability vs serializability

Often conflated. They're different.

Linearizability = consistency of a single object across nodes. Real-time order matters.
Serializability = isolation of transactions. Order is some serial order; doesn't have to match real-time.
Strict serializability = both.

A DB can be serializable but not linearizable (read-only transactions might see stale snapshot). Spanner provides strict serializability.

Key takeaways

Consistency is a spectrum from linearizable down to eventual. Pick per-operation.
CAP says: in a partition, choose C or A. PACELC says: in the normal case, choose C or L.
Strong consistency in a global system costs latency. Spanner's TrueTime is the elegant exception.
Default eventual + cache; strengthen for money, auth, sessions.
"Linearizability" and "serializability" mean different things. Both matter; conflate at peril.