跳转至

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

实现:table/merging_iterator.cc

接口:InternalIterator

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

接口:IternalIterator

这是一个 MemtableRep::Iterator 的封装,每一个 memtable 分别实现自己的迭代器以导出 memtable 自己的 kv 排序流数据。

BlockIter

实现:table/block.h

接口:InternalIterator

这个迭代器被用于读取 SST 文件的块,不管这些块是索引块还是数据块。由于 SST 文件块都是排序好的,并且不可变得,我们把这个块的数据加载到内存然后为排序好的数据创建一个 BlockIter

TwoLevelIterator

实现:table/two_level_iterator.cc

接口:InternalIterator

一个 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。