MySQL 如何让并发看起来像串行？

原文：InnoDB Data Locking，第 1 部分：引言

作者：Kuba Łopuszański，MySQL InnoDB 团队开发者，主要从事数据加锁机制的改进与并发性能优化。

这个系列介绍的是作者过去两年一直在研究的问题：怎样改进 InnoDB 对表和行的加锁方式，让客户端以为查询是一个接一个执行的，而服务器内部实际上有大量操作在并发执行。

为了便于理解，文章会先用简化的场景说明问题，再逐步补充现实中的细节。

当老妈问起「你是做什么的」时，作者会这样解释：

还记得 Excel 吗？里面有行和列，一个文件里可以有多个工作表，也可以同时处理多个文件。平时可能不会特意留意，但有一件事很重要：只要保存，填进单元格的内容就会保留下来。新增或删除一行时，即使有 SUM(A1:A100) 这样的公式引用了这些行，也会期待一切照常工作，对吧？

有没有和别人一起编辑同一张电子表格？当时是怎么避免覆盖对方修改的？是用 SharePoint 服务器限制同一时间只能有一个人编辑文件，还是每次改完都通过邮件把文件发给对方？也许办公室里还会传递一个吉祥物，谁拿到它，谁才能编辑？

后来出现了腾讯电子表格，多个人居然可以一起编辑同一张表。甚至还能按下「撤销」，只撤销自己的修改，而不影响别人的修改。

即使光标已经停在 E13，另一个人又在上方插入了一行，系统也知道，正在输入的值应该落到 E14。

现在，想象有 1,000 个人，不停地在多个文件、多个工作表里新增、删除和修改单元格。他们都觉得这些操作理应正常完成，SUM(A1:A100) 这样的公式也应该始终准确更新。

作者面对的正是这样的情况：成千上万台客户端机器执行 INSERT、DELETE、UPDATE、SELECT，或者执行由这些操作组成的更长序列，也就是事务。开发者往往把处理事务的服务器想象成一个黑盒：把事务一个接一个地执行，「一次服务一个人」。

但真要这样做，速度就太慢了。只要还能让客户端以为操作是按顺序完成的，服务器就会尽可能并行处理这些修改。也就是说，假如有人追问，服务器必须能给出一条合理的时间线，用它解释观察到的数据库状态：看起来，客户端确实是依次得到服务的，尽管实际上，操作是交错执行的，不同查询的某些部分甚至在同时执行。

程序员正是带着这种假设编写程序的，这能让开发工作轻松一些。

这也是数据库对开发者的重要价值。LAMP（Linux + Apache + MySQL + PHP）技术栈因此能向 PHP 开发者隐藏并行处理的大部分复杂性，让数据库成为唯一的事实来源。或者说，「事实」来源。

但服务器如何做到这一点？怎样编出一个令人信服的谎言？又怎样在不被识破的情况下，把谎撒得更快？

第一个办法很糟糕：一次只把所有「Excel 文件」（数据库）的访问权限交给一个事务，等它结束，再交给队列中的下一个事务。这当然与一次只处理一个客户端没有区别，因为它做的就是这件事。连接虽然有多个，但大部分时间都在等待，并没有真正加速。并行处理的承诺落空了。

而且，这已经引出了第一个现实问题：如果有人打开文件后忘记关闭，就跑去度假了，该怎么办？

可以引入超时机制。例如规定，每个事务必须在 50 秒内完成，否则就回滚：撤销它的所有工作，释放它持有的锁。之所以要这样清理，是因为不能让其他人看到未完成的工作，也不知道该怎样替它完成。等这位惹麻烦的人度假回来，收到通知后，就可以再试一次。

有一点可以用来提速：有些人只想读文件，并不打算修改。这样的人甚至可能占大多数，毕竟，创造内容通常比消费内容更费力。因此，可以设置读和写两种访问模式。写权限必须独占，既要防止其他写者干扰，也要避免读者看到尚未完成的工作；读权限则可以由多个读者同时持有。

这样就有机会大幅提速。假如写者与读者所需的处理时间之比为 1:9，那么这 9 份读取工作可以并行进行，总时间就可能从 1 + 9 降为 1 + 1，快了 5 倍。

不过，别忘了：假如有人追问，服务器仍然必须能够给出一条串行时间线，而且要与所有读者和写者的观察结果一致。

在这个例子里，这不难做到。数据库状态只会被写者改变，而两个写者不可能同时持有写权限。因此，可以先按照写者获得写权限的顺序，把它们放到时间线上。

然后，把读事务填进空隙里：每个读者都应排在它看到的那次写入之后，以及它没有看到的那次写入之前。由于读者和写者不会同时持有权限，对于任意一对读者和写者，都能明确判断谁先谁后。（有经验的读者也许会质疑：多台服务器、复制、中子星等情况下，时间的相对性问题，就这么带过了？暂时先忽略这些问题。）

写者之间、读者与写者之间，都有明确的先后顺序。但在两次写入之间，读者彼此的顺序可以由服务器自由安排。对于 n 个读者，有 n 的阶乘种排法。也就是说，服务器可以撒谎，而且没有人能发现！它能编排的顺序越多，就越有机会并行执行。

这种读写方案有一个不容易察觉的问题：如果读者不断到来，虽然每个人都遵守「每人最多 50 秒」的规定，但系统中始终至少有一个读者持有读权限，写者岂不是永远无法开始工作？这就是写者「饥饿」。

可以用先进先出队列，也就是 FIFO，来解决这个问题。规则是：新读者不能因为没人持有写权限，就直接开始读取。它还得检查前面是否有人等待；如果有，就排到队尾。

因此，如果已经有一个写者在等待现有读者结束并释放读权限，那么新读者就必须排到这个写者后面，而不能「反正能读」就直接加入。

在这个简化的场景里，最多过 50 秒，正在读取的事务就会结束，或者因超时被迫回滚，等待中的写者便能获得写锁。反过来，写者让读者饥饿的情况也能避免，尽管现实中这种情况较少见。

除了 FIFO，也可以使用优先级队列。有些事务可能出于某种原因被认为更重要，因此可以插队。

后面讨论拥塞感知事务调度（Congestion Aware Transaction Scheduling，CATS）时，还会谈到这种做法。决定把访问权限授予谁时，可以考虑事务已经在系统中等待了多久。这也是 InnoDB 早先使用的 VATS 方案的基本思路。

还可以换个思路，不必只调整队列顺序。别忘了，服务器可以撒谎！假如每隔一段时间，比如每分钟，就给所有文件做一次备份，会怎样？

读者到来时，把最近一次备份交给它就行。它不必等待正在执行或排队中的写者，可以立刻读取旧版本的文件，还看不出有什么不对。这就叫作「读视图」。每个读者在整个事务期间使用同一个读视图。多个读者可以共享一个读视图，也可以分别使用不同的读视图；只要不被识破，具体怎么做就是实现细节。

如果有人询问时间线，服务器就可以假装：这次读取「发生在」备份完成后的第一次写入之前。狡猾之处在于，写操作仍在原来的位置，读事务却被悄悄挪到了各次备份的时刻。

读者怎样才能识破？它得「从某个可靠来源得知」，某次写入「发生在」自己的读取之前，却又读不到这次写入的结果。例如，同事 Alice 明确说过，她已经把新数字填进报告了，可读者就是看不到！

或者，数字明明就是读者自己填的，也清楚记得填过，还按了 CTRL+S，真见鬼！

然而，在这个模型中，只有在同一个事务里亲自写入再读取，才算是「官方认可」的可靠来源。这正是「事务」的意义。

如果读和写不属于同一个「事务」，服务器始终可以推卸责任，大概会这样说：「也许从她的角度看，她确实认为自己已经填入了新数字。但这里的时空弯曲得很奇怪，或许你还处于她的过去，所以仍然看不到结果？」

读者反驳：「可她明明亲口说了！」

服务器回应：「抱歉，Dave，『声音』既不属于 SQL 协议，也不在服务等级协议的范围内。这里只承诺事务可以按某种顺序串行化，并没有承诺那些服务器无法接触到的带外通信，也会与这个顺序一致。如果希望把这些通信考虑进去，下次请通过 XA 协议告知。」

如果再邪恶一点，服务器完全可以每年才备份一次，甚至只在数据库最初还是空的时候备份一次，省去存储真实数据、再提供给读者的麻烦！这很讨厌，但如果只要求可串行化，规则就是如此。

这个虚构故事也说明，人们的要求通常不止于此。例如，要能看到自己写入的内容；请求最新结果时，结果至少要与挂钟时间有「某种程度」的一致；如果能证明其他人的写入「发生在」读取开始之前，也应该能看到这些修改。

要满足其中大部分要求，可以在每个事务成功「提交」后，给所有文件做一份新备份，也就是「所有数据库的快照」。新读者到来时，始终把最新的读视图交给它。这样，读视图就会包含这个读者「已知提交的事务」所做的修改。

（严格来说，仍然存在一个问题：读者读取过程中，偶然听说某位同事已经成功提交了对文件的最新修改，但这似乎与当前读视图中的内容矛盾，尤其会打破「这次读取应当发生在那次写入之前」的假象。不过，服务器仍然可以回答：「听来的传闻不归服务器管。如果听到了来自未来的消息，也许应该少相信耳朵，多看看屏幕。」）

这种方法的好处是，甚至不再需要读权限了。读者想读就读。另一方面，写者仍然需要排队，以免彼此干扰。

前面的方案假定，读者和写者可以清楚地区分开来。写者当然也能读取，但它得从事务一开始就知道自己要写入，尽早申请写权限。

但现实中，很多人都是先读文档，再决定要不要改点什么。这就需要把读权限升级为写权限。

使用快照的读视图，该怎样处理这种升级？开始编辑的一瞬间，文件要在眼前突然变成最新版本吗？暂且假设，事务执行写操作时，会弹出一个新窗口，显示最新版本。事务既可以留在旧窗口读取原来的读视图，也可以到新窗口编辑最新版本。

（顺便一提，这正是为什么在 REPEATABLE READ 隔离级别下，同一个事务内的 SELECT * FROM t; 与 SELECT * FROM t FOR SHARE; 会得到不同结果：事务可以访问两个「窗口」，前一个查询使用读视图，后一个查询使用行的最新版本。）

先把读视图放到一边，回到只有读权限、写权限和简单 FIFO 队列的方案，看看「访问权限升级」究竟怎样工作。

假设一个事务已经持有读权限，现在又申请写权限。按照前面的算法，它需要排队，等待所有读者释放读权限。可它自己也是读者！为了避免等到自己头上，需要增加一条规则：检查权限冲突时，可以忽略自己。

这样做是否正确，还得仔细分析：增加这条规则后，服务器还能不能给出一个合理的事务顺序？

一种看似合理的做法，是把这个事务放到它获得写权限的时间点。这样既能解释为什么其他并发读者没有看到它的操作，也能解释为什么它没有看到后续写者的修改。目前看不出什么问题。

但如果申请写权限时，队列里已经有另一个写者在等待呢？该插队，还是排在后面？

如果插队，似乎可以把这个事务排在等待中的写者之前。但这也留下了一个漏洞：别人可以假装只想读点东西，随后再把权限升级为写。等待中的写者只能眼睁睁地看着这些人插队。

不过，这个写者不应该无限期地饿下去。新来的人即使只申请读权限，也得排在它后面。能够抢先升级权限的，只有原本就在它前面的那有限几个读者。

如果不插队，就会发生死锁：这个事务在等写者，写者在等读者结束，而这个事务自己就在那些读者之中。（原文发表时，InnoDB 使用的是后一种做法，因为代码更简单，死锁相对少见，而且可以通过尽早申请写权限来缓解。不过，尝试第一种做法，也在当时的后续计划之中。）

到目前为止，所有数据库的访问，都是由一把读写锁保护的。

锁的粒度还可以更细。如果两个事务各自只访问一个数据库，而且访问的不是同一个，就可以并行执行。这类似于 SharePoint：某个人编辑文件时，这个文件会一直被锁住，但其他人仍然可以操作别的文件，无需等待。

如果能找到更多这样的机会，就能让更多客户端同时执行事务。

对于毫无交集的两个事务，谁先谁后其实无关紧要，服务器很容易解释。只有同时查看两个文件的人，才可能判断它们的相对顺序。可如果某个人需要访问不止一个文件，又该怎么办？前面还没有规定这种情况。

假设作者要把 Assortment.odt 中的一些数字复制到 Balance.odt。前者简称文件 A，后者简称文件 B。这需要先申请 A 的读权限，再申请 B 的写权限。

再假设 Alice 使用写权限，把数字填进文件 A；Basil 则读取两个文件，先读 B，再读 A。为了方便理解，角色的名字与他们操作文件的顺序相对应：

1、Alice 写入文件 A。

2、Basil 先读取文件 B，再读取文件 A。

3、作者先打开 A，再打开 B，后文就称他为 Abe。

无论这些操作怎样交错执行，这套加锁方案都能保证结果与 Alice、Basil 和 Abe 的某种串行执行顺序一致吗？

不妨先看看完全没有加锁规则时，可能出什么问题：Alice 坚称，已经把 Assortment.odt 里的 Apples 从 0 改成了 10；Abe 也记得，确实看到了 10 个苹果，并把这个数字写进了 Balance.odt，将 Budget 从 0 改成 10；Basil 却说，先看到了 Budget 为 10，随后又看到了 Apples 为 0。这岂不是显得 Abe 把苹果数量报多了，连这点事都做不好？

希望这套加锁方案不会酿成这样的悲剧！

接下来，按权限授予的顺序逐一分析，看看遵循加锁协议的服务器能否解释这些结果。

Abe 首先申请 A 的读权限，这与 Alice 所需的写权限不兼容，两人必然有一个先获得权限。分析就从这里分成两种情况。后面的分支会越来越多；只要理解了「分析所有可能的执行历史」是怎么回事，就可以跳过这一段。

情形 1

Alice 先获得写权限，Abe 必须等她完成，才能获得读权限。因此，Abe 查看文件 A 时，看到了她修改后的数字：10 个苹果。

随后，Abe 尝试把数字写入文件 B，需要申请写权限。这与 Basil 所需的读权限不兼容，二人又得分个先后。

情形 1.1

Abe 先获得写权限，Basil 只能等待。等 Abe 写入 Budget=10、保存并释放全部访问权限后，Basil 才能读取文件 B，看到 Budget=10。接着，Basil 获得文件 A 的读权限，看到了 Alice 写入的 Apples=10，满意地给大家都加了薪。

如果被问起，服务器就可以假装顺序是：Alice、Abe、Basil。

情形 1.2

Basil 比 Abe 更早查看文件 B，看到的是 Budget=0。接着，他申请文件 A 的读权限。Alice 已经完成，而 Abe 也只持有读权限，不会阻挡他，因此他顺利读到了 Apples=10。

Basil 觉得 Abe 很懒，但还算称职。虽然没给任何人加薪，倒也没有发火。等他结束后，Abe 再更新文件 B，完成自己的工作。

服务器可以假装顺序是：Alice、Basil、Abe。

这里的谎言很微妙：Abe 和 Basil 实际上在并行工作，但两人都看不出来。

除了没能加薪之外。

情形 2

Alice 晚了一分钟，Abe 因此读到了文件 A 的旧版本，其中 Apples=0。随后，Abe 申请文件 B 的写权限。根据他与 Basil 谁先获得权限，又可以分成两种情况。

情形 2.1

Abe 比 Basil 更早获得文件 B 的写权限。打开文件后，发现 Budget=0，就不改数字了，只把字体改成红色，表达一下悲伤。

Abe 释放访问权限之后，Basil 对文件 B 的读请求得到批准。Basil 看着红色的 Budget=0，挠了挠头，决定再去看看文件 A。

接下来还得看 Alice 是否已经更新文件。她所需的写权限与 Basil 所需的读权限互斥，二人必定有一个在前。

情形 2.1.1

Alice 先写入 Apples=10 并释放写权限，Basil 随后获得读权限。

于是，Basil 看到了 Apples=10，再结合之前看到的 Budget=0，得出结论：Abe 很懒，但至少没有凭空变出苹果。

服务器可以假装顺序是：Abe、Alice、Basil。

如果 Alice 更新文件 A 时，Basil 其实正在检查文件 B 中的 Budget，这个顺序又算是个小谎，不过谁在乎呢？

即使 Abe 没有改动 Budget=0 单元格的背景色，也不可能把顺序说成「Alice、Basil、Abe」。Abe 毕竟是称职的，不会看到 Alice 填入的 10 个苹果，还把 Budget 留在 0！

情形 2.1.2

Alice 这天来晚了，还没开始写入，Basil 就获得了读权限，读到的是 Apples=0。这与 Budget=0 对得上：Abe 没有失职，只是市场行情很差。

接着，Alice 获得文件 A 的写权限，把 Apples 改成 10，一天就这样结束了。

服务器坚持说，事情的顺序是：Abe、Basil、Alice。

如果 Abe 没有改动背景色，顺序也可以说成「Basil、Abe、Alice」，服务器便多了一种选择。

译注：情形 2.1 开头写的是修改「字体颜色」，后面两处原文则写成了「背景色」。这里保留了原文的表述差异。

情形 2.2

在 Abe 获得文件 B 的写权限之前，Basil 先获得了它的读权限。因此，Basil 看到的是旧值 Budget=0。

接着，Basil 尝试读取文件 A。由于这个访问请求与 Alice 对同一文件的写请求不兼容，二人必定有一个先获得访问权限。

情形 2.2.1

Alice 先写，Basil 后读。这就有意思了：根据整个 2.* 分支的前提，Abe 的读取又发生在 Alice 之前。只看文件 A，顺序就必须是：Abe、Alice、Basil。

但 2.2.* 的前提却是，Abe 对文件 B 的写入发生在 Basil 的读取之后。两者似乎矛盾了。

能不能因为情形 2.2.1 不符合服务器想编的故事，就宣布它不可能发生？不行，那是在作弊。必须根据访问权限 FIFO 队列的规则、参与者的观察结果，以及已有假设，证明这个场景不可能出现。

也就是说：

1、根据 2.2.* 的前提，Basil 获得文件 B 的读权限，早于 Abe 获得 B 的写权限。

▼
text
复制代码
Basil.read(B) << ABe.write(B)

2、根据 2.* 的前提，Abe 获得文件 A 的读权限，早于 Alice 获得 A 的写权限。

▼
text
复制代码
ABe.read(A) << Alice.write(A)

3、根据 2.2.1 的前提，在文件 A 的队列里，Alice 的写入位于 Basil 的读取之前。

▼
text
复制代码
Alice.write(A) << Basil.read(A)

4、此外还知道，Basil 是在读取 B 之后，才尝试读取 A：

▼
text
复制代码
Basil.read(A) << Basil.read(B)

将这些条件合起来，可以得到：

▼
text
复制代码
ABe.read(A) << Alice.write(A) << Basil.read(A) << Basil.read(B) << ABe.write(B)

译注：以上公式按原文保留。第 4 条的公式与文字描述相反：按「先读 B，再读 A」，应为 Basil.read(B) << Basil.read(A)，因此紧随其后的合并公式也不能按原样成立。原文这一处推导存在笔误，阅读时需注意。

问题在哪里？按这个顺序，Alice 获得 A 的写权限时，Abe 还持有 A 的读权限，因为 Abe 得完成对 B 的写入后才能释放它。这就是要找的矛盾！

情形 2.2.2

Alice 在 Basil 读取之后才写入。因此，Basil 在两个文件里看到的都是旧值 0。服务器可以假装顺序是：Basil、Abe、Alice。

真够累人的。

这番分析说明了几件事。

首先，服务器可以从每个文件的 FIFO 队列中得到偏序关系，再据此拼出事务的最终顺序，或者至少以此为起点。这些关系不能忽略，因为客户端可能观察到它们，例如后面的读取可能看到前面的写入。

其次，只知道每个事务要做什么，还不足以描述底层所有可能的交错执行方式。但无论实际怎样执行，服务器最终都可以把它解释成 3! 种排列中的某一种：

情形 1.1：Alice、Abe、Basil。

情形 1.2：Alice、Basil、Abe。

情形 2.1.1：Abe、Alice、Basil。

情形 2.1.2：Abe、Basil、Alice。

情形 2.2.1：不可能发生。

情形 2.2.2：Basil、Abe、Alice。

最后，这类问题往往很难证明，作者甚至也不确定这次是否证明对了。比如，为什么没有场景对应「Basil、Alice、Abe」的顺序？看来是漏了一步，还得根据 Basil 是否赶在 Alice 前面，把情形 1.2 再拆成两个分支。可见这件事有多复杂。

要站在服务器的角度推想时间线，作者发现了一个好用的办法：把整个过程想象成俄罗斯方块游戏。每一列代表一种资源，这里就是一个文件。事务申请某个文件的访问权限时，就从对应列的顶部落下一个 1×1 的方块，用颜色区分事务。方块落到地面，就表示事务获得了访问权限。

如果没落到地面，事务就得等下方方块的拥有者先完成。一列方块就像一个 FIFO 队列。

上图展示了三个事务：trxR 已经在等待 trxG 持有的资源 B；trxG 正在申请资源 C，因此必须等待当前持有 C 的 trxB。

事务结束时，它的所有方块都会消失，上方的方块随之下落，相当于在队列里向前移动。此时落到地面的方块所代表的事务，就获得了访问权限：

这个类比只适用于独占访问权限，所以暂且假设这里只有写入。

现在重放这场游戏的录像，但做一点改动：事务结束后，方块也不消失。最后就会留下这样一幅静态图：

上图中，事务形成了一层层彩色方块，每种颜色代表一个事务。

服务器可以根据这些彩色层之间的偏序关系，给出与观察结果一致的顺序。如果一个事务的方块压在另一个事务的方块上，就说明下方事务释放权限后，上方事务才获得权限。后者因此有机会看到前者的结果，在虚构的执行顺序里，也必须排在前者之后。

例如，上图中的 trxV 必须排在 trxY 和 trxO 之后。

只要给出的顺序与这些彩色层一致，就没有人能识破服务器的谎言。

但这些层真的构成偏序吗？会不会出现环？

很遗憾，会！

回到前面的例子，假设 Basil 不只是想读文件 A，还想写它。

可能出现这样的情况：Abe 持有文件 A 的读权限，Basil 持有文件 B 的读权限。接着，Abe 想写文件 B，却被 Basil 的读权限挡住；Basil 想写文件 A，又被 Abe 的读权限挡住。

这就形成了典型的死锁环。在俄罗斯方块游戏中，看起来是这样的：

注意，没有哪一层整体位于另一层上方。

两条蛇的脑袋，都压在对方的尾巴上！

怎样发现这种情况？前面已经提到过一种办法：超时。既然双方除了等待什么也做不了，最终至少有一方会超时，另一方就能继续执行。

超时后，事务所做的全部修改都会回滚，因此继续执行的事务不会看到另一方的修改。这是好事，就像那些方块从游戏的历史中彻底消失，仿佛从未存在过。

更糟的情况是，双方都超时、都重试，结果又撞在一起，如此反复。这就叫作活锁。可以尝试让每次重试前的退避等待时间随机变化，或者约定某种礼让规则，比如「长得好看的先来，年长的靠后」。

也可以遵守一条简单规则，彻底避免死锁：始终按字母顺序打开文件。

如果 Abe 和 Basil 都遵守这条规则，就不会各自持有对方需要的资源。因为按字典序排列，每个人接下来申请的资源，都在已经持有的资源之后。

在俄罗斯方块游戏中，每个事务只能向此前方块右边的列投放新方块。各层都从左向右延伸，就不可能出现「两条蛇的脑袋分别压在对方尾巴上」的局面，因为至少得有一条蛇向左移动，才能形成这样的环。

顺便说一句，LOCK TABLES 使用的就是这种策略。它会在内部对传入的表列表排序，再按升序获取锁。这也解释了为什么必须提前指定所有表，以及为什么它在一定程度上与其他死锁预防机制不兼容。

当然，不一定非得按字母排序。用什么顺序都可以，只要整个应用遵守同一套顺序。

不过，即使可以自行选择顺序，要让应用始终按这个顺序获取锁，也不容易。InnoDB 开发者对此深有体会：它的内部代码就靠规定获取顺序，避免底层锁之间发生死锁。但要让不同团队、插件、层次、模块和并行开发的分支始终遵守这条规则，确实很难。

死锁因此很难彻底避免。如何检测死锁，是第 3 部分要讨论的问题。在那之前，第 2 部分会先介绍：这些抽象概念，在 InnoDB 的锁系统中，究竟对应哪些具体的锁对象。