当数据库遇见 FPGA：POLARDB-X 异构计算如何实现百万级 TPS？

前言

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)。阿里巴巴的业务数据库系统主要有以下几个特点：

• 事务高吞吐并且读操作和写操作的低延时；

• 写操作占比相对较高，传统的数据库 workload，读写比一般在 10:1 以上，而阿里巴巴的交易系统，在双十一当天读写比达到了 3:1；

• 数据访问热点比较集中，一条新写入的数据，在接下来 7 天内的访问次数占整体访问次数的 99%，超过 7 天之后的被访问概率极低。

为了满足阿里的业务对性能和成本近乎苛刻的要求，我们重新设计开发了一个存储引擎称为 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 加速解决方案存在以下两点不足：

• 目前的加速方案基本上都是为 SQL 层设计，FPGA 也通常放置在存储和 host 之间作为一个 filter。虽然在 FPGA 加速 OLAP 系统方面已经有了许多尝试，但是对于 OLTP 系统而言，FPGA 加速的设计仍然是一个挑战；

• 随着 FPGA 的芯片尺寸越来越小，FPGA 内部的错误诸如单粒子翻转（SEU）正在成为 FPGA 可靠性的越来越大的威胁，对于单一芯片而言，发生内部错误的概率大概是 3-5 年，对于大规模的可用性系统，容错机制的设计显得尤为重要。

为了缓解 compaction 对 X-Engine 系统性能的影响，我们引入了异构硬件设备 FPGA 来代替 CPU 完成 compaction 操作，使系统整体性能维持在高水位并避免抖动，是存储引擎得以服务业务苛刻要求的关键。本文的贡献如下：

• FPGA compaction 的高效设计和实现。通过流水化 compaction 操作，FPGA compaction 取得了十倍于 CPU 单线程的处理性能；

• 混合存储引擎的异步调度逻辑设计。由于一次 FPGA compaction 的链路请求在 ms 级别，使用传统的同步调度方式会阻塞大量的 compaction 线程并且带来很多线程切换的代价。通过异步调度，我们减少了线程切换的代价，提高了系统在工程方面的可用性。

• 容错机制的设计。由于输入数据的限制和 FPGA 内部错误，都会造成某个 compaction 任务的回滚，为了保证数据的完整性，所有被 FPGA 回滚的任务都会由同等的 CPU compaction 线程再次执行。本文设计的容错机制达到了阿里实际的业务需求并且同时规避了 FPGA 内部的不稳定性。

问题背景

X-Engine 的 Compaction

X-Engine 的存储结构包含了一个或多个内存缓冲区 （memtable）以及多层持久化存储 L0, L1, … ，每一层由多个 SSTable 组成。

当 memtable 写满后，会转化为 immutable memtable，然后转化为 SSTable flush 到 L0 层。每一个 SSTable 包含多个 data block 和一个用来索引 data block 的 index block。当 L0 层文件个数超过了限制，就会触发和 L1 层有重叠 key range 的 SSTable 的合并，这个过程就叫做 compaction。类似的，当一层的 SSTable 个数超过了阈值都会触发和下层数据的合并，通过这种方式，冷数据不断向下流动，而热数据则驻留在较高层上。

一个 compaction 过程 merge 一个指定范围的键值对，这个范围可能包含多个 data block。一般来说，一个 compaction 过程会处理两个相邻层的 data block 合并，但是对于 L0 层和 L1 层的 compaction 需要特殊考虑，由于 L0 层的 SSTable 是直接从内存中 flush 下来，因此层间的 SSTable 的 Key 可能会有重叠，因此 L0 层和 L1 层的 compaction 可能存在多路 data block 的合并。

对于读操作而言，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 的存储引擎类似：

• 用户提交一个操作指定 KV pair（Get/Insert/Update/Delete）的请求，如果是写操作，一个新的记录会被 append 到 memtable 上；

• 当 memtable 的大小达到阈值时会被转化为 immutable memtable；

• immutable memtable 转化为 SSTable 并且被 flush 到持久化存储上。

当 L0 层的 SSTable 数量达到阈值时，compaction 任务会被触发，compaction 的 offload 分为以下几个步骤：

• 从持久化存储中 load 需要 compaction 的 SSTable，CPU 通过 meta 信息按照 data block 的粒度拆分成多个 compaction 任务，并且为每个 compaction 任务的计算结果预分配内存空间，每一个构建好的 compaction 任务都会被压入到 Task Queue 队列中，等待 FPGA 执行；

• CPU 读取 FPGA 上 Compaction Unit 的状态，将 Task Queue 中的 compaction 任务分配到可用的 Compaction Unit 上；

• 输入数据通过 DMA 传输到 FPGA 的 DDR 上；

• Compaction Unit 执行 Compaction 任务，计算完成后，结果通过 DMA 回传给 host，并且附带 return code 指示此次 compaction 任务的状态（失败或者成功），执行完的 compaction 结果会被压入到 Finished Queue 队列中；

• CPU 检查 Finished Queue 中 compaction 任务的结果状态，如果 compaction 失败，该任务会被 CPU 再次执行；

• compaction 的结果 flush 到存储。

详细设计

FPGA-based Compaction

Compaction Unit (CU) 是 FPGA 执行 compaction 任务的基本单元。一个 FPGA 板卡内可以放置多个 CU，单个 CU 由以下几个模块组成：

• Decoder. 在 X-Engine 中，KV 是经过前序压缩编码后存储在 data block 中的，Decoder 模块的主要作用是为了解码键值对。每一个 CU 内部放置了 4 个 Decoder，CU 最多支持 4 路的 compaction，多余 4 路的 compaction 任务需要 CPU 进行拆分，根据评估，大部分的 compaction 都在 4 路以下。放置 4 个 Decoder 同样也是性能和硬件资源权衡的结果，和 2 个 Decoder 相比，我们增加了 50%的硬件资源消耗，获得了 3 倍的性能提升。

• KV Ring Buffer. Decoder 模块解码后的 KV pair 都会暂存在 KV Ring Buffer 中。每一个 KV Ring Buffer 维护一个读指针（由 Controller 模块维护）和一个写指针（由 Decoder 模块维护），KV Ring Buffer 维护 3 个信号来指示当前的状态：FLAG_EMPTY, FLAG_HALF_FULL, FLAG_FULL，当 FLAG_HALF_FULL 为低位时，Decoder 模块会持续解码 KV pair，否则 Decoder 会暂停解码直到流水线的下游消耗掉已经解码的 KV pair。

• KV Transfer. 该模块负责将 key 传输到 Key Buffer 中，因为 KV 的 merge 只涉及 key 值的比较，因此 value 不需要传输，我们通过读指针来追踪当前比较的 KV pair。 Key Buffer. 该模块会存储当前需要比较的每一路的 key，当所有需要比较的 key 都被传输到 Key Buffer 中，Controller 会通知 Compaction PE 进行比较。

• Compaction PE. Compaction Processing Engine （compaction PE）负责比较 Key Buffer 中的 key 值。比较结果会发送给 Controller，Controller 会通知 KV Transfer 将对应的 KV pair 传输到 Encoding KV Ring Buffer 中，等待 Encoder 模块进行编码。

• Encoder. Encoder 模块负责将 Encoding KV Ring Buffer 中的 KV pair 编码到 data block 中，如果 data block 的大小超过阈值，会将当前的 data block flush 到 DDR 中。

• Controller. 在 CU 中 Controller 充当了一个协调器的作用，虽然 Controller 不是 compaction pipeline 的一部分，单在 compaction 流水线设计的每一个步骤都发挥着关键的作用。

一个 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）

从实验中我们可以得到以下三个结论：

• 在所有的 KV 长度下，FPGA compaction 的吞吐都要优于 CPU 单线程的处理能力，这印证了 compaction offload 的可行性；

• 随着 key 长度的增长，FPGA compaction 的吞吐降低，这是由于需要比较的字节长度增加，增加了比较的代价；

• 加速比（FPGA throughput / CPU throughput）随着 value 长度的增加而增加，这是由于在 KV 长度较短时，各个模块之间需要频繁进行通信和状态检查，而这种开销和普通的流水线操作相比是非常昂贵的。

异步调度逻辑设计

由于 FPGA 的一次链路请求在 ms 级别，因此使用传统的同步调度方式会造成较频繁的线程切换代价，针对 FPGA 的特点，我们重新设计了异步调度 compaction 的方式：CPU 负责构建 compaction task 并将其压入 Task Queue 队列，通过维护一个线程池来分配 compaction task 到指定的 CU 上，当 compaction 结束后，compaction 任务会被压入到 Finished Queue 队列，CPU 会检查任务执行的状态，对于执行失败的任务会调度 CPU 的 compaction 线程再次执行。通过异步调度，CPU 的线程切换代价大大减少。

容错机制的设计

对于 FPGA compaction 而言，有以下三种原因可能会导致 compaction 任务出错

• 数据在传输过程中被损坏，通过在传输前和传输后分别计算数据的 CRC 值，然后进行比对，如果两个 CRC 值不一致，则表明数据被损坏；

• FPGA 本身的错误（比特位翻转），为了解决这个错误，我们为每一个 CU 配置了一个附加 CU，两个 CU 的计算结果进行按位比对，不一致则说明发生了比特位翻转错误；

• compaction 输入数据不合法，为了方便 FPGA compaction 的设计，我们对 KV 的长度进行了限制，超过限制的 compaction 任务都会被判定为非法任务。

对于所有出错的任务，CPU 都会进行再次计算，确保数据的正确性。在上述的容错机制的下，我们解决了少量的超过限制的 compaction 任务并且规避了 FPGA 内部错误的风险。

实验结果

实验环境

• CPU：64-core Intel (E5-2682 v4, 2.50 GHz) processor

• 内存：128GB

• FPGA 板卡：Xilinix VU9P

• memtable: 40 GB

• block cache 40GB

我们比较两种存储引擎的性能：

• X-Engine-CPU：compaction 操作由 CPU 执行

• X-Engine-FPGA：compaction offload 到 FPGA 执行

DbBench

结果分析：

• 在 write-only 场景下，X-Engine-FPGA 的吞吐提升了 40%，从性能曲线我们可以看出，当 compaction 开始时，X-Engine-CPU 系统的性能下跌超过了三分之一；

• 由于 FPGA compaction 吞吐更高，更及时，因此读路径减少的更快，因此在读写混合的场景下 X-Engine-FPGA 的吞吐提高了 50%；

• 读写混合场景的吞吐小于纯写场景，由于读操作的存在，存储在持久层的数据也会被访问，这就带来了 I/O 开销，从而影响了整体的吞吐性能；

• 两种性能曲线代表了两种不同的 compaction 状态，在左图，系统性能发生周期性的抖动，这说明 compaction 操作在和正常事务处理的线程竞争 CPU 资源；对于右图，X-Engine-CPU 的性能一直稳定在低水位，表明 compaction 的速度小于写入速度，导致 SSTable 堆积，compaction 任务持续在后台调度；

• 由于 compaction 的调度仍然由 CPU 执行，这也就解释了 X-Engine-FPGA 仍然存在抖动，并不是绝对的平滑。

YCSB

结果分析：

• 在 YCSB benchmark 上，由于 compaction 的影响，X-Engine-CPU 的性能下降了 80%左右，而对于 X-Engine-FPGA 而言，由于 compaction 调度逻辑的影响，X-Engine-FPGA 的性能只有 20%的浮动；

• check unique 的存在引入了读操作，随着压测时间的增长，读路径变长，因此两个存储引擎的性能随着时间下降；

• 在 write-only 场景下，X-Engine-FPGA 的吞吐提高了 40%，随着读写比的上升，FPGA Compaction 的加速效果逐渐降低，这是因为读写比越高，写入压力越小，SSTable 堆积的速度越慢，因此执行 compaction 的线程数减少，因此对于写密集的 workload，X-Engine-FPGA 的性能提升越明显；

• 随着读写比的上升，吞吐上升，由于写吞吐小于 KV 接口，因此 cache miss 的比例较低，避免了频繁的 I/O 操作，而随着写比例的上升，执行 compaction 线程数增加，因此降低了系统的吞吐能力。

TPC-C （100 warehouses）

结果分析：

• 通过 FPGA 加速，随着连接数从 128 增加到 1024，X-Engine-FPGA 可以得到 10%~15%的性能提升。当连接数增加时，两个系统的吞吐都逐渐降低，原因在于随着连接数增多，热点行的锁竞争增加；

• TPC-C 的读写比是 1.8：1，从实验过程来看，在 TPC-C benchmark 下，80%以上的 CPU 都消耗在 SQL 解析和热点行的锁竞争上，实际的写入压力不会太大，通过实验观测，对于 X-Engine-CPU 系统，执行 compaction 操作的线程数不超过 3 个 （总共 64 核心），因此，FPGA 的加速效果不如前几个实现明显。

SysBench

在这个实验中我们包含了对于 InnoDB 的测试（buffer size = 80G）

结果分析：

• X-Engine-FPGA 提高了 40%以上的吞吐性能，由于 SQL 解析消耗了大量的 CPU 资源，DBMS 的吞吐要小于 KV 接口；

• X-Engine-CPU 在低水位达到了平衡，原因在于 compaction 的速度小于写入速度，导致 SST 文件堆积，compaction 持续被调度；

• X-Engine-CPU 的性能两倍于 InnoDB，证明了基于 LSM-tree 的存储引擎在写密集场景下的优势；

• 和 TPC-C benchmark 相比，Sysbench 更类似阿里的实际交易场景，对于交易系统而言，查询的类型大部分是插入和简单的点查询，很少涉及范围查询，热点行冲突的减少使得 SQL 层消耗的资源减少。在实验过程中，我们观测到对于 X-Engine-CPU 而言，超过 15 个线程都在执行 compaction，因此 FPGA 加速带来的性能提升更加明显。

总结

在本文中，我们提出的带有 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 带来的极致性能，也期待大家的宝贵建议。

原文链接：https://yq.aliyun.com/articles/578308