大白话解析LevelDB: TwoLevelIterator

2024-02-22 04:20
文章标签 解析 大白话 leveldb twoleveliterator

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

文章目录

  • TwoLevelIterator
    • Iterator 接口
    • TwoLevelIterator 的实现
      • TwoLevelIterator 的构造函数
        • TwoLevelIterator::InitDataBlock
      • TwoLevelIterator::Seek(const Slice& target)
      • TwoLevelIterator::SeekToFirst
      • TwoLevelIterator::SeekToLast
      • TwoLevelIterator::Next
      • TwoLevelIterator::Prev
      • TwoLevelIterator::key
      • TwoLevelIterator::value
      • TwoLevelIterator::status

TwoLevelIterator

TwoLevelIterator其实就是用于遍历SST里所有Key-Value的Iterator。

那为什么要叫做TwoLevelIterator而不叫SSTIterator呢？TwoLevel指的是哪两个Level呢？

TwoLevel不是指同时遍历两层Level，而是指SST里的Index Block和Data Block两层。

SST的结构如下:

+---------------------+
|   Data Block 1      |
+---------------------+
|   Data Block 2      |
+---------------------+
|        ...          |
+---------------------+
|   Data Block N      |
+---------------------+
|   Meta Block 1      |
+---------------------+
|        ...          |
+---------------------+
|   Meta Block K      |
+---------------------+
| Metaindex Block     |
+---------------------+
|   Index Block       |
+---------------------+
|      Footer         |
+---------------------+

SST将Key-Value分散在多个Data Block里，Index Block里存储每个Data Block的Key范围和在SST文件中的偏移量。

Index Block的内容如下:

+--------------------------------------------------+
| Key1 | Block Handle1 (指向第一个 Data Block 的信息) |
+--------------------------------------------------+
| Key2 | Block Handle2 (指向第二个 Data Block 的信息) |
+--------------------------------------------------+
| Key3 | Block Handle3                             |
+--------------------------------------------------+
| ...............                                  |
+--------------------------------------------------+
| KeyN | Block HandleN                             |
+--------------------------------------------------+

Block Handle1里包含了Data Block 1在SST文件中的偏移量和大小。

想象一下我们现在要查找一个Key-X，需要先到Index Block中通过二分查找的方式找到对应的Block Handle，然后通过这个Block Handle找到对应的Data Block，最后再到Data Block中查找这个Key-X。

所以每次查找我们都要先到Index Block中查找，然后再到Data Block中查找，这就是TwoLevelIterator的TwoLevel。

Iterator 接口

TwoLevelIterator是Iterator接口的一种实现，所以我们先看下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);
};

TwoLevelIterator 的实现

TwoLevelIterator是Iterator接口的一种实现，它需要实现Iterator接口里的所有抽象方法。

TwoLevelIterator 的构造函数

TwoLevelIterator::TwoLevelIterator(Iterator* index_iter, BlockFunction block_function, void* arg,const ReadOptions& options): block_function_(block_function),arg_(arg),options_(options),index_iter_(index_iter),data_iter_(nullptr) {}

TwoLevelIterator的构造函数挺简单的，对一些成员变量进行了初始化。

主要是block_function_这个参数，它是一个函数指针，用于获取Data Block的Iterator。

我们来看下BlockFunction block_function的定义:

typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);

BlockFunction是一个函数指针，指向一个用于创建Data Block的Iterator的函数。

当TwoLevelIterator需要创建一个新的Data Block的Iterator时，它会调用block_function_。例如，当index_iter_移动到下一处了，TwoLevelIterator需要获取对应的Data Block更新data_ter，这时，它会调用block_function_。

我们来看下TwoLevelIterator是如何使用block_function_的。

TwoLevelIterator::InitDataBlock
void TwoLevelIterator::InitDataBlock() {if (!index_iter_.Valid()) {// 如果 index_iter_ 无效，那对应的 data_iter_ 也是无效的。SetDataIterator(nullptr);} else {// 从 index_iter 中取出对应的 data_block 的 handle。Slice handle = index_iter_.value();if (data_iter_.iter() != nullptr && handle.compare(data_block_handle_) == 0) {// 与 handle 对应的 data_iter_ 已经构建好了，// 不需要重复构建。} else {// 通过 block_function_ 构建 与 handle 对应的 data_iter_。Iterator* iter = (*block_function_)(arg_, options_, handle);data_block_handle_.assign(handle.data(), handle.size());SetDataIterator(iter);}}
}

TwoLevelIterator::InitDataBlock中，会从index_iter_中取出对应的data_block的handle，然后通过block_function_构建与handle对应的data_iter_。

SetDataIterator(iter)就是用于设置data_iter_的。

void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {if (data_iter_.iter() != nullptr) SaveError(data_iter_.status());data_iter_.Set(data_iter);
}

TwoLevelIterator::Seek(const Slice& target)

void TwoLevelIterator::Seek(const Slice& target) {// index_iter_ 对应着 index_block，到 index_block 中// 查找 target 属于哪个 data_block。index_iter_.Seek(target);// 如果找到了这个 data_block，就从 SST 中加载这个 data_block。InitDataBlock();// data_iter_.iter() != nullptr 从 SST 中加载到 target// 所属的 data_block了。if (data_iter_.iter() != nullptr) data_iter_.Seek(target);// 跳过不包含数据的 data_block。SkipEmptyDataBlocksForward();
}

target是我们要查找的Key，它存储在SST的Data Block中。

要找到这个Data Block，需要先通过index_iter_在Index Block里查找target属于哪个Data Block，找到这个Data Block的data_iter，然后通过data_iter在Data Block中查找target。

现在我们应该看出为什么要叫做TwoLevelIterator了，指的就是index_iter和data_iter这两个Iterator。

index_iter.Seek(target)的实现可移步参考大白话解析LevelDB: Block Iterator。

data_iter.Seek(target)的实现可移步参考大白话解析LevelDB: Block Iterator。

SkipEmptyDataBlocksForward()的实现如下：

void TwoLevelIterator::SkipEmptyDataBlocksForward() {while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {// index_iter_ 无效，表示 index_block 已经遍历完了。// 此时将 data_iter_ 置为 null 表示 data_iter_ 已经// 到末尾了。if (!index_iter_.Valid()) {SetDataIterator(nullptr);return;}// index_iter_ 里还有东西，继续往后走一位。index_iter_.Next();// 加载与当前 index_iter_ 对应的 Data Block。InitDataBlock();// 如果 data_iter_ 有效，就将 data_iter_ 移到第一个有效的位置。if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();}
}

如果index_iter_对应的data_iter_里没有有效数据，就将index_iter_往后移一位, 加载下一个data_block。一直到找到有数据的data_block为止。

TwoLevelIterator::SeekToFirst

void TwoLevelIterator::SeekToFirst() {// 到 index_block 中查找第一个 data_block 是哪个。index_iter_.SeekToFirst();// 从 SST 中加载这个 data_block。InitDataBlock();// data_iter_.iter() != nullptr 从 SST 中加载到第一个有效的// data_block 了。if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();// 跳过不包含数据的 data_block。SkipEmptyDataBlocksForward();
}

TwoLevelIterator::SeekToFirst与TwoLevelIterator::Seek的逻辑大体一样，先通过index_iter找到对应的data_iter，然后再通过data_iter定位data_block里的第一对Key-Value。

不过有同学可能会对if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst()里的if (data_iter_.iter() != nullptr)判断有疑惑，难道SST里全是无效的Data Block？

假设我们不停的对LevelDB做删除操作，db->Delete(leveldb::WriteOptions(), key)，那某个SST里的Key就全是Delete类型的，这时候我们对这个SST做SeekToFirst操作，就找不到任何有效的Data Block。

TwoLevelIterator::SeekToLast

TwoLevelIterator::SeekToLast的逻辑和TwoLevelIterator::SeekToFirst一样，就不再赘述啦。

void TwoLevelIterator::SeekToLast() {// 到 index_block 中查找最后一个 data_block 是哪个。index_iter_.SeekToLast();// 从 SST 中加载这个 data_block。InitDataBlock();// data_iter_.iter() != nullptr 从 SST 中加载到第一个有效的// data_block 了。if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();// 跳过不包含数据的 data_block。SkipEmptyDataBlocksBackward();
}

TwoLevelIterator::Next

void TwoLevelIterator::Next() {assert(Valid());// 将 data_iter_ 往后移一位即可。data_iter_.Next();// 跳过不包含数据的 data_block。SkipEmptyDataBlocksForward();
}

TwoLevelIterator::Next就不需要用到index_iter_了，将data_iter_按顺序往后移一位即可。

TwoLevelIterator::Prev

void TwoLevelIterator::Prev() {assert(Valid());// 将 data_iter_ 往前移一位即可。data_iter_.Prev();// 跳过不包含数据的 data_block。SkipEmptyDataBlocksBackward();
}

与TwoLevelIterator::Next同理，不需要用到index_iter_，将data_iter_按顺序往前移一位即可。

TwoLevelIterator::key

Slice key() const override {assert(Valid());// 取出 data_iter_ 当前位置的 key。return data_iter_.key();
}

取出data_iter_当前位置的key即可。

TwoLevelIterator::value

Slice value() const override {assert(Valid());// 取出 data_iter_ 当前位置的 value。return data_iter_.value();
}

取出data_iter_当前位置的value即可。

TwoLevelIterator::status

Status status() const override {if (!index_iter_.status().ok()) {// 先检查 index_iter_ 是否有异常return index_iter_.status();} else if (data_iter_.iter() != nullptr && !data_iter_.status().ok()) {// 再看 data_iter_ 是否有异常return data_iter_.status();} else {// index_iter_ 和 data_iter_ 都没异常，// 返回 TwoLevelIterator 自己的状态信息。return status_;}
}

先检查index_iter和data_iter_是否有异常，如果有的话，先返回它们的异常信息。

如果index_iter和data_iter_都没有异常，就返回TwoLevelIterator自己的状态信息。

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


http://www.chinasem.cn/article/734119。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
多线程解析报表

多线程解析报表

假如有这样一个需求，当我们需要解析一个Excel里多个sheet的数据时，可以考虑使用多线程，每个线程解析一个sheet里的数据，等到所有的sheet都解析完之后，程序需要提示解析完成。 Way1 join import java.time.LocalTime;public class Main {public static void main(String[] args) thro
阅读更多...
ZooKeeper 中的 Curator 框架解析

ZooKeeper 中的 Curator 框架解析

Apache ZooKeeper 是一个为分布式应用提供一致性服务的软件。它提供了诸如配置管理、分布式同步、组服务等功能。在使用 ZooKeeper 时，Curator 是一个非常流行的客户端库，它简化了 ZooKeeper 的使用，提供了高级的抽象和丰富的工具。本文将详细介绍 Curator 框架，包括它的设计哲学、核心组件以及如何使用 Curator 来简化 ZooKeeper 的操作。 1
阅读更多...
Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码，例如： using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can
阅读更多...
图解TCP三次握手｜深度解析｜为什么是三次

图解TCP三次握手｜深度解析｜为什么是三次

写在前面 这篇文章我们来讲解析 TCP三次握手。 TCP 报文段 传输控制块TCB：存储了每一个连接中的一些重要信息。比如TCP连接表，指向发送和接收缓冲的指针，指向重传队列的指针，当前的发送和接收序列等等。 我们再来看一下TCP报文段的组成结构 TCP 三次握手 过程 假设有一台客户端，B有一台服务器。最初两端的TCP进程都是处于CLOSED关闭状态，客户端A打开链接，服务器端
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2