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

作者:操盛春,爱可生技术专家,公众号『一树一溪』作者,专注于研究 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. 总结

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

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

操盛春

爱可生技术专家,公众号『一树一溪』作者,专注于研究 MySQL 和 OceanBase 源码。