ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

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

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

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

1
2
3
4
SSTable
+-+---+----+---+
|k| v | k | v | ...
+-+---+----+---+

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

1
2
3
4
5
6
7
8
9
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结构的朴素解释。实际上MemTableSSTable都没有采用纯粹的树形结构,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论文