面试题：MySQL InnoDB存储引擎中死锁检测机制的基本原理是什么

Question

请阐述MySQL InnoDB存储引擎死锁检测机制的基本工作原理，包括死锁是如何被检测到的，以及检测过程中涉及的关键数据结构或算法。

Answer 1

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

1. 死锁检测时机：InnoDB 存储引擎并不是每次锁请求时都进行死锁检测，这样会带来较大开销。通常在发生锁等待一定时间后，才会触发死锁检测。
2. 检测方式：采用等待图（Wait - for - Graph，WFG）算法。InnoDB 会维护一个等待图数据结构，该图中节点表示事务，边表示事务之间的等待关系。例如，如果事务 T1 等待事务 T2 持有的锁，那么图中就存在一条从 T1 到 T2 的边。

死锁如何被检测到

1. 当一个事务请求锁时，如果不能立即获取锁，InnoDB 会在等待图中添加一个节点代表该事务，并尝试在已有节点和新节点间建立边来表示等待关系。
2. 每次在修改等待图（如添加新等待关系边）后，InnoDB 会检查等待图是否存在环。如果存在环，就意味着发生了死锁。例如，事务 T1 等待 T2 持有的锁，T2 等待 T3 持有的锁，而 T3 又等待 T1 持有的锁，这样就形成了一个环，即发生了死锁。

关键数据结构或算法

1. 等待图（Wait - for - Graph）：这是死锁检测的核心数据结构，用于记录事务间的等待关系。通过维护节点（事务）和边（等待关系），为死锁检测提供基础数据。
2. 深度优先搜索（DFS）或广度优先搜索（BFS）算法：在检测等待图中是否存在环时，通常会使用深度优先搜索或广度优先搜索算法。以深度优先搜索为例，从等待图的某个节点开始，沿着边进行深度探索，如果在探索过程中再次访问到已经访问过的节点，就说明存在环，即发生了死锁。