Skip to content
notes.vinhnq.com

Search

Database & ORMSenior20 min read

Transactions from the inside: WAL, MVCC and the undo log

Review 13 cards
On this page

Transactions and locking in depth series: 1. Transactions from the inside · 2. Harmful transactions · 3. Locks in InnoDB · 4. Optimistic, pessimistic and the booking lab

This post goes below isolation levels: what the database does to keep a transaction’s promises, and why one transaction left open too long slows down the whole system. Afterwards you can explain the redo log, the undo log and MVCC in InnoDB and PostgreSQL, and measure the cost of an old snapshot. Read the post on transactions, isolation levels and locking first.

1. Replaying the four isolation levels

Key idea: the textbook “which level prevents which anomaly” table follows the SQL standard, but every database implements it differently. Running it shows three differences: READ UNCOMMITTED, lost update at REPEATABLE READ, and how SERIALIZABLE says no.

Five anomalies (wrong results when two transactions interleave):

  • Dirty read: you see data someone else hasn’t committed.
  • Non-repeatable read: reading a row twice gives two values.
  • Phantom: counting twice, the second count includes a row someone just inserted.
  • Lost update: both sides read, compute in the app and write; the later write wipes out the earlier one.
  • Write skew: both read the same data and then write two different rows, which together break a rule (e.g. “at least one doctor on call”).

All numbers in this post come from experiments on Docker (MySQL 8.4.11, PostgreSQL 16.14) with JDK 21. The program opens two connections and pushes statements in exact time order; a statement not finished after 400 ms is recorded as “blocked” (waiting for a lock).

Where reality differs MySQL 8.4 (InnoDB) PostgreSQL 16
READ UNCOMMITTED real dirty read: T2 sees 0 behaves as READ COMMITTED: T2 sees 100
Lost update at RR not prevented: +50 is lost T1 fails with could not serialize access due to concurrent update
Write skew at RU, RC, RR not prevented: 0 on call not prevented: 0 on call
SERIALIZABLE reads become locks, ends in deadlock SSI: nobody waits, one side is aborted
Full results: 5 anomalies × 4 levels on MySQL 8.4 and PostgreSQL 16

Data: an acct table with 3 rows, each with balance = 100, two of them with on_call = TRUE. Code is in Exercise 1.

Scenario Level MySQL 8.4 PostgreSQL 16
Dirty read: T1 writes without committing, T2 reads RU T2 sees 0 T2 sees 100
RC, RR sees 100 sees 100
SERIALIZABLE T2 blocks until T1 finishes sees 100
Non-repeatable read: T1 reads twice, T2 updates and commits in between RU, RC 100 then 50 100 then 50
RR, SER 100 then 100 100 then 100
Phantom: T1 counts twice, T2 inserts and commits in between RU, RC 3 then 4 3 then 4
RR 3 then 3 3 then 3
SER 3 then 3, T2’s insert blocks until T1 commits 3 then 3, nobody blocks
Lost update: both read 100, compute in the app, then write RU, RC 110 left (the +50 is lost) 110 left
RR 110 left T1 fails with could not serialize access due to concurrent update
SER T2 blocks, T1 is chosen as the deadlock victim T1 gets a serialization error
Write skew: two doctors both see 2 on call, each takes themselves off RU, RC, RR 0 on call 0 on call
SER T2 hits a deadlock, 1 left on call T2 fails at commit (read/write dependencies), 1 left on call

Lost update at InnoDB’s REPEATABLE READ is a classic senior interview question. It also shows that “use READ COMMITTED for financial systems” is only half right: money still disappears if the code reads, computes and writes in the application. Correct money comes from atomic UPDATE statements, row locks or versions (part 4 measures this on a booking exercise).

2. The path of a write: write-ahead logging

Key idea: a commit only needs to append a change record to a sequential log and fsync it; the data page reaches disk later. That’s write-ahead logging (WAL).

Writing the 16 KB data page to its exact place on every commit is a random write, which is slow; appending to the end of a log is much faster. It’s like a shopkeeper who writes every order in a ledger first and tidies the stockroom at the end of the day: after a power cut, the ledger says what to redo.

flowchart LR
  A[UPDATE] --> B[Change the page in the buffer pool]
  B --> C[Append a redo record to the log buffer]
  C --> D[COMMIT: write and fsync the redo log]
  D --> E[Return OK to the client]
  B -.-> F[Dirty page flushed to the data file later]
  • Buffer pool: memory holding data and index pages. An UPDATE changes a page here, and the page becomes “dirty” (not yet on disk).
  • Redo log: a sequential log. At commit, InnoDB writes it to disk and fsyncs it (with innodb_flush_log_at_trx_commit = 1).
  • After a crash: InnoDB reads the redo log and redoes changes that hadn’t reached the data files, then uses the undo log to undo transactions that never committed. PostgreSQL does the same with its WAL (pg_wal).

Remember: the redo log is for durability (redo what was committed), the undo log is for atomicity and MVCC (undo what wasn’t, rebuild old versions). They often get mixed up.

Inside InnoDB: LSN, checkpoint, doublewrite and group commit
  • LSN (log sequence number): an ever-increasing number on each redo record. Since MySQL 8.0.30 the redo log size is set with innodb_redo_log_capacity.
  • Checkpoint: a background process gradually flushes dirty pages to the data files. Pages with an LSN below the checkpoint are safely on disk, so that part of the redo log can be reused. After a crash, InnoDB reads the redo log from the last checkpoint.
  • Doublewrite buffer: a 16 KB page can be half-written if power fails (a torn page). InnoDB writes the page to the doublewrite area first and then to its real location, so recovery always has one intact copy. PostgreSQL relies on full_page_writes instead.

3. MVCC in InnoDB: a chain of versions in the undo log

Key idea: the row in the table is always the newest version; old versions are rebuilt by applying the chain of undo records backwards. The read view decides which version each read may see.

MVCC (multi-version concurrency control): the database keeps several versions of a row so readers see a consistent snapshot without waiting for writers.

Every row has hidden columns. DB_TRX_ID is the id of the transaction that last changed the row. DB_ROLL_PTR points to the undo record holding the previous version. A table without a primary key also gets DB_ROW_ID.

Every change creates an undo record. Old versions aren’t stored as whole rows. They are rebuilt by following the DB_ROLL_PTR chain and applying each undo record backwards. The slides’ “a version of a row is called an undo log” is imprecise: an undo record is the recipe for going back to the previous version, like a Ctrl+Z history.

flowchart LR
  R["Clustered index: v4 (trx 104)"] -->|roll ptr| U3["undo: v4 back to v3 (trx 103)"]
  U3 -->|roll ptr| U2["undo: v3 back to v2 (trx 102)"]
  U2 -->|roll ptr| U1["undo: v2 back to v1 (trx 101)"]

A read view is the snapshot used for reading: the list of active transactions, the smallest id among them and the next id to be assigned. A version is visible if its DB_TRX_ID committed before the read view was created (or is your own); otherwise InnoDB walks on to an older version.

When the read view is created (the slides just say “a snapshot is created at SELECT”):

  • REPEATABLE READ: at the first consistent read of the transaction, not at START TRANSACTION. To create it immediately, use START TRANSACTION WITH CONSISTENT SNAPSHOT.
  • READ COMMITTED: a fresh one for every statement.
  • FOR UPDATE, FOR SHARE, UPDATE, DELETE: no read view. They are current reads: they read the latest committed version and lock it.

Purge cleans up old versions. Once no read view needs an old version, a background purge thread removes its undo record, and physically removes DELETEd rows (until then only delete-marked). Undo pages live in the buffer pool, so a bloated undo takes memory away from real data.

3.1. History list length: measuring the cost of an old snapshot

Key idea: history list length (HLL) is the number of committed undo records not yet purged. HLL rising steadily almost always means a transaction has been left open too long, and old snapshots get much slower to read.

You see HLL in SHOW ENGINE INNODB STATUS (the History list length line) or as the trx_rseg_history_len metric in information_schema.innodb_metrics.

The experiment: session A opens a transaction, reads the hot row once and waits. Session B runs 20,000 autocommitted UPDATEs on that row.

Moment HLL One read of hot by session A
Before the experiment 46 0.43 ms
After 20,000 updates, A still open 20,001 26.8 ms (10.5 ms on the next read)
Same moment, A reads FOR SHARE (latest version) 0.2 ms
A commits, a few seconds later 0

A primary-key read of a single row became about 60 times slower. The reason: InnoDB had to walk back through 20,000 undo records to rebuild the version A’s read view may see.

HLL experiment steps and a reference measurement from the book
  1. Session A opens a transaction, reads the hot row once (creating a read view), then waits.
  2. Session B runs 20,000 UPDATE hot SET v = v + 1 statements, each autocommitted.
  3. Session A reads the row again, both as a snapshot read and with FOR SHARE.

The book Efficient MySQL Performance (Daniel Nichter) shows the same trend: one query’s response time went from about 0.2 ms at an HLL of 0 to about 8.5 ms at an HLL of roughly 11,500.

There’s no universal HLL threshold. What should page someone is HLL rising steadily without coming back down.

4. MVCC in PostgreSQL: versions live in the table

Key idea: PostgreSQL has no undo log. Every UPDATE writes a new copy of the row into the table and the old one becomes a “dead tuple” waiting for VACUUM; an old snapshot blocks VACUUM just as it blocks purge.

  • Tuple: one version of a row, stored in the table.
  • xmin: the transaction that created the tuple. xmax: the transaction that deleted or replaced it (0 if it’s alive).
  • A transaction sees a tuple if its xmin committed before the snapshot and its xmax didn’t.
  • Dead tuple: an old version nobody needs any more. VACUUM cleans them up, usually as autovacuum in the background.

The same kind of incident as in InnoDB: a REPEATABLE READ transaction opens and sits idle, another session updates the row 5,000 times. VACUUM VERBOSE reports 5,000 dead tuples “not yet removable”. Find the culprit through the backend_xmin column of pg_stat_activity (the oldest snapshot a backend is holding):

SELECT pid, state, now() - xact_start AS xact_age, backend_xmin, left(query, 40)
FROM pg_stat_activity
WHERE backend_xmin IS NOT NULL AND pid <> pg_backend_pid()
ORDER BY xact_start;
The pageinspect experiment and VACUUM VERBOSE output

Look at two tuples of the same row directly with the pageinspect extension:

SELECT xmin, xmax, ctid, v FROM hot;      -- 832 | 0 | (0,1) | 0
BEGIN; UPDATE hot SET v = 1 WHERE id = 1; COMMIT;   -- transaction 833
SELECT lp, t_xmin, t_xmax, t_ctid FROM heap_page_items(get_raw_page('hot', 0));
--  lp | t_xmin | t_xmax | t_ctid
--   1 |    832 |    833 | (0,2)    <- old version, replaced by 833, points to the new one
--   2 |    833 |      0 | (0,2)    <- current version

VACUUM VERBOSE output while the old RR transaction is still open, after 5,000 updates:

tuples: 0 removed, 5001 remain, 5000 are dead but not yet removable

Exercises

Exercise 1: Replay the isolation level scripts

Task (paraphrased): rebuild the dirty read, non-repeatable read and phantom read scenarios for each isolation level and observe the results, instead of memorizing the table.

Solution to Exercise 1: driving two transactions from Java

I extended it with lost update and write skew and ran it on both MySQL and PostgreSQL. The tricky part is driving two transactions in exact time order, and recognizing when a statement blocks without hanging the whole program. Each session gets a single-thread executor; each step submits a statement to it and waits at most 400 ms.

static final class Session implements AutoCloseable {
    final Connection c;
    final ExecutorService ex = Executors.newSingleThreadExecutor();
    Future<?> last = CompletableFuture.completedFuture(null);

    Session(Connection c) { this.c = c; }

    /** Run one step; if it isn't done after 400 ms, treat it as waiting for a lock. */
    String run(String sql) {
        last = ex.submit(() -> exec(sql));
        try { return String.valueOf(last.get(400, TimeUnit.MILLISECONDS)); }
        catch (TimeoutException e) { return "(blocked)"; }
        catch (ExecutionException e) { return "ERROR: " + e.getCause().getMessage(); }
        catch (InterruptedException e) { Thread.currentThread().interrupt(); return "interrupted"; }
    }

    /** Wait for a previously blocked step to finish (after the other transaction ends). */
    String awaitLast() throws Exception { return String.valueOf(last.get(10, TimeUnit.SECONDS)); }

    Object exec(String sql) throws SQLException {
        try (Statement st = c.createStatement()) {
            if (!st.execute(sql)) return "ok(" + st.getUpdateCount() + ")";
            try (ResultSet rs = st.getResultSet()) {
                List<String> rows = new ArrayList<>();
                while (rs.next()) rows.add(rs.getString(1));
                return rows;
            }
        }
    }

    @Override public void close() throws Exception { c.rollback(); c.close(); ex.shutdownNow(); }
}

// Lost update scenario: both read, each computes in the application, then writes
static String lostUpdate(Session t1, Session t2) throws Exception {
    int b1 = firstInt(t1.run("SELECT balance FROM acct WHERE id = 1"));
    int b2 = firstInt(t2.run("SELECT balance FROM acct WHERE id = 1"));
    String w2 = t2.run("UPDATE acct SET balance = " + (b2 + 50) + " WHERE id = 1");
    String c2 = t2.run("COMMIT");
    String w1 = t1.run("UPDATE acct SET balance = " + (b1 + 10) + " WHERE id = 1");
    String c1 = t1.run("COMMIT");
    if (w2.equals("(blocked)")) w2 = t2.awaitLast();
    return "T2 " + w2 + "/" + c2 + ", T1 " + w1 + "/" + c1;
}

Each scenario runs four times, each time with two fresh connections set up with setTransactionIsolation(...) and setAutoCommit(false). Set innodb_lock_wait_timeout = 2 (MySQL) or lock_timeout = '2s' (PostgreSQL) so a blocked statement doesn’t wait 50 seconds. The result is the table in section 1.

The most useful lesson is in the last two rows: lost update and write skew get through MySQL’s RR. At SERIALIZABLE the two databases “say no” in two different ways (deadlock versus serialization error), so the code must retry the whole transaction.

Exercise 2: Alerting on HLL

Task (my own addition): when should you raise an alarm about history list length?

Solution: collect trx_rseg_history_len from information_schema.innodb_metrics every 15 seconds (Prometheus’s mysqld_exporter has it). Set two alerts:

  1. HLL stays several times above the system’s normal baseline for 10 minutes.
  2. The age of the oldest transaction in innodb_trx exceeds a threshold (say 5 minutes for OLTP).

Alert 2 usually fires first and points straight at the culprit. Alert 1 also catches many medium-sized transactions piling up.

Remember

  • Explain why InnoDB’s REPEATABLE READ loses an update while PostgreSQL’s raises an error.
  • Tell the redo log from the undo log, and which letter of ACID each one serves.
  • Know when the read view is created at RR and at RC, and when a read skips the read view.
  • Explain why a long-open read-only transaction slows down the whole database, and how to measure it.
  • Compare InnoDB’s undo log with PostgreSQL’s in-table tuples: rollback, bloat, VACUUM.

Interview questions

Junior

How do the redo log and the undo log differ?

The redo log redoes what was committed (durability); the undo log goes back to the previous version (atomicity and MVCC).

After a crash, the redo log lets the database redo what was committed but hadn’t reached the data files yet. The undo log is used to roll back uncommitted transactions and to rebuild old versions for snapshot reads.

Why does a database write the log before the data files?

Because a sequential append to the log is much faster than random page writes, and it’s still enough to lose nothing.

A commit only needs the log safely on disk; data pages are written later in batches. After a crash, the database reads the log to redo whatever is missing. That’s write-ahead logging.

Mid

When does InnoDB create the read view at REPEATABLE READ and at READ COMMITTED?

RR: at the first consistent read, reused until the end of the transaction. RC: a new read view for every statement.

At RR the read view isn’t created at BEGIN; to create it immediately, use START TRANSACTION WITH CONSISTENT SNAPSHOT. Locking reads and UPDATE/DELETE don’t use a read view; they read the latest version (a current read).

Why can two reads of the same row in one MySQL REPEATABLE READ transaction return different results?

Because one is a plain SELECT (a snapshot read) and the other is SELECT ... FOR UPDATE/FOR SHARE (a current read of the latest committed version).

RR only promises repeatability for consistent reads. That’s why a decision you’re going to write back must be based on a current read, or sit directly in the UPDATE’s WHERE clause.

Senior

History list length keeps growing. How do you investigate?

Find the old read view holding back purge: the oldest transaction in information_schema.innodb_trx. Then deal with it and fix the root cause in the application.

  • Order innodb_trx by trx_started and join it with the processlist and performance_schema.events_statements_current to get the connection, host and last statement.
  • A leaked connection or forgotten session: kill it (accepting the rollback time), then fix the application.
  • No old transaction: check whether purge keeps up with the write load (innodb_purge_threads).
  • Afterwards, add alerts on HLL and on transaction age.
Compare MVCC in InnoDB and PostgreSQL, and the operational consequences of each.

InnoDB keeps old versions in the undo log, PostgreSQL keeps them in the table itself; long-open transactions hurt both.

  • InnoDB: the latest version lives in the clustered index, old ones are rebuilt from undo. Tables don’t bloat, but old snapshots read slowly when undo chains are long, and rolling back a big transaction takes a long time.
  • PostgreSQL: a new tuple per update, marked with xmin/xmax. Rollback is instant, but tables and indexes bloat, it depends on VACUUM, needs freezing to avoid wraparound, and should take advantage of HOT updates.
You choose SERIALIZABLE on PostgreSQL for a business flow. What does the application need?

A retry loop wrapped outside the whole transaction, because SSI doesn’t block: it aborts a transaction with SQLState 40001, sometimes right at COMMIT.

  • Cap the attempts and use randomized backoff.
  • The transaction body must be safe to rerun: no emails, no external API calls inside.
  • Keep transactions short to reduce conflicts. Declare read-only transactions READ ONLY (or DEFERRABLE for long reports) to cut false positives.

Useful phrases for interviews

  • “The redo log is about durability; the undo log is about rollback and old versions for MVCC.”
  • “Write-ahead logging turns random page writes into a sequential append at commit time.”
  • “In InnoDB the read view is created at the first consistent read, not at BEGIN.”
  • “A plain SELECT reads the snapshot, but SELECT FOR UPDATE is a current read of the latest committed row.”
  • “A transaction left open holds back purge, so the history list grows and snapshot reads slow down.”
  • “In my test, one primary-key read went from under half a millisecond to about 27 milliseconds with twenty thousand unpurged versions.”
  • “PostgreSQL keeps old versions in the table itself, so the trade-off is bloat and VACUUM instead of undo chains.”
  • “On MySQL, SERIALIZABLE turns plain reads into shared locks; on PostgreSQL it’s SSI, which aborts instead of blocking.”

Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.