Lab 3.5 SSTBuilder

1 概述

SSTBuilder是SST文件的构造器, 它将MemTable中的数据进行编码并写入磁盘形成SST。不过这里我们并没有设计到不同组件数据的控制，这是由更上层的结构控制的。

SST和SSTBuilder的关系是什么？ 区别在于，SSTBuilder这个类的实例只在SST文件构建过程中存在, 其是可写的数据结构, 构建过程可不断添加键值对进行编码。在其调用Build后，其会将自身数据编码为SST文件，并转化为一个SST类实例, SST类本质上就是SST文件的控制结构。

这样说起来可能不好理解, 让我们结合代码将这个过程具体化, 先看其SSTBuilder和SST的头文件定义:

class SST : public std::enable_shared_from_this<SST> {
  // ...  
private:
  FileObj file;
  std::vector<BlockMeta> meta_entries;
  uint32_t bloom_offset;
  uint32_t meta_block_offset;
  size_t sst_id;
  std::string first_key;
  std::string last_key;
  std::shared_ptr<BloomFilter> bloom_filter;
  std::shared_ptr<BlockCache> block_cache;
  uint64_t min_tranc_id_ = UINT64_MAX;
  uint64_t max_tranc_id_ = 0;

public:
  // ...
};

class SSTBuilder {
private:
  Block block;
  std::string first_key;
  std::string last_key;
  std::vector<BlockMeta> meta_entries;
  std::vector<uint8_t> data;
  size_t block_size;
  std::shared_ptr<BloomFilter> bloom_filter; // 后续Lab内容
  uint64_t min_tranc_id_ = UINT64_MAX; // 后续Lab内容
  uint64_t max_tranc_id_ = 0; // 后续Lab内容

public:
  // 创建一个sst构建器, 指定目标block的大小
  SSTBuilder(size_t block_size, bool has_bloom); 
  // 添加一个key-value对
  void add(const std::string &key, const std::string &value, uint64_t tranc_id);
  // 完成当前block的构建, 即将block写入data, 并创建新的block
  void finish_block();
  // 构建sst, 将sst写入文件并返回SST描述类
  std::shared_ptr<SST> build(size_t sst_id, const std::string &path,
                             std::shared_ptr<BlockCache> block_cache);
};

构建流程

当MemTable的大小超过阈值后，准备将MemTable中最旧的Frozen Table刷出为SST。
先创建一个SSTBuilder, 按照迭代器的顺序遍历Frozen Table，将key-value对添加到SSTBuilder中:
1. SSTBuilder会有一个当前的block, 其add函数首先会调用Block::add_entry将迭代器的kv对插入
2. 如果当前的block容量超出阈值block_size, 就调用finish_block将其编码到data, 并清楚当前block相关数据, 开启下一个block的构建
3. 遍历完成迭代器的所有kv对的插入后, 调用build将所有的数据刷到文件系统, 并返回一个SST描述类

读取流程

SST构造函数会绑定一个文件描述符(这里是我自定义封装的文件读取类FileObj file)
SST中的meta entries从第一次读取后就常驻内存(第一次读取可以是构造函数, 也可以是第一次get)
上层调用get时, 会从元数据meta_entries中进行二分查找, 找到对应的block的偏移量, 然后调用文件描述对象file从磁盘中读取
读取后的字节流交由Block::decode解码得到内存中的Block
内存中的Block调用之前实现的查询函数完成二分查询

2 代码实现

2.1 SSTBuilder::add 函数

Hint: 建议你先看完下一个finish_block函数的描述后再开始写代码, 因为这个函数中需要使用finish_block函数

SSTBuilder中的block成员变量即为当前正在构建的Block, add函数不断接受上部组件传递的键值对, 并将键值对添加到当前正在构建的Block中, 当Block容量达到阈值时, 将Block写入data数组, 并创建一个新的Block继续构建。构建结束后，这个data数组就包含了多个Block的编码字节, 经进一步处理后即可刷盘形成SST:

void SSTBuilder::add(const std::string &key, const std::string &value,
                     uint64_t tranc_id) {
  // TODO: Lab 3.5 添加键值对
}

这里的一些阈值参数你同样可以采取TomlConfig::getInstance().getxxx()的方法获取配置文件config.toml中定义的常量

2.2 SSTBuilder::finish_block 函数

根据前文介绍可知, SSTBuilder只有一个活跃的block支持插入键值对进行构建, 超出阈值后其将会编码为Block并写入data数组, 这个过程就是SSTBuilder::finish_block函数的功能:

void SSTBuilder::finish_block() {
  // TODO: Lab 3.5 构建块
  // ? 当 add 函数发现当前的`block`容量超出阈值时，需要将其编码到`data`，并清空`block`
}

2.3 SSTBuilder::build 函数

当上层组件已经将所有键值对插入到SSTBuilder中后，调用SSTBuilder::build函数即可完成SST文件的构建, 其会返回一个SST指针:

std::shared_ptr<SST>
SSTBuilder::build(size_t sst_id, const std::string &path,
                  std::shared_ptr<BlockCache> block_cache) {
  // TODO 3.5 构建一个SST
  return nullptr;
}

参数列表中, sst_id表示SST的编号， path表示SST文件的存储路径， block_cache表示Block的缓存池。你相比也意识到, 当SST从内存持久化为文件后, 其IO必然收到缓存池的管理, 这也是我们之后的内容, 这里你也不需要考虑缓存池的指针, 当它为nullptr即可

这里涉及到文件IO的操作, 作者已经在include/utils中封装了一个文件IO管理类FileObj, 你需要阅读include/utils/files.h即src/utils/files.cpp来了解其使用方法

3 测试

到目前位置, 我们只是实现了SST的构建工具类SSTBuilder, 但由于我们很没有实现SST的查询功能, 所以现在我们还无法通过查询接口验证我们SST构建的正确性, 因此单元测试需要完成后续SST相关Lab才能实现。