Consistency Models

The Single-Copy Illusion: What Linearizability Buys and What It Costs

Two replicas hold the counter visits. The API increments it, returns 7, and the very next request — a read on another replica — returns 6. Nothing crashed; the replication stream was simply 40 ms behind. From the client's seat the system violated causality: it observed a state from before an operation it was told had completed. A consistency model is the name you give to the guarantee that was broken, and choosing one means choosing which anomalies clients are allowed to see.

The strongest common model is linearizability: every operation appears to take effect instantaneously at some point between its invocation and its response, and all operations are ordered consistently with real time. It is the single-copy illusion — as if the replicated data were one object on one machine. Two consequences matter in design:

1. real-time ordering: if op A returns before op B starts, every client sees A before B
   (a completed write is immediately visible to all subsequent reads)
2. per-client order = global order: no client ever sees an order that another
   client's history contradicts

Linearizable objects are expensive because every operation must coordinate. A read must confirm it is not looking at a stale copy — typically by contacting a quorum or checking a leader lease — which means a network round trip on the read path. Raft-backed systems get linearizability from leader leases (Consensus Overview with Raft); Spanner buys it with TrueTime clock uncertainty and commit waits; Calvin and many Spanner-class databases pay with a global certification step. The performance claim to be able to defend: a linearizable read over a WAN costs at least the clock/lease round trip, so p99 is bounded below by RTT, not by your storage engine.

Below linearizability sits sequential consistency: all operations appear in some total order that respects each process's program order, but not necessarily real time. The difference is a one-line anomaly: with sequential consistency a read can observe a write that has not yet "happened" in wall-clock terms, as long as the order is globally consistent. Real systems: sequential consistency allows read-only replicas with lease-based caching; linearizability forbids serving a read from a replica that cannot prove freshness.

A practical tier list, because interviews ask for exactly this:

Model	Guarantee	Typical mechanism	Cost
Linearizable	single copy, real-time order	leader + quorum/lease reads, consensus commit	RTT on every op
Sequential	one global order, program order kept	lease/fencing, ordered commit	cheaper reads, real-time skew allowed
Causal	happens-before preserved	vector clocks / session guarantees	no global order, no leader required
Monotonic reads / writes	no time travel within a session	sticky replicas, session tokens	cheap, per-session only
Eventual	converges when writes stop	async replication, anti-entropy	any transient anomaly

The decision rule that sounds senior in an interview: buy the weakest model that makes every read meaningful. Inventory display tolerates monotonic reads; a uniqueness constraint needs linearizability on the check; a social feed tolerates eventual. Over-providing is not free bragging — it is latency and availability you gave away for a guarantee no user consumes.

Note where the illusion requires failure handling: if the leader's lease expires during a GC pause, it must stop serving linearizable reads the instant the lease lapses, or two clients see contradictory orders. That fencing discipline — never act on an authority you can no longer prove — is the same force that prevents split brain in failover (Replication Fundamentals).

Causal Consistency: Ordering What Must Be Ordered, and Nothing Else

A user comments on a post (c1), then replies to their own comment (c2). A friend loads the thread from a replica that received c2 but not c1. They now see a reply to a comment that does not exist. Every event is present eventually, yet the visible order is nonsense. Causal consistency fixes exactly this class of bug: operations that are causally related must be seen in that order by every client; operations that are unrelated may appear in any order.

The relation is happens-before, and it has three sources:

e1 → e2  if:
  1. e1 and e2 are in the same process and e1 executed first   (program order)
  2. e1's result was used to produce e2                        (data / read-your-write)
  3. e1's happened-before is communicated to e2's process      (message order)

If neither e1 → e2 nor e2 → e1, the events are CONCURRENT —
no consistency model owes them any relative order.

That third clause is what makes a distributed system work: causality propagates with data. When replica B applies a write that originated at A, it learns everything A had observed, so causal information rides along instead of requiring a global clock.

Encoding the relation is where the mechanisms come from. Vector clocks attach a per-node counter vector to each write; a receiver compares vectors to decide before, after, or concurrent — full causal history at the cost of an O(N) payload per record, plus conflict detection when concurrent writes meet. Dotted version vectors and versioned entries shrink this for real stores (Riak, Cassandra) by tracking only the causal context. Cheaper still, systems that do not need general causality implement session guarantees instead: read-your-writes, monotonic reads, monotonic writes, writes-follow-reads. Sticky routing plus a session token (the last seen version vector) delivers causal behavior within a session — enough for the comment thread — without coordinating across unrelated users.

What causal consistency buys you, precisely:

No cycles: a client can never see c2 before c1 if c2 was written after c1 was observed — the thread anomaly above becomes impossible.
No linearizable round trips: replication is asynchronous, so writes ack locally; availability survives partitions better than CP designs.
Less conflict than pure eventual: because causally ordered writes are never treated as concurrent, merges only have to resolve genuinely concurrent writes — fewer false conflicts than LWW over everything.

What it does not buy: a single global order for unrelated operations (two users liking different posts can be seen in either order, forever, on different replicas), and it does not stop lost updates on a read-modify-write unless the write itself carries a conditional (compare-and-set on the version). Causal consistency constrains visibility, not atomicity.

Systems worth naming: COPS (Facebook-derived, cluster-scoped causality with get-dependencies propagated to servers), Eiger (causal + strong when required), MongoDB's causal sessions (cluster time tokens), Cassandra's logged batches with tokens, and Neo4j/Redis-style session guarantees. Most production systems implement a hybrid: causal by default per session, escalating to quorum/linearizable for operations that must be globally true.

Interview framing: draw the three arrows of happens-before, show the comment anomaly, and explain that vector clocks cost O(N) while session tokens cost one header — then state clearly that causality does not replace transactions. Next you will price the whole ladder against partitions in CAP and PACELC Trade-offs.

Eventual Consistency Is a Promise About Tomorrow — Designing for the Divergence Today

Say eventual consistency precisely and it sounds weak: if no new writes occur, all replicas will eventually converge to the same value. Two things follow that teams routinely get wrong. First, "eventually" is unbounded — a partitioned replica can serve hours of stale reads before healing, and nothing in the definition limits the window. Second, convergence says nothing about which value wins; that is decided by your merge function, and an unspecified merge function is LWW by accident.

Eventual consistency is the right model for large classes of load, but only after you have enumerated the anomalies. The standard catalogue, each with its mechanism:

Anomaly	Scenario	Mechanism that removes it
Stale read	read returns a value overwritten 2 s ago	read-your-own-writes via session token; read from leader
Lost update	two replicas each apply `count + 1`, merge keeps one	conditional write (CAS on version), CRDT counter, or CRDT merge math
Cyclic anomaly	A sees `x=1,y=0`, B sees `x=0,y=1` for causally linked writes	causal consistency / vector clocks
Non-monotonic session	page 1 shows new posts, page 2 shows an older snapshot	monotonic reads with sticky replica or token
Zombie write	a "reverted" value reappears after merge	tombstones with garbage collection (removing a set element is a delete record, not an absent record)

The zombie-write row deserves elaboration because it is the classic OR-Set trap: in a grow-only set, removing an element and merging with a replica that still holds it resurrects the element. The fix is a delete marker (tombstone) or add-wins semantics with unique tags per add — and tombstones then create their own problem of unbounded growth, which is why Cassandra's tombstone GC is a real operational concern.

Convergence itself needs a delivery mechanism, and this is where eventual systems earn their reliability: anti-entropy. Read repair fixes divergences a client happens to notice; background Merkle-tree comparison propagates fixes nobody read (Replication Fundamentals covers the quorum side). Without one of these, an offline node rejoins and stays silently wrong — the system is not eventual, it is stuck.

There is also a boundary to respect: eventual consistency operates on replicas of one item; it says nothing about invariants spanning items. "No two seats sold to the same row" or "sum of transfers equals balance" cannot be protected by eventual replication of each row independently — you need a single-writer partition, a quorum-conditional write, or consensus for the invariant itself. A useful test in design review: name the invariant, then ask which consistency model protects it — if the answer is 'eventual', the invariant is not protected.

Practically, mature systems expose the dial instead of a single global setting: DynamoDB lets you request ConsistentRead: true on a specific read; Cassandra sets QUORUM per query (LOCAL_QUORUM for multi-region); MongoDB offers causal sessions on by default and majority read concern when needed. Your job as the architect is per-operation classification — mark each read/write with the weakest model that keeps its invariant intact — rather than declaring the whole system strong or eventual. That per-operation framing is exactly what the next topic formalizes: CAP and PACELC Trade-offs.

Flashcards

Question

Linearizability vs sequential consistency: the one difference to state first

Click to reveal answer

Answer

Linearizability additionally respects real time: if op A completed before op B started, every client must see A before B, so a completed write is instantly visible everywhere. Sequential consistency only requires one global order preserving each client's program order — a read may reflect a write that had not yet completed in wall-clock terms.

Question

Define happens-before and what causal consistency guarantees about it

Click to reveal answer

Answer

e1 → e2 when they share program order, e2 used e1's result, or e1 was communicated to e2's process; otherwise they are concurrent. Causal consistency requires every client to observe e1 before e2 whenever e1 → e2, while placing no order on concurrent events — no global clock needed, because causal context travels with the data (vector clocks, dotted version vectors, session tokens).

Question

What does eventual consistency guarantee — and what does it explicitly not?

Click to reveal answer

Answer

It guarantees convergence: once writes stop, replicas become identical (requiring repair mechanisms like read repair or Merkle anti-entropy to actually get there). It does not bound staleness, decide which conflicting value wins (your merge function does, often LWW by accident), or protect invariants that span multiple items — those need conditional writes, single-writer partitions, or consensus.

Question

Name the anomaly each mechanism fixes: session token, compare-and-set, vector clock, tombstone

Click to reveal answer

Answer

Session token (last-seen version) fixes read-your-own-writes and non-monotonic reads within a session. Compare-and-set on a version prevents lost updates on read-modify-write. Vector clocks detect causal vs concurrent relationships, eliminating cycles. Tombstones (or add-wins tags) stop removed elements from being resurrected by a merge with a stale replica.

Question

Why does a linearizable read cost a network round trip even when the data is local?

Click to reveal answer

Answer

The reader must prove its copy is the freshest, not merely that it exists: it has to check with a quorum, renew/validate a leader lease, or consult the leader — all of which are network operations. Serving from a local replica without that check risks returning a value a completed write already superseded, which is exactly the linearizability violation the model forbids.

Revision Notes

Key Takeaways

1. A consistency model is a list of permitted anomalies — choose it by naming which anomalies each read can tolerate, not by brand loyalty to 'strong'
2. Linearizability adds real-time ordering on top of sequential consistency, and that single addition is why it needs a lease or quorum round trip on the read path
3. Causality is transitive and travels with data, so causal consistency orders only what must be ordered and needs neither a global clock nor a leader
4. Eventual consistency promises convergence, not freshness or a correct winner — the merge function decides the winner and repair mechanisms make convergence real
5. Invariants that span multiple items are outside what replication of each item can protect; they need conditional writes or consensus

Interview Tips

• "What is linearizability?" — the single-copy illusion with a real-time constraint; then immediately say what it costs (every op coordinates) and give one use case that needs it (uniqueness check, lock, counter)
• "Explain causal consistency with an example" — the comment-reply anomaly, the three happens-before arrows, and how causality rides along with the data (vector clock or session token) instead of a global clock
• "Two counters incremented concurrently — why 6 instead of 7?" — name lost update, then two fixes: CAS-with-retry or a CRDT counter whose merge sums deltas; mention LWW as the failure mode
• "How do you decide the consistency level for a feature?" — per-operation classification against named invariants: strongest for cross-item invariants, session guarantees for user flows, eventual for display-only data

Cheat Sheet