导语：
大多数人追寻永恒的家园（归宿），少数人追寻永恒的航向。
---- 瓦尔特.本雅明
背景
X-Engine是阿里数据库产品事业部自研的OLTP数据库储存引擎，作为自研数据库POLARDB X的储存引擎，已经广泛应用在阿里集团内部诸多业务系统中，其中包括交易历史库，钉钉历史库等核心应用，为业务大幅缩减了成本，同时也作为双十一大促的关键数据库技术，挺过了数百倍平时流量的冲击。
X-Engine团队撰写的论文X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing，详细讲述了我们在数据库储存引擎上所做的原创性工作，今年早些时候已经被SIGMOD\19 Industrial Track接收（相关阅读 & 论文下载：
前沿 国内唯一！阿里云数据库研究成果连续2次入选国际顶会SIGMOD(附论文下载)。
SIGMOD是数据库领域最重要也是最有影响力的会议之一，今年6月底即将在荷兰阿姆斯特丹举行，届时，X-Engine团队的程训焘博士（花名：闻棠）将会在会议上做一个分享，欢迎大家前来探讨。
本文将对这篇论文做一个前导性分析，帮助读者更好的理解其中的细节。
数据库储存引擎是一个有历史的技术，经过数十年的发展，已经出现很多优秀成熟的产品。各式储存引擎已经在索引组织，快取管理，事务处理，查询优化方方面面都做过细致的研究。(参考阅读：➡️观点 阿里资深技术专家：优秀的数据库储存引擎应具备哪些能力？)，即便如此，这个领域的演进仍在持续，每年都会涌现很多的新技术。
近年来，LSM(Log-Structured Merge-Tree)结构受到越来越多的关注，虽然这个技术本身出现很多年了，不算什么新事物，不过早先在KV储存系统中被应用的更多一些，近年开始在数据库储存引擎领域崭露头角，RocksDB即是典型代表。
LSM之所以变得流行，一是因为其简单，二是特点鲜明。写入模型是简单的追加，不会更新既有的资料，资料组织为简单的逻辑排序，由此带来的特点是写强而读弱，持久化资料只读的特点便于压缩。但是大多数数据库的应用场景其实都是读多写少的，直接使用LSM结构未必合适，想要另辟蹊径，须得扬长辟短。
架构
X-Engine使用了LSM作为基础架构，目标是作为一个通用的高效能低成本储存引擎，追求读写效能更为均衡，因此在其上做了大量的改进，主要围绕几个方向进行：
1. 利用先天优势，持续优化写效能。
2. 优化compaction降低对系统性能的冲击，使得系统性能表现趋于平稳。
3. 利用持久化资料层只读特点，发挥压缩优势降低成本。
4. 利用天然分层结构，结合硬件能力使用冷热分层结构，降低综合成本。
5. 利用精细化访问机制和快取技术，弥补读效能短板。
X-Engine的整体架构如下图，根据资料冷热进行分层代替LSM本身的持久化资料分层，热资料层和资料更新使用内存储存，利用了大量内存数据库的技术(Lock-Free index structure/append only)提高事务处理的效能，设计了一套事务处理流水线处理机制，把事务处理的几个阶段并行起来，提升吞吐。而访问频度低的冷(温)资料逐渐淘汰或是合并到持久化的储存层次中，结合当前丰富的储存装置层次体系(NVM/SSD/HDD)进行储存。
我们对效能影响比较大的compaction过程做了大量优化，主要是拆分资料储存粒度，利用资料更新热点较为集中的特征，尽可能的在合并过程中复用资料，精细化控制LSM的形状，减少I/O和计算代价，并同时极大的减少了合并过程中的空间放大。同时使用更细粒度的访问控制和快取机制，优化读的效能。
既然X-Engine是以LSM为基础架构的，所以一切还要从LSM本身说起。
LSM基本逻辑
一条资料在LSM结构中的旅程，从写入WAL(Write Ahead Log)开始，然后进入MemTable，这是Ta整个生命周期的第一处落脚点。随后，flush操作将Ta刻在更稳固的介质上，compaction操作将Ta带往更深远的去处，或是在途中丢弃，取决于Ta的继任者何时到来。
LSM的本质是，所有写入操作并不做原地更新，而是以追加的方式写入内存。每次写到一定程度，即冻结为一层(Level)，写入持久化储存。所有写入的行，都以主键(Key)排序好后存放，无论是在内存中，还是持久化储存中。在内存中即为一个排序的内存资料结构(Skiplist, B-Tree, etc.)，在持久化储存也作为一个只读的全排序持久化储存结构。
普通的储存系统若要支援事务处理，尤其是ACI，需要加入一个时间维度，借此为每个事务构造出一个不受并发干扰的独立视域。储存引擎会对每个事务定序并赋予一个全域性单调递增的事务版本号(SN)，每个事务中的记录会储存这个SN以判断独立事务之间的可见性，从而实现事务的隔离机制。
如果LSM储存结构持续写入，不做其他的动作，那么最终会成为如下结构：
注意这里每一层的SN范围标识了事务写入的先后顺序，已经持久化的资料不再会被修改。每一层资料按Key排序，层与层之间的Key range会交叠。
这种结构对于写入是非常友好的，只要追加到最新的内存表中即完成，为实现crash recovery，只需记录WAL(Redo Log)，因为新资料不会覆盖旧版本，追加记录会形成天然的多版本结构。
可以想见，如此累积冻结的持久化层次越来越多，会对查询会产生不利的影响，对同一个key不同事务提交产生的多版本记录会散落在各个层次中，不同的key也会散落在不同层次中，读操作诸如顺序扫描便需要查询各个层并合并产生最终结果。
LSM引入了一个compaction的操作解决这个问题，这个操作不断的把相邻层次的资料合并，并写入这个更低层次。而合并的过程实际上就是把要合并的相邻两层(或是多层)资料读出来，按key排序，相同的key如果有多个版本，只保留新(比当前正在执行的活跃事务中最小版本号新)的版本，丢掉旧版本资料，然后写入新的层。可以想见这个操作非常耗费资源。
LSM compaction操作，有几种作用，一是为了丢弃不再被使用的旧版本资料，二是为了控制LSM层次形状，一般的LSM形状都是层次越低，资料量越大(倍数关系)，这样放置的目的主要是为了提升读效能。
一般来讲，任何储存系统的资料访问都有区域性性，大量的访问都集中在少部分资料上，这也是快取系统能有效工作的基本前提，在LSM储存结构中，如果我们把访问频率高的资料尽可能放在较高的层次上，保持这部分资料量规模，可以存放在快速储存装置中(比如NVM,DRAM)，而把访问频率低的资料放在较低层次中，使用廉价慢速储存装置储存。这就是X-Engine的根据冷热分层概念。
要达到这种效果，核心问题是如何挑选合适的资料合并到更低的层次，这是compaction排程策略首先要解决的问题，根据冷热分层的逻辑，就是优先合并冷资料(访问频率相对低)。
识别冷资料有很多方法，对于不同的业务不尽然相同，对于很多流水型业务(如交易，日志系统)，新近写入的资料会有更多的概率被读到，冷热按写入时间顺序即可区分，也有很多应用的访问特征跟写入的时间不一定有关系，这个就要根据实际的访问频率去识别冷资料或是热资料。
除了资料热度以外，挑选合并资料还有其他一些维度，会对读效能产生影响，比如资料的更新频率，大量的多版本资料在查询的时候会浪费更多的I/O和CPU，因此需要优先进行合并以减少记录的版本数量，X-Engine综合考虑了各种策略形成自己的compaction排程机制。
Refined LSM
上面是LSM宏观逻辑结构，如果具体来论读写操作和compaction如何进行，就需要探讨每一层的资料组织方式, 每个LSM变种的实现各不相同。
X-Engine的memtable使用了Locked-free SkipList. 求的是简单，而且并发读写的效能都比较高。当然有更高效的资料结构，或者同时使用多种索引技术。这个部分X-Engine没有做过多优化，原因在事务处理的逻辑比较复杂，写入内存表还没有成为其瓶颈。
持久化层如何组织更显高效，这就需要讨论每层的细微结构。
资料组织
简单来说，X-Engine的每层都划分成固定大小的Extent，存放每个层次中的资料的一个连续片段(Key Range). 为了快速定位Extent，为每层Extents建立了一套索引(Meta Index)，所有这些索引，加上所有的memory tables(active/immutable)一起组成了一个元资料树(Metadata Tree)，root节点为Metadata Snapshot, 这个树结构类似于B-Tree，当然不尽相同。
需要注意的是，X-Engine中除了当前的正在写入的active memtable以外，其他结构都是只读的，不会被修改。给定某个时间点, 比如LSN=1000, 上图中的Metadata Snapshot1引用到的结构即包含了(LSN=1000)时刻的所有的资料的快照(这也是为什么这个结构被称为Snapshot的原因)。
即便是Metadata结构本身，也是一旦生成就不会修改。所有的读都是以这个Snapshot结构为入口，这个是X-Engine实现SI隔离级别的基础。之前讲过随着资料写入，累积资料越多，需要对memtable冻结，flush, 以及层与层的compaction. 这些操作都会修改每层的资料储存结构，所有这些操作，都是用copy-on-write来实现，方法就是每次都将修改(switch/flush/compaction)产生的结果写入新的Extent，然后依次生成新的Meta Index结构，乃至新的Metadata Snapshot，以一次compaction操作为例：
可以看到Metadata Snapshot 2相对于Metadata Snapshot 1并没有太多的变化，仅仅修改了发生变更的一些叶子节点以及索引节点。这个技术颇有些类似B-trees, Shadowing, and Clones（https://liw.fi/larch/ohad-btrees-shadowing-clones.pdf），如果你读过那篇论文，会对理解这个过程有所帮助。
事务处理
得益于LSM轻量化写机制，写入操作固然是其明显的优势，但是事务处理远不只是把更新的资料写入系统那么简单，这里要保证ACID，涉及到一整套复杂的流程。X-Engine将整个事务处理过程分为两个阶段：读写阶段和提交阶段。
读写阶段需要校验事务的写写冲突，读写冲突，判断事务是否可以执行或回滚重试，或是等锁。如果事务冲突校验通过，则把修改的所有资料写入Transaction Buffer, 提交阶段包括写WAL，写内存表，以及提交并返回给使用者结果的整个过程，这里面既有I/O操作(写日志,返回讯息)，也有CPU操作(拷贝日志,写内存表)。
为了提高事务处理吞吐，系统内会有大量事务并发执行，单个I/O操作比较昂贵，大部分储存引擎会倾向于聚集一批事务一起提交，称为Group Commit，能够合并I/O操作，但是一组事务提交的过程中，还是有大量等待过程的，比如写入日志到磁盘过程中，除了等待落盘无所事事。
X-Engine为了进一步提升事务处理的吞吐，采用了一种流水线的技术：把提交阶段分为四个独立的更细的阶段：拷贝日志到缓冲区(Log Buffer), 日志落盘(Log Flush), 写内存表(Write memtable), 提交返回(Commit)。我们的事务提交执行绪到了处理阶段，都可以自由选择执行流水线中任意一个阶段，这样每个阶段都可以并行起来，只要流水线任务的大小划分得当，就能充分并行起来，流水线处于接近满载状态。
另外，利用的是事务处理的执行绪，而非后台执行绪，每个执行绪在执行的时候，要么选择了流水线中的一个阶段干活，要么逛了一圈发现无事可做，干脆回去接收更多的请求，这里没有等待，也无需切换，充分的调动了每个执行绪的能力。
读操作
LSM在处理多版本资料的方式是新版本资料记录会追加在老版本资料后面，从物理上看，一条记录不同的版本可能存放在不同的层，在查询的时候需要找到合适的版本(根据事务的隔离级别定义的可见性规则)，一般查询都是查询最新的资料，总是由新的层次(最新写入)往老的层次方向找。
对于单条记录的查询而言，一旦找到便可终止，如果记录还在比较靠上的层次，比如memtable，很快便返回；如果记录不幸已经落入了很低的层次(可能是很随机的读)，那就得经历逐层查询的漫漫旅途，也许bloomfilter可以跳过某些层次加快这个旅程，但毕竟还是有更多的I/O操作。
X-Engine针对单记录查询引入了Row Cache，在所有持久化的层次的资料之上做了一个快取，在memtable中没有命中的单行查询，在Row Cache之中也会被捕获。Row Cache需要保证快取了所有持久化层次中最新版本的记录，而这个记录是可能发生变化的，比如每次flush将只读的memtable写入持久化层次时，就需要恰当的更新Row Cache中的快取记录，这个操作比较微妙，需要小心的设计。
范围扫描的操作就没这么幸运了。因为没法确定一个范围的key在哪个层次中有资料，也许是每层都有，只能扫描所有的层次做合并之后才能返回最终的结果。X-Engine同样采用了一系列的手段：比如Surf(SIGMOD\18 best paper)提供range scan filter减少扫描层数；还有异步I/O与预取对大范围扫描也有显著的提升。
读操作中最核心的是快取设计，Row Cache来应付单行查询，Block Cache负责Row Cache miss的漏网之鱼，也用来应付scan；由于LSM的compaction操作会一次大批量更新大量的Data Block，导致Block Cache中大量资料短时间内失效，带来效能的急剧抖动。
X-Engine同样做了很多的处理：
1. 减少Compaction的粒度
2. 减少compaction过程中改动的资料(见稍后章节)
3. compaction过程中针对已有的cache资料做定点更新。由此可以基本将cache失效带来的抖动降到最低的水平。
X-Engine中的快取比较多样，memtable也可算做其中一种。以有限的内存，如何恰当的分配给每一种快取，才能实现价值最大化，是一个还未被妥善解决的问题，X-Engine也在探索当中。
当然，LSM对读带来的也并非全是坏处，除了memtable以外的只读的结构，在读取路径上可以做到完全无锁(memtable也可设计成读无锁)。
Compaction
compaction操作是比较重的。需要把相邻层次交叉的key range资料读出来，合并，然后写到新的位置。这是为前面简单的写入操作不得不付出的代价。X-Engine为优化这个操作重新设计了储存结构。
如前所述，X-Engine将每一层的资料划分为固定大小的Extent，一个Extent相当于一个小的完整的SSTable, 储存了一个层次中的一个连续片段，其中又会被进一步划分一个个连续的更小的片段Data Block，相当于传统数据库中的Page，只不过是只读的，而且是不定长的。
回看资料组织一节中合并操作对元资料的改变, 对比Metadata Snapshot2和Metadata Snapshot1的区别，可以发现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积累了一些经验，定义了很多规则，而探索如何合理的排程策略是未来一个重要方向。
后记
X-Engine是阿里云智慧事业群-数据库产品事业部的重要核心技术之一。
作为相容MySQL的数据库POLARDB X的储存引擎，之前是在服务阿里集团业务中逐渐打磨成熟，今年下半年，我们将在阿里云平台上推出MySQL(X-Engine)的RDS公有云服务，为阿里云上的公有云客户提供低成本高效能的数据库服务。
