Lab 4.1 Engine 的写入

1 概述

与之前的模块不同, LSMEngine部分我们不打算按照CRUD迭代器的顺序进行实验, 因为其Put操作包含了SST的构建流程, 而Get操作是对已经构建的SST进行查询, 因此, 本章的Lab以SST的生命周期为线索, 逐步实现Lab, 这样的设计也有助于你对上层组件运行调度机制的理解。

话不多说，我们先来看看Engine的头文件定义, 然后结合理论知识, 介绍put流程和sst的构建流程

class Level_Iterator;

class LSMEngine : public std::enable_shared_from_this<LSMEngine> {
public:
  std::string data_dir;
  MemTable memtable;
  std::map<size_t, std::deque<size_t>> level_sst_ids;
  std::unordered_map<size_t, std::shared_ptr<SST>> ssts;
  std::shared_mutex ssts_mtx;
  std::shared_ptr<BlockCache> block_cache;
  size_t next_sst_id = 0; // 下一个要分配的 sst id
  size_t cur_max_level = 0; // 当前最大的 level
};

class LSM {
private:
  std::shared_ptr<LSMEngine> engine;
  std::shared_ptr<TranManager> tran_manager_; // 本Lab不需要关注
};

这里, 我们使用了LSM包裹了LSMEngine, LSMEngine是你要补全函数实现的类, 其中定义了memtable, level_sst_ids, ssts, block_cache, next_sst_id, cur_max_level等成员变量。这里比较重要的包括:

level_sst_ids: 从level到这一层的sst_id数组, 每一个SST由一个sst_id唯一表示
ssts: sst_id到SST的映射
next_sst_id: SST的id分配器, LSMEngine在flush形成行的SST时, 会分配一个sst_id给SST, 然后将sst_id和SST映射关系存入ssts中, next_sst_id就是sst_id的分配器, 每次分配sst_id时, next_sst_id都会自增1
cur_max_level: 顾名思义, 就是当前SST的最大的level
data_dir: LSMEngine的data_dir, 即数据文件的存储位置, 这个参数我们在单元测试中会进行指定, SST文件需要存放在这个目录下
MemTable: 即整个LSM Tree引擎的内存表部分

剩下的成员变量:

ssts_mtx: 全局的sst文件的访问锁, 这里是一个读写锁, 当然这个变量不是必须的, 你可以按照自己的理解实现并发控制策略(不过建议使用这个变量)
block_cache: 全局的缓存池指针, 你实现缓存池之前, 默认其为nullptr即可

这里的l0_sst_ids记录了所有sst的id, 其排序是从大到小, 因为sst的id越大表示这个sst越新, 需要优先查询。

可以使用l0_sst_ids获取的id从哈希表ssts中查询SST的描述类(类似于文件描述符)。

2 写入/删除流程

结合刚刚对类的成员变量定义的简单介绍, 我们再次回顾一下LSM Tree的读写流程:

写入MemTable:
1. 如果写入的KV的value为空, 表示一个删除标记
2. 直接调用成员变量memtable的接口即可
3. 同样有批量接口和单次操作的接口
若当前活跃的MemTable大小达到阈值, 则将其冻结
1. 这一部分已经在MemTable中实现, 你无需再实现
若冻结的MemTable容量达到阈值, 则将最早冻结的MemTable转为SST
1. 判断MemTable容量并决定是否刷盘是你需要在本小节Lab进行实现的内容之一
2. SST文件的设计是每一层的SST文件数量不能超过指定阈值, 因此你刷盘的Level 0的SST文件可能会哦触发Level 0和Level 1的SST文件的compact, 不过这一任务没有放在Lab 4.1, Lab4.1中你当做就只有Level 0这一个层级即可

因此, 本小节Lab的核心就是整合之前创建的MemTable, SST, Block, Iterator, 并调用接口实现对外服务的功能

3 代码实现

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

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

3.1 Put && Remove

你首先需要实现put函数, put函数肯定是操纵memtable成员变量, 另外你也需要根据其容量接口函数判断什么时候需要进行flush操作:

uint64_t LSMEngine::put(const std::string &key, const std::string &value,
                        uint64_t tranc_id) {
  // TODO: Lab 4.1 插入
  // ? 由于 put 操作可能触发 flush
  // ? 如果触发了 flush 则返回新刷盘的 sst 的 id
  // ? 在没有实现  flush 的情况下，你返回 0即可
  return 0;
}
uint64_t LSMEngine::remove(const std::string &key, uint64_t tranc_id) {
  // TODO: Lab 4.1 删除
  // ? 在 LSM 中，删除实际上是插入一个空值
  // ? 由于 put 操作可能触发 flush
  // ? 如果触发了 flush 则返回新刷盘的 sst 的 id
  // ? 在没有实现  flush 的情况下，你返回 0即可
  return 0;
}

这个函数的最终版本需要调用flush进行刷盘, 因此建议你将次函数和后面的flush函数一起实现。

此时你仍然可以忽略tranc_id, 将其传递到接口的参数即可。至于返回值uint64_t, 你现阶段返回0即可。

额外说明, 这里说明一下为什么返回值是uint64_t，而不是void, 这主要是为后续的事务准备的, 刷盘意味着事务操作的持久化完成, 因此需要更新已经成功持久化的最大事务id, 也就是这里的返回值。如果你现在看不懂也没关系, 到实现事务的Lab就明白了。

根据之前部分描述, 此时你可以简化刷盘部分的逻辑, 即默认现在只有Level 0的SST文件, SST文件不会进行Compact形成新的Level

3.2 put_batch && remove_batch

和put/remove函数的逻辑几乎一样, 只是写入时是批量数据:

uint64_t LSMEngine::put_batch(
    const std::vector<std::pair<std::string, std::string>> &kvs,
    uint64_t tranc_id) {
  // TODO: Lab 4.1 批量插入
  // ? 由于 put 操作可能触发 flush
  // ? 如果触发了 flush 则返回新刷盘的 sst 的 id
  // ? 在没有实现  flush 的情况下，你返回 0即可
  return 0;
}

uint64_t LSMEngine::remove_batch(const std::vector<std::string> &keys,
                                 uint64_t tranc_id) {
  // TODO: Lab 4.1 批量删除
  // ? 在 LSM 中，删除实际上是插入一个空值
  // ? 由于 put 操作可能触发 flush
  // ? 如果触发了 flush 则返回新刷盘的 sst 的 id
  // ? 在没有实现  flush 的情况下，你返回 0即可
  return 0;
}

3.3 Flush

flush函数会将MemTable中frozen_tables中最旧的一个跳表的数据刷盘，并返回刷盘过程中提取的统计信息tranc_id, 现阶段你只需要返回0即可。

Hint: flush()的返回值是和put()等接口的返回值一致的

uint64_t LSMEngine::flush() {
  // TODO: Lab 4.1 刷盘形成sst文件
  return 0;
}

flush函数应该是这一小节的关键函数了, 这里的逻辑就是从memtable的接口将最旧的跳表刷盘城SST文件, 这里涉及到文件IO的操作时, 推荐使用作者定义好的辅助类FileObj, 其定义在include/utils/files.h中, 如果你有兴趣, 也可以看看``include/utils`中定义的其他工具类及其实现。

最后，SST文件的命名格式已经在get_sst_path中进行了详细的说明:

std::string LSMEngine::get_sst_path(size_t sst_id, size_t target_level) {
  // sst的文件路径格式为: data_dir/sst_<sst_id>.<level>，sst_id格式化为32位数字
  std::stringstream ss;
  ss << data_dir << "/sst_" << std::setfill('0') << std::setw(32) << sst_id
     << '.' << target_level;
  return ss.str();
}

后缀标记了这个SST文件所属的Level, 在你实现Compact前, 这个后缀设置为0即可

你必须严格遵守SST文件格式的命名规范, 如果你采用自己的文件命名方式, 那么请自行修改对应的单元测试函数(非常不推荐)。

4 测试

由于我们目前仅实现了写入模块, 测试函数无法从引擎读取数据, 因此本小节没有单元测试, 当你实现Lab 4.2 Engine 的读取后会进行统一的单元测试。

5 思考

现在请先思考一下几个问题，然后开启Lab 4.2 Engine 的读取

Toni-LSM-Lab