迭代器实现

RocksDB 迭代器

RocksDB迭代器允许用户以排序的方式向前和向后遍历数据库。它也有能力在数据库中寻找一个特定的键，以实现这一点。迭代器需要以已排序的流的形式访问数据库。RocksDB迭代器实现类被命名为DBIter，在这个wiki页面中，我们将讨论DBIter是如何工作的以及它是由什么组成的。在下面的图中，您可以看到DBIter的设计及其组成。

https://s9.postimg.org/h8c9jz0zz/Screen_Shot_2016_08_09_at_5_21_47_PM.png

DBIter

| 实现: db/db_iter.cc (https://github.com/facebook/rocksdb/blob/master/db/db_iter.cc)
| 实现: iterator (https://github.com/facebook/rocksdb/blob/master/include/rocksdb/iterator.h)

DBIter 是一个内部迭代器(在本例中是一个合并迭代器)的包装器。 DBIter 的工作是解析底层内部迭代器公开的内部键，并将它们公开为用户键。

例子:

公开底层内部迭代器

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"

但是DBIter将向用户展示的是什么

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

MergingIterator

| 实现: table/merging_iterator.cc (https://github.com/facebook/rocksdb/blob/master/table/merging_iterator.cc)
| 实现: InternalIterator (https://github.com/facebook/rocksdb/blob/master/table/internal_iterator.h)

MergingIterator由许多子迭代器组成，基本上是迭代器的堆。在MergingIterator中，我们将所有子迭代器放在一个堆中，并将它们作为一个排序的流公开。

例子:

公开了底层子迭代器

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

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"

MemtableIterator

| 实现: db/memtable.cc ( https://github.com/facebook/rocksdb/blob/master/db/memtable.cc )
| 实现: InternalIterator ( https://github.com/facebook/rocksdb/blob/master/table/internal_iterator.h )

这是一个围绕MemtableRep::Iterator的包装器，每个memtable表示都实现它自己的迭代器，以将memtable中的键/值作为排序的流公开

BlockIter

| 实现: table/block.h ( https://github.com/facebook/rocksdb/blob/master/table/block.h )
| 实现: InternalIterator ( https://github.com/facebook/rocksdb/blob/master/table/internal_iterator.h )

这个迭代器用于从SST文件中读取块，无论这些块是索引块还是数据块。由于SST文件块是排序的和不可变的，所以我们将该块加载到内存中，并为这个排序的数据创建一个BlockIter。

TwoLevelIterator

| 实现: table/two_level_iterator.cc ( https://github.com/facebook/rocksdb/blob/master/table/two_level_iterator.cc )
| 实现: InternalIterator ( https://github.com/facebook/rocksdb/blob/master/table/internal_iterator.h )

一个双迭代器由两个迭代器组成

第一级迭代器(firstlevel_iter)
第二级迭代器(secondlevel_iter)

firstlevel_iter用于计算要使用的secondlevel_iter， secondlevel_iter指向我们正在读取的实际数据。

例子:

RocksDB使用两个oleveliterator来读取SST文件，firstlevel_iter是SST文件索引块上的BlockIter, secondlevel_iter是数据块上的BlockIter。

让我们看看这个SST文件的简化表示，我们有4个数据块和1个索引块

[Data block, offset: 0x0000]
KEY1  | VALUE1
KEY2  | VALUE2
KEY3  | VALUE3
[Data Block, offset: 0x0100]
KEY4  | VALUE4
KEY7  | VALUE7
[Data Block, offset: 0x0250]
KEY8  | VALUE8
KEY9  | VALUE9
[Data Block, offset: 0x0350]
KEY11 | VALUE11
KEY15 | VALUE15
[Index Block, offset: 0x0500]
KEY3  | 0x0000
KEY7  | 0x0100
KEY9  | 0x0250
KEY15 | 0x0500

要读取这个文件，我们将创建一个TwoLevelIterator

firstlevel_iter => BlockIter 在索引块 secondlevel_iter => BlockIter 将由firstlevel_iter确定的数据块上

例如，当我们要求我们的TwoLevelIterator查找KEY8时，它将首先使用firstlevel_iter(索引块上的BlockIter)来确定哪个块可能包含这个键。这将导致我们将secondlevel_iter设置为(BlockIter over data block with offset 0x0250)。然后，我们将使用secondlevel_iter来查找数据块中的键和值。