从朴素解释出发解释leveldb的设计

其实大家提的 LSM 最开始论文里面都使用树做搜索结构的, 现在在用的都不是严格的树结构了。

如这篇文章解释的一样，从最朴素的角度上来讲可以把SSTable(sorted string table)作为一个连续的kv构成的块。

SSTable
+-+---+----+---+
|k| v |  k | v | ...
+-+---+----+---+

对于一个大文件来说，读取整个文件以后就能构成一个各个键值的索引，当然可以在文件追加一块索引，和文件一起保存。

Index
+-+-------+
|k|offset |
+-+-------+
|k|offset |
+-+-------+
    .
    .
    .

有了索引以后用 seek 操作或者直接把文件 mmap 到内存中都可以有很好的随机读性能。

但是对于随机写来说, 会造成大量的I/O，如果我们能够保证我们的SSTable是不可修改(immutable)的，只有SSTable在内存当中的时候(也就是MemTable)才可以修改，就能避免随机写的大负载问题。

通过下面几条约束就能完成我们的要求：

1. 首先SSTable索引要放在内存中，这样读索引更快
2. 所有写只能写到MemTable当中, 因为SSTable不可修改
3. 所有读要先查看MemTable如果没有再查看内存中的索引(最后找到磁盘上的kv)
4. 定期把MemTable刷成SSTable,这段时间MemTable也变成了不可修改的,新的MemTable会顶替
5. 定期对SSTable进行合并

最终我们保证了随机写很快（因为只在MemTable中），随机读也很快（因为要么在MemTable中要么通过索引可以很快找到)。

还有一个问题是对于已有数据的删除和修改怎么办？

因为SSTable不可修改所以只能追加写一个新的数据覆盖老的数据，对于删除则是追加一个”墓碑”值覆盖掉存在的值。把索引指向新值，这样老值就不会被访问了。最后在SSTable合并的时候这些老值会完全消失。所以还要定期合并SSTable

以上是对leveldb的LSM结构的朴素解释。实际上MemTable和SSTable都没有采用纯粹的树形结构,MemTable使用的是跳表而SSTable使用的是层次的结构。(这也是为什么 leveldb 叫 level db 的原因)

从这里开始完善朴素解释

首先对于MemTable来说不是持久化的如果重启导致内存中的数据丢失怎么办？WAL 表示的是预写日志，这个日志和MemTable是同步的，这个日志把每次的命令追加到日志中再更改MemTable，这样如果重启的话能够进行”重放”把从已经持久化的状态开始把数据填回到MemTable当中。

其次是对SSTable的合并，SSTable是分层存储的，第一层也就是Level0(被称作 young level)，是MemTable刷入的一层，允许这一层的SSTable的key有交集。对于每一层都有一个阈值(young level 是 4,其他层是按大小算的，10^L MB)，如果超过阈值自动向下一层合并，从level1开始的每一次key不允许有交集。具体的做法是从 young level 中把有交集的SSTable一起和下一层key有交集的SSTable合并成一个新的SSTable，然后其他层则是从自身层取出一个和下一层有交集的SSTable合并即可。这个属性可以用归纳法证明，从0层向1层合并的时候，1层只有一个的情况下肯定不会相交，然后假设n个的时候也不相交，在n+1的时候有交集，那么n+1合并时有0层的 key 和 n 当中的有交集，但是有交集的部分会被归并掉所以矛盾，所以n+1个的时候也是没有交集的。那1层能保证没有交集的话取出一个向下合并也是类似的不会有交集。所以再重复一遍分层存储的两个属性。

对于朴素解释的两个扩展使得我们对leveldb的设计更接近了。

1. young层SSTable之间可能存在交集
2. Li（i>0）层SSTable之间不存在交集

在这个基础上再增加几个约束条件，一个是，对于合并过程每超过2MB就会产生一个新文件，如果文件和下一层的文件有交集的个数有10个以上的话也会产生一个新文件，这样的目的是保证Ln和Ln+1之间不会重复太多。个人理解是覆盖太多，会成了倒三角的”树”情况，上一层搜索性能不好。

当然大量的随机读落在磁盘上还是会有性能问题，因为 seek 也可能是不连续的，这个可以想办法优化, 比如leveldb 里面使用了一种LRU缓存优化读性能。

参考

1. 官方实现文档
2. LSM-tree论文