LSM 树：结构及其原理浅析（LevelDB）

LSM 介绍

LSM （Log Structured-Merge Tree）是一种“攒攒再写”的结构，相比于 B+tree 写入性能更好，读取性能更烂。前人之述备矣，我们直接进入正题。主要以 LevelDB 为例。

操作机制

在讲内存结构之前，说一下操作机制。虽然头一次看会有点晕，但是你必须前后对照，两个一起看，不然看不清楚。

写入

注意：所有结构其内部的数据都是有序的

写入时，先写日志（WAL）
然后写 MemTable
1. 如果 MemTable 达到阈值，则转换为 Immutable MemTable，并准备转移到磁盘成为 SSTable
2. 如果 SSTable 过多，则合并为更简练的 SSTable

由于只进行一个日志写和 MemTable 写就返回给用户，写性能比 InnoDB 好得多。

预写式日志（Write-ahead logging，WAL）：即在所有操作提交前写日志。典型的如 InnoDB 用日志文件组存放 Checkpoint 和 redo log，而 LevelDB 只是简单地 Append 到 Log 文件日志。这是 LSM 树数据库防止断电丢数的最主要机制。

删除

删除实际上就是追加标记。也就是说，并不会在记录原本的位置标记删除，而是用一条新的日志标记删除。

更新

更新实际上还是追加，只不过新的值更靠后。

读取

读取会以 Key=UserKey+Seq 作为索引，依次从 MemTable、Immutable MemTable、SSTable 从后往前查找，第一次找到（无论是找到值还是删除标记）就返回。

另外需要一提的是，程序并不会傻傻地顺序回溯，实际上每个 SSTable 和 MemTable 一样都是有序结构。因此可以利用二分加速查询索引。

然而，最糟糕的情况下，这个 Key 根本不存在，那么无论你 SSTable 有多大都会全扫一遍。这是灾难性的，被称为“读放大”，因此 Level DB 通过这几种方式减轻伤害：

Cache
1. TableCache：从 SSTable 到对应的索引块和元数据块的映射。
2. BlockCache：从 SSTable 文件号到 TableAndFile 对象的映射。缓存解压后的数据块。
3. 原理都是 LRU，即双链表配合哈希表。LevelDB 的 LRU 对多线程做了优化，可以分片上锁。
BloomFilter：
1. 引入：常用位图实现。传统位图的思路是，存在，就给对应位置标 1. 但这样无法适应大数据，会导致巨大的位图。
2. 介绍：BloomFilter 利用哈希函数，初始为 0，SSTable 插入值后，对值进行散列然后将 Bloom 数组对应位置（超长的取余数）标 1. 从而实现：有限空间下大概率猜中存不存在。
3. 假阳性问题：明明不存在，却以为存在。
压缩合并

我记得自己前几个月去面 PingCAP，面试官让我半小时写一个细粒度锁的线程安全 LRU 缓存。最后毫无悬念挂了。回来一看，原来就是 LevelDB 实现的这种，核心就是LRU 缓存分片，从而可以对局部加锁。当然即便知道原理，我也起码得一两天才能写出来。可能还有更简洁的实现，欢迎留言。

顺带提一下：除了读放大，还有写放大，就是说为了向硬盘写入 512B，硬盘内部可能实际上得先读出 4KB 然后和写入的新数据合并，再把这 4KB 写入。导致实际上写入的数据量远大于我们所以为的。

另外还有空间放大，主要是 LSM 树通过追加标记状态迁移，因此会残存大量失效的历史状态，造成空间浪费。

内部：压缩

从抽象的角度，甚至可以把写入和删除都看作是对 K,V 压栈，而读取就是从栈顶向历史回溯，找到第一个匹配的 K,V 。

因此这种“屏蔽”效应会导致可能有大量的历史失效，这些历史数据会被后台线程在压缩（合并过程）清理。每次进行 Compaction，Level DB 就会创建一个新版本

为了性能的考虑，当文件较大时，可能真实行记录不会和 Key 存放在一起，而存放在一起的是 Offset，然后根据 Offset 再去精准读取具体的记录数据。

错误恢复

错误恢复时：

先读取CURRENT文件，获取最新的 MANIFEST 文件名，从而找到最新 MANIFEST 文件。
里面的日志是 VersionEdit 格式，使用 VersionEdit::DecodeFrom 解析，然后按照日志创建 version 并恢复（Finalize）
恢复的过程就是按日志写 SSTable。

存储结构

内存结构

内存中有 MemTable 和 Immutable MemTable。

MemTable

MemTable 是 KV 表。因此可以用 AVL，B 树，RB 树，跳表实现。LevelDB、elasticsearch 用的就是跳表。反正对外就暴露哈希表接口。

跳表：跳表是一种非常简单的链状二分搜索结构，期望时间复杂度 $O(\log n)$ ，最坏 $O(n)$

Immutable Memtable

Immutable Memtable 是定格后的 MemTable。定格，是因为和 MemTable 内容完全一样，只不过不能再写入了，但是内容一样不代表结构一样，Immutable Memtable 由于要落盘，会采用更适合顺序读的结构存放。

它也是跳表结构。

磁盘结构

Log

日志文件。通过追加写入，类似 InnoDB 的 Redolog。

当 Log 超过 1MB 时，会创建新的 MemTable 以及新的 Log 文件。而旧的 MemTable 变成不可变，被后台线程 Dump 到 SSTable 文件。每条日志一个 LSN（Sequence），单调递增。

SSTable

SSTable（sort-string table，排序字节串表）是磁盘中的结构。具体来说并不是一个文件，而是一系列有层级的文件。具体来说，LevelDB 的 SSTable 从 Level 0 到 Level N 分为多层。每一层包含多个 SST 文件。

文件内数据有序（并且不是树，而是线性排列的，非常直白的 K,V 序列）。

实际上论文没有规定你怎么实现的有序，此处以 LevelDB 为例。

Level 0 SST 由Immutable Dump 产生。>= Level 1 的 SST 通过归并顺序写产生。没有真正的删除，只有标记删除。

如果一个 Level 的大小超过限制，就会合并到 Next Level，一般来说 Level 越高大小上界越高。

注：此处的文件内记录的顺序是主键顺序，不是时间顺序。

需要注意的是，Level 0 的 SSTable 文件，其 Key 范围可能有交集（比如一个是 a~~d，另一个是 c~~g），所以需要合并。由于 Level 0 到 Level 1 的过程中完成了合并，对于 Level > 0 的不会重合。

为什么会重合呢？

这是因为 Level DB 有小压缩（minor compaction）和大压缩（major compaction）之分。

小压缩：遍历 Immutable SkipList，从小到大排列，得到 Level 0 SSTable。而各次导出自然会可能重叠。

大压缩：如果剩余层级也有重叠，查找起来必然极其低效，所以会进行消除重叠的压缩合并。如果你刷题经验丰富，会见过“合并K个有序链表”这种题，实际上就和大压缩很像。就是针对有重叠线性文件的多路归并排序。

Manifset-[:num:]

这是元数据文件。记录 Level DB 的元信息，例如 Comparator，SSTable 的层级信息，最小最大记录 Key。

每次 Level DB 启动，会产生一个 CURRENT 文件，表示使用中的 Manifest.

Manifest 格式和 Log 一致，记录了启动以来的所有状态迁移。以 VersionEdit 形式写入

参考

CppGuide/articles/leveldb源码分析 at master · balloonwj/CppGuide

庖丁解LevelDB之概览 | CatKang的博客

LevelDB设计与实现_AndersCloud的博客-CSDN博客

布隆过滤器 — leveldb-handbook 文档

对论文感兴趣可以看：【Paper笔记】The Log structured Merge-Tree（LSM-Tree） ·