细说 MySQL 死锁

死锁检查线程，检查并解决死锁，分为三步走，这期先聊聊准备工作：构造锁等待图、初始化事务权重。

本文基于 MySQL 8.0.32 源码，存储引擎为 InnoDB。

1. 模拟死锁

创建测试表：

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);

创建 4 个连接，按以下顺序执行示例 SQL：

-- 连接 1（事务 1）
BEGIN;
SELECT id FROM t1 WHERE id = 10 FOR UPDATE;
-- 连接 2（事务 2）
BEGIN;
SELECT id FROM t1 WHERE id = 20 FOR UPDATE;
-- 连接 3（事务 3）
BEGIN;
SELECT i1 FROM t1 WHERE id = 10 FOR UPDATE;
-- 连接 4（事务 4）
BEGIN;
SELECT id, i1 FROM t1 WHERE id = 10 FOR UPDATE;
-- 连接 1（事务 1）
SELECT i1 FROM t1 WHERE id = 20 FOR UPDATE;
-- 连接 2（事务 2）
SELECT * FROM t1 WHERE id = 10 FOR UPDATE;

每个连接启动一个事务，分别为事务 1 ~ 4。按照各事务进入锁等待状态的顺序，等待关系如下：

• 事务 3 等待事务 1 释放 <id = 10> 的行锁。
• 事务 4 等待事务 1 释放 <id = 10> 的行锁。
• 事务 1 等待事务 2 释放 <id = 20> 的行锁。
• 事务 2 等待事务 1 释放 <id = 10> 的行锁。

2. 死锁检查线程

InnoDB 有个名为 ib_srv_lock_to 的后台线程，每秒进行一次超时检查，看看是否有锁等待超时的事务。

这个线程是个多面手，除了检查并处理锁等待超时，还会检查并解决死锁。

前面介绍锁等待超时，我们把这个线程称为超时检查线程，这里我们又把它称为死锁检查线程，大家知道这是同一个线程就好了。

死锁检查线程会监听一个锁等待事件，这个事件的超时时间为 1 秒。

每次开始监听之后的 1 秒内：

• 如果没有事务从运行状态进入锁等待状态，监听结束，进行一轮死锁检查。
• 如果某个事务加锁发生等待，会发送通知，死锁检查线程收到通知之后，立即结束监听，进行一轮死锁检查。

每一轮死锁检查，如果发现了死锁，则解决死锁。检查并解决死锁之后，继续监听锁等待事件。死锁检查线程就这么不断重复着等待、检查死锁、解决死锁的循环。

3. 锁等待快照

事务加锁发生等待，给死锁检查线程发送通知之前，都会在锁模块的 waiting_threads 属性指向的内存区域中找到一个空闲的 slot，把加锁信息保存到这个 slot 中。

> 每个 slot 存放的都是 srv_slot_t 对象，加锁信息实际上是保存到 srv_slot_t 对象中。

死锁检查线程，要做的第一件事，就是把此刻处于锁等待状态的那些事务记下来，也就是构造锁等待快照，这需要遍历 waiting_threads 属性指向的内存区域。

遍历过程从 waiting_threads 属性指向的内存区域中第一个 slot 开始，到 last_slot 属性指向的 slot 前面的 slot（已被使用的最后一个 slot）为止。

每次取一个 slot，如果这个 slot 已被某个锁等待事务使用，就构造一个 waiting_trx_info_t 对象，追加到快照数组里。

> 为了方便介绍，我们把 waiting_trx_info_t 对象称为快照对象。

快照对象有 4 个属性：锁等待事务、阻塞事务、srv_slot_t 对象、版本号（MySQL 本次启动以来发生的锁等待次数，包含这次锁等待在内）。

以示例 SQL 中第 1 个发生锁等待的事务 3 为例，它对应的快照对象如下：

{
  事务 3,        /* 锁等待事务 */
  事务 1,        /* 阻塞事务 */
  srv_slot_t 0, /* 第 1 个 slot 里面
                 * 保存的 srv_slot_t 对象 */
  4             /* 版本号 */ 
}

示例 SQL 中，4 个事务都发生了锁等待，构造出来的快照数组里有 4 个快照对象：

/* 快照数组 */
/* 0 */ { 事务 3, 事务 1, srv_slot_t 0, 4 }
/* 1 */ { 事务 4, 事务 1, srv_slot_t 1, 5 }
/* 2 */ { 事务 1, 事务 2, srv_slot_t 2, 6 }
/* 3 */ { 事务 2, 事务 1, srv_slot_t 3, 7 }

4. 锁等待图

有了快照数组，就有了构造锁等待图的基础。

不过，这个快照数组还不能直接使用，需要进一步处理，就是按照事务对象的内存地址从小到大进行排序。

以示例 SQL 的快照数组为例，排序之后，就变成下面这样了：

/* 排序之后的快照数组 */
/* 0 */ { 事务 1, 事务 2, srv_slot_t 2, 6 }
/* 1 */ { 事务 2, 事务 1, srv_slot_t 3, 7 }
/* 2 */ { 事务 3, 事务 1, srv_slot_t 0, 4 }
/* 3 */ { 事务 4, 事务 1, srv_slot_t 1, 5 }

接下来就可以基于排序之后的快照数组构造锁等待图了。

> 为了方便介绍，后面提到的快照数组，都是排序之后的快照数组。

锁等待图，表示快照数组中各个快照对象的锁等待事务之间的等待关系。

有一点需要说明，存放等待关系使用的数据结构并不是图，而是数组，我们称之为锁等待数组。

构造锁等待图，需要遍历快照数组。 遍历过程中，每次取一个快照对象（X），找到以其中的阻塞事务作为锁等待事务的快照对象（Y）。

然后，构造两个快照对象的锁等待事务之间的等待关系：

• 用快照对象 X 在快照数组中的下标，作为锁等待数组的下标，找到锁等待数组中对应的数组单元。
• 用快照对象 Y 在快照数组中的下标，作为上一步的数组单元值。

为了更好理解，我们以遍历示例 SQL 的快照数组为例，第 1 轮循环取第 1 个快照对象。

第 1 步，第 1 个快照对象（X）中的阻塞事务为事务 2，找到以它作为锁等待事务的第 2 个快照对象（Y）。

第 2 步，第 1 个快照对象在快照数组中的下标 0，作为锁等待数组的下标，找到对应的数组单元。

第 3 步，第 2 个快照对象在快照数组中的下标 1，作为上一步的数组单元值。

经过以上步骤，锁等待数组中第 1 个单元（下标为 0）的值就变成了 1，表示事务 1 等待事务 2。

遍历快照数组结束之后，就得到了锁等待数组，还是以示例 SQL 为例，得到以下锁等待数组：

/* 锁等待数组 */
[
  0: 1, /* 事务 1 等待事务 2 */
  1: 0, /* 事务 2 等待事务 1 */
  2: 0, /* 事务 3 等待事务 1 */
  3: 0  /* 事务 4 等待事务 1 */
]

5. 事务权重

5.1 初始化权重

构造锁等待图之后，接下来会给快照数组中所有事务（也就是处于等待状态的事务）初始化权重。

如果多个事务等待获得同一条记录的行锁，或者同一个表的表锁，事务优化级相同的情况下，权重最高的事务会获得锁。

初始化事务权重，也需要遍历快照数组，遍历过程中，每次取一个快照对象。

对于每个快照对象，如果其中的锁等待事务满足某个条件，InnoDB 会把该事务的权重设置为一个比较大的值，否则该事务的权重设置为 1。

描述清楚需要满足的这个条件，得费点功夫，我们慢慢来。

假设快照数组中的锁等待事务数量为 N，也就是 InnoDB 中当前有 N 个事务在等待获得锁。

如果某个快照对象中的锁等待事务（X）进入锁等待状态之后，又有 2N 个事务进入过锁等待状态，那就需要提升事务 X 的权重。

为啥呢？

因为事务 X 进入锁等待状态之后，又有 2N 个事务进入过锁等待状态，而当前只有 N 个事务正处于锁等待状态，说明这 2N 个锁等待事务中，已经有 N 个事务获得了锁，而在它们前面的事务 X 竟然还没有获得锁，这是不是有点不公平？

确实不公平，事务 X 都要饿死了。

为了不让事务 X 饿死，InnoDB 会把它的权重设置为比较大的值，也就是提升它的权重，以提升它获得锁的优先程度。

那么，权重提升到多少呢？

这有一个计算公式：

min(N, 1e9 / N)

用大白话解释上面的公式，就是取以下两个值中小的那个：

• 事务等待数量（N）。
• 1e9 / N（10 的 9 次方，除以事务等待数量）。

我们还是以示例 SQL 为例，初始化之后，各快照对象中的锁等待事务权重如下：

/* 权重数组 */
[
  0: 1, /* 事务 1 */
  1: 1, /* 事务 2 */
  2: 1, /* 事务 3 */
  3: 1  /* 事务 4 */
]

> 示例 SQL 的权重数组中，所有快照对象的锁等待事务权重都为 1，说明没有事务快要被饿死了。

5.2 提升权重

初始化快照数组中所有锁等待事务的权重之后，InnoDB 还要继续给部分锁等待事务提升权重。

哪些事务会再次被提升权重？

如果某些锁等待事务，阻塞了其它事务获得锁，也就是说，它们既是某个快照对象中的锁等待事务，又是其它一个或多个快照对象中的阻塞事务，它们就会再次被提升权重。

这里会怎么提升权重呢？

也很简单，就是把锁等待事务的权重累加到阻塞事务的权重上。

我们以示例 SQL 快照数组中的事务 1 为例，提升权重的过程，就是把被事务 1 阻塞的其它事务的权重，累加到事务 1 的权重上。

为了方便理解，我们把示例 SQL 的锁等待数组、权重数组放到这里：

/* 锁等待数组  */
[
  0: 1, /* 事务 1 等待事务 2 */
  1: 0, /* 事务 2 等待事务 1 */
  2: 0, /* 事务 3 等待事务 1 */
  3: 0  /* 事务 4 等待事务 1 */
]
/* 权重数组 */
[
  0: 1, /* 事务 1 */
  1: 1, /* 事务 2 */
  2: 1, /* 事务 3 */
  3: 1  /* 事务 4 */
]

通过锁等待数组可以看到，事务 1 阻塞了 3 个事务，分别为事务 2、3、4。

按照前面的介绍，事务 2、3、4 的权重都会累加到事务 1 的权重上。然而，这里只有事务 3、4 的权重会累加到事务 1 的权重上。

为啥呢？

因为事务 2 有点特殊，它和事务 1 相互等待，发生了死锁。

同样，虽然事务 2 阻塞了事务 1，但是事务 1 权重也不会累加到事务 2 的权重上。

发生死锁的那些事务，相互等待，它们之间的等待关系形成了一个环，想要把环中锁等待事务的权重累加到阻塞事务的权重上，不知道从哪里开始，到哪里结束。

所以，这里提升权重时，死锁环中锁等待事务的权重不会累加到阻塞事务的权重上。

等到解决死锁之后，还会再更新一次死锁环中各事务的权重。

通过以上权重数组可以看到，事务 1 ~ 4 的权重都为 1，事务 3、4 的权重累加到事务 1 的权重上，事务 1 的权重提升为 3 了。

这个步骤中，给阻塞事务提升完权重之后，示例 SQL 的权重数组变成下面这样了：

/* 权重数组 */
[
  0: 3, /* 事务 1 */
  1: 1, /* 事务 2 */
  2: 1, /* 事务 3 */
  3: 1  /* 事务 4 */
]

5.3 更新权重

经过初始化权重、提升权重两个步骤得到的各事务权重，都还保存在权重数组里，这些权重需要更新到各锁等待事务的事务对象中。

更新锁等待事务的权重时，会排除发生死锁的事务，因为这些事务的权重还没有最终计算完成。

6. 总结

死锁检查线程，每次检查是否发生死锁之前，都需要做一些准备工作：

• 构造锁等待快照，并按照快照对象中的锁等待事务对象的内存地址从小到大进行排序。
• 基于排序之后的快照数组，构造锁等待图。
• 基于锁等待图得到权重数组。
• 根据锁等待关系，进一步提升阻塞事务的权重。
• 把事务权重更新到各事务对象中。