Log Structured Merge Tree

基本概念

Log Structured Merge Tree, 其本质上是一种存储数据的方式,通常用于各种存储系统的底层数据结构,通过尽可能减少磁盘随机IO来提升写入性能, 适用于写多读少的场景.

随机写和顺序写

对于一个存储系统而言, 不可避免地需要写入文件到磁盘, 对于常规的写来说, 每来一条数据写一次文件, 数据可能是 add update delete, 需要频繁操作文件, 每一次写都是一次随机 IO; 为了提高写入速度, LSM Tree 并不是每一次写操作都把文件写到磁盘, 而是将数据在内存中更新，当内存中的数据达到一定的阈值时，才将这部分数据真正刷新到磁盘文件中. 以这种方式尽可能让每次磁盘 IO 都是顺序写;

思路

基于减少磁盘的随机 IO 来提升整体存储系统的写入性能这一背景, 很自然可以推导出用批量写入的方式, 要想批量写入, 就需要在内存维护最近写入的数据, 达到阈值之后生成一个文件写入到磁盘, 但是这样又会存在新的问题:

1. 如果某一条数据已经写入到磁盘文件, 后续又有更新, 怎么处理呢?
2. 内存中维护的临时数据, 如果还未来得及写入磁盘, 服务挂了, 重新启动时, 历史写入的数据如何恢复?
3. 每次内存中数据达到阈值,写一个整个文件到磁盘,那么最终会生成大量的文件, 如何解决?

• 解决问题1, 为了优化这种更新的写入, 可以采用数据版本的做法, 或者给数据增加标志, 然后定期合并, 当然, 这也是以空间换时间, 相同的数据存储了多次, 以提升写入性能; 与此同时, 在数据读取时,由于写入的逻辑改变, 一条数据可能会存在于多个文件中, 因此在读取时, 需要返回最新的数据, 在读取到多条数据时,需要对多条数据进行合取最新;

• 解决问题2, 在业界比较标准的做法是 WAL, WAL 的基本原理是在执行数据修改操作之前，先将这些操作记录在日志（log）文件中, 以确保在发生故障或崩溃时，可以借助日志进行恢复并保持数据的一致性;

• 解决问题3, 为了避免大量文件, 可以对文件进行定期合并, 当数据还在内存中时, 可以借助跳表或者 B+Tree 等数据结构保证内存中数据的顺序性, 在写文件时, 由于数据是有序的, 在文件合并时,很自然可以借助归并排序保证合并之后的数据的有序性, 而有序性又能天然提高查询效率.

架构

lsm 基本上就是基于以上的推导思路实现的, 整体的架构如下:

WAL

WAL(Write Ahead Logging)即日志先写原理。 日志记录所有的数据修改操作, 把数据修改预先写入日志文件, 然后在写内存或者磁盘数据区, 当日志记录了写入操作, 后续的写动作过程中, 任意步骤出现问题导致进程崩溃, 都可以借助 log 进行数据恢复;

WAL的通常的工作流程:

1. 客户端发起数据修改请求。
2. 服务器将修改操作记录到WAL日志文件。
3. 返回成功响应给客户端。
4. 异步线程将WAL日志内容同步到磁盘数据文件。
5. 当WAL日志同步完毕,数据修改才真正完成。

在 lsm tree 中, 整个 WAL 的流程可以完全融入到写入的过程中, 包括 log 文件的生命周期, 也可以随着 sstable 的落盘而结束.

SStable

SStable sorted string table, 这是一种存储数据的格式, 并且在文件中, 数据都是有序的, 并且在文件中, 保存了元数据信息, 提高数据查询的效率; 具体格式如下:

从文件的结构基本能看出来数据是如何写入的, 整个文件分为元数据信息和数据本身, 加上元数据信息是为了提高数据查询的效率, 比如元数据信息包含了当前文件中 key 的范围, 并且还可以保存 bloomfilter; 其中一个比较有意思的设计是: footer 数据为什么是在文件末尾? 从读取文件的角度而言, 读取文件的起始位置不是更符合习惯, 从后往前读, 读取文件的后 48 字节不是需要事先知道文件的大小?

个人认为这个设计主要是基于以下考虑:

数据写完才知道元数据里的 stat 和 key range, 直接把元数据 append 到文件尾部, 写入效率会更高; 如果元数据在文件的起始位置, 写完数据本身之后, 还需要去更新文件起始位置的元数据信息, 这一过程有可能会导致随机 IO;

compaction

从 lsm tree 的写入过程可以得出, L0 层的文件都是来源于 Memtable(immutable) , 为了保证顺序写入, 每次写入到磁盘都会生成一个新的文件, 基于这种背景, 数据在查询的时候又需要去查询 L0 层的文件, 如果文件很多, 查询效率必然受影响, 而 compaction 的设计就是为了提升数据查询效率;

文件在存储时设置层级, L0 文件大小上限为 10M L1 为 100M, 以此类推, 同时每个层级的文件个数也有限制; 触发 compaction 的条件为:

1. Ln 层的文件超过预定个数;
2. Ln 层的文件大小超过层级的大小限制;
3. 某个文件的无效读取过多;

compaction 的过程就是把 Li 层的若干个文件, 合并到 Li+1层, 在合并过程中,重新计算新文件的 key 范围, 如果有相同 key , 只保留最新的 key, 合并完成之后, 重新计算元数据, 然后清理历史的文件;

从 sstable 文件存储的形式来分析, compaction 的过程可以抽象为一个多路归并的算法, 可以参考 : leetcode , 稍微有些区别就是合并的内容是链表或者其他数据结构.

而解决多路归并的算法, 思路也有很多, 最简单的就是直接合并多个数组,然后基于最后的数组排序, 也可以借助大根堆进行排序, 具体实现可以参考: 堆排序.

并发问题

当在 compaction 过程中, 会有文件的清理, 此时如果用户正在读需要合并的文件, 如何解决这个读写冲突?

遇到读写冲突, 首先就能想到加锁, 读时给文件加锁, 写操作被阻塞, 虽然这样能解决问题, 但是却违背了 lsm tree 的设计初衷: 高性能的写入;

更好的解决办法是: MVCC(Multi-Version Concurrency Control)是多版本并发控制;

1. sstable 文件设置为只读，每次 compaction 都只是对若干个 sstable 文件进行多路合并后创建新的文件，故不会影响在某个 sstable 文件读操作的正确性；
2. sstable 都是具有版本信息的，即每次 compaction 完成后，都会生成新版本的 sstable，因此可以保障读写操作都可以针对于相应的版本文件进行，解决了读写冲突；
3. compaction 生成的文件只有等合并完成后才会写元数据，在此期间对读操作来说是透明的，不会污染正常的读操作；
4. 采用引用计数来控制删除行为。当 compaction 完成后试图去删除某个 sstable 文件，会根据该文件的引用计数作适当的删除延迟，即引用计数不为0时，需要等待至该文件的计数为0才真正进行删除；

参考

https://leveldb-handbook.readthedocs.io/zh/latest/basic.html

https://github.com/facebook/rocksdb/wiki/RocksDB-Overview

https://zhuanlan.zhihu.com/p/351241814