LevelDB-源码｜Block的读取与迭代

LevelDB-源码｜Block的读取与迭代

table/block.h/.cc

简述

它主要负责解析迭代从磁盘读取到的block数据

  • BlockBuilder（block_builder.h/.cc）：负责写，把一个个 KV 攒成符合格式的二进制 Block 内存数据块。Block的构建过程
    Block / Block::Iter（block.h/.cc）：负责读，把磁盘读出来的（或者内存里已有的）二进制 Block 数据进行结构化解析，并提供 Seek / Next 等迭代接口。

它是典型的“磁盘字节流 → 内存数据结构 → 高效查询接口”的解析层。

上层业务（比如 LSM-Tree 的读逻辑）不想关心底层复杂的变长编码、前缀压缩和字节偏移；而磁盘存的又必须是极致压缩的字节流。Block 模块正好站在中间，把底层的“无序字节”翻译成了上层极易使用的“高效查询接口”。

class Block

该类比较简单，只是描述一个block。

成员变量：

1
2
3
4
5
6
class Iter;

const char* data_;  // 指向 block 的指针
size_t size_;       // 整个 block 的 size
uint32_t restart_offset_;  // 一个 block 中重启点开始记录的位置
bool owned_;               // 如果block拥有内存，析构时负责释放内存

class Block::Iter

主要来研究一下它的迭代器类的相关函数，

成员变量：

1
2
3
4
5
6
7
8
9
10
11
const Comparator* const comparator_;
const char* const data_;       // block 数据
uint32_t const restarts_;      // 重启点的位置
uint32_t const num_restarts_;  // 重启点的数量

// 当前 entry 在 block 数据中的偏移。 如果 >= restarts_ 则是不合法的。
uint32_t current_;
uint32_t restart_index_;  // 当前迭代位置是第几个restart区间
std::string key_;         // 记录解析出的 key 用于解析下一条 key
Slice value_;
Status status_;

DecodeEntry

一个辅助函数，用于解码一条entry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 解码从p开始的下一条 entry，访问内存不会超过limit，并获取解码后拿到的前三个字段的值
// 返回指向 key_delta 的指针。
static inline const char* DecodeEntry(const char* p, const char* limit,
                                      uint32_t* shared, uint32_t* non_shared,
                                      uint32_t* value_length) {
  if (limit - p < 3) return nullptr;
  *shared = reinterpret_cast<const uint8_t*>(p)[0];
  *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
  *value_length = reinterpret_cast<const uint8_t*>(p)[2];
  if ((*shared | *non_shared | *value_length) < 128) {
    // Fast path: all three values are encoded in one byte each
    p += 3;
  } else {
    if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
    if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
    if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
  }

  if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
    return nullptr;
  }
  return p;
}

这里最值得说的地方就是 fast path，

1
2
3
4
5
6
7
*shared = reinterpret_cast<const uint8_t*>(p)[0];
  *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
  *value_length = reinterpret_cast<const uint8_t*>(p)[2];
  if ((*shared | *non_shared | *value_length) < 128) {
    // Fast path: all three values are encoded in one byte each
    p += 3;
    ....

由于Varint对<128的整数只需要一个字节，所以if ((a | b | c) < 128) 可以快速判断a < 128 && b < 128 && c < 128
就不用调用完整的Varint解码函数，p += 3即可，这就是 fast path 优化。

SeekToRestartPoint

把迭代器直接重置并定位到指定的index重启点位置，并将其作为当前记录解析的起始状态

1
2
3
4
5
6
7
8
9
10
11
void SeekToRestartPoint(uint32_t index) {
    key_.clear();
    // 更新重启点状态
    restart_index_ = index;
    // current_ will be fixed by ParseNextKey();

    // ParseNextKey() starts at the end of value_, so set value_ accordingly
    uint32_t offset = GetRestartPoint(index);
    // 伪造一个空 value，把它的末尾强行设置到目标 restart entry 开头
    value_ = Slice(data_ + offset, 0);
  }

在以下场景会被调用：

Seek(target)（二分查找）：
当用户要在 Block 内查找某个 Key 时，会先对重启点数组做二分查找。
找到小于等于 target 的最佳重启点后，就会调用 SeekToRestartPoint 一脚跨到该重启点，
随后再从这个点开始向后逐条做线性遍历。

SeekToFirst()（跳到开头）：
直接调用 SeekToRestartPoint(0)，定位到第 0 个重启点（即 Block 的第一条 KV）。

Prev()（反向遍历）：
由于前缀压缩无法直接倒退解析，当需要向前推移时，Block::Iter 通常会先调用 SeekToRestartPoint 回退到上一个重启点，然后再向后线性解析推演到目标位置。

ParseNextKey

Block 内除了重启点（Restart Point）位置存储的是完整 Key 之外，大部分 Key 都采用了增量前缀压缩（只存储与上一个 Key 不同的部分）。

例如：
上一个 Key：apple
当前的 Key：application
当前记录只存：共享长度 4 (appl)，非共享长度 7 (ication)，以及后缀 ication。

迭代器在顺序向后移动（如执行 Next() 或在区间内线性扫描）时，必须依靠一个专门的解码函数，
把这串压缩的字节还原成完整的 application，这个重任就落在 ParseNextKey 身上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 解析下一条 entry 的 key_ & value，同时更新restart_index_
  bool ParseNextKey() {
    current_ = NextEntryOffset();
    const char* p = data_ + current_;
    const char* limit = data_ + restarts_;  // Restarts come right after data
    if (p >= limit) {
      // No more entries to return.  Mark as invalid.
      current_ = restarts_;
      restart_index_ = num_restarts_;
      return false;
    }

    // Decode next entry
    uint32_t shared, non_shared, value_length;
    p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
    if (p == nullptr || key_.size() < shared) {
      CorruptionError();
      return false;
    } else {
      // 复原 key 和 value  
      key_.resize(shared);
      key_.append(p, non_shared);
      value_ = Slice(p + non_shared, value_length);
      // 更新解析的区间
      // 检查当前指针是否跨越到了下一个重启点区间，如果是，递增内部的 restart_index_。
      while (restart_index_ + 1 < num_restarts_ &&
             GetRestartPoint(restart_index_ + 1) < current_) {
        ++restart_index_;
      }
      return true;
    }
  }

在以下场景下会被调用：

Next()（顺序遍历）：
当用户调用 iter->Next() 获取下一条数据时，底层直接调用 ParseNextKey 顺序解析下一条 KV。

Seek(target) 中的“线性扫描阶段”：
在利用 SeekToRestartPoint 跳到目标重启点后，迭代器会在该区间内循环调用 ParseNextKey，逐条对比 Key，直到找到首个 >= target 的记录。

Prev()（反向遍历的推演阶段）：
当需要向前倒退时，迭代器先退到上一个重启点，随后也是通过反复调用 ParseNextKey 向后推演，重新定位到上条记录的位置。

Seek

Seek(target)：
找到第一条 key >= target 的 Entry。

类似于：std::lower_bound()
假设 Block 中：

1
2
3
4
5
6
7
apple
banana
cat
dog
mango
orange
zebra

执行： Seek(“mouse”); 最后会定位到： orange
如果完全从 Block 开头顺序查找，效率比较低。 所以 LevelDB 利用了 restart point。
首先在 restart points 对应的完整 key 中进行二分查找：

1
2
3
4
restart[0] -> apple
restart[1] -> dog
restart[2] -> mango
restart[3] -> zebra

对于： mouse 可以确定： mango <= mouse < zebra
于是：
跳到 mango 对应 restart point -> 顺序解析后面的 Entry -> 找到第一条 key >= mouse
所以 Block 查询本质上是：
restart array 二分查找 + restart 区间内部线性扫描

总结

前缀压缩、Restart Point、Iterator

一、 核心设计目标与定位

  1. 统一解析器：作为 Data Block（数据块）和 Index Block（索引块）的通用内存解析器，屏蔽底层复杂的编码与布局细节。
  2. 极高空间利用率：利用前缀压缩减少重复 Key 带来的空间占用。
  3. 高效检索能力：引入重启点，避免前缀压缩导致的线性扫描性能瓶颈，实现 O(logN) 级别的二分定位。

二、 内存物理布局设计

Block 接收的是一段连续的字节流（Slice），其物理结构划分为两大部分：

1
2
3
4
5
+-----------------------------------------------------------------------+
| entry 1 | entry 2 | ... | entry N      |  Restarts Array  | Num_restart  |
| (Varint32 + Key Offset/Suffix + Value) |  [off1, off2...] |    Rest.     |
+-----------------------------------------------------------------------+
|<----------------- 数据区 -------------------->|<----- 重启点索引区 --->|
  • 数据区：
    • 每个 Entry 包含 3 个变长整数（shared、non_shared、value_length）以及非共享的 key_delta 和 value。
    • 重启点位置的记录 shared = 0，存储完整的 Key。
  • 重启点索引区：
    • 末尾 4 字节记录重启点的总个数 num_restarts_。
    • 紧邻其左侧的是固定长度（4 字节/项）的 restarts_ 数组，记录各个重启点在数据区内的字节偏移量。

三、 核心实现机制：Block::Iter 迭代器

Block 本身非常轻量，它把解析和查询的所有动态状态交给了内部的 Block::Iter。

  1. 核心状态与解码（按需延迟解压）
  • 不一次性展开数据：为了节省内存，Block::Iter 仅在游标推移时动态解码。
  • ParseNextKey()：负责顺序读取 Varint32，根据前一条 Key 的缓存 key_ 与当前记录的 non_shared 增量拼接出完整 Key，并推移游标。
  1. “二分 + 线性”混合查找（Seek）

为了在压缩编码下兼顾查询效率，Seek(target) 采取两步走策略：

  • 重启点二分（跳跃）：对 restarts_ 数组进行二分查找，迅速定位到最后一个满足 Key < target 的重启点，并调用 SeekToRestartPoint(index) 一脚跨过去。
  • 区间内线性扫描（小步走）：从该重启点开始，循环调用 ParseNextKey() 向后逐条比对，直到找到第一个 >= target 的记录。
  1. 不对称的遍历设计（Next vs Prev）
  • Next()：直接调用 ParseNextKey() 顺序向后解压，速度极快。
  • Prev()：由于前缀压缩无法反向直接解码，Prev() 采用了“先退回到上一个重启点，再向后线性扫描至上一条记录”的补偿策略，牺牲小部分反向遍历性能换取极高的空间压缩率。

四、 设计亮点与总结

  • 空间与时间的平衡：通过重启点（每 16 个 entry 默认重置一次 key），既享受了前缀压缩省内存的红利，又解决了长链表线性查找慢的问题。
  • 无拷贝与高效指针移动：大量使用 Slice 引用和原位指针偏移（const char* p），极大减少了解析过程中的内存分配与拷贝开销。
存储系统
#源码分析
LevelDB-源码｜Block的读取与迭代
http://example.com/2026/09/25/LevelDB-源码｜Block的读取与迭代/
作者
lorixyu
发布于
2026年9月25日
许可协议