专栏首页linjinhe的专栏LevelDB 完全解析(8):读操作之 Get

LevelDB 完全解析(8):读操作之 Get

LevelDB 支持的读操作分为两种:

  1. 点查询(Point Query):读一个 key 的数据。
  2. 范围查询(Range Query):有序读一段 key 范围的数据。

本文主要介绍点查询的实现。

Get 接口

LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;

key 和 value 都很简单:key 是本次查询的目标;如果找到对应的 key,数据会保存到 *value 中。

leveldb::ReadOptions 是读操作的控制参数:

  • verify_checksums - 是否检查 crc32 校验和,默认 false。
  • fill_cache - 从 SSTable 读取的数据是否要放到 block cache,默认 true。
  • snapshot - 表示本次读操作要从哪个快照读取。默认是 nullptr,会从当前最新的快照读取数据。

快照

先来看看 leveldb::Snapshot 的实现。leveldb::Snapshot 是个空壳,具体实现是在 leveldb::SnapshotImpl ,也相当简单,主要就维护一个 sequence_number_—— 只读取小于等于 sequence_number_ 的数据。

如果一个快照有被外部使用(GetSnapshot),这个快照对应的 SnapshotImpl 对象会被放在 SnapshotList 中。Compaction 的时候,遇到可以清理的数据,还需要判断是否会影响这些快照

Get 的实现

我们来看看 leveldb::DBImpl::Get 的实现:

  1. 获取互斥锁
  2. 获取本次读操作的 Sequence Number:如果 ReadOptions 参数的 snapshot 不为空,则使用这个 snapshot 的 sequence number;否则,默认使用 LastSequence(LastSequence 会在每次写操作后更新)。
  3. MemTable, Immutable Memtable 和 Current Version(SSTable) 增加引用计数,避免在读取过程中被后台线程进行 compaction 时“垃圾回收”了。
  4. 释放互斥锁 。所以,下面 5 和 6 两步是没有持有锁的,不同线程的请求可以并发执行。
  5. 构造 LookupKey
  6. 执行查找:
  7. 从 MemTable 查找
  8. 从 Immutable Memtable 查找
  9. 从 SSTable 查找
  10. 获取互斥锁
  11. 更新 SSTable 的读统计信息,根据统计结果决定是否调度后台 Compaction。=> 极少遇到有读触发 compaction 的场景,这一步的似乎意义不大。
  12. MemTable, Immutable Memtable 和 Current Version 减少引用计数,返回结果

主要逻辑在于读 MemTable(包括 Immutable MemTable) 和读 SSTable。

LookupKey

LevelDB 通过 user_key 和 sequence 构造 leveldb::LookupKey ,用于 LevelDB 内部接口的查找。其格式为:

  1. klength 的类型是 varint32,存储 userkey + tag 的长度
  2. userkey 就是 Get 接口传入的 key 参数。
  3. tag 是 7 字节 sequence number 和 1 字节 value type
  4. 一个 varint32 最多需要 5 个字节,tag 需要 8 字节。所以一个 LookupKey 最多需要分配 usize + 13 字节内存(usize 是 userkey 的 size)。

读 MemTable

MemTable 底层的实现是 leveldb::SkipList ,具体可以参考本系列的一篇文章《LevelDB 完全解析(1):MemTable》

leveldb::SkipList 支持无锁一写多读具体来讲:

  1. 写写并发由上层进行同步,保证同一时刻最多只有一个线程会写 SkipList。
  2. 读写并发不需要外部同步,只要保证 SkipList 不会被垃圾回收就好——这个通过引用计数保证。

具体实现查询操作的是 FindGreaterOrEqual 函数,返回值是一个指针,指向第一个大于等于 key 的结点(如果不存大于等于 key 的结点,则是 nullptr)。

在 MemTable 中,同一个 userkey 的多个版本是按照 sequence number 降序排序的,也就说“sequence number 小的在排序中比较大,sequence number 大的在排序中比较小”。所以,如果使用一个旧的 snapshot,只能查到比这个 snapshot 旧(或一样旧)的数据。

举个例子,假设 userkey 是 hello,当前有 3 个版本—— sequence number 分别是 5、10、20。那么它们在 MemTable 中的排序(从小到大)是:

... | hello-20 | hello-10 | hello-5 | ...

假设我们通过一个 sequence number 为 15 的快照进行查找,拼装 LookupKey 为 hello-15,查找发现第一个大于等于 hello-15 的 key 是 hello-10。

如果通过一个 sequence number 大于等于 20 的快照对 hello 这个 key 进行查找,那么 FindGreaterOrEqual 返回的就是执行 hello-20 的指针。

如果我们通过一个 sequence number 为 1 的快照进行查找呢?hello 的几个版本都不符合要求,FindGreaterOrEuqal 返回的不是 hello 这个 user key 的数据。所以,MemTable 对 FindGreaterOrEqual 返回的 key 会进行检查,再返回最终结果。

读 SSTTable

LevelDB 中将 SSTable 的管理实现成 leveldb::Version ,同时通过 leveldb::VersionSet 实现多版本管理。

Version::Get

SSTable 的点查询是从 leveldb::Version::Get 开始的:

  1. 根据每个 SSTable 的 key 范围 [smallest, largest] 收集可能需要查找的 SSTable,按照从新到旧维护
    1. level-0 的每个 SSTable 的 key 范围可能相交,每一个 SSTable 都需要判断。
    2. 非 level-0 的每一层内,SSTable 的 key 范围是不相交的——SSTable 是根据 key 范围有序排序的,可以通过二分查找优化查找效率。
  2. 根据上一步收集到的 SSTable,按照从新到旧开始查找。如果找到了,就可以直接返回结果。每个 SSTable 的具体查找逻辑是在 leveldb::TableCache::Get

TableCache::Get

  1. FindTable - 从 table cache 中找到对应的 table 对象。FindTable 实现了缓存 table 对象的逻辑。
  2. Table::InternalGet - 执行查找。

Table::InternalGet

Table::InternalGet 实现了从一个 SSTable 中查找一个 key 的逻辑。

  1. 从 index block 查找对应的 data block。如果没有对应的 data block,说明 key 不存在,返回。
  2. 通过 bloom filter 判断 key 是否存在
  3. 读取 data block 进行查找
  4. Table::BlockReader 封装了 block cache 和 SSTable 读取 data block 的逻辑。
  5. Data block 中的数据查找逻辑与其格式强相关,可以参考本系列的一篇文章《LevelDB 完全解析(3):SSTable》

小结

最后,用这张简图来总结一下 LevelDB Get 操作的逻辑:这是一个从上到下的过程,这个过程可能产生多次 I/O。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(10):读操作之 Iterator

    通过前面的文章,我们了解到 LevelDB 的数据是保存在内部多个不同组件的,并且每个组件的数据格式都不一样。

    linjinhe
  • LevelDB 完全解析(9):写操作

    以上,便是 LevelDB 的写入流程。写入队列 + 合并写操作,逻辑和代码都十分简洁。比较不足的是,整个写入过程都是单线程的。

    linjinhe
  • LevelDB:读操作

    前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。

    linjinhe
  • 【深度知识】LevelDB从入门到原理详解

    LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,也就是说,LevelDB很适合应用在查询较少,...

    辉哥
  • Google-LevelDB简介

    LevelDB简介 LevelDB一句话描述 LevelDB是google开发的,一个速度非常块的KV存储库(storage library),它支持字符串的k...

    架构师之路
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

    这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如:lsm派系难道只有lsm tree这一类存储模型吗?如果答案是否定的,...

    jaydenwen123
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • 漫谈 LevelDB 数据结构(一):跳表(Skip List)

    早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传 —— 绝对是不世出的工艺品!如果你对存储感兴趣、如果你想优雅使用 C++、...

    青藤木鸟
  • LevelDB 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

    linjinhe
  • 高性能Key/Value存储引擎SessionDB

    简介 随着公司业务量的逐年成长,粘性会话(Sticky Session)越来越成为应用横向扩展(Scale Out)的瓶颈,为消除粘性会话,支持应用无状态(St...

    携程技术
  • LevelDB 代码撸起来!

    LevelDB 的大致原理已经讲完了,本节我们要亲自使用 Java 语言第三方库 leveldbjni 来实践一下 LevelDB 的各种特性。这个库使用了 J...

    老钱
  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • LevelDB原理解析:数据的读写与合并是怎样发生的?

    导语 | LevelDB是一款十分优秀的存储引擎,具有极高的数据读写性能,尤其是写入性能,在笔者经历的多个项目中都有用到,因此本文打算结合LevelDB的部分源...

    腾小云
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • 漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)

    LevelDB 是一个单机的 KV 存储引擎,但没有使用传统的平衡查找树以平衡读写性能,而是使用了 LSM-tree 结构来组织数据,牺牲部分读性能来换取较高的...

    青藤木鸟
  • 解析 hashMap 源码之基本操作 get

    通过已经计算好的 hash 值,得到 table 的索引位置并来判断链表的第一个元素是不是要查找的节点,如果不是会查找树,最后会遍历链表

    shengjk1
  • LevelDB 入门 —— 全面了解 LevelDB 的功能特性

    本节我们将全面了解一下 LevelDB 的各种特性。LevelDB 的开发语言是 C++,考虑到会使用 C++ 语言的同学不是很多,在本节我们将使用 Java ...

    老钱
  • 50亿加密手机号md5快速存储及检索,rocksDB、redis等探索

    首先需求比较简单,将所有的号码段(如130、131、132)的全部手机号的md5和其对应的手机号存起来,将来传入一批手机号的md5,能迅速给出对应的明文手机号。...

    天涯泪小武

扫码关注云+社区

领取腾讯云代金券