Compaction中的Iterator
一般来说，Compaction的Input涉及两层数据的合并，对于涉及到的每一层数据：
如果是level-0，对level-0的每一个sstable文件建立一个Iterator， 因为Level-0的sstable之间存在Overlap。
如果不是level-0，对该 level 的所有sstable文件建立一个TwoLevelIterator。
对于这个TwoLevelIterator：
first_level_iter_ : 表示该层所涉及到Compaction 的 file 元信息组成的 LevelFileNumIterator
second_level_iter_ : 表示当前所使用的数据 Block 构成的 Iterator
它们的组合将这一层所有sstable 的数据连接起来，构成了一个整体的 Iterator
这样，对于Compaction所用到的所有sstable文件，都建立了与之相关联的Iterator。最后将建立的所有Iterator合并，构成一个整体性的MergeIterator
以上为VersionSet::MakeInputIterator的操作过程
LevelFileNumIterator
LevelFileNumIterator的内容为该层所有文件的元信息：LevelFilesBrief，以下是 LevelFileNumIterator 中两个主要的函数实现：
Slice key() const override
{
assert(Valid());
return flevel_->files[index_].largest_key;
}
Slice value() const override
{
assert(Valid());
auto file_meta = flevel_->files[index_];
current_value_ = file_meta.fd;
return Slice(reinterpret_cast<const char*>(¤t_value_), sizeof(FileDescriptor));
}
key() : 表示的是当前index的sstable的largest_key
value() : 表示的是是个由当前sstable文件的FileDescriptor信息，即包含其file number 和 file size
TwoLevelIterator
TwoLevelIterator为一个两层结构的迭代器，其类成员包括两个IteratorWrapper：
IteratorWrapper first_level_iter_;
IteratorWrapper second_level_iter_;
上述的 LevelFileNumIterator 即为此处的 first_level_iter，当 TwoLevelIterator 初始化时，它会调用自身的 InitDataBlock() 函数：
void TwoLevelIterator::InitDataBlock()
{
if (!first_level_iter_.Valid())
{
SetSecondLevelIterator(nullptr);
}
else
{
Slice handle = first_level_iter_.value();
if (second_level_iter_.iter() != nullptr
&& !second_level_iter_.status().IsIncomplete()
&& handle.compare(data_block_handle_) == )
{
// second_level_iter is already constructed with this iterator, so
// no need to change anything
}
else
{
InternalIterator* iter = state_->NewSecondaryIterator(handle);
data_block_handle_.assign(handle.data(), handle.size());
SetSecondLevelIterator(iter);
}
}
InitDataBlock() 根据自身的 state 和 first_level_iter_.value()，构建第二层Iterator。
在Compaction过程中
InternalIterator* iter = state_->NewSecondaryIterator(handle);
实际调用的为:
InternalIterator* NewSecondaryIterator(const Slice& meta_handle) override
{
if (meta_handle.size() != sizeof(FileDescriptor))
{
return NewErrorInternalIterator(
Status::Corruption("FileReader invoked with unexpected value"));
}
const FileDescriptor* fd = reinterpret_cast<const FileDescriptor*>(meta_handle.data());
return table_cache_->NewIterator(read_options_, env_options_, icomparator_, *fd, range_del_agg_,
nullptr /* don't need reference to table */, file_read_hist_,
for_compaction_, nullptr /* arena */, skip_filters_, level_);
}
可以看出，实际调用的仍然为 TableCache::NewIterator()，根据某个sstable文件创建 InternalIterator
整体上来看，这个TwoLevelIterator内容为这一层的所有文件数据，
第一层Iterator：表示这一层所有文件的元信息
第二层Iterator：表示当前文件的数据信息
以下是TwoLevelIterator的Key-Value成员函数的代码，可以看出，它的Key-Value即表示当前sstable Iterator的当前Key-Value：
virtual Slice key() const override
{
assert(Valid());
return second_level_iter_.key();
}
virtual Slice value() const override
{
assert(Valid());
return second_level_iter_.value();
}
Next() 操作定位下一个Key-Value，如果当前Block已结束，second_level_iter_移动到下一个Block
void TwoLevelIterator::Next()
{
assert(Valid());
second_level_iter_.Next();
SkipEmptyDataBlocksForward();
}
void TwoLevelIterator::SkipEmptyDataBlocksForward()
{
while (second_level_iter_.iter() == nullptr
|| (!second_level_iter_.Valid() && !second_level_iter_.status().IsIncomplete()))
{
// Move to next block
if (!first_level_iter_.Valid())
{
SetSecondLevelIterator(nullptr);
return;
}
first_level_iter_.Next();
InitDataBlock();
if (second_level_iter_.iter() != nullptr)
{
second_level_iter_.SeekToFirst();
}
}
}
MergingIterator
MergingIterator 关键的成员变量如下：
const Comparator* comparator_; IteratorWrapper* current_; autovector<IteratorWrapper, kNumIterReserve> children_; MergerMinIterHeap minHeap_; std::unique_ptr<MergerMaxIterHeap> maxHeap_;
从结构上来说，一个MergingIterator由一多个children_组成，每一个child也是一个Iterator，所有的子迭代器通过堆的数据结构组织，包括一个最小堆和一个最大堆。
最小堆，是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左孩子和右孩子节点的值 ——摘自百度百科
MergingIterator的Key和Value成员函数均返回的是当前子迭代器 current_ 的Key与Value：
virtual Slice key() const override
{
assert(Valid());
return current_->key();
}
virtual Slice value() const override
{
assert(Valid());
return current_->value();
}
current_ 默认为堆顶的child，即表示数值最小的child。在Compaction过程中，这些children表示的是某一个sstable（level-0层）或者某一层sstable数据。
对于MergingIterator的迭代过程，以下是Next() 成员函数的部分节选：
virtual void Next() override
{
current_->Next();
if (current_->Valid())
{
minHeap_.replace_top(current_);
}
else
{
minHeap_.pop();
}
current_ = CurrentForward();
}
MergingIterator的Next一般来说表示的就是current_的Next，但是当current_迭代结束之后，就会取下一个child作为current。
从Compaction的角度来说，也就是MergingIterator的Next操作也就是涉及到所有sstable数据中，Key从小到大顺序遍历的过程（direction=kForward）
