Transactions, isolation and MVCC

Why did two customers get the last thali?

The festival thali is back, and this time the stock count lives in the database instead of the accountant’s notebook. There are five hundred thalis. The order code does what any careful person would do: read the stock, check it is above zero, then write back one less.

At 11:58 the count reaches one. At 11:58 and two seconds, two customers tap Order.

Both orders read the stock. Both see 1. Both write 0. Both get “Confirmed”. The kitchen screen shows two orders for a thali that exists once. The stock says zero, the orders say two were sold, and the database did exactly what it was told, twice.

That evening a second report arrives, from a different corner of the system. The kitchen has one rule for Sundays: at least one of its two cooks is on duty. The duty app checks it. One cook asked for Sunday off, and the app checked that the other was on. The other cook asked at the same moment, and the app checked that the first was on. Each request checked the rule correctly against what it saw, both were approved, and now nobody cooks on Sunday.

Both pieces of code ran inside transactions, and most people expect a transaction to prevent exactly this. It promises less than that, and how much less depends on a setting most teams never change: the isolation level.

Before reading on, write down the one SQL statement that would have stopped the double sale.

Pause and predict Both orders ran inside transactions, read 1 and wrote 0. What would have stopped the double sale?

What a transaction promises, and what it does not

A transaction groups several reads and writes into one unit. The promise is usually summarised as ACID. Each letter is narrower than its name suggests.

Pause and predict The two thali orders each read stock 1 and wrote 0, and both committed. Which letter of ACID let them down?

Isolation level

A setting that says which kinds of interference between concurrent transactions the database will prevent. Weaker levels allow more interference and block less.

For example: BEGIN ISOLATION LEVEL REPEATABLE READ; PostgreSQL’s default is Read Committed; MySQL’s InnoDB defaults to Repeatable Read.

The kinds of interference have names. Learn these five and most concurrency bugs you will ever meet become recognisable:

• Dirty read: reading a value another transaction wrote but has not committed, and may still roll back.
• Non-repeatable read: reading the same row twice in one transaction and getting two values, because someone committed in between.
• Phantom: running the same query twice and getting a different set of rows, because someone inserted or deleted matching rows.
• Lost update: two transactions read a value, both compute a new one, and the second write silently overwrites the first. This is what happened to the last thali.
• Write skew: two transactions read the same facts, each changes a different row, and together they break a rule that each one checked. This is what happened to the Sunday cooks.

A mental model

A paper ledger has the same problem, and bookkeepers solved it long before databases did.

MVCC (multi-version concurrency control)

The database keeps old versions of a row alongside new ones. Each transaction reads the versions that were committed when it began, so readers never block writers and writers never block readers.

For example: In PostgreSQL every row version carries xmin (the transaction that created it) and xmax (the one that deleted or replaced it). An UPDATE writes a new version and stamps the old one’s xmax.

MVCC is why Repeatable Read is cheap in PostgreSQL: a whole-transaction snapshot is a rule about which versions to read, and no data is copied. Writes are where transactions still collide, because two of them cannot both own the newest version of one row.

The matrix, and what PostgreSQL really does

Running every story at every level gives this table. It is computed by the same simulator you used to watch two transactions collide, and it matches PostgreSQL’s documented behaviour.

• Read Uncommitted is the standard’s lowest level. MySQL implements it and allows dirty reads. PostgreSQL accepts the name but runs Read Committed, so a dirty read cannot happen there at all.
• Read Committed takes a fresh snapshot for every statement. When an UPDATE finds a row another transaction is changing, it waits; if that one commits, PostgreSQL re-checks the WHERE clause against the new version and proceeds. The re-check covers only the WHERE clause. If your code read the stock earlier and computed the new value itself, the UPDATE writes that stale value and the other order’s change is lost. That is the lost update.
• Repeatable Read in PostgreSQL is snapshot isolation: one snapshot for the whole transaction. If you try to change a row that someone committed after your snapshot, you get ERROR: could not serialize access due to concurrent update and must retry. The lost update is caught. Write skew is not, because the two transactions changed different rows.
• Serializable in PostgreSQL is Serializable Snapshot Isolation (SSI, Ports and Grittner, 2012). It tracks which transaction read what the other wrote, and when the pattern could not come from any one-at-a-time order, it rolls one back with SQLSTATE 40001.

Row versions, by hand

Here is the thali row after the first order (transaction 815) commits, while the second order’s Repeatable Read transaction (814, which started earlier) is still open. The transaction numbers are illustrative.

Transaction 814 keeps reading stock 1, because that is the version its snapshot shows. When it tries to write, the database sees that the newest version was created by a transaction outside its snapshot, and refuses. The old version stays on disk until no open snapshot can see it; then VACUUM reclaims the space. A transaction left open for hours holds every old version it might need, and tables bloat.

The cost of a lock, in orders per second

A row lock serialises everyone who wants that row. If an order holds the thali row’s lock for 200 ms (because the transaction also waits for a payment call), at most 1 / 0.2 = 5 orders a second can buy that dish. Keep the transaction to 5 ms of database work and the same row allows 200 a second.

Lock first, or check at the end?

Three fixes work for the thali. Two of them, locking the row and the conditional update, are the usual choice, and each serves a different goal.

The conditional update works at Read Committed because of the re-check you saw in the numbers: when the second UPDATE waits behind the first and the first commits, PostgreSQL re-evaluates stock > 0 against the new version, finds it false, and changes zero rows. The general form of the same idea is a version column (WHERE id = $1 AND version = $2), which compares and sets any row. The third fix, Serializable, also works, but it is the right tool for the Sunday rule, where the invariant spans two rows and no single UPDATE can check it.

What to remember

1. ACID’s I comes in several levels, and the default level allows some anomalies. Know your database’s default (PostgreSQL: Read Committed; MySQL InnoDB: Repeatable Read) and what it allows.
2. Learn the anomalies by name: dirty read, non-repeatable read, phantom, lost update, write skew. Read-then-write code invites the last two.
3. MVCC keeps row versions so readers never block writers; a snapshot is a rule about which versions you see. Old versions wait for VACUUM.
4. Fix a lost update with a lock (FOR UPDATE), a conditional update, or a version check; fix write skew with Serializable or by locking every row the rule reads.
5. Keep transactions short, lock rows in one agreed order, and retry when the database reports a serialization error.

If your code reads a value and then writes it back, make the database do the check inside the write.

In the real world

The simulator models two transactions and one rule per level. Real engines add details that matter in production: PostgreSQL’s Serializable can abort a transaction for a dependency that turned out to be harmless (a false positive), predicate locks track ranges of rows as well as single rows, and InnoDB uses gap and next-key locks to block inserts into ranges a transaction has scanned. DDIA chapter 7 walks through all of these with the same anomalies you met here.

The stock now drops with one statement, and the duty app retries when the database says no. In lesson 2.4 the monthly report is too slow, which is a different problem: how the database finds the rows.