写点什么

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

  • 2019 年 5 月 09 日
  • 本文字数:8026 字

    阅读完需:约 26 分钟

当数据库遇见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)

ConnectionsX-Engine-CPUX-Engine-FPGA
128214279240105
256203268230401
512197001219618
1024189697208532


结果分析:


  • 通过 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


2019 年 5 月 09 日 11:0312011

评论 1 条评论

发布
用户头像
very good
2019 年 05 月 11 日 23:29
回复
没有更多了
发现更多内容

架构训练营第十周感悟

张锐

Dubbo微服务调用过程时序图

2流程序员

hive拉链表优化·百亿量级数据支持准实时更新

誓约·追光者

hive 实时数仓 海量数据库的设计与实践

week 10作业

a晖

堆栈神奇应用之CXO让我做一个计算器!!

架构师修行之路

数据结构 堆栈

【架构师训练营 - week10 -1】作业

早睡早起

架构训练营第十周作业

张锐

对微服务架构的理解

朱月俊

week 10 总结

a晖

Dubbo的服务注册与调用

superman

下载的附件名总乱码?你该去读一下 RFC 文档了!

Java课代表

Spring Boot

week10 作业

雪涛公子

微服务与DDD

走过路过飞过

练习 10-1

闷骚程序员

Eureka常见问题汇总及注意事项

xcbeyond

Java SpringCloud Eureka 服务注册与发现 常见问题

week10 总结

雪涛公子

架构师第十周

Tulane

OAuth 2.0

陈皮

架构师训练营Week10学习总结

Frank Zeng

微服务&DDD&中台

dony.zhang

中台 微服务 DDD

【架构师训练营】第 10 周作业

花生无翼

架构师训练营第十周作业

吴吴

对中台思维的思考

朱月俊

Dubbo微服务调用时序图及微服务架构个人见解

潜默闻雨

让我们慢慢地成长

姜海天

个人成长

架构师训练营Week10作业

Frank Zeng

架构师课程第十周总结

dongge

【架构师训练营】第 10 周总结

花生无翼

极客大学架构师训练营 --第10周

李朋

来自面试官的技术面试题

xcbeyond

Java 数据库 面试 自我介绍

面试官:您能说说序列化和反序列化吗?是怎么实现的?什么场景下需要它?

xcbeyond

Java 面试 序列化

当数据库遇见FPGA:POLARDB-X异构计算如何实现百万级TPS?_数据库_北楼_InfoQ精选文章