Consistency Deep Dive: Linearizability, Serializability, and the Spectrum Between

TL;DR: "Strong consistency" is a marketing phrase. Replace it with the precise guarantee: linearizable (single-object, real-time ordered), serializable (multi-object transactions equivalent to some serial order), or strict serializable (both at once, what Spanner calls "external consistency")^[1][2]. Most OLTP workloads do fine on snapshot isolation, but it lets through write skew^[3]. Tune consistency per operation, not per database. Modern systems (Spanner stale reads, CockroachDB AS OF SYSTEM TIME, DynamoDB per-request read modes) let you pay only for the guarantee each query actually needs.

Learning Objectives#

After this module, you will be able to:

• Distinguish serializability from linearizability and explain why the combination has a name
• Identify write skew, lost updates, and phantoms across transaction isolation levels
• Pick an isolation level per operation, not per database
• Reason about how Spanner, CockroachDB, Postgres SSI, DynamoDB, and Cassandra actually implement their stated guarantees
• Translate "we need strong consistency" into the precise guarantee the workload requires

Intuition#

Imagine two accountants reconciling a company's books. One works from yesterday's printed ledger (bounded staleness). She can answer "what was our revenue last quarter?" perfectly well from stale data. The other sits at the live register, processing payments in real time. She must see every transaction the instant it commits, because she is deciding whether to approve the next wire transfer.

Both accountants work for the same company. Both are "consistent." But they need fundamentally different guarantees. The ledger accountant tolerates staleness because her decisions do not depend on the latest write. The register accountant cannot, because a stale read could approve a transfer that overdraws the account.

This is the core insight: consistency is not a single dial you turn up or down. It is a two-dimensional grid. One axis is the isolation level (what concurrent transactions see of each other). The other axis is the consistency model (how quickly a committed write becomes visible to readers across replicas). "Strict serializable" sits at the top of both axes. Everything else is a named trade-off below it.

Consistency Models gave you the single-object hierarchy (linearizable, sequential, causal, eventual) and the four session guarantees. This chapter adds the transactional layer: what happens when the unit of interest is a multi-object transaction, how real databases implement the guarantees they claim, and why those claims often do not match reality.

Theory#

Recap and scope#

Consistency Models covered single-object consistency models and session guarantees. This chapter is about what happens when the unit of interest is a transaction (multi-object) instead of a single register, and how real databases implement the guarantees they claim. We will not re-derive linearizability; we build on top of it.

Isolation levels and anomalies#

The SQL-92 standard defines four isolation levels (read uncommitted, read committed, repeatable read, serializable) in terms of three anomalies (dirty read, non-repeatable read, phantom). But the English-language definitions are ambiguous and miss several important anomalies^[3:1].

Berenson et al. (1995) showed the ANSI phenomena definitions admit strict and broad interpretations, that neither captures real implementation behavior, and introduced snapshot isolation as a formal level^[3:2]. Adya's 1999 thesis generalized these with dependency graphs, producing phenomena G0 (dirty write), G1a-c (aborted/intermediate/cyclic reads), G-single (read skew), and G2 (anti-dependency cycles)^[4][5].

The anomalies that matter most in practice:

• Write skew: two transactions each read overlapping state, write disjoint keys, both commit, and the combined result violates an invariant neither individually broke. Two on-call doctors each read "someone else is on call," each remove themselves, nobody is on call.
• Read skew (G-single): a transaction reads two related values at different points in time, seeing an inconsistent snapshot.
• Phantom: a transaction re-executes a predicate query and gets different rows because another transaction inserted or deleted matching rows.

The critical vendor-mapping problem: Postgres "REPEATABLE READ" is actually snapshot isolation, not ANSI repeatable read^[6]. MySQL InnoDB RR uses next-key locking to prevent phantoms from index scans but still allows write skew. Jepsen measured approximately 140 G2-item anti-dependency cycles per minute in a contended Postgres RR workload^[7].

Write skew occurs when two transactions read overlapping state and write disjoint keys; snapshot isolation cannot detect the conflict because the write sets do not intersect.

Serializable Snapshot Isolation (SSI) fixes this. Cahill, Rohm, and Fekete (2008) showed that dangerous structures (a triple of transactions with two adjacent read-write anti-dependencies) are necessary for non-serializable outcomes^[8]. Postgres implements SSI as the SERIALIZABLE level since 9.1, tracking SIREAD locks and aborting transactions that would close a dangerous structure^[9]. SSI preserves snapshot isolation's non-blocking reads while providing true serializability.

Linearizable vs serializable vs strict serializable#

These three terms are the most commonly confused in distributed systems. They describe different things:

Linearizability (Herlihy and Wing, 1990): a single-object correctness condition. Every operation appears to take effect atomically at some point between its invocation and response; the resulting total order is consistent with real time^[10]. Cost: one consensus round per write on the object.

Serializability: a multi-object transaction correctness condition. Some serial order of committed transactions produces the observed reads and final state. It says nothing about real time^[1:1]. A database can be serializable and still reorder non-overlapping transactions freely.

Strict serializability = serializable + linearizable. Every committed transaction has an apparent commit point between invocation and response, and the serial order agrees with that real-time order^[1:2][2:1]. Spanner calls this "external consistency"^[11]. Jepsen's consistency map places strict serializable at the top of both the transaction and single-object families^[1:3].

Strict serializable is the strongest model, unifying the transaction family (left branch) and single-object family (right branch); every arrow means "implies."

The key insight: linearizability and serializability are orthogonal. You can have one without the other. CockroachDB deliberately implements serializable but not linearizable across keys (single-key operations are linearizable, but disjoint-key transactions can exhibit a "causal reverse" anomaly where T2, which begins after T1 commits, appears to commit first)^[12][13]. This is the price of avoiding Spanner-grade clock costs on commodity hardware.

Bounded staleness and read-time APIs#

Bounded staleness means "at most X seconds or N versions behind the latest committed write." It is strictly stronger than eventual (bounds the gap) and strictly weaker than linearizable (allows a gap)^[14].

Three production implementations:

• Spanner stale reads: accept a max-staleness or exact timestamp; served from any replica caught up to that timestamp, avoiding the leader round trip^[11:1].
• CockroachDB AS OF SYSTEM TIME: follower_read_timestamp() targets a historical read at least 4.2 seconds in the past (per current v26.2 docs) so the read can be served locally from a follower replica without blocking on conflicting writes^[15].
• Cosmos DB Bounded Staleness: configured by K writes or T seconds (minimum 100,000 writes / 300 seconds for multi-region); writes throttle if a region lags past the bound^[14:1].

When bounded staleness is safe: analytics, dashboards, leaderboards, audit-style "as of last close" queries, personalized recommendations.

When bounded staleness is dangerous: inventory checks ("is the last item in stock?"), account balances, uniqueness constraints, rate limiting, and any read-modify-write pattern. The writer cannot tell from the read API whether the value is current.

How real systems implement each#

Where each named database sits on the isolation-by-consistency grid; the subgraph names the guarantee the default or strongest mode provides.

Spanner: Paxos groups of approximately 5 replicas per tablet. Each transaction gets a commit timestamp within a TrueTime interval; the coordinator waits until TT.now().earliest > commit_ts before releasing locks^[11:2][16]. The 2012 Spanner paper reported TrueTime epsilon "usually less than 7 ms"; as of 2023, Google reports TrueTime provides Spanner servers with less than 1 ms clock uncertainty at p99^[16:1][2:2]. Read-only transactions pick a safe timestamp and can be served by any up-to-date replica without leader coordination.

CockroachDB: Range-based sharding with Raft groups. Transactions use a Hybrid Logical Clock (HLC). Each reader has an uncertainty interval of width max-offset (default 500 ms)^[17]. An observed write with a timestamp in that window forces a transaction restart. Parallel Commits (19.2, 2019) collapsed commit latency from two consensus rounds to one^[18]. Nodes self-shut-down if observed clock offset exceeds 80% of max-offset^[17:1].

PostgreSQL: MVCC on a single primary. SERIALIZABLE adds SIREAD locks and aborts transactions involved in a dangerous structure^[8:1][9:1]. Replication is asynchronous; read replicas are not serializable. Default isolation is READ COMMITTED^[6:1].

DynamoDB: Two read modes per request: eventually consistent (0.5 RCU per 4 KB) or strongly consistent (1 RCU, single-region only). TransactWriteItems and TransactGetItems are serializable but limited to 100 items and 4 MB^[19]. Global Tables replicate asynchronously with last-writer-wins; they do not preserve transaction atomicity across regions^[20].

Cassandra: Tunable consistency per query (ONE, QUORUM, LOCAL_QUORUM, ALL). Lightweight Transactions (LWT) implement linearizable compare-and-set via a four-round-trip Paxos protocol^[21]. CEP-14 (Cassandra 4.1) reduces uncontended LWTs to two round trips for writes.

Real-World Example#

Google Spanner: external consistency via TrueTime.

Spanner is the production system that most cleanly demonstrates strict serializability at global scale. The engineering insight is deceptively simple: expose clock uncertainty as an interval, not a point, and wait it out.

Every Spanner datacenter has GPS receivers and atomic clocks. The TrueTime API returns [earliest, latest] with the true time guaranteed to be inside. The 2012 Spanner paper reported epsilon (the interval width) "usually less than 7 ms"; as of 2023, Google reports TrueTime achieves sub-1 ms clock uncertainty at p99^[16:2][2:3].

When a read-write transaction commits:

1. The coordinator assigns commit_ts = latest from the current TrueTime interval.
2. It replicates the write via Paxos to a majority of replicas.
3. It enters commit-wait: polling TrueTime until TT.now().earliest > commit_ts.
4. Only then does it acknowledge the commit to the client.

Spanner assigns a commit timestamp within TrueTime's uncertainty interval and waits out the interval before acknowledging, ensuring any subsequent transaction observes the commit.

This commit-wait is proportional to epsilon: with sub-millisecond p99 uncertainty today, the wait is usually masked by the Paxos quorum round trip itself^[2:4][16:3]. The result is that if T1 commits before T2 starts (in real time), T1's timestamp is strictly less than T2's. This is external consistency: the serial order of transactions matches the real-time order observable by any external observer.

Read-only transactions are cheaper. They pick a safe timestamp and can be served by any replica that has applied all writes up to that timestamp, without acquiring locks or contacting the leader^[11:3].

The trade-off is explicit: Spanner requires GPS and atomic clocks in every datacenter. CockroachDB's alternative (HLC with a 500 ms max-offset budget, serializable without cross-key linearizability) runs on commodity NTP-synchronized hardware but accepts the causal-reverse anomaly^[13:1][12:1]. Jepsen's 2017 analysis of CockroachDB beta confirmed two serializability violations (both fixed) and documented the causal-reverse as by-design^[12:2].

Trade-offs#

Common Pitfalls#

Exercise#

You are designing a bank account service. Money transfers must never double-spend and must be visible to the sender immediately. Monthly statements are OK a few seconds stale. Design the consistency level per operation: what must be linearizable, what can be snapshot isolation, what can be read from a stale replica. Then pick a database (Postgres vs CockroachDB vs Spanner) and justify.

Key Takeaways#

• "Strong consistency" is marketing. Name the guarantee: linearizable, serializable, strict-serializable, snapshot, causal, or eventual.
• Linearizability is a single-object property (real-time order). Serializability is a multi-object transaction property (equivalent to some serial order). Both together is strict serializability / external consistency.
• Most OLTP workloads do fine on snapshot isolation. Know which anomalies it lets through: write skew is the big one.
• Postgres "REPEATABLE READ" is snapshot isolation, not ANSI RR. Jepsen found approximately 140 G2-item cycles per minute under contention^[7:3].
• Tune consistency per operation, not per database. Transfers need serializable; statements can use bounded staleness; balance checks need read-your-writes.
• CockroachDB is serializable but not strict-serializable across keys. Spanner is strict-serializable but requires GPS and atomic clocks. Pick based on your actual invariant requirements.
• Even "passed Jepsen" does not mean "always correct." Postgres SSI had a 9-year latent bug (2011 to 2020)^[7:4]. Test your isolation guarantees under contention.

Further Reading#

• A Critique of ANSI SQL Isolation Levels (Berenson et al., 1995) - defines snapshot isolation and exposes the ambiguity of ANSI phenomena; the foundational paper for understanding why vendor labels lie.
• Serializable Isolation for Snapshot Databases (Cahill et al., 2008) - the SSI algorithm that Postgres 9.1 shipped; read this to understand how optimistic serializability works without blocking reads.
• Spanner: Google's Globally-Distributed Database (Corbett et al., OSDI 2012) - external consistency and TrueTime; the canonical reference for strict serializability at global scale.
• CockroachDB Jepsen 2017 analysis - documents the causal-reverse anomaly and two early serializability bugs; essential for understanding what "serializable but not linearizable" means in practice.
• PostgreSQL 12.3 Jepsen analysis - proves Postgres RR is SI, finds the 9-year SSI bug, and measures G2-item rates; the most important Jepsen report for Postgres users.
• Jepsen Consistency Models reference - Kyle Kingsbury's interactive map of every consistency model with implication arrows; the clearest single-page reference online.
• Parallel Commits (Cockroach Labs, 2019) - how CockroachDB collapsed distributed commit from two consensus rounds to one; read for the TLA+ specification of implicit commit.
• DDIA Chapters 7 (Transactions) and 9 (Consistency and Consensus) by Martin Kleppmann - the canonical teaching reference for this material; read alongside this chapter for deeper formalism.

Flashcards#

References#