汀的知识碎片

8. LSM派系存储引擎

87 min read

第 8 章 LSM 派系存储引擎

笔者把各种基于 LSM 实现的存储方案均归为 LSM 派系存储引擎。那 LSM 派系的存储引擎各自是如何读/写问题的呢？本章就来回答这个问题。

8.1 LSM Tree 存储引擎

LSM Tree 在工程上的一些典型应用有 LevelDB、RocksDB、PebblesDB、HBase、Cassandra、AsterixDB、Badger 等。本节将介绍近些年兴起的一种 LSM Tree 的改进方案——KV 分离存储技术 WiscKey。掌握了 WiscKey 的核心思路后，会更加深入地理解 LSM Tree 的读/写空间放大的问题。

8.1.1 LSM Tree 工程应用

目前在工程上 LSM Tree 的应用已经非常广泛，比如 RocksDB、PebblesDB、HBase、Cassandra、AsterixDB 等。这些项目有些是单机存储引擎，有些则是分布式的存储系统。而这些分布式系统从单机角度来看，它们的数据存储方案无一例外都是借助于 LSM Tree 来构建的。下面分别对它们进行简要的介绍。

1. RocksDB

RocksDB 保留了 LevelDB 的基本架构和接口，它同样是一个嵌入式的高性能 KV 存储引擎。目前 RocksDB 存储引擎已经广泛应用于各种存储系统，比如 Cassandra、TiDB、CockroachDB、Flink 等。

RocksDB 在 LevelDB 的基础上添加了大量的新特性且做了优化工作。同时，RocksDB 中采用了插件式的架构，这使得可以通过开发不同的插件来使其适用于各种业务场景。下面简单介绍下 RocksDB 在 LevelDB 上添加的重要特性和做的一些优化。

1）新特性

在新特性方面，RocksDB 新增了列族（Column Family, CF）、压缩过滤器（Compaction Filter）、压缩模块插件化、MemTable 插件化、SSTable 插件化、数据解析工具等诸多特性。

  • 列族：一个列族里是一系列 KV 组成的数据集。所有的读/写操作都需要先指定列族。每个列族有自己的 MemTable、SSTable 文件，所有列族共享 WAL log、Current、Manifest 等文件。用户可以基于 RocksDB 任意构建不同的列族，通过引入列族可以非常方便地把 KV 数据按照不同的业务逻辑或者业务场景进行隔离存储。
  • 压缩过滤器：RocksDB 提供的压缩过滤器功能，可以让用户指定过滤条件，在数据压缩时将不符合条件的键值对过滤掉。
  • 压缩模块插件化：RocksDB 通过插件的方式提供了对多种压缩算法的支持，比如 Snappy、BZip、Zlib、LZ4、ZSTD 等，而 LevelDB 仅支持 Snappy。
  • MemTable 插件化：在 LevelDB 中 MemTable 的实现是一个跳表，因此它非常适合快速写入和范围扫描。而在 RocksDB 中通过插件化的思想对 MemTable 做了扩展，一个 MemTable 的实现既可以是跳表，也可以是 Hash 表、数组等。这使得 MemTable 既可以支持更高性能的写入，也可以根据不同的业务场景灵活选择不同的实现。
  • SSTable 插件化：RocksDB 对 SSTable 的格式也做了插件化处理，用户可以自定义格式，以使其适配不同的硬件存储介质（HDD、SSD）。
  • 数据解析工具：RocksDB 还提供了一些工具，用来离线解析 SSTable 文件中的 KV 数据等内容。而 LevelDB 则只能通过程序读取 SSTable 文件来获取 KV 数据。
2）优化项

RocksDB 对写入及压缩操作都做了一些优化，比如多 ImmuMemTable、多线程压缩、压缩限速、Read-Modify-Write 等。

  • 多 ImmuMemTable：在 LevelDB 中只有一个 MemTable，当一个 MemTable 被写满后，会将当前的 MemTable 关闭使其变成只读的 ImmuMemTable，同时再打开一个新的 MemTable 用来接收写请求。如果有大量的写请求进来，新的 MemTable 会迅速再被写满，此时，如果 ImmuMemTable 还未完成压缩的话就会影响写入。在 RocksDB 中通过一个队列来管理 ImmuMemTable，以此解决这个问题。
  • 多线程压缩：在 LevelDB 中支持单个线程处理压缩过程，而在 RocksDB 中通过划分不同的线程池来实现 Major 压缩和 Minor 压缩。当不同层的压缩操作没有涉及重叠时，可以并行执行压缩。
  • 压缩限速：在基于 LSM Tree 的存储引擎中，压缩操作通常会消耗大量的系统资源（如 CPU、磁盘等），从而对查询性能产生负面影响，同时压缩的频率直接取决于写的速率。因此为了缓解该问题，RocksDB 提供了限速功能，它基于漏桶（Leaky Bucket）机制来控制压缩操作对磁盘的写入速度。其基本思想是维护一个存有许多令牌（Token）的桶，令牌的生成由填充速度控制。在执行每次压缩操作之前，压缩操作都必须请求一定数量的令牌。因此压缩操作所产生的磁盘写入速度将受指定的令牌填充速度的限制。
  • Read-Modify-Write：在实践中经常会碰到一种业务逻辑的处理，许多应用程序通常需要先读取现有的值然后再更新它们。为了有效地支持这种操作，RocksDB 支持一种叫作 Read-Modify-Write 的操作。RocksDB 允许用户直接将增量值（Delta Value）写入内存，从而有效避免读取原始记录。然后在处理查询请求时，将增量值与基线值根据用户提供的组合逻辑进行合并。同时，RocksDB 也允许在合并过程中进一步将多个增量值合并在一起，以提高后续的查询性能。

综上就是 RocksDB 在 LevelDB 的基础上添加的特性和做的优化处理。关于这部分更多详细的内容读者可参考 RocksDB 的官方文档。

2. PebblesDB

PebblesDB 是 CockroachDB 团队受 LevelDB/RocksDB 启发，采用 Go 语言开发的另一种基于 LSM Tree 的 KV 存储引擎。根据官方文档的说明，它保持了和 RocksDB 一样的文件格式，以及相似的访问接口和实现细节，同时在此基础上扩展了 RocksDB 的一些功能，但是并没有完全支持 RocksDB 的所有功能。因为它主要的目标是为 CockroachDB 数据库提供数据存储服务，并不是替代 RocksDB。

在介绍 PebblesDB 的论文“PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees”中提到，受到跳表的启发，将跳表和 LSM Tree 结合在一起，提出了分段 LSM Tree——FLSM（Fragmented Log-Structured Merge Trees）。FLSM 通过引入 guard 来组织日志，同时避免相同层上数据的重叠。因此 FLSM 极大地减少了数据压缩/合并的频率，从而减少了因压缩/合并而产生的写 I/O，有效地缓解了写放大。除此之外，PebblesDB 还采用了其他优化技术，如并行查询（Parallel Seeks）、布隆过滤器等来减少 FLSM 引入的开销。

关于 PebblesDB 更多的详细内容，感兴趣的读者请自行查阅相关资料。

3. HBase

HBase 是 Apache 旗下的 Hadoop 生态内的一个基于列式存储的分布式数据库。HBase 的实现原理借鉴了 Google 发表的 Bigtable 论文。它将存储的数据集以 Region 为单位进行划分，每个 Region 内部的数据采用 LSM Tree 来进行管理。

在 HBase 中，LSM Tree 的数据合并策略采用了之前介绍的分层合并策略（Tiering Merge Policy）。此外，HBase 还实现了一些分层合并策略的变形。例如，它内部实现了一种基于探查的合并策略（Exploring Merge Policy），该策略会检查所有可合并的组件序列，并选择写开销最小的组件序列。这种合并策略比基本的分层合并策略更健壮，特别是在组件大小不规则的情况下。因此，它作为 HBase 的默认合并策略之一。另外，HBase 还实现了一种基于日期的分层合并策略（Date-tiered Merge Policy），该策略专门用于管理时间序列数据。它根据组件的时间范围而不是大小来进行合并，从而有效处理时态查询。此外，HBase 还支持 Region 的动态分裂和合并，可以根据给定的工作负载对系统资源进行弹性管理。例如，当一个 Region 超过其阈值后，系统会将其拆分为两个较小的 Region。同时，如果系统中存在多个较小的 Region，则会根据具体情况将它们合并。这个特性类似于之前介绍过的 B+ 树中节点的分裂和合并。

4. 其他

还有许多项目也是基于 LSM Tree 构建的，比如 Apache 旗下的 Cassandra 和 AsterixDB 等。这些分布式系统项目在单机的存储结构上都采用了 LSM Tree 的思想设计，并结合一些具体的适用场景添加或支持一些新的特性，例如二级索引等。由于篇幅有限，这里不再一一介绍，感兴趣的读者请自行搜索相关资料进行深入学习。

也许读者对 LSM Tree 的内部存储架构有些困惑。例如，SSTable 是如何进行分区合并的？合并过程又是如何实现的？第 9 章将以 LSM Tree 的经典实现 LevelDB 为例，详细分析其内部的运行机制和源码实现。

8.1.2 LSM Tree 的KV 分离存储技术WiscKey

随着技术的不断升级和迭代，SSD 逐渐盛行起来。和 HDD 相比，SSD 在成本降低很多的同时，读/写性能有大幅提升。在 SSD 中，随机读/写和顺序读/写的差距没有 HDD 那么显著。尤其是在 SSD 上的随机读采用并发请求时，在某些场景中可以取得接近顺序读的总吞吐量。这意味着最初为 HDD 考虑设计的 LSM Tree 在 SSD 作为存储介质时并不一定是最优的。于是，提出了一种为 SSD 专门优化的 LSM Tree—WiscKey。

1. WiscKey 想法的来源

在 LSM Tree 的压缩过程中，由于 K 和 V 数据是存放在一起的，这也就意味着排序过程中 K 和 V 都会参与。而实际上不管是点查询还是范围查询，只要能保证 K 有序，就可以实现这两种查询。在绝大部分场景中，通常 K 是小于 V 的。这也就意味着，如果压缩过程只对 K 进行，那么就可以大大减少排序过程中数据的总量。WiscKey 的设计思路正是来源于此。

WiscKey 认为“将 K 和 V 分离存储，压缩过程只对 K 进行排序，而不需要 V 参与”。

2. WiscKey 的主要内容

WiscKey 的结构如图 8-1 所示。将 K 和 V 分离后，V 通过 SSD 上单独的 Log 文件（value Log, vLog）存储，LSM Tree 中存储的数据是 <key, v_addr>。其中 v_addr 是指 V 在 vLog 中存储的位置（由于 V 是变长数据，因此 v_addr 一般由 offset 和 length 两部分组成，offset 是 V 写入 vLog 中的位置，length 则是 V 的长度。只要确定这两部分信息就可以完整地获取 V）。将 K 和 V 分离后，可以发现 LSM Tree 存储的是索引数据，而实际的数据存储在 vLog 中。

图 8-1 说明：图中展示了 WiscKey 的结构：左侧是 LSM Tree，存储 <key, v_addr>；右侧是 vLog，存储 <key, value>。v_addr 记录 value 在 vLog 中写入的位置 offset 及 value 的长度 length。箭头表示 KV 分离存储关系。

（1）WiscKey 的读/写操作

在 WiscKey 中，读/写请求的处理与之前的 LSM Tree 有些不同。写操作分为两个步骤：首先将 V 追加到 vLog 中，并记录 V 在 vLog 中的位置；追加成功后，再将索引信息 <key, v_addr> 写入 LSM Tree。索引信息写入 LSM Tree 的逻辑与 LSM Tree 的写操作相同。

在查询时，WiscKey 首先需要查询 LSM Tree 以获取索引信息 v_addr。读取 v_addr 的过程就是读取 LSM Tree，此处就不再重复说明了。成功从 LSM Tree 中获取 v_addr 后，就可以通过 v_addr 中记录的 V 的写入位置 offset 和 V 的长度 length 来读取 V 的实际内容。

（2）WiscKey 的性能分析

在 WiscKey 论文“WiscKey: Separating Keys from Values in SSD-Conscious Storage”中提到，相较于 LevelDB 等其他 LSM Tree，存储相同数据量，WiscKey 的 LSM Tree 要小得多。这是因为 WiscKey 将 K 和 V 分离存储。V 的大小并不会明显影响 WiscKey 的 LSM Tree 的大小，因此 WiscKey 能有效地减少写放大问题。同时，这也意味着在提升写性能的同时，能降低写放大，减少 SSD 的擦写次数，延长 SSD 的使用寿命。

此外，WiscKey 较小的 LSM Tree 也能降低读放大，提升读性能。在查询索引信息时，由于 WiscKey 的 LSM Tree 较小，这意味着相较于 LevelDB，WiscKey 只需要搜索较小层级和数量的 SSTable 文件，同时大部分数据可以缓存在内存中，减少对磁盘的访问次数。因此，对于大多数查询而言，可以忽略索引查询的开销，只需进行一次随机读取 vLog 以获取 V。总体而言，WiscKey 的读取性能应该更好。该论文还举了一个例子，假设 K 为 16B、V 为 1KB、整个数据库大小为 100GB，那么 WiscKey 的 LSM Tree 大小约为 2GB（假设用 12B 开销存储 V 的索引 v_addr），这意味着 WiscKey 的 LSM Tree 可以轻松地完全缓存在服务器的内存中。

尽管 WiscKey 的实现思路非常清晰，同时解决了读和写的放大问题，但在实现时仍然会引入一些新的问题。

（3）WiscKey 的挑战与优化

在 WiscKey 中，索引信息有序存储在 LSM Tree 中，而 V 则无序存储在 vLog 中。当处理范围查询请求时，为了获取 V，需要随机读取 vLog，即随机 I/O。此外，KV 的分离存储在 vLog 的垃圾回收和数据一致性方面也存在挑战。正是由于 KV 的分离存储，WiscKey 对 vLog 的更新机制和 LSM Tree 的 WAL Log（WAL 日志）提供了新的尝试。下面分别对上述内容进行介绍。

1）并发范围查询。

在原生的 LSM Tree 实现中，由于同一条键值对 K 和 V 的数据存储在一起，同时所有数据按照 K 进行有序存储。这使得在范围查询时，可以顺序读取 SSTable 中的键值对数据。而在 WiscKey 中，由于 K 和 V 分离存储，这意味着索引的读取可以通过顺序读取 SSTable 来实现，而对 V 的读取则大多数情况下需要随机读取 vLog。在 SSD 上，单线程的随机读性能远低于顺序读性能。然而，可以通过并行发出随机读请求来充分利用 SSD 设备内部的并行性，使其随机读取的性能接近顺序读取的性能。

在范围查询时，WiscKey 利用 SSD 设备并行 I/O 的特性，提前并发随机预读取范围查询区间内的 V 值，以提升范围查询的性能。WiscKey 会追踪范围查询的访问方式，当检测到范围查询时，会从 LSM Tree 中读取一系列的索引信息，并将这些索引信息添加到队列中。后台会通过多线程并发地获取队列中的索引信息，并从 vLog 中读取对应的 V 值存放到内存中。这种并发随机预读取的机制，有效地提升了 WiscKey 中范围查询的性能。

2）vLog 垃圾回收。

在原生的 LSM Tree 中，旧数据或被删除的数据不会立即被清理，而是在数据压缩期间回收。在 WiscKey 中，索引信息保存在 LSM Tree 中，因此可以在压缩期间清理索引信息。实际的 V 数据存储在 vLog 中，因此随着系统运行时间的增长，vLog 中旧的、无效的数据也会越来越多，因此需要为 vLog 设计一种垃圾回收机制，用于清理无效数据并释放空间，减少空间放大。

其中一种简单的垃圾回收机制是通过全量遍历 WiscKey 中的 LSM Tree 来实现的。通过遍历，可以获取每条数据的索引信息，然后从 vLog 中读取数据，并写入新的 vLog 文件中。通过一次全量遍历，可以筛选出有效的数据，最后直接清除旧的 vLog 文件以释放空间。这种方式固然可行，但在存储大量数据的场景下，一次垃圾回收的执行过程非常耗时，操作繁重，对系统资源的消耗较大。

上述方式更适合离线过程中的数据回收。而 WiscKey 需要一种轻量级的在线垃圾回收方式，希望垃圾回收能间断执行。为了实现这一目标，WiscKey 对 vLog 的数据格式进行了改进。在 vLog 中，不仅存储了 V 的值，还存储了 K 的值。由于 K 和 V 通常是变长数据，因此按照之前介绍的 TLV 格式进行存储。首先，用固定长度的空间存储 K 和 V 的长度，然后紧接着存储 K 和 V 的实际值。其次，对 vLog 文件进行划分，指定 head 和 tail 两个位置，有效的数据存储在 head~tail 的范围内。在追加数据时，总是从 head 位置往后追加；在进行垃圾回收时，则总是从 tail 位置开始处理。数据查询也限定在该范围内。改进后的 vLog 布局结构如图 8-2 所示。

图 8-2 说明：图中展示了改进后的 vLog 布局结构。vLog 中按顺序存储 ksize, vsize, key, value 等字段，整体用 head 和 tail 指针划定有效范围。tail 和 head 信息保存在 LSM Tree 中。

通过按照上述结构设计后，一次垃圾回收的过程如下。首先从 tail 位置开始按照块（一般是按照块读取，通常是 1MB）依次读取数据到内存中，然后解析出来对应的 K 和 V。得到 K 以后，再在 LSM Tree 中查找 K 对应的索引信息，判断该条数据是否有效。如果该条数据有效，则会将该条数据追加到 vLog 的 head 位置并更新索引信息。当处理完以后就会释放掉之前的块并更新 vLog 的 tail 位置（tail 信息也是存储在 LSM Tree 中，格式为 <tail，tail-vLog-offset>）。在这个过程中为了避免垃圾回收过程中系统发生异常而造成数据的丢失，WiscKey 确保在释放 vLog 空间之前将新添加的有效的 V 和 tail 位置进行持久化。在将有效的 V 追加到 head 位置后，它会对 vLog 执行 fsync() 刷盘操作，然后将索引信息和当前的 tail 信息再同步地写入 LSM Tree 中。上述操作都成功后就会释放 vLog 中的空闲空间。

WiscKey 的垃圾回收通常是定期或者按照指定阈值的方式在线执行。此外，它也可以离线执行。在大容量的存储空间、同一数据删除/更新少的情况下垃圾回收的触发都比较低频。

3）数据一致性。

在 WiscKey 中，数据的写入过程分为两个阶段：第一阶段往 vLog 中写 V，第二阶段往 LSM Tree 中写索引。因此系统在写操作执行过程中发生崩溃的情况下，数据的一致性可以分为以下几种情况来讨论。

  • 情况 1：写 vLog 失败。这种情况下因为 vLog 直接写失败了，不管是 V 的数据从未写入，还是部分写入 vLog，还是全部写入 vLog 但未来得及更新索引失败。该条数据在 LSM Tree 中是不存在索引的，用户无法读取到该条数据。该条数据在 vLog 中就是一条无效的数据，它会在将来垃圾回收的过程中被清理掉。这种情况下的 WiscKey 的数据一致性是得到保证的。
  • 情况 2：写 vLog 成功、写 LSM Tree 失败。在这种情况下，vLog 数据已经写成功，但在往 LSM Tree 中写入索引的过程中失败了。写 LSM Tree 失败的情况主要是指写 LSM Tree 的 WAL Log 失败了。因为只要 WAL Log 写成功其实在 LSM Tree 就已经认为是成功了，后面恢复时可以根据 WAL Log 数据进行恢复。所以这种情况下实际上还是等价于情况 1。
  • 情况 3：写 vLog 成功、写 LSM Tree 成功。情况 3 是最复杂的，这种情况下看起来 vLog 和 LSM Tree 都写成功了。但需要额外的一些措施来保证数据的一致性。通常情况下，在执行查询时，当获得索引信息后首先要验证索引信息中记录的 V 的位置是否在 vLog 的有效范围内（head~tail），当位置合法后再根据位置读取对应的数据，读取到数据后再验证数据中存储的 K 是否和索引中的 K 一致，如果不一致则检查失败。上述检查但凡失败都会认为该条数据在系统崩溃中丢失了。它会从 LSM Tree 中将索引信息删除，然后返回查询的数据不存在。另外，还可以通过对写入 vLog 中的每条键值对数据增加校验和等方式进行额外验证。

4）vLog 的更新优化。

在 WiscKey 的论文中提到，如果对于每次的添加操作都通过 write() 系统调用将数据追加到 vLog 中时，在写密集型的场景中，大量小的写操作引起的频繁的系统调用会带来明显的开销。为了避免这种情况，WiscKey 在内存中对要写入 vLog 的数据提供了一个缓冲区。写入 vLog 中的数据会先写入缓冲区，当缓冲区中的数据超过一定阈值或者用户手动触发同步操作时才会写入 vLog 中。通过利用缓冲区，WiscKey 有效地减少了 write() 系统调用的次数。这种方式带来的问题是需要考虑系统发生崩溃后如何恢复。恢复机制通常也是增加一个 WAL Log，具体过程类似于前面介绍 LSM Tree 中的恢复机制。在这种方式下进行查询时，首先在缓冲区中查找，如果没有找到再在 vLog 文件中查询。

5）LSM Tree 的 WAL Log 优化。

在之前介绍 LSM Tree 的原理时提到，它通过 WAL Log 来保证数据的一致性，当系统异常崩溃后重新启动的过程中会根据 WAL Log 来恢复之前丢失的数据。在前面介绍 WiscKey 的垃圾回收时提到对 vLog 的改进，写入 vLog 中的数据包含了整个键值对，且 vLog 的写入顺序也是数据的插入顺序。WiscKey 中的 LSM Tree 仅用来存储索引信息，该 LSM Tree 中的 WAL Log 维护的数据顺序和 vLog 数据顺序一样。因此，可以通过 vLog 中的数据来构建出 WAL Log 的数据。从这个角度来看，实际上完全可以用 vLog 来替代 LSM Tree 中的 WAL Log。数据的恢复依靠 vLog 文件，同时不影响数据的正确性和一致性。

这样做带来的一个问题是，如果仅依靠目前的 vLog 来恢复数据，那么恢复的过程会非常漫长，因为要扫描整个 vLog 才能实现。为了解决这个问题，WiscKey 定期地在 LSM Tree 中保存了 vLog 的 head 信息 h（格式为 <h,h-vLog-offset>），h 的 offset 位于 head~tail 之间。每当系统启动的时候，WiscKey 都首先从 LSM Tree 中读取到记录的 head 信息 h，然后从 h 位置开始往后遍历 vLog 来恢复 LSM Tree 中的索引信息，直到遍历到 vLog 的 head 位置结束。

因为 vLog 的数据写入顺序和 WAL Log 的数据写入顺序一致，而且可以通过 vLog 中的数据构建出 WAL Log 的数据，所以从 WiscKey 的 LSM Tree 中可以移除 WAL Log，避免不必要的写操作，提升系统性能。通过理论上的分析可以判定这个改进属于一个安全的优化。

3. WiscKey 的工程应用

目前在工程上基于 WiscKey 实现的项目，比较知名的有 Badger、TerarkDB、Titan 等。下面分别对它们加以介绍。

（1）Badger

Badger 是 Dgraph 图数据库内部采用的存储引擎，它是采用 Go 语言编写的。Badger 的整体架构如图 8-3 所示。

图 8-3 说明：Badger 整体架构图。内存层包含 MemTable 和 ImmuMemTable，写入流程为：1. 将大 V 写入 vLog → 2. 记录索引 v_addr（<file_id, offset, length>）→ 3. 写 WAL 日志 → 4. 写 MemTable。Flush & Minor Compact 将 ImmuMemTable 刷入 Level 0 SSTable。磁盘层包含 WAL 日志、vLog（分段）、以及多级 SSTable（Level 0 ~ Level N，大小递增：10MB、100MB、10^N+1 MB）。Major Compact 在 Level 间进行。

Badger 在架构上是比较接近 WiscKey 论文的。在 Badger 中对 V 的大小设定了一个阈值，当 Badger 收到一个写请求时，它会首先将当前 V 的大小和阈值进行比较。如果 V 小于阈值，则会将该键值对直接存入 LSM Tree 中；而当 V 大于或等于阈值时，写操作执行的逻辑跟前面介绍的 WiscKey 中描述的一样，首先将 K 和 V 一起写入 vLog 中，然后将写入该键值对后的位置信息封装成索引信息写入 LSM Tree 中（LSM Tree 中是先 WAL Log、再写 MemTable）。注意：Badger 的实现和 WiscKey 中的介绍有以下几个差异。

  1. Badger 中 vLog 的数据是分段存储的。同一时间只有一个 vLog 接受数据的写入。因此对于每一条写入 vLog 的数据而言，要想精准地查询到它的内容，需要知道该条数据写入到哪个 vLog 文件的什么位置及该条数据多长。这也说明在这种设计中索引信息由三部分构成，即 <file_id, offset, length>。
  2. Badger 中的 LSM Tree 仍然保留了它自身的 WAL Log，并没有采用之前 WiscKey 中介绍的优化。

查询过程跟前面介绍的 WiscKey 一样，首先从 LSM Tree 中获取索引信息，然后根据索引信息从 vLog 中读取数据。在范围查询时通过对 vLog 异步并发预取数据，充分利用 SSD 带宽，改善查询性能。

（2）TerarkDB

根据 TerarkDB 官方文档介绍，TerarkDB 是由 Terark 基于 RocksDB v5.18.3 开发的存储引擎。TerarkDB 目前已经在字节跳动内部投入使用。TerarkDB 的整体架构如图 8-4 所示。

图 8-4 说明：TerarkDB 整体架构图。内存层包括 MemTable 和 ImmuMemTable。写入流程：1. 写 WAL 日志 → 2. 写 MemTable → 3. 将 ImmuMemTable 中的 KV 数据分离存储，value 写入 v-SSTable 中，索引信息写入 SSTable 中 → 4. 将大 V 写入 v-SSTable → 5. 记录索引 v_addr（<file_id>）。磁盘层包含 WAL 日志、v-SSTable（存储大 V）、以及多级 SSTable（Level 0 ~ Level N）。Flush & Minor Compact 将 ImmuMemTable 刷入 Level 0 SSTable，Major Compact 在 Level 间进行。

由于 TerarkDB 是基于 RocksDB 构建的，因此写操作的逻辑和 RocksDB 的是一样的。首先记录 WAL Log，然后将数据写入 MemTable 中。当 MemTable 的大小超过阈值后，将其转变为只读的 ImmuMemTable。注意：当 ImmuMemTable 异步持久化到磁盘形成 SSTable 时，与 RocksDB 有所不同。与 Badger 类似，TerarkDB 对键值对中的 V 设定了一个阈值。当 V 小于阈值（小 V）时，将 K 和 V 直接写入 LSM Tree 中；而当 V 大于或等于阈值（大 V）时，将 K 和 V 分离存储，V 写入单独的 v-SSTable 中，所有大 V 按照 SSTable 格式组织。在这种情况下，对于大 V，在查询时只需要知道它写入在哪个 v-SSTable 中即可。索引信息中只需要维护 v-SSTable 的标识 fileno 就足够了。在 v-SSTable 写入成功后，再将索引信息 <key, fileno> 写入 LSM Tree 的 SSTable 中。存储 V 的 v-SSTable 和 LSM Tree 中的 SSTable 一样，数据按照固定格式存储。只要能定位到具体的 v-SSTable，就可以在 v-SSTable 中读取到对应的 V。关于 SSTable 的具体内容将在第 9 章详细介绍。

在 TerarkDB 中，对于 v-SSTable 的垃圾回收不需要更新 LSM Tree 中的索引，这在很多方面使得它与读/写请求无关。在进行垃圾回收时，后台根据每个 v-SSTable 的垃圾统计情况选择要进行回收的 v-SSTable。然后，在回收过程中遍历每条数据，根据索引信息判断该条数据是否有效，最后将有效的数据写入新的 v-SSTable 中。TerarkDB 在 Manifest 文件中记录 v-SSTable 之间的依赖关系。当查询请求进来时，如果用户访问的数据存储在旧的 v-SSTable 中，它将根据 Manifest 中的依赖关系重定位到最新的 v-SSTable，最后读取对应的值并返回。然而，在实际生产环境中，这种垃圾回收方式可能会导致某个 v-SSTable 被很多旧的 v-SSTable 依赖，从而在查询时降低存储性能。为了解决这个问题，TerarkDB 提供了一种特殊的压缩机制，称为重建（Rebuild）。在重建时，会尽量简化依赖关系，以确保系统正常运行。

了解了 TerarkDB 的写入和垃圾回收机制后，可以发现它对于大 V 的查询请求也分两步：首先，在 LSM Tree 中查找索引；然后从 v-SSTable 中读取数据。在读取 v-SSTable 的过程中，根据 Manifest 文件中记录的依赖关系访问最新的 v-SSTable。

（3）Titan

Titan 是 PingCAP 团队基于 RocksDB 6.4 并根据 WiscKey 的设计理念研发的一个存储引擎。目前 Titan 已经在 TiKV 中正常使用。Titan 的整体架构如图 8-5 所示。

图 8-5 说明：Titan 整体架构图。内存层包括 MemTable 和 ImmuMemTable。写入流程：1. 写 WAL 日志 → 2. 写 MemTable → 3. 将 ImmuMemTable 中的 KV 数据分离存储，value 写入 Blob 中，索引信息写入 SSTable 中 → 4. 将大 V 写入 Blob → 5. 记录索引 v_addr（<file_id, offset, length>）。磁盘层包含 WAL 日志、Blob 文件（存储大 V）、以及多级 SSTable（Level 0 ~ Level N）。Flush & Minor Compact 将 ImmuMemTable 刷入 Level 0 SSTable，Major Compact 在 Level 间进行。

由于 Titan 和 TerarkDB 都是基于 RocksDB 进行研发的，因此从整体架构上来看，Titan 的处理方式和 TerarkDB 类似，但在一些细节处理上有所不同。就写操作而言，Titan 的写操作处理与 TerarkDB 和 RocksDB 的基本一致，主要区别在于，内存中的 ImmuMemTable 持久化到磁盘上的 SSTable 文件的过程。在 Titan 中，同样是通过设定阈值来区分大 V 和小 V，小 V 仍然直接存储在 LSM Tree 中，而大 V 则通过 Blob 文件来存储。与 TerarkDB 相比，它采用 Blob 文件存储有序的 KV 数据，而不是采用 v-SSTable。因此，在这个过程中得到的索引信息是不同的。在 Titan 中，写入 V 后得到的索引信息由 <fileno, offset> 两部分组成。当 V 成功写入 Blob 文件后，再将索引信息写入 LSM Tree 中。

Titan 中有两种垃圾回收机制。第一种采用的是类似于 Badger 的策略。每次根据统计信息确定要垃圾回收的 Blob 文件，然后将该 Blob 中存储的有效数据重写到新的 Blob 文件中并同步更新 LSM Tree 中的索引。另一种垃圾回收机制称为 Level Merge。在 LSM Tree 压缩的过程中 Titan 也会将对应的 Blob 文件进行重写，并同时更新 SSTable 中的索引信息。通过这种方式可以减少对读/写请求处理的影响。这种垃圾回收机制是另一个和 TerarkDB 之间的区别。不过需要注意的是，Titan 的第二种垃圾回收机制仅在 LSM Tree 的最后两层启用。

同理，在 Titan 中进行查询时也是先在 LSM Tree 中查询索引信息，然后在 Blob 文件中获取对应的数据。处理过程跟 Badger 和 TerarkDB 的类似。

相信通过对以上三个 WiscKey 的工程应用的介绍，读者应该对 LSM Tree 和 WiscKey 的原理非常熟悉了。关于 LSM Tree 存储引擎的内容就介绍到这里，下面介绍其他几类 LSM 派系的存储引擎。

8.2 LSM Hash 存储引擎

如果将 LSM Tree 中的异步方式改为同步方式，会发生什么呢？下面一起来探究一下这个问题。

8.2.1 LSM Hash 的起源

为了保证高效地处理写请求，最直接的思路是尽可能地顺序写磁盘，并且将索引信息存储在内存或者磁盘上，根据不同的场景可以选择不同的数据结构来组织。这样写入后会引发另一个问题—空间放大。为了解决这个问题，引入了数据文件分段的设计，数据文件分段的示意图参见图 7-2。分段的依据一般是对数据文件指定的阈值，当超过阈值就创建一个新的数据文件，然后关闭旧的数据文件，旧的数据文件均变成只读状态。分段后对于空间放大的处理方案也是定期进行数据压缩/合并。

此外，分段后同一时刻对于某一条数据而言它最新状态的数据只会存储在一个文件中，因此索引信息还需要多保存一个文件标识符，即文件编号 fileno，索引结构变成 <fileno, offset, length>。该索引信息表达的含义是对于给定查询的数据，它存储在 fileno 文件的 offset 位置，长度为 length。根据该索引信息可以很快地获取到对应的数据。

上述过程实际上就是将 LSM Tree 的异步写磁盘方式改成同步写磁盘方式（需要注意的是，此处所指的写磁盘主要是指 LSM Tree 中的 SSTable，而不是 WAL Log）。改成同步后每来一条数据都直接追加写入磁盘中，然后同步记录索引信息。可以看到，同步写磁盘的处理过程要比异步写磁盘的简单许多，和 LSM Tree 相比同步方式下不需要 MemTable、WAL Log 等结构。

基于上述思想实际上可以产生非常多的存储引擎架构，因为不同的场景选择的索引结构不同，但它们的共性均是同步顺序写磁盘。这个共性可以说是 LSM 派系存储引擎的核心思想。接下来将介绍一个索引结构选择 Hash 表的存储引擎结构，笔者将其称为 LSM Hash 存储引擎，这种存储引擎的主要代表是 Bitcask。

8. LSM 派系存储引擎

8.2.2 Bitcask 的核心原理

Bitcask 是 Basho 提出的一种读/写均具有低延时、高吞吐的单机磁盘存储引擎。它是 Riak 使用的存储引擎之一。论文 “Bitcask: A Log-Structured Hash Table for Fast Key/Value Data” 中提到 Bitcask 是一种存储 KV 数据的日志结构 Hash 表。其核心思路是数据通过顺序写的方式追加到磁盘上，索引结构采用 Hash 表维护在内存中。因此笔者也将其称为 LSM Hash 存储引擎的典型实现。目前，基于 Bitcask 构建的工程应用有同名开源的 Bitcask、豆瓣内部使用并开源的分布式 KV 系统 BeansDB/GoBeansDB，以及 GitHub 上的开源项目 RoseDB、NutsDB 等。本小节重点分析一下 Bitcask 内部的运行机制。

1. Bitcask 的整体架构

Bitcask 作为一个 KV 磁盘存储引擎，它仍然满足前面介绍的经典的三层结构：用户接口层、内存层、磁盘层。Bitcask 的整体架构如图 8-6 所示。

在用户接口层，Bitcask 主要暴露给用户增删改查的接口，如 Get(k)、Put(key,value)、Delete(key)、Scan(prefix) 等。这些接口会接收用户的请求并将数据传递到内存中。

在内存层，Bitcask 采用 Hash 表或者类 Hash 的数据结构来存储索引信息。Bitcask 论文中介绍到采用 Hash 表的主要原因是它的读/写非常快，这样可以节省花费在索引上的时间开销。而在用 Go 实现的 Bitcask 中，它是采用 ART（Adaptive Radix Tree，自适应基树）来存储索引信息的。作为一种前缀树的变形，ART 树具有独特的优势：

  1. ART 树能够比普通的前缀树更好地对数据进行压缩，因此在保存相同数据的情况下，其所占用的空间更少。
  2. ART 树这种数据结构其本身增删改查操作的时间复杂度近似于 Hash 表。
  3. ART 树本身支持前缀查找（可以看作前缀排序）的特性。

而 BeansDB 则采用类似普通 Hash 表的基于数组实现的 Hash 树来存储索引。

在磁盘层，Bitcask 是采用追加写的方式记录写操作的数据，所有涉及变更的操作，例如添加、更新、删除等，Bitcask 都会将其数据组织成统一的格式，然后追加到磁盘中。磁盘上的数据分小文件多段存储（当每个文件达到一定阈值后，关闭写入重新打开一个新文件处理写请求。关闭的文件会通过 Mmap 来打开，用于后续加速读请求查找数据）。由于 Bitcask 在磁盘上的数据写入过程是追加写，类似于在系统里记录 WAL Log 的方式，即写入的数据是按照写入时间排序，而不是关键字排序的，因此它无法很好地支持范围排序查询操作。但是依赖于高效的 Hash 索引结构，对于单个键值的查询性能非常高。

用户接口层

  • Open()
  • Put(key,value)
  • Delete(key)
  • Get(key)
  • Scan(key,func)
  • Fold(func)
  • Merge()
  • Backup()

内存层

  • 索引信息（index）

磁盘层

  • 数据文件（xxxxxxxxx.data）
  • 配置文件（config.json）
  • 元信息（meta.json）
  • 000000000.data
  • 000000001.data
  • 000000002.data
  • 000000003.data
  • 000000004.data
  • 00000xxxx.data …

图 8-6 Bitcask 的整体架构

2. Bitcask 的读/写处理过程

前面提到 Bitcask 中存储数据的磁盘文件是分段组织的，对于每个写操作而言，它的数据先在内存中按照统一的格式编码，然后追加写入数据文件。Bitcask 中的数据文件格式如图 8-7 所示。

Bitcask 对 KV 数据的编码采用 TLV 方式扁平化组织。当数据写入磁盘完成后下一步就是在内存中记录该条数据的索引信息了。前面也提到过，内存中的索引主要包含三部分，即 <fileno, offset, length>。索引格式如图 8-8 所示。所以，Bitcask 的写入过程分为两步：第一步以追加的方式写入数据到磁盘文件中，第二步在内存中写入索引信息。

理解了 Bitcask 的写入过程后，读取过程就清晰了。读取操作首先从内存中的索引结构中获取索引信息，之后直接从 fileno 文件的 offset 位置开始读取 length 个字节的内容。由于在 Bitcask 中已经写满关闭的文件是通过 Mmap 方式打开的。在后续查询时首先会从内存中找到索引。如果判断出当前查询的 KV 是存储在已经关闭的文件中，则直接通过 Mmap 来读取对应的内容。如果查找的数据位于当前写入的文件，则会直接定位到该文件对应的偏移位置，然后读取数据。当从磁盘文件读取数据成功后，对该内容进行相应的解码以获取对应的 KV 数据，最后返回给用户。在这个查询过程中要判定该条数据是否存在、是否过期等。删除可以直接根据索引是否存在来判定，而对于是否过期，既可以根据索引（索引信息中存储过期时间信息）来判断，也可以根据磁盘上获取的数据来判断。Bitcask 数据的读取过程如图 8-9 所示。

Bitcask 中的数据文件格式说明：

字段大小说明
keySize4Bkey 长度
valueSize8Bvalue 长度
keylen(key)B键
valuelen(value)B值
checkSum4B校验和
ttl8B过期时间

一个典型的数据文件 0x0001.data 中存储了多个 KV 条目，如 kv1、kv2_1、kv2_2、kv3_1、kv3_2 等，按追加顺序排列。

注意：在此处，存储的 0xxx.data 其实是一个 WAL Log 文件，所有的 KV 数据都会被追加到日志文件中。然后才往内存中的索引树（自适应基树）中插入索引。此处插入的是 (key, item)。其中 item 记录的为当前的键值对存储在哪个文件（fileld）的哪个位置（offset）、所占的长度（size）是多少。

图 8-7 Bitcask 中的数据文件格式

索引格式：

每个索引项包含：

  • fileno: 文件编号
  • key: 键
  • offset: 偏移位置
  • length: 数据长度

索引在内存中组织为 Hash 表或类 Hash 结构。

图 8-8 索引格式

Bitcask 数据的读取过程：

  1. 根据 key 获取索引信息
  2. 根据索引信息中的 fileno 找到数据文件
  3. 根据索引信息中的 offset、length 从 fileno 数据文件中读取数据并解析

流程： 用户 → 内存（索引信息、元信息） → 根据索引读取磁盘数据文件（000000000.data, 000000001.data, …） → 将数据返回给用户

图 8-9 Bitcask 数据的读取过程

其实上述读取过程也是分为两个步骤：读取索引和读取数据。一般而言，读操作是写操作的逆过程，数据怎么写就对应怎么读。

3. Bitcask 的数据合并过程

随着系统的不断运行，必然会出现数据越来越多的情况。例如，同一条记录经过多次更新后，只有最后一次的数据是有效的，之前的所有数据都是无效的。这种情况会引发空间放大问题。为了解决该问题，在 Bitcask 中也是引入了数据合并功能。

Bitcask 论文中介绍的数据合并的逻辑非常简单。在启动数据合并后，Bitcask 会遍历所有已关闭的数据文件，然后将所有有效的数据写入新的数据文件中，遍历完成后将旧的已关闭的数据文件删除即可。同时，数据合并完成后也会将索引数据写入另外一个 hint 文件中。它的作用是在 Bitcask 启动的时候会直接从 hint 文件加载索引，从而避免了通过遍历全部的数据文件构建索引的过程。数据合并过程会定期触发执行。

用 Go 语言实现的 Bitcask 项目中数据合并的过程和 Bitcask 论文中介绍的有些差异。Bitcask 项目是定时触发数据合并的，数据合并的具体逻辑是首先创建一个新的 Bitcask 实例，接着对旧的 Bitcask 实例遍历它内存中的全量索引，然后依次从数据文件中获取有效的数据并写入新的 Bitcask 实例中，最后用新的 Bitcask 实例生成的数据文件替换掉旧的 Bitcask 实例所管理的数据文件。

提示：不知道读者有没有发现 Bitcask 和 WiscKey 的异同点？从数据存储上来说，Bitcask 和 WiscKey 可以看作一类存储模型，它们的数据均是按照写入的顺序存储到日志文件中的，存储的数据是无序的（不是按键排序的）。二者主要的区别在于索引的存储上。Bitcask 选用 Hash 类的数据结构并在内存中维护索引，大部分实现方案只能支持高效的点查询。在 Bitcask 的设计中，索引数据的维护受内存大小的限制，在一些工程实践中也定期地将索引持久化到磁盘上以确保服务在发生异常后，缩短重新启动过程中重建索引的时间。可以说，Bitcask 主要还是以内存来维护索引。而 WiscKey 的设计则大不相同，WiscKey 则是选择了 LSM Tree 结构来存储索引信息。这样的设计可以使得它的索引数据不受内存的限制，高频访问的索引数据可以缓存在内存中，而访问低频的索引数据可以存放在磁盘上，达到数据冷热分离的效果。同时，这样的设计也让 WiscKey 不但可以支持点查询，而且还能很好地支持范围查询。然而从系统的复杂程度来看，由于索引存储结构的不同，导致 WiscKey 要比 Bitcask 复杂得多。因此，在不同的业务场景中需要根据具体情况选择最合适的方案来解决实际问题。

8.3 LSM Array 存储引擎

见名知意，这类存储引擎采用了数组这种数据结构来实现某些功能。和其他数据结构相比，由于数组本身的特性，它的增删改查效率并不是很高，因此一般很难将它和高性能的 KV 存储引擎关联在一起，那 LSM Array 存储引擎是如何做到的呢？

8.3.1 LSM Array 的设计思想

LSM Array 存储引擎整体上可以从两个方面来考虑：第一方面是 LSM 的特性，另一方面则是数组数据结构。

由前可知，LSM 中最重要的原始数据和索引数据都可以用数组来存储。用数组存储原始数据时只需要在数组末尾不断进行追加即可，符合高效写的条件。该数组属于无序数组，姑且将该数组称为原始数据（KV 数据本身）数组。存储后，索引信息只需要记录该条数据写在数组中的位置及所占的长度即可，这两部分信息可以封装成一个定长的结构。而用数组存储索引数据时，如果数组仍然无序，则查询的效率会非常低，因此经常会考虑对该数组进行排序。排序的策略是按照 KV 数据中关键字 K 的顺序排序，相应地，该数组称为索引数组。这样实现后，对索引的查找可以在 O(log N) 的时间复杂度下完成。然后根据索引信息从原始数据数组中获取原始数据，该操作可以在 O(1) 时间复杂度下完成。基于上述思路可以实现一个基于数组的 LSM 组件，称为 LSM Array 存储引擎。基于这样的思路可以实现不同种类的存储引擎。在开源社区中，这类存储引擎中比较知名的项目有 CouchBase 实现的 Moss。

8.3.2 Moss 的核心原理

Moss 是 CouchBase 团队开源的一个基于 Go 语言实现的 KV 存储引擎。它不但提供了并发读/写、快照读、数据分组数据结构嵌套等功能，而且支持其他磁盘持久化的插件接口，可以非常方便地和 LevelDB、Sqlite 等集成。Moss 的核心设计架构则是 LSM Array，它通过一种非常巧妙的数据组织方式，采用有序的数组来完成和 LSM Tree 等价的 KV 存储功能。下面从 Moss 的整体架构、数据读/写过程、数据合并机制三个方面对其进行介绍。

1. Moss 的整体架构

结合官方的设计文档阅读 Moss 源码，总结出 Moss 的整体架构如图 8-10 所示。

Moss 整体架构示意：

用户接口层：

  • Start()
  • Get(key)
  • NewBatch()
  • ExecuteBatch()
  • Delete(key)
  • Set(key,val)
  • Merge(key,val)
  • Snapshot()

内存层（多个层级）：

  • top：存储最近写入的 Segment
  • mid：存储待合并的多个 Segment
  • base：存储已合并待持久化的 Segment
  • clean：存储可释放的 Segment

每个层级由 SegmentStack 组成，每个 SegmentStack 包含多个 Segment 对象（s1, s2, s3, …）。

磁盘层：

  • data-0x0001.moss
  • data-0x002.moss
  • data-0x003.moss
  • data-0x004.moss
  • data-0x005.moss
  • data-0x006.moss
  • data-0xxxx.moss …

图 8-10 Moss 的整体架构

对于 Moss 的整体架构这里依然采用用户接口层、内存层、磁盘层这三层架构来描述。

在用户接口层，Moss 和之前介绍的其他存储引擎一样，也是暴露给用户主要的核心接口，例如 Get(key)、NewBatch()、Set(key,value)、Delete(key)、Snapshot() 等，这些核心接口用来完成对 KV 数据的增删改查工作。Moss 中一个比较特殊的点是它提供的所有接口中 K、V 均是二进制 byte 类型。

在内存层中，Moss 整体上是采用数组来维护用户传递进来的数据的，其中原始数据和索引数据均采用数组结构来存储。它将内存中存储的数据按照分级的思想来划分，总共划分为 top、mid、base、clean 四层。每一层所采用的数据结构均是 SegmentStack 对象。一个 SegmentStack 内部维护着一个 Segment 数组，通过只对数组的一端操作来模拟栈的特性。在 Moss 中，Segment 是管理 KV 数据的基本单元，所有的 KV 数据都是通过 Segment 结构在内存存储的。每个 Segment 结构内部维护着两个数组：kvbuf 数组，用来存储原始 KV 数据；kvs 数组，用来存储索引数据。Segment 数据组织方式如图 8-11 所示。

Segment 数据组织方式：

  • kvbuf 数组：存储原始 KV 数据。当写请求的数据传递进来以后，Moss 会对 KV 数据按照 TLV 的格式进行编码，编码后的 KV 数据扁平化追加存储到 kvbuf 数组中。
  • kvs 数组：存储索引数据。kvs 是一个 uint64 数组。在 Moss 中，一条 KV 数据在 kvs 对应两个元素：一个元素存储 op_info 操作信息，另一个元素则存储 KV 数据写入 kvbuf 中的位置 offset。op_info 信息占 8B，它的前 8bit（0～7 位）存储操作类型，如更新、删除等，接着的 24bit（8～32 位）用来记录 K 的长度，紧接着的中间 4bit（33～37 位）作为保留位用 0x0 填充，最后剩余的 28bit（38～63 位）记录 V 的长度。通过上述巧妙的组织，采用两个数组来分别存储原始 KV 数据和索引数据。

图 8-11 Segment 数据组织方式

在磁盘层，Moss 也和前面介绍的其他存储引擎一样，采用小文件分段的方式来存储内存中的数据，每个文件按照固定的格式来命名，且文件中的 KV 数据也是按照固定的格式保存的。Moss 中磁盘数据格式如图 8-12 所示。Moss 将磁盘划分成页（4KB），以页为单位读/写数据。内存中的一个 Segment 结构在最终写到磁盘时，会首先写入 header 信息，然后写入 kvs 数据，最后写入 kvbuf 数据。一个 Segment 持久化后，会生成一个 SegmentLoc 对象，用于记录该 Segment 在磁盘内部的索引信息（例如 kvbuf 写入磁盘文件的位置、它的长度信息等）。此外，Moss 在持久化 Segment 时，内部为了提升性能，对 kvs 和 kvbuf 做了页对齐等操作；之前介绍 Moss 时还提到 Moss 中提供了结构嵌套的特性，所以它在图 8-12 中可以看到 childSegments 结构。childSegments 也是 Segment 对象，关于 childSegments 更细节的内容此处不再展开，感兴趣的读者请自行查阅官方文档或者其他相关资料。

磁盘数据格式：

Segment Segment File data-0x001.data 的布局：

  • header (4kB)
  • childSegments (包含多个子 segment)
  • kvindex (即 kvs 数据)
  • kvbuf

注意：在持久化时，会对 kvs 和 kvbuf 进行页对齐。一个 Segment 持久化后会对应一个 SegmentLoc 对象，其中记录了该 Segment 的 kvs 保存的位置和长度，以及 kvbuf 保存的位置和长度等信息。

图 8-12 磁盘数据格式

2. Moss 的数据读/写过程

在了解了 Moss 整体架构和内部核心结构后，对于 Moss 中数据的读/写过程也就比较清楚了。下面总结一下 Moss 中数据的读/写过程。

（1）写过程

所有的 KV 数据都是通过 Batch 接口来写入（set、delete）的。Batch 在调用 ExecuteBatch 后，内部会首先将该 Batch 数据封装成一个 Segment，并将其加入 topSegmentStack 顶部。当 topSegmentStack 元素个数达到阈值后，后台会通知合并协程。该合并协程首先将 topSegmentStack 中的所有 Segment 搬移到 midSegmentStack 中，并在 midSegmentStack 中对这些 Segment 中的数据进行压缩/合并。当压缩/合并操作完成以后会通知持久化协程，持久化协程将压缩/合并后的 midSegmentStack 中的 Segment 搬移到 baseSegmentStack 中，并做持久化处理（写入磁盘文件中）。持久化完成后会判断如果当前已持久化的 Segment 需要缓存，则会进一步将其搬移到 clean 层中，形成 cleanSegmentStack。其中存储到文件中的数据也会通过 Mmap 方式再打开，以便后续加速数据读取的效率。

（2）读过程

读取有两种方式。一种是直接调用 Get(key)，这种方式是以当前的数据作为一个快照然后进行读取，读取时会按照倒序的方式（最近写入的数据最新）读取，一旦读取到数据就结束读取过程。整体上也是首先在内存中读取，内存中读取时会按照前面介绍的四层结构，从高到低依次读取。具体到某一个 Segment 中读取时的过程如下：首先会通过二分查找的方式在 kvs 中查询索引；当获取到索引数据后再根据索引信息在 kvbuf 中读取数据；内存中没读取到后再从磁盘读取，在磁盘读取时也是首先通过 Mmap 读取索引信息，再根据索引信息读取原始数据，最终再将查找的结果返回给上层用户。另一种读取方式是通过获取一个快照 Snapshot() 来读取。这种方式是在指定点的快照上进行数据的读取逻辑。具体的读取过程和第一种方式大体类似。

3. Moss 的数据合并机制

在介绍数据读/写过程时简单地提到了数据合并的过程，这里重点介绍 Moss 中数据合并的具体过程。前面提到 Moss 中数据分为 4 层，即 top、mid、base、clean，每层都是一个 SegmentStack。

  • top：用户写请求传递进来的 KV 数据会首先加入 topSegmentStack 中。当 topSegmentStack 中的元素个数达到阈值后，就会通知合并协程，将其搬移到 mid 中。

  • mid：当从 topSegmentStack 搬移到 mid 中后，紧接着会执行数据的压缩/合并操作。合并过程结束后一方面会生成新的 Segment 对象，并依次将其存放在 midSegmentStack 中，另一方面也会通知持久化协程。

  • base：持久化协程收到通知后，会将 midSegmentStack 层中所有的 Segment 搬移到 base 层中，搬移完成后会在后台异步地将 base 层中的所有 Segment 数据持久化写入磁盘文件中。

  • clean：当 base 层中的 Segment 数据持久化完成后，内部还会根据设置的属性判断是否需要缓存已持久化的 Segment 数据。如果设置了缓存，那么将 base 层中的 Segment 数据进一步迁移到 clean 层；如果不需要缓存，则直接清除掉。

上面介绍的数据合并、持久化这两部分功能在 Moss 中是通过后台任务来执行的：Merger Goroutine 主要负责数据的合并工作；Persister Goroutine 主要负责持久化工作。下面重点介绍一下合并的细节。

合并主要是对 topSegmentStack 中搬移到 midSegmentStack 中的数据进行处理。搬移到 midSegmentStack 中的 SegmentStack 通常都有多个 Segment 对象，而每个 Segment 对象内部是由 kvs 和 kvbuf 构成。那具体怎么合并呢？其实合并操作本质上无非就是对多个 Segment 中的数据进行处理，最直接的方法就是通过一个 Hash 表对象来辅助处理，但这样的操作效率非常低。因为 Moss 中的 Segment 数据是无序组织的，对于无序的数据也只有这种遍历处理办法了，除非能让 Segment 中的数据有序。

在 Moss 中也正是采用了对 Segment 中的数据排序这个方法。每个 Segment 中的 kvbuf 已经写入无法修改，但是 kvs 数组中每个索引项都是定长的（2 个 uint64 类型），因此可以对索引信息 kvs 排序。实际上，Moss 也是采用了 Go 包自带的 sort 方法对 kvs 进行了 O(NlogN) 级别的排序。当对索引排序完成后，数据就可以有序地访问了。

综上，在合并前 Moss 会对 midSegmentStack 当前的多个 Segment 结构各自按照索引排序，排序后用堆的方式进行数据合并，以提升合并效率。图 8-13 所示为 Moss 四层结构中 Segment 的合并、持久化的转移过程。读者可以参考该图进行理解，也可以参考官方文档和项目源码进行深入探索。Moss 的代码整体实现还是比较优雅的，值得一读。

图 8-13 数据合并、持久化的转移过程

图 8-13 展示了以下步骤：

  1. 合并协程（Merger Goroutine）：

    • 将 top 层的 SegmentStack 移动到 mid 层中
    • 将 mid 层的 SegmentStack 中的 Segment 进行合并

  2. 持久化协程（Persister Goroutine）：

    • 移动 mid 层中的 SegmentStack 到 base 层中
    • 持久化 base 层中的 SegmentStack 写入磁盘文件中
    • 根据设置决定是将 base 层中的 SegmentStack 移动到 clean 层还是清除

状态转换示例：

  • 初始：top 包含 segment-5；mid 包含 segment-0~4；base 为空；clean 为空
  • 合并后：top 包含 segment-5；mid 包含合并后的 segment-0…4；base 为空；clean 为空
  • 持久化后：top 包含 segment-5；mid 为空；base 包含 segment-0…4；clean 为空
  • 缓存后（可选）：top 包含 segment-5；mid 为空；base 为空；clean 包含 segment-0…4
  • 磁盘层（lower-level-storage）存储来自 segment-0…4 的变更

8.4 其他 LSM 存储引擎

LSM 存储引擎除了前面介绍的三类比较经典的外，其实还有一些不局限于 KV 存储场景的变形应用，比如消息队列存储模型、内存中的本地缓存组件的存储结构等。本节将对这些应用场景进行简单介绍，需要重点关注的是消息队列的存储模型和 LSM 存储引擎之间的关系。

8.4 其他 LSM 存储引擎

LSM 存储引擎除了前面介绍的三类比较经典的外，其实还有一些不局限于 KV 存储场景的变形应用，比如消息队列存储模型、内存中的本地缓存组件的存储结构等。本节将对这些应用场景进行简单介绍，需要重点关注的是消息队列的存储模型和 LSM 存储引擎之间的关系。

8.4.1 LSM 存储引擎扩展

LSM 本身表达了两个核心特点：日志结构、合并。日志结构表明了数据的写入方式，类似于记录日志的方式一样，即顺序追加。而合并功能是为了解决某些场景数据重复度高，而造成的空间放大问题，用来进行空间回收。从这两个特点切入来看，日志结构是 LSM 最核心的特性（数据最终要存储在磁盘文件上），而合并则是附加特性。如果说按照日志结构顺序写入的数据本身没有重复或者重复度很低，那么合并特性完全可以不需要。

假设按照日志结构写入的每条数据都有一个唯一标识的关键字，则数据的重复度主要指同一个关键字数据的重复频率。可以认为，后写入的数据会覆盖之前的数据。有效数据只有最近一次写入的数据。

[!注意] 事实上也是如此，在 KV 存储场景中，同一条数据的增删改操作均通过日志追加记录，这种情况下对于写操作频繁的系统而言，合并特性显得至关重要。和 KV 存储场景不同，虽然在消息队列场景中也要进行大量写，但一般每一条消息会设定一个消息编号，该编号通常是自增的。这也意味着，消息队列中同一条消息（消息编号相同）重复的情况很少（除了部分写入失败重试等）。因此对消息队列而言，合并特性就显得没那么重要了。尤其对存储海量数据的消息队列而言，一方面需要大量的高效写，另一方面又需要将消息数据存储到磁盘上，因此可以考虑利用日志结构来构建存储模型。实际上，目前业界绝大部分的消息队列（比如主流的 Kafka、RocketMQ 等）也是这么设计的。这些消息队列整体上基于 LSM 思想，采用日志结构的方式设计存储模型，放弃或者精简一些合并特性。

除此之外，很多本地缓存的组件设计也是借鉴 LSM 的思路，数据分为两部分：索引数据和原始数据。这种本地缓存组件通常会开辟一段连续的内存空间来存储原始数据，并且绝大部分采用 Hash 表数据结构来存储索引数据。在写缓存时，原始数据按照某种固定的 TLV 格式进行编码，编码后的数据追加写入内存空间，之后同步插入一条索引信息。该索引信息记录了该条数据写在内存空间中的什么位置、该条数据占多大的空间、该条数据是否有效，以及过期时间等信息。当读缓存时，先获取索引信息再获取对应的数据。在这种设计中，也有 LSM 的日志结构的影子在里面。

8.4.2 消息队列 Kafka 存储引擎

Kafka 的性能高，得益于两方面：第一，它是分布式系统，可以水平扩容，性能可以线性提升；第二，单机系统消息追加写设计，吞吐量高，所以性能高。

Kafka 用 Topic 代表一类数据，数据的生产和消费都是以 Topic 来标识的。Topic 存储的数据会逻辑上分成多个 Partition 来存储，而每个 Partition 的数据是分段存储的，每一个分段称为 Segment。每条消息只会写入某一个 Partition 的某个 Segment 中。Kafka Partition 的存储结构如图 8-14 展示。

一个 Segment 包含 xxx.log、xxx.index 和 xxx.timeindex 三个文件。

  • xxx.log ：存储每条消息的原始数据。一般对消息数据进行固定格式编码后，将消息数据追加写入该文件。所有的消息在 Kafka 内部都是以顺序追加方式记录的。这就是 LSM 日志结构最典型的特性。

  • xxx.index ：存储每条消息的索引信息。当某一条消息写入 xxx.log 文件中，同时会在该文件中记录一条索引信息。该索引信息主要描述了该条消息写入 xxx.log 的什么位置、该条消息的长度等信息。

  • xxx.timeindex ：主要按照时间维度存储索引信息，记录在什么时间写入的某条消息、消息编号是多少等信息。

所以，Kafka 可以支持按照消息编号和指定时间点消费消息。

图 8-14 Kafka Partition 的存储结构（原始图片描述：存储原始数据 xxx.log，存储索引信息 xxx.index，存储时间索引信息 xxx.timeindex；Partition 包含多个 Segment，每个 Segment 包含这三个文件）

此外，Kafka 中每个 Segment 的 xxx.log 文件大小是固定的，当文件写满后，会打开一个新的 Segment 继续存储消息。消息编号是唯一且自增的，消息也是按照顺序消费的。每个 Segment 内部存储的消息是按照消息编号有序存储的，多个 Segment 之间的数据也是有序的。因此，为了加快消息查询和消费的速度，Kafka 在对 Segment 中的三个文件命名时进行了巧妙的设计。对于某个 Segment 而言，它的文件命名是由它保存的第一个消息的编号和文件扩展名拼接而成。这意味着可以根据多个 Segment 的文件名来获取它们各自保存的第一条消息的编号，并且很容易对它们进行排序。当根据消息的编号来获取消息数据时，首先可以根据文件名获取对应的消息编号并进行排序，然后根据待查询的消息编号使用二分查找法快速确定它被存储在哪个 Segment 中。一旦定位到 Segment 后，在对应的索引文件中继续使用二分查找法来定位索引信息，最后根据索引信息找到原始数据。

Kafka 对核心的消息查询流程进行了一些优化。如果每条消息都记录一条索引信息，将导致索引所占用的空间较大。为了解决这个问题，Kafka 采用了稀疏索引来进行优化，即每隔几条消息记录一条索引信息。这样索引信息所占用的空间大幅减少，并且可以更好地利用磁盘预读甚至缓存更多的索引数据到内存中，以加快查询效率。

但在消息查询时需要进行额外的处理。在定位到 Segment 后，在索引文件中进行二分查找定位索引结束时，获取的索引信息是最靠近当前待查询消息的索引信息。因此，可以根据索引信息中记录的该消息在原始数据文件中的位置开始，顺序遍历消息并逐个比较消息编号，直到找到待查询的消息为止。由于索引的记录是按照固定的间隔存储的，因此最多只需要遍历前后间隔中的 n 个消息，效率也比较高。Kafka 中完整的消息查询过程示例如图 8-15 所示。

图 8-15 Kafka 的消息查询过程（原始图片描述：查询消息 id 为 223290376 的消息；Partition 中包含多个 Segment；首先定位到 Segment（例如 223290348 对应 segment），然后从该消息开始顺序遍历查找；图中显示索引文件中的键值对如 223290348,12730、223290368,13452、223290388,19283，以及对应的 log 文件中的数据）

8.5 小结

本章对 LSM 派系中的 LSM Tree 存储引擎、LSM Hash 存储引擎、LSM Array 存储引擎，以及 LSM 其他存储引擎（主要是消息队列存储引擎）分别进行了介绍，上述几类存储引擎的总结对比如图 8-16 所示。

维度BitcaskMossPebble/LevelDB/RocksDB
数据块文件是否有序无序有序有序
内存数据组织方式ATR Tree/HashTable（保存索引）LSM ArraySkipList 等
磁盘数据组织方式大小差不多的小文件不同大小的小文件分块的小文件、分层存放
所属分类LSM HashLSM ArrayLSM Tree
压缩/合并方式定时根据内存中的索引重建新的文件，最后替换旧的文件在内存中压缩/合并，在持久化时，也会检测是否压缩/合并定时并结合一些限制条件进行分层压缩/合并

图 8-16 LSM 派系存储引擎对比