Understanding InnoDB Deadlock Detection Thread and Lock‑Wait Snapshot Construction

1. Simulating a Deadlock

We create a test table t1 with an auto‑increment primary key and an index on column i1 , insert four rows, and open four connections, each starting a transaction that acquires row locks in a specific order to form a circular wait.

CREATE TABLE `t1` (
  `id` int unsigned NOT NULL AUTO_INCREMENT,
  `i1` int DEFAULT '0',
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_i1` (`i1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb3;

INSERT INTO `t1` (`id`,`i1`) VALUES
(10,101),(20,201),(30,301),(40,401);

-- Connection 1 (Transaction 1)
BEGIN;
SELECT id FROM t1 WHERE id = 10 FOR UPDATE;

-- Connection 2 (Transaction 2)
BEGIN;
SELECT id FROM t1 WHERE id = 20 FOR UPDATE;

-- Connection 3 (Transaction 3)
BEGIN;
SELECT i1 FROM t1 WHERE id = 10 FOR UPDATE;

-- Connection 4 (Transaction 4)
BEGIN;
SELECT id,i1 FROM t1 WHERE id = 10 FOR UPDATE;

-- Continue the sequence to create the wait‑for relationships
SELECT i1 FROM t1 WHERE id = 20 FOR UPDATE;
SELECT * FROM t1 WHERE id = 10 FOR UPDATE;

The resulting wait relationships are:

Transaction 3 waits for Transaction 1 on id = 10 .

Transaction 4 waits for Transaction 1 on id = 10 .

Transaction 1 waits for Transaction 2 on id = 20 .

Transaction 2 waits for Transaction 1 on id = 10 .

2. Deadlock Check Thread

InnoDB runs a background thread named ib_srv_lock_to that wakes every second to check for lock‑wait timeouts and also to detect deadlocks. This thread listens for a lock‑wait event with a one‑second timeout; if a transaction enters a wait state, the thread is notified immediately and performs a deadlock check.

3. Lock‑Wait Snapshot

When a transaction begins waiting, the thread records its information in a free slot of the waiting_threads array, creating a waiting_trx_info_t (snapshot object) that stores the waiting transaction, the blocking transaction, the slot object, and a version number.

Example snapshot object for Transaction 3:

{
  Transaction 3,   /* waiting transaction */
  Transaction 1,   /* blocking transaction */
  srv_slot_t 0,   /* slot containing the srv_slot_t object */
  4               /* version number */
}

All four transactions produce a snapshot array of four such objects.

4. Lock‑Wait Graph

The snapshot array is first sorted by the memory address of the transaction objects. Using the sorted array, InnoDB builds a lock‑wait graph represented as a lock‑wait array where each index corresponds to a waiting transaction and the value is the transaction it waits for.

[
  0: 1,  /* Transaction 1 waits for Transaction 2 */
  1: 0,  /* Transaction 2 waits for Transaction 1 */
  2: 0,  /* Transaction 3 waits for Transaction 1 */
  3: 0   /* Transaction 4 waits for Transaction 1 */
]

5. Transaction Weight

5.1 Initialize Weight

InnoDB assigns an initial weight to each waiting transaction. If a transaction has previously waited 2 N times while only N transactions are currently waiting, its weight is boosted to min(N, 1e9/N) . In the example, all weights remain 1.

[0:1, 1:1, 2:1, 3:1]  /* weight array */

5.2 Boost Weight

Transactions that block other waiting transactions receive additional weight equal to the sum of the blocked transactions' weights, except when the blocked transactions are part of a deadlock cycle.

[0:3, 1:1, 2:1, 3:1]  /* after boosting weight of Transaction 1 */

5.3 Update Weight

The final weights are written back to the transaction objects, excluding those that are currently in a deadlock, because their final weight will be recomputed after the deadlock is resolved.

6. Summary

Before each deadlock check, InnoDB performs the following steps:

Construct a lock‑wait snapshot and sort it by transaction address.

Build a lock‑wait graph from the sorted snapshot array.

Derive a weight array from the graph.

Boost the weight of blocking transactions.

Update the transaction objects with the new weights.