LSM-Tree 概述

为什么要有 LSM-Tree

在传统的树形结构索引中，大量写入操作会带来额外的 IO 开销，要花费两倍的 IO 成本来维护实时索引，并且每次写入都会有两次 IO 操作，一次读 page，一次将 page 写回，所以要引入一种新的算法来应对这种场景，这正是 LSM-Tree 诞生的理由。

LSM-Tree 的核心思想就是写入延迟、采用批量写入，并且消除了随机的就地更新。LSM-Tree 首先将数据缓存在内存当中，当内存中的数据达到一个阈值时，将它们批量写入磁盘中。

当然，有得有失，LSM-Tree 在读取的时候会存在短板，所以 LSM-Tree 适用于写多读少的场景。

基础的 LSM-Tree 算法

在 LSM-Tree 中，数据首先被添加到 MemTable 中，这个 MemTable 是一个有序的内存数据结构，但并没有规定具体是哪一种，可以是红黑树也可以是跳表等。这样可以起到使数据先排好序的作用。当 MemTable 被写入的量达到阈值的时候，会被刷入到磁盘的一个新的 SST 文件中。

SST 这种文件格式有许多好处：

• 可以做到高效的数据文件合并，即使文件大于可用内存，合并段的操作仍然简单高效。
• 不需要在内存中保存所有键的索引，可以使用稀疏索引，因为 SST 文件是有序的。
• 由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩。

显然这种仅追加的方式，会产生越来越多的不可变的有序文件，但并不会去更新旧文件中的重复条目（或被删除的记录），所以会产生冗余（空间放大）。系统需要定期的执行合并操作（Compact），来把文件合并，消除其中重复的更新或删除操作。

合并并不仅仅是为了节省磁盘资源的浪费，更多的是要通过减少文件数量的增长，来保证读操作的性能。由于 LSM-Tree 文件有序的特性，合并操作是非常高效的。

LSM-Tree 的读取操作首先在内存中读取 MemTable，如果没有读到，再去磁盘中读取，从新的文件开始往旧的文件读取。所以 LSM-Tree 的读取性能自然要比采用就地修改的其它结构要低了。当然，可以在内存中建立索引来提高读取的速度。同时可以通过布隆过滤器来进行优化，可以大概率避免读完所有 SST 文件发现某个 Key 并不在数据库中。

所以从整体来上来 LSM-Tree，其实就是牺牲读取性能来换得写入性能，避免随机写，但带来了随机读。

Compact

基础的 Compact 方法

基本的合并方法非常简单：当创建一定数量的小文件后，将它们合并成一个单独的中等大小的文件，在这些中等大小的文件又到达一定数量后，再将它们合并为更大的文件。

这种方法带来的结果就是大量的文件会被创建，这样和我们去控制文件数量保证读取性能的思路就背道而驰了。

LevelDB 中的 Compact 方法

在 LevelDB 等数据库中，通过实现分级（Leveled）而不是大小，来将 SST 文件进行分组。这减少了最差情况下大量文件的读取，同样减少了单个压缩的（对整个数据集的）相对冲击。

这种方法跟基本方法有两个不同的关键点：

• 每一层的键不会重复，所以在某层寻找一个关键字的时候只需要查询一个文件。
• 文件一次被合并成高层级的一个文件。当一层满了，一个文件会从这一层抽离，并且合并进入上一级来创建加入更多数据的空间。这比起基本方法中，把相似大小的文件合并成一个单独的较大文件，略有些不同。

由于低层次的文件会被合并到高层次的文件中去，相比于基本方法需要的整体空间会更少，读性能也会更高，但会带来更大的 IO 负载，对于单纯以写为目的的情况，并没有帮助。

LSM-Tree 更多的一些优势

LSM-Tree 除去更好的写性能之外还有一些优势：

• SST 文件是仅追加的，所以锁定语义的实现相比于树结构更加简单。
• 在同样硬件的情况，硬件的提升对读性能的提升更大，所以在不选择提升硬件的情况下想要提升写性能可以选择 LSM-Tree。

总结

LSM-Tree 在 B+ 树和哈希索引之间取得了均衡，通过管理一组而不是单独一个索引文件，LSM-Tree 把 B+ 树或哈希索引中开销较大的随机写入 IO 替换为了快速的顺序 IO。

而读操作则不得不处理大量的随机 IO。并且 LSM-Tree 将带来额外的合并开销。