Day 402: Isolation Anomalies and Serialization Graphs

The core idea: A concurrent history is safe only if its dependency graph can be arranged into one serial order; anomalies are the cases where the graph closes into a cycle and no such order exists.

Today's "Aha!" Moment

In 01.md, Harbor Point's upgraded quotevault engine learned how to treat a multi-statement correction as one atomic unit. That solved the question "did this transaction commit or not?" It did not solve the harder question that appears as soon as two traders act at once: "can these committed transactions both be correct together?"

At 09:30, Harbor Point has 9.6M of open municipal-bond exposure against issuer MUNI-77, with a hard intraday limit of 10.0M. Trader A wants to reserve 300k of headroom for a client quote. Trader B, on another session, wants to do the same thing at the same moment. Each transaction reads the current open reservations, sees 400k of room left, inserts its own reservation row, and commits. Nothing is half-written. WAL is fine. Recovery is fine. The problem is that the final state says 10.2M is reserved, even though each transaction individually checked the rule before writing.

That is the mental shift for this lesson. Isolation anomalies are not mysterious "race conditions" floating above the database. They are specific histories with specific dependency edges. A serialization graph gives you a compact proof: if the graph has a cycle, the database allowed a story that could not have happened in any one-at-a-time execution. Write skew, phantoms, and lost updates are different surfaces of that same failure.

The next lesson on 03.md turns that theory into machinery by looking at strict two-phase locking and lock-manager internals. This lesson stays one layer earlier: how to name the bad histories precisely, how to draw them, and why production systems either block, validate, or abort transactions to keep those cycles from becoming durable facts.

Why This Matters

Harbor Point's exposure guard looked safe in code review because every approval ran inside a transaction and every transaction re-checked the issuer limit before inserting a reservation. Under light load, the invariant held. During the market-open burst, it failed intermittently. The desk did not see torn rows or crashed processes; it saw a much worse kind of bug, one that looked legitimate in every local log line and still broke a portfolio-level rule.

This is the practical value of anomaly analysis. Without it, the team argues in vague terms: "maybe MVCC is stale," "maybe the replica lagged," "maybe we need more locks." With it, the bug becomes concrete. Two transactions each read a predicate over open reservations, each inserted a row that should have changed the other's decision, and the committed history formed a cycle. That tells you exactly what kind of protection is missing: predicate locking, serializable validation, or a schema change that collapses the invariant onto one contention point.

In production, that precision matters because isolation choices affect more than correctness. They change wait behavior, abort rates, deadlock exposure, retry logic, and how you explain a postmortem. Once the team can say "this was a write-skew cycle on an issuer-limit predicate," the fix stops being folklore and becomes engineering.

Learning Objectives

By the end of this session, you will be able to:

1. Explain why an anomaly is really a failed serial-order proof - Show why Harbor Point's exposure approvals can be individually sensible and jointly wrong.
2. Build and read a serialization graph - Map reads and writes to dependency edges and decide whether a committed history is serializable.
3. Compare prevention strategies in production terms - Reason about when to block conflicts up front, when to validate and retry, and when to redesign the invariant.

Core Concepts Explained

Concept 1: An isolation anomaly is a committed history with no valid serial explanation

Return to Harbor Point's issuer-limit rule. The desk stores each tentative quote approval as a row in quote_reservations, and the rule is "the sum of all status = 'open' reservations for one issuer must stay at or below the configured limit." The approval transaction therefore reads a predicate, not just one row:

BEGIN;

SELECT COALESCE(SUM(amount), 0) AS reserved
FROM quote_reservations
WHERE issuer_id = 'MUNI-77' AND status = 'open';

-- if reserved + 300000 <= 10000000, then:
INSERT INTO quote_reservations (issuer_id, trader_id, amount, status)
VALUES ('MUNI-77', 'trader-a', 300000, 'open');

COMMIT;

If Trader A and Trader B both run that logic against the same snapshot-like view, both can read 9.6M, both can conclude that 300k fits, and both can insert. The anomaly is not that one transaction saw corrupted data. Each one saw a self-consistent database state. The anomaly is that after both commits, no serial order explains the outcome. If A had really run before B, then B's read should have seen 9.9M and declined. If B had really run before A, then A should have declined. Because both committed approvals exist, the history cannot be equivalent to either serial order.

That is why serializability is the reference contract. It does not promise that transactions literally run one at a time. It promises that the committed result can be explained as if they had. As soon as Harbor Point loses that property, the desk is no longer reasoning about one clean sequence of approvals. It is reasoning about interleavings whose combined effect may violate a portfolio invariant even though no single statement looks suspicious.

Write skew is the name usually given to this pattern when two transactions read overlapping facts and then write different rows whose combination breaks a rule. Phantoms are the same problem viewed through a predicate: a new matching row appears in a range or filter that a transaction used for its decision. Lost updates are a tighter version in which both transactions read the same item and one silently overwrites the other's derived write. Different names help with diagnosis, but the common test is still the same: can you tell one serial story that matches the final outcome?

Concept 2: A serialization graph turns concurrency into something you can prove

A serialization graph has one node per committed transaction. An edge means "these two transactions must appear in this order if the history is to make sense." Three edge families matter most in database isolation work:

• wr: T1 wrote a version that T2 later read, so T1 must come before T2.
• ww: T1 and T2 both wrote the same logical item or key range, and T2's write is later, so T1 must come before T2.
• rw anti-dependency: T1 read a version or predicate result that T2 later changed, so for T1's read to remain valid, T1 must come before T2.

Harbor Point's issuer-limit bug is a pure rw cycle:

T1: read SUM(open reservations for MUNI-77) = 9.6M
T2: read SUM(open reservations for MUNI-77) = 9.6M
T1: insert reservation R1 for 300k
T2: insert reservation R2 for 300k

Edges:
T1 --rw--> T2   because T2 inserted a row that should have changed T1's predicate result
T2 --rw--> T1   because T1 inserted a row that should have changed T2's predicate result

Once the graph contains T1 -> T2 -> T1, the proof is over. A cycle means there is no topological order, which means there is no serial schedule that could have produced the same reads and writes. That is the formal reason the history is non-serializable. The value of the graph is that it separates "something concurrent happened" from "this specific concurrency pattern violated the serial contract."

This also explains why phantoms are not just a user-interface oddity where a query returns a different count the second time. In serialization terms, a phantom is a predicate-shaped rw edge. Harbor Point's transaction did not read reservation row R2 because R2 did not exist yet, but it absolutely depended on the absence of any such row when it approved the quote. Predicate reads therefore create dependencies on gaps and ranges, not only on the row identifiers that currently exist.

If Harbor Point had instead materialized the current issuer total in one issuer_exposure row and both transactions performed a read-modify-write on that row, the anomaly surface would change. The engine could often detect or block the conflict with a simpler row-level ww interaction. That does not mean serialization graphs become irrelevant. It means schema design can move an invariant from a broad predicate conflict to a narrow key conflict that the engine handles more directly.

Concept 3: Real engines prevent cycles either by blocking edges or by aborting dangerous histories

Once you think in graphs, isolation levels stop looking like vague labels and start looking like edge-management policies. A strict two-phase locking engine tries to stop dangerous edges from forming in the first place. If Harbor Point's approval transaction reads the relevant rows or ranges under locks that are held until commit, another transaction may have to wait before it can insert a conflicting reservation. The benefit is straightforward reasoning: by the time a transaction commits, its ordering constraints were already enforced. The cost is blocking, lock memory, and the possibility of deadlocks when transactions wait on one another in a loop.

MVCC changes the shape of the problem rather than removing it. Snapshot reads let Harbor Point's readers proceed without blocking writers for many workloads, which is excellent for throughput and latency. But a stable snapshot does not by itself eliminate rw cycles. In fact, snapshot isolation is exactly where write skew often survives: each transaction reads a coherent past, writes a disjoint row, and only later does the system discover that the combination had no serial explanation. Serializable MVCC implementations solve this by tracking dangerous structures and aborting one participant before the cycle becomes a committed fact.

That design choice is visible to operators. Blocking-first systems tend to surface lock waits, deadlocks, and queue buildup. Validation-first systems surface serialization failures and application retries. Neither is "free." Harbor Point has to decide whether the issuer-limit path is better served by waiting, by retrying, or by changing the schema so the invariant becomes one atomic counter update instead of a predicate over many reservation rows. The right answer depends on hotspot intensity, tail-latency budget, and how much retry complexity the application can tolerate.

This is the bridge into 03.md. Strict 2PL is one concrete way to enforce a serial order before commit, and a lock manager is the subsystem that makes that enforcement operational. The graph perspective from this lesson tells you what that machinery is really buying: not "more locking" in the abstract, but the prevention of specific cycles that would otherwise let Harbor Point acknowledge an impossible history.

Troubleshooting

Issue: "We run at REPEATABLE READ, but the issuer limit still breaks occasionally."

Why it happens / is confusing: A stable snapshot prevents many read anomalies, but it may still allow a write-skew cycle when two transactions read the same predicate and then write different rows.

Clarification / Fix: Confirm whether the invariant depends on the absence or sum of multiple rows. If it does, move the path to true serializable isolation, add explicit locking for the predicate, or redesign the invariant around one row that every transaction must update.

Issue: "No row was overwritten, so why are we calling this a concurrency bug?"

Why it happens / is confusing: Teams often equate concurrency bugs with lost updates on one row. Harbor Point's failure is subtler: both inserts are individually valid, but together they invalidate the predicate that justified each insert.

Clarification / Fix: Inspect the history at the predicate level, not just the row level. Ask which rows or gaps each transaction assumed were absent or below threshold when it made its decision.

Issue: "After enabling serializable isolation, commits started failing with retryable errors."

Why it happens / is confusing: The database is no longer permitting dangerous cycles to commit. One transaction is being aborted so the committed history still has a valid serial order.

Clarification / Fix: Treat serialization failures as a normal control path. Keep transactions short, add supporting indexes so predicate checks are narrow, and retry from an idempotent application boundary rather than halfway through side effects.

Advanced Connections

Connection 1: Serialization graphs ↔ lock manager internals

A lock manager is the operational counterpart to the graph model. Row locks, gap locks, next-key locks, and predicate locks are all ways of forbidding certain edges from appearing concurrently. Harbor Point's issuer-limit rule is a good example of why row locks alone are not always enough: the dangerous dependency comes from a range predicate over "all open reservations for MUNI-77," not from one known row identifier. That is exactly why 03.md needs both strict 2PL and lock-manager internals in the same lesson.

Connection 2: Serialization graphs ↔ history-based correctness testing

The same reasoning appears outside one database engine. Jepsen-style analyses and formal consistency checkers take an observed history, build constraints between operations, and ask whether any legal order satisfies them. The contract is different for linearizability than for serializability, but the habit of mind is the same: correctness is a statement about which histories can be explained by a permitted order, not about whether the logs "look normal" at first glance.

Resources

Optional Deepening Resources

• [DOC] PostgreSQL Documentation: Transaction Isolation
  • Focus: Compare the guarantees of READ COMMITTED, REPEATABLE READ, and SERIALIZABLE in a production MVCC engine.
• [DOC] MySQL 8.0 Reference Manual: InnoDB Next-Key Locking
  • Focus: See how range and gap locking are used to prevent phantom-style predicate conflicts.
• [PAPER] A Critique of ANSI SQL Isolation Levels
  • Focus: Ground the anomaly vocabulary in a classic paper that explains why isolation names alone are insufficient.
• [PAPER] Serializable Snapshot Isolation in PostgreSQL
  • Focus: Study how an MVCC system can detect dangerous rw structures and abort one transaction before a non-serializable cycle commits.

Key Insights

1. An anomaly is a failed serialization proof - The question is not whether each transaction looked reasonable alone, but whether the committed history still admits any serial order.
2. Predicate reads create real dependencies - Harbor Point's limit check depends on the absence of matching rows, so phantoms and write skew live in the gaps, not only in overwritten tuples.
3. Isolation strategy is edge management - Engines either block dangerous edges early, validate and abort them later, or rely on schema design to collapse broad predicates into simpler conflicts.