Digging into MariaDB's Source 11: InnoDB Part 2 — Transactions, MVCC, Undo and Locks

What this post covers

This is the eleventh post in the "Digging into MariaDB's Source" series. In Part 10 we saw how InnoDB keeps data in 16KB pages, loads them into the buffer pool and finds rows through B-trees. That post only asked "where and how is one row stored?" This one asks what InnoDB does when many connections read and change the same rows at the same time.

On the Part 2 map we keep zooming into InnoDB inside zone ⑧, the engine, with one addition. COMMIT is not the engine's business alone, so we first look at the transaction coordination in the server layer (sql/handler.cc) that tells the engines "commit now".

The blue boxes are what we read in this post. Part 7's MDL and this post's row locks are locks on different layers.

We want to answer four questions.

• Which functions does a single COMMIT pass through from the server layer to InnoDB, and what does InnoDB do at commit time?
• Under REPEATABLE READ, why can't I see a value another connection has committed — and where does the old value I see come from?
• Who removes old values once nobody needs them, and when? Why is a long-open transaction a problem?
• Where and how are the locks stored that make SELECT … FOR UPDATE block other connections, and how are deadlocks found?

All line numbers in this post refer to that commit. Part 1 shows how to check out the same commit and build the Docker image used for the examples.

lock0lock.cc and row0sel.cc are each over 7,000 lines, and trx0trx.cc is over 2,000. This post picks only the main paths someone opening the code for the first time can follow. What I left out is listed by name and location in "What this post leaves out" at the end.

Terms to know first

A handlerton is the bundle of function pointers each engine has exactly one of (Part 2, Part 3). Here we only use its transaction slots: commit, rollback and prepare. At the reference commit those slots live in struct transaction_participant, which struct handlerton inherits from.

trx_t is InnoDB's transaction object (include/trx0trx.h). The server's THD (Part 2 — all the state of one connection) has a note slot per engine (ha_data), and InnoDB hangs its trx_t there. Each connection has one trx_t; when a transaction ends, the object is not thrown away but reused for the next one.

A transaction ID (trx id) is a sequence number handed out to transactions that write. trx_sys (trx_sys_t, the global object that owns the whole transaction system) hands them out. The trx_id in information_schema.INNODB_TRX and the TRANSACTION 23 in SHOW ENGINE INNODB STATUS are this number.

A read view (ReadView) is a small table saying "whose changes may this transaction see?" When it is created it remembers the IDs of transactions that have not committed yet; whenever a row is read, the transaction that last changed the row is checked against this table. MVCC (multi-version concurrency control) is this approach of "if a change isn't visible to you, show you an older version".

The undo log records a row's values before it is changed. It is what a rollback uses to undo changes, and what other transactions use to build old versions. Undo is written to undo pages, which are managed by rollback segments (trx_rseg_t). Since this means writing pages, it is wrapped in a mini-transaction (mtr_t) from Part 10 and leaves redo log behind (Part 10).

Purge is the background job that really removes old versions (undo) that nobody needs any more, along with records that were only marked as deleted.

A row lock is a lock InnoDB takes on individual index records. There is the record lock on one record, the gap lock on the empty space (the gap) before a record that stops anyone inserting into it, and the next-key lock, which is both together. The metadata lock (MDL) of Part 7 is a lock the server layer takes on table definitions — a different layer from these.

1. Transactions on the server side — how COMMIT reaches the engine

The server only remembers "who took part in this transaction"

A single transaction can change an InnoDB table and an Aria table together. So the server layer does not implement transactions itself. It just keeps a list of the engines taking part in this transaction, and when COMMIT arrives it tells each engine on the list to commit in turn. What an engine has to provide is fixed by the function pointers in transaction_participant.

  /*
    'all' is true if it's a real commit, that makes persistent changes
    'all' is false if it's not in fact a commit but an end of the
    statement that is part of the transaction.
    NOTE 'all' is also false in auto-commit mode where 'end of statement'
    and 'real commit' mean the same event.
  */
  int (*commit)(THD *thd, bool all);
  int  (*rollback)(THD *thd, bool all);
  int  (*prepare)(THD *thd, bool all);

sql/handler.h, lines 1341–1350

The comment warns us about the first trap of this post. all being true means a real commit; false means "one statement inside the transaction has ended". But in autocommit mode, the end of the statement and the real commit are the same event, and the call is made with all=false. An engine cannot look at all alone; it must also check whether autocommit is on (innobase_commit() below does just that).

InnoDB plugs its own functions into these slots at startup.

	innobase_hton->commit_ordered= innobase_commit_ordered;
	innobase_hton->commit = innobase_commit;
	innobase_hton->rollback = innobase_rollback;
	innobase_hton->prepare = innobase_xa_prepare;

storage/innobase/handler/ha_innodb.cc, lines 4313–4316

InnoDB puts its name on the list itself. When a statement first uses a table, the server calls ha_innobase::external_lock(), which calls innobase_register_trx() (line 16834), which in turn calls the server's trans_register_ha().

  const trx_id_t trx_id= trx->id;

  trans_register_ha(thd, false, hton, trx_id);

  if (!trx->is_registered)
  {
    trx->is_registered= true;
    if (thd_test_options(thd, OPTION_NOT_AUTOCOMMIT | OPTION_BEGIN))
      trans_register_ha(thd, true, hton, trx_id);
  }

storage/innobase/handler/ha_innodb.cc, lines 3206–3215

The server keeps two lists: thd->transaction->stmt (the current statement) and thd->transaction->all (the whole transaction). trans_register_ha(thd, false, …) adds to the statement list, trans_register_ha(thd, true, …) to the whole-transaction list. The engine only goes on the latter when the transaction was opened with BEGIN or autocommit is off (OPTION_NOT_AUTOCOMMIT | OPTION_BEGIN).

The path of COMMIT

The Part 6 parser turns the COMMIT statement into SQLCOM_COMMIT, and case SQLCOM_COMMIT in mysql_execute_command() calls trans_commit() (sql_parse.cc, lines 5590–5600). trans_commit() calls ha_commit_trans(thd, TRUE) (transaction.cc, line 271).

This is the path with the binlog off, the default. With the binlog on, a two-phase commit slots into the middle; we see that in Part 12.

If more than one engine wrote or the binlog is on, ha_commit_trans() runs a two-phase commit (prepare everyone first, then commit); otherwise it goes straight to ha_commit_one_phase() (the if (trans->no_2pc || (rw_ha_count <= 1)) at handler.cc, lines 1978–2022). The place that actually calls the engines' function pointers is this loop in commit_one_phase_2().

    for (; ha_info; ha_info= ha_info_next)
    {
      transaction_participant *ht= ha_info->ht();
      if ((err= ht->commit(thd, all)))
      {
        my_error(ER_ERROR_DURING_COMMIT, MYF(0), err);
        error=1;
      }

sql/handler.cc, lines 2282–2289

On the InnoDB side, innobase_commit() sorts out the "all=false but really a commit" case like this.

	if (commit_trx
| (!thd_test_options(thd, OPTION_NOT_AUTOCOMMIT | OPTION_BEGIN))) {

		/* Run the fast part of commit if we did not already. */
		if (!trx->active_commit_ordered) {
			innobase_commit_ordered_2(trx, thd);
		// ...
		/* Now do a write + flush of logs. */
		trx_commit_complete_for_mysql(trx);

		trx_deregister_from_2pc(trx);
	} else {
		/* We just mark the SQL statement ended and do not do a
		transaction commit */
		lock_unlock_table_autoinc(trx);
		if (UNIV_UNLIKELY(end_of_statement(trx))) {
			DBUG_RETURN(1);
		}

storage/innobase/handler/ha_innodb.cc, lines 4798–4825

If commit_trx (the all the server passed) is true, or autocommit is on and no BEGIN was issued, it really commits. Otherwise it only notes that one statement has ended (end_of_statement()) and returns. The commit is split in two. innobase_commit_ordered_2() does the fast part that fixes the commit order, and trx_commit_complete_for_mysql() does the slow part that writes the log to disk (depending on innodb_flush_log_at_trx_commit). The slow part is kept separate for group commit, where several transactions ride on a single log write (Part 12).

Example 1: the backtrace of COMMIT

I checked with gdb that commits really take this path. This example and every other example in the post were run in a Docker container (Ubuntu 24.04) with MariaDB 13.2.0 (13.2.0-MariaDB-debug), a Debug build of the reference commit (c894d97781) as is. The example folder is ex/u11-gdb-commit. Session A runs BEGIN; UPDATE t SET val = 'A' WHERE id = 20; and keeps the transaction open, gdb -p $(cat /tmp/mariadbd.pid) -batch -ex 'break trx_t::release_locks' -ex 'continue' -ex 'bt' -ex 'delete' -ex 'detach' is attached in the background, and then A sends COMMIT.

Here is the result, with addresses and argument values removed and cut off at do_command.

#0  trx_t::release_locks at storage/innobase/trx/trx0trx.cc:508
#1  trx_t::commit_in_memory at storage/innobase/trx/trx0trx.cc:1481
#2  trx_t::commit_persist at storage/innobase/trx/trx0trx.cc:1641
#3  trx_t::commit at storage/innobase/trx/trx0trx.cc:1650
#4  trx_commit_for_mysql at storage/innobase/trx/trx0trx.cc:1765
#5  innobase_commit_low at storage/innobase/handler/ha_innodb.cc:4565
#6  innobase_commit_ordered_2 at storage/innobase/handler/ha_innodb.cc:4657
#7  innobase_commit at storage/innobase/handler/ha_innodb.cc:4803
#8  commit_one_phase_2 at sql/handler.cc:2285
#9  ha_commit_one_phase at sql/handler.cc:2226
#10 ha_commit_trans at sql/handler.cc:2014
#11 trans_commit at sql/transaction.cc:271
#12 mysql_execute_command at sql/sql_parse.cc:5600
#13 mysql_parse at sql/sql_parse.cc:8005
#14 dispatch_command at sql/sql_parse.cc:1903
#15 do_command at sql/sql_parse.cc:1437

Read from the bottom up, it matches the diagram exactly. handler.cc:2285 in #8 is the ht->commit(thd, all) in the loop above, and everything above it is InnoDB. The border between the server layer and the engine is one function-pointer call.

Easy to get wrong: a single statement is a "transaction" too

Even one UPDATE in autocommit mode is a complete transaction inside InnoDB: a trx_t starts and commits. When the statement ends the server calls ha_commit_trans(thd, FALSE) through trans_commit_stmt() (transaction.cc, line 499), and the condition in innobase_commit() above decides "autocommit, so this is a real commit". That is why every statement pays the cost of a commit (a log flush) when you don't wrap them in BEGIN … COMMIT.

2. trx_t — the life of a transaction inside InnoDB

Only structures that appear in this post are drawn. The four ReadView members actually live in its parent class ReadViewBase.

This post uses five members of trx_t (trx0trx.h, from line 597).

The ways the state can change are summarized in a long comment in the source (trx0trx.h, lines 700–752). As a diagram:

Each connection keeps reusing its one trx_t. That is why there is no final state; it goes back to NOT_STARTED.

Started late, given an ID even later

Sending BEGIN does not start an InnoDB transaction. The server only sets an OPTION_BEGIN flag on BEGIN (transaction.cc, line 205), and InnoDB becomes ACTIVE through trx_start_if_not_started() → trx_start_low() the first time a row is read or written. This leads to "BEGIN does not open the read view" in section 3's example.

The transaction ID does not come right away either. trx_start_low() attaches a rollback segment and an ID only when a write is certain.

	if (!trx->read_only
	    && (!trx->mysql_thd || read_write || trx->dict_operation)) {
		/* Temporary rseg is assigned only if the transaction
		updates a temporary table */
		if (!high_level_read_only && !recv_sys.rpo) {
			trx_assign_rseg_low(trx);
		}
	} else {

storage/innobase/trx/trx0trx.cc, lines 971–978

A user transaction usually starts with read_write false and takes the else branch. Only when it takes an intention lock for writing (IX, section 6) on a table does lock_table() call trx_set_rw_mode() to get an ID and a rollback segment.

  if ((mode == LOCK_IX || mode == LOCK_X) &&
      !trx->read_only && !trx->rsegs.m_redo.rseg)
    trx_set_rw_mode(trx);

storage/innobase/lock/lock0lock.cc, lines 4187–4189

There is an exception. If a transaction that has not started yet goes straight to an INSERT, row_insert_for_mysql() starts it with trx_start_if_not_started_xa(trx, true) (row0mysql.cc, line 1275), so it gets its ID right away in the if branch of trx_start_low(). An UPDATE, a DELETE or a SELECT … FOR UPDATE is first started by row_search_mvcc() with read_write=false and gets its ID at the IX lock.

A transaction that only reads has no ID, so it never goes on trx_sys's list of "active write transactions". The ID list (m_ids, section 3) that other transactions collect when they create a read view gets shorter accordingly. It is a saving made for read-heavy workloads.

What InnoDB does at commit time

Frames #0–#4 of Example 1 are the commit inside InnoDB, in the order trx_t::commit() → commit_persist() → commit_in_memory().

commit_persist() moves this transaction's undo log to the history list (the list that collects undo of committed transactions, section 5) and commits the mini-transaction that did it (write_serialisation_history(), trx0trx.cc, lines 1147–1211). That mini-transaction's LSN is this transaction's commit LSN (commit_lsn). From the disk's point of view, this is the moment of commit.

commit_in_memory() tidies up memory.

TRANSACTIONAL_INLINE inline void trx_t::commit_in_memory(mtr_t *mtr)
{
  /* We already detached from rseg in write_serialisation_history() */
  ut_ad(!rsegs.m_redo.undo);
  read_view.close();
    // ...
    commit_state();
    DEBUG_SYNC_C("trx_after_commit_state");

    if (id)
    {
      trx_sys.deregister_rw(this);
    // ...
    if (UNIV_LIKELY(!dict_operation))
      release_locks();

storage/innobase/trx/trx0trx.cc, lines 1413–1481

1. It closes the read view (line 1417). This transaction no longer needs to see old versions.
2. It changes the state to COMMITTED_IN_MEMORY (commit_state()) and, if it was a write transaction, removes it from trx_sys's active list (deregister_rw()). From this moment on, newly created read views see this transaction's changes.
3. It releases all locks at once (release_locks() → lock_release()). Holding every lock until the end and only then releasing them all is called strict two-phase locking.

Then, on the way back to the server, trx_commit_complete_for_mysql() writes the log to disk up to commit_lsn (trx0trx.cc, lines 1776–1791). With innodb_flush_log_at_trx_commit=0 it does nothing here. What the log and that setting mean is Part 12's topic.

3. Read views and consistent reads — where do old versions come from?

Two hidden columns on every row

Records in InnoDB's clustered index (the primary-key index, which is the table itself — Part 10) carry system columns besides the ones you created. They are added as the last columns when the table definition is loaded into memory.

	dict_mem_table_add_col(table, heap, "DB_TRX_ID", DATA_SYS,
			       DATA_TRX_ID | DATA_NOT_NULL,
			       DATA_TRX_ID_LEN);
	compile_time_assert(DATA_TRX_ID == 1);
	dict_mem_table_add_col(table, heap, "DB_ROLL_PTR", DATA_SYS,
			       DATA_ROLL_PTR | DATA_NOT_NULL,
			       DATA_ROLL_PTR_LEN);
	compile_time_assert(DATA_ROLL_PTR == 2);

storage/innobase/dict/dict0dict.cc, lines 1163–1170

• DB_TRX_ID (6 bytes): the ID of the transaction that last changed this record
• DB_ROLL_PTR (7 bytes): the location of the undo record holding the value before that change

(DB_ROW_ID is a hidden primary key used only by tables without one.) You can see these two columns with your own eyes in the deadlock example's output in section 6 (Example 6). When SHOW ENGINE INNODB STATUS prints a record, it lists 0: the primary key, 1: DB_TRX_ID, 2: DB_ROLL_PTR and 3: the user column, in that order.

ReadView — the table that decides visibility

The heart of a read view is two numbers and one list.

class ReadViewBase
{
  /**
    The read should not see any transaction with trx id >= this value.
    In other words, this is the "high water mark".
  */
  trx_id_t m_low_limit_id= 0;

  /**
    The read should see all trx ids which are strictly
    smaller (<) than this value. In other words, this is the
    low water mark".
  */
  trx_id_t m_up_limit_id;

  /** Set of RW transactions that was active when this snapshot was taken */
  trx_ids_t m_ids;
  // ...
  bool changes_visible(trx_id_t id) const
  MY_ATTRIBUTE((warn_unused_result))
  {
    if (id >= m_low_limit_id)
      return false;
    return id < m_up_limit_id ||
           m_ids.empty() ||
           !std::binary_search(m_ids.begin(), m_ids.end(), id);
  }

storage/innobase/include/read0types.h, lines 38–137

• m_ids: the IDs of write transactions that had not yet committed when the view was created (kept sorted)
• m_up_limit_id: the smallest of those. Every ID below it had committed before the view was created
• m_low_limit_id: the next ID not yet handed out when the view was created. Anything at or above it started after the view

changes_visible(id) decides with these three. ① If id is at least m_low_limit_id, not visible. ② If it is below m_up_limit_id, visible. ③ In between, visible only if it is not in m_ids (it had already committed). The child class's ReadView::changes_visible() adds one more rule, "my own changes are visible" (id == m_creator_trx_id, lines 251–252).

Easy to get wrong: low_limit is the upper bound

The names look backwards. As the comment says, m_low_limit_id is the "high water mark" (upper bound) and m_up_limit_id is the "low water mark" (lower bound). It helps to read them as "the limit below which (low) IDs may be seen" and "the point from which (up) we have to check". SHOW ENGINE INNODB STATUS prints the two as Trx read view will not see trx with id >= <low_limit>, sees < <up_limit> (print_limits(), Example 3 in section 5).

When is a view opened, and when is it closed?

The function that opens a view is ReadView::open().

void ReadView::open(trx_t *trx)
{
  ut_ad(this == &trx->read_view);
  if (is_open())
    ut_ad(!srv_read_only_mode);
  else if (likely(!srv_read_only_mode))
  {
    m_creator_trx_id= trx->id;
    if (trx->is_autocommit_non_locking() && empty() &&
        low_limit_id() == trx_sys.get_max_trx_id())
      m_open.store(true, std::memory_order_relaxed);
    else
    {
      m_mutex.wr_lock();
      snapshot(trx);
      m_open.store(true, std::memory_order_relaxed);
      m_mutex.wr_unlock();
    }
  }
}

storage/innobase/read/read0read.cc, lines 229–248

If the view is already open, it does nothing. The difference between isolation levels comes from this one line and from when the view gets closed.

• Where it is opened: a non-locking read (a plain SELECT, select_lock_type == LOCK_NONE) opens it in row_search_mvcc() when it looks for the statement's first row.

	} else {
		prebuilt->sql_stat_start = FALSE;
		trx_start_if_not_started(trx, false);

		if (prebuilt->select_lock_type == LOCK_NONE) {
			trx->read_view.open(trx);

storage/innobase/row/row0sel.cc, lines 4815–4820

• Where it is closed: at READ COMMITTED and below, it is closed when a statement starts (ha_innobase::store_lock()) and when it ends (F_UNLCK in ha_innobase::external_lock()).

	if (lock_type != TL_IGNORE
	    && trx->n_mysql_tables_in_use == 0) {
		switch ((trx->isolation_level
			 = innodb_isolation_level(thd) & 3)) {
		case ISO_REPEATABLE_READ:
			break;
		case ISO_READ_COMMITTED:
		case ISO_READ_UNCOMMITTED:
			/* At low transaction isolation levels we let
			each consistent read set its own snapshot */
			trx->read_view.close();
			break;

storage/innobase/handler/ha_innodb.cc, lines 17102–17113

		if (!not_autocommit) {
			if (!not_started) {
				innobase_commit(thd, TRUE);
			}
		} else if (trx->isolation_level <= TRX_ISO_READ_COMMITTED) {
			trx->read_view.close();
		}

storage/innobase/handler/ha_innodb.cc, lines 16812–16818

So READ COMMITTED opens a new view for every statement, while REPEATABLE READ keeps the view opened by the transaction's first read until commit (section 2's commit_in_memory()). START TRANSACTION WITH CONSISTENT SNAPSHOT makes the server go through ha_start_consistent_snapshot() (transaction.cc, lines 217–224) to InnoDB's innobase_start_trx_and_assign_read_view(), which opens the view on the spot (ha_innodb.cc, lines 4579–4617). SERIALIZABLE, when autocommit is off, makes even plain SELECTs take shared locks (LOCK_S) (lines 16836–16850).

Building an old version — climbing the undo chain

If the DB_TRX_ID of a record it read is not visible to the view, row_search_mvcc() finds that out with row_sel_clust_sees() (row0sel.cc, lines 961–981) and builds an old version with row_vers_build_for_consistent_read(). It follows DB_ROLL_PTR back through the undo records one at a time, rolling back until it reaches a visible version.

All the yellow boxes are buffer pool pages: the record lives on an index page, the old values on undo pages. The numbers were picked for illustration.

		err = trx_undo_prev_version_build(
			version, index, *offsets, heap,
			&prev_version, mtr, 0, NULL, vrow);
		// ...
		if (prev_version == NULL) {
			/* It was a freshly inserted version */
			*old_vers = NULL;
			ut_ad(!vrow || !(*vrow));
			break;
		}
		// ...
		trx_id = row_get_rec_trx_id(prev_version, index, *offsets);

		if (view->changes_visible(trx_id)) {

storage/innobase/row/row0vers.cc, lines 760–785

trx_undo_prev_version_build() applies one undo record to build the version one step older (prev_version), and the loop stops when that version's DB_TRX_ID is visible to the view. If prev_version is NULL, the row "was inserted after the view was created", so for this transaction the row does not exist. The old version is built in separately allocated memory (in_heap) without touching the page.

When reading through a secondary index, the secondary index record has no DB_TRX_ID. So InnoDB first filters with "the largest transaction ID that changed this page" in the page header (page_get_max_trx_id()), and if that is not conclusive, goes to the clustered index and makes the same decision there (row0sel.cc, lines 5540–5578).

Example 2: read views seen with two sessions

This is ex/u11-mvcc-snapshot. Session A holds a transaction in one mariadb client kept open on a FIFO; session B connects fresh for every statement and commits right away with autocommit.

mkfifo /tmp/a.in
mariadb -n -f -N lab < /tmp/a.in 2>&1 &
exec 3> /tmp/a.in
A() { echo "$1" >&3; sleep 1; }                  # one statement to session A
B() { mariadb lab -e "$1"; echo "    (B: $1)"; }  # session B commits right away

The table is t(id, val) with a single row (1, 'v1'). A's SELECTs print the step name and the value on one line, as in 'A first read' AS step, val (with -N, without column names, separated by tabs).

settings	REPEATABLE-READ	1
--- 1. REPEATABLE READ: the view is opened by the first read and kept
A first read	v1
    (B: UPDATE t SET val = 'v2' WHERE id = 1)
A after B commit	v1
A after own COMMIT	v2
--- 2. READ COMMITTED: every statement gets a fresh view
A first read	v2
    (B: UPDATE t SET val = 'v3' WHERE id = 1)
A after B commit	v3
--- 3. REPEATABLE READ, but BEGIN does not open the view
    (B: UPDATE t SET val = 'v4' WHERE id = 1)
A first read	v4
    (B: UPDATE t SET val = 'v5' WHERE id = 1)
A second read	v4
--- 4. START TRANSACTION WITH CONSISTENT SNAPSHOT opens it at once
    (B: UPDATE t SET val = 'v6' WHERE id = 1)
A first read	v5
--- 5. A now writes the row it cannot see (innodb_snapshot_isolation=ON)
--------------
UPDATE t SET val = 'A-wins' WHERE id = 1
--------------

ERROR 1020 (HY000) at line 20: Record has changed since last read in table 't'; try restarting transaction
A after error	0
final	v6

The first line shows the default isolation level (REPEATABLE-READ) and innodb_snapshot_isolation (1 = on).

1. Under REPEATABLE READ, A does not see the v2 that B committed, and only sees it after its own commit closes the view. The v1 A saw in between is an old version built from the undo B's UPDATE left behind.
2. Under READ COMMITTED, the second SELECT in the same transaction sees v3, because the view is closed and reopened for every statement.
3. Even under REPEATABLE READ, the v4 that B committed after BEGIN but before the first read is visible. The view was opened by the first read, not by BEGIN; only the later v5 is invisible.
4. WITH CONSISTENT SNAPSHOT opens the view right when the statement is sent, so even v6, committed before the first read, is invisible.
5. We look at step 5 separately below.

Easy to get wrong: the snapshot is not taken at BEGIN

"REPEATABLE READ sees the data as of the start of the transaction" is only half right. As step 3 shows, the reference point is the first non-locking read. If an application does something else right after BEGIN and reads for the first time much later, it sees every commit made in between. If you want the snapshot at BEGIN, use START TRANSACTION WITH CONSISTENT SNAPSHOT.

Changing a row you cannot see — error 1020

In step 5 of Example 2, the transaction from step 4 (whose view shows v5) tries to change the row that B has already changed to v6 and committed. The result is error 1020; @@in_transaction is 0 afterwards, so A's transaction is already over. The row stays at B's v6.

UPDATE locks and changes the current version, not an old one. But the current version was written by a transaction A's view cannot see. Overwriting it would mean A overwrites "a value it has never seen" (a lost update), so InnoDB at the reference commit stops it just before taking the lock.

	if (heap_no > PAGE_HEAP_NO_SUPREMUM && gap_mode != LOCK_GAP
	    && trx->snapshot_isolation
	    && trx->read_view.is_open()) {
		trx_id = trx_read_trx_id(rec + row_trx_id_offset(rec, index));
		if (!trx->read_view.changes_visible(trx_id)
		    && IF_WSREP(!(trx->is_wsrep()
			&& wsrep_thd_skip_locking(trx->mysql_thd)), true)) {
			/* Our record was last modified by a transaction that
			we should not see. If that transaction has been
			committed, we can return an error immediately,
			without waiting for a record lock. */
			if (!trx_sys.is_registered(trx, trx_id)) {
				return DB_RECORD_CHANGED;
			}

storage/innobase/lock/lock0lock.cc, lines 6648–6661

trx->snapshot_isolation comes from the session variable innodb_snapshot_isolation, whose default at the reference commit is TRUE.

static MYSQL_THDVAR_BOOL(snapshot_isolation, PLUGIN_VAR_OPCMDARG,
  "Use snapshot isolation (write-write conflict detection)",
  NULL, NULL, TRUE);

storage/innobase/handler/ha_innodb.cc, lines 905–907

DB_RECORD_CHANGED goes up to the server as HA_ERR_RECORD_CHANGED (error 1020), and the whole transaction is rolled back (@@in_transaction was 0 in Example 2). We see where the rollback happens in section 4. I did not check in the source which version introduced this variable or what its default is in each version; all I can say is that it is on at the reference commit.

4. The undo log — material for rollback and for old versions

Undo is written before the change

Every time a row is INSERTed, UPDATEd or DELETEd, InnoDB writes an undo record with trx_undo_report_row_operation() before changing the clustered index (trx0rec.cc, lines 1828–2088). For an INSERT it records "this key was inserted" (trx_undo_page_report_insert()); for an UPDATE or DELETE, "the values before the change were these" (trx_undo_page_report_modify()). At the end it turns the location into a DB_ROLL_PTR value and returns it.

		} else {
			/* Success */
			undo->top_page_no = undo_block->page.id().page_no();
			mtr.commit();

			undo->old_offset = offset;
			undo->top_offset  = offset;
			undo->top_undo_no = trx->undo_no++;
			// ...
			if (!bulk) {
				*roll_ptr = trx_undo_build_roll_ptr(
					!rec, trx_sys.rseg_id(rseg, !is_temp),
					undo->top_page_no, offset);
			}

storage/innobase/trx/trx0rec.cc, lines 2023–2051

Writing an undo page is wrapped in its own mini-transaction (mtr), which leaves redo log. So after a crash the undo is recovered too, and once recovery is done, unfinished transactions can be rolled back using it (Part 12). trx->undo_no++ is "the number of the undo record this transaction wrote". A SAVEPOINT simply remembers this number (innobase_hton->savepoint_offset = sizeof(undo_no_t), line 4302), and section 6's deadlock detection uses it to measure "the cost of rolling back".

A DELETE does not remove the record right away; it only puts a delete mark on it, because other transactions' views must still see the row. The real removal is done by purge in section 5.

Rollback — applying undo in reverse

On ROLLBACK, the server's ha_rollback_trans() calls innobase_rollback(), and InnoDB applies the undo records in reverse, last one first, in trx_t::rollback() → rollback_low() (trx0roll.cc, lines 95–161). The actual undoing lives in row/row0uins.cc (undoing an INSERT — deleting the record) and row/row0umod.cc (undoing an UPDATE or DELETE). At the end, rollback_finish() tidies up by calling the same commit() as a commit does. In the end a rollback finishes as "the commit of a transaction with no changes".

What gets undone when an error happens?

How much is undone depends on the kind of error. The fork in the road is row_mysql_handle_errors().

	case DB_LOCK_WAIT_TIMEOUT:
		extern my_bool innobase_rollback_on_timeout;
		if (innobase_rollback_on_timeout) {
			goto rollback;
		}
		/* fall through */
	// ...
	case DB_LOCK_WAIT:
		err = lock_wait(thr);
	// ...
	case DB_DEADLOCK:
	case DB_RECORD_CHANGED:
	case DB_LOCK_TABLE_FULL:
	case DB_TEMP_FILE_WRITE_FAIL:
	rollback:
		/* Roll back the whole transaction; this resolution was added
		to version 3.23.43 */
		trx->rollback();
		break;

storage/innobase/row/row0mysql.cc, lines 657–719

• Lock wait timeout (DB_LOCK_WAIT_TIMEOUT, error 1205): with innodb_rollback_on_timeout off (default FALSE, lines 19762–19765), only that statement is undone (rollback_to_savept). The transaction stays alive, so the application has to retry or roll back itself.
• Deadlock (DB_DEADLOCK, error 1213) and section 3's DB_RECORD_CHANGED (error 1020): the whole transaction is undone (trx->rollback()).

On DB_LOCK_WAIT, it goes to sleep in lock_wait() as on line 702 above and continues the statement once it gets the lock (lines 701–709). Example 5 in section 6 is a thread stopped at exactly that line 702.

The yellow box undoes just the statement; the red box undoes the whole transaction. The branches were checked in row0mysql.cc lines 657–719 (the return to handle_new_error when lock_wait() fails is lines 701–705).

5. Purge — cleaning up old versions nobody sees

The undo of a committed transaction cannot be thrown away immediately: as in section 3, another view that is still open may need it to build an old version. So at commit the undo is moved to the rollback segment's history list (rseg->history_size++ in trx_purge_add_undo_to_history(), trx0purge.cc, line 190), and purge, in the background, picks out and removes only what "nobody will look at any more".

The red box is a problem you meet often in production. A single oldest view holds back all of purge.

Every time the purge coordinator's trx_purge() runs, it first builds "the oldest view", a merge of all currently open views, with purge_sys.clone_oldest_view() (trx0purge.cc, lines 1451–1456). The merging is done by trx_sys.

void trx_sys_t::clone_oldest_view(ReadViewBase *view) const
{
  view->snapshot(nullptr);
  /* Find oldest view. */
  trx_list.for_each([view](const trx_t &trx) {
                      trx.read_view.append_to(view);
		    });
}

storage/innobase/read/read0read.cc, lines 258–265

It walks every transaction in trx_list and merges the open views with append_to(). Undo older than the merged view's m_low_limit_no is needed by no view and can be removed (the comment at read0types.h, lines 56–61). Put the other way round, if a single REPEATABLE READ transaction keeps its view open for a long time, all undo committed after it piles up. When the history gets too long, there is also a mechanism that deliberately slows DML down if innodb_max_purge_lag is set (srv_dml_needed_delay, trx0purge.cc, lines 1468–1480).

Example 3: the history list length going up and down

This is ex/u11-purge-history. While A keeps a REPEATABLE READ view open, B changes one row 300 times (one transaction each), and we pick two lines out of SHOW ENGINE INNODB STATUS.

history() {
  mariadb -e "SHOW ENGINE INNODB STATUS\G" | grep -E "History list length|read view will not see"
}

--- 0. idle server
History list length 0
--- 1. A opens a REPEATABLE READ view and keeps it
A sees	0
--- 2. B commits 300 small updates (one transaction each)
History list length 300
Trx read view will not see trx with id >= 21, sees < 21
A still sees	0
--- 3. A commits; purge may now remove the old versions
History list length 0
final	300

• Each of B's 300 transactions adds one to the history as it commits, reaching 300. With A's view open, purge could not remove a single one.
• Trx read view will not see trx with id >= 21, sees < 21 is A's view (21 is set by how many IDs the freshly started server had handed out so far; the example uses a new container every time, so a rerun gave 21 again, but a server that has been running for a while shows a much larger number). For A's SELECT to keep seeing 0, it must climb 300 undo records back from the current version (300). An old view not only blocks purge; it also makes that view's own reads slower.
• Once A committed and its view closed, the history went back to 0 within 5 seconds.

The History list length line is printed by lock_print_info_summary() (lock0lock.cc, line 5469).

6. Locks — row locks, gaps, waiting and deadlocks

Thanks to MVCC, a plain SELECT reads without locks. Locks are needed for writes and locking reads (SELECT … FOR UPDATE, … LOCK IN SHARE MODE). These read and change the current version, so two of them must not change the same row at the same time.

Lock modes and the compatibility matrix

There are five lock modes in enum lock_mode: LOCK_IS, LOCK_IX, LOCK_S, LOCK_X and LOCK_AUTO_INC (lock0types.h, lines 39–49). Rows only get S (shared) and X (exclusive). Tables usually get the intention locks IS and IX, which say "I intend to put S (X) on some rows of this table". They let someone who wants to lock the whole table, as LOCK TABLES does, and someone locking rows notice each other quickly. The compatibility matrix:

static const byte lock_compatibility_matrix[5][5] = {
 /**         IS     IX       S     X       AI */
 /* IS */ {  TRUE,  TRUE,  TRUE,  FALSE,  TRUE},
 /* IX */ {  TRUE,  TRUE,  FALSE, FALSE,  TRUE},
 /* S  */ {  TRUE,  FALSE, TRUE,  FALSE,  FALSE},
 /* X  */ {  FALSE, FALSE, FALSE, FALSE,  FALSE},
 /* AI */ {  TRUE,  TRUE,  FALSE, FALSE,  FALSE}
};

storage/innobase/include/lock0priv.h, lines 367–374

Row locks are bitmaps per page

Making an object for every single row lock would run out of memory. InnoDB makes one lock_t per page, transaction and mode, and sets the bit in its bitmap that matches the record's heap number (its sequence number within the page, Part 10). These lock_t objects live in lock_sys.rec_hash, a hash looked up by page number (lock0lock.h, lines 752–757). The skeleton of lock_rec_lock(), which takes a record lock, looks like this.

  const page_id_t id{block->page.id()};
  LockGuard g{lock_sys.rec_hash, id};

  if (lock_t *lock= lock_sys_t::get_first(g.cell(), id))
      // ...
      if (!held_lock)
      {
        conflicting_lock_info c_lock_info=
            lock_rec_other_has_conflicting(mode, g.cell(), id, heap_no, trx);
        if (c_lock_info.conflicting)
          /*
            If another transaction has a non-gap conflicting
            request in the queue, as this transaction does not
            have a lock strong enough already granted on the
            record, we have to wait.
          */
          err= lock_rec_enqueue_waiting(c_lock_info, mode, id,
                                        block->page.frame, heap_no, index, thr,
                                        nullptr);
  // ...
  /* Simplified and faster path for the most common cases */
  if (!impl)
    lock_rec_create(null_c_lock_info, mode, id, block->page.frame, heap_no,
                    index, trx, false);

  return DB_SUCCESS_LOCKED_REC;

storage/innobase/lock/lock0lock.cc, lines 1962–2042

It latches the hash cell for the page number (LockGuard). If the page already has locks, it checks whether this transaction already holds a strong enough lock (lock_rec_has_expl()) and whether it conflicts with another transaction (lock_rec_other_has_conflicting()); on a conflict it queues a waiting lock (lock_rec_enqueue_waiting()). In the most common case, a page with no locks at all, there is nothing to check and it simply creates one with lock_rec_create(). In Example 4's SHOW ENGINE INNODB STATUS output you can see a transaction that read a range FOR UPDATE holding 2 lock struct(s), heap size 1144, 2 row lock(s): one table lock (IX) and one record lock object holding two records as bits.

An INSERTed row gets no lock object. For a newly inserted record, the fact that its DB_TRX_ID is a still-active transaction is enough to count as "that transaction holds an X lock" (an implicit lock). Only when another transaction tries to lock the row does lock_rec_convert_impl_to_expl() turn it into a real lock object (the comment at lock0lock.cc, lines 6277–6303).

Gap locks and next-key locks

Bits saying "what exactly is locked" are added to a row lock's mode (S/X) (lock0types.h, lines 110–135).

Under REPEATABLE READ, a locking range read puts a next-key lock on every record it passes, so no new row can sneak into the range (so that reading the same range again gives the same result — preventing "phantoms"). The conflict rules between gaps are unusual.

	if ((lock_is_on_supremum || (type_mode & LOCK_GAP))
	    && !(type_mode & LOCK_INSERT_INTENTION)) {

		/* Gap type locks without LOCK_INSERT_INTENTION flag
		do not need to wait for anything. This is because
		different users can have conflicting lock types
		on gaps. */

		return false;
	}

storage/innobase/lock/lock0lock.cc, lines 777–786

Gap locks never wait for each other. Two transactions can hold gap locks on the same gap at the same time. The only thing a gap lock blocks is an INSERT (LOCK_INSERT_INTENTION). Rules such as "a record lock does not wait for a gap lock" and "nobody waits for an insert intention" follow after this (lines 788–817).

Waiting — lock_wait()

Deadlock detection is not done by a separate watchdog thread; the thread about to wait does it itself, just before it goes to sleep.

lock_wait() has two key spots. Before sleeping it checks for a deadlock,

    wait_lock= Deadlock::check_and_resolve(trx, wait_lock);

    if (wait_lock == reinterpret_cast<lock_t*>(-1))
    {
      trx->error_state= DB_DEADLOCK;
      goto end_wait;

storage/innobase/lock/lock0lock.cc, lines 2353–2358

and if there is none, it sleeps on the per-transaction condition variable trx->lock.cond with my_cond_timedwait() up to innodb_lock_wait_timeout (default 50 seconds, ha_innodb.cc, lines 924–926) (lock0lock.cc, lines 2395–2409). When the holder releases the lock, lock_grant() wakes this condition variable.

It is also worth noticing that before sleeping it tells the server "this thread is sleeping on a lock" with thd_wait_begin() (line 2324). The thread pool (Part 4) receives this notice and lowers the group's count of active workers; if that count hits 0 while there is still work to do, or no listener thread is watching the connections, it wakes or creates another worker (threadpool_generic.cc, lines 1283–1300).

Example 4: watching a lock wait in information_schema

This is ex/u11-lock-wait. Table t has id 10, 20 and 30. In step 1, B tries to UPDATE a row A has grabbed with SELECT * FROM t WHERE id = 20 FOR UPDATE; in step 2, A reads id BETWEEN 11 AND 25 FOR UPDATE and B tries to INSERT 15. While B waits, we print the three information_schema tables, plus PROCESSLIST to see the waiting statement.

SELECT trx_id, trx_state, trx_rows_locked, LEFT(trx_query, 40) AS trx_query
  FROM information_schema.INNODB_TRX ORDER BY trx_started;
SELECT lock_trx_id, lock_mode, lock_type, lock_index, lock_data
  FROM information_schema.INNODB_LOCKS ORDER BY lock_trx_id;
SELECT requesting_trx_id, blocking_trx_id FROM information_schema.INNODB_LOCK_WAITS;
SELECT ID, STATE, LEFT(INFO, 40) AS INFO FROM information_schema.PROCESSLIST
 WHERE INFO LIKE 'INSERT%' OR INFO LIKE 'UPDATE%';

The step 1 output has the same shape as step 2, so I left it out (B (24) waits for A (23); both locks are X with lock_data 20). Here is the output of steps 2 and 3 (step 2's heading line and the rows A printed in that step are left out). In step 2 we also printed the transaction list of SHOW ENGINE INNODB STATUS while B waits (SET GLOBAL innodb_status_output_locks = ON at the start of the example; for records only the primary-key field 0: is kept).

+--------+-----------+-----------------+----------------------------------+
 trx_id | trx_state | trx_rows_locked | trx_query                        |
+--------+-----------+-----------------+----------------------------------+
     26 | RUNNING   |               2 | NULL                             |
     27 | LOCK WAIT |               1 | INSERT INTO t VALUES (15, 'gap') |
+--------+-----------+-----------------+----------------------------------+
+-------------+-----------+-----------+------------+-----------+
 lock_trx_id | lock_mode | lock_type | lock_index | lock_data |
+-------------+-----------+-----------+------------+-----------+
          26 | X         | RECORD    | PRIMARY    | 20        |
          27 | X,GAP     | RECORD    | PRIMARY    | 20        |
+-------------+-----------+-----------+------------+-----------+
+-------------------+-----------------+
 requesting_trx_id | blocking_trx_id |
+-------------------+-----------------+
                27 |              26 |
+-------------------+-----------------+
+----+--------+----------------------------------+
 ID | STATE  | INFO                             |
+----+--------+----------------------------------+
  8 | Update | INSERT INTO t VALUES (15, 'gap') |
+----+--------+----------------------------------+
---TRANSACTION 27, ACTIVE 2 sec inserting
LOCK WAIT 2 lock struct(s), heap size 1144, 1 row lock(s)
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 27 lock_mode X locks gap before rec insert intention waiting
 0: len 4; hex 80000014; asc     ;;
TABLE LOCK table `lab`.`t` trx id 27 lock mode IX
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 27 lock_mode X locks gap before rec insert intention waiting
 0: len 4; hex 80000014; asc     ;;
---TRANSACTION 26, ACTIVE 3 sec
2 lock struct(s), heap size 1144, 2 row lock(s)
TABLE LOCK table `lab`.`t` trx id 26 lock mode IX
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 26 lock_mode X
 0: len 4; hex 80000014; asc     ;;
 0: len 4; hex 8000001e; asc     ;;
    C: INSERT 35 went through
--------------
INSERT INTO t VALUES (15, 'gap')
--------------

ERROR 1205 (HY000) at line 1: Lock wait timeout exceeded; try restarting transaction
    B: INSERT 15 returned
--- 3. same thing under READ COMMITTED
+----+------+
 id | val  |
+----+------+
 20 | B    |
+----+------+
    B: INSERT 15 went through

• Step 1: B (24) waited for A (23) and finished once A committed (B: UPDATE finished). A waiting statement only shows up as Update in PROCESSLIST (Updating in step 1). To tell that it is asleep on a lock inside the engine, look for LOCK WAIT in INNODB_TRX.
• Step 2: A's (26) range read put next-key locks (a plain lock_mode X with no qualifier) on 20 (80000014) and on 30 (8000001e), where the scan stopped past the range. The lock objects are one table IX and one record lock; the two records are two bits of the same object. Inserting 15 requires an insert intention on "the gap before 20", so B (27) waits as locks gap before rec insert intention waiting (B's waiting lock is printed twice, in the TRX HAS BEEN WAITING … FOR THIS LOCK TO BE GRANTED section and in the lock list; that header line was filtered out by grep, lock0lock.cc, lines 5498–5513). After innodb_lock_wait_timeout = 4 it failed with error 1205, rolling back only that statement. 35, on the other hand, goes into the gap after 30, which nobody locked, so it went straight in.
• Step 3: under READ COMMITTED the same range read does not lock gaps (records only, LOCK_REC_NOT_GAP), so 15 went straight in.

One next-key lock covers a record and the gap before it. Keys, transaction numbers and outcomes are the actual output of step 2 in Example 4.

Transaction IDs (23, 24, 26, 27) and connection IDs are set by how many transactions and connections the freshly started server has seen, so in this example, which uses a new container every time, a rerun gave the same values; in another environment they will differ. The seconds in ACTIVE 3 sec, on the other hand, depend on timing: a rerun printed ACTIVE 4 sec.

Easy to get wrong: what INNODB_LOCKS does not show

This table has two limits.

1. It only shows locks involved in a wait. A's IX table lock and its lock on 30 appear in SHOW ENGINE INNODB STATUS but not in INNODB_LOCKS, because add_trx_relevant_locks_to_cache(), which fills the table, only adds the waiting lock and the locks blocking it (trx0i_s.cc, lines 882–952).
2. lock_mode has only nine values (S, S,GAP, X, X,GAP, IS … AUTO_INC, i_s.cc, lines 566–577). So a next-key lock and a record-only lock both show up as X, and B's insert intention shows up as X,GAP. For the exact kind, look for phrases such as locks rec but not gap, locks gap before rec and insert intention in SHOW ENGINE INNODB STATUS (innodb_status_output_locks=ON), as in the output above (lock0lock.cc, lines 5334–5359).

Example 5: a backtrace stopped in lock_wait()

This is the first step of the same ex/u11-gdb-commit as Example 1. With A holding its change to row 20, gdb is set on lock_wait and B UPDATEs the same row. Frames #6–#13 in the middle (the range read and the Multi-Range Read wrappers, from handler::read_range_first() to READ_RECORD::read_record()) are shortened to ....

#0  lock_wait at storage/innobase/lock/lock0lock.cc:2237
#1  row_mysql_handle_errors at storage/innobase/row/row0mysql.cc:702
#2  row_search_mvcc<InnoDBPolicy<true, true> > at storage/innobase/row/row0sel.cc:6063
#3  ha_innobase::index_read at storage/innobase/handler/ha_innodb.cc:9220
#4  handler::index_read_map at sql/handler.h:4443
#5  handler::ha_index_read_map at sql/handler.cc:4215
...
#14 Sql_cmd_update::update_single_table at sql/sql_update.cc:993
#15 Sql_cmd_update::execute_inner at sql/sql_update.cc:3324
#16 Sql_cmd_dml::execute at sql/sql_select.cc:36000
#17 mysql_execute_command at sql/sql_parse.cc:4493
#18 mysql_parse at sql/sql_parse.cc:8005
#19 dispatch_command at sql/sql_parse.cc:1903
#20 do_command at sql/sql_parse.cc:1437

An UPDATE first reads the rows it will change. The server's UPDATE execution (#14) calls handler::ha_index_read_map() (the ha_ wrapper from Part 9, #5) for a range read; InnoDB's row_search_mvcc() (#2) asked for an X lock on the row, got DB_LOCK_WAIT, and went to sleep in lock_wait() at line 702 of section 4's row_mysql_handle_errors() (#1). The fact that a write waits for its lock in "the reading function", not "the writing function", feels strange at first.

Finding deadlocks — a cycle in the wait_trx chain

A waiting transaction records "the transaction I am waiting for" in trx->lock.wait_trx. If following these arrows leads back to the start, it is a deadlock. Deadlock::find_cycle() finds this cycle with Brent's cycle-detection algorithm (a way of finding a cycle with two pointers, a tortoise and a hare, without extra memory).

  inline trx_t *find_cycle(trx_t *trx)
  {
    mysql_mutex_assert_owner(&lock_sys.wait_mutex);
    trx_t *tortoise= trx, *hare= trx;
    for (unsigned power= 1, l= 1; (hare= hare->lock.wait_trx) != nullptr; l++)
    {
      if (tortoise == hare)
      {
        ut_ad(l > 1);
        /* Note: Normally, trx should be part of any deadlock cycle
        that is found. However, if innodb_deadlock_detect=OFF had been
        in effect in the past, it is possible that trx will be waiting
        for a transaction that participates in a pre-existing deadlock
        cycle. In that case, our victim will not be trx. */
        return hare;
      }
    // ...
    }
    return nullptr;
  }

storage/innobase/lock/lock0lock.cc, lines 314–342

Once a cycle is found, Deadlock::report() picks a victim inside it (lock0lock.cc, lines 7310–7395). The criterion is calc_victim_weight(), which packs a few bits into a single number and picks the smallest (lines 7283–7302). The main weight is this macro.

#define TRX_WEIGHT(t)	((t)->undo_no + UT_LIST_GET_LEN((t)->lock.trx_locks))

storage/innobase/include/trx0trx.h, line 260

Undo records plus locks — in other words, the one that is cheaper to roll back is sacrificed. A transaction that changed non-transactional tables (MyISAM and the like) has done something that cannot be undone, so it is avoided as a victim (bit 62), and when the weights are equal, the transaction that just asked for the lock is the victim (bit 0). With innodb_deadlock_detect=OFF (default ON, lines 19963–19968) this detection is skipped and the timeout is left to deal with it.

Example 6: making a deadlock and reading LATEST DETECTED DEADLOCK

This is ex/u11-deadlock. A changes row 1 and B changes row 2; then A tries to change 2 and B tries to change 1. Both sessions are opened on FIFOs, and their output is prefixed with A| and B|.

--- 1. A locks 1, B locks 2, then each wants the other's row
B| --------------
B| UPDATE t SET val = 'B' WHERE id = 1
B| --------------
B| 
B| ERROR 1213 (40001) at line 2: Deadlock found when trying to get lock; try restarting transaction
B| step	@@in_transaction
B| B in trx	0
A| step	@@in_transaction
A| A in trx	1
--- 2. result and deadlock counter
+----+------+
 id | val  |
+----+------+
  1 | A    |
  2 | A    |
+----+------+
+------------------+-------+
 Variable_name    | Value |
+------------------+-------+
 Innodb_deadlocks | 1     |
+------------------+-------+

B got error 1213 and its whole transaction was rolled back (B in trx 0), while A changed row 2 once B's lock was released and committed. Here is the LATEST DETECTED DEADLOCK section of SHOW ENGINE INNODB STATUS (only part of it, with cuts marked ...; it is from the same run as the output above. The time, the thread handle and the seconds in ACTIVE … sec differ from run to run).

...
*** (1) TRANSACTION:
TRANSACTION 24, ACTIVE 2 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1144, 2 row lock(s), undo log entries 1
MariaDB thread id 6, OS thread handle 139695959480000, query id 11 localhost root Updating
UPDATE t SET val = 'B' WHERE id = 1
*** WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 24 lock_mode X locks rec but not gap waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 4; hex 80000001; asc     ;;
 1: len 6; hex 000000000017; asc       ;;
 2: len 7; hex 060000002e0110; asc     .  ;;
 3: len 1; hex 41; asc A;;

*** CONFLICTING WITH:
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 23 lock_mode X locks rec but not gap
...
*** (2) TRANSACTION:
TRANSACTION 23, ACTIVE 3 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1144, 2 row lock(s), undo log entries 1
...
UPDATE t SET val = 'A' WHERE id = 2
*** WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 8 page no 3 n bits 320 index PRIMARY of table `lab`.`t` trx id 23 lock_mode X locks rec but not gap waiting
...
*** WE ROLL BACK TRANSACTION (1)

• Because the UPDATE finds one row by primary key, the locks are locks rec but not gap (LOCK_REC_NOT_GAP).
• The four fields of the record are exactly section 3's hidden columns: 0: primary key 1 (80000001, stored with the sign bit flipped), 1: DB_TRX_ID = 0x17 = 23 (A changed it), 2: DB_ROLL_PTR, 3: the 'A' that A wrote.
• The two transactions weighed the same (one undo record, three lock objects), so B, the one that asked for its lock last — (1) — was the victim.

What this post leaves out

• The InnoDB side of XA and two-phase commit (innobase_xa_prepare(), innobase_xa_recover(), TRX_STATE_PREPARED): storage/innobase/handler/ha_innodb.cc, Part 12
• How SAVEPOINT is implemented: innobase_savepoint(), innobase_rollback_to_savepoint() (around line 5060 of ha_innodb.cc)
• The AUTO_INC table lock and innodb_autoinc_lock_mode: LOCK_AUTO_INC in lock_table(), lock/lock0lock.cc
• Predicate locks for spatial indexes: lock/lock0prdt.cc
• The latch partitioning of lock_sys (lock_sys_t::hash_latch, LockGuard) and transactional memory (TMLockGuard): include/lock0lock.h
• trx_sys's rw_trx_hash (a lock-free hash) and rw_trx_ids for snapshots: include/trx0sys.h, trx/trx0sys.cc
• READ COMMITTED's "semi-consistent read" (an UPDATE first looks at the last committed version of a locked row and skips it if the condition doesn't match): did_semi_consistent_read in row_search_mvcc()
• SKIP LOCKED (prebuilt->skip_locked, around the row0sel.cc excerpts above)
• Undo tablespaces and innodb_undo_log_truncate: trx_purge_truncate_history() in trx/trx0purge.cc
• The part of purge that really removes records: row/row0purge.cc
• Galera's BF abort (the wsrep_* blocks): left out of this build

Summary

What to read next

Three things in this post were only mentioned in passing: "flush the log", "roll back with undo after a crash" and "two-phase commit when the binlog is on". How the redo log left by mini-transactions gets into the log buffer and ib_logfile0, and where innodb_flush_log_at_trx_commit changes that; crash recovery, which reapplies redo and rolls back unfinished transactions; and the two-phase commit that keeps InnoDB's redo and the server's binlog in step — all of that is in Part 12: Two Logs — the Redo Log, the Binlog and Crash Recovery, and Wrapping Up.

We saw transactions from the application side in Spring Part 17. When an @Transactional method finishes, Spring's transaction manager calls JDBC Connection.commit(), which ends up as section 1's COMMIT → ha_commit_trans(). Spring's isolation attribute is passed to JDBC Connection.setTransactionIsolation() and becomes the connection's isolation level, which section 3's ha_innobase::store_lock() copies into trx->isolation_level (I did not check what statement the JDBC driver actually sends to the server). Spring decides "when to open and when to close"; what is visible and who waits in between is decided here, by InnoDB.

Not all "waiting" is the same. The metadata lock of Part 7 (Waiting for table metadata lock) is a lock the server layer's MDL_context takes to protect table definitions; this post's row locks are taken by InnoDB to protect records. An open transaction blocking ALTER TABLE is the former; SELECT … FOR UPDATE blocking another UPDATE is the latter.

• Part 10: InnoDB Part 1 — Pages, the Buffer Pool and B-trees
• Part 9: Execution and the Handler API — How the Nested-Loop Join Calls the Engine
• Part 4: Connections and Threads — One Thread per Connection, and the Thread Pool
• Spring Part 18: JdbcTemplate — the Template-Callback Pattern and Exception Translation