X-Engine

背景

笔记来自 https://www.bilibili.com/video/BV1rS4y1N7YK

X-Engine是阿里云数据库PolarDB的OLTP存储引擎（基于Mysql），主要针对电商 平台的工作负载开发，双11期间的工作负载有以下特征。

1. 活动开始时每秒交易量激增（TPS）称之为海啸问题（The tsunami problem）

海啸问题：双十一零点时的TPS增加到原来的122倍，在2018年双十一的最高峰时间段，每秒钟同事进行491000笔交易，这意味着数据库同时在处理的事务达到了七千万，阿里团队希望这样的压力下依旧能维持稳定的响应时间。

我们可以看到蓝色的线在红色的线夸张的涨幅下，仍旧维持了一个相对稳定的表现。

1. 缓存（Buffer）很快会被大量数据填满，我们称之为泄洪问题（the flood discharge problem）

泄洪问题：随着写入量的迅速增加，存储引擎的内存缓存会被大量数据迅速填满。这时，我们就需要对新增的数据进行泄洪，也就是尽快把数据转移到持久化内存中。这也意味着我们需要一个写入能力很强的存储结构。

1. 随着促销活动的转变，数据的冷热会发生迅速的切换，称之为访问热点急速变化问题（The fast-moving current problem）

数据访问局部性是缓存能够生效的关键，但是双十一中大量的整点秒杀活动，会让一些非常冷的数据变成热点数据。这时候一般数据库的存储引擎很难对这种快速的切换做出反应。从而造成缓存命中率的大幅度下降。X-Engine就是需要能够快速从持久化存储中取出新的热点数据，并且放到缓存中来解决这个问题。

访问热点急速变化问题：双十一会有各种促销活动，比如整点秒杀（seckill）活动，会使当前数据的冷热急速变化。此时数据引擎需要对数据热点的变更做出反应，快速持久化存储中取出新的热点数据。

LSM

因为电商业务涉及到大量数据的插入和修改，所以X-Engine采用了有杰出性能的LSM-Tree。其写入的操作不做原地更新，而是以追加的方式写入内存。每一次写到一定程度，即冻结一层，写入持久化存储。

一条数据->写入memtable->flush到持久化存储->经compaction操作进入持久化存储的更下层->覆盖同意key的老版本数据/同一key的新数据到来时丢弃。

真正删除老数据是在后台的compaction（合并）过程中完成的。当多个SSTable文件合并时，系统和会保留最新版本的数据，删除旧版本的数据和墓碑标记，从而释放磁盘空间。

compaction操作不断地把相邻的层次数据合并，并写入更低的层次。合并的过程实际上是吧相邻俩层数据读出，按key排序，想通的key之保留更新的版本。

LSM-Tree的特点是写强而读弱，我们可以简单理解为LSM-Tree的写入能力比B+ Tree搞一个数量级，读能力弱一个数量级。这是因为LSM-Tree的数据可能存在多个版本。PceanBase和Tidb底层都是用的LSM-Tree。

整体架构

图中上面的数据方方框就是内存，下面的数据方框就是磁盘。内存中的数据都是红色的，表示热数据，橙色表示温数据，浅黄色表示冷数据。越热的数据会越往上层放。

写入：

写入中x-engine会和其他数据库一样做一个redo log落盘操作。然后把数据写在active memtable里面。这里是一个脏页的概念，一个active memtable写满后，他会变成一个Immutable memtable。这时候Memtable就不会做改变了，Immutable memtable 会等待一个Flash操作，进入磁盘中变成持久化存储。持久化存储越上面就是越昂贵的磁盘。比如最上面是NVMe，下层是SSD，下层是HDD。磁盘的价格是由贵到便宜，价格也是由高到底。

下层之后就是依次往下合并变成一个冷数据。

读取：

首先我们要读取磁盘里面的active memtable和immutable memtable。

X-Engine总体可以分为内存中的热数据层和持久化存储的 温、冷数据层。

内存中有active memtable和多个Immutable memtable以及Read Cache和Index。

硬盘中的数据分为多层，不同层的数据通过不同的存储设备存储，每一层数据以Extent为单位组织。

X-Engine通过MVCC和2PL（二阶段锁）实现了SI（Snapshot Isolation 快照隔离）和RC隔离级别。

SI的核心特点是：事务启动时获取一个数据库快照，该事物的所有操作都基于这个快照，不会看到其他事物的修改。提交时，只有当机遇该快照的任何并发修改与该事物的修改没有冲突时才会成功提交。

SI避免了ANSI SQL-92标准定义的三种并发异常：脏读、不可重复读、幻读。读操作不会被阻塞，对于读多些少的应用场景性能表现优异。

以mysql为例，有四个标准的隔离级别：读未提交，读已提交、可重复读、串行读。其中可重复读是默认隔离级别。SI是一种实现机制，mysql在可重复读隔离级别下，通过MVCC实现了快照隔离的特性，具体来说，事务启动时会创建一个一致性快照，事务内的所有读操作都基于这个快照，不会看到其他事务提交的修改，从而保证了可重复读。

海啸问题

面对海啸问题，一个常见的思路是增加服务器的数量，横向扩展服务器集群。但这个方案在双十一场景下有俩个问题：

一是成本太高，双十一零点时TPS会激增122倍，服务器数量不可能也增加这么多倍。而是增加服务器的效果也不会很高，因为海啸问题面对的主要是写和读的混合压力，读压力比较容易扩展，写压力很难扩展，增加机器也不能很好的散开写压力。

各个阶段还是要提高CPU、线程、内存、IO等资源的利用率，在数据引擎层面提供更高的事务并发和吞吐量，来加快流转效率，避免堆积。

X-Engine主要采用了俩个措施来解决海啸问题，一个是交易的异步写入，第二个是多阶段生产线。

交易异步写入

我们把事务分为执行阶段和提交阶段。

执行阶段：

1. 查看要更新的数据是否在buffer pool中
2. 如果不在的话，读取到buffer pool中
3. 生成redo log
4. 修改数据页

提交阶段

1. 把redo log写到log buffer中
2. 把log buffer中的log落盘
3. 把数据也放入active memtable中，表示可查
4. 返回提交成功。

这就是我们常说的write ahead log（WAL）操作，redo log落盘意味着事务完成了持久化。

但是我们还需要做一个操作，把数据爷放到active memtable中，表示事务已经完成了可以被查到。

为了实现简单，大部分存储引擎，比如innodb，都会采用一个事务一条线程的方法，这种方法写入日志IO存在长时间等待。

X-Engine首先把任务分成了多种无锁写入队列。此后，大部分线程可以异步返回并处理其他交易，每个队列今流一个线程来参加多阶段流水线提交写入任务。

为什么要这样节省线程？

通常IO阶段需要线程等待较长的时间。因此我们可以执行到提交阶段后，线程就去干自己的事情。

每个队列留一个线程执行提交写入任务就ok了。

在抄告并发情况下，机器线程数也是一个限制。交易的一部写入避免了线程等待IO，可以增加线程的流转效率，从而减少甚至避免用户事务等待分配线程的情况。 redo log落盘的动作一定是要有序的。队列这种数据结构，先进先出，天然保证有序。但多个队列之间的顺序如何保证呢？

在执行阶段或者说读写阶段，我们还是一个事务一条线程来执行的。但是到提交阶段就分成了多个写入者。然后再进入了多条无锁写入队列里面，等待去进行多阶段流水线的提交过程。

那么多个写入队列的顺序如何保证呢，猜想

1. 分库或分用户，反正就是在业务层面确保写入的不相干。
2. 也可能是，一次只有一个队列写入，队列间流转。

经过验证在32核的时候，每个队列分配8个线程是表现最优的。

多阶段生产线

提交阶段分为四个独立的更细的阶段

X-Engine为了进一步提高事务处理的吞吐，在事务Group Commit的基础上，采用了一种流水线技术。

通过合理配置这四个阶段的线程数，来减少或避免对资源（如CPU、内存、IO）的等待时间从而实现，最大吞吐量。也就是避免有的阶段IO利用率高，CPU利用率低，而有的阶段则相反。

有些对多阶段生产线的解读是：事务到了提交阶段后，就可以自由选择执行流水线任意一个阶段。这样事务提交的四个阶段就可以并行起来。我认为这样是不正确的，因为这四个阶段顺序并不能颠倒

X-Engine分别限制了每个阶段的线程数。因为前俩个阶段数据和罗技的强相关新，复用第一第二个线程可以提高内存和磁盘的利用率，统一时间之允许一个线程分别执行第一第二阶段

time图中只有a线程执行1,2阶段.其他b,c,d线程争抢完成1,2阶段的任务。

图中的x箭头可能是不合理的，因为按照文中的描述，不应该会有一个线程在执行完第三个阶段之后去执行第二个阶段。

测试部分

论文的测试主要针对mysql的三个存储引擎，Innodb，rocksdb，还有X-engine进行了横向对比。因为海啸问题主要关注存储引擎的巅峰吞吐量。所以说这个测试主要是对JV接口的一个吞吐量的测试。因为Innodb没有KV接口，所以没有列入比较，因为B+相对于X-engine写入量肯定是非常弱的。（右上角）

左下角中测试交易异步写入的作用和配置多少线程数比较合适。

其中紫色，粉色，橙色和绿色是异步写入，只有线程数的差别。下面重合的三条都是同步写入。可以看到哪怕同步写入的线程数配置的再多也影响不了吞吐量。而异步的。所以X-engine选择了每个队列八条线程的方式来进行异步写入。

泄洪问题

面对泄洪问题，大促的时候瞬时的写压力向洪水一样冲击内存，内存肯定是撑不住的，要快速的把内存中的数据向下层存储转移。这个问题在一般的系统中，DBA除了增大缓冲池，没有很好的解决方法。

但是在X-Engine中，数据的向下转移表现为immutable memtable存储到硬盘和硬盘中LVM-Tree的操作。

然而这里硬盘中的LSM-Tree的compaction操作依旧是一个硬伤。

所以X-Engine主要通过优化compaction操作来解决泄洪问题。X-engine设计了多层存储结构。

第0层的快速Flush

Immutable memtable的数据会直接flush到L0层，所以L0层的数据是乱序的。那么在查找L0时，就要扫描整个L0层，这个代价是比较大的，会消耗很多IO。如果没有任何处理（所以L0层理的数据就是一个乱序的状态），那么L0层的数据会见到一定程度后直接和L1层合并。会造成大量的重复（冗余）的温数据进入更深层。

尽管L0层可能只占珍格格持久化层的百分之一都不到。但他的数据是从刚刚immutable memtable中的flash下来的，仅仅比最近添加到memtable中的数据老一点点。根据电子商务的抢时间局部性原则，L0的数据是极有可能再次被使用到的。所以说X-Engine吧L0层定义为了一个温数据层。

所以X-Engine引入了intra-L0 compaction，即只针对L0进行compaction。就是把L0层数据仅一个单独的合并操作，并排序去重，并且不写入下一层（原样写入L0层）。因为这部分数据很小，损耗也少，我们可以经常进行这个操作。

这不操作可以保证L0的温数据不会向下转移的同时，高效率降低成本（因为L0的数据很少，所以这步操作的损耗很小。

数据复用

对于非L0层的compaction，X-engine主要做了三个方面的优化

L0的数据达到阈值后，就会和L1层进行一个compaction操作向更下层去转移。

data reuse

1. ：对于没有重叠的快，不进行merge 而只改变变meta。

可以从三个粒度进行reuse，没有重叠的extent可以reuse，没有重叠的data block可以reuse，data block可以被拆分来促成reuse。

extent就是X-Engine中的数据块，每个数据块是2MB，每一层都有许多元数据索引，指向数据块，然后他们一起再去构成一个metadata snapshot，一个元数据的快照。它指向所有的数据构成一个全局的索引。这个时候我们进行一个compaction操作，这是compaction操作后的结果。

对于0层，即可用复用的extent，我们并不需要在磁盘上把它拷贝到level1层，而是可以直接修改meta index。然后生成一个全局的元数据快照即可。

extent级别的复用并不需要在磁盘上覆盖extent，而是直接修改metadata index。而data block的复用只能拷贝，即便如此也可以节省大量CPU。

绿色的块表示extent可以直接复用，紫红色表示extent需要进行分割，来支持更细力度的复用，黄色的块表示extent需要进行一个copy操作.

图中L1层和L2层要进行compaction操作，compaction操作的结果被放到L2中。

如果没有数据复用，compaction操作就会取出L1，L2的所有数据按key排序，key相同的则merge，即L1，L2的所有块都是红色。使用 data reuse的情况下，只有部分重叠的块会merge，Data Reuse会按三级粒度进行compaction。

1. extent粒度：L1的[210,280]和L2的[50,70]，都是俩层没有发生重合的部分，可以直接复用。即只改变元数据索引即可
2. data block粒度：L1的[1,35]和L2的[1,30]块重叠了。然而，重叠的仅仅是[1,25]这部分data block。所以[32,35]这部分 data block可以复用。
3. 拆分data block 粒度：L1的[80,200]和L2的多个extent重叠了。然而，这个data block的key是很稀疏的，可以看到没有在135和180之间的key。那么就可以将其拆分为[106,135][180,200]俩个data block，然后将他们和L2的[100,130][190,205]块合并，L2的[150,170]块则可以直接复用。

Extent级别的复用不需要在磁盘上拷贝覆盖extent，而是直接修改meta index。而data block的复用只能拷贝，即便如此也可节省大量的CPU。

对于数据复用的过程是在朱行迭代的过程中完成的，不过这种精细的数据复用带来的一个副作用，即数据的碎片化，所以在实际的操作的过程中也需要根据实际情况进行折中。这种精细的数据复用带来的弊端是，数据的碎片化有可能会消耗我们查询时候更多的计算资源。

异步IO

X-Engine将compaction分成Read-Merge-Write三个阶段，通过实现异步IO，来提升效率。

在Extent层次，一个compaction操作包含三个独立的阶段

1. 从持久化存储中取出俩个extent
2. 合并
3. 把合并的extent写入持久化存储

其中1,3俩步都是IO操作，2啧是计算铭感的操作。X-engine在1,3使用异步IO请求，2作为1的回调函数来执行。当多个compaction操作并发执行时，2会被其他步骤覆盖来隐藏IO。

FPGA offloading

将compaction offload到FPGA中执行，从而降低了Compaction对CPU的资源消耗。

随着IO性能的不断提高，很多传统的一IO为瓶颈的设计的数据库算法主键转变为计算资源的限制；反之亦然。阿里团队发现LSM-Tree存储引擎中的compaction操作正是由IO瓶颈转换为计算瓶颈的例子。

所有对compaction的操作都放在一个优先级队列里。一个具有频繁删除操作的案例中，对删除的compaction放在最高优先级，其他的compaction由上到下优先级依次递减。

删除案例是案例的一个实例，每当要被删除的记录数达到阈值，就会触发一次针对删除这些记录的compaction操作。而且这个compaction操作是最高优先级的，为了防止垃圾数据对存储空间的浪费。（查看源码，实际上X-Engine定制化了一个专用于删除的compaction，作为一个参数传入的compaction函数。）

实验

解决泄洪问题主要是对compaction的优化。

FPGA提升了27%的吞吐量并且大大提升了稳定性。电子上午的热点数据很集中，data reuse在记录重复率搞的情况下效果非常好。

访问热点急速变化

结构

面对访问热点急速变化问题，通常DBA是没有任何优化方法的，数据突然变热到数据完全进入缓存的期间，必然出现响应时间的上涨。

访问热点急速变化是一个纯粹的读方面问题，是LSM-Tree的弱项，因此要对整个读方法进行优化。

X-Engine对数据块、索引、缓存进行了一系列定制化的设计，来保证读效率。

对于LSM-Tree中影响非常大的compaction操作，X-Engine还涉及了增量缓存替换来减少其对缓存命中的影响。

Extent和其他LST-Tree的SSD，sorted string table非常像。

在电子商务中存在非常多更新DDL的操作，比如最常见的新增栏位。在有了schema中的这个version之后，我们可以在新增栏位的时候不需要去修改每个老extent中的schema

• data block 以行的形式存储数据
• schema中存储的是各个column的属性
• index存储每个data block的偏移量
• scheme带有一个version，为了在更新scheme的时候不需要修改旧数据。
• 每个extent 2MB，每个Data block约16KB
• extent越小，就越容易调度和复用，但管理成本也会随之上升。设为2MB，是综合考虑compation中数据复用和后面要介绍的增量缓存替换的最优解。

X-Engine的每层都划分了固定大小的Extent，存放每层数据中连续片段（key Range）。为了快速定位extent，为每层建立了一套索引（Meta Index），所有这些索引加上所有的memory table（active immutable）一起组成了一个元数据树，root节点为metadata snapshot

X-engine中除了当前正在写入的active memtable以外，其他结构都是只读的，不会被修改。

X-engine的所有读都是以快照的结构为入口。

优化缓存

X-Engine针对但记录查询引入了Row Cache，在所有持久化的层次数据上做了一个缓存，在memory table中没有命中的单行查询，在Row cache中也会被捕获。

Row Cache负责单行查询，Block Cache负责 Row cache的漏网之鱼。

俩类缓存在不同的维度上面劲量的去保证数据的命中率，着重保证单行数据查询。

多版本元数据索引

X-Engine的meta Index用来记录LSM tree结构的变化。LSM-Tree中每个subtable都有meta index，它起始于一个根节点，并在每次更新后创建新的节点。

如右图L0的extenti，它对应meta snapshotv，当extenti被compaction之后创建新的meta snapshotv+1，snapshotv+1只需要指向原来的extenti而不需要产生实际的I/O（extenti的位置也不需要改变），同时cache的数据也不需要变化。同时这样的copy on write结构使得事务可以访问任意版本的数据，避免了锁的开销。X-Engine中有GC机制类清理过期的snapshot。

增量缓存替换

X-Engine的增量缓存替换降低compaction对cache的影响。

原LSM-Tree中，当SST发生compactio时，对应内存中的数据会失效，造成突然的Cache miss

X-engine的增量缓存替换会在compaction的时候检查一个block是否被cache，如果是，则将chache中的内容替换为merge之后的block，可以有效缓解compaction 对cache命中率带来的影响。

多版本memtable

X-Engine对memtable做了一点简单的优化。

未优化时，如果多次更新同一个key，那么这个key会以<key,sequence_number>的形式存在memtable中存储，如果要查找最新的key，可能需要读取多个旧值。

X-Engine中所有内存数据结构是一个跳表并且不进行整理，因此多次频繁更新同一个key的话，那么这个key会存在多个版本的数据，虽然查找内存中的数据是非常快的，但是存在多个版本数据的时候我们可能依旧要的是读到多个旧值。

X-Engine的multi-version memtable会将同一个key的不同版本单独链起来。这样skiplist中就不会出现一个key的多个版本，同一个key的多个版本按照旧组织排序，最新的key可以被最快访问到。

总结

范围查找X-engine是要弱于Innodb的，所以选用LSM-Tree放弃范围查找的部分性能是X-Engine的可以接受的折中方案。