【论文解读】OLTP 数据库引擎性能优化

● 论文一的研究对象是纯内存计算的 OLTP 引擎，作者通过引入 C++ 20 的 coroutine 特性将 thread-to-transaction 的执行模型修改为两级 coroutine-to-transaction，在不需要内部接口改动的条件下实现了事务间的 batch 机制和基于协程的 prefetch，减少了后续计算的 cache miss，提升了事务的整体执行性能。

● 论文二在论文一的基础上，研究对象从纯内存计算的 OLTP 引擎扩展为更通用的内存计算和存储 IO 访问混合的 OLTP 引擎，更完整的讨论了数据库引擎可能在哪些环节产生性能问题（重点关注端到端的吞吐和延迟）：包括 CPU 的 cache miss、存储 IO、操作系统调度、数据同步等等。论文沿用 coroutine-to-transaction 的执行模型，通过控制线程数量、灵活的 coroutine 策略（可选择性的协程嵌套、存储感知的调度策略、流水线式的调度）在不同的场景实现 latency hiding ，以达到系统整体吞吐的提升。

纯内存计算场景

OLTP引擎

论文一所讨论的问题非常明确，即在一个纯内存计算的 OLTP 场景下，需要提高事务间的并发能力，减少访存的 cache miss。论文首先抽象了三种数据访问模型，分别是线性模型、Multi-Get 和论文的 coroutine 模型，三种模型如下图所示。图示中 T1 和 T2 代表两个事务（各自运行在独立协程），虚线方块代表等待数据从内存加载到 cpu cache，实线方块代表在 CPU 内计算。显而易见，线性模型事务间无法并发计算，CPU 利用率最低；Multi-Get 模型需要调整数据获取接口，通过 batch 的方式可以实现一定程度的事务间并发；coroutine 模型则是通过 prefetch 和 suspend/resume 的机制，当协程 T1 要通过指针访问数据时，它可以向 CPU 发起 prefetch 指令让 CPU 把这块数据从内存加载到 cache 中，因为加载数据需要时间，在这个协程发完 prefetch 指令后将当前协程挂起，不再占用 CPU，让 CPU 继续执行其他数据已经在 cache 中的协程的计算任务，这样数据加载和计算完全并行起来，cache miss 减少，达到整体执行性能的提升。

在这篇论文之前，已经有不少利用协程的 software prefetch 机制，提升CPU利用率和事务的执行性能的研究，包括论文 《Improving Hash Join Performance through Prefetching》提出的group prefetching和pipelined prefetching，论文《Asynchronous Memory Access Chaining》提出的AMAC。已有的研究成果存在两个问题：一是没有研究 prefetch 机制对整个数据库引擎端到端的性能影响；二是需要对数据存取接口进行修改，会引入编码复杂度和兼容性问题。这篇论文则是通过引入 C++ 20 的 coroutine 机制，解决了这两个问题。针对问题二，论文提出了两级协程模型（two-level coroutine-to-transaction），其本质是平衡了在事务执行引擎内各模块复杂函数调用的嵌套和修改执行引擎、拍平调用嵌套所引入的编码复杂度和减少协程切换提升性能。简而言之，因为需要在加载数据的代码处引入 CPU 的 prefetch 和协程的 suspend，数据库执行引擎内可能有复杂的模块抽象和调用依赖，形成复杂的协程嵌套。如果把这种嵌套完全拍扁为线性的 prefetch 和 suspend，会让问题二从 multi-get 接口的改写问题转变成函数调用层级拍平问题，并没有解决编码层面的复杂度。为了解决此问题，论文提出的两级协程模型，第一级协程作为事务执行的调度函数，在协程内管理事务处理的所有过程，调用其他函数或协程完成事务的最终执行。第二级协程用来优化某个步骤中所有可能发生 cache miss 的地方，所有需要改成 coroutine 的函数都通过 inline 的方式将协程调用转换为函数调用，在同一个 coroutine 中执行。这里需要注意，论文的设计并不意味着不需要代码的改动，适当的 flatten 是必须的，其优点是保留了执行引擎内的函数模块化。

对于端到端的性能影响，则体现在论文一的测试场景，论文里覆盖了比较常见的数据库性能测试场景，包括 YCSB、TPC-C、TPC-CR 和 TPC-CH，关注的性能指标是在不同控制变量情况下系统端到端的吞吐和请求延迟。

内存计算和存储IO

混合场景

在现代数据库的使用场景下，适用于纯内存计算的数据规模非常具有局限性，很多时候数据库引擎需要同时处理可以常驻内存的数据和常驻在存储介质的数据。论文二在论文一的基础上，进一步讨论了内存计算和存储 IO 混合使用的场景。该篇论文将延迟优化分为了几个细分的方向，包括内存访问和存储IO 延迟；操作系统过载和调度延迟；以及同步机制引入的延迟。每一种延迟场景论文给出了如下的解释：

● 指针数据访问：一个具体的例子是 B+ 树使用指针访问数据，从根节点到叶子结点的访问是一种随机内存访问，并不利于硬件的预取和分支预测；另一个例子是多版本数据链表的随机访问，也是缓存不友好的。

● 同步机制：论文中指对同一个内存地址访问的并发保护机制，比如使用 spinlock 或者 mutex 等。锁竞争可能会引入过多的 CPU 消耗。

● 存储 IO：显而易见访问存储的数据延迟远大于访问内存数据。另一方面，尽管有一些系统引入专用 IO 线程，比如在 MySQL 内有异步 IO，对于存储数据的预取仍然是难以判断的；同时专用 IO 引入了线程间通信，这部分通信有可能引入过度的资源消耗并产生新的延迟。

● 资源过载和操作系统调用：当创建的操作系统线程过多时，操作系统线程切换的 CPU 消耗可能会引入性能问题。另一方面一些后台专用线程也会和事务工作线程争用 CPU。

● 其他：论文里提到一些其他的产生延迟的原因，比如逻辑时钟竞争，分布式系统下的网络延迟等等。

在给出多种延迟来源后，论文二限定了所解决问题的场景为单节点，适配双路或四路 CPU 架构进行过内存优化的数据库服务。分布式架构的数据库和更大规模 CPU 插槽和核数的场景不在这篇论文的讨论范畴内。论文二在论文一实验项目 Corobase 的基础上，进一步实现了项目 MosaicDB。MosaicDB 确保系统内线程和操作系统核心数严格相等，每个线程对应于一个 worker，在工作线程内使用 coroutine-to-transaction 模式处理事务。整个系统的工作架构如下图所示：

具体解释一下工作线程内的处理流程：

step-1：工作线程每次接收一批事务请求。

step-2：对每个事务创建相应的协程处理，根据数据访问的不同情况进行选择：如果需要访问存储数据，suspend 当前协程，跳转到步骤3；如果是访问内存中数据，使用 prefetch 指令后 suspend 等待数据加载到 cpu cache。而具体的数据访问是通过指针->索引->查询数组（多版本链）的访问模式。

step-3：通过异步 IO 获取数据。

step-4 & step-5：协程 suspend 后交还 CPU 给调度器。

step-6：调度器创建协程处理其他事务，或者恢复某一个已经 suspend 的事务。

在以上系统架构的基础上，论文二提出了如下的优化点：

1. Coroutine 嵌套的优化：保留论文一内存热数据访问的二级 coroutine-to-transaction 模式，对涉及存储访问的函数保留嵌套协程。论文给出选择该种策略的两点理由：1）如果对存储访问函数也解嵌套，会引入复杂代码，也不利于代码指令缓存（这个理由我觉得不够充分，论文并没有解释的清楚为什么拍平内存访问函数没有这个问题）；2）相比于内存延迟，存储访问延迟的数量级更高，在进行 IO 请求时需要尽可能减少协程切换到 IO 等待协程的频率（我觉得这一点是更主要的原因，也更合理）。

2. 存储感知的调度策略：该策略是策略1的延续，因为需要检查异步 IO 是否结束以接收数据在 CPU 计算处理，如果频繁的协程切换检查，检查时异步 IO 又没有结束返回，会造成 CPU 的浪费。所以论文解耦了 IO 状态检查和事务执行的逻辑，为每一个等待异步 IO 结束的事务申请一个可追踪的对象，这些对象放在一起统一做 IO 状态的检查。这样就可以保证只在协程内异步 IO 结束才会切换回该协程。

3. 流水线调度策略：该策略在策略2上扩展，因为策略2按批次处理一组事务，不同事务处理时间不一定相同，当快的事务处理结束后，慢事务可能还在等待 IO 结束，会出现 CPU 空转情况。于是论文中引入了多队列的策略，分别是内存密集型队列和存储密集型队列，两个队列内的事务可以根据情况进行转换，转换有一个缓冲区，用于控制两个队列的大小，保证不出现饥饿或者队列满的情况。

4. 工作线程内的事务日志和提交：论文认为许多数据库系统中后台独立的事务日志线程和异步提交线程会引入数据同步的延迟，为了解决该问题 MosaicDB 选择将事务日志和异步提交全部集成在工作线程，所以每一个工作线程能独立处理事务的所有逻辑。

TDSQL计算引擎对比和论文启发

两篇论文读下来有不少启发，虽然 MosaicDB 的架构和目前的 TDSQL 计算引擎有不少区别，但是也有一些相似之处，这里简单做一些对比，看看有哪些可以借鉴之处。首先对 TDSQL 计算引擎做一下背景介绍。

1、TDSQL 计算引擎介绍

分布式TDSQL MySQL是一种支持存算分离、自动水平拆分、Shared Nothing 架构的分布式数据库。整体架构分为数据节点和计算节点，数据节点由腾讯自研的 TXSQL 负责底层数据管理相关功能；计算节点在协议层和功能方面兼容 MySQL 8.0，计算节点支持多读多写、无状态水平扩展，在查询下推优化、并行查询、分布式事务管理、元数据管理等模块进行了大量深度优化来保证读写性能。

2、有栈协程和无栈协程

新一代 TDSQL 计算引擎通过引入 bthread，将原有计算引擎的线程模型升级为协程模型，但 bthread 本质是一个有栈协程池，它是一个 M:N 的协程模型，这意味着协程可以在线程间迁移。论文二特别强调使用协程提升性能的关键因素在于协程切换的开销必须小于 CPU L3 cache miss。相对而言，C++ 20 coroutine 的无栈协程将上下文保存在堆内存的 coroutine frame 中，切换开销非常小。所以在 TDSQL 计算引擎中是否可以通过引入 prefetching 的技术提升性能，需要更深入的研究和测试。另外一点，在工业界代码中已经有利用 C++ 20 coroutine 和 prefetch 提升执行引擎性能的案例，比如 StarRocks 的 pr：《[Feature] improve hash join performance by coroutine-based interleaving》。有趣的是，他们的测试结果显示并不是所有的场景适合使用 coroutine interleaving，如果强制打开 coroutine interleaving，TPCH/TPCDS 的测试 SQL 性能反而下降，StarRocks 给出的分析结果是这些 SQL 中的 join hash table 不够大，另外有些相同 key 的数据聚集在一起，没有出现太多 cache miss，协程切换带来的开销反而大于从 interleaving 获得的收益。

3、后台线程的影响

TDSQL 作为一个分布式数据库，不可避免使用了很多独立的后台线程，比如 DDL 异步水位更新、后台元数据变更订阅、同步 system variable 的定时器、分布式死锁检测等等，这点和 MosaicDB 还是有很大区别的。TDSQL 的后台工作线程对系统的性能有哪些影响，是否会引起系统性能的抖动等问题，有待后续更深入的研究。

Buffer pool 和 hot-cold 架构

Buffer pool 是 TXSQL中使用的存储访存和内存管理策略，需要读取或写入的数据，都会经过 buffer pool 的页；而 hot-cold 架构则是另一种完全不同的数据库管理策略，它将热数据和冷数据分别存储在不同存储介质中，热数据直接通过主内存读写，而冷数据的读写则是直接访问第二级存储介质，比如磁盘。事实上在 TDSQL 的架构中，可以看作 buffer pool 和 hot-cold 共存，在存储层面，底层的 TXSQL 使用的是 buffer pool 策略；在计算层面，TDSQL计算引擎使用的Parallel Query或者Remote Handler通过网络访问TXSQL层数据，可以看作 hot-cold 架构的 secondary storage。这个点也很有趣，后续有更多时间，会对比 TDSQL/TXSQL 里的 IO 访问策略与 MosaicDB 有哪些异同。

论文缺少了哪些讨论

1、延迟的稳定性和可预测性

正如论文《 A Top-Down Approach to Achieving Performance Predictability in Database Systems》所说，很多关于数据库的性能测试只关注吞吐和平均延迟，而忽略了延迟的稳定性和可预测性。类似的 TPCC 的测试标准要求了 8小时压力测试内 tpmc 的波动率不能大于 2%，DynamoDB 在 USENIX-2022 的论文《Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service | USENIX 》重点强调了系统在不同数据规模下可以保证延迟的可预测性。延迟稳定性和可预测性对于延迟敏感型应用或者存在关键数据请求路径的应用非常重要。论文二使用的工作线程独立、CPU 核数和工作线程 1:1 绑定，多队列调度等策略，从理论上说都有利于保证事务处理延迟稳定性，但是论文里并没有对这一点进行描述或测试，算是一个小遗憾。

2、吞吐和延迟的相互影响

在 ICDE-2018 的论文 《Benchmarking Distributed Stream Data Processing Systems》中提出了数据处理系统中 sustainable performance 的概念，所谓的 unsustainable，是指一个数据处理系统，当请求量超过其处理能力上限时，会触发系统内部的反压机制，导致整体的性能下降或者不再能提供更高的处理能力。触发系统内部反压机制是 sustainable 和 unsustainable 临界状态的一个标志，通常进入 unsustainable 状态后系统的平均处理延迟会急剧上升，如下图所示。MosaicDB 的一些特性，比如工作线程和操作系统 CPU 核心数 1:1 绑定、多队列调度策略，理论上有助于应对系统进入 unsustainable 状态后维持性能，譬如通过请求排队，对可服务范围的请求提供足够的计算资源并保证处理延迟；而使一个 OLTP 数据库引擎进入 unsustainable 状态的最直接方法就是不断增加客户端数量和客户端的并发请求，在这种场景下度量数据库引擎端到端的吞吐和延迟，也是系统性能特征的一部分。这些在论文中也并没有涉及。

总结

两篇论文强调是现代 OLTP 引擎端到端的整体性能优化，论文在使用场景、测试方法和性能要求方面能够反映出现代、端到端数据库的真实需求。其具体优化策略和系统设计也很值得借鉴，在实验验证的环节也有综合考虑到影响数据库数据库引擎性能的多维度因素。

两篇论文出自同一个实验室的研究，论文二还有我司同事的共同合作，很期待这个实验室能在已有研究基础上进一步探索，譬如将他们的系统扩展为分布式数据库场景，一定会有更大的挑战。如果后边有时间，我们也会深入地探索 MosaicDB 中的优化方向能否应用于 TDSQL 计算引擎之中。