sstable存储结构与LSM

SSTABLE

sstable 是 google bigtable 中引出的数据结构,在 levelDB、RocksDB 以及现在各类数据库存储中配合 LSM 有广泛应用,学习下很有必要,本位以 RocksDB 中 SST 的实现来了解 SST。

优点

  • 空间利用率高:sstable 基于 sorted string 的结构使得他非常适合做压缩,有更好的空间利用率
  • 利于合并:key 本身是 sorted,非常适合采用归并排序来做 merge。LSM 中利用 sstable 作为基本存储单元也有这样的考量。

存储结构

sstable 是 sorted string table 的缩写,存储结构的设计关键在于 sorted string。sstable 文件内部有多个数据块(block)构成。一个数据块内多个 entry 的 key 是按照字符来排序的,并且充分利用 prefix string 来减少存储开销。不过为了避免第一个 prefix key 导致全部 entry 损坏,固定 entry 个数会有一个 entry 包含完整 key 信息,这个点称之为 restart point。这个 entry 的 key 的 shared 值重置为 0。block 结尾的 tailer 会记录 restart point 的偏移量信息。

下图是 restart point 的示意图

下图来源[1] 展示了 SST 的基本结构。

Block 的定义:Block 结构是指除了内部的有效数据外,还会有额外的压缩类型字段和校验码字段。每一个 Block 尾部都会有压缩类型和循环冗余校验码(crcValue),这会要占去 5 字节。压缩算法默认是 snappy ,校验算法是 crc32。

  • index block: 记录 data block 的元信息
  • metaindex block: 记录过滤器相关的元信息
  • data block: 保存了 kv 信息
  • meta block/filter block: 现在其实只有一种 meta block 即 filter block。写入 Data Block 的数据会同时更新对应 Meta Block 中的过滤器。读取数据时也会首先经过布隆过滤器过滤。Meta Block 的物理结构也与其他 Block 有所不同。bloom filter 帮助读操作,确认该 sstable 内是否包含对应数据。如果不包含对应数据,则直接避免遍历 sstable
  • footer:为于 ssTable 尾部,记录指向 Metaindex Block 的 Handle 和指向 Index Block 的 Handle。所有的 Handle 是通过偏移量 Offset 以及 Size 一同来表示的,用来指明所指向的 Block 位置。Footer 是解析 ssTable 文件最开始的地方。通过 Footer 中记录的这两个关键元信息 Block 的位置,可以方便的开启之后的解析工作。另外 Footer 种还记录了用于验证文件是否为合法 SST 文件的常数值魔数(maigicnum)。

RocksDB & LSM

简介

**LSM tree (log-structured merge-tree) **是一种对频繁写操作非常友好的数据结构,同时兼顾了查询效率。LSM tree 是许多 key-value 型、日志型数据库以及新型分布式数据库、OLAP 引擎所依赖的核心数据结构,例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB、OceanBase 等。由于 RocksDB 的实现比较有代表性,下面原理的介绍中关于实现部分都以 RocksDB 的实现为例。

使用场景

我们都知道的一个客观事实是——磁盘或内存的连续读写性能远高于随机读写性能。LSM 由于避免了随机读写,在读写性能上其实都有还不错的表现,尤其在写性能上很突出。适合于面向写多读少的场景。下图展示了磁盘内存随机、顺序读写的差异。

结构说明

  • active memtable: 接收内存写入的数据,rocksDB 实现是为一个 skipList。这个结构也可以是一个 B+树或者 hash 表,根据实际需要。
  • immutable memtable: active memtable 写满后会生成一个不可变的 memtable
  • WAL:用于故障数据恢复的,数据库基本都会使用。写完 WAL 才算写入成功。WAL 的数据后续都持久化到 SST file 之后可以删除 WAL file
  • SST file: 核心结构是 sstable,这个参考前面章节
  • block cache: 一般查找是 logN 时间复杂度,引入块缓存可以做 o(1)的查询和写入

读取数据过程

查找对象顺序为:
active memtable -> immutable memtable ->L0 ->L1 … ->Ln

Tips:

  • L0 层 key 重复: L0 有多个 sst file,由于是 memory 直接 flush 出来的,level 0 上的 sst file key 是有重复的,所以 L0 上的查找是遍历查找,不过会结合 bloom filter 提升读取效率。可见 L0 容易产生读取瓶颈,rocksDB 也有限制 L0 层文件数
  • 二分查找 0 层以上 SST 文件:L0 以后的都是经过 compaction 的,所以没有重复 key,可以用二分查找

写入数据过程

简单总结的过程如下,实际 RocksDB 写入时会根据 memtable size 阈值以及 compaction 情况做一些额外操作和判断,这里不展开。

  1. 写 WAL
  2. 写 memtable

memtable -> L0 的过程称之为 minor compaction,L0 往上的合并称之为 major compaction。

Compaction 过程

其实 Compaction 有很多种类,参考[10],下面介绍比较主流的 level compaction 和 tiered compaction。

基本概念

  • 读放大: 每次读请求带来的读盘次数
  • 写放大: 每写 1byte 数据带来 n bytes 的数据写盘,写放大为 n。例如写 1K 数据需要写一个 block,如果 block 是 32K,那么写入放大就是 32 倍。像 B+树的写放大就是叶子节点 page size。
  • 空间放大:所占空间大小/实际数据量大小,空间放大主要与未回收的过期数据量(old version/deleted entries)相关,这个在 LSM 结构中是普遍存在的。
  • **临时空间:**compaction 任务运行时需要临时空间,compaction 完成后旧数据才可以删除。与 compaction 任务的拆分粒度相关。
  • **run:**可以理解每个 run 里 KV 对具有 key 有序(sorted)和 key 不重叠(non-overlapping)的特点。

Level-Compaction

RocksDB 默认使用的 compaction 策略是 level-compaction。Level compaction适合读密集型场景。业界采用 Leveling 作为 Compaction 策略的有 LevelDB、RocksDB 等 KV 数据库。下图可以看到每一层定义的数据大小阈值,当新写入的 sst file 超过 level 设定的数据大小阈值时会触发 compaction。level-compaction 每一层都有固定的较小的 sst file 构成。总结下 Level-Compaction 的核心特点主要是:

  • 每层只有一个 run
  • 多层的 sst file大小固定
  • 满足层次设定大小阈值时触发 compaction

tips: L0->L1 使用 tiered compaction


合并条件&合并方式

当 level 满足该层大设定的数据大小阈值时,触发 compaction。数据合并到下一层的时候直接和下一层的数据合并形成一个 run。这也是 level compaction 写放大严重的问题。下图演示了 level-compaction 的过程,关键在于理解 compaction 构建的是一个有序 run。

tips: 多个 level 都需要 compaction 则会计算 score,一般而言,实际 sst file size 超过该 level 预设的大小阈值越多时,分数越高。

优点&缺点

相比别的 compaction,level-compaction 优缺点主要如下:

  • 较低程度空间放大(优点):同一层 level 内只有一个 run,各个 sst file 之间没有重复,所以冗余数据只发生在相邻 level 之间。空间的冗余占用最多是一个 sst file 的大小。由于每一层都是固定大小、较小的 sst file,所以写放大是不太严重的。例如相邻 level 的层大小阈值比例是 1:10,那么实际的空间放大最多为 10%
  • 较低程度读放大(优点):读盘次数每一层 1 次即可,每一层直接扫描一个有序的 run 即可。也就是说,run 总个数越多,读放大越厉害。
  • 写放大(缺点):如果只是在 level 层直接 append,那是没有什么写放大的,比如我要写 1K 数据,直接 append 1K 到磁盘上。我们一般指 level compaction 的写放大问题主要是指 compaction 阶段产生的写放大问题。针对 level-compaction,写入时由于要确保下一层产生一个 run,最坏情况会把当前层所有数据全部写入下一层。

tiered-compaction

level-compaction 是根据每层设定的数据量大小阈值来触发 compaction,而 tiered-compaction 是根据每层设定的 sstable 个数阈值来触发 compaction(每一层 sst file 是固定大小,不过每层的 sst file 固定大小都会大大增加)。下图[13] 展示了 tiered-compaction 合并流程,掌握关键点:

  • 个数满足阈值后,整一层作为一个新的 sstable file 放到下一层
  • compaction 后,下一层会多一个 sorted run

总结下 Level-Compaction 的核心特点主要是:
  • 每层有多个 run
  • 多层的 sst file个数固定
  • 满足层次设定sst file 个数阈值时触发 compaction
优点&缺点

相比别的 compaction,tiered-compaction 优缺点主要如下:

  • 空间放大(缺点):由于各个层次内有多个 run,有大量的数据冗余;此外高层次内的 sst file 文件比较大,很久可能都不会触发合并,这都导致了空间放大。这种空间放大 严重的时候会有 10 倍以上
  • 读放大(缺点):每个 level sorted run 个数较多,总 run 个数较多,导致读放大。
  • 临时空间放大(缺点):主要是归并合并的时候临时空间的开销。tiering 较粗粒度的 sst file 大小增加了合并时临时空间的开销。
  • 较低程度写放大(优点):compaction 过程上层数据 merge 后的 run 直接 append 到下一层,相比 level-compaction 来说写放大程度较低。

Level vs Tiered

leveling tiering
每 level run 数量最大值 只能为 1 大于 1
sst file 数量 逐层递增 每一层相同
sst file 的固定大小与层次的关系 每一层相同 逐层递增
应用场景 读密集型 写密集型

tips: 一般可以考虑 tiering+leveling 混合的方式。如果我们假设,近期数据是写密集型,远期数据是读密集型,可以在低 level 用 tiering,高 level 用 level compaction。像 rocksDB 就是 level0 用 tiering

扩展

LSM 的优化在学术界也是一个比较火热的议题,像[14]中提到的 lazy leveling 有兴趣也可以了解下。

LSM 和 B+树的比较

相对于 B+树,LSM 有更好的写性能,但是在读取性能上来说是不如 B+树的,主要原因是由于:

  • L0 层遍历开销:L0 层数据遍历,虽然有 bloom filter 加速,但是其读取性能仍然是不稳定的,最坏情况需要遍历所有 sst file,相当于 O(n)
  • 范围查询效率不高:不像 B+树排序好的叶子节点很容易也很高效做范围查询,LSM 做遍历查询需要遍历多个 SST file,对 L0 还需要做合并才能获取到最终准确的数据。这也影响了 LSM 结构上数据的查询性能。

tips: 不过现在实现 LSM 的数据库基本也都会优化 LSM 的读取性能,更好的支持范围查询。大家需要更加理性地看待 LSM 适合写多读少这句话的含义。

参考资料