架构总览：

LSM大致架构如图：

image.png

图中所示名词中：

MemTable：如图，memtable是存放在内存中的数据结构，而active memtable是用于存放user存进来的最近的数据，并且lsmTree规定在内存中存放数据是按照key有序的进行存储的，其目的下文会提及。而具体使用何种数据结构，跳表、b树等都是可以的。

Immutable MemTable：当memtable的大小大于所设定的阈值后就会转换为Immutable 。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理。

WAL（write ahead log：这个相信大家都不默认，不管是mysql、kafka、分布式数据库、raft理论都会提及预写日志这样一个东西，由于数据会放在内存一段时间，那么就不能排除可能会出现故障导致数据在内存中还没持久化而丢失，所以wal在这种场景是不可或缺的。而分布式场景wal在保证数据一致性也是极其重要的一部分，但是与本文无关就不过多解释

SSTable(Sorted String Table)：在图中sstable在持久化在磁盘中的文件，由于在内存中有序，那么sstable是有序的，因此称为sstable。至于sstable有l0、l1…的层级，后面再讲解。

优劣势分析：

追加写和原地写

这个相信大家也不陌生，但还是聊一聊。

原地写：原地写就是在写数据的时候是进行原地更新的，会找到数据原本所在位置，然后对该位置数据进行更新。

追加写：追加写就是不管前面数据如何，在写数据时都会直接在文件末尾进行写入，one by one

image.png

原地写： image.png

追加写： image.png

区别：显然原地写它不会浪费多余空间去重复对一个key进行写数据，但是原地写每次写入都会花费一定时间在磁道中寻道以及磁头转向，因此写入是比较慢的。 相反追加写就会导致数据冗余，在查找时也会逆向查找，直到找到第一个符合的数据，会非常的慢。但是在写入时由于是追加写，因此就省去了寻道的时间。

lsm tree设计思路：

而lsm tree就是追加写的思路，适用于写多读少的场景，比如说日志采集系统就是典型的写多读少的应用场景。但是如果仅仅是刚刚图示的直接在disk中进行追加写，那么就会引申出数据特别冗余、读特别慢。因此lsm tree的设计主要是对数据冗余、读性能进行的优化。

数据冗余：

针对数据冗余的问题，比较好的办法就是在一段时间后对存放的数据进行merge合并压缩，留下有效的数据，清除掉旧数据。 image.png

但数据压缩会有一个困扰，就是你在压缩的时候，可能有数据也在往里面写入，这样就会导致锁竞争，数据写入数据慢，

image.png

而针对这一问题，可以对数据进行分块，例如刚开始架构图中的memtable，写入数据只写入在active数据块中，这样对old block的merge操作与写入操作就互不干涉了。

读性能慢

读性能慢是由于冗余数据过多，读的时候必须倒叙读，直到读到第一个最新的数据返回。那如果存储的数据是有序的那么读的时候就可以进行二分，这样效率就大大提高。

前面提到了我们将数据分为了多个数据块 因此我们或许考虑对每个数据块对key进行排序，这样就可通过二分快速查找。

但是这样子在写入数据时就需要进行排序，那写入时就会特别慢，显然这违背的lsm tree的初衷。

因此可采取先写在内存中的设计思路，这里再搬出原来的图image.png

在这里我们写入数据在active memtable中，由于我们内存存放数据使用的是如btree、skipList这样有序的数据结构，这样当我们将内存数据持久化在磁盘中后，磁盘中的数据也是有序的。那么就很好的解决了这一问题。

引入内存的缺陷解决

又如我前面所说，引入内存后会带来数据不一致的问题，引入WAL，在写数据时同时将数据也写入WAL。WAL 和 memtable 可以建立对应关系，每当一个 memtable 被溢写到磁盘中成为 disktable，其发生数据丢失问题的风险也就随之消除，因此对应的 WAL 也就可以删除了. 并且，由于 WAL 中也是追加写的操作，属于磁盘顺序 IO，因此性能不会成为瓶颈。

磁盘分层：

sstable是由内存中的memtable去持久化得到的，而memtable写入数据是采取的原地写，因此在一块sstable的数据是不冗余且有序的，但是不同的sstable却是无法满足数据不重复、有序。

因此lsmtree就像图中所示，将sstable进行了分层

  • 1.memtable中溢写数据会落到l0当中
  • 2.当l0文件数据大小达到阈值后就会归并到l1当中， level(i) -> level(i+1) 的归并操作
  • 3.level(i+1) 中 disktable 的容量大小固定为 level(i) 的 T 倍，T 为常量，通常取值为 10 左右
  • 4.每个 level 层中的 disktable 数量保持一致

因此在k层的数据几乎是包揽了该数据库中所有的数据量，且有序、不重复。 刚写入数据应当是高层，比较旧的数据在低层。

补充： 在每个sstable当中，因为本身有序，因此还维护了max_key与min_key，其目的主要是方便在查找时快速定位到指定的sstable、以及在文件从高层归并到低层时能轻易指定到对应的块进行merge

层级归并演示:

image.png 假设红色的sstable是需要进行merge的，1-22是指对应的min、max_key，根据最大key最小key可得出l1中前两个sstable有重叠数据，因此都需要参与与1-22进行merge操作 merge之后：

image.png

其次lsm tree对每个sstable都维护了一个bloomfilter用户快速判断在此sstable是否有需要的key

总结lsm tree读写流程：

写操作：

1.基于就地写模式，写入内存中的 active memtable

2.active memtable 达到阈值后转为Immutable MemTable的中间态，后续转为sstable

3.level(i) 层数据容量达到后，会基于归并的方式合并到 level(i+1)，以此类推

读操作：

1.读 active memtable

2.读 readonly memtable

3.读disk，读disk时从l0依次往l1、l2往下读，每一层可根据维护的min、max_key快速指定到一个是stable进行读取，因此每一层仅需读取一个sstable，而在读取时可先根据布隆过滤器判断数据是否存在再判断是否读该sstable