前言
X-Engine 是集团数据库事业部研发的新一代存储引擎，是新一代分布式数据库X-DB的根基。为了达到10倍MySQL性能，1/10存储成本的目标，X-DB从一开始就使用了软硬件结合的设计思路， 以充分发挥当前软件和硬件领域最前沿的技术优势。而引入FPGA加速是我们在定制计算领域做出的第一个尝试。目前FPGA加速版本的X-DB已经在线上开始小规模灰度，在今年6.18，双11大促中，FPGA将助力X-DB， 将在不增加成本的前提下，满足阿里业务对数据库更高的性能要求。
背景介绍
作为世界上最大的在线交易网站，阿里巴巴的 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加速解决方案存在以下两点不足：
目前的加速方案基本上都是为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(R) Xeon(R) 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内部错误的风险。
实验结果
实验环境
我们比较两种存储引擎的性能：
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）
Connections |
X-Engine-CPU |
X-Engine-FPGA |
128 |
214279 |
240105 |
256 |
203268 |
230401 |
512 |
197001 |
219618 |
1024 |
189697 |
208532 |
结果分析：
通过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加速带来的性能提升更加明显。
-
