Lab 3.1 Block 实现

1 准备工作

老套路, 我们先理一下Block的数据结构, 看看头文件定义:

// include/block/block.h
class Block : public std::enable_shared_from_this<Block> {
  friend BlockIterator;

private:
  std::vector<uint8_t> data; // 对应架构图的 Data
  std::vector<uint16_t> offsets; // 对应架构图的 Offset
  size_t capacity;

  struct Entry {
    std::string key;
    std::string value;
    uint64_t tranc_id;
  };
  // ...
};

这里可能涉及C++的新特性:

public std::enable_shared_from_this<Block>

std::enable_shared_from_this 是 C++11 引入的一个标准库特性，它允许一个对象安全地创建指向自身的std::shared_ptr。这里先简单说明一下, 后续实现迭代器的时候就知道其作用了。

这里主要对data和offsets这两个数据结构进行说明, 他们在构建阶段和读取阶段存在一定区别, 首先还是给出架构图:

Block

构建阶段 当我们从Skiplist拿到数据构建一个SST时, SST需要逐个构建Block, 这个Block在构建时步骤如下:

逐个将编码的键值对(也就是Entry)写入data数组, 同时将每个Entry的偏移量记录在内存中的offsets数组中。
当这个Block容量达到阈值时, Block构建完成, 你需要将offsets数组写入到Block的末尾。
还需要再Block末尾写入一个Entry Num值, 用于标识这个Block中键值对的数量, 从而在解码时获取Offset的其实位置(因为每个Entry Offset大小是固定的整型值)
当前Block构建完成, SST开始构建下一个Block。

这里之所以将先将键值对持久化到data数组, 而元信息暂存于内存的offsets数组, 是因为Data是在数据部分之后的的Offset部分的偏移需要再键值对完全写入Data部分后才能确定

解码阶段 解码阶段, 直接将Data、Offset解码形成内存中的Block的实例以为上层组件提供查询功能，同时如果实现了缓存池，需要再缓存池中进行记录。

2 代码实现

你需要修改的函数都在src/block/block.cpp中。

2.1 Block 编码和解码

这里你先不要管这个Block是哪里来的, 就当它已经存在, 实现编码和解码的功能:

std::vector<uint8_t> Block::encode() {
  // TODO Lab 3.1 编码单个类实例形成一段字节数组
  return {};
}

std::shared_ptr<Block> Block::decode(const std::vector<uint8_t> &encoded,
                                     bool with_hash) {
  // TODO Lab 3.1 解码字节数组形成类实例
  return nullptr;
}

这里特别说明, encode时的数据是不包括校验的哈希值的因为哈希值是在SST控制Block构建过程中计算的, 但在decode时可以通过with_hash参数来指示传入的encoded是否包含哈希值, 如果包含哈希值, 则需要先校验哈希值是否正确, 校验失败则抛出异常。

之所以encode不计算哈希值, decode按需计算哈希值, 其实是作者初版代码设计不佳, 这里先不纠结了, 后续可能会进行优化, 如果你有优化方案, 可对代码进行修改后提PR

编解码时你需要注意数据的格式, 如果校验格式错误, 你需要抛出异常, 否则错误将非常难以Debug

2.2 局部数据编解码函数

对于二进制数据, 你需要按照设计的编码结构获取其key, value和tranc_id, 这里我们实现几个辅助函数:

// 从指定偏移量获取entry的key
std::string Block::get_key_at(size_t offset) const {
  // TODO Lab 3.1 从指定偏移量获取entry的key
  return "";
}

// 从指定偏移量获取entry的value
std::string Block::get_value_at(size_t offset) const {
  // TODO Lab 3.1 从指定偏移量获取entry的value
  return "";
}

uint16_t Block::get_tranc_id_at(size_t offset) const {
  // TODO Lab 3.1 从指定偏移量获取entry的tranc_id
  // ? 你不需要理解tranc_id的具体含义, 直接返回即可
  return 0;
}

2.3 构建 Block

Block构建是由SST控制的, 其会不断地调用下面这个函数添加键值对:

bool Block::add_entry(const std::string &key, const std::string &value,
                      uint64_t tranc_id, bool force_write) {
  // TODO Lab 3.1 添加一个键值对到block中
  // ? 返回值说明：
  // ? true: 成功添加
  // ? false: block已满, 拒绝此次添加
  return false;
}

这里需要注意, force_write参数表示是否强制写入, 如果为true, 则不管Block是否已满, 都强制写入, 否则如果Block已满, 则拒绝此次写入。

Block是否已满的判断将当前数据容量与成员变量capacity进行比较, capacity在Block初始化时由SST传入, 表示一个Block的最大容量。

如果你需要一些使用config.toml中预定义的一些阈值变量或者其他常来那个, 你也可以通过TomlConfig::getInstance().getXXX的方式获取

2.4 二分查询

Block构建时是通过SST遍历Skiplist的迭代器调用add_entry实现的, 因此Block的数据是有序的, 你需要实现一个二分查找函数, 用于在Block中查找指定key所属的Entry在offset元数据中的索引:

std::optional<size_t> Block::get_idx_binary(const std::string &key,
                                            uint64_t tranc_id) {
  // TODO Lab 3.1 使用二分查找获取key对应的索引
  return std::nullopt;
}

get_value_binary函数中会调用get_idx_binary函数, 并返回指定key的value:

// 使用二分查找获取value
// 要求在插入数据时有序插入
std::optional<std::string> Block::get_value_binary(const std::string &key,
                                                   uint64_t tranc_id) {
  auto idx = get_idx_binary(key, tranc_id);
  if (!idx.has_value()) {
    return std::nullopt;
  }

  return get_value_at(offsets[*idx]);
}

3 测试

如果成功完成了上述的所有函数, 你应该如下运行测试并得到结果:

✗ xmake
[100%]: build ok, spent 1.94s
✗ xmake run test_block
[==========] Running 10 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 10 tests from BlockTest
[ RUN      ] BlockTest.DecodeTest
[       OK ] BlockTest.DecodeTest (0 ms)
[ RUN      ] BlockTest.EncodeTest
[       OK ] BlockTest.EncodeTest (0 ms)
[ RUN      ] BlockTest.BinarySearchTest
[       OK ] BlockTest.BinarySearchTest (0 ms)
[ RUN      ] BlockTest.EdgeCasesTest
[       OK ] BlockTest.EdgeCasesTest (0 ms)
[ RUN      ] BlockTest.LargeDataTest
[       OK ] BlockTest.LargeDataTest (0 ms)
[ RUN      ] BlockTest.ErrorHandlingTest
[       OK ] BlockTest.ErrorHandlingTest (1 ms)
[ RUN      ] BlockTest.IteratorTest
test/test_block.cpp:225: Failure
Expected equality of these values:
  count
    Which is: 0
  test_data.size()
    Which is: 100

你应该能通过BlockTest.IteratorTest之前的所有单元测试, BlockTest.IteratorTest这个测试会测试Block的迭代器功能, 因为Block的迭代器功能还没有实现, 所以会失败, 这是符合预期的。

4 下一步

现在进入下一步前, 你可以先思考:

如何实现Block的迭代器
为什么我们需要让Block类继承std::enable_shared_from_this<Block>?

带着这些疑问, 欢迎开启下一章

Keyboard shortcuts

Tiny-LSM-Lab