从朴素解释出发解释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论文
稿源:yueyue.gao (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 后端存储 » 从朴素解释出发解释leveldb的设计

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录

登录

忘记密码 ?

切换登录

注册