# DDIA Ch. 10: SERIALIZABLE still returns a stale read — it is not LINEARIZABLE ## Concept A single register `reg` holds `x = 0`. Transaction **T2** opens under `SERIALIZABLE` and reads `x` — it sees **0**, fixing its snapshot. A separate transaction **T1** then writes `x = 1` and commits. Now, back in the *same* T2, you read `x` a second time. The intuition "SERIALIZABLE means I always see the latest committed value" predicts **1**. It returns **0** — the stale value — and T2 then `COMMIT`s with **no serialization error** (no SQLSTATE `40001`). Nothing was violated: the execution is perfectly serializable, equivalent to running T2 *entirely before* T1, so the stale read is legal in that serial order. What serializability does *not* give you is recency in real time — that stronger property is **linearizability**, and PostgreSQL's MVCC reads don't provide it. A fresh transaction after T2 commits reads **1**: T1's write was never lost, just invisible to T2's older snapshot. You will reproduce this on a real PostgreSQL 16 server, in two hand-typed `psql` sessions. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — *Consistency and Consensus*, §"Linearizability Versus Serializability". The book's claim, tightly paraphrased: > Serializability and linearizability are different guarantees. A database can be > serializable without being linearizable — serializability permits stale reads — > and the combination of both is called *strict serializability*. Serializability constrains the *outcome* to match *some* serial order of the transactions; linearizability constrains *when* each operation takes effect relative to the wall clock. The two are independent guarantees. Here you watch a SERIALIZABLE transaction take a serial order that puts T2 before T1 — and so read a value that is already stale in real time, without any error. ## Prerequisites The surprise turns on a single distinction: *some* serial order need not be the *real-time* order. These help; each line notes where it shows up. 1. **Serializability = equivalent to *some* serial order** — the outcome must match running the transactions one at a time in *some* sequence, but the engine is free to pick which sequence. It shows up as T2 being ordered *before* T1 even though T1 committed first in wall-clock time. 2. **Linearizability = real-time recency** — every read must return the value of the most recent completed write, as ordered by the wall clock; once a write commits, no later read may return an older value. It shows up as the guarantee T2's second read *would* need — and doesn't get. 3. **Snapshot isolation / MVCC** — a transaction reads from a consistent snapshot fixed at its first query; PostgreSQL's SERIALIZABLE (SSI) builds *on top of* this snapshot. It shows up as T2's second read still seeing `x = 0` because its snapshot predates T1's commit. 4. **The two guarantees are independent** — a system can be serializable without being linearizable (this exercise), or linearizable without being serializable (a single-object register with no multi-object transactions). It shows up as T2 committing cleanly *and* returning stale data at the same time. ### Where to learn the prerequisites - **Serializability vs. linearizability (#1, #2, #4):** DDIA §"Linearizability" and §"Linearizability Versus Serializability"; Peter Bailis, "Linearizability versus Serializability" (bailis.org/blog) — the canonical short explainer of why one does not imply the other. - **Snapshot isolation / SSI (#3):** DDIA §"Serializable Snapshot Isolation (SSI)"; the PostgreSQL manual, ch. 13 "Concurrency Control" → "Serializable Isolation Level". If only one is new, make it #1 — *some* serial order (chosen by the engine), **not** the real-time order, is the entire reason a stale read stays legal. ## Environment The interleaving is fixed, not a race, so the result is 100% reproducible: PostgreSQL 16.14 (Debian, aarch64) in Docker on macOS 26.5.2 (Darwin 25.5.0), arm64; captured via psycopg[binary] on Python 3.12 (uv), two sessions against one database; deterministic. The reader-facing steps use two manual `psql` sessions against the same server; `code/serializable_not_linearizable.py` is the capture harness that drives the identical two-session interleaving programmatically and prints the values quoted below. ## Mental model Two guarantees, often conflated, constrain *different things*. One register, two transactions — T2 reads twice, T1 writes once in between. | Guarantee | What it constrains | The rule | Does this exercise satisfy it? | | --- | --- | --- | --- | | **Serializability** | the *outcome* | the result must equal *some* serial order of the transactions — the engine picks which | **Yes** — the order is T2 (reads 0, 0) then T1 (writes 1); a valid serial schedule | | **Linearizability** | *when* each op takes effect | each op appears to take effect atomically at some point between its call and return, respecting real-time order; a read after a committed write must see it | **No** — T1 committed `x=1` in real time *before* T2's second read, yet that read returns 0 | A database can have one without the other. PostgreSQL SERIALIZABLE gives the first (serializable outcomes via SSI) but not the second (MVCC reads answer from a snapshot, not the real-time latest). "Strict serializability" is *both* at once — what Spanner provides via TrueTime. The whole interleaving is one script, `code/serializable_not_linearizable.py`; the Steps you run by hand in two `psql` sessions. ## Setup The server is already running (a shared `postgres:16` container). Give yourself your own database and a single register seeded to 0, then open **two** `psql` sessions side by side — call them **T2** (the reader, opened first) and **T1** (the writer). ``` # your own database + seed psql -h localhost -U postgres -d postgres \ -c "DROP DATABASE IF EXISTS ex_ch10_serlin; CREATE DATABASE ex_ch10_serlin;" psql -h localhost -U postgres -d ex_ch10_serlin <<'SQL' CREATE TABLE reg (id int PRIMARY KEY, x int); INSERT INTO reg VALUES (1, 0); SQL # two sessions, one per terminal: # T2 (reader): psql -h localhost -U postgres -d ex_ch10_serlin # T1 (writer): psql -h localhost -U postgres -d ex_ch10_serlin ``` The capture harness `code/serializable_not_linearizable.py` does all of this itself (drop + recreate + seed + the interleaving) and is what produced the values below: ``` uv run --python 3.12 --with "psycopg[binary]" python3 code/serializable_not_linearizable.py ``` Do **not** read ahead — make each prediction first. ## Steps ### Step 1 — T2 takes its snapshot, then T1 commits underneath it (the surprise) **Predict.** In **T2**, open a SERIALIZABLE transaction and read `x` (this returns 0 and fixes the snapshot). Then, in **T1**, write `x = 1` and commit. Back in **T2** (still the same transaction), read `x` a second time. Does the second read return **0** (T2's snapshot) or **1** (T1's committed write)? ``` -- T2: open the transaction, first read fixes the snapshot BEGIN ISOLATION LEVEL SERIALIZABLE; SELECT x FROM reg WHERE id = 1; ``` ``` -- T1: write x = 1 and commit (autocommit: one statement is one transaction) UPDATE reg SET x = 1 WHERE id = 1; ``` ``` -- T2: same transaction, read x again SELECT x FROM reg WHERE id = 1; ``` **Observe.** T2 prints: ``` BEGIN x --- 0 (1 row) x --- 0 (1 row) ``` **Both reads return 0 — the second is stale.** T1's `x = 1` committed in real time *between* T2's two reads, yet T2's second read still returns 0. T2's snapshot was fixed at its first query, before T1 committed, and every read in the transaction is answered from it. This is exactly the recency guarantee linearizability would give and serializability does not. ### Step 2 — T2 commits with no serialization error **Predict.** T2 read a value (0) that a concurrent transaction has already overwritten and committed. When T2 now `COMMIT`s, does PostgreSQL abort it with a serialization failure (SQLSTATE `40001`, "could not serialize access"), or does it commit cleanly? ``` -- T2: commit the transaction COMMIT; ``` **Observe.** ``` COMMIT ``` **Clean commit — no `40001`.** SSI only aborts a transaction when the committed outcome could *not* correspond to any serial order (a dangerous read/write dependency cycle). Here there is no cycle: ordering **T2 entirely before T1** is a perfectly valid serial schedule that produces exactly what T2 saw (0, then 0). The stale read is not an anomaly to be caught — it is *consistent* with a real serial order, just not with the real-time one. ### Step 3 — a fresh transaction sees the write (it was never lost) **Predict.** T2 has committed. Open a brand-new transaction and read `x`. Does it return T2's stale **0**, or T1's committed **1**? ``` -- a fresh session/transaction, entirely after T2 committed BEGIN ISOLATION LEVEL SERIALIZABLE; SELECT x FROM reg WHERE id = 1; COMMIT; ``` **Observe.** ``` BEGIN x --- 1 (1 row) COMMIT ``` **1 — T1's write was there all along.** The staleness was never data loss; it was purely a property of T2's *old snapshot*. Any transaction whose snapshot is taken *after* T1's commit sees 1. The staleness is specific to a long-lived snapshot that started before the write committed. ## What you should see - **T2 read 1 = 0**, then T1 commits `x = 1`, then **T2 read 2 = 0** — a stale read under SERIALIZABLE. - **T2 `COMMIT` succeeds**, no SQLSTATE `40001` — the execution is serializable (equivalent to T2 before T1). - **T3 (fresh) read = 1** — the write is visible to any later snapshot; only T2's view was stale. - The harness summary lines: `STALE READ under SERIALIZABLE` / `succeeded (no 40001)` / `T3 read = 1`. ## Why Serializability and linearizability answer two different questions, and the exercise pries them apart. Serializability asks: *is the result equivalent to running these transactions one at a time in some order?* Linearizability asks: *does every operation appear to take effect at a single instant, consistent with the real-time order in which the operations actually happened?* The first is about the existence of *a* serial order; the second is about *which* order — the wall-clock one. T2's second read is stale because its snapshot was taken at its first query, before T1 committed. Under MVCC, that snapshot pins the exact set of row versions T2 can see, and T1's later commit creates a *newer* version that is simply not in T2's visible set. So T2 reads 0 both times. Now ask whether this violates serializability: is there a serial order of {T2, T1} that produces this outcome? Yes — **T2 entirely before T1**. In that order T2 reads 0, reads 0, and commits; *then* T1 writes 1. Every value T2 saw is consistent with that schedule, so SSI has nothing to abort, and `COMMIT` returns cleanly. The read is stale only against the *real-time* order (T1 committed first), and serializability never promised to respect real-time order. To *also* be linearizable, T2's second read would have to reflect T1's already-committed write — a strictly stronger, real-time property. Linearizability would forbid the serial order "T2 before T1" here, because T1's commit *precedes* T2's second read in real time, so any linearizable history must order T1 before that read and the read must return 1. PostgreSQL's MVCC reads deliberately don't provide this for a transaction's snapshot: the whole point of a snapshot is to give a stable view, which means ignoring writes that commit after it opens. You get serializable *outcomes* without paying for real-time *recency*. **The boundary — the staleness lives in the long-lived snapshot, not in SERIALIZABLE itself.** Read the same register in a *fresh* transaction (Step 3), or force a real-time-current read with `SELECT x FROM reg WHERE id = 1 FOR UPDATE` (which takes a row lock and reads the latest committed version, blocking on or conflicting with concurrent writers), and you see 1. The gap only opens when a transaction holds a snapshot taken *before* a write and then reads *after* that write commits. A single-object store that answers every read from the latest committed value *is* linearizable for that object — it just isn't doing multi-statement snapshot reads. So place your own system by asking: does a read answer from a point-in-time snapshot (serializable, possibly stale) or from the real-time-latest state (linearizable, always current)? ### Go deeper 1. **Provoke a real `40001`.** Give T2 a *write* that depends on its stale read (e.g. both T1 and T2 read then write the same rows to form a write-skew cycle) and watch SSI abort one with SQLSTATE `40001` — the contrast with this exercise's clean commit shows exactly *which* stale-read consequences serializability forbids (dangerous cycles) versus permits (a pure stale read). 2. **Strict serializability.** Read DDIA on strict serializability = serializable + linearizable, and how Spanner achieves it with TrueTime: commit timestamps from bounded-uncertainty clocks force the serial order to agree with real time, closing exactly the gap you just observed. 3. **REPEATABLE READ shows the same staleness.** Re-run Step 1 with `ISOLATION LEVEL REPEATABLE READ` instead of SERIALIZABLE. Predict whether the second read changes (it won't — both levels sit on the same MVCC snapshot), and confirm that the stale read is a snapshot property, not a SERIALIZABLE-specific one.