一 | Leveldb 如何工作 #

本文意在提取 leveldb 实现的启发性知识，不会详细介绍 LSM-Tree

结构上：

• Memtable、Immtable 采用 SkipList 实现
• Level 0 SST 来源于 Immtable，彼此间可能有重叠
• Level 1+ SST 由压缩得到，彼此间不重叠，有序

Write：

• 接受 WriteBatch 作为写入内容
• 先写入 WAL，再写入 Memtable
• 如果 Memtable 已满，就安排一次 Compaction，压入 Immtable

[!question] 为什么用 Write 等效替代 Delete？

Delete 需要查找 key，并进行删除，不符合我们追加写入的原则

Read：

• 记录当前 Version，过滤新写入的数据
• 依次读 Memtable、Immtable、SStable

Version：

• 维护当前版本的 SSTable File 集合
• 记录每个 table 的 Key-Range，用于快速过滤

[!note] 记录一个 WriteBatch 的优化

Leveldb 对单个线程采用 WriteBatch 实现原子写入，但也对多线程同时写入的情况进行了批处理

我们将每个 WriteBatch 绑定一个 Writer，加入等待队列，每次 Write 取出队首的一系列 Writer，将其合并为一个巨大的 WriteBatch，一并写入

二 | 数据在磁盘上是怎么存储的 #

LSM 存储的 kv-data 是变长的，无法直接获取 offset，只能间接访问

并且由于是 append 写入，在接受完 data 之前，我们不能确定统计信息

因此磁盘上的文件内，就设计为三部分：

• Data，存放数据块
• Index，存放数据块索引，单个索引是定长的
• Footer，固定长度，存放元信息

读取时，我们就从 Footer 中读出 block_count，并由此反推 Index Block 的 offset，再二分查找对应的 Index，最后找到对应的 Data Block

可以看到 SSTable、Block 都遵循这样的设计

[!question] Block 中的 Restart points，为什么是稀疏的？

这取决于 Data 的长度，如果 data 过短，那么密集索引显然浪费大量空间，因此在 Block 中，我们对 Data 进行分组，每组记录一个 restart point 索引即可

另外，在 Leveldb 中，SSTable 是通过 immtable 跳表持久化得来，这个过程是用 迭代器 获取 key，因此内部 key 天然有序，Block 内部就采用前缀压缩，相邻的两个 key 会记录共同前缀长度 shared_length 与 unshared_key

而 restart point 其实是 key 到 offset 的映射，如果都采用前缀压缩，完整的 key 就被破坏了，因此在 restart point 对应的位置，一定会记录一个完整的 key，相当于在这里重启了前缀压缩

而 Log 存储的 WriteBatch、Manifest 存储的 VersionEdit，只需要顺序读，就不需要再编码 index 块

[!note]

编码字节流的 Builder、解析字节流的 Parser，其实都可以看作是一种 DFA，用 do-while 循环实现更简单

另外，SSTable 中增加的 Filter Block，即布隆过滤器，也可以如法炮制，在 Footer 中记录 Fliter-offset，定位到对应的 Filter 块

一个 Block 内部有多个 Filter 存在，每个 filter 是按照 DataBlock 的 offset 索引的，每个 filter 负责维护一段定长 offset 的 DataBlock 中的 key

这样一来，上层使用 fliter 时，只需要根据 offset 的高位就可以定位到具体 fliter，而不需要设计额外的 IndexBlock

一句话讲清区别，DataBlock 存储的是 (key, value)，而 FliterBlock 存的是 (offset, fliter)，因此可以快速索引，只不过二者都借用了 Block 这个基本单元

[!tip]

最后讲一个 IndexBlock 的小优化

在构建 SSTable 时，随着读入 Data Block，我们会记录对应的 key 与 offset，然而 leveldb 会多等一拍，先读入下一个 key，找到能区分它们的最短 key，再写入 index

Index key 只需要划分范围，而不需要准确定位，这样就压缩了空间

三 | 为什么 Block 对象要申请堆，而不是栈 #

[!info]

这个问题是我在读 table.cc 的实现时遇到的

要从 SSTable 中读出 Data Block，leveldb 选择用 Block* block = new Block()，我很疑惑，明明是临时使用的对象，为什么特意要 new 一块空间呢

我们先分析下 Block 对象的作用

可以这么认为，从磁盘中读出的 Data，解码到内存中的 Block，需要动态申请空间

我们调用 Flie 接口读取 BlockContent，再将 Content 中的 data 指针解码到 Block

在解析 Block 内容时，我们持有以下对象：

• File 接口返回的 data_ 指针
• BlockContent，持有 data_ 和 is_alloc 标记
• Block 对象，持有管理 block 所需的元数据，和 data_
• BlockIterator，持有 data_ 和迭代器内部状态

[!note]

我一直很难理清楚各个类的功能边界，一会解析字节，一会又遍历迭代器，读起来很混乱，原因就是没有分清 “数据” 与 “计算” 发生的位置

想到这个问题后，就捋了一遍 BlockData 存放在哪里，何时被 OS 加载到内存，又何时被解析到内存对象 Block 中，如何被 Iterator 管理，思路就清晰了

现在我们知道，Block 对象本身，只是对 Data 进行管理，并不拷贝 Data 本身，因此不必担心占用过多的内存，用 堆 管理是可行的

现在回答"为什么"，因为 Block 需要存储在 BlockCache 里

数据是可以共享的，可能会有多个线程反复读写同一块 Block，这样就产生了缓存的需求，其实是一个很好理解的想法

为什么我没有产生这样的直觉呢？其实还是没能将 “数据” 和 “过程” 作为两个独立的部分看待，将二者强行绑定到一起了，但前者的生命周期显然可以更长

[!tip]

这里讲一个实现的细节，Block 的来源有两种：Cache 与 File，显然对两种 Block，它们的析构方式是不同的，前者只需要减少 cache 里的 ref 次数即可，这一点怎么实现呢？

Block 的生命周期其实是与 BlockIterator 绑定的，因此 Iterator 在析构时会尝试释放 Block 资源

leveldb 则是为 Iterator 设计了一个 CleanupNode 成员，专门用于清理迭代器引用的资源，只需注册底层写好的清理函数即可，这里应用了回调函数

对应到 Block，就是根据来源，分别注册两个不同的函数 DeleteBlock 与 ReleaseBlock ，对应两种不同的清理逻辑

不过这种手动管理内存的写法，我觉得已经过时了，在现代可以用 RAII 对象和智能指针管理

四 | Env 提供的 Read 接口，有什么隐患 #

我注意到 Block 对象中，有一个 is_alloc 标记，控制析构时是否调用 delete data_，为什么呢？难道 Block 引用的 data_ 指针，还能不在内存中吗？我们回到最初 ReadBlock 的地方

  char* buf = new char[n + kBlockTrailerSize];
  Slice contents;
  Status s = file->Read(handle.offset(), n + kBlockTrailerSize, &contents, buf);

调用 File->Read(buf) 接口时，我们是先 new 了一块空间 buf 承担 data，希望 File 能将内容写到 buf 里

但是这取决于 File 的内部实现，如果当前数据就存在于内存中（cache 或 mmap），底层实现就会忽略 buf，直接返回内存中已有的指针，我们自己 delete buf

注意到什么？我们 Data 内存的来源出现分歧了！

一种是自己 new 的 buf 指针，另一种是 File 返回的现有指针

那么在释放 Block->data_ 时就需要分类讨论：

• 如果是 buf，就需要 delete
• 如果是 File 提供的，就不需要 delete

这本质是资源归属权的问题，所以在读出 BlockContent 时，我们会判断 buf 是否被占用，从而设置 is_alloc 标记，提醒 Block 是否应该 delete

五 | 复合 Iterator 是如何实现的 #

每个结构都有其对应的 Iterator

• memtable：MemtableIterator，由 SkipList 提供
• block：BlockIterator，由 restart point 提供 Seek，而 Next 通过 parse 字节实现
• sstable：TwoLevelIterator，由 IndexBlock 提供 Seek

先前的 Iterator 管理的都是小粒度结构，如 memtable、block

而对于 Table 这种，迭代器内部还要引用下层 iter 的结构，就需要对 iter 进行管理

由此，leveldb 提供一个 Iterator_wrapper 对象，负责包装底层 iter，并实现一个 Set 接口，支持变更内部 iter

我认为 wrapper 起到容器的作用，而 Set 负责管理所有权

由于 leveldb 使用 C++98，没有 move 右值语义，所以只能采用这种朴素实现

另外，TwoLevelIter 又需要动态读取 block 内容，以修改内部的 blockIter

如果把 ReadBlock 写到 TwoLevel 内部，又会破坏封装

为了保持模块间的独立性，这里 TwoLevel 将 ReadBlock 作为回调函数，将其放入成员变量，由此进行动态调用

而 MergeIterator 的实现也很简单

用 Iterator[] 存储若干个需要 merge 的迭代器

使用 *current 指代当前对应的 key-value 迭代器

在 n 个 child 里，选取 current 的过程，被封装为 FindSmallest 或 FindLargest 函数，每次只需要在最后调用这个函数，更新 current 即可

而对于 Next / Prev 的处理，调用 child 内部的 Seek 来维护大小关系即可，随后只推动 current 的位置

这样 MergingIterator 就可以利用 IteratorWrapper 抽象，将 memtable、block、table 这些对象组织起来，共用一个合并逻辑

[!note]

以上是我读源码时随手做的笔记，直接搬过来了，这边总结一下

MergeIterator 是压缩逻辑的事实执行者，用归并排序实现，将底层的各种 Iterator 综合起来，就可以提供上层可用的 DBIter

而 TwoLevelIterator，还是逃不出之前讨论的 Index+Data 范式，只不过是用 Iterator 的形式读出 Data

而 Iterator 本身的设置就取决于底层对象，因此也是用回调函数 GetXXXIterator 进行解耦

补充一个笔记没提到的 LevelFileNumIterator，用于遍历各级 Level 内部的 FileMeta 信息，以此读出 SSTable，显然这个 Iterator 就是用作 SSTable 的 TwoLevel 索引

六 | 为什么我分不清 Block 和 Page #

这是个稍微有点呆的问题，我的表述会有不严谨的地方

读到分块相关的处理时，比如写入 Log Record、构建 Block Builder，我注意到一个 Block 的大小可以超出预设的 option_block_size，而不是严格小于

我就很疑惑，为什么可以超出上限呢，那样读出时不会增加 IO 次数吗

分析后我明白了，leveldb 中的 Block 分块是逻辑上的

Block 的引入是为了从逻辑上分割 Data，便于 Index 查找 与 Cache 加速
这其实是一个逻辑上的 Block，是一个软件概念

问出这个问题，我是把 Block 与 OS 中的 Page 搞混了

为了适应磁盘 IO 的粒度，我们需要对 Page 内部进行结构设计，大小固定

page 是一个磁盘上的 Page，是一个硬件概念，与 Block 有本质区别

而对 Block 进行设计，其实是为了保持各个块之间的独立性，防止损坏

七 | 如何提供只读快照 #

首先明确 snapshot 的应用场景：

多进程情况下，一个用户在进行读操作，不希望自己在读的视图，收到其他线程的写入影响，这时我们保存当前的 seqNumber，获取 snapshot Version，在这个 Version 上进行读写

在 block 层，我们可以将[key, seq] 作为真正的 key，以此过滤 snapshot 可见的 key

而 Version 的粒度，其实是记录 SSTable file ，每次 Compact 都会增删 SSTable，我们将这种变更记录为 VersionEdit，以此创建一个新的 Version 加入 VersionSet

而 Manifest 就记录着每次 Compact 产生的 VersionEdit，以此追踪那些应该保留的 SSTable，那些不被 current_version 引用的 SSTable 就可以删除了

八 | 拆解 Compaction 流程 #

调用链：

1. MaybeScheduleCompaction：检测状态，与 OS 调度器交互
2. BGWork：回调函数，包装 BackgroundCall
3. BackgroundCall：再次检测状态（此时已经是另一个线程）
4. BackgroundCompaction：根据选取 Compact 文件
5. DoCompactionWork：用 MergeIterator 完成合并，生成新文件
6. InstallCompactionResults：将变更写入到 VersionSet

Compact 的关注点更侧重于 “策略” 而非 “机制”，也就是 PickCompact 的决策逻辑，这一部分 leveldb 选择统计 size 与 seek 次数，将每个维度换算成统一的 score，以此划分压缩优先级

选定需要压缩的 sstable 后，再根据 Version 存储的 key range，寻找与其重叠的其他 sstable，一起合并到下层，version_set.cc 中相当一部分函数都是在处理 range 覆盖这样琐碎的问题

[!note]

记录一个我注意到的事实，leveldb 单独定义了一个 Compact 类，用于维护压缩过程中涉及到的各种信息、文件

把 “计算过程” 包装成一个类，最后合并到 VersionSet 中（即 Install），这个设计本身就天然支持并发，有点 RCU 的意思

九 | Leveldb 不足的地方 #

语法上，仍然采用手动 new/delete 管理内存，可以使用智能指针重写

IteratorWrapper::Set() 实现的所有权管理，也可以用更现代的移动语义 std::move 重写

  // Takes ownership of "iter" and will delete it when destroyed, or
  // when Set() is invoked again.
  void Set(Iterator* iter) {
    delete iter_;
    iter_ = iter;
    if (iter_ == nullptr) {
      valid_ = false;
    } else {
      Update();
    }
  }

另外，函数实现中，还存在大量用于 接收返回值 的 指针参数，这一点可以用 Expect<> 或 Result<> 包装返回值 + move 重写

性能上，Leveldb 只有一个 imm_ 空位，压缩也是单线程的，限制了吞吐量，此外在 compact 调度与策略、filter 设计等方面也不够丰富，并且缺乏针对新硬件的优化、事务支持

给 leveldb 增加线程池应该是一个可观的提升

十 | 杂项 #

[!info]

util/ 实现的工具类，这里直接贴笔记，我没有做额外的讨论

SkipList 是什么？ #

SkipList 是一种有序链表结构，查找、修改复杂度为 $O(\log n)$

它的思想是这样的：

既然单层有序链表的查改复杂度为 ，瓶颈是只能一步步访问

那么我利用其有序性，跳过某些节点进行查找，判断是否“跳过了”，就可以降低复杂度

常规的多层链表确实是这样，按照二分法，每次都取出一半的节点，建立高层的稀疏链表，由此建立多层

查找是很快了，但一旦插入节点，底层建立的二分数量关系，就会被破坏，只要构造特定的数据就能退化成 

而 SkipList 吸取了教训：我们不再按个数比例提升层数了，而是按概率 p

这样内部结构就与插入顺序无关了，完全依赖于概率，可以证明期望复杂度为 

SkipList 描述如下：

• 分为多层链表
• 最底层存储全部的 key
• 对于一个节点，它记录上下左右四个方向的指针
• 插入第  层节点时，每次有 p 的概率会插入到  层
• 查找时，自顶向下查找
• 链表有序，所以高层找到 key 对应的区间后，会向下层移动，直到到达最底层，或找到目标 key
• 增加或删除时，需要维护该节点在所有层的副本

使用模板编程时，有时需要用 typename 关键字，告诉编译器后面是类型名

Leveldb 对 skipList 的实现很简单，用模板 <KeyType, Comparator> 编程，内部定义模板结构体 Node 作为基本单位

而 Node 只存储 Key 和 Next 指针

Prev 指针在向下查找的过程中动态维护

值得注意的是，这里只实现了逻辑上的多层链表，并没有复制很多 Node 副本

只需要对 Next 指针做分层即可，所以 Node 实际存储的应该是 <level, next> pair

[!question]

为什么选用 SkipList 作为底层数据结构

一方面是 SkipList 天然支持 迭代器 与 追加写入，另一方面，插入一个 key 的过程是原子性的，我们只需要保证调整 next 指针时不被干扰就可以，因此底层实现是 lock-free 的

Leveldb 用 Arena 分配堆内存，它做了什么？ #

相比直接调用 New / Delete，Arena 对小块的处理更优秀

Arena 的想法是这样：

每次调用 New 都需要成本，如果频繁的对小块进行申请，那么会产生大量内存碎片

既然如此，我们就集中申请，每次申请一个固定大小的 4KB block

当小请求到来时，我们就可以直接利用 block 的剩余空间，并调整 offset 变量

而大请求到来时，我们就申请对应的大块，因为已经足够大，此时用 New 就是划算的

另外 Arena 还提供对齐的 Alloc，多申请没对齐的位数即可

可以用 sizeof(void*) 来判断对齐位数

注意 Arena 是 RAII 对象，析构时会调用 delete 释放所有资源

十一 | 阅读经验 #

读 leveldb 的体验还是比较流畅的，很享受这种知识流进大脑的感觉，这里记录一下读源码的方法论

第一，不要直接扎进项目里，需要先调研整体架构，读 doc 文档，了解提供了哪些特性、应用场景是什么，再做下一步规划

第二，不要抓起一个文件硬读，缺乏有关的 context 是不可能读懂的，我的选择是 ”主题阅读“，先确定好 “我要读整个 Write 的调用链”，或者 ”我想先读完底层基本对象的实现“，一旦有这样一个主题指引，就不容易被无关的函数缠住

第三，不要通读每一行代码，如果你知道它在做什么，就不必知道 How，一些重复性的、机械性的代码，读了也只是在浪费专注力

第四，必要时停顿，理解源码是一个螺旋上升的过程，阅读过程中极有可能推翻之前的结论，从这种自我辩论中更容易提取到有价值的信息，LLM 大大减少了这种停顿的成本，你要做的只是发现问题，提出问题，判断 LLM 的回复是否有价值

第五，随手做笔记，读完真的会忘干净，如果你能把前面四点的过程都记录下来，一方面是减少切换 context 的成本，另一方面也有助于复盘。注意这里不是说你要照搬源码，而是用自己的理解重新表述一遍，写作本身就是最好的思考，如果能从时间上记录下完整的思维流，也是很酷的事情