整体架构

LevelDB 整体架构.png

上图简单展示了 LevelDB 的整体架构。LevelDB 的静态结构主要由六个部分组成：

1. MemTable：内存数据结构，具体实现是 SkipList。 接受用户的读写请求，新的数据修改会首先在这里写入。
2. Immutable MemTable：当 MemTable 的大小达到设定的阈值时，会变成 Immutable MemTable，只接受读操作，不再接受写操作，后续由后台线程 Flush 到磁盘上。
3. SST Files：Sorted String Table Files，磁盘数据存储文件。分为 Level0 到 LevelN 多层，每一层包含多个 SST 文件，文件内数据有序。Level0 直接由 Immutable Memtable Flush 得到，其它每一层的数据由上一层进行 Compaction 得到。
4. Manifest Files：Manifest 文件中记录 SST 文件在不同 Level 的分布，单个 SST 文件的最大、最小 key，以及其他一些 LevelDB 需要的元信息。由于 LevelDB 支持 snapshot，需要维护多版本，因此可能同时存在多个 Manifest 文件。
5. Current File：由于 Manifest 文件可能存在多个，Current 记录的是当前的 Manifest 文件名。
6. Log Files (WAL)：用于防止 MemTable 丢数据的日志文件。

粗箭头表示写入数据的流动方向：

1. 先写入 MemTable。
2. MemTable 的大小达到设定阈值的时候，转换成 Immutable MemTable。
3. Immutable Table 由后台线程异步 Flush 到磁盘上，成为 Level0 上的一个 sst 文件。
4. 在某些条件下，会触发后台线程对 Level0 ~ LevelN 的文件进行 Compaction。

读操作的流动方向和写操作类似：

1. 读 MemTable，如果存在，返回。
2. 读 Immutable MemTable，如果存在，返回。
3. 按顺序读 Level0 ~ Leveln，如果存在，返回。
4. 返回不存在。

参考文档

• LevelDB 实现原理
• LevelDB Source Code
• MyRocks Deep Dive (slide)