RocksDB 的 Iterator

概述

RocksDB的数据主要存储在三个部分：Memtable，Immutable Memtable和SST文件，当用户需要遍历整个数据集合时，RocksDB提供了Iterator的接口解决这个问题。

Iterator的结构

  // Try to generate a DB iterator tree in continuous memory area to be
  // cache friendly. Here is an example of result:
  // +-------------------------------+
  // |                               |
  // | ArenaWrappedDBIter            |
  // |  +                            |
  // |  +---> Inner Iterator   ------------+
  // |  |                            |     |
  // |  |    +-- -- -- -- -- -- -- --+     |
  // |  +--- | Arena                 |     |
  // |       |                       |     |
  // |          Allocated Memory:    |     |
  // |       |   +-------------------+     |
  // |       |   | DBIter            | <---+
  // |           |  +                |
  // |       |   |  +-> iter_  ------------+
  // |       |   |                   |     |
  // |       |   +-------------------+     |
  // |       |   | MergingIterator   | <---+
  // |           |  +                |
  // |       |   |  +->child iter1  ------------+
  // |       |   |  |                |          |
  // |           |  +->child iter2  ----------+ |
  // |       |   |  |                |        | |
  // |       |   |  +->child iter3  --------+ | |
  // |           |                   |      | | |
  // |       |   +-------------------+      | | |
  // |       |   | Iterator1         | <--------+
  // |       |   +-------------------+      | |
  // |       |   | Iterator2         | <------+
  // |       |   +-------------------+      |
  // |       |   | Iterator3         | <----+
  // |       |   +-------------------+
  // |       |                       |
  // +-------+-----------------------+
  //
  // ArenaWrappedDBIter inlines an arena area where all the iterators in
  // the iterator tree are allocated in the order of being accessed when
  // querying.
  // Laying out the iterators in the order of being accessed makes it more
  // likely that any iterator pointer is close to the iterator it points to so
  // that they are likely to be in the same cache line and/or page.

RocksDB为所有的子Iterator申请连续的内存，目的是所有的Iterator指针距离更近，尽可能的在相同的Cache Line，这样迭代起来速度更快。

其中IternalIterator就是具体使用的Iterator: 它的具体实现就是依次从RocksDB里的三个数据存储部分Memtable, Immutable Memtable和SSTtable文件创建Iterator，下面解释一下具体关于数据存储部分的Iterator:

MemtableIterator：Memtable和Immutable Memtable的Iterator：

以默认的Memtable的数据结构SkipList来举例，就是SkipList暴露的Iterator接口。Iterator的 Next() 迭代也就是SkipList的第0层迭代
TwoLevelIterator：SSTable文件的Iterator
- Level-0层:
  
  因为Level-0层有重叠的数据，所以每个文件的Iterator都需要作为一个单独的Iterator被添加
- 非Level-0层:
  
  迭代该层级的所有文件，因为是不重叠的，所以简单的顺序迭代就可以。
- TwoLevelIterator 封装了SSTable中Block的Index Iterator和Data Iterator，根据Index定位到具体的Data:
  - 首先通过 index_iter_->Seek(target) 得到 index_iter_ 的Value，即Key所在的Data的索引信息
  - 定位到具体的Data之后，调用 data_block_iter_->Seek(target)，定位到需要查找的Key

Iterator结构梳理

结合上面的结构图和解释，我们可以梳理RocksDB的Iterator结构：

数据的Iterator：

包括 MemtableIterator, BlockIterator, TwoLevelIterator
合并后的Iterator：

每个数据的Iterator内部是有序的，MergingIterator 负责将这些收集的数据Iterator合并，返回一个完整的所有数据有序的Iterator，MergeingIterator 包含所有的Iterator。
DBIter 的构造过程:

对DB遍历时，获取整个DB内部的Iteraror，然后封装成DBIterator
- 获得Memtable的Iterator
- 获得Immutable memtable的Iterator
- 获得整个SSTable的Iterator
  - Level-0中所有的SSTable的Iterator
  - 非Level-0的层级上的SSTable的Iterator集合
  - 将获得的所有Iterator作为 child iter 构造 MergingIterator
- 构造DBIterator

Iterator使用的一个子问题

Iterator遍历的是什么时间节点的数据？

Iterator是迭代某一个快照的数据，将快照的 read_options.snapshot->GetSequenceNumber() 作为SequenceNumber。如果没有指定快照，则将 versions_->LastSequence() 设为SequnceNumber。