MySQL 死锁产生原因

所谓死锁（Deadlock），是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象。若无外力作用，它们都将无法推进下去，此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

相较于行级锁，表级锁产生死锁的场景较少，因此解决死锁问题主要还是针对最常用的 InnoDB 存储引擎。死锁的关键在于：两个（或以上）的 Session 加锁的顺序不一致。对应的解决死锁问题的关键就是：让不同的 Session 加锁有次序。

相关参考资料：

死锁的概念

死锁是指两个或两个以上的事务在执行过程中，因争夺资源而造成的一种互相等待的现象。若无外力作用，事务都将无法推进下去。

解决死锁的最简单方法是不要有等待，将任何的等待转换为回滚，并且事务重新开始。但在线上环境，这可能会导致并发性能下降，甚至任何一个事务都不能进行，而这所带来的问题远比死锁的问题更严重。

超时机制

解决死锁问题最简单的一种方法是超时。当两个事务互相等待时，当一个等待时间超过设置的某一阈值时，其中一个事务回滚，另一个等待的事务就能继续运行了。在 InnoDB 存储引擎中，参数 innodb_lock_wait_timeout 用来设置超时时间。

超时机制虽然简单，但是其仅通过超时后对事务进行回滚的方式处理，或者说其是根据 FIFO（First Input First Output）的顺序选择回滚对象。但若超时的事务所占权重比较大，如事务操作更新了很多行，占用了较多的 undo log，这是采用 FIFO 方式就显得不合适了，因为回滚这个事务的时间相对另一个事务所占用的时间可能会更多。

等待图（Wait-For Graph）

除了超时机制，当前的数据库还采用 wait-for graph（等待图）的方式来进行死锁检测。较之超时的解决方案，这是一种更为主动的死锁检测方式，InnoDB 存储引擎也是采用这种方式。

wait-for graph 要求数据库保存以下两种信息：

  • 锁的信息链表
  • 事务等待链表

通过上述链表可以构造出一张图。而这个在图中若存在回路，就代表存在死锁，因此资源间相互发生等待。在 wait-for graph 中，事务为图中的节点，而在图中，事务 T1 指向 T2 边的定义为：

  • 事务 T1 等待事务 T2 所占用的资源
  • 事务 T1 最终等待 T2 所占用的资源，也就是事务之间在等待相同的资源，而事务 T1 发生在事务 T2 的后面

看一个例子，当前事务和锁的状态如图：

在 Transaction Wait Lists 中可以看到共有 4 个事务 t1、t2、t3、t4，故在 wait-for graph 中应有 4 个节点。而事务 t2 对 row1 占用 X 锁，事务 t1 对 row2 占用 S 锁。事务 t1 需要等待 t2 中 row1 的资源，因此在 wait-for graph 中有条从节点 t1 指向节点 t2。事务 t2 需要等待事务 t1、t4 锁占用 row2 对象，故此存在节点 t2 到节点 t1、t4 的边。同样，存在节点 t3 到节点 t1、t2、t4 的边，因此最终 wait-for graph 为：

如图，可以发现回路 (t1, t2)，因此存在死锁。通过上述介绍，可以发现 wait-for graph 是一种较为主动的死锁检测机制，在每个事务请求锁并发生等待时都会判断是否存在回路，若存在则有死锁。通常来说，InnoDB 存储引擎会选择回滚 undo 量最小的事务。

wait-for graph 的死锁检测通常采用深度优先的算法实现。在 InnoDB 1.2 版本之前，都是采用递归方式实现，而 1.2 版本开始，对 wait-for graph 死锁检测进行了优化，将递归用非递归的方式实现，从而提高了 InnoDB 存储引擎的性能。

死锁概率

死锁应该非常少发生，若经常发生，则系统是不可用的。此外，死锁的次数应该还要少于等待，因为至少需要 2 次等待才会产生一次死锁。从数学角度来分析，死锁发生的概率问题如下：

当前数据库中有 n+1 个线程执行，即当前总共有 n+1 事务，假设每个事务所做的操作相同。若每个事务由 r+1 个操作组成，每个操作从 R 行数据中随机操作一行数据，并占用对象的锁，每个事务在执行完最后一个步骤释放锁占用的所有锁资源。最后，假设 nr << R，即线程操作的数据只占所有数据的一小部分。

在上述模型下，事务获得一个锁需要等待的概率是多少？当事务获得一个锁，其他任何一个事务获得锁的情况为：

(1+2+3...+r)/(r+1) ≈ r/2

由于每个操作为从 R 行数据中取一条数据，每行数据被取到的概率为 1/R，因此，事务中每个操作需要等待的概率 PW 为：

PW = Nr / 2R

事务由 r 个操作锁组成，因此事务发生等待的概率 PW(T) 为：

PW(T) = 1 - (1 - PW)^r ≈ r * PW ≈ nr^2 / 2R

死锁是由于产生回路，也就是事务互相等待发生的。如果死锁的长度为 2，即两个等待的节点间发生死锁，那么其概率为：

一个事务发生死锁的概率 ≈ PW(T)^2 / n ≈ nr^4 / 4R^2

由于大部分死锁的长度为 2，因此上述的公式基本代表了一个事务发生死锁的概率。从整个系统来看，任何一个事务发生死锁的概率为：

系统中任何一个事务发生死锁的概率 ≈ n^2 * r^4 / 4R^2

上述公式可以发现，由于 nr << R，因此，发生死锁的概率是非常低的。同时，事务发生死锁的概率与以下几点因素有关：

  • 事务中事务的数量 n，数量越多发生死锁的概率越大
  • 每个事务操作的数量 r，每个事务操作的数量越大，发生死锁的概率越大
  • 操作数据的集合 R，越小发生死锁的概率越大

死锁示例

如果程序是串行的，不可能发生死锁，死锁只存在于并发的情况。而数据库本身就是一个并发运行的程序，因此可能发生死锁。下面演示了死锁的一种经典情况，即 A 等待 B，B 等待 A，这种死锁被称为 AB-BA 死锁。

在上述操作中，会话 B 中的事务会抛出 1213 的错误，即表示发生死锁，死锁的原因是会话 A 和会话 B 的资源在互相等待。大多数死锁 InnoDB 存储引擎本身可以侦测到，不需要人为干预。但是在上述例子中，在会话 B 中的事务抛出死锁异常后，会话 A 中马上得到了记录为 2 的这个资源。这其实是因为会话 B 中的事务发生了回滚，否则会话 A 中的事务是不可能得到该资源的。InnoDB 存储引擎是不会回滚大部分的错误异常，但是死锁除外。发生死锁后，InnoDB 存储引擎会马上回滚一个事务，这点需要注意。因此如果在应用程序中捕获 1213 这个错误，其实并不需要对其进行回滚。

外键索引导致的死锁

Oracle 数据库中产生死锁的常见原因是没有对外键添加索引，而 InnoDB 存储引擎会自动对其进行添加，因而能够很好的避免这种情况发生。而人为删除外键上的索引，就会抛出异常。

create table p(
    a int,
    primary key(a)
) engine=innodb;

create table c(
    b int,
    foreign key(b) references p(a)
) engine=innodb;

show index from c;

此时我们尝试删除索引：

drop index b on c;
-- Error Code: 1553. Cannot drop index 'b': needed in a foreign key constraint

可以看到，虽然在建立子表时指定了外键，但是 InnoDB 存储引擎会自动在外键列上建立一个索引 b，并且人为的删除这个列是不允许的。

间隙锁导致的死锁

此外还存在另一种死锁，即当前事务持有了待插入记录的下一个记录的 X 锁，但是在等待队列中存在一个 S 锁的请求，则可能发生死锁。来看一个例子：

DROP TABLE t;

CREATE TABLE t(
    a INT PRIMARY KEY
) ENGINE=INNODB;

INSERT INTO t VALUES(1),(2),(4),(5);

表 t 仅有一列 a 并插入了 4 条记录，运行如下查询：

可以看到，会话 A 已经对记录 4 持有 X 锁，但是在会话 A 中插入记录 3 时会导致死锁发生。这个问题的产生是由于会话 B 中请求记录 4 的 S 锁而发生等待，但之前请求的锁对于主键记录 1、2 都已经成功。若在事件点 5 能插入记录，那么会话 B 在获得记录 4 持有的 S 锁后，还需要向后获得记录 3 的记录，这样显然不合理。因此 InnoDB 存储引擎在这里主动选择死锁，而回滚的是 undo log 记录大的事务，这与 AB-BA 的死锁处理方式又不同。

说明

  • 文中提到的 InnoDB 1.2 版本优化主要对应 MySQL 5.6 时期，当前主流版本（MySQL 5.7/8.0）在死锁检测与锁算法上已有进一步演进。
  • 数学概率模型为理论估算，实际生产环境中死锁概率受业务逻辑、索引设计及事务隔离级别等多重因素影响。