Lab 4.2 Engine 的读取

1 概述

从之前 Lab 4.1 Engine 的写入中, 我们已经实现了SST的构建流程, 这一章我们将实现Engine的读取流程。(这里的读取还包括引擎的初始化流程中对SST文件的读取)

同样地, 我们想从逻辑上梳理引擎的读取和查询流程:

1 存储引擎启动时

遍历data_dir下的SST文件, 将SST文件的元信息加载到内存中

2 接受查询请求

查询当前活跃的MemTable, 如果查到有效记录或删除记录, 则返回
若查询当前活跃的MemTable未命中, 则遍历冻结的MemTable, 由于冻结的MemTable也存在次序, 需要先查询最近冻结的MemTable
若查询冻结的MemTable未命中, 则遍历SST, 由于SST也存在次序, 需要先查询最近创建的SST
1. SST的顺序先按照Level排序, Level越低的SST越新, 需要先查询
2. 相同Level的SST按照sst_id排序, 这里的逻辑有所不同:
  1. 如果是Level 0的SST, 则按照sst_id排序, 从大到小查询, 越大的sst_id表示这个SST越新, 需要有限查询
  2. 如果是其他Level以上的SST, 其所有的SST的key都是有序分布且不重叠的, 既然key不重叠也就无所谓谁的优先级更高、谁会覆盖谁的key, 可以采用二分查询实现更高的效率, 下面是一个SST文件的案例:
```
Level 0: sst_15(key000-key050), sst_14(key005-key030), sst_13(key020-key040)
Level 1: sst_10(key100-key120), sst_11(key121-key140), sst_12(key141-key160)
Level 2: sst_08(key100-key120), sst_09(key121-key140)
```
整个SST文件遍历完成后, 若仍未命中, 则返回空指针表示key没有找到

补充

在后续实现WAL后, 在上述所有流程前, 会有一个对WAL日志进行检查并实现崩溃恢复的流程

2 代码实现

本小节你需要更改的代码文件为:

src/lsm/engine.cpp
include/lsm/engine.h

2.1 引擎的初始化

上一章Lab 4.1 Engine 的写入中, 我们在put操作中惰性触发了SST的刷盘操作, 因此在Engine启动时, 我们需要遍历data_dir下的SST文件, 将SST文件的元信息加载到内存中, 以便后续的查询操作:

LSMEngine::LSMEngine(std::string path) : data_dir(path) {
  // 初始化日志
  init_spdlog_file();

  // TODO: Lab 4.2 引擎初始化
}

说明

后续实现缓存池后, 构造函数中需要对缓存池进行初始化, 现阶段你的构造函数, 只需要将block_cache初始化为nullptr即可
第一次启动引擎时, 需要创建数据目录
init_spdlog_file函数用于初始化日志, 其内部是对std::call_once的封装, 因此其只有第一次调用时会执行

Hint

你需要从SST文件的命名格式中对next_sst_id和cur_max_level进行更新

level_sst_ids映射的数组需要你自己维护其优先级顺序, 不同Level的SST文件优先级可能不同, 现在你不需要关心Level 0以外的SST

2.2 查询接口

2.2.1 get

std::optional<std::pair<std::string, uint64_t>>
LSMEngine::get(const std::string &key, uint64_t tranc_id) {
  // TODO: Lab 4.2 查询

  return std::nullopt;
}

这里传入的uint64_t tranc_id是为了在实现事务功能后控制不同事务的可见性的, 也就是实现事务基础属性中的隔离性, 现阶段你可以忽略它

此外, 这里的返回值是一个由optional包裹的pair, pair的第一个元素是value, 第二个元素是tranc_id, value表示查询到的值, tranc_id表示这个键值对最新的修改事务的的tranc_id(现阶段同样可以忽略), 如果查询不到, 则返回std::nullopt

2.2.2 get_batch

std::vector<
    std::pair<std::string, std::optional<std::pair<std::string, uint64_t>>>>
LSMEngine::get_batch(const std::vector<std::string> &keys, uint64_t tranc_id) {
  // TODO: Lab 4.2 批量查询

  return {};
}

没啥好说的, 就是在get的基础上变成了批量查询

2.2.3 sst_get_

通过后缀你可以看出, 这个查询是专门在SST中进行查询的接口, 其_表示这个函数是不需要进行加锁操作的, 其加锁逻辑是其他上层组件控制的:

std::optional<std::pair<std::string, uint64_t>>
LSMEngine::sst_get_(const std::string &key, uint64_t tranc_id) {
  // TODO: Lab 4.2 sst 内部查询
  return std::nullopt;
}

思考: 什么情况下会单独对SST部分进行查询?

3 测试

完成Lab 4.1 Engine 的写入和本节Lab后, 你应该能通过test/test_lsm.cpp中IteratorOperations前的所有单元测试:

✗ xmake
[100%]: build ok, spent 1.936s
✗ xmake run test_lsm
[==========] Running 9 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 9 tests from LSMTest
[ RUN      ] LSMTest.BasicOperations
[       OK ] LSMTest.BasicOperations (0 ms)
[ RUN      ] LSMTest.Persistence
[       OK ] LSMTest.Persistence (228 ms)
[ RUN      ] LSMTest.LargeScaleOperations
[       OK ] LSMTest.LargeScaleOperations (1 ms)
[ RUN      ] LSMTest.MixedOperations
[       OK ] LSMTest.MixedOperations (0 ms)
[ RUN      ] LSMTest.IteratorOperations
unknown file: Failure
C++ exception with description "Not implemented" thrown in the test body.

[  FAILED  ] LSMTest.IteratorOperations (0 ms)

Keyboard shortcuts

Tiny-LSM-Lab