InnoDB数据锁–第5部分“并发队列”

到目前为止，我们已经看到当前授予和等待授予的访问权限表示为内存中的记录锁和表锁对象，我们可以通过performance_schema.data_locks进行检查。我们还了解到，它们形成了“队列”，从概念上讲每种资源都有一个队列。我们省略了技术细节，队列本身是一个数据结构，可以从许多（也许是数千个）线程中并行访问。我们如何确保队列的完整性和快速的并行操作？具有讽刺意味的是，锁系统本身似乎需要某种形式的闩锁。

这篇文章是关于锁系统性能最重要的更改，“WL#10314: InnoDB: Lock-sys optimization: sharded lock_sys mutex”在PawełOlchawa提出并实施了概念验证之后的数年，它出现在8.0.21版本。这个想法似乎相对容易解释，让在不同资源的锁队列上运行的线程并行运行，而不是闩锁整个锁系统。例如，如果一个事务需要在一个表中排队等待一个行的锁，该操作可以与另一个事务并行释放另一个资源上的锁来完成。请注意，这是高频的“锁”的低级更改，而不是高频的长期“锁” –我们在这里关心的是队列本身的数据完整性，以及如何协调对队列对象的操作，例如如“入队”，“出队”和“迭代” 。在实践中每种操作都很短，但是过去要求闩锁住整个锁系统，因此，在完成之前，其他任何线程都无法碰到任何队列。本文比以前的文章中介绍的要低一个抽象级别，要排队的锁可能要等待几秒钟才能被授予，但仅排队的操作，这是一个很小的，非常短的分配操作我们现在关注的是锁对象，并将其添加到列表中。

在阅读了本系列的前几篇文章后，花了这么长时间将Paweł的想法付诸现实的原因之一希望现在可以弄清楚，锁系统是一种非常复杂的野兽，并至少有两个地方试图在整个等待图上做一些全局的事情，而不是在一个队列内本地做一些事情:死锁检测和CATS，它们都执行了DFS。先前文章中描述的更改将这些昂贵的操作移到了单独的线程上，并确保它们在操作时不必闩锁整个锁系统。我们代码库中的所有其他操作都涉及一个或两个锁队列。

与每个锁定队列有一个闩锁不同，我们使用一种略有不同的方法。我们将固定数量的“分片”放入锁队列中，每个分片都有自己的闩锁。（这样实现的技术原因是，“锁队列”在InnoDB代码中并不存在。这个概念是一个有用的谎言，我已经用来解释锁系统试图实现的目标，并且您可能会在我们的代码中找到注释，因为它是真实存在的。但是实际的实现是锁位于哈希表中，每个存储区有一个双链接的锁结构列表，其中哈希是根据资源的<space_id，page_no>计算的。这意味着碰巧被哈希到同一存储区的许多不同资源的“锁队列”被混合在一起成为一个列表。这使得将任何内容与“锁队列”相关联是不切实际和无益的。相反，我们可以尝试将某些内容与“哈希表存储区”相关联，这几乎就是我们要做的，我们只是添加了一个额外的步骤modulo 512以固定“分片”的数量，并独立于您可以在运行时配置的哈希表存储区的数量。共有3个哈希表：用于记录锁，用于谓词锁和表锁，最后一个使用锁定表的ID进行哈希处理，并使用其自己的单独512分片进行闩锁）

我已经谈论了很多涉及一个队列的操作，但是没有涉及必须在两个队列之间移动锁的情况。当一个页面被重组由于B-树分裂或合并,或当一个记录被删除(随后清除),这样“点轴”消失,因此锁必须“继承”产生的差距(当一个新的点分裂差距产生对称问题)。我们已经看到，如果您没有预先计划以某种商定的顺序请求这两种资源，那么请求访问它们很容易导致死锁。因此，InnoDB总是按照升序闩锁分片。

即使我们消除了所有需要非本地访问锁系统的地方，仍有一些地方需要“阻止整个系统”。如果死锁真的发生了，那么我们必须暂时闩锁整个锁系统，以确保没有事务手动回滚的竞争条件等。还有其他这样的地方，主要是在报告中，为了给用户一个一致的描述情况，我们必须停止整个系统。(我们将来也可能消除它们- -也许对这种情况还有其他实际有用的看法，它们并不具有全局一致性。例如:我们可以确保每个单独的锁队列的内容在内部是一致的，但是允许不同的队列在不同的时间抓取快照)。

闩锁整个锁系统的一种方法是简单地锁定所有分片（按升序）。实际上，获取1024个闩锁的速度太慢。（对于Release版本来说，这是可以接受的，因为这种情况很少发生，但是Debug版本经常运行自诊断验证功能，这些功能需要闩锁整个锁系统，这使得运行测试的速度令人难以忍受。有两种不同的实现，一种用于测试，另一种用于用户，这就违背了测试的目的，所以我们采用了稍微复杂一点但统一的解决方案)。

我们重复使用了关于表锁和记录锁的文章中提到的想法——我们引入了一个两级的层次结构。新的全局级别允许你闩锁整个锁系统，或者只显示闩锁单个分片的意图。全局闩锁可以独占或共享闩锁模式。如果一个线程需要闩锁整个锁系统，它只需要在独占模式下获取全局闩锁。如果一个线程计划只闩锁单个分片，那么它首先必须在共享模式下获得全局闩锁。大多数时候没有人对闩锁整个锁系统感兴趣，所以在共享模式下获取全局闩锁没有困难……除了ARM64。

您会看到，实现我们的读写闩锁的方式会跟踪当前有多少线程共享对其的访问，这意味着您需要非常频繁地以原子方式递增和递减计数器。在ARM64上，将诸如增量（从内存读取x；加一个；将x写入内存）之类的原子级的读-修改-写操作编译为重试循环，如果另一个线程更改了读和写之间的值，则可能需要重试。这意味着内存总线上的许多往复、线程争用访问高速缓存块，覆盖彼此的尝试等，而不是像成年人一样“简单地”协作。

解决方案是再次使用…分片。我们没有使用一个全局闩锁，而是使用64个。要获取排他权限，线程将以排他模式闩锁它们。为了获得共享权限，线程会随机选择64个实例之一（我们尝试使用线程局部固定值。我们尝试使用cpu-id。似乎随机是一种方法）并且在共享模式下进行闩锁。（在排他模式下闩锁64次仍然比闩锁1024个互斥锁更快）。

使得这一切比最初预期的要困难的另一个因素是，我们的代码中有一些地方从垂直的角度看一组锁，它们需要遍历与给定资源相关的锁，而不是遍历与给定事务相关的锁。您可以想象在二维网格中排列的锁，其中每一行代表一个资源，每个事务都有自己的列。前面介绍的分片技巧使您可以安全地锁住整行，但是，例如，如果要释放提交事务持有的所有锁，该怎么办？

一种方法是简单地锁定整个锁定系统。在我们的测试中，这太慢了。

另一种方法是将闩锁与每个列（事务）相关联，并使用它来保护列。现在，必须格外小心，以确保每当您在给定的行（资源）和列（事务）的交集处“修改”某物时，您都会获得两个锁存器：用于分片和用于事务。确切地算作“修改”是一个困难的话题，但是，如果我们要完全删除或引入一个锁对象，则一定要让事务和相应的队列知道这一点。锁住两件事需要格外小心，以免发生死锁。因此，InnoDB使用一个规则，即在事务闩锁（“列”）之前应使用与队列相关的闩锁（“行”）。原则上，规则可以相反。无论哪种方式，都需要解决一个严重的问题，这是以下两个问题之一

• 如果我必须先锁住包含锁的分片，但我不知道我的事务的分片锁在哪里，因为我不能访问我的事务锁的列表，直到我锁住它，我如何有效地遍历我的事务的所有锁?
• 如果排序所有等待者都要求我先锁定分片，但是授予锁需要锁定作为赢家的事务，那么我如何有效地为事务授予锁呢?

这两个看起来都像是鸡生蛋还是蛋生鸡的问题，不管你选择哪条规则，你总是会遇到至少一个这样的问题:“行”在“列”之前会使第一个变得困难，“列”在“行”之前会使第二个变得困难。

目前InnoDB倾向于“行”先于“列”锁挂，这意味着要解决的问题是“如何遍历事务的所有锁来释放所有的锁?”在这个层次上，我们首先锁定“列”，并对事务锁执行只读扫描，对于每个锁，我们记录它属于哪个分片，暂时释放事务的闩锁，闩锁分片，并重新获取事务的闩锁。在反复检查锁对象没有改变，列表也没有改变之后，我们可以安全地继续保持“列”和“行”闩锁以处理锁。

在此执行的最常见的锁操作是释放它。使用CATS算法释放锁，我们将对锁的队列进行排序（这很安全，因为我们已经锁住了它的分片），并将锁授予一个或多个事务（这需要暂时锁住其事务的“列”，这不违反“列”的规则） ”应该在“行”之后闩锁）。 处理完锁后，我们释放分片的闩锁，然后移至事务列表上的下一个锁。

好奇的读者可能会注意到，在提交一个事务并将锁授予另一个事务时，可能会发生低级死锁，当请求另一个事务的闩锁时，线程已经在第一个事务的“列”上保留了闩锁。到目前为止，我们最喜欢的补救措施是确保某些商定的顺序，并争辩说此类闩锁始终根据此顺序使用。但是，这在我们的情况下不太肯，为什么期望被授予锁的事务具有地址，ID或其他的比我们的大？我们在这里可以使用什么顺序？

最简单，最懒惰的答案是序列化顺序。毕竟，整个锁系统的全部主要目的是提供一个顺序，其中一个事务必须等待另一个事务。这不是一个非常有说服力的证明，不仅似乎假设了这一论点，而且还忽略了以下事实，事务可以使用较低的隔离级别，创建死锁周期（本质上是序列化顺序中的周期），然后回滚。但是，这指明了正确的方向，即使它可能是很难描述跨越时间所有事务中的一个黄金的顺序，我们可以使用当前第一个事务没有等待而另一个事务正在等待的事实来证明一个循环是不可能的，因为所有边都从活动事务到等待事务，在相反的方向上没有边。(对更严格的证明感兴趣的读者，可以参考源代码注释中的证明，例如:使用“当前”这个词到底是什么意思??你说的“等待”是什么意思?或者我最喜欢的，从哪个线程的角度看内存状态??)

有关性能提升的主张应以图表为依据，所以让我分享其中的一些内容。我们要解决的原始问题之一是2-Socket服务器上的可伸缩性问题，其中单个全局lock_sys-> mutex上的同步跨套接字进行协调非常昂贵，成为瓶颈，您只需禁用其中一个套接字上的CPU，就可以每秒获得更多事务。因此，这项工作最重要的基准之一是提高数据库的sysbench OLTP-RW工作负载的性能，该数据库有8个表，每个表有10M记录，查询会影响通过Pareto分布（左列）或统一（右列）随机选择的行），来自大型2插槽计算机上的128个客户端（顶部行）或1024个客户端（底部行），这些驱动器具有非常快的驱动器和大量的RAM，因此我们可以专注于CPU问题。

您可以看到每秒的事务数（条形图的高度）在我们引入了新的CATS实现时有所增加，然后又在其上引入了lock_sys-> mutex的分片时又增加了。条形图上的白色百分比是贝叶斯（Bayesian）估计的可信度，即由于源代码的更改导致TPS至少提高了1％（如果您不信任自己的眼睛，我们将在5分钟的时间里对每个组合进行5分钟的实验，并进行1分钟的预热））。

这是使用功能强大的dim_STAT工具获取的更细粒度的Pareto分布图，它显示了更改的影响（左=未修改的基准中继线，中=新CATS算法，右=在新CATS顶部锁定Sys分片）各种互斥量（上部）的拥塞以及当我们以指数方式改变连接数时，它如何转换为TPS：1、2、4、8、16、32、64、128、256、512、1024。

您可以看到新的CATS算法已经降低了lock_sys-> mutex的拥塞，并且新的分片彻底消除了互斥锁，将其替换为许多lock_sys_page互斥锁分片（在图表中不易看到总拥塞）和许多分片。的lock_sys_table互斥对象，甚至没有进入前7名。您还可以看到TPS下降到128个以上，以及消除lock_sys- > mutex如何使下降变得不那么引人注目，这使我们有了终极武器来战斗：trx_sys- > mutex。让我向您保证，这场战斗也一定会赢。