概述

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

Iterator的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 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。

    ​