ARTICLE · 1085164
【LevelDB 源码阅读】00 开篇词:我为什么想学习 LevelDB 源码
最初接触 LevelDB 时，我对它的认识主要来自几个概念：LSM Tree，MemTable，SSTable 和 Compaction。看了不少介绍 LevelDB 原理和文件存储结构的技术文章。对于 LevelDB 大致的工作过程似乎也有了一些认识。数据先写入日志和内存，MemTable 达到一定大小后被写成 SSTable，后台再通过 Compaction 整理逐渐积累的文件。
但这些宽泛的概念和笼统的介绍并不能让我真正理解 LevelDB。
我还缺少了“Show me the code”这一步。
于是我开始尝试去阅读 LevelDB 的源码。在源码阅读的过程中，我也能够逐渐将 LevelDB 的代码实现和原理对应起来。同时，在阅读源码的过程中，我也产生了许多新的疑问，例如为什么要用这种实现方式？这样实现是为了解决什么问题？和其他比较知名的组件相比，LevelDB 这么实现是为了解决哪些场景的问题？
通过不断产生疑问并解决疑问的过程，我也对 LevelDB 有了更清晰的认知。因此，我也产生了写这么一系列文章的想法，也是为了记录下我这一路的思考，当作一次再学习。
在阅读源码之前，我对自己提出的第一个问题是：
在 LevelDB 中，一次 Put 操作都经历了哪些步骤？
于是我开始阅读与 `Put` 操作有关的源码实现，很快又产生了新的问题：
为什么写请求需要排队？
多个写请求如何合并成一个 WriteBatch？
MemTable 为什么使用跳表？
SSTable 为什么压缩 Key 的公共前缀，却不单独压缩 Value？
一个 Key 同时出现在内存和多个 SSTable 中时，LevelDB 如何确定应该返回哪个版本？
已经落盘的数据为什么还要经过反复合并和重写？
这其中任何一个问题的代码都可以在某个文件中找到，但为什么这么实现，却涉及整个 LevelDB 的设计哲学。只有将所有这些问题对应的代码流程串联起来，分析（有时也需要猜测）其需要解决的问题，才能对当时编码的取舍窥见一二。
通过深入阅读代码，我们才能够清晰地认识到，一次写入会同时影响日志、MemTable 和序列号。一次读取可能需要查看多个数据源。一次 Compaction 不只是合并文件，还会改变文件之间的版本关系。LevelDB 的各个模块并不是孤立工作的，许多看似局部的选择，实际都来自整个存储流程的约束。
从 GitHub 仓库获取 LevelDB 的源码后（本系列阅读的是 v1.23），我们可以看到如下目录结构：
... db/ ... include/ ... table/ ... util/
关于每个目录具体实现的功能，我会在后面的系列文章中展开说明。在这里，我想先聊一些“宽泛”的内容。
刚接触源码时，我们很容易就陷入到具体代码的研读中，陷入理解每一行代码意思的泥沼中，最终只知部分，不知全貌。
例如，只看 table/block_builder.cc，可以知道一个 Entry 如何被写入 DataBlock；但要理解它为什么采用这种编码，还需要知道 SSTable 是不可变的、有序的，也需要考虑磁盘空间、读取成本和范围扫描。
因此，带着某个问题去阅读源码，沿着数据流动的方向和变化的过程阅读源码，更有利于我们理解整个系统的运作模式。
回到我之前提出的问题：
在 LevelDB 中，一次 Put 操作都经历了哪些步骤？
在阅读的过程中，我们就会涉及多个概念，沿着数据流动的方向，我们就可以把这些概念连接起来：
Put → WAL → MemTable → Immutable MemTable → SSTable → Compaction先跟随一条数据进入系统，再观察它如何从内存来到磁盘，如何被读取，如何产生新的版本，又如何在某次 Compaction 中被清理。
这个过程中，我会记录关键的源码实现，但也会保留阅读时产生的问题：
这段代码解决的是什么问题？
它依赖了哪些前提？
如果替换一种数据结构，行为会发生什么变化？
这个选择带来了哪些收益，又增加了哪些成本？
后来的存储引擎是否保留了这个设计？
我不打算把这些问题都写成确定的结论。源码能够告诉我们 LevelDB 做了什么，但“为什么这样做”有时来自代码，有时来自硬件和使用场景，还有一些理解可能只是阅读过程中的推测，需要结合其他系统继续验证。
学习 LevelDB 时，我经常会联想到以前接触过的其他存储系统，例如 Redis。
两者都保存 Key-Value，也使用了一些相似的数据结构。但当相同技术出现在不同系统中时，它们承担的职责可能并不相同。
比如跳表。
Redis 使用跳表实现 Sorted Set，需要支持长期、持续的插入、删除、排名和范围查询。LevelDB 将跳表用于 MemTable。一代 MemTable 写满后便不再修改，随后被写成 SSTable，并在完成 Flush 后整体释放。
它们使用了相似的数据结构，却有不同的生命周期：
Redis 中的跳表长期存在，持续更新。
LevelDB 中的跳表属于一代 MemTable，冻结后整体淘汰。
这种差异让我开始关注一个问题：选择数据结构时，除了查找和插入的时间复杂度，我们是否也应该考虑数据的生命周期、更新方式以及最终去向？
DataBlock 和 Redis SDS 的差别也给了我类似的启发。
SDS 管理的是内存中的动态字符串，需要考虑长度获取、空间分配、扩容和二进制安全。SSTable 中的记录一旦生成便不再修改，因此 DataBlock 并不需要解决字符串原地扩容的问题。
LevelDB 选择利用相邻 Key 的有序性进行前缀压缩。例如：
user:1001:addressuser:1001:emailuser:1001:name
这些 Key 的公共部分比较稳定，而 Value 的格式由调用方决定，可能是文本、序列化对象，也可能是已经压缩过的二进制数据。与其假设 Value 具有某种结构，LevelDB 更愿意将它视为一段不透明的字节。
把这两种实现放在一起，我们可以了解到当面对的环境存在差异时，我们在做设计时应该关注哪些问题：
SDS 关注内存中的动态对象
DataBlock 关注磁盘上的不可变记录
当存储介质、数据生命周期和访问方式发生变化时，即便都在保存字符串，设计重点也会随之改变。
除了 Redis，我也会在阅读过程中联想到 InnoDB、RocksDB、Pebble 和其他开源项目。
这些对比不会单独放在系列末尾，也不会追求一一对应。我的想法是，在遇到具体问题时，寻找一个合适的参照。
讨论 WAL 时，可以一起看看 Redis AOF 和 InnoDB RedoLog。它们都使用追加写，但记录的内容、恢复目标和生命周期并不完全相同。
讨论 MemTable 时，可以对比 Redis Sorted Set 中的跳表，观察相同数据结构如何服务于不同的读写过程。
讨论 DataBlock 时，可以联系 Redis SDS、Listpack 以及 InnoDB 的数据页，看看内存对象、不可变 Block 和可更新 Page 各自在意什么。
讨论 Bloom Filter 时，可以比较它在缓存场景和 SSTable 查询中的不同位置。同一个概率型数据结构，在 Redis 场景中可能用于避免无效的后端查询，在 LevelDB 中则用于减少不必要的 SSTable 读取。
讨论 RocksDB 时，我更想关注它在 LevelDB 的基础上增加了什么，以及这些变化对应了哪些新的工作负载和工程问题。
我希望这些对比能帮助自己回答两类问题：
LevelDB 为什么采用这种实现？
当约束发生变化时，这种实现是否仍然适用？
这个系列会从整体结构开始，但不会一次介绍完所有模块。
我计划先跟踪写入路径：
DBImpl::Write → Writer Queue → WriteBatch → WAL → MemTable接着从 MemTable 的冻结和 Flush 进入 SSTable，逐步分析 DataBlock、Index Block、Filter Block 和 Footer。
理解文件结构后，再回到读取路径：
MemTable → Immutable MemTable → Level 0 → Level 1...N这里会涉及 Iterator、Table Cache、Block Cache、Bloom Filter、序列号和 Snapshot。
最后再进入 Compaction、VersionSet 和 Manifest。对我而言，这部分也是 LevelDB 中最难建立完整认识的区域。文件不断产生、被引用、参与合并并最终删除，而读取过程还要在这些变化中获得一致的视图。
我的阅读路径大致可以整理为几条相互交叉的线索：
写入如何被接收和持久化？
内存中的数据如何变成 SSTable？
查询如何跨越多个数据源？
新旧版本如何共存？
后台如何整理不断增加的文件？
元数据如何记录文件集合的变化？
这些线索不会完全按照源码目录的顺序展开。有些问题可能需要先跳到后面的模块，再回来补充前面的理解。我也会尽量保留这种真实的阅读过程，而不是事后把所有内容整理成一条过于平滑的路线。
按这个顺序，系列正文将分成五个部分：全景与写入路径、SSTable 文件格式、读取路径、Compaction 与版本管理，以及最后的综合与实践——把前面积累的认知落回两件事：怎么用好 LevelDB，以及从源码里还能带走哪些通用的工程模式。
这不是一套 LevelDB 使用教程，也不是对源码的逐行翻译。它是我在阅读 LevelDB 源码时的一篇篇阅读笔记：以 LevelDB 为主线，记录我如何从一次写入开始，逐渐理解一个 LSM 存储引擎的基本结构。
文章中会有源码分析，也会涉及数据结构、文件格式和工程取舍。
每篇文章围绕一个主干主题，并视情况带两个固定小节：对比参照，就具体问题与其他系统做对照；工程启示，再分成两类——怎么用好 LevelDB（参数、API、坑），以及哪些设计当我们在遇到类似问题时可以借鉴。
有些篇目可能围绕完整流程展开，有些则会集中讨论一个细节，例如：
Writer Queue 如何组织并发写入？
WAL 为什么采用分片的 Record 格式？
SkipList 为什么适合 MemTable？
DataBlock 如何平衡前缀压缩与随机查找？
Value 为什么被视为不透明字节？
Bloom Filter 如何减少无效读取？
Level 0 为什么具有特殊的查询和合并规则？
VersionSet 如何描述不断变化的文件集合？
空泛地讨论存储引擎，很容易变成名词解释。在学习代码或组件时，实际操作一番往往是最好的入门方式。在整个系列中，我会尝试用一个短链接服务作为贯穿始终的示例，从第一篇跑通第一个 Demo、引入它的 key 设计开始，到临近结尾时为它做一次完整的参数调优。
它的访问模式恰好能覆盖 LevelDB 的各个侧面：
写入热点：创建短链，会经过写队列、WriteBatch、MemTable 和 Flush；
点读多、不存在的 Key 也不少：解析短码，包括爬虫扫不存在的码，正好考验 Bloom Filter 和缓存；
计数器的读改写：点击计数是典型的热点更新；
按用户范围扫描：遍历某用户的全部短链，对应 Iterator 的正确用法；
过期删除：过期短链的清理，对应墓碑与 Compaction 的空间回收；
一致性导出：每日统计报表，对应 Snapshot。
初始的 Key 设计如下，后续会随着讨论深入再回头审视它：
c:{code} → 短码主体记录（目标 URL 等元数据） c:{code}:click → 点击计数 u:{user}:c:{code} → 用户 → 短码索引（范围扫描）
此外，部分篇章还会有一些额外的实操示例：例如对真实的 SSTable 文件做 hex dump、kill -9 之后的恢复重放、缓存命中率统计等。
我也希望在写作过程中不断修正自己的理解。如果某些判断随着阅读深入发生变化，我会保留这种变化，并说明原来的认识忽略了什么。
LevelDB 并不是今天功能最丰富的 LSM 存储引擎，但它的代码仍然提供了一个相对清晰的入口。通过它，可以看到日志、内存结构、不可变文件、缓存、过滤器、Compaction 和版本管理如何组合在一起。
下一篇，我会先站远一点看全貌：LevelDB 从哪里来，作为一个嵌入式 Key-Value 库它处在什么位置，代码是怎么组织的。也是在这一篇，短链接服务会正式登场。
然后，回到这个最基本的问题：
当数据无法全部留在内存中时，一个 Key-Value 存储需要重新面对哪些问题？
再回到这行看似简单的代码：
db->Put(write_options, key, value);看看一条短链数据从这里出发，会经历哪些过程，在内存和磁盘之间如何流转。
