面试题：MySQL死锁检测机制的基本原理是什么

Question

请阐述MySQL数据库中死锁检测机制的基本工作原理，以及死锁检测在MySQL架构中的大致位置和触发时机。

Answer 1

死锁检测机制基本工作原理

1. 等待图构建：MySQL会在内存中维护一个等待图（Wait-For Graph，WFG），图中的节点表示事务，边表示事务之间的等待关系。当一个事务请求的资源正在被另一个事务持有，并且该事务需要等待资源释放时，就会在等待图中创建一条从等待事务到持有事务的边。
2. 环检测：死锁检测机制会周期性地（或在特定条件下）检查等待图是否存在环。如果存在环，就意味着出现了死锁。例如，事务A等待事务B持有的资源，事务B等待事务C持有的资源，而事务C又等待事务A持有的资源，这样就形成了一个环，表明发生了死锁。常见的环检测算法有深度优先搜索（DFS）和广度优先搜索（BFS），MySQL一般使用DFS算法来检测等待图中的环。
3. 死锁处理：一旦检测到死锁，MySQL会选择一个代价最小的事务（通常根据事务已执行的时间、已修改的行数等因素综合判断）作为牺牲者（victim），将其回滚，释放它持有的资源，从而打破死锁，让其他事务能够继续执行。

死锁检测在MySQL架构中的大致位置

死锁检测机制位于MySQL的存储引擎层。不同的存储引擎（如InnoDB、MyISAM等）对死锁检测的实现略有差异，以InnoDB为例，死锁检测相关的代码和逻辑存在于InnoDB存储引擎内部，与事务管理、锁管理等模块紧密关联。它依赖于锁管理模块提供的信息来构建等待图，同时事务管理模块也会参与到死锁发生后的事务回滚等处理过程。

死锁检测的触发时机

1. 周期性检测：InnoDB存储引擎默认会每隔一定时间（可以通过参数innodb_lock_wait_timeout间接影响检测频率）对等待图进行检查，以发现可能存在的死锁。这个时间间隔不是固定不变的，会根据系统负载等情况动态调整。
2. 锁请求时检测：当一个事务请求锁资源时，如果等待队列的长度超过了一定阈值（这个阈值可以通过参数innodb_deadlock_detect控制，从MySQL 5.7.5版本开始，默认值为ON，表示开启死锁检测），MySQL会立即进行死锁检测。这是为了及时发现由于新的锁请求加入等待队列而可能导致的死锁情况，避免死锁长时间未被发现而影响系统性能。