RocksDB Iterator
??RocksDB Iterator提供用戶以有序的方式前向或者后向遍歷DB泌参，也可以seek 到DB的特定key上霎桅。為了做到這樣旅择，Iterator必須以有序流的方式訪問DB宣赔。RocksDB Iterator的實(shí)現(xiàn)類命名為DBIter预麸。
DBIter
- Implementation: db/db_iter.cc
- Interface: Iterator
??DBIter是InternalIterator的封裝。DBIter的任務(wù)就是解析由InternalIterator 暴露出來的InternalKeys儒将，最后以u(píng)ser key的形式展現(xiàn)吏祸。
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 是一個(gè)Iterators堆钩蚊。在MergingIterator 中贡翘，我們把所有的child Iterator放進(jìn)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的封裝诱渤，內(nèi)存表實(shí)現(xiàn)自己Iterator都是以keys/values的有序流的形式暴露丐巫。
BlockIter
- Implementation:table/block.h
- Interface: InternalIterator
這個(gè)Iterator用來從SST file中讀取blocks，與blocks是Index blocks或者data block是無關(guān)勺美。由于递胧，SST file blocks是有序的且不可更變的，所以我們可以load block數(shù)據(jù)到memory總赡茸，然后為這個(gè)有序的數(shù)據(jù)創(chuàng)建一個(gè)BlockIter缎脾。
TwoLevelIterator
- Implementation: table/two_level_iterator.cc
- Interface: InternalIterator
一個(gè)TwoLevelIterator 包含兩個(gè)Iterators
- First level Iterator (first_level_iter_)
- Second level Iterator (second_level_iter_)
first_level_iter_用來計(jì)算出接下來要使用的second_level_iter_，second_level_iter_指向我們要讀取的實(shí)際數(shù)據(jù)占卧。
Example:
RocksDB使用TwoLevelIterator 來讀取SST file遗菠，first_level_iter_ 是SST File Index block上的BlockIter联喘，second_level_iter_ 是Data Block上的BlockIter。
下面看一個(gè)簡單的SST file辙纬，有4個(gè)Data blocks和1個(gè)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
要想讀這個(gè)file豁遭，我們要?jiǎng)?chuàng)建一個(gè)TwoLevelIterator
- first_level_iter_ => BlockIter over Index block
- second_level_iter_ => BlockIter over Data block that will be determined by first_level_iter_
當(dāng)通過TwoLevelIterator seek到KEY8時(shí)，首先使用first_level_iter_ (BlockIter over Index block)計(jì)算出哪個(gè)block可能包含這個(gè)key贺拣，結(jié)果是設(shè)置second_level_iter_ to be (BlockIter over data block with offset 0x0250)蓖谢。然后我們使用second_level_iter_ 在data block中讀取key &value
