leveldb笔记之18:Iterator

#leveldb

Iterator 的思想在 stl 很常见,通过迭代器,可以实现算法和容器的解耦。当我们实现某个算法时,只需要关注迭代器的常见操作,例如++ --等,而不用关心作用的具体容器是 map 还是 vector.

在 leveldb 的代码里,迭代器的应用也非常普遍,接口上变成了next prev等,在我看来主要有两个好处:

  1. 通用的设计:我们已经都习惯了迭代器的使用,通过Iterator来提供遍历数据的接口,学习成本低,protobuf里也在大量使用。
    2.易于实现:在不同的数据上,实现相同的Iterator接口,使得在操作这些不同数据时,可以统一使用Iterator.这个跟 stl 里的思想是一致的。

正是由于大量的使用,理解leveldb 的Iterator,对通顺的阅读源码十分重要。

1. Iterator

Iterator是最原始的基类,定义在iterator.h

文档里的注释很全面,接口就不一一介绍了。

子类定义较多:

iterator

注:在SkipList里同样有一个SkipList::Iterator定义,跟本文内容无关.

2. leveldb::Block::Iter

leveldb::Block::Iter用于 block 的读取,例如 sstable 里的 data-block index-block meta-index-block 等

3. leveldb::MemTableIterator

leveldb::MemTableIterator用于 memtable 的读取

4. MergingIterator

MergingIterator用于文件多路归并,记录每一个 sstable 的 iterator,非常像 stl 里的merge.

初始化时,传入多个Iterator*

  MergingIterator(const Comparator* comparator, Iterator** children, int n)
      : comparator_(comparator),
        children_(new IteratorWrapper[n]),
        n_(n),
        current_(nullptr),
        direction_(kForward) {
    for (int i = 0; i < n; i++) {
      children_[i].Set(children[i]);
    }
  }

多个Iterator记录到children_n_表示其大小。

Seek为例:

  virtual void Seek(const Slice& target) {
    for (int i = 0; i < n_; i++) {
      children_[i].Seek(target);
    }
    FindSmallest();
    direction_ = kForward;
  }

首先是所有Iterator*都查找target,然后通过FindSmallest找到最小的那个,记录到current_

void MergingIterator::FindSmallest() {
  IteratorWrapper* smallest = nullptr;
  for (int i = 0; i < n_; i++) {
    IteratorWrapper* child = &children_[i];
    if (child->Valid()) {
      if (smallest == nullptr) {
        smallest = child;
      } else if (comparator_->Compare(child->key(), smallest->key()) < 0) {
        smallest = child;
      }
    }
  }
  current_ = smallest;
}

后续每次Next都是current_++;FindSmallest()的过程,其实就是 mergesort 的指针操作了。

key()/value()返回的是current_->key()/value(),因此不断Next就可以有序获取到全部文件的数据。

Prev则恰好相反,direction_记录当前是Next/Prev,用于调整指针位置。

4. leveldb::Version::LevelFileNumIterator

LevelFileNumIterator接收一个有序的文件列表,支持查找 target 可能存在于哪个文件,以及遍历文件列表。

// 接收一个有序的文件列表,支持遍历
// key: 文件的largest key encode 后的值
// value: 文件的number && size encode 后的值
class Version::LevelFileNumIterator : public Iterator {
 public:
  LevelFileNumIterator(const InternalKeyComparator& icmp,
                       const std::vector<FileMetaData*>* flist)
      : icmp_(icmp),
        flist_(flist),
        index_(flist->size()) {        // Marks as invalid
  }

还是以Seek为例:

  //index_指向可能存在 target 的文件
  virtual void Seek(const Slice& target) {
    index_ = FindFile(icmp_, *flist_, target);
  }

FindFile我们会在二分法里专门介绍下。

key存储文件的 largest,value存储文件的number + file_size,通过这两个值,我们就可以进一步使用Table::Open打开文件了。

  Slice key() const {
    assert(Valid());
    return (*flist_)[index_]->largest.Encode();
  }
  Slice value() const {
    assert(Valid());
    EncodeFixed64(value_buf_, (*flist_)[index_]->number);
    EncodeFixed64(value_buf_+8, (*flist_)[index_]->file_size);
    return Slice(value_buf_, sizeof(value_buf_));
  }

5. leveldb::TwoLevelIterator

leveldb::TwoLevelIterator顾名思义,是由两层的 iterator 实现的。

class TwoLevelIterator : public Iterator {
  ...
private:
  ...
  BlockFunction block_function_;
  void* arg_;
  const ReadOptions options_;
  Status status_;
  IteratorWrapper index_iter_;
  IteratorWrapper data_iter_; // May be nullptr
  // If data_iter_ is non-null, then "data_block_handle_" holds the
  // "index_value" passed to block_function_ to create the data_iter_.
  std::string data_block_handle_;
}

第一层 index_iter_ 指向索引
第二层 data_iter_ 指向数据

TwoLevelIterator

5.1. Table读取

Iterator* Table::NewIterator(const ReadOptions& options) const {
  return NewTwoLevelIterator(
      //传入index_block的iterator
      rep_->index_block->NewIterator(rep_->options.comparator),
      &Table::BlockReader, const_cast<Table*>(this), options);
}

table的读取为例,说明下Seek接口下两层 iterator 移动的方式。

  // 先在 index block 找到第一个>= target 的k:v, v是某个data_block的size&offset
  index_iter_.Seek(target);
  // 根据v读取data_block,data_iter_指向该data_block内的k:v
  InitDataBlock();
  if (data_iter_.iter() != nullptr) data_iter_.Seek(target);
  SkipEmptyDataBlocksForward();

可以看到是两个 iterator 逐次 Seek 同一个 target 的过程。

InitDataBlock通过index_iter_.value()定位到数据块,使用注册的block_function_解析该数据块,并且返回一个Iterator,赋值到data_iter_

void TwoLevelIterator::InitDataBlock() {
  if (!index_iter_.Valid()) {
    SetDataIterator(nullptr);
  } else {
    Slice handle = index_iter_.value();
    if (data_iter_.iter() != nullptr && handle.compare(data_block_handle_) == 0) {
      // data_iter_ is already constructed with this iterator, so
      // no need to change anything
    } else {
      // 返回该data block对应的iterator
      Iterator* iter = (*block_function_)(arg_, options_, handle);
      // 记录block的size&offset
      data_block_handle_.assign(handle.data(), handle.size());
      SetDataIterator(iter);
    }
  }
}

void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
  if (data_iter_.iter() != nullptr) SaveError(data_iter_.status());
  data_iter_.Set(data_iter);
}

此时,data_iter_只是刚初始化与数据块关联,还未指向任何数据,data_iter_.Seek(target)后,”可能”指向了target

此时,就可以调用keyvalue接口来判断了(返回data_iter_.key()/value()):

  virtual Slice key() const {
    assert(Valid());
    return data_iter_.key();
  }
  virtual Slice value() const {
    assert(Valid());
    return data_iter_.value();
  }

two_level_iterator的设计,是单纯的二层 iterator 模型,实际上不止用于读取 table.

5.2. sst文件merge

考虑前面介绍的MergingIterator

MakeInputIterator

对 level 0,sstable files 之间数据是有 overlap 的,因此每次都需要判断current_指向哪个文件。

而对于 > 0 的 level,我们可以继续优化一些,因为 sstable files 之间数据是完全有序的,我们实际上可以用一个 iterator 来实现遍历。同时,先定位到文件,再定位到具体 key,也是一个二层 iterator 的模型。

        // Create concatenating iterator for the files from this level
        list[num++] = NewTwoLevelIterator(
            // 遍历文件列表的iterator
            new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
            &GetFileIterator, table_cache_, options);

第一层 iterator 就是前面介绍的Version::LevelFileNumIterator
第二层 iterator 由GetFileIterator返回,实际上就是用于 sstable 读取的TwoLevelIterator

6. 总结

可以看到 iterator 贯穿了整个 leveldb,memtable block sstable 等,而在 merge 时可以同时操作不同类型的 iterator,这种“神奇”效果的产生,就来源于对不同操作的抽象。