本文出自组内小伙伴

RocksDB iterator 允许用户遍历整个数据库，本文主要介绍 iterator 整体结构，如何实现seek，如何实现next等。介绍的顺序如下：

1. RocksDB iterator 类层次关系，iterator 架构。用于建立整体认识。
2. seek、next的实现。seek用于进行等值查询或寻找区间的上下限，next用于获取某个范围内的下一条数据；

Iterator 类之间的关系

介绍RocksDB 如何实现遍历整个数据库之前，有必要讲清楚实现迭代器的类，提供一个清晰的iterator 类之间的关系图便于后面的seek、next实现的分析，因为RocksDB iterator实现的逻辑是很复杂的。

通常使用 iterator 的方式如下：

rocksdb::Iterator* it = db->NewIterator(rocksdb::ReadOptions());
  for (it->SeekToFirst(); it->Valid(); it->Next()) {
    cout << it->key().ToString() << ": " << it->value().ToString() << endl;
  }
  assert(it->status().ok()); // Check for any errors found during the scan
  delete it;

NewIterator()函数会创建一个迭代器，我会先讲一下该函数的实现，目的是引出后面seek或者next可能会用到的各种iterator，最后给出一个iterator的框架图，有了整体的结构，后面分析seek或者next的实现会容易很多。

上面的代码是准备创建 iterator的代码，可以看到有传入snapshot，实际创建迭代器的工作在NewIteratorImpl中完成，代码如下：

函数最后返回的是ArenaWrappedDBIter 类型的迭代器，根据类名可以判断出这只是一个包装类，其内部包含了DBIter和Arena：

DBIter 其实是 iterator 体系最上层的迭代器，NewArenaWrappedDbIterator函数的任务就是创建DBIter类型的对象并赋值给 db_iter_, 该对象的创建以及后续迭代器对象的创建都是使用Arean进行内存分配，保证这些迭代器对象在连续的内存空间中，这样缓存友好。现在DBIter类型的迭代器创建完成了。

NewInternalIterator 又是创建了什么迭代器呢？我们进入函数看看：

代码的注释解释的还是很清楚的，首先是一个MergeIteratorBuilder类型的对象，看后面的代码该对象是把其他iterator加入到MergingIterator内部。代码1 是创建了 mutable mem iterator，其实就是当前column family 活跃的memtable；代码2 是创建了all immutable memtables iterators，即column family 目前所有的immutable memtable分别创建了iterator。代码3 是创建磁盘上L0至LN层的迭代器，代码3要展开讲因为L0和其它层的处理是不一样的。

可以看到这里对于非空的level会逐层创建iterator，进入AddIteratorsForLevel:

如果是L0层，每个文件都必须创建iterator，因为L0层SST文件之间key可能会重叠。cfd_->table_cache()->NewIterator(…)创建的迭代器是TwoLevelIterator, TwoLevelIterator 类内部包含 first_level_iter_ 迭代器和 second_levle_iter_ 迭代器，对于Level0 来说，fiter_level_iter_是 BlockIter类型的迭代器，用来遍历SST文件的index block，second_level_iter_也是BlockIter类型的迭代器，负责遍历SST文件的data block。

如果不是L0层，则没有必要为每个文件都创建iterator，因为文件之间key有序且不重叠的。代码如上所示，非L0层创建的也是 TwoLevelIterator类型的迭代器，但是first_levle_iter_ 的类型是LevelFileNumIterator，负责该层文件的遍历。那second_level_iter_是什么类型的。可以猜想second_level_iter_应该是在文件内部遍历的，L0层在文件内部遍历创建的是TwoLevelIterator，非L0层也一样，因为SST文件结构都是一样的。所以非L0层的TwoLevelIterator的second_level_iter_ 还是一个TwoLevelIterator。

mutable memtable、 immutable memtbale、L0~LN 这些迭代器都创建完之后，统统加入到MergingIterator对象中, 回到创建迭代器代码刚开始的地方：

代码1处创建了DBIter对象，代码2处创建了MergingIterator对象，其中DBIter对象包含MergingIterator对象。整个iterator的结构脑海中应该也有了吧，上一幅图总结一下：

seek、next实现

本节 seek、next的实现主要聚焦在SST文件上，MyRocks 中查找还要考虑transaction 中的writebatch，本节也忽略。

直接进入DBIter::Seek函数一探究竟：

target 便是用户指定要seek的key, 代码1处是将user_key转换成InternalKey，IntenalIterator类型的迭代器处理的都是InternalKey类型的key, 代码2处调用了MergingIterator::Seek函数，代码3处解析MergingIterator::Seek到的InternalKey返回给用户user_key。

我们先从代码2处分析，

MergingIterator::Seek 调用每个child iterator的Seek函数，第1小节已经介绍过其包含哪些child iterator了。非L0层的Seek 其实与db->Get()类似，根据key 先利用LevelFileNumIterator迭代器定位出key可能在哪个文件，然后TwoLevelIterator的first_level_iter定位到可以在哪个data block，second_level_iter定位key在data block中的具体位置。

每次child.Seek(target)执行完之后，child iterator都会加入到最小堆中(minheap_)，其中minHeap_.push(&child)函数内部会维持最小堆的性质，所有child Seek完之后返回堆顶的iterator： current_=CurrentForward()。

MergingIterator 内部维护了一个最小堆，所有child iterator在MergingIterator内部是有序的，举一个例子：

InternalKey(user_key="Key1", seqno=10, Type=Put)    | Value = "KEY1_VAL2"
InternalKey(user_key="Key1", seqno=9,  Type=Put)    | Value = "KEY1_VAL1"
InternalKey(user_key="Key2", seqno=16, Type=Put)    | Value = "KEY2_VAL2"
InternalKey(user_key="Key2", seqno=15, Type=Delete) | Value = "KEY2_VAL1"
InternalKey(user_key="Key3", seqno=7,  Type=Delete) | Value = "KEY3_VAL1"
InternalKey(user_key="Key4", seqno=5,  Type=Put)    | Value = "KEY4_VAL1"

上面是child iterator seek完之后，最小堆中的元素，相同key，seq大的排在前面，同时也不会过滤type=delete类型的key，多版本的过滤、type=delete的过滤、seqno大于当前快照的过滤都在DBIter 层完成，上面的例子经过DBIter过滤后如下：

Key="Key1"  | Value = "KEY1_VAL2"
Key="Key2"  | Value = "KEY2_VAL2"
Key="Key4"  | Value = "KEY4_VAL1"

DBIter完成此工作的函数就是FindNextUserEntry,也就是上面DBIter::Seek函数中的代码3处，该函数从MergingIterator 的最小堆的堆顶处理，返回一个有效的user key-value，该函数的逻辑流程如下所示

该函数确保用户看到的key-value 是有效的。

Seek的实现介绍到此，下面介绍Next 的实现，DBIter::Next函数代码如下：

direction_ 这里是kForward，所以逻辑调用iter_->Next()，即MergingIterator::Next()函数，它的处理逻辑如下：

current_ 即堆顶的child iterator,其他child iterator不动，原理类似于多路归并排序，每次是最小的那一路移动。以Level1 为例，因为seek操作已经定位到了data block， 所以Next操作继续在该data block 里操作，直接解析下一个key-value就可以了，

如果到了data block的末尾就利用BlockIter(index block)移动到当前data block 后面的block，如果是当前文件已经遍历完了，则利用LevelFileNumIterator::Next移动到下一个文件，代码如下，只是增加索引下标即可。

current_->Next()操作介绍后，MergingIterator要重新调整堆保持最小堆的性质。MergingIterator::Next操作完之后，回到DBIter::Next，还是需要调用FindNextUserEntry过滤key,主要注意的地方是第一个参数是true了，在seek的时候第一个参数是false，true的目的是跳过相同key的旧版本，其他逻辑同上面的流程图一致。

非L0层存在两个嵌套的TwoLevelIterator，代码分析时这部分代码可能比较绕，结合第一小节的类关系图会有所帮助。

总结

本文主要介绍了RocksDB 迭代器的整体结构，Seek、Next的实现细节，Iterator模块整体代码量很多，且有些逻辑比较烧脑，需慢慢品味其设计的巧妙之处。迭代器在整个RocksDB架构中位置很重要，本文并没有覆盖所有细节，也没有介绍与其交叉的模块，其他模块留在其他文章再介绍。