Ch05-LevelDB 之 SSTable
May 16, 2022
SSTable
SSTable 不是一个内存数据结构，其保存的是 MemTable（SkipList）第 i 层的数据，在 Minor Compaction 触发的时候，由 TableBuilder 将其构建成不同的 Block，最后保存到ldb文件中。在 doc/table_format.md 中可以看到部分格式说明。
1. 基本结构 #
注意：上图中 Meta Block 等于下文中的 Filter Block
SSTable 由若干个 Block 组成，而 Block 则由若干个 Entry 组成，Entry 则是对 KV 的编码形成的一串字符串，如上图所示。
| Block 分类 | 说明 |
|---|---|
| Data Block | 由 BlockBuilder 完成构建，用于保存实际的 KV 数据。 |
| Filter Block | 由 FilterBlockBuilder 完成构建，存储了对应的 DataBlock 的 Bloom Filter。 |
| MetaIndex Block | 由 BlockBuilder 完成构建，保存了指向 Filter Block 的指针，可以简单的认为 <BloomFilter(Name), (Filter)BlockHandler>（目前也只有这一个）。 |
| Index Block | 由 BlockBuilder 完成构建，用于指向对应的 Data Block，可以简单的认为 <restart point, (Data)BlockHandler>。 |
2. 生成流程 #
class BlockBuilder {
public:
void Add(const Slice& key, const Slice& value); // 将 MemTable 中的所有数据存入到 buffer 中
Slice Finish(); // 将 buffer 中的字符转成 Slice
private:
std::string buffer_;
}
class BlockHandle {
private:
uint64_t offset_;
uint64_t size_;
}
BlockBuilder 和 BlockHandle 关系是 BlockBuilder::Finish() 产生 content，BlockHandler 保存该 content 保存到 ldb 文件中的 offset 和 content 大小。举个例子，比如 data_block->Finish() 生成了 data_block 这一 block 的所有字符，将其写入到 ldb 文件前，在将 offset 和 content.size() 记录到 data_block_handle 中。而对于其他的 block（比如 filter_block, meta_index_block, index_block）也是同理。
// table/table_builder.cc
Status TableBuilder::Finish() {
// 1. data_block
Flush(); // WriteBlock(&r->data_block, &r->pending_handle);
// 2. meta_blcok | filter
WriteRawBlock(r->filter_block->Finish(), kNoCompression, &filter_block_handle);
// 3. meta_index_block
WriteBlock(&meta_index_block, &metaindex_block_handle);
// 4. index_block
WriteBlock(&r->index_block, &index_block_handle);
// 5. footer
r->status = r->file->Append(footer_encoding);
}
TableBuilder 则是调用各个 BlockBuilder 将编码好的 content 依次存入到 ldb 中。
3. 读取流程 #
打开 SSTable 步骤如下：
- 读取 Footer，根据里面的读取 Meta Index Block 和 Index Block，将 Index Block 的内容缓存到内存中；
- 根据 Meta Index Block 读取布隆过滤器的数据，缓存到内存中。
读取一个键的步骤如下：
- 根据键对 Index Block 的 restart point 进行二分搜索，找到这个键对应的 Data Block 的 BlockHandler；
- 根据 BlockHandler 的偏移计算出布隆过滤器的编号，读取相应的布隆过滤器；
- 通过布隆过滤器的数据判断键是否存在，不存在就结束
- 否则读取对应的 Data Block
- 对 Data Block 里的 restart point 进行二分搜索，找到搜索键对应的 restart point；
- 对这个 restart point 对应的键进行搜索，最多搜索 16 个键，找到键或者找不到键。