小镇的夕阳|深度 | X-Engine的In-Memory读性能优化作者：顾绅/北楼背景虽然同为LSM-tree

作者：顾绅/北楼
背景虽然同为LSM-tree架构， X-Engine的设计哲学与传统基于LSM-tree架构的Rocksdb等引擎并不完全一致，如下图所示：
设计关键点1：X-Engine磁盘上的数据，在常态下只有两层（L1/L2）， L0层是MemTable在compaction来不及的情况下暂存到磁盘上缓解内存压力时才启用的，正常情况下被冻结的MemTable可以直接和磁盘上的L1合并。
设计关键点2：在L1/L2之间的compaction合并过程中， X-Engine的冷热合并算法倾向于将热点数据保留在L1层(基于访问频度），将访问较少的数据下刷到L2层并进行压缩存储。这是一个对数据在物理上进行冷热分离的过程，其结果是L1存储的都是热点数据， L2存储的都是冷数据。对L1进行缓存时会有更高的内存利用率。
按照设计初衷， X-Engine正常运行时， Memtable中缓存了最近写入还未刷盘的数据， L1中保存了磁盘访问频度最高的数据，也大部分被内存缓存，分层之后X-Engine的读性能优化被分解为两个独立子问题：

内存MemTable部分和L1层数据读操作是CPU bound的，手段主要是优化CPU指令的执行效率和访问主存的速度。
L2层的读性能依赖于磁盘的随机读能力，对此部分的优化手段是更精准的冷热识别，其目标是最大化IOPS利用率。

考虑到Memtable部分数据量较少，在冷热识别算法精准并且内存足够缓存热点数据的前提下， X-Engine的性能整体上取决于对L1部分数据的内存查找效率，这也是今天这篇文章探讨的主题: 如何最大化命中内存时的读取性能。
读取路径存在的问题在数据集小于可用内存时， X-Engine的读性能受限于CPU资源。分析一个CPU bound程序的性能问题时，我们需要看CPU在哪些地方繁忙。按照CPU使用率的定义， CPU在执行指令时或者在等待数据时(stall) 都会处于busy状态，存储引擎的读性能优化最后都会落到两个点上：

提升CPU Cache命中率，主要靠执行线程在时间上和空间上访存的局部性。
提升CPU指令的执行效率，这一方面需要精简实现代码，减少不必要的执行路径，另一方面需要减少不同线程之间的状态同步，保证指令流水线顺畅执行。

L1层数据组织和读取过程：X-Engine将数据划分成2MB大小的Extent ， Extent内部会记录编码成16KB的Block ，每个Extent内部包含一个IndexBlock以辅助定位DataBlock 。整体看X-Engine中L1/L2层的数据组织是一个类似B+树的索引结构。如果所有操作都能命中内存，在Extent中读取一条key=X的记录，操作会按如下四个步骤执行：

ExtentMeta数组是这棵B+树的根节点，在其中二分查找定位出X所属的Extent.
Extent可以理解为一棵子树，首先需要通过一次Hash查找（查询缓存）获取到该Extent的IndexBlock 。
从IndexBlock中定位出X所属的DataBlock的Key ，并通过一次Hash查找定位到X所属的DataBlock 。
在内存中的DataBlock中查找到该记录的实际内容，并返回对应的Value.

结合上述读路径的实现逻辑，同时对X-Engine全内存命中读过程进行Perf分析之后。我们在如下三个方面进行改进尝试（1）数据页的编码及查找指令优化 (2) 降低BufferPool的管理开销（3）优化多核上的多线程运行的Cache冲刷问题，最终获得了整体124%的读性能提升。
接下来我们将详述这三个问题的根源以及我们的优化方法，最后通过实验对每一步优化手段的收益进行了评估。考虑到这三个问题在数据库存储引擎中的普遍性，这些优化方法对于InnoDB, Rocksdb等引擎也是适用的。