关于rocksdb:RocksDB剖析系列-Iterator

参考：

• https://github.com/facebook/r…
• https://github.com/facebook/r…
• https://blog.csdn.net/Z_Stand…
• https://www.jianshu.com/p/f57…
• https://book.tidb.io/session3…
• https://www.iggiewang.cn/2021…

Introduction

RocksDB 的 Iterator 在通过高度封装后，能够像 C ++ stl 库为每一个容器结构的迭代器的 iterator 一样被应用，它能够定位到某个 key，并能够从这个 key 开始进行 scan，它也能够被用来进行反向 scan。

如果在创立迭代器时，ReadOptions.snapshot 被给定，迭代器将返回该 snapshot 的数据，如果传入的为 nullptr，隐性视图将被创立，隐性视图不能转为显性。

用户对 Iterator 的应用

• NewIterator 创立一个迭代器，须要传入 ReadOptions
• Seek 查找一个 key
• SeekToFirst 迭代器挪动到 db 的第一个 key 地位，个别用于程序遍历整个 db 的所有 key
• SeekToLast 迭代器挪动到 db 的最初一个 key 地位，个别用于反向遍历整个 db 的所有 key
• SeekForPrev 挪动到以后 key 的上一个地位，个别用于遍历 (limit, start] 之间的 key
• Next 迭代器挪动到下一个 key
• Prev 迭代器挪动到上一个 key

Iterator::status()能够返回以后迭代器的 error。error 蕴含 IO error，checksum 不匹配，外部谬误等 …

如果没有谬误，状态为 Status::OK()。如果 Iterator::Valid()是 true，status 必定为 OK。
而如果 Iterator::Valid()为 false，可能是因为此时迭代器走到了数据的开端，这种状况 status 是 OK；也有可能是呈现了谬误，这种状况 status 不是 OK。

5.13.x 或更早的版本中，这两个 API 会有不同，须要再查阅文档。

各 Iterator

DBIter

Implementation: db/db_iter.cc

Interface: Iterator

DBIter 是对 InternalIterator 的封装，它的工作次要是将 Internal key 解析成 user key，并展现进去

Example

底层的 InternalIterator 中

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 将 Internal Key 解析为 User Key，并裸露接口给用户

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

MergingIterator

Implementation: table/merging_iterator.cc

Interface: InternalIterator

MergingIterator 由很多 Children Iterator 组成

autovector<IteratorWrapper, kNumIterReserve> children_;

MergingIterator 会将这些 Children Iterator 放入堆中，并向下层有序地展现。

Example

children iterator 为：

= 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 将所有 children iterator 放入堆中，使其有序

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

用作对 Memtable 的迭代器，每个 memtable 实现了他们本人的迭代器，来对外界暴露出有序可迭代的 kv 对

BlockIter

Implementation: table/block_based/block.h

Interface: InternalIterator

该迭代器用于从 SST File 中读取 block，无论这些 block 是 index block 还是 data block 或是 meta block（DataBlockIter、IndexBlockIter、MetaBlockIter 继承了 BlockIter）。因为 SST 文件块是有序且不可变的，因而咱们将该块加载到内存中，并为此排序后的数据创立一个 BlockIter。

TwoLevelIterator

Implementation: table/two_level_iterator.cc

Interface: InternalIterator

一个 TwoLevelIterator 由两个迭代器组成

• first_level_iter_
• second_level_iter_

first_level_iter_ 用来找到应用哪个 second_level_iter_ , 而后 second_level_iter_ 指向理论须要读的数据

Example

RocksDB 应用 TwoLevelIterator 来读取 SST files, first_level_iter_ 是对于 Index block 的 BlockIter，second_level_iter_ 是对于 Data block 的 BlockIter.

[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

first_level_iter_ => BlockIter over Index block
second_level_iter_ => BlockIter over Data block，将被 first_level_iter_决定指向哪个
当应用 TwoLevelIterator 来 seek KEY8 时，首先应用 first_level_iter_ seek 到对应的 data block（0x0250），而后应用 second_level_iter_来 seek 具体的 key。

读取 Data Block 时，若 Block 在 Block Cache 当中，间接返回对象地址，否则，产生磁盘 IO，读取 SST 的 Block，结构 Block 对象并缓存其地址在 Block Cache 中。