强强联袂！腾讯云 TDSQL 与国双战略签约，锚定国产数据库巨大市场

LSM-Tree（Log Structured Merge Tree）是数据库领域内较高效的 key-value 存储结构，被广泛应用于工业界数据库系统，如经典的单机 kv 数据库 LevelDB、RocksDB，以及被诸多分布式 NewSQL 作为底层存储引擎。

本期将由腾讯云数据库高级工程师韩硕来为大家分享基于 LSM-Tree 存储的数据库性能改进，重点介绍近年来学术界对 LSM-Tree 的性能改进工作，并探讨这些改进措施在工业界数据库产品中的应用情况以及落地的可能性。以下是分享实录：

# 1. LSM-Tree 基本结构

LSM-Tree 全称为“Log Structured Merge Tree”，是一种基于磁盘存储的数据结构。1996 年 Patrick O’Neil 等人在信息系统期刊上发表了一篇题名为“Log Structured Merge Tree”的论文，首次提出 LSM-Tree 结构。相比于传统的 B+树，LSM-Tree 具有更好的写性能，可以将离散的随机写请求转换成批量的顺序写操作，无论是在 RAM、HDD 还是在 SSD 中，LSM-Tree 的写性能都更加优秀。

作为高效的 key-value 存储结构，LSM-Tree 已被广泛应用到工业界数据库系统中，如经典的单机 kv 数据库 LevelDB、RocksDB，以及被诸多分布式 NewSQL 作为底层存储引擎，近日发布的 TDSQL 新敏态引擎存储模块也运用了 LSM-Tree 结构。LSM-Tree 结构有较多优点：写性能强大、空间利用率高、较高的可调参特性、并发控制简单、有完备的修复方案等。

LSM-Tree 的本质是基于 out-place update 即不在原地更新。下图展示了 in-place update 即原地更新与 out-place update 即不在原地更新的区别。

在 in-place update 中，数据更新操作是将数据的新值直接覆盖旧值，但会带来随机读写问题。在 out-place update 中，数据更新操作则是将新值按时间顺序追加到文件末尾，通常会带有版本号用于标记新值或旧值，一般为顺序写，因此写性能更好，但缺点是会产生冗余数据，在读性能和空间利用率上也无法与 in-place update 相比。

当前主流的 LSM-Tree 基本结构如下图，分为内存和磁盘两部分。内存采用 MemTable 数据结构，可以通过 B+树或跳表实现。MemTable 用于接受最新的数据更新操作，维护内部数据 in-tree 逻辑上的有序。磁盘中的部分数据存储物理有序。数据按照层进行堆放，层次越往下，数据写入的时间就越早。每层内部按是否有序可划分为一个或多个 sorted run。一个 sorted run 内部的数据必定有序（通常指物理上有序）。sorted run 数据可进一步划分为不同的 SSTable。当 MemTable 中的数据写满时，其会向 L0 进行落盘操作即 Flush 操作。如果 LSM-Tree 的某一层也达到容量阈值，就会向下合并，将同样的 key 的过期版本清除，即 compaction 操作。

RocksDB 是基于 LSM-Tree 的存储引擎，其基本结构如下图。它与 LSM-Tree 基本结构在主体上保持一致，不同点在于 RocksDB 的内存中增加了 Immutable MemTable 部分，这是用于 Flush 操作的写缓存机制。当 MemTable 中的数据写满时，会先暂存到 Immutable MemTable 中，再通过后台的异步线程将 Immutable MemTable 慢慢落盘到磁盘中的 SST 基本件。RocksDB 中还增加了 WAL 日志，用于 crash 时的数据恢复。

LSM-Tree 支持的查询可分为点查与范围查询两大类，对应的执行方式如下：

● 点查：先查 MemTable，再从 SST 中的 Level0、Level1…...一层层向下探查，找到数据就返回。由于上层数据必定比下层数据的版本新，因此返回的都是最新数据。

● 范围查询：每一层都会找到一个匹配数据项的范围，再将该范围进行多路归并，归并过程中同一 key 只会保留最新版本。

**LSM-Tree 性能的衡量主要考虑三类因素：空间放大、读放大和写放大。**

第一类因素是空间放大。在 LSM-Tree 中所有写操作都是顺序追加写，数据的更新操作则是通过创建一个新的空间来存储新值，即 out-place update。与此同时，因为旧值不会立即被删除，因此会占用部分空间。实际上这部分冗余数据占用空间的大小要远大于有效数据本身，这种现象被称为“空间放大”。LSM-Tree 会利用 compaction 操作来清理旧数据从而降低空间放大。

第二类因素是读放大。在 LSM-Tree、B+树等外存索引结构中，进行读操作时需要按从上到下的顺序一层层去读取存储节点，如果想读一条数据，就会触发多次操作，即一次读操作所读到的数据量实际上要远大于读目标数据本身，从而影响读性能，这种现象被称为“读放大”。

第三类因素是写放大。在 LSM-Tree 中，compaction 操作会将多个 SST 文件反复读取，合并为新的 SSTable 文件后再次写入磁盘，因此导致一条 kv 数据的多次反复写入操作，由此带来的 IO 性能损失即写放大。

LSM-Tree 的初衷是想通过空间放大和读放大来换取写放大的降低，从而达到极致的写性能，但也需要做好三方面因素的权衡。EDBT 2016 的一篇论文首先提出 RUM 猜想（R 为 read，U 为 update，M 为 memory usage，RUM 为三者缩写）。该论文认为，三者之间存在权衡关系，无法使得三个方面的性能都达到最优，因此必须在三者之间进行有效权衡。

以 compaction 操作为例，其目的是保证数据的局部有序和清理数据旧值，即一个 sorted run 内部的多个 SST 文件中的数据是有序的，从而降低读放大。对一个查询而言，在一个 sorted run 中至多只需要读取一个 SST 中的一个数据块。

如果完全不做 compaction 操作，即一直顺序写，LSM-Tree 就会退化为 log 文件，这时写性能达到最佳。因为只需要顺序写 log 即可，不需要做任何操作。但读性能将会处于最差状态，因为在没有任何索引、无法保证有序性的情况下，每次想读到固定的数据项，就需要扫描所有的 SST 件。

如果 compaction 操作做到极致，实现所有数据全局有序，此时读性能最优。查询时只需要通过索引和二分法即可迅速找到要读的键值的位置，一次 IO 操作即可完成，但代价是需要频繁进行 compaction 操作来维持全局有序状态，从而造成严重的写放大，即写性能变差。

**这就延伸出两种 compaction 策略：**

● Tiering compaction：较少做 compaction 操作，有序性较弱，每一层允许有多个 sorted run。

● Leveling compaction：更频繁的 compaction 操作，尽可能增强有序性，限制每一层最多只有 1 个 sorted run（L0 层除外）。

# 2. Compaction 优化策略与分析

Leveling compaction 策略中，每层只有一个 sorted run，sorted run 内部的数据保持物理有序。具体实现上我们以 RocksDB 为例。一个 sorted run 可以由多个 key 不重叠且有序的 SSTable files 组成。当第 L 层满时，L 层会选取部分数据即部分 SSTable，与 L+1 层有重叠的 SSTable 进行合并，该合并操作即 compaction 操作。

Tiering compaction 策略中，每层可以有至多 T 个 sorted run，sorted run 内部有序但每层不完全有序。当第 L 层满时，L 层的 T 个 sorted run 会合并为 L+1 层的 1 个 sorted run。因为每层允许有多个 sorted run，因此 SST 文件间可能会存在数据范围的重叠，compaction 操作的频率会更低，写性能也会更强。

两种 compaction 策略各有优劣。Tiering compaction 因为 compation 操作频率低，过期版本的数据未能得到及时清除，因此空间利用率低，由此带来的查询操作的代价比较高。在极端情况 log file 即完全不做 compaction 操作时，写入性能最优。Leveling compaction 则会更频繁地做 compaction 操作，因此数据趋向更有序。极端情况 sorted array 即数据达到全局有序时，此时查询性能和空间利用率最优。

SIGMOD 2018 的一篇论文对上述两种 compaction 策略进行了详细的理论分析，分析结果归纳为下表，其分析结果与前述一致。理论分析过程如下：

先从写入操作复杂度进行分析。I/O 以 block 为基本单位，一次 I/O 平均读写 B 条 kv，因此一条 kv 写一次磁盘的代价可以表示为 1/B。在 leveling compaction 策略中，第 i 层向第 i+1 层最多合并 T 次，在第 j 层合并到第 i 层时，其可被后续的数据项反复进行 t-j 次合并。由此可得，每条 KV 在第 i 层即任意一层被平均 IO 的读写次数为 t/2 次，即 O(T)。从 MemTable 一直向下合并到最后一层即第 L 层，会得到平均写磁盘数即“TL/B”。

以下图为例，每合并一次，第 i 层的增量不会超过 1/T。第 i 层通道从空到满，其最多向下合并 t 次，因此每条 kv 在每层平均被合并 2/T 次。

在 Tiering compaction 策略中，每条 KV 在第 i 层时只会被合并一次，因此从 MemTable 一直向下合并到最后一层即第 L 层，会得到平均写磁盘数即 L/B。

在第 i-1 层向第 i 层合并时，会在第 i 层产生一个新的 sorted run，平均每条 kv 在每层只会被合并一次。

再从空间放大率进行分析。space-amplification 定义为：过期版本的 kv 数与有效 kv 总数之比。在 Leveling compaction 策略中，最坏的情况为前 L-1 层的每条数据在最后一层即第 L 层中都各有一条未被清除的过期版本数据。每层容量为比值为 T 的等比数列，根据等比数列求和公式， 第 L−1 层的 kv 数量占总 kv 数的 1/T，最后一层则占 (T−1)/T，因此空间放大为 1/T，空间放大率较低。

在 Tiering compaction 策略中，允许每层最多有 T 个 sorted run，最坏情况下最后一层的 T 个 sorted run 之间都是每个 kv 的不同版本，即一条 kv 在最后一层的每个 sorted run 都出现一次，共 T 个不同版本，因此空间放大为 O(T)。

Leveling compaction 的空间放大系数为 1/T，因此空间利用率较高。Tiering compaction 在最坏情况下，最后一层的每个 sorted run 都是冗余数据，空间利用率较差。

**再从查询角度进行分析。点查使用 Bloom filter 进行过滤，将其分成两类：**

● 读穿透，即查询数据不存在。

● 假设知道每次发生假阳性的概率，如果判定结果为假阳性，则需要读一次磁盘。

在 Leveling compaction 策略中，每层只有一个 sorted run，实现完全有序，因此每层只需要查询一次 Bloom 过滤器。根据二项分布期望公式，推导出的期望读盘次数为 L×e 的-m/n 次方。

在 Tiering compaction 策略中，每层最多有 T 个 sorted run，最多可能查询 T 次 Bloom filter，在前述结构基础上乘以 T 的系数，根据推导出的期望读磁盘次数，其查询性能落后于 Leveling compaction。

如果查询数据存在，因为发生假阳性的概率远小于 1，因此大部分情况下，无论是 Tiering compaction 还是 Leveling compaction，都只需要读一次盘。

再从范围查询角度进行分析。该论文将范围查询分为短范围查询和长范围查询。短范围查询指返回 block 数量的大小不超过最大层数范围的两倍；反之则为长范围查询。

通过统计公式发现，短范围查询在归并前的各版本数据趋向于均匀分布在各层，因此 Leveling compaction 和 Tiering compaction 的查询复杂度分别为 O(L)和 O(T×L)。长范围查询在归并前各版本数据大部分来自最后一层，因此上述两种策略的代价分别为返回 block 数的大小、返回 block 数的大小再乘以 T，因此 Leveling compaction 比 Tiering compaction 的读性能更好。

**通过上述理论分析，可以得到如下结论：**

● Tiering compaction 的写放大低，compaction 频率低，其缺陷为空间放大高、查询效率低，更利于 update 频繁的 workload；Leveling compaction 的写放大高，compaction 操作更频繁，但空间放大低，查询效率高。

● 尽管 Tiering compaction 和 Leveling compaction 的空间放大不同，但导致空间放大的主要原因相同，即受最下层的过期版本数据影响。

● 越往下的层，做一次 compaction 的 I/O 代价越高，但发生的频率也更低，不同层之间做 compaction 的期望代价大致相同。

● 点查、空间放大、长范围查询的性能瓶颈在 LST-tree 的最下层，而更新操作则更加均匀地分布在每一层。因此，减少非最后一层的 compaction 频率可以有效降低更新操作的代价，且对点查、空间放大、长范围查询的性能影响较小。

# 3. 降低写放大

基于上述理论分析，该论文提出混合 compaction 策略即 Lazy Leveling。它将 Leveling 与 Tiering 进行结合，在最后一层使用 Leveling 策略，其他层使用 Tiering 策略，即最后一层只能存在唯一的 sorted run，其他层允许存在多个 sorted run，从而有效降低非最后一层做 compaction 的频率。

下表是采取 Lazy Leveling 策略后的性能汇总表，其中，绿色部分表示效果较好，红色部分表示较差，黄色部分代表适中。从下表可以看出，Lazy Leveling 的更新操作（update）性能优于 Leveling，接近于 Tiering。这是由于在前 L-1 层维持 Tiering 策略，做 compaction 的频率更低，写放大低。但 Lazy Leveling 的空间放大接近于 Leveling，远好于 Tiering。这相当于结合了两种策略的优势。

对于点查（point lookup），论文中分别分析了查找不存在 kv 和 kv 在最后一层两种情况，并基于论文 Monkey 的思路对每层的 bloom filter bit 进行了优化，可以达到与 Leveling+Monkey 策略相匹配的点查性能。对于长范围查询，Lazy Leveling 可以做到与 Leveling 一致的性能，而短范围查询则退化至接近 Tiering 的水平。

论文对此进行总结：使用一种单一 compaction 策略，不可能在上述所有操作中做到性能最优。Lazy Leveling 本质上是 Tiering 与 Leveling 策略的折衷加调优，在侧重于更新操作、点查和长范围查询的 workload 上性能较好；Leveling 适用于查询为主的 workload；Tiering 则适用于更新操作为主的 workload。

论文通过建立代价模型将 Lazy Leveling 进行推广，将其称为 Fluid LSM-Tree。假设有两个参数，分别为 Z 和 K。Z 表示最后一层允许有最多 Z 个 sorted run；其他层则允许有多个 sorted run。K 为限制参数，表示每层最多有 K 个 sorted run。当每个 sorted run 的值达到 t/k 时会向下做 compaction。通过这样的方式，将 Lazy Leveling 进行泛化推广，通过不同的 workloads 来调节参数 Z 和 K。下表是将参数 Z 和 K 添加进去后的 Fluid LSM-Tree 的代价利用分析结果。

但这在实际操作中会遇到问题，即如何根据 workloads 来选取参数 Z 和 K。论文采取搜索方式去找到针对某个 workload 代价模型最小的参数 K 和 Z。在真正实现时，我们对 workload 的认知相对有限，想要找到最优的参数 K 和 Z 会较为困难，且该模型总体比较复杂，实践性有限。

RocksDB 在某种意义上也采取了混合 compaction 策略。RocksDB 的 L0 层的 SST 之间，K 允许互相重叠，即允许多个 sorted run。这实际上是 Tiering 策略，因为其落盘的 Flush 的性能更优。在 L1-Ln 层中采取 Leveling 策略，能够更及时地清理过期数据，提高空间利用率。

RocksDB 将每个 sorted run 切割为多个 SST 文件，每个 SST 文件都有大小阈值。其优点在于每次发生 compaction 时，只需要选取一个或者少量的 SSTable 与下层有 KV 重叠的 SSTable 进行合并，涉及到合并的有效数据量处于可控范围。

SOSP 2017 中有一篇名为 PebblesDB 的论文，提出了 compaction Guard 概念。每层分割为多个分片，分片间的分割称之为 compaction Guard，即一次 compaction 操作不会跨越该分界线，每个分界线内部 SST 之间允许重叠，可理解为 Tiering compaction。这种做法最大的好处是可以保证数据项从第 i 层向第 L+1 层进行 compaction 时，写入只有一次。因为它将原生的 LSM-Tree 进行分隔，形成 FLSM 结构。其坏处是读性能会变差。因为找到对应分片后，分片内部如果存在多个 SST，我们就不知道数据的真正存放位置，这时需要借助 Bloom 过滤器来对每个 SST 进行探查，且即使使用 Bloom 过滤器，其发生假阳性的期望次数也会增加。

在 RocksDB 实践过程中，我们发现它实际上提供了一个 SST Partitioner 的类，通过类可以在代码实现上保证分片，但与 PebblesDB 不同的是，其在分片内部保持 SST 不重叠，仍然采取 Leveling 策略。其好处是读性能不变。虽然写性能没有得到提升，但更加适配于扩容场景，便于迁移及迁移后数据的物理删除操作。

以 TDSQL 新敏态引擎架构为例。每层的存储节点称为 TDstore，一个 TDstore 真实的数据存储相当于维护一个 LSM-Tree 结构来存储 KV 数据，再将 KV 数据按照区间划分成不同 Region。需要扩容时，我们会增加若干个存储节点，再将原来节点上的部分 Region 迁移过去。Region 迁移涉及到 Region 数据的迁移。如果采用前述的分割策略，将 LSM-Tree 的每一层基于 Region 边界进行分割，将 Region 从相对完整的 SST 文件中捞取出来，并插入到新增的 TDstore 存储节点中。因为 SST 根据边界进行分割，我们可以相对完整地将 Region 内部的数据迁移或删除，因此 Region 数据迁移的性能会得到提升。

# 4. 降低读放大

降低读放大必须结合布隆过滤器。具体实现为：每层设置一个布隆过滤器，通过布隆过滤器进行过滤，减少无效读磁盘 block 的次数。

下图为前述的结论表。当数据查询不存在即发生读穿透时，发生假阳性的概率为 e 的-m/n 次方。只要发生假阳性，就必须去读数据块，进行一次读磁盘操作。在 Leveling 中，每层只有一个 sorted run，查一次 Bloom filter 的概率为 e 的-m/n 次方，根据期望公式推导出的期望读盘次数为 L 乘以 e 的-m/n 次方。Tiering 中则是 T 乘以 L 再乘以 e 的-m/n 次方。假设点查时使用布隆过滤器进行过滤，每层都建立一个布隆过滤器即固定的 bits 团，读性能就可得到提升。

2017 年一篇名为 Monkey 的论文对布隆过滤器进行优化。在 LSM-Tree 不同层设置不同的布隆过滤器的 bits，可以有效降低 IO 开销，从而减少读穿透的期望次数。其结论分析如下：第 i 层设置（a+b）×（L-i）的 bits。由于最后一层数据量最大，只用一个 bit 来 hash 到布隆过滤器中。相比于前述公式，这可以减少一个 L 系数。因为 Bloom filter 要在内存中持有，而每层的 bits 不同，因此总体上降低了布隆过滤器的内存开销。其点查的读性能和整体 Bloom filter 的空间利用率都会得到提升。

SIGMOD 2021 一篇名为 Cuckoo 的论文，采用布谷鸟过滤器代替布隆过滤器，从而优化读性能。布隆过滤器的优化方式为：LSM-Tree 的每层甚至每个 SST 文件都会维护一个 Bloom filter，查询时需要从 MemTable L0 到 Ln 一层层向下探查，每次探查时先走一遍相应的布隆过滤器。该论文提出替代方案，不需要每层都维护一个布隆过滤器，而是选择维护一个全局的布谷鸟过滤器。先查全局的布谷鸟过滤器，如果反馈不存在则表示数据不存在，如果反馈存在，考虑到可能发生假阳性，我们再去查数据文件。

实现原理为：全局的布谷鸟过滤器里记录了 Level ID。如果在布谷鸟过滤器中有 mash，则不需要继续向下探查，可以直接找到其对应的 Level ID，找到对应层、对应的 sorted run 去读磁盘，看数据是否存在。布谷鸟过滤器对接两部分：其 hash map 或签名，再加上位置 ID 即 level ID。

布谷鸟过滤器。我们通过两次哈希算出 key 所要插入的具体位置，所对应的两个桶称为 b1 和 b2。b1 直接拿 key 进行擦洗，b2 不需要用 key 的原值，在算出签名指纹后再做哈希，因此每个 key 会有两个可以存放的位置。

布谷鸟过滤器哈希的数据插入过程如下：假设要插入 item X，通过第一个哈希计算出其位置是 2，即 b1 等于 2，第二个哈希算出其位置是 6。我们先将其放在第一个位置，如果可以放下则放下，如果放不下再看第二个位置即 b2，如果 b2 没有被占则直接放下。如果 b2 也被占则进行 relocate，将原来的对象剔除，新插入的值再放到第二个位置。被剔除的值会放到它的两个 bucket 中的另一个。如果另一个 bucket 也被占据，被占的元素会继续被踢走，直到所有元素都有一个新的空白位置存放，则该过程结束。

Cuckoo 论文中还需要记录其签名，用于确认 key。如果签名冲突则会造成假阳性。除此之外，还需要记录其 Level ID 如下图中的 1、4、5，Level ID 的作用是记录该值位于哪个 sorted run。通过 Level ID 可以在具体的 sorted run 里查询或更新。

# 5. 降低空间放大

RocksDB 默认采用 Leveling compaction，但也提供类似 Tiering compaction 的选项。如果选择 Leveling compaction，它会提供 dynamic level size adaptation 机制。理论分析表明，在最后一层数据充满时，Leveling compaction 的空间放大率不高，等于 1/T。但在实践中，最后一层的实际数据通常不会达到阈值。

假设每层容量放大比例为 T，每层容量是 T 系数的等比数列。根据等比数列进行求和，我们发现最后一层的数据量占绝大多数，等于总大小的（T-1）/T，前面所有层只占总大小的 1/T，此时冗余数据量为前面所有层数据量与最后一层数据量之比，等于 1/（T-1）。假设放大比率为 10，阈值为 1G，L1 到 L4 的阈值分别为 10G、100G、1000G。如果 L4 为最后一层，通过计算可知冗余率为 1.1。

实际情况下，最后一层的数据量一般不会达到阈值。在上述例子中的 L4 层，如果以静态阈值为参照，当前 L4 的数据并没有写很多，可能只有 200G 数据，其放大率会比较差，前面存在大量冗余数据。

因此 RocksDB 提出了动态调整每层容量阈值的机制。以下图为例，当 L0 充满时，其数据先不往 L1 写，而是先往 L5 进行合并，这时 L1 至 L4 为空。

当 L5 的实际数据量达到阈值 10M 时，compaction L0 往下落的目标层切到 L4，并让 L4 的阈值保持最初的阈值即 10M，再将 L5 的阈值乘以放大系数 T，L4 与 L5 之间的容量阈值仍保持 T 倍的关系。假设 L5 的实际数据量达到 11M，则 L4 的阈值为 1.1M。

数据不断往 L4 写，L4 再向 L5 进行 compaction，L4 会逐渐达到阈值。

L4 达到阈值后，以此类推，当 L3 达到 10M 后，开启 L2 作为 L0 的合并目标层。L3 初始阈值为 10M，这时 L4 扩大为 100M，L5 扩充为 1000M。

在这种动态调整每层空间大小阈值的策略下，可以将数据冗余量始终保持在 1/（T-1）。在 T=10 时，其空间放大率不会超过 1.1，这是比较理想的空间放大率。

降低空间放大还有其他的实践措施。目前 RocksDB 已经实现 key prefix encoding，可以让相邻的 key 共享一次，只存一次，从而节省 10%的空间开销。sequence ID garbage collection 也是较好的优化措施。当一个 key 的 sequence number 小于最老的 snapshot 的 sequence number，则它的 sequence number 可以改写为 0，而不影响数据的正确性。sequence number 压缩率的提高带来了空间利用率的提高。

加压缩也可以优化空间放大。目前 RocksDB 支持多种压缩方法。第三方压缩方法有 LZ、Snappy 等方法。我们还可以以 SST 文件作为单元来设置不同的压缩算法，从而对 KV 数据进行压缩。降低空间消耗的同时会增加读开销，压缩过程中也会消耗一定的 CPU 资源，读的过程中还要进行解压，这就要求我们必须进行权衡。因此实践的优化策略通常为：L0 至 L2 层不压缩，L3 及以下使用较为轻量级的压缩算法，如 Snappy、LZ，可以综合考虑压缩带来的空间开销受益和读性能受益。最后一层采用压缩率更大的压缩算法，一方面是因为数据较老，读到的概率较低，另一方面是因为越往下的层的容量阈值越大，存储的数据也越多，压缩率高可以节省较大的空间开销。

RocksDB 也在 Bloom filter 方面进行优化实践。Bloom filter 本身会有相应的内存开销，在内存有限的情况下，可以减少 Bloom filter 对内存的占用。方法之一是最后一层数据不再建立 bloom filter。因为最后一层的数据量较大，Bloom filter 本身占用的空间也比较大，会消耗较多内存，且考虑到最后一层的数据较老，被访问的概率较小，因此在最后一层或最后几层不再建立 Bloom filter，在节省内存消耗的同时对读性能影响小。

还有其他的优化方法，比如 compaction job 并发。在 RocksDB 中，compaction 在后台异步进行执行，执行过程中分为不同 compaction job，如果两个 compaction job 之间的 SST 集合互相不重叠，则这两个 compaction job 可以实现现场并发。L0 层的 SST 文件通常互相重叠，RocksDB 对此进行优化，提出 subcompaction 概念，将 L0 层有 SST 重叠的情况也做并发。IPDPS 2014 的一篇论文还提出，compaction 之间可以做流水线。

# 6. 结语

相比于传统的 B+树，LSM-Tree 结构具有更好的写性能，可以将离散的随机写请求转换成批量的顺序写操作。其性能衡量主要考虑三类因素：空间放大、读放大和写放大。LSM-Tree 最初的设计理念是想通过空间放大和读放大来换取写放大的降低，从而达到极致的写性能，但也需要做好三方面因素的权衡，可以从降低写放大、降低读放大、降低空间放大三方面来对 LSM-Tree 结构进行优化，从而提升数据库性能。