死锁检查线程，检查并解决死锁的第二步，看看它是怎么发现死锁的。
作者：操盛春，爱可生技术专家，公众号『一树一溪』作者，专注于研究 MySQL 和 OceanBase 源码。
爱可生开源社区出品，原创内容未经授权不得随意使用，转载请联系小编并注明来源。
本文基于 MySQL 8.0.32 源码，存储引擎为 InnoDB。
1. 一定会检查死锁吗？
上一期，我们介绍了死锁检查线程做的一些准备工作。按照故事发展套路，接下来就要顺理成章的进行死锁检查了。
但是，我们不禁还要问一句：一定会进行死锁检查吗？
答案是否定的。
死锁检查线程是否会检查并解决死锁，由系统变量 innodb_deadlock_detect 决定。如果它的值为 ON（默认值），就会检查并解决死锁，值为 OFF，就不需要检查、更不用解决死锁。
如果不需要检查并解决死锁，死锁检查线程做的那些准备工作不就白费了吗？
不白费。
没有了死锁检查，死锁环中最先达到锁等待超时时间的事务，会结束锁等待。
一个事务结束锁等待之后，死锁环中其它事务、死锁环之外的事务，就有机会获得锁。
这些嗷嗷待哺的事务中，谁能获得锁呢？
死锁检查线程的准备工作之一，是给快照数组中各锁等待事务初始化权重，给阻塞事务提升权重，也就是重新计算了各锁等待事务的权重。
重新计算的权重，会影响到这些嗷嗷待哺的事务获得锁的优先程度。
所以，即使不需要检查并解决死锁，死锁检查线程的准备工作也会不白费。
2. 找到死锁环
死锁检查线程在准备工作阶段，得到了锁等待数组，现在可以基于这个数组，去发现死锁了。
发生死锁时，两个或多个事务之间的等待关系形成了一个环，我们称之为死锁环。
发现死锁的过程，就是基于锁等待数组找到死锁环的过程。这个过程会遍历锁等待数组。
遍历过程可能会进行多轮循环，从锁等待数组的第一个单元开始，每轮循环以一个单元为起点，根据数组单元描述的等待关系顺藤摸瓜，找到锁等待路径上的每一个单元。
也就是说，锁等待数组的每个单元，都作为一条锁等待路径的起点。每轮循环遍历一条锁等待路径，看看这条路径是不是形成了环。
如果遍历某条锁等待路径时，从锁等待数组的某个单元开始，又回到了这个单元，就说明存在死锁环，也就发现了死锁。
从上面的介绍可以看到，找到死锁环的过程并不复杂，但是似乎比较抽象。
为了把这个抽象的过程具象化，我们以示例 SQL 的锁等待数组为例，模拟找到死锁环的过程。
开始之前，我们把示例 SQL 和锁等待数组放到这里。
示例 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;
锁等待数组：
/* 锁等待数组 */
[
0: 1, /* 事务 1 等待事务 2 */
1: 0, /* 事务 2 等待事务 1 */
2: 0, /* 事务 3 等待事务 1 */
3: 0 /* 事务 4 等待事务 1 */
]
示例 SQL 的锁等待数组中，第一轮循环，从第一个数组单元开始，根据数组单元表示的锁等待关系，遍历这条锁等待路径上的所有数组单元。
第 1 步，第一个单元的下标（0）和值（1），表示事务 1 等待事务 2。
单元值（1）是事务 2 在锁等待数组中的下标。
第 2 步，找到锁等待数组中下标 1 对应的单元，这个单元的值为 0，表示事务 2 等待事务 1。
单元值（0）是事务 1 在锁等待数组中的下标。
第 3 步，第 1 轮循环从事务 1 等待事务 2 开始，这里又发现事务 2 在等待事务 1，说明这两个事务相互等待形成了一个环，也就是死锁环。
第一轮循环经过三个步骤已经发现了死锁环。
这是不是说明已经发现了死锁呢？
还不能最终确定。因为发现死锁环的过程，遍历的是锁等待数组，而这个数组是基于快照数组得到的。
从构造快照数组完成，到发现死锁环，已经过了一段时间。这段时间内，可能出于某种原因，死锁环中某个事务已经结束等待，死锁环有可能已经不存在了。
所以，接下来还要再确认一下，死锁环中每个事务是否依然处于锁等待状态，也就是需要进行二次确认。
3. 二次确认
二次确认过程分为两个步骤。为了更直观的理解这两个步骤的逻辑，我们把示例 SQL 的快照数组放到这里：
/* 快照数组 */
/* 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 }
步骤 1：确认死锁环中每个锁等待事务占用的 slot（里面保存着 srv_slot_t 对象）是否已经易主。
这个步骤会遍历死锁环中各事务对应的快照对象，判断每个快照对象是否满足以下两个条件：
- slot 依然处于已使用状态。
- slot 依然被这个快照对象的锁等待事务占用。
以示例 SQL 快照数组中第 1 个快照对象为例，判断该快照对象是否满足以下两个条件：
- srv_slot_t 0 依然处于已使用状态。
- srv_slot_t 0 依然被事务 3 占用。
只要死锁环中任何一个事务对应的快照对象不满足以上两个条件之一，说明刚刚发现的死锁环已经不存在了，也就不需要解决死锁了。
如果死锁环中所有事务对应的快照对象，都满足以上两个条件，进入步骤 2。
步骤 2：确认死锁环中每个锁等待事务，是否还处于锁等待状态。
只要死锁环中任何一个事务，已经不处于锁等待状态了，也说明刚刚发现的死锁环已经不存在了，同样不需要解决死锁。
如果死锁环中所有事务依然处于锁等待状态，就说明死锁环依然存在，也就确认发现了死锁。
4. 总结
死锁检查线程是否会检查并解决死锁，由系统变量 innodb_deadlock_detect 决定。
如果需要检查并解决死锁，死锁检查线程会以锁等待数组中每个数组单元作为一条锁等待路径的起点，根据每个数组单元描述的等待关系，看看这条路径是否形成了环。
如果发现某条锁等待路径开成了环，还需要二次确认，以确定这个环依然存在。
