高压缩引擎（X-Engine）原理剖析_云原生数据库 PolarDB(PolarDB)-阿里云帮助中心

X-Engine是阿里云数据库产品事业部自研的联机事务处理OLTP（On-Line Transaction Processing）数据库存储引擎。目前已经广泛应用在阿里集团内部诸多业务系统中，包括交易历史库、钉钉历史库等核心应用，大幅缩减了业务成本，同时也作为双十一大促的关键数据库技术，挺过了数百倍平时流量的冲击。

为什么设计一个新的存储引擎

X-Engine的诞生是为了应对阿里内部业务的挑战，早在2010年，阿里内部就大规模部署了MySQL数据库，但是业务量的逐年爆炸式增长，数据库面临着极大的挑战：

极高的并发事务处理能力（尤其是双十一的流量突发式暴增）。
超大规模的数据存储。

这两个问题虽然可以通过扩展数据库节点的分布式方案解决，但是堆机器不是一个高效的手段，我们更想用技术的手段将数据库性价比提升，实现以少量资源换取性能大幅提高的目的。

传统数据库架构的性能已经被仔细的研究过，数据库领域的泰斗，图灵奖得主Michael Stonebreaker就此写过一篇论文 《OLTP Through the Looking Glass, and What We Found There》，指出传统关系型数据库，仅有不到10%的时间是在做真正有效的数据处理工作，剩下的时间都浪费在其它工作上，例如加锁等待、缓冲管理、日志同步等。

造成这种现象的原因是近年来我们所依赖的硬件体系发生了巨大的变化，例如多核（众核）CPU、新的处理器架构（Cache/NUMA）、各种异构计算设备（GPU/FPGA）等，而架构在这些硬件之上的数据库软件却没有太大的改变，例如使用B-Tree索引的固定大小的数据页（Page）、使用ARIES算法的事务处理与数据恢复机制、基于独立锁管理器的并发控制等，这些都是为了慢速磁盘而设计，很难发挥出现有硬件体系应有的性能。

基于以上原因，阿里开发了适合当前硬件体系的存储引擎，即X-Engine。

X-Engine架构

全新架构的X-Engine存储引擎不仅可以无缝对接兼容MySQL（得益于MySQL Pluginable Storage Engine特性），同时X-Engine使用分层存储架构。

因为目标是面向大规模的海量数据存储，提供高并发事务处理能力和降低存储成本，在大部分大数据量场景下，数据被访问的机会是不均等的，访问频繁的热数据实际上占比很少，X-Engine根据数据访问频度的不同将数据划分为多个层次，针对每个层次数据的访问特点，设计对应的存储结构，写入合适的存储设备。

X-Engine使用了LSM-Tree作为分层存储的架构基础，并进行了重新设计：

热数据层和数据更新使用内存存储，通过内存数据库技术（Lock-Free index structure/append only）提高事务处理的性能。
流水线事务处理机制，把事务处理的几个阶段并行起来，极大提升了吞吐。
访问频度低的数据逐渐淘汰或是合并到持久化的存储层次中，并结合多层次的存储设备（NVM/SSD/HDD）进行存储。
对性能影响比较大的Compaction过程做了大量优化：
- 拆分数据存储粒度，利用数据更新热点较为集中的特征，尽可能的在合并过程中复用数据。
- 精细化控制LSM的形状，减少I/O和计算代价，有效缓解了合并过程中的空间增大。
同时使用更细粒度的访问控制和缓存机制，优化读的性能。

X-Engine架构图

说明

X-Engine的架构和优化技术已经被总结成论文 《X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing》，在数据管理国际会议SIGMOD'19发表，这是中国内地公司首次在国际性学术会议上发表OLTP数据库内核相关的技术成果。

技术特点

利用FPGA硬件加速Compaction过程，使得系统上限进一步提升。这个技术属首次将硬件加速技术应用到在线事务处理数据库存储引擎中，相关论文 《FPGA-Accelerated Compactions for LSM-based Key Value Store》已经被2020年的FAST'20国际会议接收。
通过数据复用技术减少数据合并代价，同时减少缓存淘汰带来的性能抖动。
使用多事务处理队列和流水线处理技术，减少线程上下文切换代价，并计算每个阶段任务量配比，使整个流水线充分流转，极大提升事务处理性能。相对于其他类似架构的存储引擎（例如RocksDB），X-Engine的事务处理性能有10倍以上提升。
X-Engine使用的Copy-on-write技术，避免原地更新数据页，从而对只读数据页面进行编码压缩，相对于传统存储引擎（例如InnoDB），使用X-Engine可以将存储空间降低至10%~50%。
Bloom Filter快速判定数据是否存在，Surf Filter判断范围数据是否存在，Row Cache缓存热点行，加速读取性能。

LSM基本逻辑

LSM的本质是所有写入操作直接以追加的方式写入内存。每次写到一定程度，即冻结为一层（Level），并写入持久化存储。所有写入的行，都以主键（Key）排序好后存放，无论是在内存中，还是持久化存储中。在内存中即为一个排序的内存数据结构（Skiplist、B-Tree等），在持久化存储也作为一个只读的全排序持久化存储结构。

普通的存储系统若要支持事务处理，需要加入一个时间维度，为每个事务构造出一个不受并发干扰的独立视域。例如存储引擎会对每个事务定序并赋予一个全局单调递增的事务版本号（SN），每个事务中的记录会存储这个SN以判断独立事务之间的可见性，从而实现事务的隔离机制。

如果LSM存储结构持续写入，不做其他的动作，那么最终会成为如下结构。

LSM流程

这种结构对于写入是非常友好的，只要追加到最新的内存表中即完成，为实现故障恢复，只需记录Redo Log，因为新数据不会覆盖旧版本，追加记录会形成天然的多版本结构。

但是如此累积，冻结的持久化层次越来越多，会对查询产生不利的影响。例如对同一个key，不同事务提交产生的多版本记录会散落在各个层次中；不同的key也会散落在不同层次中。读操作需要查找各个层并合并才能得到最终结果。

因此LSM引入了Compaction操作解决这个问题，Compaction操作有2种作用：

控制LSM层次形状
一般的LSM形状都是层次越低，数据量越大（倍数关系），目的是为了提升读性能。
通常存储系统的数据访问都有局部性，大量的访问都集中在少部分数据上，这也是缓存系统能有效工作的基本前提。在LSM存储结构中，如果把访问频率高的数据尽可能放在较高的层次上，存放在快速存储设备中（例如NVM、DRAM），而把访问频率低的数据放在较低层次中，存放在廉价慢速存储设备中。这就是X-Engine的冷热分层概念。
合并数据
Compaction操作不断的把相邻层次的数据合并，并写入更低层次。合并的过程实际上是把要合并的相邻两层或多层的数据读出来，按key排序，相同的key如果有多个版本，只保留新的版本（比当前正在执行的活跃事务中最小版本号新），丢掉旧版本数据，然后写入新的层，这个操作非常耗费资源。
合并数据除了考虑冷热分层以外，还需要考虑其他维度，例如数据的更新频率，大量的多版本数据在查询的时候会浪费更多的I/O和CPU，因此需要优先进行合并以减少记录的版本数量。X-Engine综合考虑了各种策略形成自己的Compaction调度机制。

高度优化的LSM

X-Engine的memory tables使用了无锁跳表（Locked-free SkipList），并发读写的性能较高。在持久化层如何实现高效，就需要讨论每层的细微结构。

数据组织
X-Engine的每层都划分成固定大小的Extent，存放每个层次中的数据的一个连续片段（Key Range）。为了快速定位Extent，为每层Extents建立了一套索引（Meta Index），所有这些索引，加上所有的memory tables（active/immutable）一起组成了一个元数据树（Metadata Tree），root节点为Metadata Snapshot，这个树结构类似于B-Tree。
X-Engine中除了当前的正在写入的active memory tables以外，其他结构都是只读的，不会被修改。给定某个时间点，例如LSN=1000，上图中的Metadata Snapshot 1引用到的结构即包含了LSN=1000时的所有的数据的快照，因此这个结构被称为Snapshot。
即便是Metadata结构本身，也是一旦生成就不会被修改。所有的读请求都是以Snapshot为入口，这是X-Engine实现Snapshot级别隔离的基础。前文说过随着数据写入，累积数据越多，会执行Compaction操作、冻结memory tables等，这些操作都是用Copy-on-write实现，即每次都将修改产生的结果写入新的Extent，然后生成新的Meta Index结构，最终生成新的Metadata Snapshot。
例如执行一次Compaction操作会生成新的Metadata Snapshot，如下图所示。
可以看到Metadata Snapshot 2相对于Metadata Snapshot 1并没有太多的变化，仅仅修改了发生变更的一些叶子节点和索引节点。
说明
这个技术颇有些类似 B-trees, shadowing, and clones，如果您阅读那篇论文，会对理解这个过程有所帮助。
事务处理
得益于LSM的轻量化写机制，写入操作固然是其明显的优势，但是事务处理不只是把更新的数据写入系统那么简单，还要保证ACID（原子性、一致性、隔离性、持久性），涉及到一整套复杂的流程。X-Engine将整个事务处理过程分为两个阶段：
1. 读写阶段
  校验事务的冲突（写写冲突、读写冲突），判断事务是否可以执行、回滚重试或者等锁。如果事务冲突校验通过，则把修改的所有数据写入Transaction Buffer。
2. 提交阶段
  写WAL、写内存表，以及提交并返回用户结果，这里面既有I/O操作（写日志、返回消息），也有CPU操作（拷贝日志、写内存表）。
为了提高事务处理吞吐，系统内会有大量事务并发执行，单个I/O操作比较昂贵，大部分存储引擎会倾向于聚集一批事务一起提交，称为Group Commit，能够合并I/O操作。但是一组事务提交的过程中，还是有大量等待过程的，例如写入日志到磁盘过程中，除了等待落盘无所事事。
X-Engine为了进一步提升事务处理的吞吐，使用流水线技术，把提交阶段分为4个独立的更精细的阶段：
1. 拷贝日志到缓冲区（Log Buffer）
2. 日志落盘（Log Flush）
3. 写内存表（Write memory table）
4. 提交返回（Commit）
事务到了提交阶段，可以自由选择执行流水线中任意一个阶段，只要流水线任务的大小划分得当，就能充分并行起来，流水线处于接近满载状态。另外这里利用的是事务处理的线程，而非后台线程，每个线程在执行的时候，选择流水线中的一个阶段执行任务，或者空闲后处理其他请求，没有等待，也无需切换，充分利用了每个线程的能力。
读操作
LSM处理多版本数据的方式是新版本数据记录会追加在老版本数据后面，从物理上看，一条记录不同的版本可能存放在不同的层，在查询的时候需要找到合适的版本（根据事务隔离级别定义的可见性规则），一般查询都是查找最新的数据，总是由最高的层次往低层次找。
对于单条记录的查找而言，一旦找到便可以终止，如果记录在比较高的层次，例如memory tables，很快便可以返回；如果记录已经落入了很低的层次，那就得逐层查找，也许Bloom Filter可以跳过某些层次加快这个旅程，但毕竟还是有很多的I/O操作。X-Engine针对单记录查询引入了Row Cache，在所有持久化的层次的数据之上做了一个缓存，在memory tables中没有命中的单行查询，在Row Cache之中也会被捕获。Row Cache需要保证缓存了所有持久化层次中最新版本的记录，而这个记录是可能发生变化的，例如每次flush将只读的memory tables写入持久化层次时，就需要恰当的更新Row Cache中的缓存记录，这个操作比较微妙，需要精心的设计。
对于范围扫描而言，因为没法确定一个范围的key在哪个层次中有数据，只能扫描所有的层次做合并之后才能返回最终的结果。X-Engine采用了一系列的手段，例如SuRF（SIGMOD'18 best paper）提供range scan filter减少扫描层数、异步I/O与预取。
读操作中最核心的是缓存设计，Row Cache负责单行查询，Block Cache负责Row Cache的漏网之鱼，也用来进行范围扫描。由于LSM的Compaction操作会一次更新大量的Data Block，导致Block Cache中大量数据短时间内失效，导致性能的急剧抖动，因此X-Engine做了很多的优化：
- 减少Compaction的粒度。
- 减少Compaction过程中改动的数据。
- Compaction过程中针对已有的缓存数据做定点更新。
Compaction
Compaction操作是比较重要的，需要把相邻层次交叉的Key Range数据读取合并，然后写到新的位置。这是为前面简单的写入操作付出的代价。X-Engine为优化这个操作重新设计了存储结构。
如前文所述，X-Engine将每一层的数据划分为固定大小的Extent，一个Extent相当于一个小而完整的排序字符串表（SSTable），存储了一个层次中的一个连续片段，连续片段又进一步划分为一个个连续的更小的片段Data Block，相当于传统数据库中的Page，只不过Data Block是只读而且不定长的。
回看并对比Metadata Snapshot 1和Metadata Snapshot 2，可以发现Extent的设计意图。每次修改只需要修改少部分有交叠的数据，以及涉及到的Meta Index节点。两个Metadata Snapshot结构实际上共用了大量的数据结构，这被称为数据复用技术（Data Reuse），而Extent大小正是影响数据复用率的关键，Extent作为一个完整的被复用的物理结构，需要尽可能的小，这样与其他Extent数据交叉点会变少，但又不能非常小，否则需要索引过多，管理成本太大。
X-Engine中Compaction的数据复用是非常彻底的，假设选取两个相邻层次（Level1, Level2）中的交叉的Key Range所涵盖的Extents进行合并，合并算法会逐行进行扫描，只要发现任意的物理结构（包括Data Block和Extent）与其他层中的数据没有交叠，则可以进行复用。只不过Extent的复用可以修改Meta Index，而Data Block的复用只能拷贝，即便如此也可以节省大量的CPU。
一个典型的数据复用在Compaction中的过程可以参见下图。
可以看出数据复用的过程是在逐行迭代的过程中完成的，不过这种精细的数据复用带来另一个副作用，即数据的碎片化，所以在实际操作的过程中也需要根据实际情况进行分析。
数据复用不仅给Compaction操作本身带来好处，降低操作过程中的I/O与CPU消耗，更对系统的综合性能产生一系列的影响。例如，在Compaction过程中数据不用完全重写，大大降低了写入时空间的增大；大部分数据保持原样，数据缓存不会因为数据更新而失效，减少合并过程中因缓存失效带来的读性能抖动。
实际上，优化Compaction的过程只是X-Engine工作的一部分，更重要的是优化Compaction调度的策略，选什么样的Extent、定义compaction任务的粒度、执行的优先级等，都会对整个系统性能产生影响，可惜并不存在什么完美的策略，X-Engine积累了一些经验，定义了很多规则，而探索更合理的调度策略是未来一个重要方向。