死锁检查线程，检查并解决死锁，分为三步走，这期先聊聊准备工作：构造锁等待图、初始化事务权重。
作者：操盛春，爱可生技术专家，公众号『一树一溪』作者，专注于研究 MySQL 和 OceanBase 源码。
爱可生开源社区出品，原创内容未经授权不得随意使用，转载请联系小编并注明来源。
本文基于 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 释放 的行锁。
- 事务 4 等待事务 1 释放 的行锁。
- 事务 1 等待事务 2 释放 的行锁。
- 事务 2 等待事务 1 释放 的行锁。
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. 总结
死锁检查线程，每次检查是否发生死锁之前，都需要做一些准备工作：
- 构造锁等待快照，并按照快照对象中的锁等待事务对象的内存地址从小到大进行排序。
- 基于排序之后的快照数组，构造锁等待图。
- 基于锁等待图得到权重数组。
- 根据锁等待关系，进一步提升阻塞事务的权重。
- 把事务权重更新到各事务对象中。
