Transactions Primer

Atomicity and durability are one mechanism, so take them together. Before any data page is touched, the engine appends a record describing the change to the write-ahead log. The log is the transaction; the pages are a cache of it, and they can be written whenever.

Two transactions interleave on one log below. The record being appended is the one the clock is on, and once T1's COMMIT record lands, everything of T1's behind it is durable. Play it through:

Notice that the data page never reaches the disk — it changes in RAM and stays there. Durability arrives at the COMMIT record and nowhere else: one sequential fsync makes the whole transaction survive. T2 has two records on the same log and no commit record, so as far as recovery is concerned T2 never happened.

That is the invariant recovery runs on: a transaction took effect if and only if its commit record is on disk. Drag the crash marker back through the log and watch the redo set and the undo set reshuffle:

At five records T1's two updates are on disk and its COMMIT is not, so all three surviving updates are undone and the client — who never got an acknowledgement — is right to assume nothing happened. Move one record further and the same two updates are redone instead. ARIES (Mohan, 1992) is that rule plus the bookkeeping to restart a recovery that itself crashed.

Durability costs one fsync per commit, and where that fsync has to reach decides the ceiling. Each rung below is the one above it plus another place the bytes must land, and the rungs already paid for stay lit. Walk down it:

The step worth memorising is the third rung to the fourth: a local NVMe fsync is 50 µs and one on a network disk is 700 µs, with the cheaper rungs already paid inside both. Same code, same query — fourteen times the wait, and one connection committing in series lands 20,000 commits a second against 1,429. Nothing above that rung is a database problem; it is a storage problem, and no SQL tunes it away.

So people turn the dial. synchronous_commit = off returns from COMMIT before the flush, and PostgreSQL then flushes at most three wal_writer_delay cycles late — 600 ms at the default. Raise the commit rate and watch the window fill:

At 5,000 commits a second the window holds 3,000 transactions the application was told had committed. They fail silently: no error, no rollback, no log line — the rows are simply not there after the restart. That is the failure that reaches a customer.

The C is the letter people overestimate. A database enforces what you declared — CHECK, foreign keys, UNIQUE, NOT NULL — and nothing else. Move the transfer past 120 to make the declared constraint fire, then switch to writing only one leg:

The two failures do not look alike. The CHECK rejects the statement: an error code, a rolled-back transaction, a stack trace somebody will read. The broken sum raises nothing at all, because a + b = 200 was never declared to anyone. ACID's C is your invariants holding across the transaction; the engine only helps with the ones you wrote down.

Which brings the four letters together. Every knob below trades one of them for throughput, latency or convenience. Walk the knobs and watch the letter each one weakens:

Two of these are defaults rather than decisions. PostgreSQL ships on READ COMMITTED and MySQL InnoDB on REPEATABLE READ, so unless your code asked for something stronger, the I in your ACID is already turned down — and unlike the durability knobs, nobody turned it down on purpose. That is the dial the next section is about.

All five have the same shape: two transactions, one clock, and one thing that should not have been visible. Every figure in this section is that drawing — two lanes carrying the operations each transaction issues, and a clock you walk with the track under the stage. Behind the clock, what already happened stays lit.

The cheapest one first. T1 reads a row that T2 has written and not committed, and T2 then rolls back. Press play and step through it:

Notice T1 did not read a stale value. It read a value that never existed in any committed state — there is no moment, before or after, at which the answer it acted on was true. Everything above READ UNCOMMITTED blocks this, and PostgreSQL blocks it even when you ask for READ UNCOMMITTED: it has no such level and silently gives you READ COMMITTED, so the dirty read is the one anomaly nobody can buy there.

READ COMMITTED buys exactly that and nothing more. Each statement gets a fresh snapshot, so one row read twice inside one transaction can come back with two different values:

Notice that nothing errors. T1 simply computes with two mutually inconsistent readings of one row — which is how a report footer disagrees with its own rows. REPEATABLE READ fixes it with one snapshot for the whole transaction rather than one per statement.

The same problem has a second shape, and the standard counts it as a separate hazard: not a row that changed, but a row that appeared inside a range T1 had already counted. Walk the clock:

The standard's REPEATABLE READ allows the phantom, because a read lock can only be taken on rows that already exist. A snapshot has no such limit — which is why PostgreSQL's REPEATABLE READ, really snapshot isolation, blocks the phantom its own name permits. InnoDB gets there with gap locks on the index range.

Now the one that actually ships, and it lives in application code rather than in SQL. Two transactions read the same balance, each subtracts from what it read, and each writes the result back:

Notice that both commits succeeded and both callers were told their withdrawal went through. The row holds 90 where it should hold 60, and the missing 30 raised nothing anywhere. That is a lost update — most often introduced by an ORM that reads an object, mutates a field and saves it.

The last one is subtle enough to survive snapshot isolation completely. Two transactions read the same two rows, each concludes its own write is safe, and each writes a different row:

Because they wrote different rows there is no write-write conflict for MVCC to catch: each write is legal on its own, and the invariant is broken only by the pair. Seeing that requires tracking what each transaction read, not what it wrote — which is exactly what serializable snapshot isolation adds on top, and exactly what nothing weaker can do.

Five anomalies, four levels, and three engines that disagree about what the levels mean. Walk the level and switch the engine underneath it:

The divergences are the load-bearing part. On REPEATABLE READ PostgreSQL does not block a lost update, it aborts you with SQLSTATE 40001 and expects a retry loop; InnoDB, on the same level and the same anomaly, lets the write through in silence, because a locking read takes the latest committed row rather than the snapshot. One fails loudly, one quietly, on identical code.

Which makes the fix a choice of spelling, not a choice of level. All four of these take 30 and 10 out of the same 100, on the same engine, at whatever level you already have; only the first loses one of the two withdrawals.

-- 1  read, then write → 90
T1: SELECT bal FROM acct WHERE id = 1;   -- 100
T2: SELECT bal FROM acct WHERE id = 1;   -- 100
T1: UPDATE acct SET bal = 70 WHERE id = 1;
T2: UPDATE acct SET bal = 90 WHERE id = 1;

-- 2  atomic UPDATE → 60
T1: UPDATE acct SET bal = bal - 30 WHERE id = 1;
T2: UPDATE acct SET bal = bal - 10 WHERE id = 1;

-- 3  FOR UPDATE → 60
T1: SELECT bal FROM acct WHERE id = 1 FOR UPDATE;
T2: SELECT bal FROM acct WHERE id = 1 FOR UPDATE;
--  T2 waits for T1's COMMIT, then reads 70

-- 4  SERIALIZABLE → 60
BEGIN ISOLATION LEVEL SERIALIZABLE;
  SELECT bal FROM acct WHERE id = 1;
  UPDATE acct SET bal = 70 WHERE id = 1;
COMMIT;  -- loser raises 40001; retry the block

The difference is where the subtraction happens. Spelling 1 does it in the application and sends a literal; the other three either send the subtraction itself, or make the second reader wait, or make the second committer fail. Switch between them and read the balance each leaves:

Only the first is wrong, and it is wrong in the way that survives review: it reads, computes in the application, and writes a literal. The other three never let two transactions compute from one starting value — one by never reading it, one by holding the row lock until commit, one by aborting the loser and retrying.

That last one is not free. If a commit conflicts with probability p, attempts are geometric, so landing one commit costs 1/(1−p) of them. Raise the conflict probability:

At p = 0.50 every commit costs two attempts and half the useful work is thrown away; at p = 0.90, ten attempts and ninety per cent. Ports and Grittner measured PostgreSQL's SSI within a few per cent of plain snapshot isolation on a read-mostly benchmark: the overhead is the aborts, not the bookkeeping, and the abort rate is a property of your workload.

The rule is: never overwrite a row. An UPDATE creates a new version and marks the old one dead; a DELETE only marks. So every version carries two hidden columns — xmin, the transaction that created it, and xmax, the transaction that killed it, zero while it is still live.

Drawn on the transaction-id axis, a version is an interval: it exists from its xmin to its xmax. Your snapshot is a vertical line, and the version it crosses is the one you read. Drag it across:

Notice how little work that is. No lock, no wait, no coordination with any writer — a read is two integer comparisons per version, and two transactions reading the same row at different snapshots land on different versions without either of them knowing the other exists.

Those two comparisons are the whole rule, and it is stated as a loop assertion: a version is visible when its creator committed before your snapshot and its deleter did not. Move the snapshot, then change what the writing transaction did:

Set the writer to still running and the version disappears even though xmin is below the snapshot: committing is what counts, not writing. Set it to aborted and it disappears permanently — which is how a rolled-back transaction leaves versions on disk that no snapshot, present or future, will ever be entitled to.

Nobody will ever see them, and they are still there. That is MVCC's bill: a dead version per update, in the same 8 KiB page as the live one. Raise the update count and fill the page:

Because a sequential scan reads every one of them, the bill lands on every query, not just the writes. At 27 updates the table holds one live row and 27 dead ones, and the scan pays 28 times the bytes for the same answer. That is bloat: it never errors, so it is found on a latency graph rather than in a log.

VACUUM is the collector, and it has one rule it may not break: a version can only go once no running snapshot could still want it. Drag the horizon back and empty the reclaimable set:

Because the horizon is the oldest running snapshot, one connection sitting in idle in transaction leaves every dead version behind it pinned for the whole cluster. Autovacuum keeps running, frees nothing, and the table grows anyway. That is why idle_in_transaction_session_timeout exists, and why a forgotten transaction is a storage incident, not a connection leak.

There is a second clock and it is harder. Transaction ids are 32 bits, and each one can only see 2³¹ ids behind it, so the usable space is finite. Spend it:

Watch the last two thresholds arrive together. PostgreSQL forces autovacuum at autovacuum_freeze_max_age — 200 million by default — starts warning at 40 million remaining, and at three million shuts the cluster down rather than let it wrap. At 5,000 write transactions a second, 40 million ids is 2.2 hours: the warning window is one on-call handover, not one sprint.

Every MVCC engine runs up the same bill and they differ only in where the dead versions are kept, next to or away from the live row. Walk the four:

PostgreSQL keeps the dead versions in the table, which is why "bloat" is PostgreSQL vocabulary. InnoDB and Oracle use an undo log, moving the symptom to a growing undo space and to Oracle's ORA-01555 snapshot too old. SQL Server uses tempdb. What breaks it is the same everywhere: a reader that stays open too long.

Our request has to charge a card, reserve stock, send a mail and write an audit row. Four systems, one "commit". One coordinator asks all of them first and tells them afterwards, which is two network round trips instead of one fsync.

Two phases: PREPARE, in which each participant writes its changes durably and votes, and then the decision going back out. Play it through:

Notice what a yes vote costs. A participant that has voted has written its changes to its own log and taken every lock it needs, and may neither commit nor abort on its own — it is waiting for one message. In PostgreSQL that is a prepared transaction, and it pins the vacuum horizon from §03 as well as the rows.

That window is the whole objection. Drag the coordinator's crash along the protocol and find the interval where no participant can recover on its own:

Before anyone has voted a timeout is safe, because nothing is durable and everyone can abort. After the decision is durable, recovery replays it. Between the vote and the decision there is no safe unilateral choice, so the participants hold their locks until an operator intervenes — and every transaction wanting those rows queues behind them.

So modern systems give up atomicity across services and buy it back with compensations: each step is a local transaction and each has an inverse. Choose which step fails:

There are no distributed locks and no in-doubt state — and no atomicity either. Between the charge and its compensation the outside world can see a customer who paid for nothing. A saga does not remove that window; it makes it short and makes it yours, and the compensations are business logic written alongside the forward path.

It also makes every step retryable, which means every step must be idempotent. Retry the charge, with and without a key the receiver can deduplicate on:

Without the key, a retry after a timeout is indistinguishable from a new request and the customer is charged once per attempt. The key is not an optimisation — it is what makes at-least-once delivery safe to build on, and it belongs in the request from the API's first version, because adding it later means reconciling the charges made without it.

Sagas coordinate services; replication coordinates copies, and there the answer is a majority. Choose the group size and how many are down:

A quorum is ⌊n/2⌋+1, so five nodes tolerate two failures and seven tolerate three. Even sizes buy nothing: six nodes also tolerate two and pay one more replica on every write. That is the whole reason cluster sizes in the wild are odd numbers.

The cost is latency, and geography decides it rather than code. Move the far replicas and read the commit off the second-nearest one:

Notice that one nearby follower is not a quorum: the leader still needs a second yes, so it pays the second-nearest round trip and the ones past the quorum cost nothing. With the far replicas across an ocean the network alone costs 70 ms and one serial writer tops out at 14 commits a second. Spanner pays that and adds a commit wait of about 2ε — roughly 10 ms — so its timestamps are ordered globally.

And when the network splits, the majority rule decides for you. Drag the partition across the group, then switch what the minority side is allowed to do:

That is CAP, and it is a choice about the minority side only: at 2 | 3 one side can still commit and the other must decide between refusing writes and diverging. PACELC adds the half people forget — else, with no partition at all, a read allowed to go to an asynchronous replica is still trading latency against consistency. Both trades are usually made in a configuration file, by someone optimising a p99.

• SELECT then UPDATE, with no FOR UPDATE. A lost update: silent on InnoDB, a 40001 on PostgreSQL.
• A transaction held open across an HTTP call. Its row locks last as long as a third party's p99, and its snapshot pins the vacuum horizon.
• A saga whose compensations are TODO. The first partial failure leaves three services inconsistent and nothing to undo with.
• A cross-service transaction on XA. One coordinator failure wedges every participant, locks held.
• READ UNCOMMITTED set for "performance". On PostgreSQL it does nothing at all.