RocksDB系列十九：Iterator Implementat
RocksDB Iterator
RocksDB Iterator提供用户以有序的方式前向或者后向遍历DB，也可以seek 到DB的特定key上。为了做到这样，Iterator必须以有序流的方式访问DB。RocksDB Iterator的实现类命名为DBIter。
DBIter
- Implementation: db/db_iter.cc
- Interface: Iterator
DBIter是InternalIterator的封装。DBIter的任务就是解析由InternalIterator 暴露出来的InternalKeys，最后以user key的形式展现。
Example：
The underlying InternalIterator exposed
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"
But what DBIter will expose to the user is
Key="Key1" | Value = "KEY1_VAL2"
Key="Key2" | Value = "KEY2_VAL2"
Key="Key4" | Value = "KEY4_VAL1"
MergingIterator
- implementation: table/merging_iterator.cc
- Interface: InternalIterator
MergingIterator 包括很多 child iterators，MergingIterator 是一个Iterators堆。在MergingIterator 中，我们把所有的child Iterator放进heap中，以一种有序的流形式暴露。
Example：
The underlying child Iterators exposed：
= 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 将所有的child Iterators 放到堆中，以有序流的形式暴露。
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
- Implementation: db/memtable.cc
- Interface: InternalIterator
MemtableIterator是MemtableRep::Iterator的封装，内存表实现自己Iterator都是以keys/values的有序流的形式暴露。
BlockIter
- Implementation:table/block.h
- Interface: InternalIterator
这个Iterator用来从SST file中读取blocks，与blocks是Index blocks或者data block是无关。由于，SST file blocks是有序的且不可更变的，所以我们可以load block数据到memory总，然后为这个有序的数据创建一个BlockIter。
TwoLevelIterator
- Implementation: table/two_level_iterator.cc
- Interface: InternalIterator
一个TwoLevelIterator 包含两个Iterators
- First level Iterator (first_level_iter_)
- Second level Iterator (second_level_iter_)
first_level_iter_用来计算出接下来要使用的second_level_iter_，second_level_iter_指向我们要读取的实际数据。
Example:
RocksDB使用TwoLevelIterator 来读取SST file，first_level_iter_ 是SST File Index block上的BlockIter，second_level_iter_ 是Data Block上的BlockIter。
下面看一个简单的SST file，有4个Data blocks和1个Index Block
[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
要想读这个file，我们要创建一个TwoLevelIterator
- first_level_iter_ => BlockIter over Index block
- second_level_iter_ => BlockIter over Data block that will be determined by first_level_iter_
当通过TwoLevelIterator seek到KEY8时，首先使用first_level_iter_ (BlockIter over Index block)计算出哪个block可能包含这个key，结果是设置second_level_iter_ to be (BlockIter over data block with offset 0x0250)。然后我们使用second_level_iter_ 在data block中读取key &value
