RocksDB 是怎么工作的：一份 LSM-Tree 的极简笔记

准备面试的时候，我花了点时间，把 RocksDB 的工作原理从头到尾学了一遍——它的存储引擎到底是怎么设计的，数据是怎么写进去、又怎么读出来的。RocksDB（以及它背后的 LSM-Tree）是那种很多人听过、但真要讲清楚就容易卡壳的东西，我自己以前也是。等真的搞懂了，就把里面的核心思路整理成这份笔记，分享给同样想弄明白它的人。

我不敢说讲得有多专业、多全面，但希望读完，你（还有未来的我）能对「RocksDB 大概是怎么转起来的」有一个清楚的整体印象。下面这些英文词我尽量保留原样（LSM-Tree、MemTable、SST、WAL、compaction……），因为面试和文档里大家就是这么说的，硬翻成中文反而别扭。

一句话：一个可嵌入的、持久化的键值（key-value）存储引擎。

可嵌入（embedded）：它不是一个像 MySQL 那样单独跑的服务器，而是一个库，直接编进你的程序里，省掉了进程间通信的开销。
持久化：数据落在磁盘上，崩了也不丢。
2012 年从 Google 的 LevelDB fork 出来，用 C++ 写的，专门为 SSD 和写多的场景做了优化。Meta、Microsoft、Netflix、Uber 都在用。
它不是分布式的——副本、分片这些得你自己在上层做。

它对外提供的操作很朴素：put(key, value) 写、get(key) 读、delete(key) 删、merge(key, value) 合并、还有 iterator.seek() 做范围扫描。

核心思想：LSM-Tree

RocksDB 的一切都建立在 LSM-Tree（Log-Structured Merge-Tree，日志结构合并树） 上。

它要解决的核心矛盾是：磁盘最怕随机写，最喜欢顺序写。LSM 树的思路就是——先把写攒在内存里排好序，再一次性顺序地刷到磁盘。换句话说，它把大量随机写「攒」成了顺序写，这就是它写得快的根本原因。

结构上，数据分成很多层：最上面一层在内存里，下面一层层在磁盘上，编号 L0、L1、L2……越往下的数据越老、容量越大（通常下一层是上一层的约 10 倍）。

内存   ┌──────────────────────────────┐
       │  MemTable（可写，内部有序）    │  ← 新数据先进这里
       └──────────────────────────────┘
- - - - - - - - - - - - - - - - - - - - - -  flush（刷盘）
磁盘   L0   [SST] [SST] [SST]      ← 最新；文件之间 key 范围可能重叠
       L1   [SST][SST][SST][SST]   ← 每层内部 key 不重叠，且更大
       L2   [SST][SST] ......      ← 越往下越老、越大（约 ×10）
       ...

这套结构 1996 年就提出来了，专门优化写密集的负载。除了 RocksDB，Bigtable、HBase、Cassandra、MongoDB 的 WiredTiger 引擎用的也都是 LSM 树。

写：数据是怎么进去的

一次写入，会同时落到两个地方：

put(key, value)
      │
      ├──► WAL    （顺序追加到磁盘，防崩溃）
      │
      └──► MemTable（在内存里排好序）
                  │  写满约 64MB
                  ▼
            转为只读，后台线程刷成一个 SST 文件 → 落到 L0

MemTable：内存里的写缓冲，所有增删改都先到这。它内部是按 key 排好序的（默认用跳表 skip list 实现），这样后面刷盘和范围查询才高效。一个细节：删除不是真的把数据抹掉，而是写一条墓碑（tombstone）记录，表示「这个 key 删了」——真正的清理留给后面的 compaction。

WAL（Write-Ahead Log，预写日志）：MemTable 在内存里，断电就没了。所以每次写也会顺序追加一条记录到磁盘上的 WAL 文件，里面有 key、value、操作类型和校验和（checksum）。崩溃重启后，靠重放 WAL 把 MemTable 恢复出来。注意 WAL 是按写入顺序追加的，不排序——它图的就是个快。

Flush（刷盘）：MemTable 写满后会变成只读，换一个新的继续接客；后台线程把这个只读的 MemTable 刷成一个 SST 文件，落在 L0。刷完，对应的 WAL 就可以丢了。因为 MemTable 本来就是有序的，这一刷就是一次顺序写——LSM 树的精髓就在这儿。

SST 文件长什么样

SST（Static Sorted Table，静态有序表） 是磁盘上真正存数据的文件，一旦写好就不再修改。它里面是一堆排好序的 key-value，并且为了查询方便做了精心的分块设计（block，默认 4KB，可以用 Snappy、LZ4、ZSTD 等压缩）。

一个 SST 大致分几部分：

数据块（data）：有序的 key-value。因为相邻 key 很像，可以只存差异（delta encoding）省空间。
索引（index）：记录每个数据块「最后一个 key → 在文件里的位置」，这样查的时候能二分直接定位到某个块，而不用扫整个文件。
布隆过滤器（Bloom filter，可选）：一个概率型结构，能极快地回答「这个 key 一定不在这个文件里」。它可能误报「在」，但绝不漏报「不在」——所以特别适合在读的时候先挡掉一大批根本不用查的文件。

读：数据是怎么找出来的

读一个 key，要从新到老一层层找，因为新写的值在上层、旧值在下层，第一个找到的就是最新的：

先查正在写的 MemTable；
再查还没刷完的只读 MemTable；
再查 L0 的每个 SST 文件（L0 文件之间 key 范围会重叠，所以得挨个看，从新到旧）；
L1 及以下，每层内部 key 不重叠，所以每层只需定位并查一个文件。

而在单个 SST 文件里找，又是三步走：先用 Bloom filter 问一句「key 在不在」，不在就直接跳过这个文件；在的话，用 index 二分定位到对应的数据块；最后把那个块读出来，在块内找到 key。

所以读的代价，关键看要翻多少层、多少文件——这也引出了下一节要解决的问题。

Compaction：后台一直在「打扫」

前面说了，删除只是写墓碑、更新也只是写新值盖在旧值上面。时间一长，磁盘上就会堆满过期的旧版本和墓碑：既白占空间，又让读的时候要翻越更多文件。

Compaction（压缩合并） 就是后台干这个清理活的：把某一层的若干 SST 文件，和下一层有重叠的文件合在一起，丢掉那些被覆盖的旧值和被删的 key，再写成新的、干净的 SST 放到下一层。因为每个文件本来都有序，合并用的是多路归并（k-way merge），就是归并排序里「合并」那一步的放大版。整个过程在后台线程跑，不挡前台的读写。

RocksDB 默认用 leveled compaction（分层合并）：

L0 比较特殊，文件之间 key 范围允许重叠（因为它们是 MemTable 直接刷下来的）；当 L0 文件数攒到阈值（默认 4 个）就触发合并。
L1 及以下，每一层内部所有文件的 key 范围互不重叠、整体有序；当某层的总大小超过设定值，就把超出的部分往下一层合并，有时会一路连锁往下压好几层。

一切都是权衡：三种「放大」

理解 RocksDB（其实是所有 LSM 引擎）调优的关键，是三个放大（amplification）指标：

空间放大（space amplification）：实际占的磁盘空间 ÷ 数据本身的大小。旧版本和墓碑越多，空间放大越大。
读放大（read amplification）：读一条数据，底层实际要做几次 I/O。要翻的层和文件越多，读放大越大。
写放大（write amplification）：写一条数据，底层实际写了几次。同一条数据会在 compaction 里被反复重写到更下面的层，所以写放大会很大。

这三者按下葫芦浮起瓢：compaction 越勤，空间和读放大越小，但写放大越大；反之亦然。怎么平衡全看你的负载，参数极多且互相影响——连 RocksDB 官方都坦言很难讲清每个参数的确切效果，建议多做 benchmark，盯着这三个放大指标调。

顺带一提：merge 操作
除了 put 和 delete，RocksDB 还有个 merge。当你要对一个值做大量「增量更新」（比如不停往一个计数器或列表上追加）时，传统做法是 read-modify-write：读出来、改、再写回去，很费劲。merge 让你只写「增量」本身，把怎么合并交给一个你自定义的 merge 函数，到读取或 compaction 时再真正算出最终值。好处是省写放大、还线程安全；代价是读变贵了——没合并之前，每次读都得把这些增量重新算一遍。

记住这几点就够了

如果只留一张「脑图」，是这样的：

RocksDB = 可嵌入的持久化 KV 存储，源自 LevelDB，核心是 LSM-Tree；
写：先进内存的 MemTable（有序）+ 顺序写 WAL（防崩溃）→ 攒满后刷成 SST 文件落到 L0 → 后台 compaction 慢慢往下整理；
读：从新到老一层层找，靠 Bloom filter + index 跳过和定位，少读冤枉文件；
本质：用「写放大」换「把随机写变成顺序写」的高吞吐——空间、读、写三种放大之间，永远是权衡，没有免费的午餐。

把这几句记住，RocksDB 的大框架就立起来了。更细的东西——skip list、delta encoding、各种 compaction 策略、参数到底怎么调——等真正用到的时候再往里钻也不迟。

这份笔记里不少理解，来自 Artem Krylysov 的 How RocksDB Works——原文讲得非常细致，想往深里走的话很推荐读一读。

推荐订阅源

博客 on Neil的自留地