在前面我写了B、B+树、Wisckey的总结。不过我觉得应该将今天的内容放在总结Wisckey之前。因为wisckey就是针对LSM进行效率上的提升。所以本文我们重点介绍LSM与LevelDB。

LSM

1 LSM概念介绍

首先我们简单的介绍一下LSM的思想。而具体的操作过程我们放在LevelDB中进行讲述。

实际上，要是给LSM的命名断句，Log和Structured这两个词是合并在一起的，LSM-Tree应该断句成Log-Structured、Merge、Tree三个词汇，这三个词汇分别对应以下三点LSM的关键性质：

将数据形成Log-Structured：由于数据会首先写入内存，而内存存在断电丢失的情况。所以在将数据写入LSM内存结构之前，先记录log。这样LSM就可以将有易失性的内存看做永久性存储器。

• 在将数据写入LSM内存结构之前，先记录log。这样LSM就可以将有易失性的内存看做永久性存储器。并且信任内存上的数据，等到内存容量达到门限再集体写入磁盘。将数据形成Log-Structured，也是将整体存储结构转换成了“内存(in-memory)”存储结构。

• 由于磁盘随机读写比顺序读写慢3个数量级，LSM尽量将磁盘随机读写转换成顺序读写。

对于B树来说，虽然其查找非常高效，但是如果磁盘是随机读写的情况，那么就会由于大量寻道导致其性能不佳。而对于LSM，它将所有数据不组织成一个整体索引结构，而组织成有序的文件集。每次LSM面对磁盘写，将数据写入一个或几个新生成的文件，顺序写入且不能修改其他文件，这样就将随机读写转换成了顺序读写。LSM将一次性集体写入的文件作为一个level，磁盘上划分多level，level与level之间互相隔离。这就形成了，以写入数据时间线形成的逻辑上、而非物理上的层级结构，这也就是为什么LSM被命名为”tree“，但不是“tree”。

• 之后将数据按key排序。为了防止不同file、level上存在文件更新或者相同空间从而造成冗余和降低读性能。所以我们要将数据按key排序，并合并不同file、level上的数据。

很明显，LSM牺牲了一部分读的性能和增加了合并的开销，换取了高效的写性能。那LSM为什么要这么做？实际上，这就关系到对于磁盘写（直接写的效率）已经没有什么优化手段了，而对于磁盘读，不论硬件还是软件上都有优化的空间。通过多种优化后，读性能虽然仍是下降，但可以控制在可接受范围内。实际上，用于磁盘上的数据结构不同于用于内存上的数据结构，用于内存上的数据结构性能的瓶颈就在搜索复杂度，而用于磁盘上的数据结构性能的瓶颈在磁盘IO，甚至是磁盘IO的模式。

2 LSM结构

• 一、WAL

在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 到WAL 文件中，之后插入到内存中的 MemTable 中。这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。当程序挂掉重启时，可以从 WAL 文件中重新恢复内存中的 MemTable。

• 二、MemTable

MemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构，通常用 SkipList 来实现。MemTable 提供了 k-v 数据的写入、删除以及读取的操作接口。其内部将 k-v 对按照 key 值有序存储，这样方便之后快速序列化到 SSTable 文件中，仍然保持数据的有序性。而MemTable 就是直接与写入的数据直接接触。由于在内存中且为顺序直接保存，所以其写入效率是极高的。

• 三、Immutable Memtable

顾名思义，Immutable Memtable 就是在内存中的只读 MemTable，由于内存是有限的，通常我们会设置一个阀值，当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。

之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

• 四、SSTable

image.png

SSTable分为许多级别（例如levelDB中的level0~level6）。

SSTable 就是 MemTable 中的数据在磁盘上的有序存储，其内部数据是根据 key 从小到大排列的。通常为了加快查找的速度，需要在 SSTable 中加入数据索引，可以快读定位到指定的 k-v 数据。

SSTable 通常采用的分级的结构，例如 LevelDB 中就是如此。MemTable 中的数据达到指定阀值后会在 Level 0 层创建一个新的 SSTable。当某个 Level 下的文件数超过一定值后，就会将这个 Level 下的一个 SSTable 文件和更高一级的 SSTable 文件合并，由于 SSTable 中的 k-v 数据都是有序的，相当于是一个多路归并排序，所以合并操作相当快速，最终生成一个新的 SSTable 文件，将旧的文件删除，这样就完成了一次合并过程。

3 LSM基本操作

对于存储相关的内容无非设计“增、删、改、查”四中操作。下面我们具体的看一看相关操作。

一、写入

image.png

在 LSM Tree 中，写入操作是相当快速的，只需要在 WAL 文件中顺序写入当次操作的内容，成功之后将该 k-v 数据写入 MemTable 中即可。尽管做了一次磁盘 IO，但是由于是顺序追加写入操作，效率相对来说很高，并不会导致写入速度的降低。数据写入 MemTable 中其实就是往 SkipList 中插入一条数据，过程也相当简单快速。

二、更新

更新操作并不是我们想象中的那样，找到数据的位置然后将value修改掉balabala。而其和写入一个 k-v 数据没有什么不同。我们倘若要修改数据，那么不需要管理level-n中的数据，而是直接选择插入新数据。由于数据在低层的数据比高层要新，所以我们从低到高读出的数据是从新到旧的。所以这个机制也帮助了我们不少。

而对于这些多余的数据，也就是说此时在整个 LSM Tree 中可能会同时存在多个 key 值相同的数据，只有在之后合并 SSTable 文件的时候，才会将旧的值删除。

三、删除

如图所示，我们key3就是删除的操作。删除一条记录的操作比较特殊，并不立即将数据从文件中删除，而是记录下对这个 key 的删除操作标记，同插入操作相同，插入操作插入的是 k-v 值，而删除操作插入的是 k-del 标记，只有当合并 SSTable 文件时才会真正的删除。

四、Compaction

当数据不断从 Immutable Memtable 序列化到磁盘上的 SSTable 文件中时，SSTable 文件的数量就不断增加，而且其中可能有很多更新和删除操作并不立即对文件进行操作，而只是存储一个操作记录，这就造成了整个 LSM Tree 中可能有大量相同 key 值的数据，占据了磁盘空间。

为了节省磁盘空间占用，控制 SSTable 文件数量，需要将多个 SSTable 文件进行合并，生成一个新的 SSTable 文件。

比如说有 5 个 10 行的 SSTable 文件要合并成 1 个 50 行的 SSTable 文件，但是其中可能有 key 值重复的数据，我们只需要保留其中最新的一条即可，这个时候新生成的 SSTable 可能只有 40 行记录。

通常在使用过程中我们采用分级合并的方法，其特点如下：

每一层都包含大量 SSTable 文件，key 值范围不重复，这样查询操作只需要查询这一层的一个文件即可。(第一层比较特殊，key 值可能落在多个文件中，并不适用于此特性）

image.png

当一层的文件达到指定数量后，其中的一个文件会被合并进入下一层的文件中。

五、读取

由于LSM更偏向写入数据，所以其读效率相对较低。

当需要读取指定 key 的数据时，先在内存中的 MemTable 和 Immutable MemTable 中查找，如果没有找到，则继续从 Level 0 层开始，找不到就从更高层的 SSTable 文件中查找，如果查找失败，说明整个 LSM Tree 中都不存在这个 key 的数据。

如果中间在任何一个地方找到这个 key 的数据，那么按照这个路径找到的数据都是最新的。

image.png

在每一层的 SSTable 文件的 key 值范围是不重复的，所以只需要查找其中一个 SSTable 文件即可确定指定 key 的数据是否存在于这一层中。Level 0 层比较特殊，因为数据是 Immutable MemTable 直接写入此层的，所以 Level 0 层的 SSTable 文件的 key 值范围可能存在重复，查找数据时有可能需要查找多个文件。

LevelDB

写的比较详细的原理介绍有：https://www.cnblogs.com/zhihaowu/p/7884424.html

LevelDB的官方网站：https://leveldb.org.cn/