C++从零开始实现LSM-Tree-KV存储-04-SST

项目
,

这一小节实现基于之前的Block完成SST的编解码、迭代器。

代码仓库：https://github.com/ToniXWD/toni-lsm

1 SST设计

上一小节已经介绍了Block和SST的关系, 以及SST和Immutable MemTable的关系。不过缺失了SST的编码方式。

参考Minni LSM的编码方式: SST文件由多个Block组成，每个Block的格式如下：

SST

这里的每个Block_x就是上一节介绍的编码格式, 其后会追加32位的哈希值，用于校验, 这也是为什么之前的Block::decode需要一个参数来判断Block是否包含哈希值的原因。每个Block对应一个Meta, 每个Meta记录这个Block在SST文件中的偏移量、第一个和最后一个key的元数据(长度和大小)。

对每个Block的索引和Block不同, 需要尤其注意。因为Block的数据是已经加载到内存中的, 而SST则是存在磁盘上的, 所以这里需要根据Meta Section Offset定位到Meta Section并将其读取到内存，然后根据索引在内存中读取对应的Meta, 再从文件系统重读取真正的Block, 读取的字节序列交由我们之前实现的Block::decode处理。也就是说, 第一次读取Meta Section之后其就常驻于内存中, 之后的Block的元数据读取都是在内存中进行的。(这里还没有实现缓存池管理, 因此后续的代码可能会有变化)。

2 SST实现

2.1 BlockMeta

根据之前描述的编码方式和过程，如下设计：

1
2
3
4
5
6
7
8
9
10
11
class BlockMeta {
  friend class BlockMetaTest;
public:
  size_t offset;       // 块在文件中的偏移量
  std::string first_key; // 块的第一个key
  std::string last_key;  // 块的最后一个key
  static void encode_meta_to_slice(std::vector<BlockMeta> &meta_entries, std::vector<uint8_t> &metadata);
  static std::vector<BlockMeta> decode_meta_from_slice(const std::vector<uint8_t> &metadata);
  BlockMeta();
  BlockMeta(size_t offset, const std::string& first_key, const std::string& last_key);
};

这里的重要函数只有encode_meta_to_slice和decode_meta_from_slice，分别用于将BlockMeta编码到字节序列和从字节序列解码出BlockMeta。这里的实现也就是比较繁琐, 倒没有特别易错的地方和技术难度, 这里就不列出了, 有兴趣的可以看代码。

2.2 SST

这里把SST分为SSTBuilder和SST两个类，SSTBuilder用于构建SST文件，SST用于读取SST文件。SSTBuilder执行刷盘后会返回SST描述类, SST描述类中对SST文件的读取和解析需要是惰性的（后续实现缓存池管理后代码可能会有变化）。

这里的SST类的设计如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class SST : public std::enable_shared_from_this<SST> {
  friend class SSTBuilder;

private:
  FileObj file; // 封装的对SST文件的操作, 后续会提到
  std::vector<BlockMeta> meta_entries; // 内存中的meta数据, 读取sst文件时会从文件中加载
  uint32_t meta_block_offset;
  size_t sst_id;
  std::string first_key;
  std::string last_key;

public:
  // 从文件中打开sst
  static std::shared_ptr<SST> open(size_t sst_id, FileObj file);
  // 创建一个sst, 只包含首尾key的元数据
  static std::shared_ptr<SST>
  create_sst_with_meta_only(size_t sst_id, size_t file_size,
                            const std::string &first_key,
                            const std::string &last_key);
  // 根据索引读取block
  std::shared_ptr<Block> read_block(size_t block_idx);

  // 找到key所在的block的idx
  size_t find_block_idx(const std::string &key);

  // 根据key返回迭代器
  SstIterator get(const std::string &key);

  // 返回sst中block的数量
  size_t num_blocks() const;

  // 返回sst的首key
  std::string get_first_key() const;

  // 返回sst的尾key
  std::string get_last_key() const;

  // 返回sst的大小
  size_t sst_size() const;

  // 返回sst的id
  size_t get_sst_id() const;

  SstIterator begin();
  SstIterator end();
};

class SSTBuilder {
private:
  Block block; // 当前block
  std::string first_key; // 当前block的第一个key
  std::string last_key; // 当前block的最后一个key
  std::vector<BlockMeta> meta_entries; // 全局的meta数据
  std::vector<uint8_t> data; // 全局sst编码数据
  size_t block_size; // block的阈值
  std::vector<uint32_t> key_hashes;

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

这里为了后续实现迭代器, SST类也继承了std::enable_shared_from_this<SST>，这样在SstIterator中可以通过shared_from_this获取SST的shared_ptr。

最后这里理清下SST的构建和读取流程：

构建流程

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

读取流程

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

这里介绍完逻辑后, 关键代码给出add, build:

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SSTBuilder::add(const std::string &key, const std::string &value) {
  // 记录第一个key
  if (first_key.empty()) {
    first_key = key;
  }

  // 计算当前key的hash并存储
  uint32_t hash = static_cast<uint32_t>(std::hash<std::string>{}(key));
  key_hashes.push_back(hash);

  if (block.add_entry(key, value)) {
    // block 满足容量限制, 插入成功
    last_key = key;
    return;
  }

  finish_block(); // 将当前 block 写入

  block.add_entry(key, value);
  first_key = key;
  last_key = key; // 更新最后一个key
}

build

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
std::shared_ptr<SST> SSTBuilder::build(size_t sst_id, const std::string &path) {
  // 完成最后一个block
  if (!block.is_empty()) {
    finish_block();
  }

  // 如果没有数据，抛出异常
  if (meta_entries.empty()) {
    throw std::runtime_error("Cannot build empty SST");
  }

  // 编码元数据块
  std::vector<uint8_t> meta_block;
  BlockMeta::encode_meta_to_slice(meta_entries, meta_block);

  // 计算元数据块的偏移量
  uint32_t meta_offset = data.size();

  // 构建完整的文件内容
  // 1. 已有的数据块
  std::vector<uint8_t> file_content = std::move(data);

  // 2. 添加元数据块
  file_content.insert(file_content.end(), meta_block.begin(), meta_block.end());

  // 3. 添加元数据块偏移量
  file_content.resize(file_content.size() + sizeof(uint32_t));
  memcpy(file_content.data() + file_content.size() - sizeof(uint32_t),
         &meta_offset, sizeof(uint32_t));

  // 创建文件
  FileObj file = FileObj::create_and_write(path, file_content);

  // 返回SST对象
  auto res = std::make_shared<SST>();

  res->sst_id = sst_id;
  res->file = std::move(file);
  res->first_key = meta_entries.front().first_key;
  res->last_key = meta_entries.back().last_key;
  res->meta_block_offset = meta_offset;
  res->meta_entries = std::move(meta_entries);

  return res;
}

至于get, 需要先实现迭代器

3 SST迭代器实现

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

首先看迭代器的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class SST;

class SstIterator {
  friend SST;

private:
  std::shared_ptr<SST> m_sst;
  size_t m_block_idx;
  std::shared_ptr<BlockIterator> m_block_it;

public:
  using value_type = std::pair<std::string, std::string>;

  // 创建迭代器, 并移动到第一个key
  SstIterator(std::shared_ptr<SST> sst);
  // 创建迭代器, 并移动到第指定key
  SstIterator(std::shared_ptr<SST> sst, const std::string &key);

  void seek_first(); // 将迭代器置于开始位置
  void seek(const std::string &key); // 将迭代器置于指定key的位置
  bool is_end();
  std::string key();
  std::string value();

  SstIterator &operator++();
  SstIterator operator++(int) = delete;
  bool operator==(const SstIterator &other) const;
  bool operator!=(const SstIterator &other) const;
  value_type operator*() const;
};

这里使用m_sst, m_block_idx和m_block_it分别记录原始的SST类对象、当前Block在SST中的位置、当前迭代器在Block中的位置。

这里比较重要的是定位迭代器的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void SstIterator::seek_first() {
  if (!m_sst || m_sst->num_blocks() == 0) {
    m_block_it = nullptr;
    return;
  }

  m_block_idx = 0;
  auto block = m_sst->read_block(m_block_idx);
  m_block_it = std::make_shared<BlockIterator>(block);
}

void SstIterator::seek(const std::string &key) {
  if (!m_sst) {
    m_block_it = nullptr;
    return;
  }

  try {
    m_block_idx = m_sst->find_block_idx(key);
    auto block = m_sst->read_block(m_block_idx);
    if (!block) {
      m_block_it = nullptr;
      return;
    }
    m_block_it = std::make_shared<BlockIterator>(block, key);
  } catch (const std::exception &) {
    m_block_it = nullptr;
    throw std::runtime_error("could not read a block from m_sst");
  }
}

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

4 下一步是什么？

现在已经有了Blcok, SST, MemTable。我们是不是可以完成基础的CRUD了呢?

并不是, 首先是我们目前很没有实现文件加载的FileObj类。这个下一节介绍。

然后就是，SST的迭代器SstIterator只包含当前的SST内容, 但如果不同的SST中有标记删除的键值对(value为空), 后续的SST迭代器会出现bug, 这个也需要使用之前的堆完成排除。