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的偏移量信息。
image.png

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

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由于避免了随机读写,在读写性能上其实都有还不错的表现,尤其在写性能上很突出。适合于面向写多读少的场景。下图展示了磁盘内存随机、顺序读写的差异。
image.png

结构说明

image.png

  • 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。

基本概念

  • 读放大: 读放大是指为满足查询需求,实际读取的数据量相对于所需读取数据量的比例。在理想情况下,数据库仅需要读取与查询结果大小相同的数据量。然而,在实际应用中,由于数据结构、查询优化等因素的影响,数据库可能需要读取更多的数据以获得最终结果。读放大越高,数据库在处理查询时所需的 I/O 开销就越大。举例来说,假设有一个包含 100 个键值对的数据库,查询需要返回 10 个键值对。在理想情况下,数据库仅需读取 10 个键值对即可。但由于数据结构和查询优化等原因,数据库实际上可能需要读取 50 个键值对。在这种情况下,读放大为 50 / 10 = 5。
  • 写放大: 每写1byte数据带来n bytes的数据写盘,写放大为n。例如写1K数据需要写一个block,如果block是32K,那么写入放大就是32倍。像B+树的写放大就是叶子节点page size。
  • 空间放大:所占空间大小/实际数据量大小,空间放大主要与未回收的过期数据量(old version/deleted entries)相关,这个在LSM结构中是普遍存在的。
  • 临时空间:compaction任务运行时需要临时空间,compaction完成后旧数据才可以删除。与compaction任务的拆分粒度相关。
  • sorted 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构成。

run的解释:
Each run contains data sorted by the index key. A run can be represented on disk as a single file, or alternatively as a collection of files with non-overlapping key ranges.

tips: L0->L1 使用tiered compaction

image.png

Level compaction每层总大小有个固定的阈值
image.png

合并条件&合并方式

当level满足该层大设定的数据大小阈值时,触发compaction。数据合并到下一层的时候直接和下一层的数据合并形成一个sorted run。下图演示了level-compaction的过程,关键在于理解compaction构建的是一个有序run。level mapping为了确保一层只有一个sorted run需要在compaction时去除冗余数据,这个就会非常容易涉及这一层非常多的sst file,导致严重写放大。例如下面例子,为了写level 1的1号sst file,最坏情况下需要修改level 2的所有sst file。

image.png

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

优点&缺点

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

  • 较低程度空间放大(优点):同一层level内只有一个run,各个sst file之间没有数据重叠,所以冗余数据只发生在相邻level之间。
  • 较低程度读放大(优点):读盘次数每一层1次即可,每一层直接扫描一个有序的run即可。本质也是因为同一层内没有重叠数据,所以读放大较小。
  • 写放大(缺点):因为compaction的时候要生成sorted run,一份数据在多个层级内移动的时候会发生多次写,这也就产生了写放大

TIPS: 空间放大和读放大基本上是正相关的,冗余数据多意味着空间放大严重,读取会扫描到更多冗余数据,自然读放大问题也更加严重。反之亦然。

总结下Level-Compaction的核心特点主要是:

  • 每层只有一个sorted run
  • 满足层次设定大小阈值时触发compaction(一般是1比10递增阈值)
  • 跨层的sst file size相同
  • 写放大严重,没有太大的读放大、空间放大问题
  • 相比tiered compaction有更好读性能

tiered-compaction

tiered-compaction是根据每层设定的sstable个数阈值来触发compaction(每一层sst file的总个数是固定大小,但是每层的sst file固定大小都会大大增加)。下图[13] 展示了tiered-compaction合并流程,掌握关键点: compaction是追加数据的过程,同一层会产生多个sorted run
image.png

优点&缺点

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

  • 空间放大(缺点):由于各个层次内有多个run,有大量的数据冗余;此外高层次内的sst file文件比较大,很久可能都不会触发合并,这都导致了空间放大。这种空间放大 严重的时候会有10倍以上
  • 读放大(缺点):读取时因为扫描冗余数据导致读放大
  • 临时空间放大(缺点):主要是归并合并的时候临时空间的开销。tiering较粗粒度的sst file大小增加了合并时临时空间的开销。
  • 较低程度写放大(优点):compaction过程上层数据merge后的run直接append到下一层,相比level-compaction来说写放大程度较低。
总结下Tiered Compaction的核心特点主要是:
  • compaction是追加数据,每层有多个sorted run
  • 满足层次设定sst file个数阈值时触发compaction
  • 跨层的sst file size按阈值的sst file个数比例放大
  • 没有严重写放大问题,但是由于有较多冗余数据,会有严重空间放大、读放大问题(读取性能也差了)
  • 相比level compaction有更好写性能

Leveling和Tiered的trade-off

compaction的实现有很多变种和优化,本质上就是在读写性能上的trade-off。[18] 中的图很好表达了这一点:
image.png
工程实践上可以考虑tiering+leveling混合的方式。如果我们假设,近期数据是写密集型,远期数据是读密集型,可以在低level用tiering,高level用level compaction。像rocksDB就是level0用tiering。LSM的优化在学术界也是一个比较火热的议题,像[14][18]中提到的lazy leveling 就是混合了leveling compaction和tiered compaction的实现。有兴趣也可以了解下。

LSM和B+树的比较

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

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

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

参考资料