Lab 3.6 SST 查询

1 概述

首先, 需要声明, 这一小节的实验容量稍大, 你将同时实现SST的基础查询功能和迭代器SstIterator。

为什么需要这样设计呢？答案是因为，我们对组件的查询设计沿用了STL的迭代器风格，查询都是返回迭代器作为结果的。但我们的思路首先应该是实现SST本身, 后续再实现迭代器SstIterator。但STL风格的接口设计导致二者耦合了，因此，这里索性将二者同时实现了。

1.1 SST 的定义

同样，我们先看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; // 暂时忽略
  // ...
};

SST最关键的成员变量是meta_entries, 其本质上就是从硬盘中读取了SST文件的Meta Section部分解析后的BlockMeta数组。在接受外部查询请求时, 我们会根据key在meta_entries中查找对应的BlockMeta, 然后从硬盘中读取Block并解码得到内存中的Block, 最后再调用Block的查询接口完成查询。这里的FileObj file成员变量就是实现对应的SST文件的IO操作的类实例。

当然, 如果你完成了后续Lab, 这里的逻辑存在一些不同:

如果后续实现了缓存池, 就可以从缓存池中查询Block, 而不是从硬盘中读取。

如果后续实现了BloomFilter, 那么在查询时, 首先会通过BloomFilter判断key是否有存在的可能, 如果不可能存在, 则直接返回nullptr, 否则继续调用查询接口完成查询。

1.2 SstIterator 的定义

然后是SstIterator的定义:

class SstIterator : public BaseIterator {
  // friend xxx

private:
  std::shared_ptr<SST> m_sst;
  size_t m_block_idx;
  uint64_t max_tranc_id_;
  std::shared_ptr<BlockIterator> m_block_it;
  mutable std::optional<value_type> cached_value; // 缓存当前值
  // ...
};

要实现SST的迭代器, 需要记录当前的Block索引, 以及Block中的Entry索引, 因此也需要原SST类的this指针, 之前已经介绍过enable_shared_from_this了, 不再赘述。

这里使用m_sst, m_block_idx和m_block_it分别记录原始的SST类对象、当前Block在SST中的位置、当前迭代器在Block中的位置。cached_value仍然用做缓存值, 因为读取键值对涉及文件IO操作, 因此这里的cached_value就不仅仅是为了实现->的辅助成员变量了, 而是正儿八经的优化手段。

本小节Lab中, 你需要修改的代码文件:

实现SST需要修改的文件
- src/sst/sst.cpp
- include/sst/sst.h (Optional)
实现SstIterator需要修改的文件
- src/sst/sst_iterator.cpp
- include/sst/sst_iterator.h (Optional)

2 SST 基础代码实现

2.1 打开 SST 文件

你需要实现SST：：open函数:

// 头文件中将其定义为静态函数
std::shared_ptr<SST> SST::open(size_t sst_id, FileObj file,
                               std::shared_ptr<BlockCache> block_cache) {
  // TODO Lab 3.6 打开一个SST文件, 返回一个描述类

  return nullptr;
}

尽管我们的SST对数据的查询是惰性地从文件系统中进行读取, 但必要的元信息需要我们加载到内存中。SST::open的工就是将SST文件的元信息进行解码和加载，返回一个描述类SST，你可以将SST看做是SST文件的操作句柄，或者是文件描述符。

如果你后续Lab实现了布隆过滤器, 那么布隆过滤器的bit数组也需要加载到内存中

block_cache是缓存池的指针, 你现在不需要管它是哪里来的, 只需要对类的成员变量进行简单赋值即可

2.2 加载 Block

在接受其他组件的查询请求后, SST会根据元信息定位请求的key可能位于哪一个Block(因为BlockMeta中存储了首尾的key), 接下来就是读取这个Blcok, 这就是你需要实现的read_block函数:

std::shared_ptr<Block> SST::read_block(size_t block_idx) {
  // TODO: Lab 3.6 根据 block 的 id 读取一个 `Block`
  return nullptr;
}

实现缓存池后, 你的代码逻辑应该是

从缓存池获取Block, 如果缓存命中, 直接返回。

缓存未命中才从文件系统中读取

返回前别忘了更新缓存池

2.3 根据 key 查询 Block

size_t SST::find_block_idx(const std::string &key) {
  // 先在布隆过滤器判断key是否存在
  // TODO: Lab 3.6 二分查找
  // ? 给定一个 `key`, 返回其所属的 `block` 的索引
  // ? 如果没有找到包含该 `key` 的 Block，返回-1
  return 0;
}

find_block_idx函数的目的是根据key在meta_entries中查找对应的BlockMeta, 返回BlockMeta在meta_entries中的索引。如果key不存在于SST中, 则返回-1。

这里由于Block的数据是有序的, 因此你需要使用二分查找算法提速, 否者你的查询性能会非常差。

3 SstIterator 代码实现

3.1 SstIterator 定位函数

你需要实现下面的迭代器定位函数:

void SstIterator::seek_first() {
  // TODO: Lab 3.6 将迭代器定位到第一个key
}

void SstIterator::seek(const std::string &key) {
  // TODO: Lab 3.6 将迭代器定位到指定key的位置
}

Hint 这里的逻辑也很简单, 就是先使用记录在sst中的meta_entries找到包含要查找的key的Block(find_block_idx), 从文件中读取这个Block(read_block), 然后再读取的Block中调用获取指定key的迭代器的构造函数, 通过BlockIterator实现在Block中的定位。

SST创建迭代器时, 会在构造函数中选择是否偏移到指定的key, 你可以查看SstIterator的构造函数, 看看他们是如何与不同组件和函数见衔接的。

3.2 运算符重载函数

作为迭代器, 我们的惯例就行要实现下面几个运算符重载函数:

BaseIterator &SstIterator::operator++() {
  // TODO: Lab 3.6 实现迭代器自增
  return *this;
}

bool SstIterator::operator==(const BaseIterator &other) const {
  // TODO: Lab 3.6 实现迭代器比较
  return false;
}

bool SstIterator::operator!=(const BaseIterator &other) const {
  // TODO: Lab 3.6 实现迭代器比较
  return false;
}

SstIterator::value_type SstIterator::operator*() const {
  // TODO: Lab 3.6 实现迭代器解引用
  return {};
}

4 补全 SST

在实现了SstIterator后, 你可以补全以SST中以SstIterator作为返回值的几个函数:

SstIterator SST::get(const std::string &key, uint64_t tranc_id) {
  // TODO: Lab 3.6 根据查询`key`返回一个迭代器
  // ? 如果`key`不存在, 返回一个无效的迭代器即可
  throw std::runtime_error("Not implemented");
}

SstIterator SST::begin(uint64_t tranc_id) {
  // TODO: Lab 3.6 返回起始位置迭代器
  throw std::runtime_error("Not implemented");
}

SstIterator SST::end() {
  // TODO: Lab 3.6 返回终止位置迭代器
  throw std::runtime_error("Not implemented");
}

这几个函数都很简单, 因为具体的定位操作是在SstIterator内部完成的(虽然其反过来有调用了SST的find_block_idx等函数), 因此只需要调用SstIterator的构造函数即可。这里作为Lab的内容主要是为了让你对不同组件之间的交互有一个认真, 意思到这样一个设计思路: 迭代器是连接不同组件的桥梁.

5 测试

此次测试包含之前Lab 3.5的实现, 预期的结果是:

✗ xmake
[100%]: build ok, spent 0.517s
✗ xmake run test_sst  
[==========] Running 8 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 8 tests from SSTTest
[ RUN      ] SSTTest.BasicWriteAndRead
[       OK ] SSTTest.BasicWriteAndRead (3 ms)
[ RUN      ] SSTTest.BlockSplitting
[       OK ] SSTTest.BlockSplitting (1 ms)
[ RUN      ] SSTTest.KeySearch
[       OK ] SSTTest.KeySearch (0 ms)
[ RUN      ] SSTTest.Metadata
[       OK ] SSTTest.Metadata (0 ms)
[ RUN      ] SSTTest.EmptySST
[       OK ] SSTTest.EmptySST (0 ms)
[ RUN      ] SSTTest.ReopenSST
[       OK ] SSTTest.ReopenSST (0 ms)
[ RUN      ] SSTTest.LargeSST
[       OK ] SSTTest.LargeSST (0 ms)
[ RUN      ] SSTTest.LargeSSTPredicate
test/test_sst.cpp:235: Failure
Value of: result.has_value()
  Actual: false
Expected: true

unknown file: Failure
C++ exception with description "bad optional access" thrown in the test body.

[  FAILED  ] SSTTest.LargeSSTPredicate (1 ms)
[----------] 8 tests from SSTTest (8 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test suite ran. (8 ms total)
[  PASSED  ] 7 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] SSTTest.LargeSSTPredicate

 1 FAILED TEST
error: execv(/home/toni/proj/toni-lsm/build/linux/x86_64/release/test_sst ) failed(1)

如果仅仅是得到一个可以跑的SST, 那么现在你已经完成的SST的大部分功能了。这里的LargeSSTPredicate需要你在实现下一小节的谓词查询后才能通过。

Toni-LSM-Lab