原文地址：https://mysqlserverteam.com/contention-aware-transaction-scheduling-arriving-in-innodb-to-boost-performance/
原文作者： Sunny Bains, Jiamin Huang (University of Michigan)
译者：沈刚
什么是事务调度？
目前大多数的数据库系统都是通过锁的方式来控制并发的情况。但是对于很多数据库厂商来说，都会有一个问题:
当有多个事务同时需要获取同一把锁，那么哪个事务应该最先获得这把锁？
包括之前版本的MySQL在内，几乎所有的数据库都是通过FIFO机制来解决这个问题。简单来说，FIFO机制就是将锁分配给最先请求该锁的事务（即该事务在等待队列的最前面，除非它们与当前锁赋予的锁不兼容）。因为这种机制是实现起来简单，所以很多的数据库厂商都是通过FIFO的策略进行事务调度，没有考虑其他的调度策略。
最近一个密歇根大学的研究组织提出，这个问题背后隐藏着巨大的性能提升空间。Mozafari教授和他的学生证明了不同的锁分配策略以及事务调度策略对于数据库性能有着很大的影响。他们提出了一种称之为Contention-Aware Transaction Scheduling(CATS)的算法，使用这种算法进行事务调度相较于之前的FIFO策略，显著地减少了数据库延迟，提高了吞吐量。
Oracle MySQL官方团队和Mozafari教授以及他的学生们紧密合作，使得MySQL是第一个采用这种新技术的数据库。在MySQL 8.0.3版本之后，CATS策略作为InnoDB的默认调度算法，也就是说MySQL的使用者可以感觉到显著的性能提升，尤其是在持续高压力负载的情况下。
CATS机制原理
CATS算法是基于很简单的一个观点：不是所有的事务都是平等的，不是所有的对象都是平等的。当一个事务已经持有了多个对象的锁，当该事务请求一个新的锁的时候，该事务应该被优先分配。从另一个方面讲，解锁这样的事务有助于解锁更多的事务。因为该事务优先被分配锁能更快的结束事务，释放另外已经获取到的对象的锁。通过这种方式可以使数据库获得更高的吞吐和更低的延迟。
有一个比喻的例子：如果有一个出租车司机和一个公交车司机都在等咖啡，那么先给公交车司机做咖啡（即使公交车司机比出租车司机迟来）可能会让更多的人尽早到达他们的目的地。因为公交车上的乘客比出租车上的乘客多。这看起来似乎对出租车司机不公平，但是这种策略可以使得整个系统运行的更快，这对于系统内的每个人都是有利的。
当然，我们现在是在解决锁的问题而不是交通司机的问题。让我们通过一个简单的例子来阐述一下CATS机制在数据库中是如何工作的。我们知道在不同的事务隔离级别下，事务在读取或者更新数据的时候，需要先获取对应数据的锁。当一个事务所需要的锁已经被其他事务所持有了，那么这个事务会一直等待直到其他事务释放这个锁。当事务已经持有一部分对象锁的时候，可能会在获取其他对象的锁的时候一直被阻塞住，这个时候就需要死锁检测机制来检测当前数据库中没有锁等待循环，防止死锁。来看下面这张图：
Transaction contention
在这种场景下，FIFO策略很简单，只需要考虑那个事务先请求O1对象的锁。但是CATS算法会更加智能地处理这个情况：CATS算法会计算每个事务直接阻塞和间接阻塞的事务数量，然后将O1对象的锁分配给阻塞了更多事务的事务。在这个场景下，t1事务阻塞了4个事务，t2事务阻塞了3个事务。所以根据CATS算法会将O1对象的锁分配给t1事务。这样可以将更多的事务释放出来，这样有利于提高系统整体的性能。
对于共享锁（S锁），CATS算法会尽可能多的分配共享锁。在这方面FIFO和CATS算法有不同的地方。FIFO按照队列的先后顺序分配共享锁，当遇到分配的对象上已经有排他锁（X锁）了，则停止分配。而在CATS中，按照事务阻塞的事务数进行倒序排序，然后按照这个顺序进行锁分配。
CATS机制带来的性能提升
Oracle的Dimitri Kravtchuk通过Sysbench 的OLTP脚本测试这种新的算法。通过结果显示，在并发情况下，CATS算法比FIFO算法在TPS，平均延迟，95%延迟等指标方面都有显著的性能提升。有趣的是，即使在没有并发的情况下，CATS算法的性能和FIFO算法性能是一样的。那是因为在没有并发的时候，没有事务需要进行调度，所以也就没有性能的差异。换而言之，使用CATS算法替换FIFO算法，没有任何损失，反而在数据库繁忙的时候，有很大的性能提升。
CATS vs. FIFO in TPS, mean latency and 95th percentile (up to 5.05x improvement)
结论
MySQL是全球第一个使用这种最先进的CATS事务调度算法的数据库。这个算法解决了数据库在遇到高压力情况下性能急剧下降的问题，这个也是MySQL 8.0主要想要达到的目标。
CATS算法是针对当事务并发超过32的情况，这个数值没有参数配置，是通过经验设置的。
博客地址：https://win-man.github.io/
公众号：欢迎关注