InnoDB数据锁–第4部分“调度”

作者：Kuba 译：徐轶韬

在本系列博客中，我将描述InnoDB如何对数据（表和行）加锁，以向用户提供查询是按顺序执行的错觉，以及在最近的发行版中如何对此进行了改进。

正如我们已经看到的，服务器假设事务发生的顺序（序列化顺序）与授予事务锁定的顺序相关。因此，授予锁的顺序可以影响事务出现的顺序和性能。

当一个资源目前没有被任何人锁定时，一个事务请求对它的访问权，InnoDB会立即授予它。你可以想象一个不同的策略，在这个策略中，事务的ID、时间戳或之前锁定的资源以某种方式发挥作用，但InnoDB只是将一个无竞争的资源授予立即需要它的人。

但是，当事务完成并因此不再需要访问资源时，我们就有机会向正在等待该资源的其他事务之一授予对该资源的访问权限。问题是：选择哪一个？这是服务器在调整序列化顺序和性能时所具有的灵活性。

方法1.先进先出 FIFO

最简单且相对较好的方法是先授予等待时间最长的事务的访问权，这可以通过使用first In first Out队列来完成。每个资源都有一个这样的FIFO。当一个事务请求访问一个资源时，我们首先检查是否可以立即授予它。这可以很简单，只需扫描当前拥有该资源访问权限的事务列表，并检查访问权限是否冲突。然而，为了避免互斥等待，检查已经在队列中等待的事务也是有意义的。我们在InnoDB数据锁——第2部分“锁”中看到，检查两个锁请求之间冲突的规则可能相当复杂，但最终我们应该能够决定是否立即授予我们的新请求，还是必须等待。如果我们必须等待，我们将请求附加到特定于给定资源的队列的末尾。

事务完成后，我们逐一释放其每个锁，每次检查相应的等待队列，并按FIFO顺序逐一考虑等待者，检查是否可以将锁授予他们。请注意，有可能发生无法授予的情况（例如，如果我们的事务具有共享锁并且仍然有其他访问权的持有人），或者可能同时有多个请求被授予（例如，如果我们的事务在资源上拥有排他锁，并且有个事务正在等待对该资源的共享锁）。同样有可能的是，将请求授予某个等待者实际上会禁止向队列中稍后的等待者授予请求（例如，如果两个等待者中的第一个需要互斥锁）。

多年来，此算法一直是InnoDB的默认算法，直到与学术界的合作为我们带来了下面的改进。

差异感知事务调度

在论文 “Identifying the Major Sources of Variance in TransactionLatencies: Towards More Predictable Databases” 《确定事务延迟差异的主要来源：建立更可预测的数据库》中来自密歇根大学的Jiamin Huang，Barzan Mozafari，Grant Schoenebeck和Thomas Wenisch提出了一个旨在最小化调度造成的差异的想法。这个想法是，FIFO虽然乍一看似乎很公平，因为新来者不会绕过队列中已有的事务，但这并没有真正将“旧事务应具有优先于新事务的优先权”这一概念推向其逻辑结论：队列中的顺序应由事务的“时间”（即事务已在系统中花费的时间）确定。要了解FIFO并没有真正按“时间”对事务进行排序，请认识到单个事务可以在其生命周期内请求多个资源，从而访问多个队列，并且每次它都被视为一个“新成员”，即使它已经在之前的队列中花费了很多时间。为了让这更公平，他们将根据事务产生的时间重新安排。

AFAIK的这一版本的想法并未在mysql的正式发布中发布，因为密歇根州的研究人员很快提出了另一项改进。

竞争感知锁调度

Boyu Tian, Jiamin Huang, Barzan Mozafari和Grant Schoenebeck在他们的下一篇论文“Contention-Aware Lock Scheduling for TransactionalDatabases” 《用于事务性数据库的竞争感知锁调度》中提出了一种使用不同标准对等待者进行排序的想法。由于给定的事务必须等待而(传递性地)阻塞了其他事务。在等待资源之前，一个正在等待的事务可能已经积累了对许多资源的请求权限，现在其他事务必须等待它释放这些权限。如果我们强迫这样的事务等待，我们也间接地迫使所有其他事务等待它，这意味着额外“等待单位”的影响将乘以等待的事务的规模。从概念上讲，这类似于为每个事务分配“权重”，与等待它的等待者和等待等待它的等待者的“子树”的大小成比例。“等待图”的概念在InnoDB数据锁-第3部分“死锁”中有描述，简单来说，你可以把等待的事务想象成有箭头指向它们等待资源的事务。图通常是一个有向无环图，而不是树，因此“权重”应该是“子图”的大小，而不是“子树”。

您也可以在我们之前的文章 “Contention-Aware Transaction Scheduling Arriving in InnoDB to Boost Performance”查阅这部分内容。

这是与MySQL 8.0.3一起发布的算法，其首字母缩写为CATS（竞争意识事务调度）。

要把论文中的想法直接正确地贯彻执行，存在一些困难。刚开始，每当等待图中的一条边出现或消失时，通过增加或减小权重来跟踪每个事务的权重似乎很容易，假设您只需要添加或减去已经计算出的权重即可。然而，经过更仔细的思考，您不仅必须传播从边缘端点可到达的所有节点的权值(它们的权值也改变了!)——甚至不清楚应该更新的值是什么!“权重”的定义取决于“B是否可以从A到达?”而不是“从A到B有多少种不同的方式?”对于树而言，这可能是无关紧要的差异，但不适用于可能有不止一种方法从一个节点到达另一节点的更复杂的图，因此尚不清楚添加一条边或移除一条边是否会更改可达性。例如，很可能情况是从权重为5的节点向另一个节点添加一条新边不会带来5个新关注者，而只是3个新关注者，因为其他2个已经可以到达该节点。同样，删除单个边缘并不一定意味着您已经失去了相对侧节点之间的连接性。

试图忽略这种差异（在“可以到达我的节点数”和“可以到达我的路径数”之间），在实际中并没有什么大不了的。出于性能原因，这确实是初始实施的目的。我们在增加和减少的数字不完全是本文中定义的“权重”，但它们似乎仍与特定事务引起的“争用”相关。您可以创建路径数量成指数的等待图，从而导致溢出，但是实际上这很少发生，可以通过限制值进行修补。

但是，在此简化的实现中存在一个更细微的错误：没有考虑图形本身随时间变化的情况，并且当边缘出现时您添加的数字不一定与消失时所减去的数字相同，这可能会导致达到令人吃惊的结果，例如负重或溢出。这些再次通过收紧得到解决，但是越来越明显的是，要获得“真实”值，应该从头开始重新计算所有值，而不是进行点更新。

但从性能的角度来看，这是不允许的：每当一条边出现或消失时，以拓扑顺序处理整个等待图表，以使调度“更加公平”而使整个世界停止，这将是一个不好的权衡。幸运的是，我们可以重用更快的死锁检测所需的思想和实现，从而获得我们今天拥有的解决方案……

Atomic CATS！

如InnoDB数据锁–第3部分“死锁”中所述，在InnoDB中，可以对事务之间的等待关系的精简版本进行快照。它是在后台线程中完成的，不需要停止整个系统。这意味着我们可以根据此快照非常便宜地估计每个事务的“权重”。计算值仍不完全是论文作者想要的，因为在图形的精简版本中，每个节点最多只有一个输出边缘。但是，这种近似值在实践中足够好，并且总是从头开始重新计算，因此错误（如果有的话）不会随着时间的流逝而增加。使用C ++原子性将计算值无锁存地存储在事务对象中，并且在对等待者进行排序之前以相同的方式读取它们。

这种变化的意思是执行事务的线程不必仅仅因为它必须在图的整个“下游”部分执行更新权重而停止系统，这消除了我们所经历的痛苦瓶颈并使CATS算法变得实用。从历史上看，我们曾在CATS和FIFO之间进行选择，因为CATS在某些情况下太慢，不值得使用。有了原子CATS，我们终于可以放弃FIFO实现，现在在每种情况下都可以使用CATS。（您可以通过注释一下lock_wait_compute_and_publish_weights_except_cycles和lock_wait_update_weights_on_cycle来使用CATS“模拟” FIFO，这将有效地使所有事务具有相同的权重–我们无需为此进行切换，因为CATS在我们的测试中始终比以前更好）

您可以通过检查目前的计算值quering INFORMATION_SCHEMA.INNODB_TRX.TRX_SCHEDULE_WEIGHT列（不要与TRX_WEIGHT列混淆，它是用来确定一个最轻死锁牺牲品）。

等待者的排序利用了以下事实：权重的常见的值为1（没人等待事务），因此在运行O（NlgN）排序之前，我们首先进行O（N）扫描以筛选出所有权重为1的事务，这些事务应在schedule_weight> 1之后处理。通常，这意味着没有什么可排序的了。

但是，这并不是锁系统可进行优化的终点。恰恰相反！这只是一个先决条件，使我们能够最终解决更大的问题– 锁系统的可伸缩性，这是下一部分InnoDB 数据锁 –第5部分“并发队列”的主题。