Raven's Blog

zhang.xingrui@foxmail.com

0%

leveldb源码阅读记录-TwoLevelIterator

发表于 分类于

TwoLevelIterator是用来访问可用 index域和 data域访问的数据。

如，sstable中的data block和index block。就是分别将index block的block iter和data block的block iter赋值给index iter和data iter.

0. TwoLevelIterator内部成员·

1
2
3
4
5
6
7
8
9
10
11
12
13
class TwoLevelIterator : public Iterator {
 ...

  BlockFunction block_function_;
  void* arg_;
  const ReadOptions options_;
  Status status_;
  IteratorWrapper index_iter_;	// 两个iter warpper， 
  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_;
};

注意到TwoLevelIterator中的成员函数主要包括， block_function_, index_iter和data_iter_. 后面两个iter是一个包装类，主要提供了cache策略，减少由于虚函数调用带来的开销。

1. 创建一个TwoLevelIterator·

1
2
3
4
5
Iterator* NewTwoLevelIterator(Iterator* index_iter,
                              BlockFunction block_function, void* arg,
                              const ReadOptions& options) {
    return new TwoLevelIterator(index_iter, block_function, arg, options);
}

一个实际调用的例子（这部分VersionSet::MakeInputIterator中，实际上这个函数是在DoCompaction过程中被调用）：

1
2
3
list[num++] = NewTwoLevelIterator(
         new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
         &GetFileIterator, table_cache_, options);
  • index_iter等于我们上篇文章中说的LevelFileNumIterator。
  • block_function = GetFileIterator
  • table_cache_，options，作为block_function的参数

2. Seek·

1
2
3
4
5
6
void TwoLevelIterator::Seek(const Slice& target) {
      index_iter_.Seek(target);
      InitDataBlock();
      if (data_iter_.iter() != nullptr) data_iter_.Seek(target);
      SkipEmptyDataBlocksForward();
}

首先将index_iter定位到target。

InitDataBlock·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TwoLevelIterator::InitDataBlock() {
  if (!index_iter_.Valid()) {
    SetDataIterator(nullptr);
  } else {
     // handle = 文件序列号和文件size
    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 {
      Iterator* iter = (*block_function_)(arg_, options_, handle);
      data_block_handle_.assign(handle.data(), handle.size());
      SetDataIterator(iter);
    }
  }
}

首次调用InitiDataBlock，会走到:

1
2
3
Iterator* iter = (*block_function_)(arg_, options_, handle);
data_block_handle_.assign(handle.data(), handle.size());
SetDataIterator(iter);

以下面的例子来说明这个创建过程。

1
2
3
list[num++] = NewTwoLevelIterator(
           new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
           &GetFileIterator, table_cache_, options);
  • block_function_是GetFileIterator
  • arg_ = table_cache_
  • options_ = ReadOptions
  • handle = 文件序列号和文件size

现在深入到GetFileIterator中：

1
2
3
4
5
6
7
8
9
10
11
12
13
static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
                                 const Slice& file_value) {
   // 强转为table cache
  TableCache* cache = reinterpret_cast<TableCache*>(arg);
  if (file_value.size() != 16) {
    return NewErrorIterator(
        Status::Corruption("FileReader invoked with unexpected value"));
  } else {
      // 根据file number和file size ，构造一个cache iterator
    return cache->NewIterator(options, DecodeFixed64(file_value.data()),
                              DecodeFixed64(file_value.data() + 8));
  }
}

到这里可以得到结论， TwoLevelIterator由两个iterator组成，一个是LevelFileNumIterator， 用于提供数据索引需要的元信息。另一个是cache iterator, 用于实际访问数据。

注意：这里LevelFileNumIterator和Table Iterator实际上又会被IteratorWrapper warp起来。（上文也提到了）。

上一篇文章已经说过了LevelFileNumIterator, 之后再说说Table Iterator

3. Next & Prev·

一旦有了data_iter， next和prev就简单了。

1
2
3
4
5
6
7
8
9
10
11
12
void TwoLevelIterator::Next() {
  assert(Valid());
  data_iter_.Next();
   // 跳过empty data block
  SkipEmptyDataBlocksForward();
}

void TwoLevelIterator::Prev() {
  assert(Valid());
  data_iter_.Prev();
  SkipEmptyDataBlocksBackward();
}

ok,其余几个seek操作都比较简单。

4. key & value·

1
2
3
4
5
6
7
8
Slice key() const override {
   assert(Valid());
   return data_iter_.key();
 }
 Slice value() const override {
   assert(Valid());
   return data_iter_.value();
 }

5. TwolevelIterator总结·

TwoLevelIterator是一种组合的Iterator，其内部由两个iter组成：index_iter和data_iter. index_iter用于索引，它包含了用来创建data_iter的元数据，实际上真实的key value存放在data_iter中。 在TwolevelIterator的各个seek操作中，都是先由index_iter找到合适的位置（索引），得到用来创建data_iter的元数据（sstable的file number和file size), 然后创建data_iter, 最终data_iter才seek到真实数据的位置。

6. TwolevelIterator的应用–Table::Iterator·

之前通过Compaction过程中用到的iterator介绍了TwoleveIIterator。现在用Table的Iterator来进一步理解TwolevelIterator。先看看入口：

1
2
3
4
5
Iterator* Table::NewIterator(const ReadOptions& options) const {
  return NewTwoLevelIterator(
      rep_->index_block->NewIterator(rep_->options.comparator),	// index iter
      &Table::BlockReader, const_cast<Table*>(this), options);	// data iter
}

首先分析用来创建index iter的Block::NewIterator:

1
2
3
4
5
6
7
8
9
10
11
Iterator* Block::NewIterator(const Comparator* comparator) {
  if (size_ < sizeof(uint32_t)) {
    return NewErrorIterator(Status::Corruption("bad block contents"));
  }
  const uint32_t num_restarts = NumRestarts();
  if (num_restarts == 0) {
    return NewEmptyIterator();
  } else { // 正常情况下会走到这里
    return new Iter(comparator, data_, restart_offset_, num_restarts);
  }
}

从这里可以看到index iter本质上就是一个Block::Iter, 是用来遍历index_block. 我们曾在SSTable章节中说过，index_block和data_block采用完全相同的结构。所以可以用Block::Iter进行遍历。

现在，看TwoLevelIterator的data iter部分，data iter主要由NewTwoLevelIterator参数中 &Table::BlockReader, const_cast<Table*>(this), options构成。在TwoLevelIterator::InitDataBlock函数中会初始化data iter:

1
Iterator* iter = (*block_function_)(arg_, options_, handle);

此时：

  • block_function_ = BlockReader
  • arg_ = const_cast<Table*>(this)
  • options_ = options
  • handle = index_iter->value(), 即index_block的value，也即index_block对应data_block的block_handle(offset和size）。

再看BlockReader：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Convert an index iterator value (i.e., an encoded BlockHandle)
// into an iterator over the contents of the corresponding block.
Iterator* Table::BlockReader(void* arg, const ReadOptions& options,
                             const Slice& index_value) {
 
    // 这里省略的代码的工作为，根据index_value(即data_block位置信息)从block_cache中获取block
   ...


  Iterator* iter;
  if (block != nullptr) {
     // 创建Block::Iter
    iter = block->NewIterator(table->rep_->options.comparator);
    ...
  }
  return iter;
}

丛这里可以看到，BlockReader返回的也是一个Block::Iter，所以这个TwoleveIIterator的data iter就是data block的Block::Iter.

总结·

Table的Iter，是一个TwoLevelIterator，这个Iterator由index iter和data iter组成。 index iter为Block::iter, datablock iter也为Block::Iter.

文章对你有帮助?打赏一下作者吧