专栏首页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 完全解析(8):读操作之 Get

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

    linjinhe
  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

    linjinhe
  • 分布式——详解Google leveldb中的LMST细节

    LSMT是一个在分布式系统当中应用非常广泛,并且原理直观简单的数据结构。在上一篇文章当中我们进行了详细的讨论,有所遗忘或者是新关注的同学可以点击下方的链接回顾一...

    TechFlow-承志
  • 漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)

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

    青藤木鸟
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

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

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

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

    腾小云
  • LevelDB 完全解析(11):Compaction

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

    linjinhe
  • LevelDB

    无论是 put 、 delete 还是batch操作,leveldb 底层都是以 batch 作为执行实例。

    itliusir
  • SSTable 介绍

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

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

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

    linjinhe
  • 谈谈数据库的选型

    在开发游戏服务器程序的过程中,好像大家都默认使用Mysql, 如果有性能问题,大不了再加个Memcached, 或者干脆使用Redis来做数据库。

    重归混沌
  • 深入理解什么是LSM-Tree

    十多年前,谷歌发布了大名鼎鼎的"三驾马车"的论文,分别是GFS(2003年),MapReduce(2004年),BigTable(2006年),为开源界在大数据...

    我是攻城师
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • 大数据那些事(11):复活的LSM-Tree--BigTable的系统实现

    BigTable是一个非常复杂的系统,发表的论文写得并不是很清楚。所幸Google开源了LevelDB这个Key-Value Store。这个项目的作者是Jef...

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

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

    辉哥
  • 大数据那些事(11):复活的LSM-Tree--BigTable的\b系统实现(修)

    修正一些小错误。 BigTable是一个非常复杂的系统,发表的论文面面俱到,但是每个方面都写得并不是很清楚。所幸Google开源了LevelDB这个Key-Va...

    用户1564362
  • 【深入浅出leveldb】文件类型与文件名

    leveldb运行一段时间后,系统中会产生一些文件,这些文件有哪些,各个文件又有什么作用,文件名怎么命名的呢?

    公众号guangcity

扫码关注云+社区

领取腾讯云代金券