Transactions, ACID, anomalies, and isolation levels
Running transactions one at a time is always correct and always slow. Interleaving them reclaims throughput but lets some wrong answers leak through. This lesson is a catalogue of exactly which interleavings are wrong, a single graph test that decides correctness, and the isolation levels that name how much wrongness you are willing to permit.
By the end you can
- State each ACID guarantee and say which engine subsystem actually delivers it.
- Recognise dirty write, dirty read, non-repeatable read, phantom, lost update, and write skew from their operation traces.
- Build a precedence graph for a schedule and use acyclicity to decide conflict serializability.
- Separate the serializability axis from the recoverability axis (recoverable, cascadeless, strict).
- Explain why 2PL gives conflict serializability, why strict 2PL is needed on top, and why snapshot isolation is neither above nor below Repeatable Read.
- Answer the standard traps: levels are defined by phenomena not locking, serializable does not mean serial, a phantom is not a non-repeatable read.
Where this sits in the engine
The first eleven weeks followed one read down the stack:
SELECT name FROM emp WHERE salary > 75000 ORDER BY name, from the parser
(week 8) through the optimizer (week 11)
to the executor, the B+tree, the buffer pool, and the slotted page. A read can be careless about other
transactions because it does not change anything. This week starts the second journey, the one a write forces
you to confront. The running statement becomes a transaction:
BEGIN;
UPDATE account SET balance = balance - 100 WHERE id = 42;
COMMIT;The layer above is the query processor, which has already turned this into a plan that locates the row for id 42 exactly as journey 1 located its tuples (optimizer, access method, buffer, storage). What this layer adds is the question that plan never had to ask: while this transaction runs, other transactions are touching the same rows, and the machine can crash. This week (week 12) frames the problem and the correctness theory. It hands down to week 13 the mechanisms that enforce it (strict 2PL, the lock manager, MVCC), and those hand down to week 14 the logging that makes a committed write survive a crash. Atomicity and durability are mostly week 14's job. Isolation, the property that concurrency control delivers, is the subject here.
Think of a transaction as a single edit to the database that must look instantaneous from the outside, even though inside it is many small steps. The database wants to run several such edits at once so the CPU is not idle while one of them waits on disk. The danger is that two edits, interleaved, can land on a result that neither could have produced if it had run alone. The whole job of this lesson is to catalogue those bad landings and find a cheap test that spots them.
ACID: four guarantees against two threats
A transaction is a unit of work the database promises to treat as one logical step although it is built from many physical ones: read this page, write that row, append this log record. Two things threaten that promise. Failures: the machine crashes halfway through. Concurrency: other transactions run at the same time and touch the same data. ACID is the name for the four guarantees that close those threats. The thing worth carrying away is which subsystem each one belongs to, because they are not all the same machinery.
| Letter | Guarantee | Delivered by |
|---|---|---|
| Atomicity | All of a transaction's effects happen, or none do. | The log and the abort/undo path (week 14), not locking. |
| Consistency | Each transaction moves the database between states that satisfy declared rules. | Partly the application's logic, partly declared constraints the engine checks. The weakest engine guarantee. |
| Isolation | Concurrent transactions produce a result equal to some serial order. | Concurrency control (this week and week 13). |
| Durability | Once committed, effects survive a crash. | Write-ahead logging plus forcing the log at commit (week 14). |
The C in ACID is not the same property as serializability, and it is the weakest of the four as an engine
guarantee. The engine cannot know your application's intended invariants beyond the constraints you declared
(a CHECK, a foreign key, a unique index). Atomicity and durability come from the log; isolation
comes from concurrency control. Only isolation is really about the interleaving of transactions, which is why
this whole lesson is about isolation and the other three letters are handled elsewhere.
Run transactions strictly one at a time and you get isolation for free: there is no interleaving to go wrong. But a transaction that blocks on a disk read would idle the whole CPU while it waits, and disk is five to six orders of magnitude slower than memory (week 4). Interleaving lets one transaction use the CPU while another waits on I/O. That throughput is the entire reason concurrency control exists. We accept interleaving and then forbid exactly the interleavings that produce wrong answers.
The catalogue of wrong answers
Every anomaly below is one shape: an interleaved schedule producing a result that no serial order could.
The notation follows the critique paper [Berenson et al. 1995].
w1[x] is transaction 1 writing item x, r2[x] is transaction 2 reading x,
c1 is transaction 1 committing, a1 is transaction 1 aborting.
| Anomaly | Trace | What breaks |
|---|---|---|
| Dirty write (P0) | w1[x] w2[x] c1 c2 | Two transactions' writes to x interleave, so rollback cannot restore a clean before-image. Forbidden at every level. |
| Dirty read (P1) | w1[x] r2[x] a1 | T2 reads a value T1 wrote then never committed. T2 saw something that officially never existed. |
| Non-repeatable read (P2) | r1[x] w2[x] c2 r1[x] | T1 reads x twice and gets two different committed values inside one transaction. |
| Phantom (P3) | r1[P] w2[y in P] c2 r1[P] | T1 re-runs a predicate query and the set of matching rows changed. A row appeared or vanished, not just a value. |
| Lost update | r1[x] r2[x] w1[x] w2[x] | Both read 10, both compute 11, both write 11. One increment is silently discarded. |
| Write skew (A5B) | r1[x] r1[y] r2[x] r2[y] w1[x] w2[y] | Each transaction reads an overlapping set, checks a constraint that holds, then writes a different item. Individually fine, together a violation. |
A non-repeatable read is a changed value of a row T1 already saw. A phantom is a changed set of rows matching a predicate, because someone inserted or deleted a matching row. The distinction matters because preventing phantoms needs predicate or gap locking, not just locking the rows that currently exist. There is no existing row to lock for a row that does not exist yet. This is exactly why Repeatable Read can forbid P2 yet still permit P3.
Write skew is the subtle one and the one the critique paper uses as its headline result. The textbook case: two doctors are on call, a rule says at least one must stay on call. Both read "two on call, fine," each takes themselves off, and now zero are on call. There was no write-write conflict on a single item (each wrote a different doctor's row), so a rule that only watches single-item write conflicts will never catch it. Hold that thought; it is what breaks snapshot isolation below.
Serializability, and the graph that tests it
We want a precise target, not a vibe. A schedule is serializable if its final effect equals some serial schedule of the same transactions. That is the correctness goal. The trouble is that "equal effect" over all possible data is expensive to reason about, so engines test a sufficient proxy that is cheap to check.
Two operations conflict when they come from different transactions, touch the same item, and at least one is a write. The three conflict types are write-read, read-write, and write-write. A schedule is conflict-serializable if you can turn it into a serial schedule by repeatedly swapping adjacent non-conflicting operations. This is sufficient for serializability and, unlike view serializability (which is NP-complete to test and so never used), it is decidable in polynomial time.
Build a directed graph, one node per transaction. Draw an edge from Ti to Tj whenever an operation of Ti conflicts with and precedes a later operation of Tj on the same item. The schedule is conflict-serializable if and only if this precedence graph is acyclic. A topological sort of an acyclic graph gives an equivalent serial order. A cycle means no serial order exists.
Simulator: build a schedule, watch the precedence graph
Pick a preset anomaly or drag your own operations onto the shared timeline. The tool draws the precedence graph live and colours it green when acyclic (with the equivalent serial order shown) or red when a cycle appears (with the conflicting edges highlighted). A second readout classifies the schedule on the independent recoverability axis. Try the write-skew preset: you will watch it form a two-node cycle even though no two operations write the same item.
The second axis: recoverability
Serializability is about correctness under concurrency. Recoverability is a separate concern about correctness under aborts, and the two are independent: a schedule can be serializable but not recoverable, and vice versa. Three nested classes, each stronger than the last.
- Recoverable. A transaction commits only after every transaction whose data it read has already committed. If T2 read T1's write, T2 must not commit before T1. Otherwise T1 aborts and you have a committed transaction that read a value that was rolled back, which you cannot undo. Every real system requires at least this.
- Cascadeless (avoids cascading aborts). Transactions read only values written by already committed transactions. This stops one abort from forcing a chain of dependent aborts. Stronger than recoverable.
- Strict. No transaction reads or overwrites an item until the transaction that last wrote it has committed or aborted. This makes undo trivial: the before-image to restore is always the value that existed before this transaction's write. Strict 2PL produces strict schedules, which is why production locking systems use it.
The containment is strict ⊂ cascadeless ⊂ recoverable. In the simulator, the dirty-read and recoverable-but-not-serializable presets are the ones to study: they show that a schedule can sit anywhere on one axis independent of the other.
"Recoverable implies serializable" and "serializable implies recoverable" are both false. They are independent axes. Recoverability constrains commit order relative to reads. Serializability constrains the equivalent serial order. A schedule can satisfy one and violate the other.
Two-phase locking: how you actually get serializability
The precedence graph tells you whether a finished schedule was serializable. It does not tell you how to make the scheduler produce only good ones as it runs. The dominant lock-based answer is two-phase locking. Each transaction obeys one rule with two phases.
- Growing phase. The transaction may acquire locks but may not release any.
- Shrinking phase. Once the transaction releases its first lock, it may release more but may not acquire any. The instant it holds all its locks, just before the first release, is the lock point.
Order the transactions by their lock points. Suppose Ti has an operation that conflicts with and precedes Tj's on some item. Then Ti held the lock on that item before Tj could acquire it, so Ti's lock point comes before Tj's. Every precedence-graph edge therefore points in lock-point order, which means the graph cannot contain a cycle. An acyclic graph is conflict-serializable. The lock-point order is itself a valid serial order. The rule is sufficient, not necessary: some conflict-serializable schedules cannot be produced under 2PL [CMU 15-445 notes].
Plain 2PL still allows dirty reads and cascading aborts, because a transaction can release a write lock during its shrinking phase and commit later. Another transaction can read that just-unlocked but uncommitted value. Two stronger variants close the gap, and they are what production systems run.
| Variant | Lock-holding rule | What it buys |
|---|---|---|
| Plain 2PL | Two phases, but locks may be released before commit. | Conflict serializability only. Still allows dirty reads and cascading aborts. |
| Strict 2PL | Hold all exclusive (write) locks until commit or abort. | Adds recoverability and cascadelessness; produces strict schedules. |
| Rigorous 2PL | Hold all locks, shared and exclusive, until commit or abort. | Serialization order equals commit order; the shrinking phase collapses to one instant. |
2PL does not by itself prevent deadlock: two transactions can each hold a lock the other wants. PostgreSQL detects deadlocks with a waits-for graph and aborts a victim rather than preventing them up front [PG Explicit Locking]. The lock manager itself is a hash table keyed by object id, each entry holding a granted-modes set and a FIFO wait queue, protected by latches (short mutexes, distinct from locks). All of that mechanism is week 13.
Isolation levels: choosing how much wrongness to permit
Strict 2PL gives you serializability, but it is expensive: readers and writers block each other. Most applications do not need full serializability for every statement, so SQL defines weaker levels. The defining insight of the ANSI standard, and the central correction in the critique paper, is that the levels are defined by which phenomena they forbid, not by which locking they use. An implementation is free to forbid more than the floor requires.
| Level | Dirty read | Non-repeatable read | Phantom | Write skew |
|---|---|---|---|---|
| Read Uncommitted | possible | possible | possible | possible |
| Read Committed | no | possible | possible | possible |
| Repeatable Read | no | no | possible (ANSI) | possible |
| Serializable | no | no | no | no |
| Snapshot isolation | no | no | no | possible |
Notice the snapshot-isolation row. It forbids dirty reads, non-repeatable reads, and even phantoms, yet it permits write skew. That single cell is why SI does not fit on the ANSI ladder at all.
Under SI each transaction reads from a consistent snapshot taken at its start, so it never sees another transaction's in-progress or concurrently-committed changes. Write conflicts are resolved by First-Committer-Wins: if two concurrent transactions wrote the same item, the first to commit wins and the second aborts. But First-Committer-Wins only catches write-write conflicts on the same item. Write skew is two transactions writing different items after reading an overlapping set, so there is no write-write conflict to catch, even though the precedence graph has a cycle. SI therefore forbids the ANSI phantom yet permits an anomaly Serializable forbids, which makes it incomparable with Repeatable Read, not simply above or below it [Berenson et al. 1995, section 4.2].
Simulator: does this level block this anomaly?
Pick an isolation level and an anomaly. The tool runs the canonical two-transaction script under that level's rules and shows, step by step, whether the anomaly is blocked or slips through. Fill in the whole grid and you reproduce the table above, including the cell where snapshot isolation breaks on write skew while ANSI Serializable does not.
PostgreSQL exposes all four ANSI levels but implements only three: its Read Uncommitted behaves exactly like Read Committed, so dirty reads are impossible at any level. Read Committed (the default) takes a fresh snapshot per statement; Repeatable Read is snapshot isolation taken once at transaction start (and, unlike bare ANSI, it does not show phantoms); Serializable is Serializable Snapshot Isolation, which adds dependency checks on top of SI and aborts transactions forming a dangerous structure [PG Transaction Isolation]. SQLite reaches serializability by the opposite route: it allows only one writer at a time, and WAL mode gives readers a snapshot so they do not block that writer [SQLite isolation].
What this hands down
This lesson set the target (serializability), the test (the acyclic precedence graph), the second axis
(recoverability), and the vocabulary of phenomena and levels. It did not build the machinery that enforces any of
it at runtime. Week 13 picks up exactly there: the lock manager and the
S/X compatibility matrix that implement 2PL, deadlock detection versus prevention, and MVCC, which delivers
snapshot isolation by keeping old row versions so readers never block writers. When you see PostgreSQL stamp a
tuple's xmin and xmax next week, remember that the visibility rule it computes is just a
mechanical way of giving each transaction the snapshot this lesson described.
Check yourself
Which statement about the ANSI SQL isolation levels is false?
The levels are defined by forbidden phenomena, not by an implementation. The whole point of the critique paper is that the phenomenon definitions are implementation-independent (and were originally ambiguous, which is why P0 dirty write was added). PostgreSQL and a lock-based engine can both be Serializable by completely different mechanisms.
Snapshot isolation differs from Serializable because it:
SI reads from a frozen snapshot, so it forbids dirty reads, non-repeatable reads, and phantoms. Its one gap is write skew: First-Committer-Wins only catches two writes to the same item, and write skew writes different items, so no conflict is detected even though the precedence graph cycles. That is why SI is incomparable with Repeatable Read rather than strictly stronger.
A schedule's precedence graph is acyclic. Which conclusion is correct?
Acyclic precedence graph if and only if conflict-serializable, and any topological order is an equivalent serial schedule. Recoverability is a separate axis (an acyclic graph can still be unrecoverable), and 2PL is sufficient but not necessary, so the schedule need not come from 2PL.
Which statement about two-phase locking is false?
Plain 2PL only guarantees conflict serializability. It may release a write lock during the shrinking phase before commit, which permits a dirty read and therefore a cascading abort. You need strict 2PL (hold write locks to commit) to get cascadeless, strict schedules. The other three are true.
"Serializable" isolation means:
Serializable constrains the result, not the execution. PostgreSQL's Serializable runs transactions concurrently and only aborts the ones whose interleaving could not match any serial order. Confusing "serializable" with "serial execution" is the classic trap.
A non-repeatable read and a phantom both involve a re-read returning something new. The difference is:
A non-repeatable read is a changed value of a row you already saw. A phantom is a changed set of matching rows (an insert or delete). The practical consequence is that stopping phantoms needs predicate or gap locking, not just row locks, which is why Repeatable Read can forbid P2 yet allow P3.
Active recall
The source for P0 dirty write, the phenomenon-based level definitions and their original ambiguity, snapshot isolation with First-Committer-Wins, write skew (A5B), and the argument that SI is incomparable with Repeatable Read. Focus on sections 3 and 4 and the level-comparison figure.
Want me to walk a specific schedule through the precedence graph by hand, derive the 2PL lock-point argument more slowly, or show the exact PostgreSQL error string a serialization failure raises? Ask me to go deeper, draw it differently, or quiz you harder. I am your teacher for this course, not just a document.