在并发控制和事务系统中，锁管理器是研究最多的组件之一。尽管对事务处理的各方面进行了数十年的研究，锁调度好像没有被注意到，以至于面对如下重要问题：“当同一个对象上有多个锁定请求时，应该首先授予哪一个？”几乎现有的数据库系统都给出FIFO（First In， First Out）策略来决定授予锁给哪些事务。本文引用VLDB 2018一篇题为“Contention-Aware Lock Scheduling for Transactional Databases”的论文（下称论文）对上述问题进行分析和解答。论文提出的方法已经作为MySQL8.0.3后默认的锁调度算法，具有相当的实用性。
锁是一组共享对象被多个事务（或应用程序）并发访问时确保一致性最常用机制。在一个封锁系统中，主要存在两种锁类型（数据库系统中还有意向锁）：共享锁和独占锁。在事务可以读取一个对象（例如一个元组）之前，它必须首先获取该对象上的共享锁（又名读锁），锁住该对象。同样，在事务请求写入或更新对象之前，它必须获取该对象上的排他锁（也称为写锁）。只要该对象上不存在排他锁，系统就可以授予共享锁的封锁请求。然而，只有对象上在没有其它锁的情况下才可以满足该对象上的排他锁封锁请求。当事务不能立即获取被访问对象上的锁，它进入阻塞状态，直至满足上述规则，系统唤醒该事务，授予事务相应的锁。这里就产生了一个最基本的问题：当多个事务竞争某个对象上的锁，一旦该锁可用，哪个事务应该优先获取锁？这个问题，称之为锁调度。尽管已有很多工作关注并发控制和封锁协议，但令人惊讶的是很少有人关注锁调度问题。此外，虽然已有相当多研究聚焦在实时系统的调度问题上，这些工作都有一个假设前提就是，当负载请求到达系统的时候它们的执行时间是已知的或者是有明确的执行时间限制。锁调度的如下几个特点使得这是一个独特的挑战性问题，特别是考虑到现实世界数据库系统的性能。- 在线问题。当一个事务被授予锁的时候，系统并不知道该事务何时才会释放锁。因为事务的执行时间只有事务结束的时候才知道。
- 错综复杂的依赖。在DBMS中存在依赖关系。当一个事务正在等待由另外一个并发事务持有的锁，这就形成依赖关系。在实践中，这些依赖关系可以相当复杂，因为每个事务都可以持有多个对象上的锁以及多个事务可以持有同一个对象的共享锁。
- 非一致访问模式。数据库中的对象并非具有同等的热度。此外，不同的事务有不同的访问模式。
- 多种锁模式。将对象上的排他锁授予给一个写事务或者将共享锁授予给多个读事务是问题复杂的根源。
针对上述问题特点，本文就论文提出的竞争感知的锁调度算法进行阐述和分析。论文约定系统遵循严格两阶段锁定（strict 2PL）协议：一旦系统授予事务相应的锁，它会一直持有该锁，直至事务结束为止。一旦事务完成执行（即它提交或被中止），它释放持有的所有锁。
锁调度问题就是在如下两个事件发生的时候，确定哪个事务获得锁：
给定系统中某个时刻的事务集合T以及数据库全体对象O, 本文定义系统依赖图为带有边标签信息的图G = (V, E, L)。其中，图的顶点V为集合T∪O，由事务与数据库对象组成；图的边E定义为：E⊆T × O∪O × T，描述了事务与对象之间的封锁关系。特别地，对于事务t ⊆ T, 对象o ⊆ O，- L(t, o) = X, 意味着事务t等待对象o上的排他锁
- L(t, o) = S, 意味着事务t等待对象o上的共享锁
- L(o, t) = X, 意味着事务t持有对象o上的排他锁
- L(o, t) = S, 意味着事务t持有对象o上的共享锁
在死锁检测模块的保证下，图G是一个有向无环图(Directed Acyclic Graph, DAG)。假定Ⓖ为系统所有DAG的集合。锁调度问题可以归结为上述两个事件对应的函数对A = (Areq, Arel)：Ⓖ × O × T × {S, X} → 2^T。例如，给定系统依赖图 G，当事务t请求对象o上的排他锁，Areq(G, o, t, X) 确定当前正在等待o上的锁请求(包括t本身)的哪个事务应该被调度。同理，给定系统依赖图 G，当事务t释放对象o上的共享锁，Arel(G, o, t, S) 确定当前正在等待o上的封锁请求(包括t本身)的哪些事务应该被调度。注意到，根据上述DAG定义，除事务之外，事务请求的锁定类型以及锁竞争的激烈程度也在 G 中被捕获。据此论文定义竞争感知的锁调度算法为一类算法，可以根据对系统整体竞争的影响来确定事务的优先级。论文探讨了若干机制来实现竞争感知的锁调度算法。第一种是简单根据事务持有锁的数量推断该事务更有可能阻塞其他事务的运行，因而具有更高的优先级（Most Lock First，MLF）。如图1所示，事务t1相较于事务t2具有更高的优先机，前者持有4个锁而后者只持有两个锁。但是这种方法忽略了热点问题，事务可能持有冷数据上的大量的锁，但是对系统运行不会产生实质性的影响。一个启发式策略是纳入考虑范围的必须是存在等待事务的锁(Most Blocking Lock First，MBLF）。
依据该准则，图1中事务t2较事务t1具有更高的优先级，因为t2拥有两个被等待的锁，而t1只有一个。这个方法也存在不足，即不论这个锁有多少个竞争事务等同视为只有一个等待事务。图2展示了这个方法的不足。
按照MBLF的标准，阻塞了两个事务运行的事务t2应该先于t1被调度。虽然t1只有一个等待事务t3，但是t3自身阻塞了其他另外三个事务的运行。先调度t2运行的MBLF策略有可能阻塞系统更长的时间。
一个更为复杂的策略是将事务依赖子图的深度纳入考虑，称之为最深依赖子图优先(Deepest Dependency First, DDF). 这个思想的背后是具有更长路径的子图有可能阻塞更多的事务。如图3所示，事务t1的子图深度是3，而事务t2的事务是2。因此t1具有更高的优先级。
这种方法也有弊端，也就是只是从纵深角度考虑热点锁，缺乏系统运行总体概况。鉴于上述算法的不足，论文提出了最大依赖集优先的算法(Largest Dependency Set First, LDSF)。它为平均延迟的期望提供了形式化保证。
给定系统两个事务t1, t2, 如果在有向无环图中存在从t1到t2的一条路径，称t1依赖于t2。定义事务t的依赖集g(t)为所有依赖于t的事务集合。LDSF算法使用不同事务的依赖集的大小确定优先调度哪个（哪些）事务执行。例如，在图4，事务 t1（包括 t1 本身）的依赖集大小为5，而事务t2的依赖集为4。因此，在某种情况下t1和t2都请求对象 o1上的独占锁，LDSF将尽快将锁授予 t1（而不是 t2）。LDFS将对象o上的所有请求共享锁的事务视为同一个事务。因此对象o上的请求共享锁的事务依赖集为该对象上所有请求共享锁事务的依赖集的并集。锁调度算法在请求排他锁的事务中挑选依赖集最大的事务，然后与请求共享锁的事务的依赖集相比较，挑选依赖集较大的事务执行。如果是授予共享锁，则所有等待共享锁的事务获得锁。在系统中只有排他锁的情况下，LDSF在衡量平均延迟期望方面是最优算法。这背后的直观思维是，如果事务 t1 是依赖于t2 上，则t2 的任何执行进度也可以被视为 t1的进度，因为 t1 无法获取其请求的锁，除非t2执行完毕。
因此，通过向具有最大依赖集的事务授予锁，LDSF允许最多事务都向前推进，直至完成。
但是在存在共享锁的情况，上述情况不一定为真。即使事务t1依赖于t2，但是t2的执行不一定会对t1的进度有影响。例如，如图5所示，t1依赖于t2，t3，但是t2的执行不一定会对t1的进度产生影响，除非并发事务t3在t2之前释放其持有的共享锁。如前所述，LDSF会将共享锁授予所有等待该锁的事务。然而这并不是一个最优策略。一般来说，在同一对象上授予大量共享锁增加了长事务出现的可能性。在长事务释放其锁之前，没有独占锁可以被授予在该对象上。换句话说，最慢的事务持有共享锁的期望时长会随着事务数量的增加而增加。这就是著名的straggler问题，它随着并发进程/线程的增加而加剧。既然向更多事务授予共享锁可能延迟独占锁请求，因此很容易想到，仅授予共享锁给等待事务的子集可能会减少系统的整体延迟。基于上述考虑，论文提出一种bLDSF（batch LDSF）算法，仅仅将共享锁授予给对象o上的共享锁请求的子集。引入延迟因子f(k), 它表示单独向每个事务授予锁相比（系统中正在运行事务的剩余时间作为随机变量，取其数学期望），向 k 个一批事务一起授予共享锁时（k个事务剩余运行时间这个随机变量最大值的数学期望）产生的速度比值。f(k) 量化了释放 k 个一批事务（对比 1 个事务）持有的共享锁平均需要多长时间。在独立同分布的事务剩余执行时间的随机变量上的延迟因子f(k)满足：
图6给出了bLDSF算法的演示。假定f(2) = 1.5, f(3) = 2,如果批量将共享锁授予事务t1, t2, t3, 则t4的等待时间为2R(R为事务运行时间的平均延迟）,因此事务t4依赖集的总等待时间为10R（5 × 2R）；如果锁授予顺序为t1, t4, (t2, t3),则总等待时间为5R + 2 * 2R。与LDSF算法不同，bLDSF 需要延迟因子进行分析。然而，由于事务运行的剩余时间可以建模为随机变量，确切的延迟因子 f(k) 的函数形式也将取决于这些随机变量的分布。
从MySQL8.0.3开始，锁调度算法已经默认更换为bLDSF。具体来说，对象上所有挂起的锁定请求都被放置在队列中。锁请求仅当满足以下条件之一时，才会在事务到达后立即授予。- 请求的锁类型与当前该对象上的所有锁兼容，并且前面没有不兼容的请求在等待队列中。
类似地，每当对象上的锁被释放时，MySQL的锁管理器从头开始扫描整个队列。只要上述条件成立，它将调度任何锁请求的事务。一旦调度程序遇到第一个无法被授予的锁请求，它就会停止扫描队列的其余部分。实现 LDSF 和 bLDSF 的一个挑战是跟踪事务依赖集的大小。实际的实现中，并不需要事务依赖集大小的准确值，近似值即可满足要求, |g(t)| = ∑|g(t′)| + 1, 其中t′为t的依赖集中的事务。另一个实现的挑战在于 bLDSF 需要找到满足要求的一批事务。算法首先对事务的依赖集大小按降序排序，然后令k=1,2,3,...寻找|g(t)|/f(k)的最大值q。然后确定调度的锁类型。实验对比了上述启发式算法、FIFO以及VAST算法（Variance-Aware Transaction Scheduling,当有多个事务等待获取同一个数据对象的锁时,它会优先让等待时间最长的事务获取锁,而不是简单的先到先得）。论文在Intel(R) Xeon(R) E5-2450 16核 CPU，配置缓存为5GB的环境上进行测试。测试数据集是TPCC以及作者自定义的microbench。这里给出若干测试结果（详细测试结果参考论文）。
在吞吐量上，当有100 个连接时，bLDSF 的性能仅优于 FIFO1.4 倍，VATS 1.1 倍。然而，在900 个客户端连接时，bLDSF的吞吐量比FIFO 高 6.5 倍，比VATS高 2 倍。如图 9 所示，bLDSF 算法显著优于 FIFO倍和 VATS,性能提升分别是300倍和80倍。论文还在图10中报告了P99延迟。bLDSF 的性能比 FIFO 高出 190 倍。有趣的是，bLDSF的表现也优于 VATS（高达16 倍），尽管后者是专门为减少尾延迟而设计的。这是因为对于所有事务平均而言，bLDSF算法能使得它们以更快的速度完成。因此，事务在队列末尾的等待的时间也会更少，从而达到更低的尾延迟。论文也在吞吐量和延迟等因素对比了其他的启发式算法，具体见图11~图16。
数据库系统社区对锁管理器的研究在多核处理器时代主要聚焦在降低临界区资源的竞争。
例如被PostgreSQL采用的锁继承技术就属于第一类。竞争感知的封锁技术从全局考虑，目标是以最快的速度推进系统中运行的事务，具有很好的理论与实用性。该算法目前已经作为MySQL 8.0.3后默认的锁调度算法，有兴趣的读者可以进一步研究代码实现。最后作为一个思考题，为什么论文没有将意向锁考虑进来？欢迎大家一起研究探讨。
论文：《Contention-Aware Lock Scheduling for Transactional Databases》https://doc.kunlunbase.com/zh/Klustron_Instruction_Manual.htmlhttps://doc.kunlunbase.com/zh/Klustron_Quickly_Guide.htmlhttps://doc.kunlunbase.com/zh/Klustron-function-experience-example.htmlhttps://doc.kunlunbase.com/zh/product-usage-and-evaluation-guidelines.html同时欢迎大家扫码👇添加小助手（备注：加入Klustron技术交流群）欢迎大家在交流群共同探讨更多问题及主题。
