大白话解析LevelDB: Block Iterator

2024-02-22 01:20

本文主要是介绍大白话解析LevelDB: Block Iterator,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • Block Iterator
    • Iterator 接口
    • Block Iterator 的实现
      • Block Iterator 的私有成员
      • Block Iterator 的构造函数
      • Block::Iter::Valid()
      • Block::Iter::status()
      • Block::Iter::key()
      • Block::Iter::value()
      • Block::Iter::Next()
      • Block::Iter::Prev()
      • Block::Iter::Seek(const Slice& target)
      • Block::Iter::SeekToFist()
      • Block::Iter::SeekToLast()

Block Iterator

Block Iterator用于遍历一个SST中的某个BlockBlock的结构如下:

+----------------+
|    Key1:Value1 |
+----------------+
|    Key2:Value2 |
+----------------+
|       ...      |
+----------------+
|    KeyN:ValueN |
+----------------+
| Restart Point1 |
+----------------+
| Restart Point2 |
+----------------+
|       ...      |
+----------------+
| Restart PointM |
+----------------+
| Num of Restarts|
+----------------+

关于Block的结构详情可移步参考(大白话解析LevelDB: BlockBuilder)[https://blog.csdn.net/sinat_38293503/article/details/134997464#Block__153]。

Iterator 接口

Block::IterIterator接口的一种实现,所以我们先看下Iterator里都有哪些接口需要实现:

class LEVELDB_EXPORT Iterator {public:Iterator();Iterator(const Iterator&) = delete;Iterator& operator=(const Iterator&) = delete;virtual ~Iterator();// 判断迭代器当前所在位置是否有效,如果有效,// 则可以通过 key() 和 value() 获取当前键值对。virtual bool Valid() const = 0;// 将当前位置移动到第一个 Key-Value 所在处。virtual void SeekToFirst() = 0;// 将当前位置移动到最后的 Key-Value 所在处。virtual void SeekToLast() = 0;// 将当前位置移动到第一个大于等于 target 的 Key-Value 所在处。virtual void Seek(const Slice& target) = 0;// 将当前位置移动到下一个 Key-Value 所在处。virtual void Next() = 0;// 将当前位置移动到上一个 Key-Value 所在处。virtual void Prev() = 0;// 返回当前位置的 Key。virtual Slice key() const = 0;// 返回当前位置的 Value。virtual Slice value() const = 0;// 返回迭代器的当前状态。// 如果状态不是 ok,则说明迭代器已经失效,不可使用了。virtual Status status() const = 0;// 用户可注册多个 CleanupFunction,当迭代器被销毁时,会按顺序调用这些 // CleanupFunction。// 需要注意的是,RegisterCleanup 这个方法不需要 Iterator 的子类实现,// Iterator 已经实现了,用户不需要重写。using CleanupFunction = void (*)(void* arg1, void* arg2);void RegisterCleanup(CleanupFunction function, void* arg1, void* arg2);
};

Block Iterator 的实现

Block::IterIterator接口的一种实现,它需要实现Iterator接口里的所有抽象方法。

Block Iterator 的私有成员

在阅读Block Iterator的实现之前,我们先来看一下Block Iterator里各个私有成员的含义,为后续的阅读做好准备。

class Block::Iter : public Iterator {private:// 构造 Iter 的时候传入一个 Comparator,决定了 Block 中的 key 的排序方式const Comparator* const comparator_;// data_ 指向存放 Block 数据的地方const char* const data_;       // underlying block contents// 通过 data_ + restarts_ 可得到重启点数组的起始位置uint32_t const restarts_;      // Offset of restart array (list of fixed32)// 重启点的数量uint32_t const num_restarts_;  // Number of uint32_t entries in restart array// current_ is offset in data_ of current entry.  >= restarts_ if !Valid//// 当前 Key-Value 在 data_ 中的偏移量uint32_t current_;// 当前处在哪个重启点,通过 restarts_[restart_index_] 可拿到当前重启点uint32_t restart_index_;  // Index of restart block in which current_ falls// 当前 Key-Value 中的 keystd::string key_;// 当前 Key-Value 中的 valueSlice value_;// 当前 Iterator 的状态Status status_;
}

Block Iterator 的构造函数

SST中解析出一个Block的以下 3 个信息后,就可以构造一个Block Iterator了:

  • data指针
  • 重启点数组在data中的偏移量
  • 重启点的数量
Iter(const Comparator* comparator, const char* data, uint32_t restarts, uint32_t num_restarts): comparator_(comparator),data_(data),restarts_(restarts),num_restarts_(num_restarts),current_(restarts_),restart_index_(num_restarts_) {assert(num_restarts_ > 0);
}

Block::Iter::Valid()

current_表示当前Key-Valuedata_中的偏移量,restarts_表示重启点数组在data_中的偏移量,所以current_小于restarts_时,Block::Iter是有效的。

如果current_大于等于restarts_current_就已经指向重启点的区域了,此时Block::Iter是无效的。

bool Valid() const override { return current_ < restarts_; }

Block::Iter::status()

没啥好说的,直接返回当前Iterator的状态。

Status status() const override { return status_; }

Block::Iter::key()

Prev(), Next(), Seek()方法会将current_指向一个有效的Key-Value,并且将该Key-Valuekeyvalue分别存储到key_value_中,所以key()方法直接返回key_即可。

Slice key() const override {assert(Valid());return key_;
}

Block::Iter::value()

Prev(), Next(), Seek()方法会将current_指向一个有效的Key-Value,并且将该Key-Valuekeyvalue分别存储到key_value_中,所以key()方法直接返回key_即可。

Slice value() const override {assert(Valid());return value_;
}

Block::Iter::Next()

将迭代器移动到下个Key-Value的位置。

void Next() override {assert(Valid());// 将 current_ 移动到下一个 Key-Value 的位置,// 并且解析出 Key。ParseNextKey();
}

Next()的实现逻辑都甩给了ParseNextKey().

ParseNextKey()的实现如下:

bool ParseNextKey() {// 计算下一个 Key-Value 的偏移量current_ = NextEntryOffset();// 找到下一个 Key-Value 的首地址const char* p = data_ + current_;// limit 指向重启点数组的首地址const char* limit = data_ + restarts_;  // Restarts come right after data// 如果当前 Key-Value 的偏移量超过了重启点数组的首地址,// 表示已经没有 Next Key 了。if (p >= limit) {current_ = restarts_;restart_index_ = num_restarts_;return false;}// 根据重启点来解析下一个 Key-Valueuint32_t shared, non_shared, value_length;p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);if (p == nullptr || key_.size() < shared) {// 解析失败,将错误记录到 Iterator 的 status_ 里。CorruptionError();return false;} else {// 解析成功,此时 p 指向了 Key 的 non_shared 部分,// 将 shared 和 non_shared 部分拼接起来,得到当前 Key。key_.resize(shared);key_.append(p, non_shared);value_ = Slice(p + non_shared, value_length);// 更新 restart_index_,找到下一个重启点while (restart_index_ + 1 < num_restarts_ &&GetRestartPoint(restart_index_ + 1) < current_) {++restart_index_;}return true;}
}

Block::Iter::Prev()

Prev()Next()实现不一样,不能简单的将current往上移一个位置。

见下图,假设current_指向Key3,上一个KeyKey2Key2Key3里都没有存储完整的KeyKey3需要依赖Key2来解析出完整的Key3,而Key2需要依赖Key1来解析出完整的Key2,以此类推,Key1需要依赖Key0来解析出完整的Key1,而Key0位于重启点,是没有依赖的,自己本身就存储了完整的Key

所以要找到Key2,我们需要先找到Key3之前最近的一个重启点,也就是RestartPoint0

然后将current_移动到该重启点的位置,再不断的向后边移动current_,边解析出当前Key,直到current_指向Key3的前一个Key,也就是Key2

                              current_+|v+--------+--------+--------+--------+--------+--------+|  Key0  |  Key1  |  Key2  |  Key3  |  Key4  |  Key5  |+--------+--------+--------+--------+--------+--------+^                                   ^|                                   |+                                   +
RestartPoint0                       RestartPoint1
void Prev() override {assert(Valid());// 把 restart_index_ 移动到 current_ 之前最近的一个重启点。const uint32_t original = current_;while (GetRestartPoint(restart_index_) >= original) {if (restart_index_ == 0) {// 前面没有 Key 了current_ = restarts_;restart_index_ = num_restarts_;return;}restart_index_--;}// 把 current_ 移动到重启点的位置,SeekToRestartPoint(restart_index_);do {// 将 current_ 不断向后移动,一直移动到原先 current_ 的前一个位置。} while (ParseNextKey() && NextEntryOffset() < original);
}

Block::Iter::Seek(const Slice& target)

理解Prev()的实现后,Seek()的实现就比较容易理解了。我们不能直接去找target的位置,而是需要先找到target的那个重启点。然后再从这个重启点开始,一步步向右移动current_,直到找到第一个大于等于targetKey

而找重启点的过程,是一个二分查找的过程。

void Seek(const Slice& target) override {// 理解 Prev() 的实现后,Seek() 的实现就比较容易理解了。// 我们不能直接去找 target 的位置,而是需要先找到 target // 的那个重启点。用二分的方式查找这个重启点。uint32_t left = 0;uint32_t right = num_restarts_ - 1;int current_key_compare = 0;if (Valid()) {// 如果当前 Iterator 已经指向某个有效的 Key 了,我们就可以利用这个 Key 来把// 二分查找 target 重启点的范围缩小一些。current_key_compare = Compare(key_, target);if (current_key_compare < 0) {// 如果当前 Key 比 target 小,那么 target 重启点的位置一定在当前重启点的// 右边,包括当前重启点。left = restart_index_;} else if (current_key_compare > 0) {// 如果当前 Key 比 target 大,那么 target 重启点的位置一定在当前重启点的// 左边,包括当前重启点。right = restart_index_;} else {// 如果当前 Key 已经是 target 了,那么就不需要再做其他操作了。return;}}// 二分查找 target 的重启点。while (left < right) {// 找到 left 和 right 中间的那个重启点,看这个重启点的 Key 和 target 的大小关系。//   - 如果 mid 重启点的 Key 比 target 小,那么 target 重启点的位置一定在 mid //     的右边,需要吧 left 移动到 mid 的位置。//   - 如果 mid 重启点的 Key 比 target 大,那么 target 重启点的位置一定在 mid//     的左边,需要把 right 移动到 mid 的位置。    uint32_t mid = (left + right + 1) / 2;uint32_t region_offset = GetRestartPoint(mid);uint32_t shared, non_shared, value_length;const char* key_ptr = DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,&non_shared, &value_length);if (key_ptr == nullptr || (shared != 0)) {CorruptionError();return;}Slice mid_key(key_ptr, non_shared);if (Compare(mid_key, target) < 0) {left = mid;} else {right = mid - 1;}}// 找到 target 的重启点后,一步步向右移动 current_,直到找到第一个大于等于// target 的 Key。assert(current_key_compare == 0 || Valid());bool skip_seek = left == restart_index_ && current_key_compare < 0;if (!skip_seek) {SeekToRestartPoint(left);}while (true) {if (!ParseNextKey()) {return;}if (Compare(key_, target) >= 0) {return;}}
}

Block::Iter::SeekToFist()

void SeekToFirst() override {// 移动到一个重启点。SeekToRestartPoint(0);// 解析出第一个 Key。ParseNextKey();
}

Block::Iter::SeekToLast()

void SeekToLast() override {// 移动到最后一个重启点。SeekToRestartPoint(num_restarts_ - 1);// 不断向后移动 current_,直到最后一个 Key。while (ParseNextKey() && NextEntryOffset() < restarts_) {}
}

这篇关于大白话解析LevelDB: Block Iterator的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/733714

相关文章

C语言中自动与强制转换全解析

《C语言中自动与强制转换全解析》在编写C程序时,类型转换是确保数据正确性和一致性的关键环节,无论是隐式转换还是显式转换,都各有特点和应用场景,本文将详细探讨C语言中的类型转换机制,帮助您更好地理解并在... 目录类型转换的重要性自动类型转换(隐式转换)强制类型转换(显式转换)常见错误与注意事项总结与建议类型

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查

在Rust中要用Struct和Enum组织数据的原因解析

《在Rust中要用Struct和Enum组织数据的原因解析》在Rust中,Struct和Enum是组织数据的核心工具,Struct用于将相关字段封装为单一实体,便于管理和扩展,Enum用于明确定义所有... 目录为什么在Rust中要用Struct和Enum组织数据?一、使用struct组织数据:将相关字段绑

使用Java实现一个解析CURL脚本小工具

《使用Java实现一个解析CURL脚本小工具》文章介绍了如何使用Java实现一个解析CURL脚本的工具,该工具可以将CURL脚本中的Header解析为KVMap结构,获取URL路径、请求类型,解析UR... 目录使用示例实现原理具体实现CurlParserUtilCurlEntityICurlHandler

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT

数据库使用之union、union all、各种join的用法区别解析

《数据库使用之union、unionall、各种join的用法区别解析》:本文主要介绍SQL中的Union和UnionAll的区别,包括去重与否以及使用时的注意事项,还详细解释了Join关键字,... 目录一、Union 和Union All1、区别:2、注意点:3、具体举例二、Join关键字的区别&php

Spring IOC控制反转的实现解析

《SpringIOC控制反转的实现解析》:本文主要介绍SpringIOC控制反转的实现,IOC是Spring的核心思想之一,它通过将对象的创建、依赖注入和生命周期管理交给容器来实现解耦,使开发者... 目录1. IOC的基本概念1.1 什么是IOC1.2 IOC与DI的关系2. IOC的设计目标3. IOC

java中的HashSet与 == 和 equals的区别示例解析

《java中的HashSet与==和equals的区别示例解析》HashSet是Java中基于哈希表实现的集合类,特点包括:元素唯一、无序和可包含null,本文给大家介绍java中的HashSe... 目录什么是HashSetHashSet 的主要特点是HashSet 的常用方法hasSet存储为啥是无序的

Linux中shell解析脚本的通配符、元字符、转义符说明

《Linux中shell解析脚本的通配符、元字符、转义符说明》:本文主要介绍shell通配符、元字符、转义符以及shell解析脚本的过程,通配符用于路径扩展,元字符用于多命令分割,转义符用于将特殊... 目录一、linux shell通配符(wildcard)二、shell元字符(特殊字符 Meta)三、s

使用Python实现批量访问URL并解析XML响应功能

《使用Python实现批量访问URL并解析XML响应功能》在现代Web开发和数据抓取中,批量访问URL并解析响应内容是一个常见的需求,本文将详细介绍如何使用Python实现批量访问URL并解析XML响... 目录引言1. 背景与需求2. 工具方法实现2.1 单URL访问与解析代码实现代码说明2.2 示例调用