Featured image of post MySQL MVCC Explained: Undo Log, Purge and the History List

MySQL MVCC Explained: Undo Log, Purge and the History List

An order row on a MySQL server has just been changed by a transaction that has not committed yet. In the same second a report reads that row, a customer's page reads it, and a second transaction tries to change it. On a busy server that is thousands of queries on the same rows at once. Which of them have to wait, which of them see the change, and where does MySQL keep the version the others see?

TL;DR
MVCC (multi-version concurrency control) is how MySQL’s InnoDB engine runs thousands of transactions at once without readers waiting for writers. This post is about what InnoDB keeps in order to do that: where the old version of a changed row goes (the undo log), what purge, its background cleanup, does with those versions, what the history list length counts, and where a connection left idle at MySQL’s default settings fits in. Every number comes from runs on MySQL 8.4.13.

So here is how MVCC works, in outline. Locking every row a transaction reads is not practical on a busy server: with thousands of transactions in flight, readers and writers would spend their time waiting for each other, and the hottest rows would set the pace for everything. InnoDB skips that. Each transaction works from a snapshot, a fixed view of the data as it stood when the transaction started (or, depending on the setting, when each statement started). When a query changes a row, InnoDB writes the new value into the row itself and keeps the old value aside, so a transaction whose snapshot is older than the change can still be shown the row as it was. Readers see their version, writers write theirs, and nobody waits.

A quick reminder about transactions

Moving 100 from one account to another takes two changes, a subtraction from one row and an addition to another. If the server dies between them, or a second transfer slips in between, money appears or disappears. Guarding against that in application code is hard, so databases take the job on: a transaction is a group of statements the database promises to treat as one unit. You open one with BEGIN (or START TRANSACTION) and end it with COMMIT to keep every change, or ROLLBACK to drop every change. With autocommit on, MySQL’s default, a statement sent on its own is a transaction of one.

That promise is usually summed up as ACID, four guarantees that InnoDB, the engine that stores MySQL’s tables, is built around:

GuaranteeWhat it promises
Atomicall of the transaction’s changes happen, or none of them do
Consistentevery rule the schema declares (keys, constraints) holds when the transaction ends
Isolateda transaction is not disturbed by other transactions running at the same moment
Durableonce committed, the changes survive a crash

Isolated is the hard one, because of how many transactions there are. Every program talking to the database holds a connection, which MySQL calls a session; MySQL allows 151 by default, busy systems run thousands, and at any moment many of them are inside a transaction on the same tables. Keeping each one undisturbed by the others, without making them queue, is the job MVCC does.

The table holds only the newest version

The tests in this post ran on MySQL 8.4.13 in Docker at the default settings unless a test says otherwise, limited to 4 CPUs and 4 GB of memory, on an accounts table of 1,000,000 rows (an id, an owner, a balance, a timestamp and a note).

Two sessions, A and B. Session A opens a transaction at the default settings, which keep one view of the data from its first read to its end, and reads account 42: the balance is 187.89. Session B adds 100 to the same account and commits. B’s update did not wait for A; it finished in 2.87 ms. B now reads 287.89, while A, reading again inside its transaction, still gets 187.89. Once A commits and reads again, it gets 287.89 like everyone else. By then the balance A had been reading was not in the table at all.

Both answers can be true at once because of how InnoDB stores a row. An InnoDB table is its primary key: the rows live in the leaf pages of the primary key’s B-tree, which the manual calls the clustered index, the index “that stores row data.” Each row there is one version, the newest, and it carries two hidden fields (manual) that let a reader tell whether that version is meant for it and, if not, find the one that is. DB_TRX_ID is “the transaction identifier for the last transaction that inserted or updated the row”; every transaction that writes gets a number, handed out in order, so it says when this version came into being. DB_ROLL_PTR, the roll pointer, “points to an undo log record” holding “the information necessary to rebuild the content of the row before it was updated.” The rebuilt version carries a roll pointer of its own, so the records chain back through the row’s history.

Those records are the undo log, and it existed before MVCC did. It is InnoDB’s record of how to reverse a change: an undo log record holds “information about how to undo the latest change by a transaction to a clustered index record” (manual). Its first job is ROLLBACK. InnoDB writes a change into the row the moment the statement runs, so it needs the previous values kept somewhere in case the transaction never commits. MVCC gives the same records a second job: “if another transaction needs to see the original data as part of a consistent read operation, the unmodified data is retrieved from undo log records.” One write, then, produces the new row in the table and one undo record in the undo tablespaces, files separate from the table, and that record is the old version. (InnoDB’s redo log is a different thing, a record of committed changes for crash recovery; it plays no part in versions.)

In InnoDB the primary key page holds only the new balance 287.89, with DB_TRX_ID set to B’s transaction and a roll pointer to an undo record saying the balance was 187.89. New sessions read the row as it is; session A starts at the row and follows the pointer.

The two fields are what a snapshot is checked against. A snapshot is not a copy of the data but a record of which transactions had committed at a certain moment, which InnoDB calls a read view, and a read through it is a consistent read: it “sees the changes made by transactions that committed before that point in time, and no changes made by later or uncommitted transactions.” The rule applied to every row: if the row’s DB_TRX_ID counts as committed in the snapshot, show the row as it stands; if not, follow the roll pointer back, one version at a time, until a version does. For A, account 42’s DB_TRX_ID was B’s transaction, which A’s snapshot did not count, so InnoDB rebuilt 187.89 from the undo record. A new session’s snapshot counts B as committed, so it reads the row as it is and never opens the undo log.

How long a snapshot lives is the one setting that matters for the rest of this post. At MySQL’s default settings a transaction takes its snapshot at its first read and keeps it to the end (“consistent reads within the same transaction read the snapshot established by the first read”), and going quiet afterwards does not make it younger. The other behaviour is a fresh snapshot per statement, so an idle transaction holds none; run that way, A’s second read returned B’s new balance. MySQL’s setting for this has four levels (it calls them isolation levels; the default is REPEATABLE READ, the fresh-snapshot one READ COMMITTED). This post simplifies them to those two behaviours, and the isolation levels post covers the rest.

Seen this way, a transaction does not hold its changes back until COMMIT. InnoDB writes them into the rows as it goes, stamped with the transaction’s number, with an undo record for every change; the undo records are what make ROLLBACK possible, and COMMIT decides whether the number counts for later snapshots:

StatementThe row in the tableUndo record written
INSERTa new row, DB_TRX_ID set to this transactionhow to take the row out again, dropped at commit
UPDATEnew values written over the old, DB_TRX_ID set to this transaction, roll pointer to the undo recordthe values it overwrote
DELETEstays in place, marked deleted, DB_TRX_ID set to this transactionenough to clear the mark again

A DELETE removes nothing yet: a deletion “is treated internally as an update where a special bit in the row is set to mark it as deleted,” and the row waits in the table for cleanup. A rollback does real work, copying the old values back from the undo records; a commit leaves the row alone. PostgreSQL makes the opposite choice and writes each new version as a new row in the table, which the PostgreSQL MVCC post measures on the same table.

Where MySQL still waits

MVCC removes one kind of waiting, readers for writers, and leaves the others in place. To see which, session A did something and then held its transaction open for 2 seconds before committing, while session B tried something else, each case on a new 1,000-row table:

Session A, transaction held openSession BB waited
updated account 42plain SELECT of account 420.6 ms
updated account 42UPDATE of account 422,019 ms
updated account 42SELECT ... FOR UPDATE of account 422,008 ms
SELECT ... WHERE id > 990 FOR UPDATE, default settingsINSERT of id 10012,017 ms
the same, fresh snapshot per statementINSERT of id 10016.7 ms
one plain SELECT of account 42, then idleALTER TABLE accounts ADD COLUMN2,043 ms
same, with that ALTER waitingplain SELECT of account 7, sent 0.3 s after the ALTER1,730 ms

Bar chart: a plain SELECT of the changed row waited 0.6 ms; an UPDATE of the same row 2,019 ms; SELECT FOR UPDATE 2,008 ms; an INSERT into a range locked FOR UPDATE 2,017 ms at the default settings and 6.7 ms with a fresh snapshot per statement; ALTER TABLE while A sat idle after one SELECT 2,043 ms; a plain SELECT sent after that ALTER 1,730 ms.

The plain read returned the committed balance without waiting. Everything that wanted to change the row, or to lock it, waited until A committed, because two writers on one row still take turns. SELECT ... FOR UPDATE is a locking read, and like UPDATE and DELETE it works on the latest version, not the snapshot: the manual says it “reads the latest available data, setting exclusive locks on each row it reads”, and after its wait it returned the value A had just committed. (That read-the-snapshot, write-the-latest split is how MySQL lets through lost updates that PostgreSQL refuses; the isolation levels post shows it.)

Every one of those waits lasted as long as A’s transaction, not A’s statement. Run once more with A’s update sent without BEGIN, so that it committed on its own, B waited 7.3 ms instead of 1,708; same statement, same idle connection afterwards. A row lock is held until the transaction that took it ends.

Two of the rows are locks on things other than the row. At the default settings, A’s FOR UPDATE over id > 990 locked the gap above 1000 as well, “using gap locks or next-key locks to block insertions by other sessions into the gaps covered by the range” (manual), so an insert of a row that did not exist yet waited the full 2 seconds; with a fresh snapshot per statement, where gap locking is limited to foreign-key and duplicate-key checks, it went through in 6.7 ms. And a transaction that has only read a table still holds a metadata lock on it until it ends (manual), so the ALTER waited for idle A, and a plain read from a third session then waited behind the queued ALTER. An idle transaction plus a schema change is one of the few ways to make plain reads wait in MySQL.

Purge frees the undo space but keeps the files

Locks end with the transaction that took them. Undo records do not: B’s record for account 42 outlived B’s commit because A still needed it. Throwing records away once no snapshot can need them is the work of purge, a set of background threads that discards undo records and, for deleted rows, removes the row itself; the manual says InnoDB “only physically removes the corresponding row and its index records when it discards the update undo log record written for the deletion.” How far behind purge is shows up as the history list length, the number of committed transactions whose undo records purge has not discarded yet.

If the table only ever holds the newest version, updating every row should leave the table the same size and grow the undo log instead. I updated all 1,000,000 accounts in a single statement, with nobody else connected, waited for purge, and did it again:

Bar chart: the MySQL table stayed 120 MB through two updates of every row. The undo log grew from 48 MB to 96 MB after the first update, stayed 96 MB after purge, grew to 128 MB after the second update and stayed 128 MB after purge.

StepTableUndo logHistory listTook
Before120 MB48 MB12
After updating every row120 MB96 MB02.1 s
After purge120 MB96 MB2
After a second full update120 MB128 MB52.4 s
After purge120 MB128 MB7

The table never moved from 120 MB. The undo log doubled to hold the million old balances, and the history list stayed near zero: the whole update was one transaction, and with no older snapshot around, purge cleared its undo almost at once. What purge did not do is shrink the files. It frees the space inside the undo tablespaces for reuse; giving it back to the operating system happens only when a tablespace passes innodb_max_undo_log_size, 1 GiB by default (manual). Below that, the undo files keep whatever size they reached. The same update on PostgreSQL doubled the table itself, from 135 to 269 MB; that is the trade the two designs make.

One idle read holds every old version back

Purge kept up above because nobody held a snapshot older than the update. This run puts one there. Session A opens a transaction at the default settings, reads a single row and then does nothing, the way an application can leave a connection sitting inside BEGIN. Meanwhile session B makes 100,000 single-row updates to 1,000 accounts, 100 each, every update its own transaction. Five seconds after the last one, I read the history list length.

Bar chart: history list length 5 seconds after 100,000 single-row updates on MySQL 8.4.13. 229 with nobody else in a transaction; 100,001 with one session idle at the default settings after BEGIN and one SELECT of one row.

Each of B’s updates was its own transaction, so one history list entry is one old version. With nobody idle, 229: purge was keeping up. With A idle, 100,001, an old value from every one of B’s updates, because A’s snapshot predated all of them and A had read exactly one row. More purge threads would not have moved the number. Undo records “can be discarded only after there is no transaction present for which InnoDB has assigned a snapshot that in a consistent read could require the information,” and the manual’s advice follows: commit regularly, “including transactions that issue only consistent reads.”

Session A, sitting idleHistory list length
No transaction open229
Fresh snapshot per statement, had only read90
Fresh snapshot per statement, had updated one unrelated row105
Default settings, had only read one row100,001

With a fresh snapshot per statement, A held no snapshot between statements and blocked nothing, even after writing a row of its own. (PostgreSQL, where that behaviour is the default, kept all 100,000 dead rows for the idle writer.)

Nobody else paid for the backlog at read time:

Bar chart: pages touched to read one hot account by primary key. 3 with no other transaction open, 3 for a new session while another sat idle at the default settings, and 103 for the idle session itself, whose old snapshot rebuilds each account through 100 undo records.

The newest version is always in the row, so a session with a current snapshot read a hot account in 3 pages, the same as with nobody idle. Only A paid, rebuilding each account back through 100 undo records. The cost is the backlog itself: the undo files grow to fit it and are not shrunk below 1 GiB, and when A finally committed, purge took 110 seconds to bring the history list back under 100.

An idle transaction is enough
Nothing about session A looks expensive: one small SELECT, then silence. The damage comes from the transaction staying open, and at MySQL’s default settings it happens even if the transaction never writes anything. On a production replica, one forgotten read like this let the history list reach about a billion and left the replica three days behind.

What to watch

The history list length is the number to graph. It is in the TRANSACTIONS section of SHOW ENGINE INNODB STATUS, and as trx_rseg_history_len in information_schema.INNODB_METRICS; a history list that climbs and does not come back down means a snapshot is holding purge back, and information_schema.INNODB_TRX shows whose:

1
2
3
4
5
6
SELECT count FROM information_schema.INNODB_METRICS
 WHERE name = 'trx_rseg_history_len';

SELECT trx_mysql_thread_id, trx_started, trx_query
  FROM information_schema.INNODB_TRX
 ORDER BY trx_started;

An old trx_started with a NULL trx_query is a session A: open, and running nothing. MySQL has no setting that ends such a transaction; wait_timeout closes an idle connection after 8 hours by default, and by then the history list has had a working day to grow. What holds up is committing before waiting on anything outside the database, and at MySQL’s default settings that includes transactions that only read. Part V of the queries series covers the disk side of the same problem.

SELECT insights FROM experience WHERE downtime = 0; -- Ruslan Tolkachev