LSM-Tree 论文阅读笔记

1 LSM-Tree 是啥
2 LSM-Tree 解决了什么问题
3 LSM-Tree 怎么解决的
4 LSM-Tree 创新点有哪些
5 LSM-Tree 有什么缺点
6 LSM-Tree 适合什么场景

梳理 leveldb 压实逻辑的时候, 看代码逆向逻辑太难了, 非常零碎, 很难搞清楚作者为何那么实现, 想起来 LSM-Tree 论文还没读过, 于是找了读了一下, 可是原始论文太晦涩了, 读不懂, 可以参考这篇博客来读论文.

1 LSM-Tree 是啥

一种数据库索引方法, 不同于 B-Tree.
数据更改时, 非 update-in-place 形式修改数据, 而是顺序写日志文件(此为 log structure, 以优化写); 每个文件有序(以优化读); 文件多了合并(此为merge)为大的文件减少文件数(以优化读).

不管是机械磁盘还是 SSD 甚至是内存, random access 性能都比 sequential access 慢三个数量级. 这个问题也指出了解决方向.
LSM-Tree 采用了 append 模式, 依赖 sequential access, 不管增删改都是 append 形式追加日志到文件(只有一次 IO 操作, 写就完了), 而且通过内存+磁盘两级模式实现了批量 append.

顺序写, 随机读. 解决了写的问题, 但是读又成问题了.
读性能不好. 由于数据是追加到文件中, 整个结构是平的, 而且无序, 无法快速定位到要查找的数据, 导致读取性能不好.
为了缓解(不是解决)这个问题, LSM-Tree 实现采取了多种办法, 具体为:
- 文件内容要变无序为有序. 最直接的就是先确保内存那份是有序的(一般用 RBTree 或者 SkipList ), 满了序列化到磁盘仍然确保有序性; 同时每份文件尾部加一份当前文件内容的索引块, 查询时根据索引能快速定位到该数据项目标位置.
- 通过合并让文件数变少. 内存不可能无穷大, 所以前一步提到的内存那份也不能太大, 这就意味着磁盘上的有序文件也不能太大, 但这就会导致一个问题, 文件数会非常多. 想法减少文件数. 怎么减少呢? 合并, 把多个小文件合并为有序大文件.
- 缓存. 有一个全局的布隆过滤器(这里只是推断为全局, leveldb 实现是每个文件一个布隆过滤器), 所有查询先走一遍布隆过滤器确定是否存在, 不存在就不用查了; 如果疑似存在去查文件内容(所以要查的文件要有序而且文件数尽量越少越好).

---End---