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

内容简介：从朴素解释出发解释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论文

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 全局角度出发讨论敏捷
• 2019 已落幕，2020 再出发
• 从观察者模式出发，聊聊RxJava
• 【技术分享】从MySQL出发的反击之路
• 走的太久忘记了为什么出发
• 从对象头出发了解Synchronized关键字

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。