专栏首页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 完全解析(11):Compaction

    因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:

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

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

    linjinhe
  • LevelDB:读操作

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

    linjinhe
  • 微服务开源框架TARS的RPC源码解析 之 初识TARS C++客户端

    导语:微服务开源框架TARS的RPC调用包含客户端与服务端,《微服务开源框架TARS的RPC源码解析》系列文章将从初识客户端、客户端的同步及异步调用、初识服务端...

    TARS基金会
  • 为什么说虚拟主机是个人站长的最佳选择

    网站在现代生活中逐渐扮演着信息传播、信息交流以及文化和服务驿站的角色,其重要性日益突出,因此不管是企业还是个人都有建站的需要。但是不同于企业建站,个人建站更注重...

    企鹅号小编
  • heidisql使用小技巧

    heidisql这个开源的mysql客户端连接工具很好用,它能显示很多mysql的运行参数,对于DBA或者偏sql的运维人员非常适用。

    二狗不要跑
  • Go 语言的大版本更新:Go 2.0 安排上了

    今年 8 月 Go 开发团队公布了 Go 2.0 的设计草案,包括错误处理和泛型这两大主题。现在备受瞩目的 Go 2.0 又有了新动向 —— 昨日 Go 开发团...

    Debian中国
  • 什么是数据挖掘?

    近年来,数据分析,数据挖掘和数据科学等领域不可谓不火热。而且人工智能、算法、数据科学领域的薪酬普遍高于传统互联网行业。既然决定从事互联网行业,那就得给自己找一个...

    爱吃西瓜的番茄酱
  • 2019年第十届蓝桥杯B组C++省赛手记

    这已经是第二次参加蓝桥杯大赛,之前参加蓝桥杯团队赛项只拿到了国家三等奖(安慰奖),上年编程成绩也是甚不理想,今年吃了上一年的亏,准备了许久,虽然是做的比较基础,...

    Debug客栈
  • golang下载安装

    官方二进制发行版 支持 FreeBSD(8-STABLE 发行版及以上)、Linux、Mac OS X(Snow Leopard 及以上)和 Windows 操...

    超蛋lhy

扫码关注云+社区

领取腾讯云代金券