专栏首页linjinhe的专栏LevelDB 完全解析(3):SSTable

LevelDB 完全解析(3):SSTable

前文回顾

SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB 中的大部分数据是以 SSTable 的形式保存在外存上。

SSTable 由 compaction 生成:

  • Minor Compaction:一个 MemTable 直接 dump 成 level-0 的一个 SSTable。
  • Major Compaction:多个 SSTable 进行合并、重整,生成 1~多个 SSTable。

SSTable 的格式

SSTable 格式

在一个 SSTable 中,文件末尾的 Footer 是定长的,其他数据都被划分成一个个变长的 block:index block、metaindex block、meta blocks、data blocks。

  • Footer Footer 的大小为 48 字节,内容是一个 8 字节的 magic number 和两个 BlockHandle —— index handle 和 meta index handle,index handle 指向 index block,meta index handle 指向 meta index block。BlockHandle 相当于一个 block 的“指针”,由这个 block 的 offset(varint64) 和 size(varint64) 组成。由于采用 varint64 进行编码,每个 varint64 最多占用 10 字节,所以一个 BlockHandle 最多占用 20 字节。因为 BlockHandle 是定长,而 BlockHandle 编码的结果是变长的,所以 Footer 编码的时候需要进行 padding
  • Index Block Index block 中的每条 key-value 指向一个 data block。value 比较简单直接,就是对应的 data block 的 BlockHandle。key 是一个大于等于当前 data block 中最大的 key 且小于下一个 block 中最小的 key,这一块的逻辑可以参考 FindShortestSeparator 的调用实现。这样做是为了减小 index block 的体积,毕竟我们希望程序运行的时候,index block 被尽可能 cache 在内存中。
  • Meta Index Block Meta index block 中的每条 key-value 指向一个 meta block。目前 LevelDB 中只有一个 meta block,保存的是这个 SSTable 中的 key 组成的 bloom filter。
  • Data Block Data block 是实际的 key-value 数据。

Block

Index blockmeta index blockdata block 都是通过 BlockBuilder 来生成,通过 Block 来读取的。最简单的方式,block 里面只需要将一个个 key-value 有序保存。但是为了节省空间,LevelDB 在 block 的内部实现了前缀压缩

前缀压缩利用了 key 的有序性(前缀相同的有序 key 会聚集在一起)对 key 进行压缩,每个 key 与前一个 key 相同的前缀部分可以不用保存。读取的时候再根据规则进行解码即可。

LevelDB 将 block 的一个 key-value 称为一条 entry。每条 entry 的格式如下:

entry 格式

  • shared_bytes:和前一个 key 相同的前缀长度。
  • unshared_bytes:和前一个 key不同的后缀部分的长度。
  • value_length:value 数据的长度。
  • key_delta:和前一个 key不同的后缀部分。
  • value:value 数据。

一个 block 的数据格式如下:

block 格式

  • restarts:在 LevelDB 中,默认每 16 个 key 就会重新计算前缀压缩,重新开始计算前缀压缩到第一个 key 称之为重启点(restart point)。restarts 数组记录了这个 block 中所有重启点的 offset。
  • num_restarts:是 restarts 数组的长度。

在 block 中查找一个 key(Block::Iter::Seek):

  1. 先在 restarts 数组的基础上进行二分查找,确定 restart point。
  2. 从 restart point 开始遍历查找

Filter

Meta block(bloom filter)由 FilterBlockBuilder 来生成,通过 FilterBlockReader 来读取。

后面会单独写一篇介绍 filter。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(4):Manifest

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

    linjinhe
  • LevelDB 完全解析(6):Filter

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

    linjinhe
  • 设计数据密集型应用(10-11):大数据的批处理和流处理

    谈大数据批处理,绕不过的就是 MapReduce。MapReduce 是大数据处理的老祖宗了。

    linjinhe
  • 【Java】12 Map 集合

       Map 用于保存具有映射关系的数据,因此 Map 集合里保存着两组值,一组值用于保存 Map 里的 key,另外一组值用于保存 Map 里的 value,...

    Demo_Null
  • 谈谈堆与栈:数据结构和内存角色

    堆包含一个链表来维护已用和空闲的内存块。在堆上新分配(用 new 或者 malloc)内存是从空闲的内存块中找到一些满足要求的合适块,这个操作会更新堆中的块链表...

    江不知
  • DBDB: 一个简单的key/value数据库(二)

    DBDB引用了一个Storage实例,self._tree也引用了此实例。DBDB实例可以通过字典查找(db [key])来获取键值。同时Python也会调用D...

    哒呵呵
  • 【PAT甲级】Broken Keyboard

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 对比Vector、ArrayList、LinkedList有何区别?不同容器类型适合的场景?

    Verctor是 Java 早期提供的线程安全的动态数组,如果不需要线程安全,并不建议选择,毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据,...

    葆宁
  • Python操作Redis之设置key的过期时间

    对于一个已经存在的key,我们可以设置其过期时间,到了那个时间后,当你再去访问时,key就不存在了

    周小董
  • 这道高频面试题你掌握了吗?

    这是在 Daily-Interview-Question 项目看到一个比较有意思的题目。

    石燕平

扫码关注云+社区

领取腾讯云代金券