InnoDB锁——第三部分“死锁”

作者：Kuba Łopuszański 译：徐轶韬

在本系列博客中，我将描述InnoDB如何锁住数据(表和行)，使得客户端认为它们的查询是按顺序执行，以及在最近的版本有哪些改进。

在InnoDB Data Locking - Part 1“Introduction中，我介绍了一些基本的概念。

• 数据库、表、行(如共享驱动器上的文件、文件中的电子表格和电子表格中的行)
• 事务的可序列化性(通过一个令人信服的故事来解释随着时间推移观察到的状态，关于并行操作的相对顺序)
• 超时(用于行为不当的锁所有者，并解决死锁)
• 读写锁(共享/独占访问权限)
• 互斥等待(持续地读取和写入互斥等待)
• 队列(FIFO，或优先级)
• 读视图(只读快照，允许旧读并发到新写)
• 锁的粒度(所有事务的访问权限vs.所需资源的访问权限)
• 由粒度引起的死锁，以及通过锁排序克服死锁的方法

在这篇文章中，我将描述死锁检测在InnoDB 8.0.18中的工作原理，并介绍以下概念:

• 等待图
• 死锁循环
• 死锁的受害者

一个关于死锁的例子：

在InnoDB Data Locking - Part 1“Introduction”中，我们看到了一个简单的例子，两个人无法完成他们进行中的事情，因为一个人需要等待另一个人释放正在使用的资源，反之亦然。ABe已经读取文件A并要求写入文件B,但必须等到BAsil先释放他对该文件的读访问权，然而BAsil不能这样做，直到他完成写入文件A，但是文件A正在由ABe使用。

他们为什么就不能礼貌一点互相谦让呢?

首先有必要回答一个挥之不去的问题。为什么他们不能在完成对第一个文件的读取之后，在请求对下一个文件的写访问之前，释放读访问权限? 例如，为什么不让ABe释放他对file A的读访问权限，这样BAsil就可以获得文件A的写访问权限，完成他的工作，释放所有持有的访问权限，之后ABe就可以在没有任何延迟的情况下继续工作了。这肯定会消除僵局，为什么不做这个看起来很聪明的事情呢? 简短的回答，这实际上等同于将一个事务分成两个较小的事务，这可能会产生意外的结果。请记住，为了实现承诺的可串行性，服务器必须编造一个关于所有事务顺序的故事。如果我们把ABe的事务分成两个独立的事务，那么服务器就可以按照如下顺序运行:

ABe.part1 << BAsil << ABe.part2

(或者，如果这是一个性能非常糟糕的服务器，它甚至可以假装ABe.part2发生在ABe.part1之前，但谢天谢地，InnoDB不会那么做)

这种分裂和重新排序在实践中意味着什么?假设ABe的计划是“将文件B中的余额设置为文件A中的苹果数量”:

ABe1. open file A for Read
ABe2. read number of Apples from file A #let's call this number $ApplesSeenByABe
ABe3. open file B for Write
ABe4. write $ApplesSeenByABe to file B as the Balance

BAsil 计划是“将A文件中苹果的数量与B文件中的余额相等”:

BAsil1. open file B for Read
BAsil2. read the Balance from file B #let's call this number $BalanceSeenByBAsil
BAsil3. open file A for Write
BAsil4. write $BalanceSeenByBAsil to file A as the number of Apples

显然，他们都希望两个文件包含相同的数量，无论两个计划(事务)的相对顺序如何，最终结果都应该是两个文件包含相同的数量，而不管初始条件是什么。

假设文件A最初有10个苹果，文件B的余额是0。

如果 ABe的事务发生在BAsil之前，那么ABe应该把余额改为10，BAsil的事务没有变化，最终状态是苹果=余额=10。

如果BAsil的事务发生在ABe之前，BAsil会看到余额=0，将苹果设为0，然后ABe会将0复制回B，导致最终状态苹果和余额都为0。

但是，如果我们允许服务器提前释放ABe持有的文件A的读访问权限，那么接下来的交错就会发生:

  ABe1. open file A for Read
  ABe2. read number of Apples from file A #$ApplesSeenByABe=10
BAsil1. open file B for Read
BAsil2. read the Balance from file B #$BalanceSeenByBAsil=0

 ABe2b. prematurely close file A  #<-- HERE !!!

BAsil3. open file A for Write
BAsil4. write $BalanceSeenByBAsil (which is 0) to file A as the number of Apples
  ABe3. open file B for Write
  ABe4. write $ApplesSeenByABe (which is 10) to file B as the Balance

最终的结果是在文件A的苹果=0和文件B的余额=10之间不匹配，他们都没有意识到这个问题，直到查看月度报告时才会发现！

这一最终结果与这两个事务可能发生的顺序不一致，但它与ABe的事务被一分为二的历史是一致的:

ABe的第一个事务:

ABe1. open file A for Read
ABe2. read number of Apples from file A #let's call this number $ApplesSeenByABe

ABe的第二个事务:

ABe3. open file B for Write
ABe4. write $ApplesSeenByABe to file B as the Balance

而服务器坚持它是按照顺序执行的:

ABe.first  << BAsil << ABe.second

(这就是为什么过早释放锁会被视为提交一个事务并开始一个新的事务的原因)

如何避免死锁？

如果过早地释放访问权限(锁)无法解决问题，那么还有什么其他选项可以避免死锁呢?

我们之前已经看到过一个——预先请求所有需要的访问权限。在许多情况下，实现它非常困难，而且仍然需要小心地按正确的顺序请求它们。以ABe和BAsil为例，修改后的计划保证不会出现死锁。

new-ABe1. open file A for Read
new-ABe2. open file B for Write
new-ABe3. read number of Apples from file A #let's call this number $ApplesSeenByABe
new-ABe4. write $ApplesSeenByABe to file B as the Balance

new-BAsil1. open file A for Write
new-BAsil2. open file B for Read
new-BAsil3. read the Balance from file B #let's call this number $BalanceSeenByBAsil
new-BAsil4. write $BalanceSeenByBAsil to file A as the number of Apples

我们如何证明不会发生死锁?引入等待图形的概念将会有所帮助。有向图是由点(“节点”)和连接其中一些点的箭头(“边”)组成的集合。重要的是节点之间的关系, 哪个节点连接，哪个节点不连接，而不是它们在图上的确切位置，所以你可以以任何方式布局相同的关系。

我们的等待关系将涉及等待资源(文件)的事务(人)，这些资源目前属于其他事务。因此有两种节点(事务和资源)和两种边。

(T –等待访问–> R 和 R –-被访问–> T)

例如，下面这张图显示了ABe，BAsil，文件A和文件B。在我们故事开始的时候，还没有人能访问任何资源。

ABe                         fileA

BAsil                       fileB

现在，让我们看看当我们按照以下顺序执行他们最初计划的步骤时，这幅图是如何演变的:

ABe1. 打开文件A 用于读取

ABe     <--is-accessed-by-- fileA

BAsil                       fileB

ABe2.从文件A读取苹果的数量(这不会请求任何新的访问权限，也不会授予它们，所以让我们继续)BAsil1.打开文件B读取

ABe     <--is-accessed-by-- fileA

BAsil   <--is-accessed-by-- fileB

BAsil2.从文件B(没有改变图)中读取余额。ABe3.打开文件B进行写操作(此操作将被阻塞，ABe必须等待)

ABe     <--is-accessed-by-- fileA
   \
    \--waits-for-access-to--\
                             \     
                              v
BAsil   <--is-accessed-by-- fileB

BAsil3.打开文件A进行写操作(该操作也将被阻塞，BAsil将不得不等待)

ABe     <--is-accessed-by-- fileA <-.
   \                                |
    \--waits-for-access-to--\       |
                             \      |
                              v     |
BAsil   <--is-accessed-by-- fileB   |
  \                                 |
   \-----waits-for-access-to--------/

现在，我们在现实世界中观察到的是，ABe和BAsil都处于等待状态，最终其中至少有一个将超时。 但是，这个现实问题如何在图上体现出来？作为一个循环：

ABe --> fileB --> BAsil --> fileA --> ABe ...

每当我们看到这样一个循环时，我们可以确定这是由于死锁而无法进行的一组事务，因此我们将其称为“死锁循环”。 这是为什么呢因为离开事务的唯一边是“waits-for-access”类型的并通向资源，而离开资源的唯一边是“is-accessed-by”类型的并通向事务，因此，循环必须在事务和资源之间交替，具有均匀的长度，涉及同等数量的事务和资源，每个事务阻塞等待它不能获得的资源，因为它拥有另一个事务，该事务也在等待。循环中的事务都不能进行，因此循环将持续到解决死锁为止。

那么，为什么在计划的修改版本（new-ABe1..new-ABe4和new-BAsil1..new-BAsil4）中不可能出现死锁？如果图如下：

ABe                         fileA

BAsil                       fileB

并尝试想象涉及ABe和BAsil的任何死锁循环，很快就会发现，对于ABe和BAsil而言，它至少必须具有一个输入边和一个输出边：

ABe <--...                  fileA
  \
   \_____..

BAsil <--...                fileB
  \
   \__...

否则，它们将不会处于循环状态。但是，拥有输入边意味着已经拥有一些资源，而拥有输出边意味着请求资源，因此我们可以将未完成的草图改进为：

ABe <--is-accessed-by-..             fileA
  \
   \--waits-for-access-to-..

BAsil <--is-accessed-by-..           fileB
  \
   \--waits-for-access-to-..

而且，如果我们查看它们的执行计划，我们可以轻松地确定这些边必须来自何处以及它们去往哪里，因为我们知道它们中的每一个都首先获得了对文件A的访问权限 （步骤new-ABe1和new-BAsil1）。请求访问文件B（步骤new-ABe2和new-BAsil2）。这意味着完成此图的唯一方法是：

 _____________________________________
/                                     \
| ABe <--is-accessed-by-------------- fileA
|  \
\   \--waits-for-access-to------------\
 \________________________             |
                          \            v
 BAsil <--is-accessed-by--/           fileB
   \                                   ^
    \--waits-for-access-to-------------/

但这不是死锁循环，请注意箭头的方向，它们不会形成循环！ 另外，此图还违反了以下假设：对文件A的写访问应具有排他性，因为我们可以看到文件A中有两个箭头，与我们的假设相矛盾。 该图可以解释为从文件A到文件B的两条路径。 通常，如果每个人都遵循规则以相同的顺序获取资源，那么图片将始终看起来像所有路径都遵循该顺序。这就是为什么循环不可能发生的原因。循环必须以某种方式从较晚的资源返回到较早的资源，但所有的边都是向前的。

死锁检测

我们如何自动找到死锁？有很多算法，但是必须考虑到这个图可能很大（许多并发事务，许多拥有的资源）并且随着新的边和节点的出现和消失而不断变化。

通过观察，删除边或节点不会引入死锁循环，可以简化处理这些动态更改的过程。只有添加新的边后，才能形成新的循环，而且新的边必须是关闭循环的缺失环节。这表明仅在添加新的边时才执行搜索死锁循环的方法，这种情况主要发生在事务T请求对资源R的访问权并且必须等待时，并且需要确定是否已经有一条从R到T的道路？

（另一个可能出现新的边的情况是在授予另一个事务已经等待对它的写访问权限之前，授予一个事务对资源的读访问权限，在此我们忽略这一点，假设防止互斥等待的算法可以避免这种情况，更复杂的情况是当一个事务请求一个LOCK_GAP并且已经有一个事务在等待LOCK_INSERT_INTENTION这个间隙时，InnoDB允许“读取”绕过“插入”，这意味着一个新的边导致了我们添加了节点，这也要求我们检查相反方向的死锁。修复这方面的错误是重新实现死锁检测算法的动机之一。

如果存在这样的路径，添加边将导致死锁，否则这个请求不会引起死锁，因此我们可以继续。

一旦确定了死锁循环，我们就需要以某种方式“解决它”。如前所述，我们不能仅删除边（过早释放单个访问权限）。我们必须删除整个节点（回滚事务之一）。我们选择循环中的一个节点作为“死锁受害者”，牺牲它以使其他节点继续前进。选择正确的死锁受害者有多种策略。（InnoDB避免杀死组复制所使用的高优先级事务，并倾向于牺牲定义的“较轻”事务INFORMATION_SECHEMA.INNODB_TRX.TRX_WEIGHT）

如果事情是如此简单，按照我所说的故事，您可能会感到每个节点最多只有一个输出边。虽然看起来事务可以明确声明其当前正在等待的单个资源似乎是正确的，但通常并非每次只能通过一个事务访问每个资源。换句话说，可能从一个资源到多个事务有多个“–is-accessed-by–>”边。原因包括：

• 可能有多个事务具有对同时授予的资源的共享（读取）访问权限
• 为了避免已经等待资源的事务陷入互斥等待，新来者必须等到现有的等待者完成等待为止，从某种意义上说，这就像旧的等待者正在“阻塞”他们正在“等待”的资源。值得庆幸的是，这只会向图中添加循环，可以忽略
• （实际上，在InnoDB中，事务通常要求同时访问一行和该间隙之前的间隙，如果您更喜欢将其建模为具有从一个事务到两个单独资源的两个传出边，或者您更喜欢将其建模为具有其他复杂访问权限的单个资源[gap + row]，这仅仅是角度问题。 [ ReadRow，ReadGap，ReadGapAndRow，WriteRow，WriteGap，WriteGapAndRow，WriteRowAndReadGap …]，有了重要的“兼容性”规则，可以允许多个事务共享资源，从而有多个从资源发出的边。到目前为止，InnoDB灵活地使用了后一种方法，即“锁拆分”技术，以获得前一种方法的好处。）

基本上，人们必须对图形使用某种搜索（BFS，DFS等），以查看在将新边从T添加到R之后，是否现在有一条路径可以返回到我们开始的地方。这是MySQL 8.0.17及之前版本中使用的旧的实现方法。

为了更详细地描述它是如何工作的，我们必须回顾一下上一篇文章，Lock System将请求的访问权限表示为内存中的对象，称为“锁”。在8.0.17中，“等待图”并没有显式地存储在内存中，但是可以从每个资源的锁对象列表和每个事务存储的指向当前等待授予的锁的单个指针中动态地推断出来事务当前正在等待的锁，您可以检查与同一资源相关的所有锁的列表，并检查其中哪些与您的锁冲突以及谁拥有它们，这样您就可以推断出您的事务正在等待哪个事务。虽然概念简单，但8.0.17中关于“等待图”的DFS需要相当复杂的低级代码，该代码遍历锁列表，并在此过程中锁定整个锁系统。为了避免因同一队列中的多个事务多次检查同一个锁而造成N^2的损失，使用了锁的DFS——标记已访问的锁，而不是标记已访问的事务或资源。考虑到锁是“访问请求”，它们更像是“等待图”的边而不是节点，这意味着DFS相当难理解。为了避免堆栈溢出，这两者都是通过手动堆栈管理简化为一个循环，并对所采取的步骤数量有各种硬限制。它不是代码中最漂亮的部分，而是关键路径上的瓶颈。我不希望这个视频能帮助你理解它是如何工作的，但让我们试一试:

在这个视频中，事务(T1,T2，..)被描述为三角形，锁是圆形:绿色代表(G)ranted，红色代表(W)aiting。如果事务正在等待一个锁，那么它将指向它正在等待的锁。算法扫描锁的相关资源列表，T1正在等待[row1]和每个与T1正在等待的锁冲突的锁,它检查如果锁拥有者(T2)也在等待在这种情况下,它将下行“递归”。一旦以这种方式检查了正在等待的锁之前的所有锁，它将回溯。如果找到返回T1的路径，则报告死锁循环。

现在，让我为您简要介绍8.0.18中引入的更改。

新的死锁检测算法

旧算法存在一个问题，要安全正确地运行它，必须在遍历图的整个过程中“stop the world”，并且这个图可能巨大，因为它既包含事务又包含它们所拥有的资源。

第一个观察结果，您可以处理一个较小的图，该图仅由事务组成，但不明确表示资源：从事务A到事务B的边表示事务A “等待事务B访问资源” 。 简单而言：A–waits-for–>B。用更多的数学术语来说：存在一个资源R，使得 A–waits-for-access-to–>R–is-accessed-by–>B。大图中的循环必须对应于较小图中的循环，反之亦然。 因此，我们可以想象死锁检测算法可以在这个较小的图上工作，而产生相同的结果。但这提出了一个问题，即如何创建和维护这样的等待图而不浪费太多资源。 请注意，即使节点集缩小了，我们仍然可能有很多边（如果R引出了很多边，它们将被A “继承” ）。 而且，如果我们每次仍然必须“stop the world”来重新创建这样的图，它可能会失败。

第二个观察结果并不那么琐碎，我们可以通过为每个事务选择最旧的输出边来创建“稀疏图”，并使用它代替原始的“密集图”来检测死锁。

让我先给你一些关于为什么会这样的直觉: 在“密集图”中形成一个循环的边不能从“密集图”中消失，正是因为它们的节点是死锁的。而属于未阻塞事务的边最终会从“密集图”中消失，因此在有限的时间内“稀疏图”将不得不选择形成死锁循环的边。

死锁检测可以限制为“稀疏图”的证明

现在，为了使证明更加正式，我们将假定：

• 系统中的事务数是有界限的（受Tnum限制），
• 单个事务访问的资源数量是有界限的（受Rnum限制），
• 以防止互斥等待的方式授予资源（在轮到其他事务之前最多可以授予Tnum的资源事务T等待），
• 事务不会等待资源以外的其他任何东西（特别是它们在有限的时间内完成或请求下一个资源），

证明将是自相矛盾的，因此我们假设在某个时间点上，“密集图”内出现了一个死锁循环，从而永远不会被注意到，没有节点被选为死锁受害者。（如果有多个，则选择其中任何一个，例如说形成最早的一个，涉及的事务ID的顺序首先是词典编排，或者是其他确定性的方式）。 让我们将循环的边和节点涂成红色。 让我们看一下稀疏图，它必须至少缺少一个红色边，否则算法将不得不选择至少一个红色节点作为受害者来解决红色死锁循环，这将与假设红色节点永远不会被注意。 稀疏图很可能已经包含了一些红色边，请注意，一旦红色边出现在稀疏图中，它将永远存在其中，因为红色边消失的唯一方法是当其端点事务之一完成时，我们认为永远不会发生。因此，稀疏图中的红色边只会随着时间的增长而增长，并且随着它的边界（受Tnum限制）到来，它最终必须停止增长。 让我们快进这一刻。 让我们将密集图中所有尚未为红色的节点和边都涂成蓝色，以便此时此刻每个节点和边为红色或蓝色，并且将来添加的边和节点将为黑色。 现在，有一些来自定序理论的数学技巧。我们将在每个节点中放置一对存储自然数的计数器，并按照一些规则对其进行更新。第一个计数器限制了该事务尚未获取多少资源，第二个计数器限制了有多少其他事务可以在互斥等待之前等待资源而绕过它。 最初，我们将所有计数器设置为<Rnum,Tnum>，并且每次出现一个新的(黑色)节点时，我们将<Rnum,Tnum>放入其中。每次新的边稀疏图出现，它可能因为事务请求新的资源(我们减少第一个计数器，第二个计数器重置回Tnum)或因为资源等待授予另一个事务(我们第二计数器递减)。我们不知道发生了什么，可以选择最坏的情况。但是我们知道，由于starvation freedom，第二个计数器不能降到零以下（因为在轮到我们之前，最多只有Tnum事务），并且由于每个事务都请求有限数量的资源，所以第一个计数器也不能降到零以下。 因此，现在让我们看一看在稀疏图中没有红色输出边的红色节点之一。（回想一下，“稀疏图”包含“密集图”的所有节点，特别是它包含所有红色节点）。 它必须具有*一些*输出边，因为密集图形中至少有一个输出边（我们尚未选择的红色输出边）。因为我们选择了最旧的边，而黑色的边比仍然可用的红色的边要新，所以一定是我们选择了蓝色的边。 由于稀疏图中的每个节点最多具有一个输出边，因此让我们遵循稀疏图中从该节点开始的唯一可能路径。 由于节点的数量是有限的，因此必须循环回到它之前访问过的某个节点，或者停在没有输出边的节点中。 让我们记下沿路径的数字序列（直到循环）<R1，T1>，..，<Rk，Tk>。 在循环的情况下，算法将检测到该循环并选择其节点之一作为死锁受害者（并且我们假定它不是我们的红色节点）。这意味着将从图中移除循环的一个节点，并且需要更新之前的节点。要么将其授予资源，从而将没有输出边（至少在一定时间内），要么必须等待，因为其他人在他之前获得了资源（在这种情况下，我们减少了它的第二个计数器）。在任何情况下，该路径在字典上都会变小。 如果路径停止在没有输出边的节点中，则意味着在有限的时间内，最后一个节点将完成（路径会变短，或者节点在更新之前会变小）或将请求一个资源，在这种情况下，路径可能会变长，但是第一个计数器将必须删除，从字典上来说也会更小。 因此，在有限的时间内与路径相关的数字序列在字典上将变小。 现在，没有无限减少的有界数的有界序列链！每个这样的序列都可以看作是一个非常大的2* tnnum位的长整数，以Tnum+Rnum+1为基数，并且它每次至少递减1，你不能将一个自然数递减无限次，不是吗? 这意味着在有限的时间后，我们的红节点将不得不将输出边切换到其他边。但是蓝边的数量是有限的。所以在有限的时间后，我们的红结点必须选择红边，但这与红边不再出现的假设相矛盾。

矛盾结束了证明。

但是您可能会反对，认为不应该限制事务访问的资源数量。数据库中的行数可以任意增加。您可能会怀疑，将“starvation freedom”等同于“每个请求都是在先天的有限时间内授予的”不是通常的定义。好吧，但是您必须承认，行数是有限的，并且为了避免互斥等待，必须在有限的时间内授予请求，因此让我们达成一个折衷方案。您可以将任意一对自然数(大小不限)放入每个新节点中。你看，这个证明仍然有效，因为不存在无限长递减链的有界长度的自然数序列，BUAHAHA！ 您可以通过归纳法看到这一点，很明显，它适用于长度<= 1的序列。如果我们只看每个序列中的第一个元素，那么从某个有限自然数开始，它必须是非递增的。如果存在无限长的序列链，但长度不超过N + 1，那么我们可以根据第一个元素对其进行分组，并且至少一个组将包含无限长的递减序列链，所有序列均以相同的数字开头，因为只有有限数量的组，并且其中有无限数量的元素。如果我们从中切出第一个元素，则会得到无限长的序列链，长度不超过N。矛盾结束了证明。

但是，但是....您可能会反对，一旦我们已经承认系统可以随着时间增长，就认为序列具有有限的长度是不公平的！是的，它在任何给定时间都是有限的，但不受限制。这是一个更棘手的问题，是否存在无限长的自然数有限序列的递减链？它们存在，<1>，<0,1>，<0,0,1>，<0,0,0,1>，……所以，如果您的服务器可以处理任意数量的大量并行事务，那么这种证明可能就行不通了，但是世界上只有这么多的套接字，RAM和客户端。

理论上的东西太多了，天文数字也很多。在实践中，大多数情况下会立即发现死锁，因为情况很简单，事务几乎不会发生互斥等待，循环几乎不会涉及所有事务，我们在选择边的时候不会运气很差。上面的理论证明只是给我们一些温暖舒适的感觉，即使在最坏的情况下也能想象得到。

它能为我们带来的好处是，我们无需为每个大型事务图添加一个混乱的图，而只需为每个事务存储一个指针即可，该指针指向当前正在等待的事务（或nullptr）。最多具有一个输出边的图很容易导航，只有一种前进的方式，因此您可以在恒定的内存和线性时间中找到一个循环。一旦不必处理图这样复杂的数据结构，您还可以做更多的事情！

第三个观察结果，您不必“stop the world”即可在稀疏图中搜索循环。如果存在死锁循环，它必须仅涉及已经在等待的事务。它们不会走到任何其他地方。 事实证明InnoDB已经有一个数组，该数组可以保存所有当前正在等待的事务，因此检测循环就像遍历该数组以记录它们等待的原因一样简单，并运行简单的线性算法来检测复制数据中的一个循环。由于该算法适用于副本，您无需在运行时“stop the world”，并且如果您在其中找到了一个循环，则可以保证该循环也仍然存在于实密度图中，因为它无法解决自己（记住超时和杀死查询的其他方式）。您可能会认为至少在抓取快照期间，我们需要“stop the world”。哈哈。不。

第四次个观察结果，我们只需要确保迭代所遍历的事务在创建快照时不会从内存中释放，因此，从它们那里复制当前等待的原因是安全的——它们仍然可以获得资源(边被删除)，或者在迭代过程中改变它们等待的原因(边的端点改变)。我们只需要避免读取指针本身(使用原子)，但快照是否一致并不重要。重要的是，如果有一个红色循环，那么它将停留在那里直到我们注意到为止。因此，快照的重要片段将保持一致。可能会出现一些误报，如果将不同时刻的边拼接在一起，那么最终的“弗兰肯斯坦图”可能看起来像是一个循环，实际上从来没有一个循环。ABA问题并且只有在最终再次检查死锁循环候选者确实是一个死锁时才stop the world（我们几乎没有误报，真正的死锁应该很少发生，因此“stop the world”对每一个死锁来说都不是什么大事）。几乎没有误报的原因是如果你真的认为这么槽,那么即使循环从不同的瞬间边缝合，然后因为事务使用两阶段锁的唯一方式循环是假正向的，如果它已经解决了由于事务被中止(可以最小化的机会通过运行同一线程死锁检测负责检测超时)或你误以为一个事务为另一个(因为它有重用id或指针地址或slot编号或任何你用来识别的东西),所以你只需要更小心ABA错误。

可观察性（演示）

InnoDB跟踪一些与死锁检测有关的统计信息。您可以在INFORMATION_SCHEMA.INNODB_METRICS中看到它们：

• lock_deadlocks –死锁数
• lock_timeouts –锁超时数
• lock_deadlock_false_positives –启发式算法在等待图中发现虚假候选死锁循环的次数
• lock_deadlock_rounds –等待图在搜索死锁中的扫描次数
• lock_threads_waiting –休眠等待锁定的查询线程数

以上信息来自information_schema.innodb_metrics

SELECT name,comment 
FROM INFORMATION_SCHEMA.INNODB_METRICS 
WHERE name IN ('lock_deadlocks','lock_timeouts','lock_deadlock_false_positives','lock_deadlock_rounds')

例如，您可以使用以下命令查找到目前为止发生了多少死锁：

SELECT `count` FROM INFORMATION_SCHEMA.INNODB_METRICS
WHERE NAME="lock_deadlocks";

另外，您还可以使用以下方法获取有关最新死锁的信息：

SHOW ENGINE INNODB STATUS;

并查看（可能不存在）“最新检测到的死锁”部分。 让我们在SQL中使用ABe和BAsil模拟该示例。（实际上，我们将使用更为明智和精细的方法，在该方法中，我们请求访问各个“单元”（“苹果”或“余额”），而不是整个“文件”（“ fileA”和“ fileB”），但是最终的死锁将具有相同的结构。我们必须这样做，因为InnoDB中的表级锁会以使解释更复杂的方式来干扰MySQL服务器本身的表级锁）

首先让我们准备阶段：

CREATE DATABASE test;
use test;
CREATE TABLE fileA (name VARCHAR(10) PRIMARY KEY, value INT);
CREATE TABLE fileB (name VARCHAR(10) PRIMARY KEY, value INT);
INSERT INTO fileA (name,value) VALUES ("Apples",10);
INSERT INTO fileB (name,value) VALUES ("Balance",0);

现在，在ABe的客户中：

ABe> BEGIN;
ABe> SELECT value FROM fileA WHERE name='Apples' FOR SHARE;
+-------+
| value |
+-------+
|    10 |
+-------+

我们可以确认，正如预期的那样，ABe获得了授予“苹果”的权限：

> SELECT ENGINE_TRANSACTION_ID as trx_id,OBJECT_NAME as `table`,INDEX_NAME,LOCK_DATA,LOCK_MODE,LOCK_STATUS FROM performance_schema.data_locks WHERE LOCK_TYPE='RECORD';
+-----------------+-------+------------+-----------+---------------+-------------+
| trx_id          | table | INDEX_NAME | LOCK_DATA | LOCK_MODE     | LOCK_STATUS |
+-----------------+-------+------------+-----------+---------------+-------------+
| 284271835218160 | filea | PRIMARY    | 'Apples'  | S,REC_NOT_GAP | GRANTED     |
+-----------------+-------+------------+-----------+---------------+-------------+

performance_schema.data_locks包含针对事务请求的每个访问权限。请注意，如何通过ENGINE_TRANSACTION_ID标识事务，通过OBJECT_NAME标识表，并且请求的实际资源是特定索引的行（因此，如果每个表有多个索引，则INDEX_NAME很重要），而LOCK_DATA标识该行。如早先提到的，InnoDB使用一组非常复杂的LOCK_MODE，它使事务可以指定它是否需要访问该行或它之间的间隙，或它们的某种组合，并且正如ABe指定的那样，他选择了该行FOR SHARE 并可以通过主键直接指向它，仅指向记录，而不指向必须被锁定且仅处于S（hared）模式的间隙。

现在，让BAsil从单独的连接开始：

BAsil> BEGIN;
BAsil> SELECT value FROM test.fileB WHERE name='Balance' FOR SHARE;
+-------+
| value |
+-------+
|     0 |
+-------+

并确认他也获得了所请求的访问权限：

> SELECT ENGINE_TRANSACTION_ID as trx_id,OBJECT_NAME as `table`,INDEX_NAME,LOCK_DATA,LOCK_MODE,LOCK_STATUS FROM performance_schema.data_locks WHERE LOCK_TYPE='RECORD';
+-----------------+-------+------------+-----------+---------------+-------------+
| trx_id          | table | INDEX_NAME | LOCK_DATA | LOCK_MODE     | LOCK_STATUS |
+-----------------+-------+------------+-----------+---------------+-------------+
| 284271835218160 | filea | PRIMARY    | 'Apples'  | S,REC_NOT_GAP | GRANTED     |
| 284271835219208 | fileb | PRIMARY    | 'Balance' | S,REC_NOT_GAP | GRANTED     |
+-----------------+-------+------------+-----------+---------------+-------------+

现在，让BAsil继续，尝试将Apple修改为0：

BAsil> UPDATE test.fileA SET value=0 WHERE name='Apples';

您会注意到，该查询不会立即返回，而是开始等待。如果不够快且等待时间太长，则会发生超时。可以使用以下方法检查默认超时：

SELECT @@innodb_lock_wait_timeout;
+----------------------------+
| @@innodb_lock_wait_timeout |
+----------------------------+
|                         50 |
+----------------------------+

不必急于处理此类情况，可以将其全局更改为类似以下的内容：

SET GLOBAL innodb_lock_wait_timeout=1000000;

您可以通过以下方式确认BAsil正在等待对表filea中的记录“ Apples”进行X（包含）锁定（但不在其前的空白处）

> SELECT ENGINE_TRANSACTION_ID as trx_id,OBJECT_NAME as `table`,INDEX_NAME,LOCK_DATA,LOCK_MODE,LOCK_STATUS FROM performance_schema.data_locks WHERE LOCK_TYPE='RECORD';
+-----------------+-------+------------+-----------+---------------+-------------+
| trx_id          | table | INDEX_NAME | LOCK_DATA | LOCK_MODE     | LOCK_STATUS |
+-----------------+-------+------------+-----------+---------------+-------------+
|            3064 | fileb | PRIMARY    | 'Balance' | S,REC_NOT_GAP | GRANTED     |
|            3064 | filea | PRIMARY    | 'Apples'  | X,REC_NOT_GAP | WAITING     |
| 284271835218160 | filea | PRIMARY    | 'Apples'  | S,REC_NOT_GAP | GRANTED     |
+-----------------+-------+------------+-----------+---------------+-------------+

在此需要注意的一个特殊细节是，BAsil的ENGINE_TRANSACTION_ID已从非常长的伪随机数284271835219208更改为看上去更理智且小巧的3064。InnoDB区分只读和读写事务。InnoDB试图保持乐观，最初假定事务是只读的，直到它执行一些更新。这样做的想法是避免必须分配来自单调序列的事务ID，此过程的同步成本很高。因此，在确实有必要之前事务没有分配实际的ID。一旦BAsil发出UPDATE语句，InnoDB就会发现这是一个读写事务，需要为其分配一个真实的事务ID。

现在，让我们回到ABe并尝试通过将Balance设置为10继续：

ABe> UPDATE fileB SET value=10 WHERE name='Balance';
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

从受害者的角度来看，这就是一个僵局。这次是被选为受害人的ABe，但可能是BAsil。

从幸存者的角度来看，它看起来只是授予了所请求的访问权限，因此BAsil的查询仅返回：

Query OK, 1 row affected (23.52 sec)

‍

（这23秒是我同时键入博客时手动执行此脚本的时间：D）

因此，BAsil可以毫无问题地完成工作：

BAsil> COMMIT;
Query OK, 0 rows affected (0.01 sec)

并且数据库的最终状态与ABe回滚且BAsil已提交的历史记录一致：

> SELECT * FROM test.fileA;
+--------+-------+
| name   | value |
+--------+-------+
| Apples |     0 |
+--------+-------+
1 row in set (0.00 sec)

> SELECT * FROM test.fileB;
+---------+-------+
| name    | value |
+---------+-------+
| Balance |     0 |
+---------+-------+
1 row in set (0.00 sec)

那ABe呢？他应该简单地重试整个事务。通常，这就是您应该如何处理死锁错误：不要惊慌，只需重试即可。

我们可以确认此死锁已正确计算：

> SELECT `count` FROM INFORMATION_SCHEMA.INNODB_METRICS WHERE NAME="lock_deadlocks";
+-------+
| count |
+-------+
|     1 |
+-------+

并在SHOW ENGINE INNODB STATUS输出中查看此（最新）事件：

------------------------
LATEST DETECTED DEADLOCK
------------------------
2020-07-27 14:21:59 0x2410
*** (1) TRANSACTION:
TRANSACTION 3064, ACTIVE 154 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 1200, 2 row lock(s)
MySQL thread id 10, OS thread handle 22236, query id 30 localhost ::1 root updating
UPDATE test.fileA SET value=0 WHERE name='Apples'

*** (1) HOLDS THE LOCK(S):
RECORD LOCKS space id 5 page no 4 n bits 72 index PRIMARY of table `test`.`fileb` trx id 3064 lock mode S locks rec but not gap
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 7; hex 42616c616e6365; asc Balance;;
 1: len 6; hex 000000000bf7; asc       ;;
 2: len 7; hex 810000009a0110; asc        ;;
 3: len 4; hex 80000000; asc     ;;


*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 4 page no 4 n bits 72 index PRIMARY of table `test`.`filea` trx id 3064 lock_mode X locks rec but not gap waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 6; hex 4170706c6573; asc Apples;;
 1: len 6; hex 000000000bf5; asc       ;;
 2: len 7; hex 81000000990110; asc        ;;
 3: len 4; hex 8000000a; asc     ;;


*** (2) TRANSACTION:
TRANSACTION 3065, ACTIVE 631 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 1200, 2 row lock(s)
MySQL thread id 9, OS thread handle 6128, query id 32 localhost ::1 root updating
UPDATE fileB SET value=10 WHERE name='Balance'

*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 4 page no 4 n bits 72 index PRIMARY of table `test`.`filea` trx id 3065 lock mode S locks rec but not gap
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 6; hex 4170706c6573; asc Apples;;
 1: len 6; hex 000000000bf5; asc       ;;
 2: len 7; hex 81000000990110; asc        ;;
 3: len 4; hex 8000000a; asc     ;;


*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 5 page no 4 n bits 72 index PRIMARY of table `test`.`fileb` trx id 3065 lock_mode X locks rec but not gap waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 7; hex 42616c616e6365; asc Balance;;
 1: len 6; hex 000000000bf7; asc       ;;
 2: len 7; hex 810000009a0110; asc        ;;
 3: len 4; hex 80000000; asc     ;;

*** WE ROLL BACK TRANSACTION (2)

这里有很多要解开的东西。首先，每个死锁都涉及一个循环中的一些事务，这些循环称为（1），...（N）。在这里，我们有一个仅涉及两个事务（1）和（2）的循环。***标记重要的部分，其中：

• 尝试描述事务（1）：
  • 识别事务本身的数据，
  • 在死锁时刻它拥有什么访问权限（该循环中的上一个trx需要），
  • 以及它正在等待获得什么访问权限，
• 然后对于事务（2）相同：
  • …
• <并且如果还有更多事务，则以相同的方式描述它们>
• 最后，宣布了牺牲事务（2）的裁决。

事务持有和请求的访问权限的描述方式很底层，需要一些实践才能正确解析。但更重要的是，它需要了解如何实现锁并将其绑定到InnoDB树的页面。您会看到，InnoDB将记录存储在页面中，并且页面由一对space_id和page_no标识。单个页面上可能有多个记录。事务的一种常见情况是选择一个对所有行请求相似访问权限的行序列，这为压缩提供了机会，与其将每个访问权限请求单独存储，不如将同一事务的所有同类请求分组给定的页面，我们使用位图来指示此页面涉及哪个记录。这也意味着锁定系统不必知道表和记录的实际“名称”，因此不会在字符串和主键上浪费内存。（这样做的代价是，要以人类可读的形式显示信息，必须查询实际的数据库页面以解码space_id和page_no映射到表和索引的名称，以及位图中的位置（heap_no）如何映射到实际键值。有时（例如由于缓冲池高速缓存未命中），此类信息不可用，因此将在输出中丢失。另一个缺点是每次B树页面重组都需要与Lock System合作来更新映射）

例如：

*** (1) HOLDS THE LOCK(S):
RECORD LOCKS space id 5 page no 4 n bits 72 index PRIMARY of table `test`.`fileb` trx id 3064 lock mode S locks rec but not gap
Record lock, heap no 2 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
0: len 7; hex 42616c616e6365; asc Balance;;
1: len 6; hex 000000000bf7; asc ;;
2: len 7; hex 810000009a0110; asc ;;
3: len 4; hex 80000000; asc ;;

表示事务（1）拥有以下访问权限：

• 下面列出的所有特定记录的权利在由space_id = 5和page_no = 4标识的内部页中。位图中有72位。该页面属于表test.fileb的PRIMARY索引。交易记录ID为3064。下面列出的所有权利都具有相同的模式“ S ”，仅用于记录本身，而不能用于它们之间的间隔：
  • 第0个字段的长度为7个字节，并包含字符串“ Balance ”
  • 1个第一字段具有6个字节，并含有x000000000bf7（其为3063，其是所述修饰的该行，这是在制备步骤的插入最后事务的事务ID）
  • 2第二字段具有7个字节，并含有x810000009a0110（这是一个“roll_ptr”又名“撤消指针”，其应指向的先前版本的数据行，但因为这是插入后的行的初始版本，它仅仅具有第55位设置为1表示该事实和其他一些信息）
  • 3 RD字段有4个字节，并含有x80000000（这是一个正零个长相如何以十六进制等在由SQL使用的编码。换句话说，值= 0）
  • <更多用户定义的列将在这里...>
  • 有权记录驻留在此页面堆上第2位的内容。（这意味着72位长位图有其2次位设置，从零编号）。该记录包含4个字段，格式紧凑。它的信息位等于0。这是该记录的字段（请注意，这是非常低级的内容，具体取决于InnoDB的索引类型和特定版本，其中一些列是由InnoDB本身生成的，等等。因此，如果没有一些其他知识，就无法解释它。表的形状，索引结构和源代码）：
  • <如果位图中有更多位设置为1，则将在此处列出更多记录>
• 重要说明：如果事务具有对其他页面或同一页面的访问权限，但使用的模式不同于S，REC_NOT_GAP，则它们不会在此处列出。输出仅包含死锁循环中涉及的锁定对象的描述，而不包含事务持有的其他锁定对象。如果它们全部都编码在同一个锁对象的位图中，则您可能偶尔会看到列出的更多锁，但是通常此输出不会让您知道该事务持有的所有锁。您可以通过查看输出中的“ LOCK WAIT 4个锁结构，堆大小1200、2个行锁”来确定是否丢失了某些内容，它表示内存中应该有4个锁对象，2其中的一个用于记录锁定（其他4-2 = 2用于表锁定）。

您可以用类似的方式解析其他部分。

对于我们人类来说，也许最重要的部分是通过提供它试图执行的查询来描述事务本身的部分：

*** (1) TRANSACTION: TRANSACTION 3064, ACTIVE 154 sec starting index read mysql tables in use 1, locked 1 LOCK WAIT 4 lock struct(s), heap size 1200, 2 row lock(s) MySQL thread id 10, OS thread handle 22236, query id 30 localhost ::1 root updating UPDATE test.fileA SET value=0 WHERE name='Apples'

同样，正确地解析和解释此问题可能需要调查源代码，但是至少我们知道事务等待完成的查询是什么。

SHOW ENGINE INNODB STATUS只显示你最近发现的死锁，如果你想跟踪所有这些，你可能想使他们记录到错误日志的innodb_print_all_deadlocks，但首先应该检查

SELECT `count` FROM INFORMATION_SCHEMA.INNODB_METRICS 
WHERE NAME="lock_deadlocks"

查看期望的输出，以免您不知所措。

还有一个选项可以使用innodb_deadlock_detect变量来禁用死锁检测算法，这对于使用旧版实现的某些客户很有用。我相信新的（8.0.18）实现不仅速度更快，而且更重要的是从专用后台线程运行而不会阻塞事务线程，因此我认为没有必要禁用此机制。我建议您保留默认值（开）。

感谢您使用MySQL！

感谢您关注MySQL解决方案工程师！