前言
X-Engine 是集团数据库事业部研发的新一代存储引擎，是新一代分布式数据库 POLARDB-X 的根基。为了达到 10 倍 MySQL 性能，1/10 存储成本的目标，POLARDB-X 从一开始就使用了软硬件结合的设计思路， 以充分发挥当前软件和硬件领域最前沿的技术优势。而引入 FPGA 加速是我们在定制计算领域做出的第一个尝试。目前 FPGA 加速版本的 POLARDB-X 已经在线上开始小规模灰度，在今年 6.18，双 11 大促中，FPGA 将助力 POLARDB-X， 将在不增加成本的前提下，满足阿里业务对数据库更高的性能要求。
背景介绍
作为世界上最大的在线交易网站，阿里巴巴的 OLTP （online transaction processing） 数据库系统需要满足高吞吐的业务需求。根据统计，每天 OLTP 数据库系统的记录写入量达到了几十亿，在 2017 年的双十一，系统的峰值吞吐达到了千万级 TPS (transactions per second)。阿里巴巴的业务数据库系统主要有以下几个特点：
为了满足阿里的业务对性能和成本近乎苛刻的要求，我们重新设计开发了一个存储引擎称为 X-Engine。在 X-Engine 中，我们引入了诸多数据库领域的前沿技术，包括高效的内存索引结构，写入异步流水线处理机制，内存数据库中使用的乐观并发控制等。
为了达到极致的写性能水平，并且方便分离冷热数据以实现分层存储，X-Engine 借鉴了 LSM-Tree 的设计思想。其在内存中会维护多个 memtable，所有新写入的数据都会追加到 memtable ，而不是直接替换掉现有的记录。由于需要存储的数据量较大，将所有数据存储在内存中是不可能的。
当内存中的数据达到一定量之后，会 flush 到持久化存储中形成 SSTable。为了降低读操作的延时，X-Engine 通过调度 compaction 任务来定期 compact 持久化存储中的 SSTable，merge 多个 SSTable 中的键值对，对于多版本的键值对只保留最新的一个版本（所有当前被事务引用的键值对版本也需要保留）。
根据数据访问的特点，X-Engine 会将持久化数据分层，较为活跃的数据停留在较高的数据层，而相对不活跃(访问较少)的数据将会与底层数据进行合并，并存放在底层数据中，这些底层数据采用高度压缩的方式存储，并且会迁移到在容量较大，相对廉价的存储介质 (比如 SATA HDD) 中，达到使用较低成本存储大量数据的目的。
如此分层存储带来一个新的问题：即整个系统必须频繁的进行 compaction，写入量越大，Compaction 的过程越频繁。而 compaction 是一个 compare & merge 的过程，非常消耗 CPU 和存储 IO，在高吞吐的写入情形下，大量的 compaction 操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响。
而完全重新设计开发的 X-Engine 有着非常优越的多核扩展性，能达到非常高的性能，仅仅前台事务处理就几乎能完全消耗所有的 CPU 资源，其对资源的使用效率对比 InnoDB,如下图所示：
在如此性能水平下，系统没有多余的计算资源进行 compaction 操作，否则将承受性能下跌的代价。
经测试，在 DbBench benchmark 的 write-only 场景下，系统会发生周期性的性能抖动，在 compaction 发生时，系统性能下跌超过 40%，当 compaction 结束时，系统性能又恢复到正常水位。如下图所示：
但是如果 compaction 进行的不及时，多版本数据的累积又会严重影响读操作。
为了解决 compaction 的抖动问题，学术界提出了诸如 VT-tree、bLSM、PE、PCP、dCompaction 等结构。尽管这些算法通过不同方法优化了 compaction 性能，但是 compaction 本身消耗的 CPU 资源是无法避免的。据相关研究统计，在使用 SSD 存储设备时，系统中 compaction 的计算操作占据了 60%的计算资源。因此，无论在软件层面针对 compaction 做了何种优化，对于所有基于 LSM-tree 的存储引擎而言，compaction 造成的性能抖动都会是阿喀琉斯之踵。
幸运的是，专用硬件的出现为解决 compaction 导致的性能抖动提供了一个新的思路。实际上，使用专用硬件解决传统数据库的性能瓶颈已经成为了一个趋势，目前数据库中的 select、where 操作已经 offload 到 FPGA 上，而更为复杂的 group by 等操作也进行了相关的研究。但是目前的 FPGA 加速解决方案存在以下两点不足：
为了缓解 compaction 对 X-Engine 系统性能的影响，我们引入了异构硬件设备 FPGA 来代替 CPU 完成 compaction 操作，使系统整体性能维持在高水位并避免抖动，是存储引擎得以服务业务苛刻要求的关键。本文的贡献如下：
问题背景
X-Engine 的 Compaction
X-Engine 的存储结构包含了一个或多个内存缓冲区 （memtable）以及多层持久化存储 L0, L1, … ，每一层由多个 SSTable 组成。
当 memtable 写满后，会转化为 immutable memtable，然后转化为 SSTable flush 到 L0 层。每一个 SSTable 包含多个>
一个 compaction 过程 merge 一个指定范围的键值对，这个范围可能包含多个>
对于读操作而言，X-Engine 需要从所有的 memtable 中查找，如果没有找到，则需要在持久化存储中从高层向底层查找。因此，及时的 compaction 操作不仅会缩短读路径，也会节省存储空间，但是会抢夺系统的计算资源，造成性能抖动，这是 X-Engien 亟待解决的困境。
FPGA 加速数据库
从现在的 FPGA 加速数据库现状分析，我们可以将 FPGA 加速数据库的架构分为两种，“bump-in-the-wire” 设计和混合设计架构。前期由于 FPGA 板卡的内存资源不够，前一种架构方式比较流行，FPGA 被放置在存储和 host 的数据路径上，充当一个 filter，这样设计的好处是数据的零拷贝，但是要求加速的操作是流式处理的一部分，设计方式不够灵活；
后一种设计方案则将 FPGA 当做一个协处理器，FPGA 通过 PCIe 和 host 连接，数据通过 DMA 的方式进行传输，只要 offload 的操作计算足够密集，数据传输的代价是可以接受的。混合架构的设计允许更为灵活的 offload 方式，对于 compaction 这一复杂操作而言，FPGA 和 host 之间数据的传输是必须的，所以在 X-Engine 中，我们的硬件加速采用了混合设计的架构。
系统设计
在传统的基于 LSM-tree 的存储引擎中，CPU 不仅要处理正常的用户请求，还要负责 compaction 任务的调度和执行，即对于 compaction 任务而言，CPU 既是生产者，也是消费者，对于 CPU-FPGA 混合存储引擎而言，CPU 只负责 compaction 任务的生产和调度，而 compaction 任务的实际执行，则被 offload 到专用硬件（FPGA）上。
对于 X-Engine，正常用户请求的处理和其他基于 LSM-tree 的存储引擎类似：
当 L0 层的 SSTable 数量达到阈值时，compaction 任务会被触发，compaction 的 offload 分为以下几个步骤：
详细设计
FPGA-based Compaction
Compaction Unit (CU) 是 FPGA 执行 compaction 任务的基本单元。一个 FPGA 板卡内可以放置多个 CU，单个 CU 由以下几个模块组成：
一个 compaction 过程包含三个步骤：decode，merge，encode。设计一个合适的 compaction 流水线的最大挑战在于每一个步骤的执行时间差距很大。比如说由于并行化的原因，decode 模块的吞吐远高于 encoder 模块，因此，我们需要暂停某些执行较快的模块，等待流水线的下游模块。为了匹配流水线中各个模块的吞吐差异，我们设计了 controller 模块去协调流水线中的不同步骤，这样设计带来的一个额外好处是解耦了流水线设计的各个模块，在工程实现中实现更敏捷的开发和维护。
在将 FPGA compaction 集成到 X-Engine 中，我们希望可以得到独立的 CU 的吞吐性能，实验的 baseline 是 CPU
单核的 compaction 线程 （Intel® Xeon® E5-2682 v4 CPU with 2.5 GHz）
从实验中我们可以得到以下三个结论：
异步调度逻辑设计
由于 FPGA 的一次链路请求在 ms 级别，因此使用传统的同步调度方式会造成较频繁的线程切换代价，针对 FPGA 的特点，我们重新设计了异步调度 compaction 的方式：CPU 负责构建 compaction task 并将其压入 Task Queue 队列，通过维护一个线程池来分配 compaction task 到指定的 CU 上，当 compaction 结束后，compaction 任务会被压入到 Finished Queue 队列，CPU 会检查任务执行的状态，对于执行失败的任务会调度 CPU 的 compaction 线程再次执行。通过异步调度，CPU 的线程切换代价大大减少。
容错机制的设计
对于 FPGA compaction 而言，有以下三种原因可能会导致 compaction 任务出错
对于所有出错的任务，CPU 都会进行再次计算，确保数据的正确性。在上述的容错机制的下，我们解决了少量的超过限制的 compaction 任务并且规避了 FPGA 内部错误的风险。
实验结果
实验环境
我们比较两种存储引擎的性能：
结果分析：
结果分析：
TPC-C （100 warehouses）
| Connections | X-Engine-CPU | X-Engine-FPGA |
|---|
结果分析：
在这个实验中我们包含了对于 InnoDB 的测试（buffer size = 80G）
结果分析：
总结
在本文中，我们提出的带有 FPGA 加速的 X-Engine 存储引擎，对于 KV 接口有着 50%的性能提升，对于 SQL 接口获得了 40%的性能提升。随着读写比的降低，FPGA 加速的效果越明显，这也说明了 FPGA compaction 加速适用于写密集的 workload，这和 LSM-tree 的设计初衷是一致的，另外，我们通过设计容错机制来规避 FPGA 本身的缺陷，最终形成了一个适用于阿里实际业务的高可用的 CPU-FPGA 混合存储引擎。
写在最后
此项目是 POLARDB-X 引入异构计算设备，以加速数据库核心功能的第一个落地项目。从使用经验来看，FPGA 能完全解决 X-Engine 的 Compaction 带来的计算需求。同时我们也在进一步研究将更多合适的计算任务调度到 FPGA 上运行，如压缩，生成 BloomFilter，SQL JOIN 算子等。目前压缩功能开发基本完毕，将会和 Compaction 做成一套 IP，同步完成数据合并和压缩操作。
POLARDB-X FPGA-Compaction 硬件加速，是数据库事业部数据库内核团队，服务器研发事业部定制计算团队，浙江大学三方合作完成的一个研发项目。同时此项目的落地也有赖 Xilinx 公司技术团队的大力支持，在此一并表示感谢。
POLARDB-X 将在今年上线阿里云进行公测，大家可以体验到 FPGA 加速给 POLARDB-X 带来的极致性能，也期待大家的宝贵建议。
原文链接：
