1、What is X-Engine
X-Engine是阿里云自研OLTP数据库存储引擎，已经广泛应用于包括钉钉、核心交易、阿里妈妈在内的阿里巴巴核心业务，在提供高性能的同时大幅降低了存储开销。
经过阿里双十一等高压场景的考验与打磨，RDS MySQL(X-Engine)版即将在阿里云上向外部客户提供服务，将技术红利带给云上用户。
X-Engine:An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing 介绍了X-Engine的系统架构以及核心设计，发表在SIGMOD'19 Industrial Track。
近日，X-Engine团队的另一项工作FPGA-Accelerated Compactions for LSM-based Key-Value Store被FAST'20 Research Track接收（USENIX Conference on File and Storage Techniques (FAST)，CCF A类会议，存储领域顶会，2020年接受率16%），本文会对这项工作进行简单介绍。
X-Engine采用了LSM-tree架构，同时广泛针对现代多核，大内存，高速存储的服务器进行了优化，例如其内部大量采用无锁设计，具有良好的扩展性。
在开始论文的解读前，我们先分析下X-Engine所处时代的服务器硬件发展趋势，以及LSM-tree架构的存储引擎对服务器计算资源及存储资源的需求特点，两项结合，读者能更好的理解为何在数据库中引入CPU以外的专用计算设备会是未来的一个趋势。
2、硬件发展趋势
近年来，包括处理器和存储在内的服务器端硬件的发展非常快。CPU 方面，Intel 的 Xeon CPU 家族在 14nm 制程上完成了第一轮 "Process-Architecture-Optimization" 模型下的迭代，在 10nm 制程上也推出了最新的 Tiger Lake 微架构。
在 CPU 核数的增长已经变得司空见惯的今天，Tiger Lake 不仅拥有比 Skylake 高约 30% 的时钟频率，还拥有更大的 L1/L2 cache，更大的 cache line，使用 HBM 技术的 L4 cache 和更快的 I/O。这些突破性的进展都标志着 CPU 处理能力的跃升。放眼未来，Intel 还预计于 2021 年开启一轮新的迭代，发布其新的 7nm 制程处理器。
CPU 之外，新型 FPGA、GPU 和各类 AI 处理器层出不穷。2019年，阿里巴巴发布了峰值推理性能达到 78563 IPS的含光800处理器。传统的异构加速器在不断迭代升级之外，也发展出了日渐成熟的混合架构，如 CPU-FPGA（e.g., Intel Arria），和 FPGA-accelerated NVMe SSD (e.g., BittWare 250)。存储方面，随着比传统 NAND 闪存快近千倍的 3D XPoint 技术的发展和应用，无论是 NVM 还是 SSD 的性能都有了长足的进步。
最新的 Intel Optane SSD 的随机读、写性能都达到了 550000 IOPS，顺序读写带宽更是分别达到了 2500 MB/s 和 2200 MB/s，读写延迟 10 µs。下图则展示过去10年间，每年进入市场的 Intel SSD 的峰值 I/O 性能。我们可以看到，无论是顺序I/O，还是随机 I/O 的能力都有了非常快的进步。
在我们的工业实践中，三年前我们所使用的典型服务器，还只能提供2.4GB/S的顺序读带宽，而到了今年，在我们最新的服务器上，测试值已经达到了 12GB/S的带宽。
过去10年间，每年上市的 Intel SSD 的峰值 I/O 性能
新硬件趋势和底层硬件性能的变化往往会造成上层软件的性能瓶颈的迁移，尤其是像数据库存储引擎这样的直接接触存储硬件的基础软件。随着 I/O 性能的不断提高，很多传统的瓶颈在 I/O的 数据库算法逐渐转变为被计算资源所限制；反之亦然。在这项工作中，我们发现 LSM-tree 存储引擎的中的 Compaction 操作正是一个正在由 I/O 瓶颈转变为计算瓶颈的例子。具体细节，请看下文详细展开。
3、LSM-tree 的 Compaction
在LSM-tree架构中，写入操作会首先插入到内存中，当大小到达阈值后，会写到磁盘上，并和磁盘上的数据合并（类似于merge sort），而磁盘上的数据按照层级进行组织，每一层的数据达到阈值后都会和下一层的数据进行合并（图（a））。
这样做的好处主要有两点：1. 写入操作（insert/update/delete）统一转化为追加操作，不会更新原有数据，写性能要优于innodb等存储引擎；2. 分层存储，数据有序排列，每个block都是紧凑的，不存在空洞，便于压缩，存储成本优势明显。
X-Engine 的数据层次结构与LevelDB, RocksDB这些使用LSM-tree的存储引擎类似，写入首先写入到memtable中，当memtable写满后转化为immutable memtable，之后immutable memtable会刷盘持久化。
X-Engine磁盘上的数据也是按层组织，每一层一般切分成多个固定大小的有序段（X-Engine中的Extent，类似于RocksDB中的SSTable），每一个Extent再切分成多个data block，data block中的数据一般进行前缀编码存储，每一个Extent会有一个Index block来索引data block（图（b））。
后台的flush/compaction线程负责将内存数据和磁盘上的数据进行合并，每一层的数据量到达阈值后也会触发和下层数据的合并，这个操作称之为 compaction 。
及时的compaction非常重要，LSM-tree在持续高强度写入压力下会产生形变（层数累计过多），会给读操作带来非常大的麻烦（由于多版本数据的影响，读操作需要顺序扫描各层并合并产生结果）。compaction及时合并多版本数据，删除旧版本数据，维持一个健康的读取路径长度，对存储空间释放及系统性能意义重大。
下图展示了不同KV长度的compaction执行时间分解图，在短KV情况下（value长度小于等于64B），compaction的计算时间占比在50%以上。近年来存储设备读写性能提升非常快，而CPU主频的提升则非常缓慢，compaction操作中计算时间占比越来越长。另外，X-Engine的数据块都是压缩存储的，考虑到压缩带来的额外CPU消耗，计算资源的瓶颈更加明显。
下图展示了X-Engine长时间运行的性能以及资源利用情况（key=8B, value=32B），预热时间1个小时，观测窗口2个小时，读写比为3:1，在32个compaction线程的设置下，系统性能达到了最高水位。
这个随着后台compaction线程数增加性能类似抛物线的变化说明了两个问题：
1.及时的compaction能让系统性能得以保持在高水位，否则LSM-tree层数的堆积增长会严重损害系统性能（32个线程配置下，X-Engine性能是8个线程配置的2倍左右）。
2.在CPU资源受限的情况下，compaction操作需要和前台的事务处理线程竞争计算资源，资源竞争对系统性能的损害在超过32个compaction 线程的设置下开始显现。
- 为了使compaction任务及时的被处理，我们可以设置更多的compaction线程， 但过多的compaction线程争抢计算资源又会对执行前台事务操作的线程带来负面影响，降低吞吐。前台事务产生新数据的速度和后台compaction线程消纳堆积数据的速度达到平衡时，系统达到均衡性能，但此性能一般远低于数据库可以达到的峰值性能。
Compaction需要做，但不一定非得CPU来做。一个compaction任务包含了多路数据块的读取、解码、归并排序、编码、写回等阶段，对于同一个compaction任务来说，前后阶段存在数据依赖，但是对于多个任务来说，并不存在数据依赖，完全可以通过流水线执行来提高吞吐能力。
通过将compaction offload到适合处理流水线任务的FPGA来执行，CPU可以全部服务于复杂的事务处理，从而避免了后台任务对于计算资源的侵占。如此数据库系统可以一直以峰值性能处理事务。
4、整体架构
我们所使用的FPGA加速卡是通过PCIe接口连接到服务器上，它并不能像服务器上的CPU一样方便的访问内存和磁盘。另外FPGA计算能力强大，但是单次访问的延时却更像一个IO设备。这样的特点决定了我们不能直接将之前CPU版本的compaction算法直接应用到FPGA上。
为了适配FPGA加速卡，我们首先将CPU版本的流式compaction实现改造成分批次模式。CPU负责将compaction拆分成特定大小的task，每个task可以并行执行，这样可以充分发挥FPGA加速卡上多CU的并行能力。
在X-Engine中，我们设计了一个任务队列（Task Queue）来缓存需要执行的compaction任务，通过Driver来下发给FPGA上的计算单元（compaction unit，CU）执行，执行的结果会缓存在结果队列（Result Queue）中，等待CPU写回持久化存储。
- 架构关键设计一：Compaction 调度器
度器负责构建compaction任务，然后分发给CU执行，并将compaction的结果写回到磁盘上，我们设计了三种线程来完成整个链路：
Builder thread：将需要被合并的Extent按照range切分，形成compaction task。每一个compaction task结构体维护了必要的元信息，包括Task Queue指针，输入数据的起始地址（传输到FPGA需要做CRC校验保证数据正确性），compaction结果的写回地址，以及后续逻辑的回调函数指针。
此外，每一个task还包含return code，标志此次compaction任务是否执行成功，对于失败的任务，我们会调用CPU再次执行。通过线上运行的数据显示，大概只有0.03%的task会被CPU再次执行（主要是KV长度过长的case）。
Dispatcher thread：由于FPGA上存在多个CU，需要设计相应的分发算法，目前我们采用了简单的round-robin分发策略，由于每一个下发的compaction task大小接近，实验表明不同CU的利用率比较均衡。
Driver thread：负责将数据传输至FPGA并通知CU开始工作，当CU任务执行完成后会中断Driver thread将结果传回内存，并将task入队Result Queue。
- 架构关键设计二：Compaction Unit
Compaction Unit （CU）是CPU compaction对应的FPGA实现逻辑。一个FPGA上可以部署多个CU，由Driver进行分发调度。一个CU由Decoder、KV Ring Buffer、KV Transfer and Key Buffer、Merger、Encoder、Controller组成。
Decoder模块的设计和LSM-tree的compaction policy相关，目前的CU采用4路Decoder设计。X-Engine采用tiering策略，因此可能会存在多路合并的情况，从实际的运行情况来看，2~4路的归并是比较常见的，而4路归并的设计比2路归并的设计更加高效（性能提升3倍，硬件资源消耗增加40%左右）。Decoder模块将前序编码的KV对解码后缓存到KV Ring Buffer中。
KV Ring Buffer 由32个8KB的slot构成，每一个slot中6KB存储KV数据，另外2KB存储KV的元信息（KV长度等）。每一个KV Ring Buffer有三种状态：FLAG_EMPTY, FLAG_HALF_FULL, FLAG_FULL，来标识Ring Buffer是处在空、半满、满，根据缓存的KV数量我们会决定是否要继续推进流水线，还是要暂时Decoder以等待下游消耗。
KV Transfer和Key Buffer主要负责KV的传输，由于归并排序并不需要比较value，因此只需要缓存Key值即可。
Merger操作负责合并 Key Buffer中的key，下图中，第二路的key值最小，Controller会通知KV Transfer将对应 KV 从 KV Ring Buffer中传输到 KV Output Buffer（和KV Ring Buffer结构类似），并将KV Ring Buffer的读指针前移得到下一个KV，Controller会通知Merger进行下一轮比较。
Encoder模块主要负责将Merger输出的KV进行前序编码，组织成data block的格式写入到FPGA的内存中。
为了控制各个阶段的处理速度，我们引入了Controller模块，Controller模块负责维护KV Ring Buffer的读写指针，并根据KV Ring Buffer的状态感知流水线上下游处理速度的差距，通过暂停/重启相应模块来维持流水线的高效运转。
- 架构关键设计三：容错机制
保证数据一致性是数据库引擎基本功能，引入异构计算设备，增加了额外变量，引入新风险。X-Engine在整体架构设计上考虑到了FPGA 计算设备失效，传输链路出现bit跳变等风险。容错方面X-Engine做了如下工作。
1.X-Engine可以探测到服务器是否部署FPGA加速卡，以及当前FPGA卡是否可用（有刷入compaciton/压缩解压 固件，设备是否存活)等。X-Engine的Compaction/压缩等逻辑均有CPU版本实现做备份。如果运行过程中FPGA突然失联，可以平滑的切换回CPU模式，只是峰值性能稍低，稳定性不会有任何影响。切换回CPU模式之后，X-Engine会定期探测FPGA加速卡的可用性，如有可能就立即切换到FPGA加速模式。
2.Compaction CU的每一个步骤中，均保存了CRC校验值，同时compaction任务的输入输出在FPGA卡的内存和主机内存之间传输后，均会做校验。确保传输链路中不会出现跳变。
3.X-Engine可以兼容部分compacton任务的执行失败。由于超时，内存读写错误导致的单个任务失败，X-Engine会捕获到执行结果，并将失败的任务交由CPU重新执行并获得结果。而且这个设计还给我们带来另一个好处，由于FPGA卡的compaction固件逻辑实现涉及到芯片上的寄存器分配及逻辑布线，如果需要处理key或者value特别长的记录，会导致FPGA逻辑的计算效率降低。
因此我们的FPGA实现中，只支持特定长度KV记录。遇见超长KV记录时会直接报错返回，并交由CPU处理。这样可以避免让FPGA处理一些数据库中出现的长TEXT/BLOB等字段。这样就实现了功能（长KV)和性能的兼顾. X-Engine在线上实际运行中，统计到的失败的task占比在万分之三左右, 证明我们的思路是可行的。
5、实验评估
本文的所有实验均在装有两个Intel XeonPlatinum 8163 2.5 GHz 24-core (two-way hyperthreading)的处理器上进行，内存为512GB的DDR4-2133，磁盘环境为由10块SSD构成的RAID 0阵列，Linux版本为4.9.79。FPGA板卡型号为Xilinx VU9P (200M Hz)，FPGA内存大小为16GB，通过 x16 PCIe Gen 3和主机相连。FPGA上共配置了8个CU。
1.CU加速评估
我们设计单测来比较单CU和CPU单核心的compaction吞吐。load四路共计400万条记录并触发compaction，在不同的KV场景下，FPGA compaction加速比在2到5倍之间。
为了能够定量评估流水线各个模块的吞吐速度，我们还为CU的处理速度进行了建模，实际上，无论是对于FPGA Compaction还是CPU compaction，能够精准控制compaction执行时间都是非常重要的。通过理论模型，我们可以通过预估提供指定compaction吞吐所需要的CU数量。模型计算的结果和单测结果误差在20%以内。
2.系统性能评估
性能评估工具：DbBench，workload分布采用Zipf-1.0，读写比默认设置为3：1，load 32个subtable（对应一棵LSM-Tree），每个subtable包含200000000条数据，内存设置为70GB，Key和Value的大小分别设置为8B和32B，该配置是线上的一个常见配置，所有的实验预热时间3600秒，评估时间为7200秒。
使用FPGA加速后，X-Engine的性能和32个线程的CPU版本性能提升在25%左右，CPU的利用率降低了10%左右。虽然32个线程以上的CPU compaction吞吐大于FPGA版本的compaction，但是增加了计算资源的竞争，虽然数据消解更快（数据量），但是性能也不理想。
6、总结
存储引擎的发展就是在应用负载不断变化、硬件环境不断革新的情况下寻找成本和性能最优平衡的过程。
LSM-tree生态的繁荣正是上述两点共同作用的结果，一方面，写操作、点查询逐渐成为了用户负载的主要部分（WPI，write and point read-intensive），数据量的爆炸增长，写操作比例的上升令LSM-tree存储引擎得以广泛应用，另一方面，存储介质技术的飞速发展，SSD，NVMe等介质将持久化层的吞吐推上了一个新的高度，存储引擎的性能瓶颈开始从IO过渡到CPU，也正在催生许多新的挑战。
运用新硬件来解决存储系统的瓶颈问题，我们只是向前迈了一小步，还有很多有意思的问题需要更好的解答：
Compaction越快越好吗？如何在及时compaction和避免compact热点数据造成cache miss之间寻找平衡，timing compaction看似显而易见，实则需要细细考量。
“专用”是把双刃剑。如何在compaction压力较小的时候提高FPGA资源的利用率，可以考虑同时支持多个实例以及不同IP共享硬件资源，哪种方案更切实可行，还需要更长时间的工业实践积累来告诉我们答案。
前路漫漫，道阻且长。
致谢
本工作由阿里巴巴数据库产品事业部X-Engine团队、基础设施事业部定制计算(AIS)团队、达摩院数据库与存储实验室以及阿里巴巴-浙江大学前沿技术联合研究中心（AZFT）合作完成。在此向参与此项工作的研究人员以及指导论文写作的老师表示感谢，相信未来还会有更多的合作成果产生。
