转载自：https://www.sohu.com/a/203933205_487483?sec=wd&spm=smpc.author.fd-d.2.1557386676880JSjtJwV
好多同学后台留言说姜老师最近技术文章写得少，主要原因是换了新工作之后正在熟悉相关业务，调整数据库架构，MGR调研、测试与上线等。此外还有神秘的金融云项目，目前雏形已完成，感觉市面上所有云都要哭晕在厕所啦~~~
最近一直在跟进MySQL 8.0，周末发现InnoDB团队老大Sunny Bains发文的Contention-Aware Transaction Scheduling Arriving in InnoDB to Boost Performance[1]，倏地感觉眼前一亮，并水藤摸瓜地继续看了几篇论文[2]，[3]，很是有收获。
CATS
————
Contention-Aware Transaction Scheduling，基于竞争感知的事务调度（下简称CATS），是MySQL 8.0.3版本默认的事务调度算法。之前事务的调度算法可视为FCFS（first come first serve）。简单来说，就是先到的事务先获得锁，如果发生等待则根据FIFO算法进行排队。这个算法看似非常公平，且沿用非常之久。
然而，FCFS并不能算是公平的算法。因为FCFS公平的前提是假设每个事务持有的锁数量是一样的，实际上这是不可能的。一个系统中总有不同的业务和事务处理。在金融支付这块，设计的原则之一就是快慢分离，即快事务不要被慢事务挡住。这通常需要业务进行控制，因为数据库层无法感知事务的优先级。
CATS是一种通过排序事务阻塞其他事务的数量来判断当前事务重要性的算法，重要性高的事务需要提前获得锁。从感觉上看，还是比较合理的。当然论文中会有相关推到和论证。
上图中，事务t2虽然依赖了5个对象的锁，但仅有3个事务在等待。而事务t2持有的锁少，但却有4个事务在等待t1。因此，在CATS算法下，锁将会授予事务t1。论文[3]中指出MySQL 8.0.3中使用的算法是LDSF（Largest-Dependency-Set-First)，他们新提出的算法bLDSF（batched LargestDependency-Set-First）还能有进一步的性能提升。
同时论文[3]也指出CATS和原有的FCFS算法的时间复杂度都是为O（N*N），因此在调度上并不会有性能损失。
性能
————
大家最关心的还是性能问题。论文[3]中的测试场景最为丰富，下面仅罗列TPC-C场景的结果：
可以看到在TPC-C大并发量场景下，原来的FIFO性能退化非常严重，然而bLDSF算法却依然能保持较高的性能水准。MySQL官方也做了相关测试，采用了sysbench OLTP pareto分布，性能也能有较大的提升，在512线程下性能有5倍的差距：
TPC-C、Sysbench都是现成的工具，感兴趣的小伙伴可以测试下，复现测试结果应该并不难。不过到最后的测试结果，我的疑问却停留在了如果使用线程池，那么高并发不就不会有性能下降了嘛？那这时CATS的提升或者帮助还能有多少呢？
源码
————
[4]是原作者在MySQL 5.7版本中添加CATS的分支，patch代码没有超过1000行，感觉还是可以理解的，主要逻辑集中在函数vats_grant。[5]是官方建的工作日志，对具体实现感兴趣的同学可以继续研究。
最后，我感觉这篇论文给我打开了很多新的思考空间，数据库内核层可以做的事情除了Paxos，其实还可以有很多。