研究背景
X-Engine 是一种基于 Log-structured Merge Tree (LSM-tree) 的存储引擎，较基于 B-tree 一族的其它存储引擎而言年轻很多，所以在实践中遇到问题也更多，对研究的需求也更大。LSM-tree 是 1996 年由美国计算机科学家 Patrick O'Neil 等人提出的一种数据结构，和 B-tree 相比，它拥有更快的写入性能和层次化的存储结构，能够同时利用好 DRAM 内存的高性能和持久化存储的高容量。尤其是 LSM-tree 的分层存储结构，可以天然地利用数据局部性将热数据和冷数据区别开，方便压缩算法有的放矢，有机会在降低整体成本的情况下，实现同样优秀的性能。但是，与几乎所有的计算机数据结构和系统设计一样，有得必有失。LSM-tree 难以避免的在读性能、I/O 写放大和空间效率上面对挑战。
写路径上的罗生门
首先，LSM-tree 使用了能够支持快速写入的 copy-on-write （CoW）方式来存储新增数据。顾名思义，假如我要使用 CoW 来更新一条记录，我不需要定位存储引擎中该条记录的地址并将它读取出来，只需要直接将我要更新的内容（例如，key = 100, value = value +100）写入内存和日志（直接写磁盘）即可。这样整个写入操作就像记日记一样，我只需要在日记本的最后一个空白页上新增内容即可，至于这个日记本已经写了多少页，或者以前的某页里面写了什么，我都不需要管。所以，LSM-tree 的写入操作代价很低，而且与数据库已存数据无关，无论这个数据库已经存了多少数据了，运行了多少天，写一条记录永远是这么快。同理，如果我需要删除一条记录，我只需要新插入一条反记录即可。
那么问题来了，读记录的时候我难免要去检查一下这条记录的原始数据在哪里，是什么，它有没有更新，在哪里，是什么，然后把所有这样的碎片合并在一起，我才知道这条记录到底是什么（例如，key == 100， value = 0 + 100）。这个过程显然是比较费时的，不如我直接根据索引读一份数据来得快。而且，绝大部分的数据库是需要服务大量查询的，帮用户查数据才是数据库的主要工作，用户存数据就是为了有朝一日要读取它。LSM-tree 涉嫌拣了芝麻，丢了西瓜。
问题还不至于此，因为在数据库中所有的数据最终都要落盘来实现持久化存储，那么我在内存中新写入的记录就需要时不时地刷入到磁盘里。刷盘时，反正都要做 I/O 写，我们可以把新数据与旧数据直接合并到位，这样就把碎片控制住了，同时保持了磁盘上数据的有序，方便读取。可是，当盘上数据越来越多时，这样的合并会越来越昂贵，在不能按字节寻址的存储器件上，我们必须读入所有需要参与合并的页，完成合并，并将这些页写回。随着数据增多，我们要读的页也会越来越多，整体代价也就越来越大。我们称这个问题为『写放大』。除了对性能的影响外，写放大也会给 SSD 盘本身的 endurance 带来压力，如果写放大过高，会提高云厂商的服务成本。
为了解决写放大问题，LSM-tree 在磁盘上已经进化出了一种分层存储结构。新数据先写在『零层』，零层我们给他一个非常小的容量，只存刚刚刷下来的数据。因为数据局部性的缘故，零层的数据有很大概率会被访问到，那么通过限制容量，无论怎么访问，点读也好，扫描也罢，它总共就这么大点地方，不会慢到哪里去。当零层容量饱和时，我们将它的内容与『壹层』中的数据合并。壹层比零层更大，比如大10倍。那么理论上，这次合并，最多需要读取和写回壹层中十分之一左右的数据，不会更大了。写放大，也就被我们限制住了。当『壹层』也满了的时候，我们使用同样的方法继续往下刷，刷出『贰层』、『叁层』等等等等，以此类推。每一层的容量，比上一层大10倍，整个存储中每层的大小呈指数级增长。有了层次化的存储，配合合并操作，写放大就这样被控制住了。对于数据库系统中的很多问题，我们往往不太可能把它彻底解决掉，而是将其控制在一定的可接受的界限内即可。
分层控制住了写放大，但是新的问题又来了，合并算法本身是一种数据密集型算法，它需要读取多路数据，然后进行相对简单的合并计算，再将合并结果写回去，整个过程其实本质上读写很多，对存储带宽的消耗非常大，也会给 CPU 流水线带来很多的 I/O 等待、内存等待等气泡，从而降低 CPU 流水线的执行效率，拖慢整个系统。单次跑一下还好，如果频繁跑，会对系统性能有很大影响。而且它即不处理查询，也不处理新增数据，完全是个看起来不必要的背景操作。这种合并操作，我们叫他『Compaction』。在 LSM-tree 引擎中，compaction 不仅肩负着层与层之间合并数据的任务，还肩负着为了删除操作将反记录与真实记录合并从而实现删除的任务等等，是一种多功能的重要操作，但它的成本真得不低。
到此为止，LSM-tree 在写路径上的各个部分都已经悉数登场了，而这片江湖上的恩恩怨怨才刚刚开始。为了服务好写越来越多的 workload，LSM-tree 为了加速写可谓是不遗余力，基本上所有的设计都向写路径的性能做了倾斜，让写入看上去十分美好，实际上也开了一闪罗生门，门后惨象环生。具体怎么惨，下文详述。
读路径上带着镣铐的舞蹈
LSM-tree 上的读路径，从出生就带着镣铐。因为 CoW 的使用，读一条记录实际上需要把这条记录所有的增量碎片都找到。因为横跨内存和磁盘两种介质和有层次化的存储，这些碎片可能藏在各种犄角旮旯里面。更惨的是，如果是读一个范围内的记录，俗称 range scan，因为 LSM-tree 的每一层的 key range 是交叠的，那么一个 range 内的数据就很有可能会落在所有的层次上，为了把他们都找到，我们就需要每层都去读，这个工作量也不小。
为了解决这个问题，目前的 LSM-tree 引擎把各种经典技术都用上了：索引、cache。但是为了提高索引和 cache 的效率，让他们一直发挥比较好的作用，难度不小。以 cache 为例，X-Engine 中使用了两种经典的 cache，一种是 row cache，缓存记录级别的热数据，一种是 block cache，缓存数据块级别的热数据。Row cache 可以加速点查询，block cache 可以加速 range scan，一切看上去都是很完美的芭蕾舞。然而，当 compaction 被大王叫来巡山的时候，危险就发生了。因为 compaction 会重新组织数据块里面的内容，干掉一些老的 block，生成一些新的 block，传统的 cache 替换策略对老的 block 做的访问统计会失效，而新的 block 它不认识，没统计信息。此外，compaction 还会移动数据。这两点加起来，只要 compaction 巡了一次山，cache 里面缓存中的记录就有很大可能出现大面积失效，导致原本可以命中 cache 查询，不得不去访问磁盘，造成严重的延迟尖刺。
热数据的麻烦还不仅仅来源于 cache，因为热数据经常会被大量更新，而 X-Engine 为了实现一个 OLTP 数据库的 ACID 特性，使用了 MVCC 的并发控制方法，会为一条热数据上存上非常多的版本，这样的设计实际上造成了一条逻辑记录可能会有特别多的物理分身。这个现实无论是对承接新写入数据的 memtable（经常被实现为跳跃链表），还是索引，还是 compaction，都是一个很烦人的刺头，硬生生地通过放大数据的体量来造成各种各样的问题。
除了上述由于 LSM-tree 或者数据库的机制带来的问题意外，这些涉及到的数据结构本身的设计和实现也有很大的挑战，比如 cache 的分桶策略、锁的管理、跳跃链表和索引的查询效率、数据结构针对多核处理器的并行优化等等等等，都是有很大发力空间的坑。除了读路径的问题，LSM-tree 上还有删除效率的问题、空间效率的问题等等，此处不再详述，详见相关论文。
学术成果与产学研互动
X-Engine 团队为了解决上述问题做出了很多优化，申请了大量专利，其中的很多技术也作为学术成果在数据库和存储领域的顶会内完成了发表。
2019年，我们在 ACM SIGMOD 的 industrial track 中发表了一篇介绍 X-Engine 来龙去脉的论文《X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing》。在这篇文章中，我们介绍了 X-Engine 这种面向写入优化的存储引擎为什么在工业界人气飙升，为什么阿里巴巴的电商场景需要这样的引擎，主要原因就是每次电商促销所带来的富含新增数据的高流量。面对这样的挑战，我们首先将问题拆解为了具体的数据库技术问题，如处理高流量所需的并行写入流水线、数据量海啸快速占满内存对数据刷盘带来的压力、促销导致的数据热点范围频繁变化带来的加速读的挑战等等。为了解决这些实际的技术问题，我们介绍了 X-Engine 做了怎么样的技术选型，采取了哪些优化，以及每项优化所带来的实际效果。这篇论文是中国大陆公司首次在 SIGMOD 上发表数据库内核上的工作。详情请见论文（在 ACM DL 中可免费下载）。
Alibaba runs the largest e-commerce platform in the world serving more than 600 million customers, with a GMV (gross merchandise value) exceeding USD 768 billion in FY2018. Online e-commerce transactions have three notable characteristics: (1) drastic increase of transactions per second with the kickoff of major sales and promotion events, (2) a large number of hot records that can easily overwhelm system buffers, and (3) quick shift of the "temperature'' (hot v.s. warm v.s. cold) of different records due to the availability of promotions on different categories over different short time periods. For example, Alibaba's OLTP database clusters experienced a 122 times increase of transactions on the start of the Singles' Day Global Shopping Festival in 2018, processing up to 491,000 sales transactions per second which translate to more than 70 million database transactions per second. To address these challenges, we introduce X-Engine, a write-optimized storage engine of POLARDB built at Alibaba, which utilizes a tiered storage architecture with the LSM-tree (log-structured merge tree) to leverage hardware acceleration such as FPGA-accelerated compactions, and a suite of optimizations including asynchronous writes in transactions, multi-staged pipelines and incremental cache replacement during compactions. Evaluation results show that X-Engine has outperformed other storage engines under such transactional workloads.
论文摘要
2020年，与 AIS 软硬件结合开发团队合作，我们在存储领域的顶会 USENIX FAST 2020 上发表了我们利用 FPGA 异构计算技术来加速 X-Engine 中很多问题的罪魁祸首—— compaction 的工作《FPGA-Accelerated Compactions for LSM-based Key-Value Store》。在这项工作中，我们首先系统研究了 compaction 对 LSM-tree 存储引擎在 CPU、内存、磁盘等资源的消耗上有什么特征，分析了 compaction 的算法，发现 compaction 算法在合并较短的记录的时候竟然是受限于 CPU 的。其原因一方面是因为 compaction 对计算的需求，另一方面也是因为这些年来磁盘带宽有了显著的增长。所以，我们提出将 compaction 算法 offload 到 FPGA 加速卡上，并在 FPGA 上设计和实现了一套高效的流水线，和 CPU host 实现了快速的交互，也实现了 compaction 算法的加速。这项工作所做的探索让我们看到了计算型存储技术的红利。近年来，随着 SSD 的不断发展和处理器的微小型化，市场上出现了类似 SmartSSD 这样的计算型存储设备，其核心优势是把较小的 ARM CPU 处理器或者 FPGA 芯片直接嵌入 SSD 内部，让部分计算任务不需要离开 SSD 就能完成，省去了 I/O 和 CPU 的开销。因为 SSD 内部的访存带宽比外部的 I/O 快几十倍，计算型存储特别适合处理类似 compaction、scan 等相对而言更加访存密集的操作。今年阿里云数据库团队在 FAST 上收获了大丰收，投稿的 3 篇论文全部被录用，而 FAST 是个比较小而专的会议，今年一共也仅有 23 篇论文。
Log-Structured Merge Tree (LSM-tree) key-value (KV) stores have been widely deployed in the industry due to its high write efficiency and low costs as a tiered storage. To maintain such advantages, LSM-tree relies on a background compaction operation to merge data records or collect garbages for housekeeping purposes. In this work, we identify that slow compactions jeopardize the system performance due to unchecked oversized levels in the LSM-tree, and resource contentions for the CPU and the I/O. We further find that the rising I/O capabilities of the latest disk storage have pushed compactions to be bounded by CPUs when merging short KVs. This causes both query/transaction processing and background compactions to compete for the bottlenecked CPU resources extensively in an LSM-tree KV store.
In this paper, we propose to offload compactions to FPGAs aiming at accelerating compactions and reducing the CPU bottleneck for storing short KVs. Evaluations have shown that the proposed FPGA-offloading approach accelerates compactions by 2 to 5 times, improves the system throughput by up to 23%, and increases the energy efficiency (number of transactions per watt) by up to 31.7%, compared with the fine-tuned CPU-only baseline. Without loss of generality, we implement our proposal in X-Engine, a latest LSM-tree storage engine.
论文摘要
除了上述已经发表的成果，我们还探索了使用机器学习技术来预测 compaction 前后的数据访问趋势，以解决传统 cache 替换策略被干扰的问题；我们也探索了在 X-Engine 内部应用细粒度、自适应的调度算法，来改善 compaction 的执行时机，从而提高系统性能的稳定性；我们也优化了内存分配策略、cache 结构和访问方式等等底层细节，旨在从根本上显著提高 X-Engine 的性能。目前，这些工作还在进一步的研发中。
X-Engine 自 2019 年进入数据库界国际顶级学术圈以来，通过向学术界介绍阿里巴巴的应用场景以及技术挑战，尤其是 X-Engine 引擎本身所面对的技术挑战，已经吸引了很多专家学者的目光。我们所抛出的 LSM-tree 删除性能差的问题，已经吸引了来自波士顿大学和哈佛大学的研究者提出了新的优化技术，相应学术成果将发表在最近的学术会议中。在国内，X-Engine 团队与阿里自家的达摩院数据库存储与实验室、浙江大学 AZFT 实验室孙建玲教授、中科院计算所陈世敏教授等学者和研究人员长期合作，共同研究 LSM-tree 相关的技术问题，并且不断产出优质的学术成果。通过学术合作，目前已经发表了 FAST 一篇，VLDB 一篇。除此以外，我们追求将学术研究探索出来的新技术真正落地在 X-Engine 系统内核中，为提高 X-Engine 产品力贡献力量。
未来研究方向
未来，X-Engine 团队会针对生产实践中遇到的各项技术难题展开公关，也会紧跟新的技术趋势，探索新型硬件（如 NVM，FPGA 等）在 X-Engine 上的应用。首先，分布式是数据库产品的潮流。在未来，用户不需要再操心分库分表或者扩展性上的麻烦，而是买一份分布式数据库，把所有任务都交给它后就高枕无忧了。X-Engine 团队当前正致力于下一代分布式数据库 PolarDB-X 的研发，旨在为用户提供一款高性能、低成本、伸缩性好的分布式数据库产品，将阿里多年来积累的数据库技术红利分享给阿里云上的客户们。在这个方向上，我们会着力于私有协议、分布式事务处理、分布式负载均衡、故障恢复等重要技术问题。其次，我们认为，X-Engine 的内存部分可以看成一个内存数据库，应该与处理器、DRAM 内存等硬件深度融合，突破性能瓶颈。具体的研究方向包括 cache-conscious 的高性能内存索引、利用 SIMID 技术（Single Instruction Multiple Data）来加速内存数据结构访问、降低内存锁开销等。最后，对于时下的热点人工智能，我们也不会放过。目前，我们已经探索了机器学习技术在 cache 替换上的应用，未来我们会探索智能调参、智能 compaction 调度、智能索引等 AI for DB 技术。我们希望利用人工智能技术，将复杂的数据库运维转换为十分傻瓜的简单操作，降低用户使用和维护数据库的难度，同时改善数据库的性能。
作为一款重量级的数据库基础软件，X-Engine 虽然看上去只是负责数据增、删、改、查这样平淡无奇的操作，但正是因为这些操作足够基础，X-Engine 才会被集成与 MySQL 内核和分布式数据库 PolarDB-X 中，我们的每一项优化也拥有了更大的影响力，直接决定着所有上层应用的安全、稳定和性能。欢迎有志于从事国产自研存储引擎研发的同学加入我们。
