概述

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。