RocksDB 迭代器¶
RocksDB 迭代器允许用户以一个排序好的顺序向后或者向前遍历 db。它还拥有查找 DB 中的一个特定 key 的功能,为此,迭代器需要以一个排序好的流来访问 DB。RocksDB 迭代器实现类名为 DBIter,在这个 wiki 页,我们会讨论 DBIter 是如何工作的,以及他的构成。在下面的图片,你可以看到 DBIter 的设计和构成。
DBIter¶
实现: db/db_iter.cc 接口: Iterator
DBIter 是 InternalIterator(在这里是 MergingIterator)的一个封装。DBIter 的工作是解析 InternalIterator 返回的 InternalKeys,然后把它们解开成用户 key。
例子:
底层 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 导出给用户的是
Key="Key1" | Value = "KEY1_VAL2"
Key="Key2" | Value = "KEY2_VAL2"
Key="Key4" | Value = "KEY4_VAL1"
MergingIterator¶
MergingIterator 由非常多的子迭代器组成,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
这是一个 MemtableRep::Iterator 的封装,每一个 memtable 分别实现自己的迭代器以导出 memtable 自己的 kv 排序流数据。
BlockIter¶
这个迭代器被用于读取 SST 文件的块,不管这些块是索引块还是数据块。由于 SST 文件块都是排序好的,并且不可变得,我们把这个块的数据加载到内存然后为排序好的数据创建一个 BlockIter
TwoLevelIterator¶
实现:table/two_level_iterator.cc
一个 TwoLevelIterator 由两个迭代器构成:
- 第一层迭代器 (first_level_iter_)
- 第二层迭代器 (second_level_iter_)
first_level_iter_ 被用于找出需要使用的 second_level_iter_,second_level_iter_ 指向实际读取的数据。
例子:
RocksDB 使用 TwoLevelIterator 来读取 SST 文件,first_level_iter_ 指向 SST 文件的索引块的 BlockIter,而 second_level_iter_ 则是一个数据块的 BlockIter。
来看一个简单的 SST 文件例子,我们有 4 个数据块和一个索引块:
[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:
- first_level_iter_ => BlockIter 指向索引块
- second_level_iter_ => BlockIter 指向数据块,会通过 first_level_iter_ 来决定
比如,当我们要求 TwoLevelIterator 查找 KEY8,他会先使用 first_level_iter_(索引块的 BlockIter)来找出那个块可能会包含这个 key。这会找到对应的 second_level_iter_(偏移 0x0250 的数据块的 BlockIter)。我们会使用 second_level_iter_ 来找到我们在数据块的 key 和 value。