关于算法:从-RocksDB-看-LSMTree-算法设计

原创不易，转载请注明出处

前言

目前笔者自己正在基于 Pulsar 搭建公司外部的音讯平台，天然也对其底层存储做了一些钻研。Pulsar 应用 BookKeeper 作为存储层，BookKeeper 底层应用到了 RocksDB 来保留 Entry (BookKeeper 中的数据存储单元) 对应的地位索引。RocksDB 是我始终关注的存储引擎技术，因为之前在调研长久型 KV 存储的时候，发现支流开源的 pika/kvrocks，以及最终选用的云厂商的长久型 KV 存储服务，底层都是基于 RocksDB。还有赫赫有名的 TiDB，其存储引擎也是 RocksDB。

怀着好奇，我开始了对于 RocksDB 的学习，因为 RocksDB 个别用于底层开发，如果不是开发数据存储中间件，日常很难接触到，所以我决定先去学习 RocksDB 的数据结构设计：LSM 树。

本文先是介绍了 RocksDB 对于 LSM 树的实现，再总结了 LSM 树的设计思维，也类比了 Elasticsearch Lucene 的存储设计思维，最初将 LSM 树和常见的 B+ 树做了比照。

LSM 树 简介

LSM 树，全称 Log-Structured-Merge Tree。初看名字你可能认为它会是一个树，但其实不是，LSM 树实际上是一个简单的算法设计。这个算法设计源自 Google 的 Bigtable 论文（引入了术语 SSTable 和 memtable）。

基于 LSM 树算法设计实现的存储引擎，咱们称之为 LSM 存储引擎。在 LevelDB、RocksDB、Cassandra、HBase 都基于 LSM 树算法实现了对应的存储引擎。

上面咱们通过 RocksDB 的 LSM 树实现，来具体理解一下 LSM 树的设计思维。如果只想看 LSM 树的设计思维总结，能够跳转到最初的总结局部，私认为总结的还是不错的。

RocksDB LSM 树 实现

1. 外围组成

首先，先看看 RocksDB 的三种根本文件格式 memtable & WAL & SSTable。

下图形容了 RocksDB LSM 树的外围组成和要害流程步骤（读 & 写 & flush & compaction）。

1.1 memtable (active & immutable)

memtable 是 RocksDB 内存中的数据结构，同时服务于读和写；数据在写入时总会将数据写入 active memtable，执行查问的时候总是要先查问 memtable，因为 memtable 中的数据总是更新的；memtable 实现形式是 skiplist，适宜范畴查问和插入；

memtable 生命周期

当一个 active memtable 被写满，会被置为只读状态，变成 immutable memtable。而后会创立一块新的 active memtable 来提供写入。

immutable memtable 会在内存中保留，期待后盾线程对其进行 flush 操作。flush 的触发条件是 immutable memtable 数量超过 min_write_buffer_number_to_merge。flush 会一次把 immutable memtable 合并压缩后写入磁盘的 L0 sst 中。flush 之后对应的 memtable 会被销毁。

相干参数：

• write_buffer_size：一块 memtable 的 容量
• max_write_buffer_number：memtable 的最大存在数
• min_write_buffer_number_to_merge：设置刷入 sst 之前，最小可合并的 memtable 数（如果设置成 1，代表着 flush 过程中没有合并压缩操作）

1.2 WAL (write-ahead log)

WAL 大家应该都很相熟，一种有利于程序写的长久化日志文件。很多存储系统中都有相似的设计（如 MySQL 的 redo log/undo log、ZK 的 WAL）；

RocksDB 每次写数据都会先写入 WAL 再写入 memtable，在产生故障时，通过重放 WAL 复原内存中的数据，保证数据一致性。

这种设计有什么益处呢？这样 LSM 树就能够将有易失性（volatile）的内存看做是长久型存储，并且信赖内存上的数据。

至于 WAL 的创立删除机会，每次 flush 一个 CF（列族数据，下文会提）后，都会新建一个 WAL。这并不意味着旧的 WAL 会被删除，因为别的 CF 数据可能还没有落盘，只有所有的 CF 数据都被 flush 且所有的 WAL 无关的 data 都落盘，相干的 WAL 才会被删除。

1.3 SSTable (sorted string table)

SSTable，全称是 Sorted String Table，存在于磁盘，是一个长久化的、有序的、不可更改的 Map 构造，Key 和 Value 都是任意的 Byte 串。上文提到内存中的 memtable 在满足条件的状况下会执行 flush 操作

SSTable 的 文件构造如下：

既然对文件构造进行了划分，每块区域必定都有其作用：

• 数据块 Data Block，存储 有序 键值对，是 SSTable 的数据实体；为了节俭存储空间，并不会为每一对 key-value 对都存储残缺的 key 值，而是存储与上一个 key 非共享的局部，防止了 key 反复内容的存储（这种通过 delta encode 的形式节俭空间的形式在其余存储中间件底层中也很常见）。
• Meta Block，存储 Filter 相干信息，用于放慢 sst 中查问数据的效率；Filter 通过 Bloom Filter 来过滤判断指定的 data block 中是否存在要查问的数据。
• Meta Index Block，对 Meta Block 的索引，它只有一条记录，key 是 meta index 的名字（也就是 Filter 的名字），value 为指向 meta index 的地位；
• Index Block，index block 用来存储所有 data block 的相干索引信息。indexblock 蕴含若干条记录，每一条记录代表一个 data block 的索引信息；
• Footer，指向各个分区的地位和大小。Footer 是定长的，读取 SSTable 文件的时候，就是从文件开端，固定读取字节数，进而失去了 Footer 信息。Footer 中的信息，指明了 MetaIndexBlock 和 IndexBlock 的地位，进而找到 MetaBlock 和 DataBlock。

能够看到，SSTable 文件除了存储理论数据外，还有索引构造 和 Filter，来放慢 SST 的查问效率，设计十分精妙。

2. 其余的一些名词概念

Column Family（CF）

RocksDB 3.0 当前增加了一个 Column Family 的 feature，每个 kv 存储之时都必须指定其所在的 CF。RocksDB 为了兼容以往版本，默认创立一个“default”的 CF。存储 kv 时如果不指定 CF，RocksDB 会把其存入“default”CF 中。

RocksDB 容许用户创立多个 Column Family，这些 Column Family 各自领有独立的 memtable 以及 SST 文件，然而共享同一个 WAL 文件，这样的益处是能够依据利用特点为不同的 Column Family 抉择不同的配置，然而又没有减少对 WAL 的写次数。

如果类比到关系型数据库中，列族能够看做是表的概念。

3. 读 & 写

3.1 读操作

1. 在 active memtable 中查找；
2. 如果 active memtable 没有，则在 immutable memtable 中查找；
3. 如果 immutable memtable 没有，则在 L0 SSTable 中查找（RocksDB 采纳遍历的办法查找 L0 SSTable，为了进步查找效率会管制 L0 文件的个数）；
4. 如果找不到，则在残余的 SSTable 中查找（对于 L1 层以及 L1 层以上层级的文件，每个 SSTable 没有交叠，能够应用二分查找疾速找到 key 所在的 Level 以及 SSTable）

每个 SSTable 在查找之前通过 bloom filter 疾速判断数据是否存在于以后文件，缩小不必要的 IO。

RocksDB 为 SST 中拜访频繁的 data blocks 设置了一个读缓存构造 Block cache，并提供了两种开箱即用的实现 LRUCache 和 ClockCache。

3.2 写操作

1. 写操作会先写 WAL 文件，保证数据不失落；
2. 实现 WAL 写入后，将数据写入到 内存中的 active memtable 中（为了保障有序性，RocksDB 应用跳表数据结构实现 memtable）；
3. 而后等 memtable 数据达到肯定规模时，会转变成 immutable memtable，同时生成新的 memtable 提供服务；
4. 在满足落盘条件后，immutable memtable 会被合并刷入到硬盘的 SST 中；

顺带一提，默认状况下 RocksDB 中的写磁盘行为都是异步写，仅仅把数据写进了操作系统的缓存区就返回了（pageCache），而这些数据被写进磁盘是一个异步的过程。异步写的吞吐率是同步写的一千多倍。异步写的毛病是机器或者操作系统解体时可能丢掉最近一批写申请收回的由操作系统缓存的数据，然而 RocksDB 本身解体并不会导致数据失落。而机器或者操作系统解体的概率比拟低，所以大部分状况下能够认为异步写是平安的。

4. Compaction

LSM 树将离散的随机写申请都转换成批量的程序写申请（WAL + memtable），以此进步写性能。但也带来了一些问题：

• 读放大（Read Amplification）。依照下面【读操作】的形容，读操作有可能会拜访大量的文件；
• 空间放大（Space Amplification）。因为所有的写入都是程序写（append-only）的，不是在对数据进行间接更新（in-place update），所以过期数据不会马上被清理掉。

所以保护和缩小 SST 文件数量是很有必要的。RocksDB 会依据配置的不同 Compaction 算法策略，进行 Compaction 操作。Compaction 操作会删除过期 或者标记为删除 / 反复的 key，对数据进行从新合并来进步查问效率。

4.1 Level Style Compaction (default compaction style)

默认状况下，RocksDB 采纳 Level Style Compaction 作为 LSM 树的 Compaction 策略。

如果启用 Level Style Compaction，L0 存储着 RocksDB 最新的数据，Lmax 存储着比拟老的数据，L0 里可能存着反复 keys，然而其余层文件则不可能存在反复 key。每个 compaction 工作都会抉择 Ln 层的一个文件以及与其相邻的 Ln+1 层的多个文件进行合并，删除过期 或者 标记为删除 或者 反复 的 key，而后把合并后的文件放入 Ln+1 层。

Compaction 尽管缩小了读放大（缩小 SST 文件数量）和空间放大（清理有效数据），但也因而带来了写放大（Write Amplification）的问题（底层 I/O 被 Compaction 操作耗费，会大于下层申请速递）

RocksDB 还有反对的其余的 Compaction 策略。

4.2 Universal Compaction

• 只压缩 L0 的所有文件，合并后再放入 L0 层里；
• 指标是更低的写放大，并且在读放大和空间放大中 trade off；

具体算法本篇不深究；

4.3 FIFO Compaction

• FIFO 顾名思义就是先进先出，这种模式周期性地删除旧数据。在 FIFO 模式下，所有文件都在 L0，当 SST 文件总大小超过 compaction_options_fifo.max_table_files_size，则删除最老的 SST 文件。对于 FIFO 来说，它的策略十分的简略，所有的 SST 都在 Level 0，如果超过了阈值，就从最老的 SST 开始删除。
• 这套机制非常适合于存储时序数据。

⭐ LSM 树 设计思维总结

LSM 树的设计思维很有意思。我这里做下总结。

LSM 树将对磁盘的随机写入转化为了磁盘敌对型的程序写（无论机械磁盘还是 SSD，随机读写都要远远慢于程序读写），从而大大提高了写性能。

那么是怎么转化的呢？外围就是在内存中保护一个有序的内存表（memtable），当内存表大于阈值的时候批量刷入磁盘，生成最新的 SSTable 文件。因为自身 memtable 曾经保护了按键排序的键值对，所以这个步骤能够高效地实现。

写入内存表时先将数据写入 WAL 日志，用以在产生故障时，通过重放 WAL 复原内存中的数据，保障数据库的数据一致性。

在这种追加（append-only）写入模式下，删除数据变成了对数据增加删除标记，更新数据变成了写入新的 value，在同一个工夫数据库中会存在同个 key 的新值和旧值。这种影响被称之为 空间放大（Space Amplification）。

随着数据的写入，底层的 SSTable 文件也会越来越多。

读申请在这个模式下，变成了先在内存中寻找关键字，如果找不到则在磁盘中依照新 -> 旧查找 SSTable 文件。为了优化这种拜访模式的读性能，存储引擎通常应用常见的针对读的优化策略，比方应用额定的 Bloom Filter、读 Cache。

这种须要屡次读取的过程（或者说影响）被称之为 读放大（Read Amplification）。很显然，读放大会影响 LSM 树的读性能。

为了优化读性能（读放大），同时优化存储空间（空间放大），LSM 树通过在运行合并和压缩过程缩小 SSTable 文件数量，删除 有效（被删除或者被笼罩） 的旧值。这一过程被称之为 compaction。

然而 compaction 也会一些影响，在数据库的生命周期中每次的数据写入实际上会造成屡次的磁盘写入。这种影响被称之为写放大（Write Amplification）。在 写入沉重的应用程序 中，性能瓶颈可能是数据库能够写入磁盘的速度。在这种状况下，写放大会导致间接的性能代价：存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。

这也是我认为 LSM 引擎存储的一个毛病，就是 压缩过程有可能会烦扰到正在进行的读写申请。只管存储引擎尝试逐渐执行压缩而不影响并发拜访，然而磁盘资源无限，所以很容易产生申请须要期待磁盘实现低廉的压缩操作。对吞吐量和均匀响应工夫的影响通常很小，然而如果是高百分位状况下（如 P99 RT），有时就会呈现查问响应较长的状况。

上述是对 LSM 树的集体总结，一些没有提到实现细节的形象形容（比方 memtable、compaction），在理论的存储中都有对应的实现，细节可能不同，然而设计思维都是相似。

在本文具体提到的 RocksDB 实现中，写放大、读放大、空间放大，这三者就像 CAP 定理一样，无奈同时达到最优。为此 RocksDB 裸露了很多参数来让使用者进行调优，以适应更多的利用场景。这其中很大一部分工作是在写放大、读放大和空间放大这三个放大因子之间做好 trade off。

Elasticsearch Lucene 中的类 LSM 设计思维

ES 底层搜索引擎 Lucene 的 segment 设计思维和 LSM 树十分类似。也使用到了 WAL、内存 buffer、分段 merge 等思维。

一个文档被索引之后，就会被增加到内存缓冲区，并且 追加到了 translog。

随着以后分片（shard）的 refresh 操作，这些在内存缓冲区的文档被 flush 到一个新的 segment 中，这个 segment 被关上，使其可被搜寻，对应的内存缓冲区被清空。

随着数据的写入，还会触发 commit 操作，做一次全量提交，而后对应的 Translog 会被删除。（具体过程限于篇幅不赘述）。

segment 被 refresh 或 commit 之前，数据保留在内存中，是不可被搜寻的，这也就是为什么 Lucene 被称为提供近实时而非实时查问的起因。

Segment 中写入的文档不可被批改，但可被删除，删除的形式也不是在文件外部原地更改，而是会由另外一个文件保留须要被删除的文档的 DocID，保障数据文件不可被批改。Index 的查问须要对多个 Segment 进行查问并对后果进行合并，还须要解决被删除的文档，为了对查问进行优化，Lucene 会有策略对多个 Segment 进行合并，这点与 LSM 对 SSTable 的 compaction 相似。

这种机制防止了随机写，数据写入都是 Batch 和 Append，能达到很高的吞吐量。同时为了进步写入的效率，利用了文件缓存零碎和内存来减速写入时的性能，并应用日志来避免数据的失落。

⭐ LSM 树 vs B+ 树

讲到这里了，想想不如再和咱们常见的 B+ 树做一些比照。

设计理念不同

尽管像 LSM 树一样，B+ 树放弃按键排序的键值对（这容许高效的键值查找和范畴查问），然而两者设计理念齐全不同。

• LSM 树将数据库合成为可变大小的段，通常是几兆字节或更大的大小，并且总是按程序编写段。
• 相比之下，B+ 树将数据库分解成固定大小的块或页面，传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更靠近于底层硬件，因为磁盘也被安顿在固定大小的块中。

数据的更新和删除方面

• B(+) 树能够做到原地更新和删除（in-place update），这种形式对 数据库事务反对更加敌对，因为一个 key 只会呈现一个 Page 页外面；
• 但因为 LSM 树只能追加写（out-place update），并且在 L0 层的 SSTable 中会重叠，所以对事务反对较弱，只能在 compaction 的时候进行真正地更新和删除。

性能方面

• LSM 树的长处是反对高吞吐的写（可认为是 O(1)），这个特点在分布式系统上更为看重，当然针对读取一般的 LSM 树结构，读取是 O(n) 的复杂度，在应用索引或者缓存优化后的也能够达到 O（logN）的复杂度。
• B+ 树的长处是反对高效的读（稳固的 O(logN)），然而在大规模的写申请下（复杂度 O(LogN)），效率会变得比拟低，因为随着 insert 的操作，为了保护树结构，节点会一直的决裂和合并。操作磁盘的随机读写概率会变大，故导致性能升高。

通常 来说，咱们会说，LSM 树写性能会优于 B 树，而 B 树的读性能会优于 LSM 树。然而请不要疏忽 LSM 树写放大的影响，在进行性能断定是要更辩证的思考。

参考

1. 《设计数据密集型利用》第三章：存储与检索（强烈推荐浏览的一本书！！！）
2. https://github.com/facebook/r…
3. https://www.lxkaka.wang/rocks…
4. http://alexstocks.github.io/h…
5. https://cloud.tencent.com/dev…
6. https://www.elastic.co/guide/…