LevelDB:读操作

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

LevelDB 的版本更新不是很频繁,整体变化不大。本文的源代码参考和索引的版本是 LevelDB v1.20

LevelDB 的目录结构很简单,就不用介绍了,直接进入正题吧。

leveldb::DB

LevelDB 暴露给外部的操作接口都封装在 leveldb::DB 这个抽象类里,具体实现是 leveldb::DBImpl 。使用时,leveldb::DB 用于引用一个 LevelDB 实例。一个 LevelDB 实例可以简单认为是一个支持并发读写和持久化的 map。

LevelDB 暴露给外部的操作接口都很简单,具体可以根据上面提供的索引链接看看代码和注释。

读操作

leveldb::DB::Get 根据 Key 获取 Value,先看看函数的原型:

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

leveldb::ReadOptions 是读操作的一些参数。verify_checksumsfill_cache 是两个偏优化的参数,重点是 snapshot 参数,表示本次读操作要从哪个 Snapshot 读取。snapshot 默认是 NULL,此时 LevelDB 会从当前 Snapshot 读取。

讲到 Snapshot,我们顺便来看看 leveldb::Snapshot 的实现。leveldb::Snapshot是个空壳,具体实现是在 leveldb::SnapshotImpl ,也相当简单,和 Snapshot 相关的变量只有一个 number_ (SequenceNumber) —— 不难看出 LevelDB 是通过维护一个 Sequence Number 来实现快照功能。

LevelDB 单个 Key 的读取操作的具体实现是 leveldb::DBImpl::Get 。我们来看看读操作的过程:

  1. 获取互斥锁
  2. 获取本次读操作的 Sequence Number:如果 ReadOptions 参数的 snaphot 不为空,则使用这个 snapshot 的 Sequence Number;否则,默认使用 LastSequence(LastSequence 会在每次写操作后更新)。
  3. MemTable, Immutable Memtable 和 Current Version 增加引用计数,避免在读取过程中被后台线程进行 Compaction 时“垃圾回收”了。Version 主要用来维护 SST 文件的版本信息。
  4. 释放互斥锁下面 5 和 6 两步是没有持有锁的,特别是第 6 步
  5. 构造 LookupKey
  6. 查找
    1. 从 MemTable 查找
    2. 从 Immutable Memtable 查找
    3. 从 SST 文件查找
  7. 获取互斥锁
  8. 更新 SST 文件的统计信息,根据统计结果决定是否调度后台 Compaction
  9. MemTable, Immutable Memtable 和 Current Version 减少引用计数
  10. 释放锁(由析构函数完成),返回结果

MemTable

上面分析读流程的时候,可以发现第 6 步,从 Memtable、Immutable Memtable 和 Current Version 指向的 SST 文件查找内容是不需要持有锁的。这样做没有并发读写的问题吗?

简单分析一下:引用计数保证了相关文件和内存数据结构不会被回收,而 Immutable Memtable 和 SST 文件都是只读的,没有并发读写问题。所以,只要看 MemTable 是否支持并发读写

leveldb::MemTable 底层的实现是 leveldb::SkipList 。在 leveldb::SKipList 有一段注释说明 ,简单地说就是:

  1. 写写冲突需要外部同步。
  2. 读写冲突不需要外部同步,只要保证 SkipList 不会被垃圾回收就好。
  3. 这里的 SkipList 只插入,不修改和删除

因此,从这段注释可以看出,MemTable 支持一写多读同时并发操作。后面有机会聊到 LevelDB 的写操作再来介绍一下 SkipList 的 Insert 操作如何实现读写并发不需要锁。

LookupKey

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

LookupKey.png

  1. klength 的类型是 varint32,是 leveldb 内部编码的可变长度的 uint32_t,存储 userkey + tag 的长度表示一个 varint32 最多需要 5 个字节
  2. userkey 就是一个 userkey 的 char 数组。
  3. tag 是使用 LittleEndian 编码的 uint64,其组成是 7 字节的 sequence 和 1 字节的 value_type。
  4. 所以,一个 LookupKey 的最大长度为: 5 + userkey size + 8 = userkey size + 13

SST 文件的查找

LevelDB 中将 SST 文件的管理实现成 leveldb::Version ,同时实现了 leveldb::VersionSet 管理多个 Version —— 因为 LevelDB 要支持 MVCC 所以可能同时存在多个版本。

查找的时候,获取当前版本 current , 调用 leveldb::Version::Get 在 SST 上进行查找。

  1. 从 level0 开始一层一层查找 —— 小 level 的数据比大 level 新,所以如果先找到了的话可以直接返回。
  2. 在要查找的 level 收集需要查找的文件。level0 的 sst 文件比较特殊,是直接由 Immutable MemTable dump 得到的,因此,每个文件的 key 范围可能重叠。level0 可能需要查找多个文件,其它 level 的 文件的 key 不会重叠,至多只需要读一个文件。
  3. 对步骤 2 收集到的文件进行查找。具体查找逻辑由 leveldb::TableCache::Get 实现。这里面涉及一些 Cache 相关的实现,暂时略过。
  4. 查找过程会记录一些统计信息:如果不止读取一个 sst 文件,则记录最后读取的是哪个 level 的哪个文件。

读触发的 Compaction

读取结束后,如果不止读取一个 sst 文件,则更新统计信息,决定是否触发 Compaction。更新统计信息时,直接将记录的文件的 leveldb::FileMetaData 的 allowed_seeks 减一,当 allowed_seeks <= 0时,表示读取效率很低,需要执行 Compaction,减少这条路径上的文件数量。

调用 MaybeScheduleCompaction 尝试调度后台线程的 Compaction。

小结

这里只是简单介绍了 LevelDB 的读操作的大概情况。实际上,LevelDB 的读操作涉及很多东西,如:写操作相关的并发读写、Sequence Number 等;Compaction 相关的 Version、VersionSet等;读操作还有可能触发 Compaction;还有 Table Cache、Block Cache 这些相关的东西没提及。

参考文档

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PhpZendo

MongoDB 学习笔记

感谢 Karl Seguin 编写的 The Little MongoDB Book 这本 MongoDB 入门书。

1061
来自专栏Java成神之路

Spring_总结_04_高级配置(四)_bean的作用域

Spring应用上下文中所有的bean默认都是单例的。也就是说,不管一个bean被注入到其他bean多少次,每次注入的都是同一个实例。

872
来自专栏阿杜的世界

Redis学习札记

Redis支持两种持久化方式,一种是RDB方式(快照:根据指定的规则“定时”将内存中的数据存储在硬盘上),另一种是AOF方式(在每次执行命令后都将命令本身记录下...

1103
来自专栏漏斗社区

代码审计|禅道7.3SQL注入复现

上周的zentaopms漏洞复现你们觉得还OK吗? 斗哥想要的是一个肯定。 如果你们觉得意犹未尽, 本期将进入, 代码审计的小练习。 Zentaopms v7....

3886
来自专栏Rgc

python更新数据库脚本两种方法

最近项目的两次版本迭代中,根据业务需求的变化,需要对数据库进行更新,两次分别使用了不同的方式进行更新。 第一种:使用python的MySQLdb模块利用原生的s...

3997
来自专栏Python

Flask快速入门,知识整理

一、Flask介绍(轻量级的框架,非常快速的就能把程序搭建起来)   Flask是一个基于Python开发并且依赖jinja2模板和Werkzeug WSGI服...

4339
来自专栏专注 Java 基础分享

Java EE基础之JSP(二)

     接着上篇文章,我们上篇文章讲到了jsp的基本原理以及和servlet的关系,还介绍了jsp的基本语法部分,本篇文章就继续介绍余下的内容。 编译指令Pa...

1818
来自专栏数据结构与算法

1777:文件结构“图”

1777:文件结构“图” 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 在计算机上看到文件系统的结构通常很有用。Micr...

36510
来自专栏DT乱“码”

一些linux命令总结。

5690
来自专栏别先生

基于jsp+servlet图书管理系统之后台用户信息修改操作

上一篇的博客写的是查询操作,且附有源码和数据库,这篇博客写的是修改操作,附有从头至尾写的代码(详细的注释)和数据库!  此次修改操作的源码和数据库:http:...

45310

扫码关注云+社区