SSTable 原理

2018/11/27 Paper

介绍 SSTable 原理和 LSM Tree, Bigtable整体介绍可见Bigtable论文阅读总结 — langrx

SSTable 起源

SSTable 最早来自于 Google 的 Bigtable 论文,论文中对 SSTable 的描述如下:

An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Operations are provided to look up the value associated with a specified key, and to iterate over all key/value pairs in a specified key range. Internally, each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory, which allows us to perform lookups and scans without touching disk.

通过以上描述,我们可以把 SSTable 抽象为以下结构,每个 SSTable 包含了很多按照 key 排序的 key-value 对,key 和 value 都是任意的字节数组。SSTable 可以方便的支持基于 key 的查找和范围扫描。SSTable 会把数据分成块进行存储,并在 SSTable 文件尾部保存块索引(Block Index), 块索引记录每个块结束的 key 及对应的offset。块索引一般会在 SSTable 打开的时候载入内存。每次读取 SSTable 的时候,在内存中找到对应的块,再进行一次磁盘访问,读取到块中的数据。当然,把 SSTable 大小限定在可以加载进内存的大小,每次直接加载进内存访问也是一种方法。

在后续很多SSTable的实现中,每个块内部也都添加了索引,称为行索引( Row Index ), 最简单的行索引类似于块索引,记录 row key 及对应的 offset 即可,这样在块内读数据的时候二分查找可以快速定位行的位置。RocksDB 实现一种带压缩的行索引,如图所示。根据每行公共前缀进行压缩,公共前缀称为以重启点的形式存在块尾部,重启点包含公共前缀和以该前缀开始的第一行的offset,这样读取数据的时候找到最长的公共前缀对应的重启点,直接从重启点对应的offset开始查找即可。

由于 SSTable 在磁盘中是有序的,数据更新和删除是非常困难的,如果你需要这样做, 你可以把每个 SSTable 的大小控制在可以直接 map 到内存中,从而方便随机的读写。Bigtable 是没有这么做的,具体 Bigtable 的做法可以参考后文对 Tablet Server 的描述。

论文中 SSTable 是 Tablet 的重要组成部分,Tablet 的工作原理如图所示:

  • 写操作:Tablet 把响应的操作写入操作日志(tablet log),然后将具体的内容写入内存中 MemTable

  • 读操作:读操作需要同时读 Memtable 和 SSTable,将结果合并返回。Memtable 和 SSTable 都是按照 key 有序的,可以快速的进行类似归并排序的合并。

  • Minor Compaction:随着写请求的不断增多,Memtable 在内存中的空间不断增大,当 Memtable 的大小达到一定阈值时,Memtable 被 dump 到 GFS 中成为不可变的 SSTable。

  • Merging Compaction:随着 Memtable 不断的变为 SSTable,SSTable 也不断增多,意味着读操作需要读取的 SSTable 也越来越多,为了限制 SSTable 的个数,Tablet Server 会在后台将多个 SSTable 合并为一个

  • Major Compaction:Major Compaction 是一种特殊的 Merging Compaction,只把所有的 SSTable 合并为一个 SSTable,在 非 Major Compaction 产生的 SSTable 中可能包含已经删除的数据,Major Compaction 的过程会将这些数据真正的剔除掉,避免这些数据浪费存储空间。

另外 Bigtable 论文还提出很多 SSTable 相关优化:

  • 压缩,Locality Group Compression:SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取,类似上文提到 RocksDB 的前缀压缩。

  • 缓存,Scan Cache & Block Cache:SSTable 写入磁盘后是很少变化的,因此 Cache 机制可以邮箱提高读操作的效率。Scan cache 是一个相对高级别的缓存,缓存 SSTable Scan 操作返回的结果集。Block Cache 缓存的是 SSTable 从 GFS 读取数据时对应 Block 的缓存。

  • 索引,Bloom filters:正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,一个针对每一个 SSTable 添加 Bloom Filter,当我们确定一个 SSTable 不包含需要的数据时,我们直接不访问对应的 SSTable。

  • 分裂和合并 :SSTable 需要根据大小不断的进行分类和合并,当分裂的时候,生成一个新的 Memtable,负责新的数据段的写入。原来的 Memtable 保持不变,当原来 Memtable 需要落盘的时候,根据 key 决定落入哪个 SSTable。Bigtable 采用了三级索引的结构,子 Tablet 的分裂只需早父 Tablet 插入一条数据并更新对应的范围即可。所以 Tablet 的分裂和合并实际上不涉及磁盘数据的调整,可以很快的完成。

LSM Tree

其实,Tablet是 LSM Tree 的一种实现,参考 3 给出了 LSM Tree 的论文。LSM Tree 是一种不同于 B+ Tree 的存储结构。它基于一个事实就是磁盘的顺序访问速度远大于随机访问深度,如图所示。甚至于磁盘的顺序访问速度大于内存的随机访问速度。尤其是对于越来越成为主流的 SSD 硬盘,对随机读的支持非常好,但是随机写就差很多。因此 LSM Tree 会在内存中维护一个有序的 Tree C0 (Bigtable 的 Memtable), 当 C0 的大小满足一定条件后刷盘(Big Table 的 SSTable)。数据一旦写入磁盘,就是 immutable 的,数据的更新和删除通过插入新的数据实现。为了避免磁盘中的文件越来越多,LSM Tree 也需要周期性的将磁盘中的文件进行合并。

LSM Tree 的索引机制和 B+ Tree 的索引机制是明显不同的,B+ Tree 为所有的数据维护了一个索引,LSM Tree 则是为每个 磁盘文件维护了一个 Index。

Level Compaction

Bigtable 论文发表之后,这套基于 LSM Tree 的文件管理机制被各种单机的(LevelDB, RocksDB, MyRocks)和分布式的(HBase, Cassandra)存储系统作为底层的存储引擎。在这众多的实现中,不得不提就是 LevelDB。LevelDB 同样是 Google 开发,基于 Bigtable 的 Tablet 机制并进行了改进。LevelDB 的一个重要改进就是 Level Compaction,这也可能是其之所以叫 LevelDB 的原因。现在基于 LSM Tree 的存储系统像 RocksDB,Cassandra 等一般都会支持多种 Compaction 的配置。RocksDB 是基于 LevelDB,由 Facebook 领导独立于 LevelDB 进行了开发。相比于 RocksDB,LevelDB 已经进入了半维护的状态,所以生产环境还是建议使用 RocksDB 而不是 LevelDB。接下来本文介绍一下 Level Compaction。

上文说到 SSTable 包含两类 Compaction:Minor Compaction 和 Merging Compaction,Major Compaction 是一种特殊的 Merging Compaction。Level Compaction 实际上也由这两种 Compaction 组成,只不过进行了分层。如图所示。Level 0 (后文简称 L0)的文件对应于 Minor Compaction,由 内存中的 Memtable 直接 dump 到磁盘生成,所以在 L0 中,一个 key 是可能存储在不同 SSTable 中的。Ln ( n > 1) 层的 SSTable 由低层的 SSTable 合并而来。

除了 L0,每一层的 SSTable 都基于 key 进行了 partation,所以在 Ln (n > 1)中,一个 key 是不会存在于多个文件中的,所以层内不包含冗余的数据。同时,partation 另外一个好处是当读取数据时,根据 key 就可以知道需要读取哪些 SSTable,从而减少需要读取 SSTable 的个数。

L0 层的文件个数一般有一个限制,当 SSTable 个数超出这个限制时将会进行 Level Compaction。除 L0 层外,每一层都有一个空间大小上限,当文件大小超出这个上限时进行 Level Compaction。

进行 Level Compaction 时,至少从 Ln-1 层中选出一个SSTable 与 Ln 层的相关 SSTable 进行合并,如果合并后 Ln 层也超出了大小限制,则继续与 Ln+1层进行合并。由于 Ln(n>1) 层的 key 都是 partation 过的,所以多个 SSTable 可以可以并发的 Compaction。为了提高 L0层合并的并发性,一般也会现将 L0 层的文件先划分为多个文件,每个文件分别进行合并

合并时究竟应该选择哪个 SSTable 进行合并以及每层的 SSTable 空间上线是多大,不同的系统有不同的实现,RocksDB 的实现细节可见参考5。

Lucene

由于工作内容的关系,本人经常会涉及 Elasticsearch 相关内容,Elasticsearch 是基于 Lucene 的分布式搜索引擎。学习 LSM Tree 的过程让我不断联想到 Lucene 的工作流程,仔细梳理一下发现,其实 Lucene的存储也是一种 LSM Tree 的实现,不同于 Bigtable 的是,Bigtable 存储在磁盘上的是有序的 key-value 集合,Lucene 存在磁盘上的是倒排索引,两者都可以很好的支持合并操作。下边本文介绍一下 Lucene 的工作流程,读者也可以对比一下 Lucene 的工作流程和 LSM Tree。

当新增加一片文档时,lucene 会将内容同时写入 Translog 和 In-memory Buffer 并返回,Translog 类似于 Bigtable 的 Tablet log,都是操作日志,具有很好的写入性能。默认情况下,每隔1s Lucene 将 In-memory Buffer Refresh 到磁盘缓存中生成一个 segment(图中灰色柱体所示),从而可以保证数据可以被读到。

随着 segment不断的增多,lucene 将 segment 不断的进行合并,lucene 提供了多种可配置的合并策略。Lucene 不断将小 segment 合并为大 segment, 并将合并前的小 segment 删除。默认情况下,当大 segment大小超过512M时,将 segment 进行 flush 操作,segment 从磁盘缓存中被持久化到磁盘中,删除 Translog 中对应的数据,这个操作成为 commit。Lucene 的合并操作 可以在磁盘缓存中的 segment 和磁盘中已经 commit 的 segment 之间进行。从上述过程可以看出,其实 Lucene 就是一个 LSM Tree 的存储结构。

参考

  1. SSTable and Log Structured Storage: LevelDB - igvita.com

  2. MyRocks A RocksDB storage engine with MySQL MyRocks

  3. LSM Tree

  4. Log Structured Merge Trees - ben stopford

  5. Leveled Compaction · facebook/rocksdb Wiki

Search

    Table of Contents