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 构造进行优化，从而晋升数据库性能。