一条数据的漫游奇遇记

数据库存储引擎是一个有历史的技术，经过数十年的发展，已经出现很多优秀成熟的产品。阿里巴巴 X-Engine 团队撰写的论文 "X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing"，详细讲述了团队在数据库存储引擎上所做的原创性工作，今年早些时候已经被 SIGMOD'19 Industrial Track 接收(SIGMOD 是数据库领域最重要也是最有影响力的会议之一)。本文将对这篇论文做一个前导性分析。

背景

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

数据库存储引擎是一个有历史的技术，经过数十年的发展，已经出现很多优秀成熟的产品。各式存储引擎已经在索引组织，缓存管理，事务处理，查询优化方方面面都做过细致的研究。即便如此，这个领域的演进仍在持续，每年都会涌现很多的新技术。

近年来，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 会交叠。