leveldb源码学习(1)-背景知识

发表于 分类于

学习背景

虽然我的工作内容是纯缓存redis，但是也经常跟做磁盘数据库的同学交流沟通，我发现深入的理解rocksdb这种十分常用的kv数据库是相当有必要的。它能补齐我磁盘数据库知识缺失的一块。

并且，不能只从宏观原理上理解，比如只理解lsm-tree就可以了，我渴望从更深层的底层源码理解它的运作。

考虑到rocksdb过于复杂以至于并不适合新手学习lsm-tree的kv引擎，加上有句话说：“跟leveldb学习c++”，我决定开始学习leveldb。

几个链接：

基础术语与宏观理解

这里更多是翻译的其doc/impl.md的内容，并增加自己的一些理解。

核心文件类型（精简核心组件）

WAL 日志文件（Write-Ahead Log，*.log）

  • 定义：LevelDB 的预写日志文件，是保障崩溃一致性的核心组件。
  • 核心机制：所有写操作（Put/Delete）会先以追加方式写入当前 WAL 日志，再写入内存中的 MemTable。这种 “先写日志，后写内存” 的设计，确保崩溃后可通过日志恢复 MemTable 数据。
  • 触发切换：当日志文件达到预设阈值（默认 4MB）时，触发 MemTable 刷盘（生成 sstable），同时创建新 WAL 日志承接后续写操作。
  • 关键解析：WAL 日志与 MemTable 是 “逻辑绑定” 关系，同一时段内一个 WAL 对应一个活跃 MemTable，刷盘后旧 WAL 会被标记为过期，等待垃圾回收。

排序字符串表（SSTable，*.ldb，*.sst）

  • 定义：LevelDB 的持久化存储核心，是按键有序排列的不可变数据文件。
  • 存储内容：每个条目包含 InternalKey（用户键 + 序列号 + 操作类型）与对应值，或键的删除标记（tombstone）—— 删除标记用于屏蔽旧 sstable 中已过时的键值对，避免读取时返回无效数据。

层级组织规则：

  • 0 级（Level-0）：由 MemTable 刷盘直接生成，特点是文件可能存在键范围重叠（因 MemTable 刷盘是独立触发的），读取时需合并所有重叠文件。
  • 1 级及以上（Level-L，L≥1）：文件键范围互不重叠，层级越高，单文件数据量越大，Level-1 为 10MB，Level-2 为 100MB，以此类推。

核心价值：不可变特性避免了写时冲突，用于只允许追加写，为磁盘高效写设计。

清单文件（MANIFEST）

  • 定义：数据库元数据的 “变更日志”，记录全量层级信息与文件元数据。
  • 存储内容：各层级包含的 sstable 列表、每个 sstable 的键范围（smallest_key/largest_key）、当前 WAL 日志号（log_number）、最大序列号（last_sequence）等核心元数据。
  • 更新机制：采用追加写（Append-Only）模式，数据库重启或元数据变更（如 Compaction、sstable 增减）时，不会修改原有文件，而是生成新 MANIFEST 文件并更新 CURRENT 指向。

manifest的内容实际上可以理解为VersionEdit数组，每次版本更替时（比如memtable刷盘成sst），会往文件里面追加写入一条VersionEdit。因此重放时，从头到尾依次读出VersionEdit，最后整合为当前的Version，涵盖了每个level的文件列表。

当前指针文件（CURRENT）

  • 定义：轻量级文本文件，仅存储最新 MANIFEST 文件的文件名。
  • 核心作用：简化恢复流程 —— 数据库启动时无需遍历所有 MANIFEST 文件，只需读取 CURRENT 即可定位最新元数据文件，提升启动效率。

辅助文件

  • LOCK 文件：进程级排他锁，防止多个进程同时操作同一数据库目录，避免数据损坏。
  • INFO 日志（LOG/LOG.old）：记录系统运行日志（如 Compaction 触发、错误信息），用于问题排查。
  • 临时文件（*.dbtmp）：Compaction 或刷盘过程中生成的中间文件，操作成功后会重命名为正式 sstable，失败则直接删除，不影响数据一致性。

压实操作（Compaction）

MemTable 刷盘与 Level-0 生成

  • 触发条件：当前活跃 MemTable 对应的 WAL 日志达到 4MB 阈值。

核心流程：

  1. 原子创建新 MemTable 与新 WAL 日志，后续写操作直接导向新组件；
  2. 后台线程将旧 MemTable 数据有序写入磁盘，生成 Level-0 sstable；
  3. 刷盘成功后，释放旧 MemTable 内存，标记旧 WAL 日志为过期；
  4. 将新 sstable 加入 Level-0 层级。

设计解析：刷盘过程采用 “后台异步 + 原子切换”，实际上在一个memtable写满后不会直接刷盘否则会阻塞前台写操作，而是变成immutable-memtable，等待后台线程刷盘和更新manifest，同时旧组件仅在刷盘成功后释放，确保崩溃时可通过旧 WAL 恢复数据。

核心流程

定义：LevelDB 核心后台任务，用于解决 sstable 累积导致的读取性能下降，核心目标是 “合并数据、清理过期条目、维持层级结构”。

触发条件：

  • Level-0：文件数量超过 4 个（因文件重叠，数量过多会导致读取时需合并大量文件）；
  • Level-L（L≥1）：总数据量超过10^L MB 阈值。

核心逻辑：

  1. 选文件：Level-0 压实会选取所有含有重叠key范围的文件，Level-L（L≥1）仅选取一个文件及 Level-L+1 中所有有key范围重叠的文件；
  2. 归并排序：将选中文件的键值对按 InternalKey 重新排序，过滤过期值（被覆盖的键）与无效删除标记（无更高层级文件包含该键范围）；
  3. 生成新文件：按 2MB 分片生成 Level-L+1 新 sstable，确保新文件键范围不重叠；
  4. 原子替换：新文件写入成功后，将旧文件标记为过期，更新 MANIFEST 元数据。

特定层级的压实操作会按键空间（key space）循环执行。具体来说，对于每个层级 L，系统会记录该层级上一次压实操作的结束键；下一次 L 层级的压实操作会选取第一个起始键位于该结束键之后的文件（若不存在此类文件，则循环回到键空间的起始位置）。

压实操作会丢弃被覆盖的值（overwritten values）；若不存在更高编号的层级包含与当前键范围重叠的文件，则会一并丢弃该键的删除标记（deletion markers）。

时间开销 Timing

Level-0 压实操作最多会从 Level-0 读取 4 个 1MB 大小的文件，最坏情况下需读取所有 Level-1 文件（总计 10MB）。即，压实过程需读取 14MB 数据并写入 14MB 数据。

除特殊的 Level-0 压实外，会从 L 层级选取 1 个 2MB 大小的文件。最坏情况下，该文件会与 L+1 层级的约 12 个文件重叠（其中 10 个源于 L+1 层级的总大小是 L 层级的 10 倍，另外 2 个源于 L 层级与 L+1 层级的文件键范围通常无法对齐，导致边界处额外重叠）。因此，压实操作需读取 26MB 数据并写入 26MB 数据。假设现代硬盘的 I/O 速率为 100MB/s（常规水平），最坏情况下压实耗时约 0.5 秒。

若将后台写入速率限制在较低水平（例如，硬盘峰值速率 100MB/s 的 10%），一次压实操作可能耗时长达 5 秒。若用户写入速率为 10MB/s，Level-0 可能会累积大量文件（约 50 个文件，用于存储 5 秒内写入的 50MB 数据）。这会导致读取时需合并更多文件，显著增加读取开销。

26MB/(10MB/s) = 2.6秒，但这是最理想的情况，文档写5秒估计是测试结果。

解决方案

  1. 当 Level-0 文件数量较多时，可提高日志切换阈值（即 WAL 日志触发刷盘的大小阈值）。但该方案的缺点是，阈值越大，对应的 MemTable 所需占用的内存就越多。
  2. 当 Level-0 文件数量增加时，可人工降低写入速率。
  3. 优化大范围合并的开销。实际上就是增加block_cache的大小，让level0的大部份文件的原始数据在内存中存在，就不用去磁盘读了。

恢复流程（Recovery）

  1. 读取 CURRENT 文件，获取最新已提交的 MANIFEST 文件名称；
  2. 读取该 MANIFEST 文件，重建层级元数据；
  3. 清理过期文件（未被任何层级引用的 sstable 及旧 WAL 日志）；
  4. 此处可打开所有 sstable，但采用惰性加载（按需打开）或许更优 —— 避免启动时加载大量无关数据，提升恢复速度；
  5. 将未过期的 WAL 日志片段转换为新的 Level-0 sstable；
  6. 创建新的 WAL 日志文件，沿用恢复得到的最大序列号（sequence number），承接后续写入操作。

文件垃圾回收（Garbage collection of files）

RemoveObsoleteFiles() 函数会在每次压实操作结束后及恢复流程完成后调用。该函数会遍历数据库目录下的所有文件，执行以下清理逻辑：

  1. 删除所有非当前活跃 WAL 日志的日志文件；
  2. 删除所有未被任何层级引用、且不属于活跃压实操作输出的 sstable 文件。

使用方法

这里先不赘述了，有空用中文写一遍。

我觉得官方文档的index.md文件写的非常好。能从对外能力上，全局视角理解它的使用。

从它的使用方法上，我觉得后续有几个能力的内核实现方式需要重点关注

  • WriteBatch的具体实现
  • 并发读写的实现方式
  • 迭代器Iterator的实现
  • block_cache和block_size在内核中的表现
  • 布隆过滤器的NewBloomFilterPolicy实现，如何在sst文件的后面放filter meta block的。
  • 估计某个范围的key数量的实现GetApproximateSizes
  • 快照的实现GetSnapshot