Lab 4.3 ConcactIterator

1 概述

其实这一章出现在这里是有一点突兀的, 照理说我们正常实现基础LSMEngine的下一个步骤是Compact。讲到这里我们接得知道Compact的逻辑了。

这里用一个具体案例进行讲解。

我们假设此时的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需要进行限制, 当这一层的SST数量超过阈值时, 我们需要将这一层所有的SST进行Compact到下一层。

在这个案例中, 我们下一次flush刷盘后, 假设得到了一个Level 0的SST为sst_16(key060-key080), 那么此时Level 0的SST数量超过了阈值4(这个是是假定的, 实际上是可在config.toml中配置的), 我们需要将Level 0的SST进行sst_16, sst_15, sst_14, sst_13到Level 1。但我们新Compact的SST会和Level 1本来的SST的key存在范围重叠, 这是不允许的, 所以实际上, 我们是将原来的Level 0和旧的Level 1的所有SST一并进行重新整理Compact形成新的Level 1 SST, 这里实际上就是用迭代器将2个Level的迭代器进行串联, 遍历这个迭代器, 逐一构建新的Level 1的SST, 那么是怎么个串联法呢?

首先, Level 0的SST之间存在key的重叠, 需要进行去重, 这里我们可以复用已有的HeapIterator, 见Lab 2.2 迭代器
其次就是我们将要实现的ConcactIterator, 这个迭代器会串联Level 1的所有SST形成层间迭代器
最后就是之后小节实现的TwoMergeIterator, 这个迭代器会串联HeapIterator和ConcactIterator, 按照优先级对迭代器进行输出, 遍历TwoMergeIterator即可构建新的Level 1的SST

Question

如果Compact发生的Level不是Level 0和Level 1, 而是Level x和Level y(x>0)呢?

答案显而易见, 还是用TwoMergeIterator对2个Level的层间迭代器进行遍历, 遍历过程中构造新的Level y的SST。只是TwoMergeIterator中包裹的Level x的迭代器从HeapIterator变成了ConcactIterator。

这一小节我们先实现ConcactIterator。

2 代码实现

你需要修改的文件:

src/sst/concact_iterator.cpp
include/sst/concact_iterator.h (Optional)

2.1 头文件分析

按照惯例, 我们简单分析下头文件定义:

class ConcactIterator : public BaseIterator {
private:
  SstIterator cur_iter;
  size_t cur_idx; // 不是真实的sst_id, 而是在需要连接的sst数组中的索引
  std::vector<std::shared_ptr<SST>> ssts;
  uint64_t max_tranc_id_;
};

这里的ssts就是这一层所有SST句柄的数组, cur_idx是当前迭代器指向的SST在ssts中的索引, cur_iter是当前cur_idx指向的SST的迭代器。

max_tranc_id_是调用这个迭代器的事务id, 也就是其最大的事务可见范围, 现在你不需要实现。

2.2 ConcactIterator 实现

这一章由于我们先介绍了Compact过程中的逻辑, 因此就先实现最简单的一个ConcactIterator:

BaseIterator &ConcactIterator::operator++() {
  // TODO: Lab 4.3 自增运算符重载
  return *this;
}

bool ConcactIterator::operator==(const BaseIterator &other) const {
  // TODO: Lab 4.3 比较运算符重载
  return false;
}

bool ConcactIterator::operator!=(const BaseIterator &other) const {
  // TODO: Lab 4.3 比较运算符重载
  return false;
}

ConcactIterator::value_type ConcactIterator::operator*() const {
  // TODO: Lab 4.3 解引用运算符重载
  return value_type();
}
ConcactIterator::pointer ConcactIterator::operator->() const {
  // TODO: Lab 4.3 ->运算符重载
  return nullptr;
}

这里基本上都是实现迭代器的运算符重载函数, 算是比较简单的一个小Lab

3 测试