RocksDB源码学习:深入BlockBasedTable(一)

BlockBasedTable是RocksDB中SST文件的默认格式，本文是源码学习BlockBasedTable的第一篇，主要围绕数据块（Data Block）层面，进行介绍。

一、 BlockBasedTable 整体认知

在深入研究 RocksDB 的核心存储单元之前，我们首先需要建立一个关于 BlockBasedTable (SST 文件格式) 的宏观视图。它是 RocksDB 默认的、用于在磁盘上持久化存储键值对的格式。

1.1 SST 文件磁盘布局概览

一个 BlockBasedTable 格式的 SST 文件在逻辑上由多个部分组成，一个典型的 SST 文件结构如下，特别是注意其读取入口位于文件的末尾：

<文件起始>
[数据块 1]
[数据块 2]
...
[数据块 N]

// --- 以下元数据块的顺序并非固定 ---

[Meta Block: Filter Block]
[Meta Block: Properties Block]
[Meta Block: Compression Dictionary Block]
[Meta Block: Range Deletion Block]
... (其他元数据块) ...

[Index Block] (数据块的总索引)

[Metaindex Block] (元数据块的索引)

[Footer] (固定大小的文件尾部，包含指向 Index 和 Metaindex 的指针)
<文件结束>

Data Blocks: 存储实际的、已排序的键值对数据。
Index Block: 数据块的索引，使得可以快速定位到包含特定 key 的数据块，而无需扫描整个文件。
Meta Blocks: 存储元数据，如布隆过滤器 (Filter)、表属性 (Properties) 等。
Metaindex Block: “元数据的索引”，用于定位所有的 Meta Block。
Footer: 文件的入口点，固定大小，存储了指向 Index Block 和 Metaindex Block 的指针。RocksDB 读取一个 SST 文件时，总是先从这里开始。

1.2 数据块 (Data Block)

在整个 SST 文件结构中，数据块 (Data Block) 是最基本的存储单元。所有用户的键值对数据最终都被组织在一个个数据块中。因此，理解数据块的内部格式、构建方式和读取逻辑，是掌握 BlockBasedTable关键第一步。

二、数据块的内部格式

数据块的设计目标是在保证快速查找的同时，尽可能地节省存储空间。为此，它采用了两种关键技术：前缀压缩 (Prefix Compression) 和 **重启点 (Restart Points)**。

2.1 键值对条目 (Entry) 的存储格式

块内的每一个键值对（Entry）都遵循以下格式进行编码，以实现前缀压缩：

// 源码: table/block_based/block_builder.cc 注释
shared_bytes:   varint32  // 与上一个 key 共享的前缀长度
unshared_bytes: varint32  // 当前 key 不共享的后缀长度
value_length:   varint32  // value 的长度
key_delta:      char[unshared_bytes] // key 的非共享后缀部分
value:          char[value_length]   // 完整的 value 数据

2.2 核心设计一：前缀压缩 (Prefix Compression)

由于数据块内的 key 是有序的，相邻的 key 常常拥有共同的前缀。前缀压缩技术正是利用了这一点，对于一个 key，我们不存储它的完整内容，而是存储它与上一个 key 的共享前缀长度 (shared_bytes)，以及它自己独有的后缀部分 (key_delta)。这样，在数据密集且前缀重复度高的场景下（如 URL、文件路径等），可以节省大量存储空间。

2.3 核心设计二：重启点 (Restart Points)

虽然前缀压缩节省了空间，但它也带来了一个问题：要解码任意一个 key，必须先解码它之前的所有 key，这是一个 O(N) 的操作。为了解决这个问题，引入了“重启点”机制。

一个重启点是一个不使用前缀压缩、完整存储 key 的条目。数据块中每隔 block_restart_interval 个条目（默认是16）就会设置一个重启点。这些重启点的存在，使得我们可以在块内进行二分查找，从而将查找复杂度降低到 O(logR + K)（R是重启点数量，K是重启点间隔），极大地提高了查找效率。

2.4 块尾 (Trailer) 的结构

在一个数据块所有条目存储完毕后，其尾部会附加一个 Trailer，包含两部分信息：

重启点偏移量数组: 一个由 uint32_t 组成的数组，按顺序列出了块内所有重启点相对于块起始位置的偏移量。
重启点总数: 一个 uint32_t 整数，表示重启点的数量。

这个 Trailer 结构为块内的高效查找提供了必要的元数据。

三、数据块的构建：`BlockBuilder` 的工作原理

BlockBuilder 类负责将有序的键值对序列打包成一个遵循上述格式的数据块。

3.1 `BlockBuilder` 的设计目标与初始化

BlockBuilder 的目标就是高效地完成数据块的构建。其构造函数接收几个关键参数：

// 源码: table/block_based/block_builder.h
explicit BlockBuilder(int block_restart_interval,
                      bool use_delta_encoding = true,
                      ...);

block_restart_interval: 定义了重启点的间隔。
use_delta_encoding: 控制是否启用前缀压缩。

3.2 `Add` 方法详解：如何添加一个键值对

Add 方法是 BlockBuilder 的核心。每当一个键值对被添加时，它会执行以下逻辑（主要在 AddWithLastKeyImpl 中实现）：

// 源码: table/block_based/block_builder.cc
inline void BlockBuilder::AddWithLastKeyImpl(...) {
  size_t shared = 0;
  // 1. 检查是否需要创建重启点
  if (counter_ >= block_restart_interval_) {
    restarts_.push_back(static_cast<uint32_t>(buffer_.size()));
    counter_ = 0;
  } else if (use_delta_encoding_) {
    // 2. 计算共享前缀
    shared = key_to_persist.difference_offset(last_key_persisted);
  }

  const size_t non_shared = key_to_persist.size() - shared;

  // 3. 写入元数据
  PutVarint32Varint32Varint32(&buffer_, static_cast<uint32_t>(shared),
                               static_cast<uint32_t>(non_shared),
                               static_cast<uint32_t>(value.size()));

  // 4. 写入数据
  buffer_.append(key_to_persist.data() + shared, non_shared);
  buffer_.append(value.data(), value.size());

  // 5. 更新状态
  counter_++;
  // last_key_ 会在 Add() 方法中被更新
}

3.2.1 前缀压缩与重启点的协同工作

Add 方法的核心逻辑完美地展示了前缀压缩和重启点是如何协同工作的。

重启点创建: 当内部计数器 counter_ 达到 block_restart_interval 时，当前条目就成为一个新的重启点。此时，共享前缀长度 shared 为 0，完整的 key 会被写入，并且其在缓冲区中的起始偏移量会被记录在 restarts_ 数组中。
前缀压缩: 当条目不是重启点时，代码通过 key_to_persist.difference_offset(last_key_persisted) 计算出与上一个 key 的共享前缀长度 shared。然后，只将非共享的后缀部分 (key_delta) 写入缓冲区，从而实现压缩。

3.2.2 一个具体的构建示例

为了更清晰地理解这个过程，我们假设 block_restart_interval = 3，并依次添加以下5个键（为简化，忽略值）：

key: "apple"
key: "apply"
key: "apricot"
key: "banana"
key: "bandana"

BlockBuilder 内部会发生以下过程：

Entry 1: 添加 “apple”

counter 为 0，满足重启点条件，这是一个重启点。
restarts 数组记录当前偏移量 0。
shared = 0, non_shared = 5。
写入 buffer: <varint(0)><varint(5)>... "apple" ...
last_key 更新为 "apple"，counter 变为 1。

Entry 2: 添加 “apply”

counter 为 1，不是重启点。
与 "apple" 比较，共享前缀为 "appl"。
shared = 4, non_shared = 1 (后缀为 “y”)。
写入 buffer: <varint(4)><varint(1)>... "y" ...
last_key 更新为 "apply"，counter 变为 2。

Entry 3: 添加 “apricot”

counter 为 2，不是重启点。
与 "apply" 比较，共享前缀为 "ap"。
shared = 2, non_shared = 5 (后缀为 “ricot”)。
写入 buffer: <varint(2)><varint(5)>... "ricot" ...
last_key 更新为 "apricot"，counter 变为 3。

Entry 4: 添加 “banana”

counter 为 3，满足重启点条件，这是一个新的重启点。
restarts 数组记录下当前条目的起始偏移量。
shared = 0, non_shared = 6。
写入 buffer: <varint(0)><varint(6)>... "banana" ...
last_key 更新为 "banana"，counter 重置为 1。

Entry 5: 添加 “bandana”

counter 为 1，不是重启点。
与 "banana" 比较，共享前缀为 "ban"。
shared = 3, non_shared = 4 (后缀为 “dana”)。
写入 buffer: <varint(3)><varint(4)>... "dana" ...
last_key 更新为 "bandana"，counter 变为 2。

这个例子清晰地展示了 BlockBuilder 如何在节省空间（通过前缀压缩）和保证查找效率（通过重启点）之间取得平衡。

3.3 `Finish` 方法：完成一个数据块的构建

当一个块的数据全部添加完毕，Finish 方法被调用以完成最终的打包工作。

// 源码: table/block_based/block_builder.cc
Slice BlockBuilder::Finish() {
  // 将重启点数组写入 buffer
  for (size_t i = 0; i < restarts_.size(); i++) {
    PutFixed32(&buffer_, restarts_[i]);
  }

  // 将重启点数量和其他信息打包成 footer 并写入
  uint32_t num_restarts = static_cast<uint32_t>(restarts_.size());
  uint32_t block_footer = PackIndexTypeAndNumRestarts(index_type, num_restarts);
  PutFixed32(&buffer_, block_footer);
  
  finished_ = true;
  return Slice(buffer_);
}

这个方法将之前记录的所有重启点偏移量和总数作为 Trailer 追加到数据缓冲区的末尾，形成一个完整、独立、可解析的数据块。

四、数据块的解析与迭代：`Block` 与 `DataBlockIter`

Block 和 DataBlockIter 类执行的是与 BlockBuilder 相反的操作：解析数据块并提供遍历能力。

4.1 `Block` 类的角色：块的容器

Block 类是一个轻量级的容器。它的构造函数接收一个数据块的原始二进制 Slice，但它只解析块尾的 Trailer，提取出重启点数组的位置和数量。它并不会立即解码所有的键值对，这是一种延迟加载（Lazy Loading）的思想，避免了不必要的计算开销。

// 源码: table/block_based/block.cc
Block::Block(BlockContents&& contents, ...) {
  auto& size = contents_.data.size_;
  if (size < sizeof(uint32_t)) {
    size = 0;  // Error marker
  } else {
    // 从块的末尾读取重启点的数量
    num_restarts_ = NumRestarts(); 
    // ... 根据块的索引类型计算重启点数组的起始偏移量
    restart_offset_ = static_cast<uint32_t>(size) -
                      (1 + num_restarts_) * sizeof(uint32_t);
    // ... 其他初始化
  }
}

Block 类的主要职责是作为工厂，通过 NewDataIterator() 方法创建一个 DataBlockIter 实例，并将解析好的重启点等信息传递给它。

4.2 `DataBlockIter`：数据块的遍历者

DataBlockIter 是实现块内数据访问的核心。它是一个有状态的迭代器，在内部维护了遍历所需的所有上下文信息。

4.2.1 核心状态变量

DataBlockIter (及其基类 BlockIter) 内部维护着以下关键状态：

data_: 指向整个数据块内存的指针。
restarts_: 指向重启点数组在 data_ 中的偏移量。
num_restarts_: 重启点总数。
current_: 当前正在处理的条目在 data_ 中的偏移量。
restart_index_: 当前条目所属的重启点区间的索引。
raw_key_: 一个可复用的内部缓冲区（IterKey 类型），用于存放当前完整解码后的 key。
value_: 一个 Slice，直接指向 data_ 中当前条目的 value 部分。

4.2.2 顺序遍历 (`Next`) 与增量解压

当调用迭代器的 Next() 方法时，其核心是 ParseNextKey() 函数。该函数负责从当前位置解码下一个条目，并重建出完整的 key。

// 源码: table/block_based/block.cc (BlockIter::ParseNextKey)
// ...
// 解码元数据: shared, non_shared, value_length
uint32_t shared, non_shared, value_length;
p = DecodeEntryFunc()(p, limit, &shared, &non_shared, &value_length);

if (shared == 0) {
    // 重启点，key 是完整的。raw_key_ 直接指向这块内存。
    UpdateRawKeyAndMaybePadMinTimestamp(Slice(p, non_shared));
} else {
    // 增量编码的 key。
    // raw_key_ 需要保留前 shared 个字节，并追加新的 non_shared 部分。
    raw_key_.TrimAppend(shared, p, non_shared);
}
// value_ 指向 value 的内存区域
value_ = Slice(p + non_shared, value_length);
// ...

这个过程精确地反映了 BlockBuilder 的编码逻辑：通过 shared 和 non_shared 的信息，迭代器可以高效地从上一个 key 的状态（保存在 raw_key_ 中）和当前条目的增量数据中重建出完整的 key。

4.2.3 随机查找 (`Seek`) 与重启点的应用

Seek(target_key) 操作充分展现了重启点的威力。它分为两步：

二分查找重启点: 首先，在块尾部的重启点偏移量数组上进行二分查找 (BinarySeek)，快速找到不大于 target_key 的最后一个重启点。这一定位过程非常快，复杂度为 O(logR)。
```
// 源码: table/block_based/block.cc, DataBlockIter::SeekImpl
bool ok = BinarySeek<DecodeKey>(seek_key, &index, &skip_linear_scan);
```
小范围线性扫描: 定位到重启点后，迭代器跳转到该重启点的内存位置，然后开始逐个解码条目并比较，直到找到第一个大于或等于 target_key 的条目。由于重启点间隔不长（默认为16），这个线性扫描的范围很小，开销也很低。
```
// 源码: table/block_based/block.cc, DataBlockIter::SeekImpl
FindKeyAfterBinarySeek(seek_key, index, skip_linear_scan);
```

这个“二分查找 + 小范围线性扫描”的策略，使得在数据块内部的随机查找性能远高于纯粹的线性扫描。

4.3 关键实现细节：`raw_key_` 的状态管理

在迭代过程中，迭代器内部的 raw_key_ 成员变量（一个可复用的缓冲区）如何被维护，是一个体现性能优化的关键细节。

4.3.1 指针引用 vs. 内存拷贝

raw_key_ 的更新方式有两种，取决于当前解码的条目类型：

情况	对应方法	内存操作	原因
重启点的 Key	`SetKey(..., copy=false)`	指针引用	完整的 key 在原始数据块中是连续的，直接指向它可以避免不必要的内存拷贝，效率更高。
增量编码的 Key	`TrimAppend(...)`	构建/拷贝	完整的 key 在原始数据块中不是连续存放的，必须在迭代器自己的缓冲区中通过“截断+追加”的方式重新构建出来。

这种双模操作的设计，体现了在可能的情况下（重启点）尽量避免内存拷贝，在必要的情况下（增量编码）高效复用缓冲区的优化思想。

五、总结与展望

通过本次学习，我们深入了解了 RocksDB 中最基本的数据单元——数据块（Data Block）的设计与实现。其核心在于前缀压缩和重启点机制。

构建 (BlockBuilder): 将有序的键值对通过增量编码和重启点策略，打包成紧凑的二进制块。
解析 (Block & DataBlockIter): 通过解析块尾的重启点数组，实现了块内高效的“二分查找+线性扫描”式查找，并通过状态化的迭代器缓冲区 raw_key_ 高效地完成前缀解压。

理解了单个数据块的运作原理后，我们下次学习将进入更高的层次，去探索 BlockBasedTable 是如何将这些数据块、索引块、过滤器块等组织成一个完整的 SST 文件，并提供高效的读写服务的。

KV数据库

KV数据库 RocksDB

转载请注明出处

RocksDB源码学习:深入BlockBasedTable(二) 上一篇

RocksDB中Cuckoo Table技术内幕解析下一篇

RocksDB源码学习:深入BlockBasedTable(一)

一、 BlockBasedTable 整体认知

1.1 SST 文件磁盘布局概览

1.2 数据块 (Data Block)

二、 数据块的内部格式

2.1 键值对条目 (Entry) 的存储格式

2.2 核心设计一：前缀压缩 (Prefix Compression)

2.3 核心设计二：重启点 (Restart Points)

2.4 块尾 (Trailer) 的结构

三、 数据块的构建：BlockBuilder 的工作原理

3.1 BlockBuilder 的设计目标与初始化

3.2 Add 方法详解：如何添加一个键值对

3.2.1 前缀压缩与重启点的协同工作

3.2.2 一个具体的构建示例

3.3 Finish 方法：完成一个数据块的构建

四、 数据块的解析与迭代：Block 与 DataBlockIter

4.1 Block 类的角色：块的容器

4.2 DataBlockIter：数据块的遍历者