MySQL 8.0 竞争感知的事务调度(CATS)

一、事务调度

在数据库系统中，锁是最常用的并发控制方法，当多个事务在同一个对象上等待锁时，哪个事务，或者哪些事务应当最先获得锁？

大多数系统使用First-In-First-Out (FIFO)策略及其变种，简单来说，FIFO策略就是在队列前面的事务，按照请求锁的先后顺序来授予锁，除非它们与当前授予的锁不兼容。因为这种策略简单，易于实现，被很多数据库系统采用。

密歇根大学的一个研究小组指出，事务调度这个看似简单的问题背后，隐藏着一个提高性能的绝佳机会。Mozafari教授和他的博士生表示，锁调度的不同方法对事务数据库的总体性能有着重要的影响。他们发明了一个新的算法，基于竞争感知的事务调度算法，Contention-Aware Transaction Scheduling (CATS)。与FIFO算法相比，它可以显著地减少延迟和提高吞吐量。

Oracle的MySQL团队与CATS算法的发明者紧密合作，使MySQL成为第一个集成该新技术的数据库。从8.0.3版本开始，CATS成为InnoDB事务调度的默认算法，所有使用MySQL 8.0.3及之后版本的用户，将能体验到MySQL性能的显著提升，特别是对于有锁竞争的场景。

二、CATS算法原理

CATS算法基于一个简单的观点，不是所有的事务都相等，也不是所有的对象都相等。当一个事务已经在许多对象上拥有锁时，它在请求一个新锁时应该获得优先权。换句话说，解除阻塞这样的事务将间接地有助于解除阻塞系统中更多的事务，总体上，这意味着更高的吞吐量和更低的延迟。

举一个例子，如果一个出租车司机和一个公交车司机排队等咖啡，先给公交车司机煮咖啡（即使他是在出租车司机之后到达的），会让更多的人更快到达目的地，因为公交车上的乘客比出租车上的乘客多。虽然这对出租车司机来说似乎不公平，但由于数据库系统中复杂的相互依赖关系，这种策略会使整个系统变得更快，以至于每个人，甚至出租车里面的人，都会受益于更有效的服务。

当然，我们处理的是锁和交易，而不是繁忙的交通工具，让我们用一个例子来说明CATS在数据库世界中是如何工作的。我们知道，根据事务隔离级别，在读取或更新每个数据对象之前，事务必须获取它的锁。如果该对象上已经持有不兼容的锁（例如由其他事务持有），则当前事务将被阻塞，直到这些锁被释放为止。已经锁定此对象的事务本身可能会在其他对象上被阻塞（死锁检测/预防机制将确保此处没有循环）。

FIFO策略只需查看哪个事务首先请求对象锁就可以做出决定。CATS算法做这个决定时更加聪明，它计算每个事务（直接或间接）阻塞的事务总数，并将锁授予阻塞更多事务的事务，这将使更多的事务能够更快地被解除阻塞，从而使系统更快更高效。

对于共享锁，CATS将尝试授予尽可能多的事务。FIFO和CATS的区别在于，FIFO在遇到独占锁时会根据到达时间停止授予锁，而CATS则按照它们所阻塞的事务数的降序对事务进行排序。

三、CATS算法性能提升

通过测试，对比CATS与FIFO算法性能，测试结果表明，在有锁竞争的场景中，CATS算法相对于FIFO算法有显著的性能提升。没有锁竞争的场景，CATS算法与FIFO算法性能基本一致。这是因为当没有争用时，就没有调度决策要做，即每个锁最多有一个事务在等待。换句话说，用CATS代替FIFO，你不会有任何损失，但是一旦系统中出现竞争，使用CATS，你将会受益很多。

四、CATS算法饥饿等待问题

出租车与公交车等咖啡问题，如果公交车源源不断地到来，将会出现出租车一直等不到咖啡的情况，也就是所谓的饥饿问题。

针对该问题，CATS算法研究小组回应，事务刚开始时，都是出租车，随着时间的推移，获取了更多锁之后，就变成了公交车。或者可以这样理解，没有出租车的概念，大家统一都是公交车，区别在于公交车里面乘客多少的问题，这里乘客相当于锁，每个公交车（事务）初始状态都是空的，没有乘客（锁），随着时间的推移，公交车里乘客（锁）渐渐多了起来。

但是理论上，在一些罕见的情况下，饥饿情况是可能出现的。因此MySQL在实现CATS算法时增加了一些额外的机制，比如跟踪事务长时间的锁等待，然后提升其优先级。或者不时地在锁等待队列中放置一个分界线，并确保分界线之前的事务优先被授予锁。这些机制将在MySQL 8.0.3 之后的版本中引入。

五、总结

MySQL是世界上最早采用这种最先进的事务调度技术的数据库之一，Contention-Aware Transaction Scheduling (CATS)这种算法解决了当数据库系统负载增加时所面临的性能急剧下降的问题，这也是MySQL 8.0要解决的主要问题之一。

当等待的事务数超过32个时，CATS就会启动，CAST目前没有配置选项，经实验测试检验，选择32。