SSTable & LSM Tree

2018/11/27 Middleware

介绍 SSTable & LSM Tree 关系,原理和使用

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 在文件中对应的 offset,方便快速读取数据。

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

论文中 SSTable 主要在 Tablet Server中使用,所以首先介绍一下 Bigtable Tablet 的工作原理,Tablet 的原理图如图所示。Tablet 使用 GFS 作为底层存储,每个Tablet 包含多个 SSTable。

  • 写操作:Tablet Server 把响应的操作写入tablet log。Tablet 会把多个操作以 batch 的形式一次性写入内存的 memtable 中。

  • 读操作:读操作会同时读 memtable 和 SSTable,将结果合并返回。memtable 和 SSTable 都是按照字典序排序的,因此可以很方便的将结果合并。

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

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

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

以上是 Bigtable Tablet Server 的工作原理,但是很多 SSTable 的细节在上述的工作原理是没有体现出来的,在 Bigtable 的 Refinements 一节有很多 SSTable 相关的描述,可以让我们更好的了解 SSTable

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

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

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

  • Immutability:SSTable 一个非常重要的特性就是 Immutability,所以不需要并发控制,Tablet Server 唯一需要并发控制的就是 memtable。当 Tablet Server 分裂时,不需要为每个子 Tablet 分割数据,只需要让他们共享父 Tablet 的数据即可。

LSM Tree

其实,Bigtable Tablet Server 是 LSM Tree 的一种实现,参考 3 给出了 LSM Tree 的论文。LSM Tree 是一种不同于 B+ Tree 的存储结构。它基于一个事实就是磁盘的顺序访问速度远大于随机访问深度,如图所示。甚至于磁盘的顺序访问速度大于内存的随机访问速度。很多数据库都利用磁盘的这个特性做了 WAL 机制提升数据的写性能。但是如果不对数据加以重组,顺序写入的文件对于读操作的友好性是非常差的。因此 LSM Tree 会在内存中维护一个有序的Tree C0 (Bigtable 的 Memtable), 当 C0 的大小满足一定条件后刷盘(Big Table 的 SSTable)。数据一旦写入磁盘,就是 immutable 的,数据的更新和删除通过插入新的数据实现。为了提升数据的读性能,每个写入磁盘的文件会增加一个 index,记录 key 及 key 在文件中的 offset,方便快速查找数据(这个 index 机制也被用在 kafka partation 的索引)。同时为了避免没有必要的磁盘访问,也会为每个磁盘的文件添加 Bloom Filter。为了避免磁盘中的文件越来越多,LSM Tree 也需要周期性的将磁盘中的文件进行合并。LSM Tree 的索引机制和 B+ Tree 的索引机制是明显不同的,B+ Tree 为所有的数据维护了一个索引,LSM Tree 则是为每个 File 维护了一个 Index。

总的来说,LSM Tree 的写性能高于 B+ Tree,读性能低于 B+ Tree。LSM Tree 适合大量数据存储的情况,尤其是写多读少的场景。关于更多 LSM Tree 和 B+ Tree 的对比,本文不展开叙述。

LevelDB,RocksDB,Cassandra,etc…

##

Bigtable 论文发表之后,这套基于 LSM Tree 的文件管理机制被各种单机的(LevelDB, RocksDB, MyRocks)和分布式的(HBase, Cassandra)存储系统作为底层的存储引擎。在这众多的实现中,不得不提就是 LevelDB。LevelDB 同样是 Google 开发,基于 Bigtable 的 Tablet Server并进行了改进,很多人把 LevelDB 当做 Bigtable Tablet Server 的开源实现去更好的了解 Bigtable。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,经过 Major Compaction 产生的 SSTable 不包含冗余的数据。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 层的文件先划分为多个文件,每个文件分别进行合并 ing

合并时究竟应该选择哪个 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