Part 6 · Invariants under concurrency

Transactions: ACID, Isolation Levels, and Anomalies

Part 5 split one dataset across many machines and learned to operate it: each shard owns a slice (lesson 11), a routing tier and multitenancy ops keep it healthy under load (lesson 12), and a row lives wherever its key hashes. But splitting, replicating, and operating data does nothing to tame the other source of chaos — concurrency on the same data. Two requests read the same feature row and both write back; a job updates a counter while another reads it; a node crashes between two writes that were supposed to happen together. Each individual query looked fine, yet the result is corrupt. A transaction is the abstraction that lets the application pretend a chosen set of concurrency and crash faults simply did not happen. The interesting, subtle dial is isolation — how convincing that pretence is — and this lesson is the home of the isolation anomalies the rest of the track refers back to.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 7 (Transactions) — the meaning of ACID, the weak-isolation levels (read committed, snapshot isolation) and the anomalies they do and do not prevent, and the three roads to serializability. Original synthesis; the ML-infra framings are ours.

Linear position

Prerequisite: Lessons 03–04 — the ordered, durable write-ahead log and on-disk storage engines (atomicity and durability are built on the log). Lessons 08–09 — replication and the idea that two writes can be concurrent with no agreed order. We reuse "concurrent writes need a rule" and now give that rule a name: an isolation level.
New capability: Name every classic isolation anomaly, state which isolation level prevents it and at what cost, walk a write-skew interleaving step by step, and decide which invariants in an ML system actually require a serializable transaction versus a cheaper guard.

The plan

Six moves. (1) Define ACID precisely, letter by letter — and why consistency is the application's job, not the database's, while isolation is the one that hides concurrency. (2) Build the anomalies one at a time, each paired with the level that kills it: dirty reads/writes → read committed. (3) Read skew → snapshot isolation (and what MVCC is). (4) Lost update → atomic ops / locks / compare-and-set. (5) Write skew and phantoms — the subtle ones — → serializable, with a full worked interleaving. (6) The three ways to actually achieve serializability (serial execution, two-phase locking, serializable snapshot isolation), then a trade-off table, failure modes, and the hand-off to clocks and fencing.

1 · ACID, letter by letter

What this is: the four-letter promise, and which letter actually hides concurrency.

A transaction is a bundle of reads and writes that succeeds or fails as one unit, so the application can ignore certain concurrency and crash faults. ACID is the four-letter promise the bundle makes. The letters are not equally deep, and marketing has blurred them, so define each precisely.

Atomicity

All-or-nothing. Move 100 dollars between accounts — debit A, credit B — and a crash between the two steps must leave neither, never a vanished 100. If a multi-step transaction is interrupted partway (crash, constraint violation, client disconnect) the database aborts it and discards every write it made, as if it never started. Built on the durable log (lesson 03): undo the partial writes, or never make them visible until commit. The right antonym is abortability, not "concurrency."

Consistency

Application invariants hold before and after the transaction (e.g. "credits equal debits", "this username is unique"). The catch: the database can only enforce the invariants you told it about as constraints; the rest is the application's responsibility. This C is the app's, not the database's. It rides along in the acronym; A, I, D are properties the store actually provides.

Isolation

Concurrently executing transactions behave as if they ran one at a time — the system hides interleavings that would otherwise let one transaction see another's half-done work or clobber it. This is the interesting letter: in practice it is not a single guarantee but a ladder of levels, each admitting a different set of anomalies for more concurrency.

Durability

Once a transaction commits, its writes survive crashes — they were flushed to a durable medium (the WAL on disk, or replicated to enough nodes). After "commit OK", a power loss cannot lose the data. In a distributed store, durability means "written to enough replicas to survive the failures you planned for" (lesson 09).

So a transaction lets the application pretend two kinds of fault did not happen: crash faults (atomicity + durability — you never see a half-applied operation, and a commit you saw never un-happens) and concurrency faults (isolation — another transaction's interleaved reads and writes never corrupt yours). The rest of the lesson is about the second kind, because that is where the subtlety lives.

"Isolation" is a ladder, not a switch

The strongest isolation — serializable — means the result is equivalent to some serial order of the transactions, as if they never overlapped. It is the easiest to reason about and the most expensive to provide (locks, validation, aborts, lost concurrency). So real databases offer weaker levels that run faster but admit specific anomalies. The entire skill of this lesson is knowing which anomaly each level still allows, and whether your invariant can survive it.

2 · Dirty reads and dirty writes → READ COMMITTED

What this is: the first rung — only ever see or overwrite committed data.

The weakest useful level is read committed. It makes two promises, each killing one anomaly:

No dirty reads. A dirty read is reading a value another transaction has written but not yet committed. If that other transaction aborts, you acted on data that never existed. Read committed guarantees you only ever see committed values — a transaction's writes are invisible to others until it commits.
No dirty writes. A dirty write is overwriting a value another transaction has written but not yet committed. Read committed makes writes take a brief row lock until commit, so two transactions cannot interleave their writes to the same row — the later writer waits for the earlier one to finish.

dirty read (what READ COMMITTED forbids) T1: BEGIN T1: UPDATE feature SET ctr = 42 (uncommitted) T2: SELECT ctr -> reads 42 <-- DIRTY: sees uncommitted value T1: ROLLBACK (42 never existed; T2 acted on a ghost) under READ COMMITTED, T2's read blocks or returns the old committed value, never 42.

Read committed is the default in many databases (PostgreSQL, Oracle, SQL Server) because it is cheap — short write locks, reads never block on writes (the read just returns the last committed value). But it still allows everything below: a transaction that reads the same row twice can get two different answers if someone committed in between. That is the next anomaly.

3 · Read skew (non-repeatable read) → SNAPSHOT ISOLATION

What this is: the next rung — every read in a transaction sees one frozen point in time.

Read skew, also called a non-repeatable read, is when a transaction reads several rows and another transaction commits in the middle, so the reader sees an inconsistent mix of "before" and "after" states. Classic example: you read account A (balance 500), a transfer of 100 from A to B commits, then you read account B (balance now 600). Your snapshot shows 500 + 600 = 1100 — 100 dollars that never existed at any single instant. Each individual read was of committed data, so read committed permits this; the corruption is in seeing two points in time at once.

The fix is snapshot isolation: each transaction reads from a consistent snapshot of the database as it was at the moment the transaction started. Every read in that transaction sees the same frozen point in time, no matter what commits elsewhere. Reads never block writes and writes never block reads.

MVCC — how the snapshot is built

Snapshot isolation is almost always implemented with multi-version concurrency control (MVCC): instead of overwriting a row in place, the database keeps multiple versions of each row, each tagged with the transaction id that created it (and the one that deleted it). A transaction starting at time t is handed a list of which transaction ids had already committed at t; for every row it reads, it returns the newest version visible to that set, ignoring anything committed after it began. The cost is storage (old versions linger until a background garbage collector / vacuum reclaims versions no live transaction can still see) and the bookkeeping to track version visibility.

read skew under READ COMMITTED vs SNAPSHOT ISOLATION state: A = 500, B = 500 (invariant: A + B = 1000) T1 (read both): T2 (transfer 100, A->B): read A -> 500 UPDATE A = 400 UPDATE B = 600 COMMIT read B -> 600 => T1 sees A+B = 1100 <-- read skew: a state that never existed SNAPSHOT ISOLATION: T1 reads the snapshot from when it began. read A -> 500 ; read B -> 500 => A+B = 1000 (consistent point in time)

Snapshot isolation is what most databases call "repeatable read" (the SQL standard's names are notoriously muddled). It eliminates read skew and dirty reads cleanly. But it does not prevent two remaining anomalies that involve concurrent writes: lost update and write skew.

4 · Lost update → atomic ops, locks, or compare-and-set

What this is: the read-modify-write race snapshot isolation does not catch, and three cures.

A lost update is the read-modify-write race: two transactions each read the same value, each computes a new value from it, and each writes it back — the second write silently erases the first. This is the increment-a-counter bug, and snapshot isolation alone does not stop it, because both transactions read the same snapshot value and neither sees the other's write.

lost update — two clients increment the same counter state: views = 100 T1: read views -> 100 T2: read views -> 100 T1: write views = 101 T2: write views = 101 T1: COMMIT T2: COMMIT result: views = 101 <-- one increment LOST; should be 102

Three standard cures, in rising generality:

Atomic write operations. Push the read-modify-write into the database as one indivisible op: UPDATE feature SET views = views + 1 WHERE id = ?. The database takes an exclusive lock on the row for the duration, so the increments serialize. Best when the operation expresses cleanly as one statement — counters, append-to-set.
Explicit locking. The application reads ... FOR UPDATE, which locks the rows so any concurrent transaction must wait before reading-to-modify them. Use when the new value is computed by application code the database cannot express as one atomic statement.
Compare-and-set (CAS). Write only if the value has not changed since you read it: UPDATE feature SET views = 102 WHERE id = ? AND views = 100. If a concurrent transaction already moved views off 100, the WHERE matches no rows, the update is a no-op, and the application retries with the fresh value. This is optimistic — no lock held, but you must check the affected-row count and loop.

Some databases under snapshot isolation also offer automatic lost-update detection: the engine notices two transactions wrote the same object and aborts the later one, forcing a retry. That is convenient but only catches lost updates, not the harder anomaly next.

5 · Write skew and phantoms → SERIALIZABLE

What this is: the top rung — two transactions each pass a check, then jointly break the invariant.

Write skew is the anomaly that snapshot isolation cannot stop and the one that trips up careful engineers. The shape: two transactions each read an overlapping set of rows, each checks that an invariant still holds, and then each writes to a different row. Individually both decisions were correct against the snapshot they read — but their writes jointly violate the invariant, because neither saw the other's write.

The on-call doctors example (the canonical write skew)

Invariant: at least one doctor must be on call at all times. Two doctors, Alice and Bob, are both on call and both want to take the shift off. Each opens a transaction, reads "how many doctors are currently on call?", sees the answer is 2 (≥ 1, safe to leave), and updates her/his own row to off-call. Under snapshot isolation, each read the snapshot showing 2 on call, so each check passed — but the two writes touch different rows, so no lost-update detection fires, and the result is zero doctors on call. The invariant is over a predicate ("count of on-call doctors"), not a single row, so row-level locking the row you write does not protect it.

A full worked interleaving: how SI fails and SERIALIZABLE saves it

Two on-call doctors, Alice (id 1) and Bob (id 2), both on_call = true. The application logic for "go off call" is: count on-call doctors; if more than one, set my own row to off.

SNAPSHOT ISOLATION — write skew slips through state: doctor{1: on_call=true, 2: on_call=true} invariant: count(on_call) >= 1 time T_alice (id=1) T_bob (id=2) ---- ---------------------------------- ---------------------------------- t0 BEGIN (snapshot: 1=on, 2=on) t1 BEGIN (snapshot: 1=on, 2=on) t2 SELECT count(*) WHERE on_call=true -> 2 (>1, safe to leave) t3 SELECT count(*) WHERE on_call=true -> 2 (>1, safe to leave) <-- same snapshot t4 UPDATE doctor SET on_call=false WHERE id=1 (writes DIFFERENT row than Bob) t5 UPDATE doctor SET on_call=false WHERE id=2 t6 COMMIT COMMIT result: doctor{1: off, 2: off} -> count(on_call) = 0 INVARIANT VIOLATED no lost-update detection: the two writes touched different rows (id 1 vs id 2).

SERIALIZABLE — the conflict is caught Equivalent serial orders are only "Alice then Bob" or "Bob then Alice". In EITHER serial order, the second transaction's COUNT sees just ONE on-call doctor left and its check (count > 1) FAILS, so it does not go off call. Under 2PL: Alice's predicate read takes a range/predicate lock on the "on_call=true" set; Bob's read of that same predicate must WAIT, then sees count=1 after Alice commits, and abstains. Under SSI: both run optimistically; at commit the engine detects that each read a premise the other invalidated, and ABORTS one. It retries, re-reads count=1, and abstains. result: at least one doctor stays on call. Invariant holds.

The reason snapshot isolation fails is precisely that it gives each transaction its own frozen snapshot and lets non-conflicting writes commit independently. Write skew needs the system to notice that one transaction's write changed a premise the other read. That is what serializable isolation must guarantee.

Phantoms

The on-call example has a sibling problem: phantoms. A phantom is when a transaction's search condition (a predicate like WHERE on_call=true, or "is this username taken?", or "rows in this time range") would match a row that another transaction inserts. Locking the rows that currently exist does nothing, because the offending row does not exist yet when you take the lock. Phantoms are why serializable isolation needs more than row locks — it needs to lock the predicate or the index range, so a concurrent insert into that range is blocked or detected. Write skew and phantoms are two faces of "the invariant is over a set defined by a predicate, not over fixed rows."

6 · Three roads to serializability

What this is: three ways to make concurrent transactions equal some serial order.

Serializable isolation guarantees the outcome equals some serial execution of the transactions. Three implementation strategies dominate, trading concurrency, latency, and abort rate differently.

Actual serial execution

Literally run transactions one at a time on a single thread (VoltDB, Redis). No locks, no anomalies — trivially serializable. Viable only when transactions are short, fit in memory, and each finishes in microseconds, because there is no concurrency at all. Throughput comes from partitioning so independent partitions each get their own single thread.

Two-phase locking (2PL)

Pessimistic. Readers and writers take shared/exclusive locks and hold them until commit; predicate/index-range locks block phantoms. "Two-phase" = acquire locks (growing phase), then release all at commit (shrinking phase). Correct and classic, but locks serialize hot data, latency rises under contention, and you get deadlocks (two transactions each holding a lock the other wants) that the database resolves by aborting one.

Serializable snapshot isolation (SSI)

Optimistic. Run on top of MVCC snapshots with no locks; at commit, the engine checks whether any transaction read a premise that another transaction's write invalidated, and if so aborts the offender to retry. Great when contention is low (most transactions commit first try), since reads and writes never block. The cost is wasted work and retries when contention is high. PostgreSQL's SERIALIZABLE level is SSI.

Mapping back to the doctors: 2PL makes Bob's predicate read wait on Alice's lock, so he reads count = 1 afterward and abstains. SSI lets both run, then aborts one at commit because each read a count that the other's write changed. Serial execution never lets them overlap at all. All three preserve the invariant; they just pay for it at different times (block early, abort late, or never concurrent).

Serializability is not linearizability

They sound alike and are independent. Serializability (this lesson) is about transactions: the result equals some serial order — it says nothing about which order, and nothing about real time. Linearizability (lesson 16) is about recency on a single object: once a write completes, every later read returns that value, as if there were one up-to-date copy. A system can be serializable but not linearizable (a transaction may read a slightly stale but consistent snapshot), or linearizable but not serializable. The strongest combination, strict serializability, is both. Keep them separate: this lesson hides concurrency between transactions; lesson 16 is about freshness.

ML-infra tie — a budget/quota check is write skew

A serving platform enforces "team X's total provisioned GPUs ≤ 64". Two requests arrive concurrently, each asking for 40 GPUs. Each transaction reads "currently provisioned: 0", checks 0 + 40 ≤ 64 (passes), and inserts its own allocation row. Under snapshot isolation both pass and commit, and the team now holds 80 GPUs — write skew, because the invariant is a sum over a predicate ("rows for team X") and the two inserts are different rows (plus a phantom: each inserts a row the other's count should have seen). The cures: run the quota check at SERIALIZABLE; or materialize the running total in one row and use atomic UPDATE ... SET used = used + 40 WHERE used + 40 <= 64 so the conflict collapses to a single-row lost-update guard (§4). The same pattern covers concurrent increments to a feature counter or a rate-limit budget — decide whether your invariant is over one row (cheap atomic op) or a predicate (needs serializable).

Trade-offs

Choice	Buys	Costs / still allows
Read committed	No dirty reads or dirty writes; cheap, high concurrency (default in most DBs)	Read skew, lost update, write skew, phantoms all still possible
Snapshot isolation (MVCC)	Consistent point-in-time reads; reads never block writes; kills read skew	Lost update and write skew/phantoms remain; storage for old versions + vacuum
Atomic op / CAS / FOR UPDATE	Targeted cure for lost update on a single row	Only protects single-row invariants, not predicate invariants (write skew)
Serial execution	Trivially serializable, no locks, no anomalies	No concurrency; needs in-memory, microsecond, partitioned transactions
Two-phase locking (2PL)	Serializable, blocks phantoms via predicate/range locks	Locks serialize hot data; latency under contention; deadlock aborts
Serializable snapshot isolation (SSI)	Serializable with non-blocking reads/writes; great at low contention	Aborts and retries under high contention; wasted work

Failure modes

Assuming "repeatable read" means serializable. The SQL standard's names are muddled; most "repeatable read" levels are snapshot isolation and still allow write skew. Symptom: an invariant breaks only under concurrent writers to different rows.
Lost update under snapshot isolation. A read-modify-write counter loses increments because SI does not serialize writes by itself. Symptom: counts drift low under load, exact under single-threaded test.
Write skew on a predicate invariant. Row-level locks "looked sufficient" but the invariant spans a set (sum, count, "at least one"). Symptom: budget overshoots, zero on-call doctors, double-booked seat.
Phantom via concurrent insert. A uniqueness or "no overlap" check passes for both transactions because each inserts a row the other never saw. Symptom: two rows that should have been mutually exclusive.
Confusing the C in ACID with the database's job. Expecting the store to uphold an invariant you never declared as a constraint. Only constraints + isolation the app actually requested are enforced.
SSI retry storm. High contention turns optimistic SSI into a flood of aborts/retries; throughput collapses. Symptom: rising serialization-failure error rate under load.

Decision checklist

For each invariant: is it over one row (use an atomic op / CAS) or over a predicate / set (you need serializable)?
What isolation level does this database call its default, and which anomalies does that level actually allow?
Is any read-modify-write protected against lost update — atomic statement, FOR UPDATE, or CAS with a retry loop?
Does any check-then-act logic (quota, uniqueness, "at least one") run at SERIALIZABLE, or is the predicate materialized into a single guarded row?
If using SSI, do clients retry on serialization failure, and is contention low enough that retries stay rare?
If using 2PL, is there deadlock detection, and are transactions short enough to bound lock-hold time?
Are these even transactions on one node, or do they span shards (lesson 11)? Cross-shard serializability is far more expensive — prefer keeping an invariant's data co-located.

Checkpoint exercise

Try it

You run a feature-serving platform backed by a single relational shard. (a) A nightly job increments a per-feature access_count while online requests also increment it; name the anomaly that loses counts under snapshot isolation and give the exact UPDATE statement that fixes it without raising the isolation level. (b) Teams share a pool of 64 GPUs and you must enforce "sum of a team's active allocations ≤ 64"; two 40-GPU requests arrive concurrently — show the interleaving that overshoots under snapshot isolation, name the anomaly, and give two distinct fixes (one isolation-level, one data-model). (c) State, for each fix in (b), what it costs under high concurrency (blocking, aborts/retries, or reduced flexibility).

Where this points next

A transaction holds its invariant inside one database: atomicity, isolation, and durability all assume the work begins and ends within a single store's commit machinery. But real systems rarely end at the database edge — a committed write must also enqueue a message, fire an event, call a downstream service, or update a search index, and that second action lives outside the transaction. The instant an operation straddles the DB-and-message boundary, "all-or-nothing" stops being free: the commit can succeed while the message is lost, or the message can be delivered twice while the commit happened once. The next lesson, Messaging, Idempotency, and the Transaction Boundary (lesson 14), takes the invariants you just learned to protect within a transaction and carries them across that boundary — why at-least-once delivery forces idempotent consumers, how the dual-write problem mirrors the lost-update and write-skew anomalies one level up, and where the transactional outbox redraws the boundary so the database stays the single source of truth.

Where is truth?

For a transaction, truth is the committed state of the database — and the whole point of isolation is to keep that truth from being corrupted by concurrent observers. System of record: the committed rows in the single database/shard, ordered by the durable write-ahead log; an uncommitted write is not yet truth. Copies / derived views: the per-transaction MVCC snapshots each transaction reads from — consistent point-in-time views of truth, not truth itself — plus any uncommitted in-flight writes. Freshness budget: the isolation level is the freshness contract — read committed lets a transaction's view skew across statements, snapshot isolation freezes it at begin time, serializable admits no anomaly at all; you choose how stale a reader's view of truth may be. Owner: the transaction manager / lock manager on the owning shard, which decides commit order and resolves conflicts. Deletion path: a delete is a committed write; under MVCC the old version lingers until a no-live-transaction-can-see-it garbage collector (vacuum) reclaims it. Reconciliation / repair path: conflict handling — 2PL blocks the conflicting reader, SSI aborts and retries the offender, atomic ops/CAS collapse a read-modify-write into one guarded step — so that the committed state always equals some serial order. Evidence it is correct: the declared invariants and constraints hold over committed state, no anomaly (lost update, write skew, phantom) is observable, and the serialization-failure/abort rate stays bounded under load.

Takeaway

A transaction lets the application pretend chosen concurrency and crash faults did not happen. ACID is atomicity (all-or-nothing, built on the log), consistency (the application's invariant, only enforced where you declared constraints), isolation (the interesting one), and durability (committed writes survive crashes). Isolation is a ladder: read committed kills dirty reads and dirty writes but allows read skew; snapshot isolation (via MVCC — each transaction reads a consistent point-in-time snapshot) kills read skew but still allows lost update (fix with an atomic op, FOR UPDATE, or compare-and-set) and the subtle write skew and phantoms, where two transactions read an overlapping predicate, each pass a check, and jointly break an invariant by writing different rows. Only serializable isolation forbids those, implemented by serial execution, two-phase locking (pessimistic, blocks, deadlocks), or serializable snapshot isolation (optimistic, aborts and retries). The engineering judgment: decide whether each invariant lives in one row (cheap guard) or over a predicate/set (serializable), and never assume "repeatable read" is serializable — it usually is not.

Interview prompts

Define each letter of ACID, and say which one is not really the database's job. (§1 — atomicity = all-or-nothing/abortability; consistency = the app's invariant, enforced only via declared constraints; isolation = hide concurrent interleavings; durability = committed writes survive crashes. The C is the application's responsibility.)
What anomaly does read committed still allow, and what fixes it? (§2–3 — it prevents dirty reads/writes but allows read skew / non-repeatable reads; snapshot isolation, which gives each transaction a consistent point-in-time snapshot via MVCC, fixes it.)
What is MVCC and how does it implement snapshot isolation? (§3 — multi-version concurrency control keeps multiple versions of each row tagged by transaction id; a transaction reads the newest version committed before it began, so reads never block writes and see one consistent point in time.)
Why doesn't snapshot isolation prevent lost updates, and how do you fix one? (§4 — both transactions read the same snapshot and write back, erasing one update; fix with an atomic SET x = x + 1, SELECT ... FOR UPDATE, or compare-and-set with a retry loop.)
Explain write skew with an example, and why row locking the written row is insufficient. (§5 — two transactions read an overlapping predicate, each pass a check, then write different rows that jointly break the invariant (on-call doctors → zero on call); the invariant is over a predicate/set, so locking each written row protects nothing — you need serializable / predicate locks.)
What is a phantom and why does it force serializable isolation to lock more than rows? (§5 — a row another transaction inserts that would match your search predicate; the row doesn't exist when you'd lock it, so serializable needs predicate or index-range locks to block/detect the insert.)
Name the three ways to achieve serializability and their cost profiles. (§6 — serial execution (no concurrency, in-memory short txns); two-phase locking (pessimistic, blocks hot data, deadlock aborts); serializable snapshot isolation (optimistic, non-blocking, aborts/retries under contention).)
An ML quota check lets two concurrent requests overshoot a budget — diagnose and fix. (§5 ML tie — write skew (a sum over a predicate, two inserts of different rows); fix by running the check at SERIALIZABLE, or materialize the running total into one row and guard it with an atomic UPDATE ... WHERE used + n <= cap.)