庖丁解LevelDB之Iterator



  • 通过之前对LevelDB的整体流程,数据存储以及元信息管理的介绍,我们已经基本完整的了解了LevelDB。接下来两篇要介绍的内容并不是LevelDB的基本组成,却是让LevelDB更优雅高效的重点和体现,Iterator就是这样一种存在。

    作用

    正如庖丁解LevelDB之数据存储中介绍的,LevelDB各个组件用不同的格式进行数据存取。在LevelDB内部、外部、各个不同阶段又不可避免的需要从不同的视角遍历这些数据。如果每一个层次的数据遍历都需要详细的关心全部数据存储格式,无疑将使得整个过程变得无比的冗余复杂。Iterator的出现正式为了解决这个问题,Iterator在各个层次上,向上层实现提供了:

    无须了解下层存储细节的情况下,通过统一接口对下层数据进行遍历的能力。

    接口

    Iterator用确定的遍历接口将上层需求和下层实现解耦和。熟悉STL的同学一定不会陌生Iterator的使用方式,这里LevelDB的Iterator接口包括:

    • Seek到某一位置:Seek,SeekToFirst,SeekToLast;
    • 访问前驱后继:Next,Prev;
    • 判断当前位置是否有效:Valid;
    • 获取当前位置数据信息:key,value,status;
    • 可以注册多个Cleanup方法,当Iterator析构前做一些清理操作。

    分类

    LevelDB大量使用了各种Iterator,根据Iterator的实现和层次,我们将其分为三种类型:

    • 基本Iterator:最原子的Iterator,针对相应的数据结构实现Iterator接口;
    • 组合Iterator:通过各种方式将多个基本Iterator组合起来,向上层提供一致的Iterator接口。
    • 功能Iterator:某种或多种组合Iterator的联合使用,附加一些必要的信息,实现某个过程中的遍历操作。
    • 基本Iterator

    LevelDB中包括三种基本Iterator,他们分别针对Memtable,Block以及Version中的文件索引格式,实现了最原子的Iterator:

    MemTableIterator

    在Memtable Skiplist的格式上的Iterator实现。Memtable格式见庖丁解LevelDB之数据存储。

    Block::Iter

    针对SST文件Block存储格式的Iterator实现。遍历的过程中解析重启点,拼接key的共享部分和特有部分,获取对应的value值。Block详细格式见庖丁解LevelDB之数据存储。

    Version::LevelFileNumIterator

    庖丁解LevelDB之版本控制中介绍了Version中记录了当前所有文件按层次划分的二维数组。其中Level1层之上的文件由于相互之间没有交集且有序,可以利用文件信息中的最大最小Key来进行二分查找。LevelFileNumIterator就是利用这个特点实现的对文件元信息进行遍历的Iterator。其中每个项记录了当前文件最大key到文件元信息的映射关系。这里的文件元信息包含文件号及文件长度。

    组合Iterator

    组合Iterator由多个基本Iterator或组合Iterator组合而成,LevelDB中包含两种组合Iterator:

    TwoLevelIterator

    TwoLevelIterator实现逻辑上有层次关系的数据的遍历操作。组合了index iterator和data iterator两层迭代器,其中index iterator记录从数据key值到data iterator的映射,而data iterator则负责真正数据key到value的映射。生成TwoLevelIterator时,需要提供index Iterator及BlockFunction函数,其中BlockFunction实现了index iterator value值的反序列化以及对应的data iterator的生成。

    MergingIterator

    通过MergingIterator可以实现多个有序数据集合的归并操作。其中包含多个child iterator组成的集合。对MergingIterator的遍历会有序的遍历其child iterator中的每个元素。

    功能Iterator

    为了实现不同场景下不同层次的数据遍历操作,可以联合一种或多种组合Iterator,这里称为功能Iterator,按其所负责的数据层次由下自上进行介绍:

    Table::Iterator

    对SST文件的遍历,通过庖丁解LevelDB之数据存储可知,这里有明显的层级关系,可以利用上面介绍的TwoLevelIterator,其index iterator为Index Block的Block::Iter,data iterator为Data Block的Block::Iter

    0_1501556055852_7123aac5-f799-4b57-89d1-a2787b8d1c9a-image.png

    Compaction过程Iterator

    Compaction过程中需要对多个文件进行归并操作,并将结果输出到新的下层文件。LevelDB用MergingIterator来实现这个过程,其clild iterator包括庖丁解LevelDB之版本控制中提到的要Compaction的多个文件对应的Iterator:

    • 如果有Level0文件,则包含所有level0文件的Table::Iterator
    • 其他Level文件,加入NewConcatenationIterator,作为一个TwoLevelIterator,由Version::LevelFileNumIterator作为index iterator,Table::Iterator作为data iterator

    0_1501556076755_2e122c6e-d418-4153-837b-0024c4efb587-image.png

    NewInternalIterator

    LevelDB作为整体同样通过Iterator向外部用户提供遍历全部数据的能力。这里使用MergingIterator将Memtable,Immutable memtable及各层SST文件的Iterator归并起来,使得外部使用者不用关心具体的内部实现而有序的循环LevelDB内部的数据,LevelDB首先实现了NewInternalIterator:

    0_1501556089824_79a82603-512c-4990-814f-fc0885fc8c2d-image.png

    在NewInternalIterator的基础上,LevelDB有封装了DBIter来处理快照,过滤已删除key。


登录后回复
 

与 区块链大学 | qkldx.net 的连接断开,我们正在尝试重连,请耐心等待