1. 首页
  2. 源码解析
  3. 存储与数据库
  4. LSM 初探

LSM 初探

  • 发布于 2024-10-24
  • 8 次阅读

什么是 LSM Tree ？

LSM，即Log-Structured Merge Tree，是一种用于存储键值对的数据结构，它被设计用来优化写操作的性能。这种数据结构特别适用于需要频繁进行写入操作的场景，如日志文件系统和某些类型的数据库（例如LevelDB, RocksDB等）。下面是LSM树的基本结构特点：

  1. 内存表（MemTable）：当数据被写入时，首先会被放入一个内存中的数据结构中，这个数据结构通常是跳表（Skip List）或者平衡二叉查找树（如AVL树、红黑树）。因为这些数据都在内存中，所以可以非常快速地插入。

  2. 不可变内存表（Immutable MemTable）：当内存表达到一定大小后，它会变为只读，并转换为不可变内存表。这时新的写入将继续进入一个新的空内存表中。不可变内存表最终会被刷写到磁盘上形成SSTable（Sorted String Table）。

  3. SSTables：SSTable是有序且不可更改的键值对集合，它们按照键的顺序在磁盘上持久化存储。每个SSTable都包含了索引以便于快速查找。

  4. 多层架构：为了提高查询效率并减少磁盘空间占用，LSM树通常采用分层的方式管理SSTable。新生成的SSTable最初放置在最底层（或称为第0层），随着更多数据的到来，通过合并过程将不同层级之间的SSTable进行合并以保持数据的紧凑性及删除过期数据。这一过程中可能会产生更高层次的新SSTable。

  5. 合并策略：LSM树使用特定的算法来决定何时以及如何合并不同的SSTable。常见的策略包括大小驱动合并、时间驱动合并等。合并操作可以帮助清理已删除的条目，并确保同一键下的最新版本总是可访问的。

  6. 布隆过滤器：为了进一步加速查找过程，有时会在每一层SSTable之上添加布隆过滤器。这允许系统快速确定某个键是否存在于给定级别中，从而避免不必要的磁盘I/O。

总之，LSM树通过牺牲部分读取性能来换取极高的写入性能，并通过复杂的后台任务（如定期合并）来维持系统的整体效率。这样的设计非常适合那些写密集型的应用场景。

LSM（Log - Structured Merge - Tree）是一种存储引擎的数据结构，主要用于高效地处理写入密集型工作负载，以下是其详细结构：


  1. 内存组件（MemTable）

    • 结构特点：LSM - Tree 将数据首先写入内存中的一个有序树结构，通常是跳表（Skip - List）。这个内存中的数据结构被称为 MemTable。跳表是一种概率性的数据结构，它在链表的基础上，通过增加多层索引来加快查找速度。与平衡树相比，跳表的插入和删除操作相对简单，不需要进行复杂的旋转操作。

    • 数据写入过程：当有新的数据写入时，数据会先插入到 MemTable 中，并且按照键的顺序进行排序。这个过程非常快速，因为内存操作的速度相对磁盘操作要快得多。例如，在一个数据库应用中，用户插入一条新的记录，这条记录会先在 MemTable 中找到合适的位置插入，等待后续的处理。

    • 作用：MemTable 的存在可以缓冲写入操作，使得系统能够快速响应写入请求，同时为后续的数据合并和持久化操作提供了一个临时的数据存储区域。

  2. SSTables（Sorted String Tables）

    • 结构特点：SSTables 是 LSM - Tree 存储在磁盘上的主要数据结构。它是一种经过排序的键值对文件，每个 SSTable 都包含一系列按照键排序的记录。SSTables 的内部结构通常包括索引部分和数据部分。索引部分可以帮助快速定位数据在 SSTable 中的位置，数据部分则存储实际的键值对。

    • 生成过程：当 MemTable 达到一定的大小限制时，它会被刷新（Flush）到磁盘上形成 SSTables。在这个过程中，数据会根据一定的规则进行排序和组织。例如，可能会按照键的范围或者时间顺序将 MemTable 中的数据划分到不同的 SSTables 中。

    • 层次结构：LSM - Tree 通常会有多个层次的 SSTables。新生成的 SSTables 会被放置在较高级别的层次（Level），随着数据的更新和合并操作，SSTables 可能会逐渐下沉到较低的层次。层次结构的设计有助于提高数据的读取效率，因为较新的数据更有可能在较高级别的 SSTables 中找到，减少了磁盘 I/O 的次数。

  3. 合并（Compaction）过程

    • 触发条件：为了避免 SSTables 数量过多导致读取性能下降，LSM - Tree 会定期进行合并操作。合并操作可以由多种因素触发，例如，当某个层次的 SSTables 数量达到一定的阈值，或者系统负载较低时，就会启动合并进程。

    • 合并方式：在合并过程中，会选择相邻层次或者满足一定条件的 SSTables 进行合并。例如，将较高级别的小 SSTables 与较低级别的 SSTables 进行合并。合并过程中，会读取多个 SSTables 中的键值对，根据键的顺序进行重新排序和整合，去除重复的键值对（如果有更新操作的话，会保留最新的值），然后将合并后的结果写入新的 SSTables。

    • 作用：合并操作可以减少 SSTables 的数量，优化数据存储，提高读取性能。通过将多个小的、可能存在重叠的数据文件合并为一个大的、更紧凑的 SSTable，系统在读取数据时可以更快地定位到所需的键值对，减少了查找多个文件的开销。

  4. 日志文件（Write - Ahead Log，WAL）

    • 结构特点：WAL 是一种顺序写入的日志文件，用于记录所有的写入操作。它的结构简单，通常是一系列按照时间顺序记录的操作日志，每个日志条目包含操作类型（如插入、更新、删除）和对应的键值对信息。

    • 作用：WAL 主要用于数据恢复。在系统出现故障（如断电、进程崩溃等）时，通过回放 WAL 中的日志，可以将系统恢复到一个一致的状态。例如，如果在将 MemTable 刷新到 SSTables 的过程中系统崩溃，重新启动后可以根据 WAL 中的记录重新构建 MemTable，确保数据不会丢失。

NoSQL检索：为什么日志系统主要用LSM树而非B+树？

B+树作为检索引擎中的核心技术得到了广泛的使用，尤其是在关系型数据库中。

但是，在关系型数据库之外，还有许多常见的大数据应用场景，比如，日志系统、监控系统。这些应用场景有一个共同的特点，那就是数据会持续地大量生成，而且相比于检索操作，它们的写入操作会非常频繁。另外，即使是检索操作，往往也不是全范围的随机检索，更多的是针对近期数据的检索。

那对于这些应用场景来说，使用关系型数据库中的B+树是否合适呢？

我们知道，B+树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。

那么，针对这种频繁写入的场景，是否有更合适的存储结构和检索技术呢？今天，我们就来聊一聊另一种常见的设计思路和检索技术： LSM树（Log Structured Merge Trees）。LSM树也是近年来许多火热的NoSQL数据库中使用的检索技术。

LSM树的优势

  1. 写放大:

    • 在LSM树中，写入首先发生在内存中的MemTable里，这是一个顺序写的过程，比直接写入磁盘要快得多。

    • 当MemTable满时，它会被标记为Immutable MemTable，并被转储到磁盘形成SSTable，这个过程也是顺序写的，避免了随机写带来的性能开销。

  2. 读取优化:

    • 虽然LSM树的读取性能可能不如B+树，但它通过多种技术来提高读取效率，如布隆过滤器、多级索引等。

    • 对于最新的数据查询，可以直接从内存中的MemTable进行快速查找；对于较旧的数据，则可以利用有序的SSTable和索引来加速检索。

  3. 压缩和合并:

    • 通过定期或按需进行SSTable之间的合并，LSM树能够去除过期的数据条目，并且将较小的文件合并成较大的文件，从而减少存储空间占用并保持数据的紧凑性。

  4. 适合范围查询:

    • 因为SSTable是按照键排序的，所以对于基于时间戳或其他连续键值的范围查询非常高效。

  5. 可调参数:

    • LSM树允许调整各种参数，如MemTable大小、合并策略等，以适应不同的工作负载特性。

使用场景

  • 日志系统: 日志通常是一直在生成的数据流，而且经常需要对最近的日志进行分析。LSM树非常适合这样的场景，因为它能很好地支持大量的写入操作，并且对近期数据的读取也相对快速。

  • 监控系统: 监控数据同样具有持续产生并且数量庞大的特点，同时还需要实时或近实时地进行查询。LSM树可以帮助实现高性能的写入以及有效的检索。

  • 消息队列: 消息队列系统也需要处理大量的写入请求，同时保证一定的读取性能。LSM树可以提供良好的写入性能，同时也支持高效的读取操作。

  • 时间序列数据库: 时间序列数据库特别适用于存储带有时间戳的数据点，这些数据通常是按照时间顺序不断追加的。LSM树能够很好地支持这种模式，并且可以通过合理的分层和合并策略来优化存储和查询性能。

总之，在面对高写入负载和非全范围随机检索的需求时，LSM树提供了比传统B+树更为合适的解决方案。许多现代NoSQL数据库如RocksDB、Cassandra等都采用了LSM树作为其核心的数据结构，这表明LSM树在大数据时代的重要性和适用性。

  1. B + 树在频繁写入场景的不合适性

    • 在关系型数据库中，B + 树表现出色是因为它平衡了读写操作。然而，在日志系统、监控系统等频繁写入的大数据应用场景下，B + 树存在明显的劣势。B + 树的叶子节点存储数据，且一般位于磁盘。每次插入新数据时，需要在磁盘上进行随机写入。磁盘的随机写入性能差，这是因为磁盘的机械结构（对于机械硬盘而言）和读写原理导致的。例如，磁盘读写头需要在盘片上快速移动到指定位置进行写入，这个寻道过程很耗时。在高频率写入的场景下，如日志系统每秒要写入大量数据，这种频繁的随机磁盘操作会产生巨大的性能开销，使系统响应变慢甚至无法正常工作。

  2. LSM 树的优势

    • 写入操作优化

      ：

      • LSM 树将数据首先写入内存中的一个有序树结构（如 MemTable），通常是跳表。内存操作速度比磁盘操作快得多，所以写入操作可以快速完成。例如，在日志系统中，新的日志条目可以先快速插入到内存的 MemTable 中，不需要立即进行磁盘操作，从而缓冲了写入请求，提高了系统的写入性能。

    • 合并操作提升性能

      ：

      • LSM 树会定期进行合并操作。当内存中的 MemTable 达到一定大小，会被刷新到磁盘形成 SSTables。而且，系统会对 SSTables 进行合并。在合并过程中，会读取多个 SSTables 中的键值对，重新排序和整合，去除重复的键值对（如果有更新操作，会保留最新的值），然后将合并后的结果写入新的 SSTables。这种方式可以减少磁盘上 SSTables 的数量，优化数据存储。例如，在监控系统中，随着时间推移，数据不断写入，通过合并操作可以使磁盘上的数据存储更加紧凑和高效，减少磁盘 I/O 的次数，进而提升系统性能。

    • 适应近期数据检索需求

      ：

      • LSM 树的结构特点也使其更适应这类应用场景中的检索需求。通常，这些应用场景更多地是检索近期数据。LSM 树中较新的数据更有可能在较高级别的 SSTables 或者内存结构（MemTable 和 Immutable Memtable）中找到。由于内存结构的查询速度非常快，对于检索近期数据来说，可以快速响应。而对于较旧的数据检索，虽然可能涉及磁盘 I/O，但通过合理的层次结构和索引设计，也能在一定程度上保证检索效率。所以，LSM 树在频繁写入和侧重近期数据检索的应用场景中是一种更合适的存储结构和检索技术。

如何利用批量写入代替多次随机写入？

刚才我们提到B+树随机写入慢的问题，对于这个问题，我们现在来思考一下优化想法。操作系统对磁盘的读写是以块为单位的，我们能否以块为单位写入，而不是每次插入一个数据都要随机写入磁盘呢？这样是不是就可以大幅度减少写入操作了呢？

LSM树就是根据这个思路设计了这样一个机制：当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此，LSM树至少需要由两棵树组成，一棵是存储在内存中较小的C0树，另一棵是存储在磁盘中较大的C1树。简单起见，接下来我们就假设只有C0树和C1树。

  1. 批量写入的原理和优势

    • 操作系统磁盘读写原理的利用：操作系统对磁盘的读写是以块为单位的。在传统的 B + 树结构中，每次插入一个数据可能就需要一次随机写入磁盘操作，这会导致频繁的磁盘寻道和写入延迟。而批量写入的思路是利用磁盘块的概念，将多个数据组合在一起形成一个磁盘块，一次性写入磁盘。例如，假设磁盘块大小为 4KB，而单个数据记录大小为 1KB，那么可以将 4 个数据记录组成一个块进行写入。这样做的好处是大大减少了磁盘寻道的次数，因为寻道时间在磁盘操作中占据了相当大的比例。通过批量写入，将原本多次随机写入磁盘的操作转化为一次或少数几次顺序写入操作，顺序写入的性能要比随机写入高很多，从而提高了整体的写入效率。

  2. LSM 树中的具体实现方式（C0 树和 C1 树）

    • C0 树（内存树）的作用：在 LSM 树的这种机制中，数据首先被写入内存中的 C0 树。C0 树通常采用高效的内存数据结构，如跳表，用于快速存储和查询数据。因为内存操作速度远远快于磁盘操作，所以在这个阶段可以快速地处理数据写入和查询请求。例如，在数据写入过程中，新的数据会按照一定的顺序插入到 C0 树中，这个过程就像在内存中的一个有序列表中添加元素一样，速度非常快。同时，在查询数据时，由于 C0 树的结构特点（如跳表的多层索引），可以迅速定位到数据所在位置。

    • 从 C0 树到 C1 树的批量写入过程：当 C0 树持续变大，达到一定的阈值时，就会触发批量写入磁盘的操作，将数据写入 C1 树。这个阈值的设定是一个关键因素，它需要综合考虑内存使用情况、写入频率等因素。例如，如果阈值设置得过低，可能会导致频繁的磁盘写入，无法充分发挥批量写入的优势；如果阈值设置得过高，可能会占用过多的内存资源，并且在 C0 树数据丢失（如系统崩溃）的情况下，丢失的数据量会比较大。在批量写入时，会将 C0 树中的数据按照一定的规则（如按照键的顺序）组织成磁盘块，然后以块为单位顺序写入 C1 树。这样就实现了用批量写入代替多次随机写入，提高了磁盘写入的效率，同时也减少了磁盘 I/O 的次数，优化了整个存储系统的性能。


您提到的优化思路确实是在LSM树中实现的核心概念之一，即通过批量写入来减少磁盘I/O操作。这种做法利用了内存的速度优势以及磁盘顺序写入比随机写入更高效的特点。下面详细解释一下这个机制是如何工作的：

LSM树中的批量写入机制

  1. MemTable (C0 树):

    • 数据首先被写入到位于内存中的MemTable（这里称为C0树）。

    • MemTable通常是基于跳表或平衡二叉查找树等数据结构实现，支持快速的插入和查询操作。

    • MemTable的设计保证了数据在内存中的有序性，这对于后续的数据持久化非常重要。

  2. 延迟写入:

    • 在MemTable中的数据不会立即写入磁盘，而是等待MemTable达到一定的大小阈值。

    • 这个过程减少了频繁的磁盘I/O操作，因为每次写入都是一个完整的块，而不是单条记录。

  3. Immutable MemTable:

    • 当MemTable达到预定大小后，它会被标记为只读（Immutable MemTable），并且新的写入会进入一个新的MemTable。

    • Immutable MemTable准备被异步地转储到磁盘形成SSTable。

  4. 批量写入磁盘 (C1 树):

    • 一旦MemTable变为Immutable，其内容将被序列化并以连续块的形式写入磁盘，形成SSTable（这里称为C1树）。

    • SSTable是按Key排序的文件，每个文件内部也是有序的，这有助于后续的读取和合并操作。

  5. 多层架构与合并:

    • 随着更多的数据到来，系统会生成多个SSTable，并且可能需要定期进行合并操作，以保持数据的一致性和去除重复的数据。

    • 合并操作通常涉及多个SSTable之间的归并排序，最终生成更大的、更加紧凑的SSTable。

  6. 读取操作:

    • 读取时，系统会先检查最新的MemTable，然后是Immutable MemTable，最后是磁盘上的SSTable。

    • 由于最近的数据很可能还在内存中，因此可以提供较快的访问速度。

  7. 布隆过滤器和其他优化:

    • 为了加速读取操作，SSTable通常会使用布隆过滤器来快速判断某个键是否存在，从而避免不必要的磁盘I/O。

    • 另外，还可以使用缓存技术来存储热点数据，进一步提高性能。

总结

通过上述机制，LSM树能够显著减少磁盘的随机写入次数，而改为批量的顺序写入，这样可以极大地提升写入性能。同时，通过对内存和磁盘数据的分层管理，LSM树也能够在一定程度上保证读取性能。这种设计非常适合于写密集型的应用场景，如日志系统、监控系统等。

批量写入的优势体现在哪些方面？ LSM 树中的 C1 树是如何实现的？ 与传统的 B+树相比，LSM 树在写入性能上有哪些提升？

  1. 批量写入的优势

    • 减少磁盘寻道次数：

      • 操作系统的磁盘读写是以块为单位的。传统的随机写入方式下，每次写入一个数据可能都需要磁盘读写头进行寻道操作来定位写入位置。例如，在机械硬盘中，读写头需要在高速旋转的盘片上移动到指定的磁道和扇区进行写入，这个过程相对较慢。而批量写入是将多个数据组合成一个磁盘块后再写入，这样在一次写入操作中，只需进行一次寻道，就可以将整个块的数据写入磁盘，大大减少了寻道时间，从而提高了写入效率。

    • 提高顺序写入比例：

      • 批量写入能够将多次单个数据的随机写入转化为一次或少数几次的顺序写入。磁盘的顺序写入性能远高于随机写入性能。因为顺序写入时，磁盘的读写头可以沿着磁道连续地写入数据，不需要频繁地移动位置。就像在流水线上作业一样，数据可以按照顺序依次存储到磁盘的连续区域，这种方式能够充分利用磁盘的带宽，提高写入速度。

    • 降低磁盘 I/O 开销：

      • 每次磁盘 I/O 操作都伴随着一定的开销，包括寻道时间、旋转延迟和数据传输时间等。通过批量写入，减少了 I/O 操作的次数。例如，原本需要进行 100 次单个数据的 I/O 操作，现在通过批量写入可能只需要 10 次（假设每次批量写入包含 10 个数据），这样就大大降低了磁盘 I/O 的总开销，减轻了系统的负担，提高了整体性能。

  2. LSM 树中 C1 树的实现

    • 数据结构基础：

      • C1 树存储在磁盘上，它通常是由一系列的 SSTables（Sorted String Tables）组成。SSTables 是一种经过排序的键值对文件，每个 SSTable 内部的键值对是按照键的顺序排列的。SSTables 包含索引部分和数据部分，索引部分用于快速定位数据在 SSTable 中的位置，数据部分存储实际的键值对。这种排序结构使得在进行数据查找时，可以利用二分查找等高效算法来定位数据。

    • 生成过程：

      • C1 树中的 SSTables 是通过将 C0 树中的数据批量写入生成的。当 C0 树（内存中的树）大小达到阈值时，数据会按照一定的规则被组织成磁盘块，然后以块为单位顺序写入磁盘，形成 SSTables。在写入过程中，会对数据进行排序和整理，以符合 SSTables 的结构要求。新生成的 SSTables 可能会先存放在 C1 树的某个层次（LSM 树通常有层次结构），随着数据的更新和合并操作，SSTables 可能会在层次间移动。

    • 合并操作优化：

      • 为了避免 C1 树中的 SSTables 数量过多导致读取性能下降，LSM 树会定期进行合并操作。在合并过程中，会选择相邻层次或者满足一定条件的 SSTables 进行合并。例如，将较高级别的小 SSTables 与较低级别的 SSTables 进行合并。合并时，会读取多个 SSTables 中的键值对，根据键的顺序进行重新排序和整合，去除重复的键值对（如果有更新操作，会保留最新的值），然后将合并后的结果写入新的 SSTables。通过合并操作，可以优化 C1 树的存储结构，减少 SSTables 的数量，提高读取性能。

  3. LSM 树与 B + 树在写入性能上的提升对比

    • B + 树写入性能的瓶颈：

      • B + 树的数据存储在叶子节点，而叶子节点一般存储在磁盘。每次插入新数据时，需要在磁盘上进行随机写入。如前面所提到的，磁盘的随机写入性能差，因为需要频繁地进行寻道操作。对于频繁写入的应用场景，如日志系统每秒要写入大量数据，这种随机写入的方式会导致磁盘 I/O 开销巨大，使得系统性能急剧下降。

    • LSM 树写入性能的提升：

      • LSM 树通过将数据先写入内存中的 C0 树，避免了频繁的磁盘随机写入。当 C0 树达到阈值后，再进行批量写入磁盘的 C1 树，将随机写入转化为顺序写入，大大提高了写入性能。例如，在高写入频率的场景下，LSM 树可以先在内存中快速缓冲大量的数据，然后以更高效的方式写入磁盘，而 B + 树则会因为频繁的随机磁盘操作而陷入性能困境。因此，LSM 树在写入性能上相对于 B + 树有显著的提升，更适合写入频繁的应用场景。

LSM树由至少2部分组成：内存的C0树和磁盘的C1树

C1树存储在磁盘中，因此我们可以直接使用B+树来生成。那对于全部存储在内存中的C0树，我们该如何生成呢？在上一讲的重点回顾中我们分析过，在数据都能加载在内存中的时候，B+树并不是最合适的选择，它的效率并不会更高。因此，C0树我们可以选择其他的数据结构来实现，比如平衡二叉树甚至跳表等。但是为了让你更简单、清晰地理解LSM树的核心理念，我们可以假设C0树也是一棵B+树。

那现在C0树和C1树就都是B+树生成的了，但是相比于普通B+树生成的C0树，C1树有一个特点：所有的叶子节点都是满的。为什么会这样呢？原因就是，C1树不需要支持随机写入了，我们完全可以等内存中的数据写满一个叶子节点之后，再批量写入磁盘。因此，每个叶子节点都是满的，不需要预留空位来支持新数据的随机写入。

如何保证批量写之前系统崩溃可以恢复？

B+树随机写入慢的问题，我们已经知道解决的方案了。现在第二个问题来了：如果机器断电或系统崩溃了，那内存中还未写入磁盘的数据岂不就永远丢失了？这种情况我们该如何解决呢？

为了保证内存中的数据在系统崩溃后能恢复，工业界会使用 WAL技术（Write Ahead Log，预写日志技术）将数据第一时间高效写入磁盘进行备份。WAL技术保存和恢复数据的具体步骤，我这里总结了一下。

  1. 内存中的程序在处理数据时，会先将对数据的修改作为一条记录，顺序写入磁盘的log文件作为备份。由于磁盘文件的顺序追加写入效率很高，因此许多应用场景都可以接受这种备份处理。

  2. 在数据写入log文件后，备份就成功了。接下来，该数据就可以长期驻留在内存中了。

  3. 系统会周期性地检查内存中的数据是否都被处理完了（比如，被删除或者写入磁盘），并且生成对应的检查点（Check Point）记录在磁盘中。然后，我们就可以随时删除被处理完的数据了。这样一来，log文件就不会无限增长了。

  4. 系统崩溃重启，我们只需要从磁盘中读取检查点，就能知道最后一次成功处理的数据在log文件中的位置。接下来，我们就可以把这个位置之后未被处理的数据，从log文件中读出，然后重新加载到内存中。

通过这种预先将数据写入log文件备份，并在处理完成后生成检查点的机制，我们就可以安心地使用内存来存储和检索数据了。

如何将内存数据与磁盘数据合并？

解决了内存中数据备份的问题，我们就可以接着写入数据了。内存中C0树的大小是有上限的，那当C0树被写满之后，我们要怎么把它转换到磁盘中的C1树上呢？这就涉及 滚动合并（Rolling Merge）的过程了。

我们可以参考两个有序链表归并排序的过程，将C0树和C1树的所有叶子节点中存储的数据，看作是两个有序链表，那滚动合并问题就变成了我们熟悉的两个有序链表的归并问题。不过由于涉及磁盘操作，那为了提高写入效率和检索效率，我们还需要针对磁盘的特性，在一些归并细节上进行优化。

C0树和C1树滚动合并可以视为有序链表归并

由于磁盘具有顺序读写效率高的特性，因此，为了提高C1树中节点的读写性能，除了根节点以外的节点都要尽可能地存放到连续的块中，让它们能作为一个整体单位来读写。这种包含多个节点的块就叫作 多页块（Multi-Pages Block）。

下面，我们来讲一下滚动归并的过程。在进行滚动归并的时候，系统会遵循以下几个步骤。

第一步，以多页块为单位，将C1树的当前叶子节点从前往后读入内存。读入内存的多页块，叫作清空块（Emptying Block），意思是处理完以后会被清空。

第二步，将C0树的叶子节点和清空块中的数据进行归并排序，把归并的结果写入内存的一个新块中，叫作填充块（Filling Block）。

第三步，如果填充块写满了，我们就要将填充块作为新的叶节点集合顺序写入磁盘。这个时候，如果C0树的叶子节点和清空块都没有遍历完，我们就继续遍历归并，将数据写入新的填充块。如果清空块遍历完了，我们就去C1树中顺序读取新的多页块，加载到清空块中。

第四步，重复第三步，直到遍历完C0树和C1树的所有叶子节点，并将所有的归并结果写入到磁盘。这个时候，我们就可以同时删除C0树和C1树中被处理过的叶子节点。这样就完成了滚动归并的过程。

LSM树是如何检索的？

现在你已经知道LSM树的组织过程了，我们可以来看，LSM树是如何完成检索的。

因为同时存在C0和C1树，所以要查询一个key时，我们会先到C0树中查询。如果查询到了则直接返回，不用再去查询C1树了。

而且，C0树会存储最新的一批数据，所以C0树中的数据一定会比C1树中的新。因此，如果一个系统的检索主要是针对近期数据的，那么大部分数据我们都能在内存中查到，检索效率就会非常高。

那如果我们在C0树中没有查询到key呢？这个时候，系统就会去磁盘中的C1树查询。在C1树中查到了，我们能直接返回吗？如果没有特殊处理的话，其实并不能。你可以先想想，这是为什么。

我们先来考虑一种情况：一个数据已经被写入系统了，并且我们也把它写入C1树了。但是，在最新的操作中，这个数据被删除了，那我们自然不会在C0树中查询到这个数据。可是它依然存在于C1树之中。

这种情况下，我们在C1树中检索到的就是过期的数据。既然是过期的数据，那为了不影响检索结果，我们能否从C1树中将这个数据删除呢？删除的思路没有错，但是不要忘了，我们不希望对C1树进行随机访问。这个时候，我们又该怎么处理呢？

我们依然可以采取延迟写入和批量操作的思路。对于被删除的数据，我们会将这些数据的key插入到C0树中，并且存入删除标志。如果C0树中已经存有这些数据，我们就将C0树中这些数据对应的key都加上删除标志。

这样一来，当我们在C0树中查询时，如果查到了一个带着删除标志的key，就直接返回查询失败，我们也就不用去查询C1树了。在滚动归并的时候，我们会查看数据在C0树中是否带有删除标志。如果有，滚动归并时就将它放弃。这样C1树就能批量完成“数据删除”的动作。


  • 内存结构中的检索（MemTable 和 Immutable Memtable）

    • LSM 树在内存中有 MemTable 和 Immutable Memtable 这两个结构用于缓冲写入和协助检索。它们通常采用如跳表这样高效的内存数据结构。

    • 当进行检索操作时，首先会在 MemTable 中查找数据。由于 MemTable 是按照键排序的有序结构，通过利用这种排序特性，可以使用类似于二分查找的方法在内存中快速定位数据。例如，如果要查找一个特定的键值，从 MemTable 的中间位置开始比较键的大小，如果目标键大于中间位置的键，则继续在 MemTable 的后半部分查找；反之，则在前半部分查找。这种方式能够在较少的比较次数内找到目标键（如果存在）。

    • 当 MemTable 达到一定大小被转换为 Immutable Memtable 后，它仍然可以用于检索。Immutable Memtable 虽然不能再写入新数据，但在其有效期内（直到被合并到磁盘的 SSTables），仍然可以作为一个快速检索的数据结构。检索方式和在 MemTable 中类似，因为它们具有相似的内部结构。

  • 磁盘 SSTables 中的检索

    • SSTables 是 LSM 树存储在磁盘上的主要数据结构，每个 SSTable 都是按照键排序的文件。在检索时，会利用 SSTables 的索引部分来快速定位数据在 SSTable 中的大致位置。

    • SSTables 的索引可以是稀疏索引，即它只记录了部分键值对的位置信息。例如，索引可能每隔一定数量的键值对记录一个索引条目。当查找一个键时，首先在索引中查找小于等于目标键的最大索引条目，确定数据可能存在的范围，然后在这个范围内进行更精细的查找，比如顺序扫描。

    • 对于多层 SSTables 的情况，检索通常从较高级别的 SSTables 开始。因为较新的数据更有可能在较高级别的 SSTables 中找到。如果在较高级别的 SSTables 中没有找到目标数据，就会依次向下查找较低级别的 SSTables。这种分层检索的方式有助于减少不必要的磁盘 I/O，提高检索效率。

  • 合并操作对检索的影响

    • LSM 树会定期进行合并操作，将多个 SSTables 合并为一个或几个新的 SSTables。合并操作会优化数据存储结构，去除重复的数据（如果有更新操作，会保留最新的值），并且重新组织索引。

    • 从检索的角度来看，经过合并后的 SSTables 结构更加紧凑和有序，使得检索过程更加高效。例如，合并后的 SSTables 可能减少了索引的层次，或者使得索引更加密集，从而在查找数据时能够更快地定位到目标键的位置。而且，由于去除了重复数据，减少了检索过程中需要检查的数据量，进一步提高了检索速度。

  1. C1 树的结构复杂性与数据一致性问题

    • C1 树是由多个 SSTables 组成的，每个 SSTable 都有自己独立的索引和数据部分。当在 C1 树中查询一个在 C0 树中未找到的键（key）时，即使在某个 SSTable 中查到了该键，也不能直接返回。这是因为 LSM 树存在数据合并（Compaction）的过程。在合并之前，数据可能是分散在不同的 SSTables 中的，而且不同 SSTables 中的数据可能存在不同的版本。

    • 例如，在数据写入过程中，可能先将一部分数据写入了某个 SSTable，之后又有新的数据更新或者写入了其他 SSTable。如果直接返回在某个 SSTable 中找到的键值，可能会返回一个旧版本的数据，而不是最新的数据。这就涉及到数据一致性的问题，为了保证返回的数据是最新的、准确的，不能简单地在找到键后就直接返回。

  2. 合并操作对数据的影响与检索策略调整

    • LSM 树会定期进行合并操作，目的是将多个 SSTables 合并为一个更紧凑、数据更准确的新 SSTable。在合并过程中，会对数据进行重新排序、去重，并且处理更新操作（保留最新的值）。

    • 所以，当在 C1 树中查询一个键时，需要考虑到数据可能正在合并或者尚未合并的情况。一种更好的策略是，在 C1 树中查询时，要检查是否有正在进行的合并操作，并且如果找到键值，还需要检查是否存在更新的数据在其他尚未合并的 SSTables 中。这可能需要遍历多个相关的 SSTables，或者参考合并操作的记录（如合并日志等），以确保返回的是经过合并后最新的、正确的数据。

  1. LSM 树合并过程中的一致性实现

    • 合并触发机制与数据整合：

      • LSM 树的合并操作通常是由一些条件触发的，比如当某个层次的 SSTables 数量达到一定阈值，或者系统负载较低时。在合并过程中，会选择相邻层次或者满足一定条件的 SSTables 进行合并。例如，将较高级别的小 SSTables 与较低级别的 SSTables 合并。在读取多个 SSTables 中的键值对时，会根据键的顺序进行重新排序和整合。对于相同键的数据，如果有更新操作，会按照一定的规则（通常是保留最新的值）来处理，以此保证数据的一致性。

    • 原子性操作与日志记录：

      • 为了确保合并过程的一致性，整个合并操作可以看作是一个原子操作。在开始合并之前，可以记录合并的相关信息，如参与合并的 SSTables 列表、合并的时间戳等，这些信息可以存储在一个日志文件中。如果在合并过程中出现故障（如断电、系统崩溃），可以通过回放日志来恢复合并操作，或者确定合并的状态，从而避免数据不一致的情况。

    • 版本控制与数据清理：

      • 在 LSM 树的存储结构中，可能会涉及到数据的版本问题。通过合理的版本控制机制，在合并过程中能够准确地识别和处理不同版本的数据。例如，每个键值对可以带有一个版本号，在合并时，根据版本号来确定要保留的数据。同时，合并操作也是一个清理旧数据和冗余数据的过程，通过去除重复的键值对和过期的数据，保证存储的数据都是有效的、最新的，进一步维护数据的一致性。

  2. LSM 树中索引和过滤器的处理

    • 索引构建与优化：

      • SSTables 作为 LSM 树存储在磁盘上的主要数据结构，通常包含索引部分和数据部分。索引的构建对于提高检索效率至关重要。SSTable 的索引可以是稀疏索引，即只记录部分键值对的位置信息。例如，索引可能每隔一定数量的键值对记录一个索引条目。在构建索引时，会根据数据的特点和查询模式进行优化。如果数据的分布比较均匀，索引的间隔可以相对固定；如果数据分布不均匀，可能会采用自适应的索引间隔，在数据密集的区域增加索引条目，以提高查询的命中率。

    • 过滤器的应用：

      • 为了减少不必要的磁盘 I/O，LSM 树可以使用过滤器。过滤器通常是基于布隆过滤器（Bloom Filter）的原理。布隆过滤器是一种空间效率很高的概率数据结构，用于判断一个元素是否在一个集合中。在 LSM 树中，每个 SSTable 可以对应一个布隆过滤器，用于快速判断一个键是否可能存在于该 SSTable 中。例如，在查询一个键时，先通过 SSTable 对应的布隆过滤器进行检查，如果过滤器判断键不存在，就可以直接跳过该 SSTable 的读取，从而节省磁盘 I/O 开销。

    • 索引和过滤器的更新与维护：

      • 在 SSTables 的合并过程中，索引和过滤器也需要进行更新和维护。当新的数据通过合并操作写入新的 SSTables 时，需要重新构建索引，以适应新的数据分布和结构。对于过滤器，也需要根据新的数据进行更新，确保其准确性。同时，在数据更新或删除操作频繁的情况下，还需要定期检查和优化索引和过滤器，以保证它们能够有效地辅助数据检索。

  3. LSM 树实现的优化

    • 写入优化 - 内存缓冲与批量写入：

      • LSM 树通过将数据先写入内存中的 C0 树（如采用跳表等高效内存数据结构）来缓冲写入操作。这避免了频繁的磁盘随机写入，因为内存操作速度远快于磁盘操作。当 C0 树达到一定大小后，进行批量写入磁盘的 C1 树，将随机写入转化为顺序写入。这种方式大大提高了写入性能，尤其适用于写入频繁的应用场景。

    • 读取优化 - 分层存储与缓存策略：

      • LSM 树采用分层存储结构，较新的数据更有可能在较高级别的 SSTables 或者内存结构（MemTable 和 Immutable Memtable）中找到。这种分层结构可以根据数据的热度（访问频率）进行优化。例如，可以将经常访问的数据缓存到内存中，减少磁盘 I/O。同时，利用 SSTables 的索引和过滤器，可以更快速地定位和读取数据，进一步提高读取性能。

    • 合并优化 - 自适应合并策略与并行合并：

      • 为了减少合并操作对系统性能的影响，LSM 树可以采用自适应合并策略。根据系统的负载、数据写入速度和存储资源等因素，动态调整合并的时机和范围。例如，在系统负载高时，延迟合并操作；在系统负载低时，加大合并的力度。此外，还可以采用并行合并的方法，同时对多个 SSTables 进行合并，提高合并的效率，缩短合并时间，减少对数据读写操作的干扰。


LSM树的检索过程是基于其分层存储结构设计的，通常包括内存中的MemTable（或称为C0树）和磁盘上的SSTable（或称为C1树及更高层级）。下面是LSM树进行数据检索的基本步骤：

  1. 检查MemTable:

    • 检索首先在最新的MemTable中进行。由于MemTable位于内存中，并且通常是跳表或平衡二叉查找树等高效的数据结构，因此这里的查询速度非常快。

    • 如果在MemTable中找到了对应的键值对，则直接返回结果。

  2. 检查Immutable MemTable:

    • 如果在MemTable中没有找到，那么会继续检查Immutable MemTable。这些也是最近写入但还没有被持久化到磁盘的数据。

    • 与MemTable一样，Immutable MemTable也支持快速查找。

  3. 检查SSTable:

    • 如果在内存中的所有MemTable都没有找到数据，接下来就会在磁盘上的SSTable中查找。

    • SSTable按Key排序，每个SSTable内部也可能包含多级索引和布隆过滤器来加速检索。

    • 使用布隆过滤器可以迅速判断某个键是否存在于当前的SSTable中。如果布隆过滤器指示键可能不存在，则可以直接跳过这个SSTable。

    • 如果布隆过滤器指示键可能存在，那么通过索引定位到相应的块，然后读取该块进行精确匹配。

  4. 合并结果:

    • 由于SSTable之间可能存在重复的键（因为它们是在不同时间点生成的），所以需要确保返回的是最新版本的数据。

    • 在某些实现中，可能会有一个“合并”过程，它会在不同的层级间进行，以确保最终返回的结果是最新的。

  5. 缓存机制:

    • 为了进一步提高性能，许多LSM树的实现还会使用缓存（如LRU缓存）来存储最近访问过的数据块。

    • 这样，在后续的查询中，如果请求的数据已经在缓存中，就可以直接从缓存中获取，而不需要再次访问磁盘。

总结

LSM树的检索逻辑是先查内存再查磁盘，这样可以最大化利用内存的速度优势。同时，通过使用高效的内存数据结构、布隆过滤器、多级索引以及缓存机制，LSM树能够在保证写入性能的同时，提供可接受的读取性能。这种设计非常适合于写密集型的应用场景，例如日志系统、监控系统等，其中写操作远多于读操作，而且读操作往往集中在较新的数据上。

您提到的问题非常关键，它涉及到LSM树如何处理数据版本的一致性。在LSM树中，当我们在C0树（MemTable）中没有查询到某个key时，系统会继续在磁盘中的C1树（SSTable）以及其他可能存在的更高级别的SSTables中查找。即使在C1树中查到了该key，也不能直接返回结果，原因如下：

数据版本一致性

  1. 可能存在更新的版本:

    • 在LSM树结构中，较新的数据通常存储在较高的层级（如内存中的MemTable），而较旧的数据则逐渐被写入较低层级（如磁盘上的SSTable）。

    • 如果在C0树中没有找到key，但在C1树中找到了，这并不意味着C1树中的数据就是最新的。有可能在C0树中有对该key的更新或删除操作，只是还没有持久化到磁盘。

  2. 删除标记和墓碑:

    • LSM树通过“墓碑”机制来标记已经删除的数据。如果一个key在C0树中被标记为删除，那么即使在C1树中存在该key，也应该被视为已删除。

    • 因此，在返回结果之前，必须确保检查所有层级中是否存在对该key的删除标记。

处理步骤

为了确保返回的结果是最新的且一致的，系统需要执行以下步骤：

  1. 从最高层级开始查找:

    • 从内存中的最新MemTable开始，逐层向下查找，直到找到该key或者遍历完所有的层级。

  2. 合并结果:

    • 在每一层中找到的数据需要进行合并。如果有多个层级中都存在同一个key，则需要根据时间戳或其他元信息确定哪个是最新版本。

    • 如果在较高层级中发现了该key的删除标记（墓碑），则应该忽略较低层级中的对应数据。

  3. 最终结果:

    • 经过上述步骤后，系统可以确定是否有一个有效且最新的key-value对，并将其返回给用户。

示例

假设我们有以下层级结构：

  • C0: MemTable

  • C1: SSTable 1

  • C2: SSTable 2

  1. 用户请求查询key K。

  2. 系统首先在C0（MemTable）中查找，没有找到。

  3. 接着在C1（SSTable 1）中找到了key K，值为 V1。

  4. 再次检查C0，发现有一个针对key K的删除标记。

  5. 根据删除标记，系统知道K已经被删除，因此不会返回V1，而是返回Key not found或类似的错误信息。

通过这种方式，LSM树能够保证数据的一致性和最新性，即使数据分布在不同的层级中。这种机制使得LSM树能够在频繁写入的情况下依然保持高效的数据检索。

LSM Tree 全名：Log Structured Merge Tree ，是一种在机械盘时代大放异彩的存储架构设计。LSM Tree 是一个把顺序写发挥到极致的设计架构。它的核心之一就是 log 文件。

笔者以几个问答来看下它的设计思想：

问题一：LSM Tree 存储引擎到底是什么？

不就是一个 key/value 存储引擎嘛。

问题二：用户写是怎么一个流程？

用户递交数据流程分为两步：写 log 文件，修改内存。所以会看到， 写的流程是非常简单的，用户的时延正常情况下就只包含这两步。

问题三：用户的删是怎么一个流程？

LSM Tree 为了极致的写性能把所有的更新操作都化作顺序写。也就是说， 删除也是写入。往存储里面写一条带删除标记的记录，而不是直接更新原来的数据。

问题四：这是一个持久化的存储吗？能保证掉电不丢数据吗？

是持久化的，因为 log 持久化了嘛。掉电不会丢数据，因为可以从 log 文件中恢复出来。恢复很简单，其实就是遍历 log 文件，然后解析出来就好。

那既然说到解析 log 文件，那么问题又来了，log 文件越大解析时间会越长，无限制增长这个是无法忍受的。

问题五：log 文件本身是不具备查找功能的，那怎么办？

log 文件其实是一种有时间顺序的文件，新数据不断的往后 append 写入，这种结构利于实现顺序写。但是 从用户 key/value 来讲是 log 的结构是一种无序的结构，它的查找效率非常低。

所以，自然而然，LSM 的架构里就需要引入一种新型的有序的数据结构，这个就是 sst 文件（ 全名：sorted string table ）。

所以，看到了，持久化的 log 数据向有序的 sst 文件转变是 LSM 的一个核心的流程。

划重点：sst 为有序的结构。

问题六：为什么 sst 文件经常很多个？

log 文件转变到 sst 文件是持续不断发生的。所以，很自然的，所以，系统中不会只有一个不断变大 sst 文件。因为一个庞大的空间这种查找效率会很低，并且每次重建一个有序的 sst 文件的开销会很大。

所以，在 LSM 的实践中，是划分了很多个有序的空间（sst 文件），每个文件内部又按照 block 划分，block 内部又按照 restart point 划分。

问题七：冗余或被删除的空间怎么释放？

把有效的数据从 sst 文件中读出来（删除或者被覆盖的旧数据丢弃）写到新的文件，然后修改指向关系，然后把旧的文件删掉。这个过程叫做 compact ，compact 是 LSM 设计中另一个核心流程。

LSM Tree 的设计思想？

存储的核心是读写，针对读写有不同的优化手段，比如预读，缓存，批量，并发，聚合等等。但是优化读和优化写能采用的手段其实不同，在机械盘时代，机械盘一定是瓶颈，它的随机性能极差，顺序的性能还能将就。

如果要优化 IO 读，有非常多的优化策略，比如使用多层缓存，CPU Cache，内存，SSD 等等，也可以采用丰富多彩的查询组织结构，比如各种平衡树型结构，提高读的效率。

但是，对于写，它一定是受限于磁盘的瓶颈。因为写的流程，数据落盘才算完。所以，对于写的优化手段非常有限，无论用什么手段，一定绕不过一点： 保持顺序，因为只有这样才能压榨出机械盘的性能。在写保持顺序的基础上，才去考虑加上其他的优化手段，比如批量，聚合等操作。

这正是 LSM Tree 的设计思想，考虑 极致的提升写的性能，读的性能则靠其他的手段解决。

下面介绍一些具体的 LSM Tree 项目的优秀实现。

LSM Tree 的架构

先声明一下，下面的架构设计就假定按照 leveldb 的实现介绍，虽然 rocksdb 也是 LSM 的实现但是加了很多复杂特性，介绍起来还挺麻烦的。

整体架构

先看看 LSM 的架构里有哪些东西吧，我们一个个说说：

CURRENT 是个文本文件，里面存的是一个文件名，记录当前可用的 MANIFEST 文件； MANIFEST 是一个二进制文件，里面存储的是整个集群的元数据； log 文件则是 wal 文件，是承接用户写 IO 的文件，这个文件的写性能直接关联用户的写性能； Memtable 和 Immutable Memtable 是内存结构，一般实现为一个具备查询效率的数据结构，比如跳表结构； ssttable 文件是内部生成的文件，每个文件都是按照 key 排序的文件。sst 内容格式都是一样的，但是大小不一定； Memtable（还有 Immutable Memtable）和 sstable 都是需要承接用户读 IO ，所以这两个里面都有大量的提升查询效率的手段；

确实，LSM树的架构中包含了多个组件，每个都有其特定的作用。根据您的描述，我们可以更详细地讨论这些组件：

  1. CURRENT 文件:

    • 这是一个文本文件，里面保存着当前有效的MANIFEST文件的名字。

    • 它用于追踪最新的元数据状态，确保系统能够正确加载最近的配置。

  2. MANIFEST 文件:

    • MANIFEST是一个二进制文件，它记录了整个存储系统的元数据信息。

    • 包括所有SSTable的信息（如文件名、大小、键范围等）以及版本历史等。

    • 当系统启动时，会读取MANIFEST来恢复状态，并且在每次进行合并操作后更新该文件以反映新的布局。

  3. Write-Ahead Log (WAL) 文件:

    • 也称为日志文件或预写日志，用来保证数据的持久性和一致性。

    • 在内存中的数据被刷新到磁盘之前，先记录到WAL中，以防系统崩溃导致未保存的数据丢失。

    • WAL提供了额外的安全性，因为即使MemTable没有及时刷入磁盘，也可以通过重放WAL来恢复数据。

  4. MemTable:

    • MemTable是位于内存中的临时存储区，用于接收新写入的数据。

    • 通常使用跳表或者平衡树结构实现，以支持高效的插入和查找操作。

    • 当MemTable达到一定大小时，会被标记为不可变（Immutable MemTable），并准备被持久化到磁盘上。

  5. Immutable MemTable:

    • 一旦MemTable满了，就会转换成Immutable MemTable。

    • Immutable MemTable不再接受新的写入请求，但仍然可以提供读服务。

    • 随后，Immutable MemTable会被异步地转储到磁盘形成SSTable。

  6. SSTable (Sorted String Table):

    • SSTable是磁盘上的持久化数据存储格式，每个SSTable都按Key排序。

    • 每个SSTable内部可能包含索引块和过滤器（如布隆过滤器），以便快速定位数据或排除不存在的键。

    • SSTables之间可能会定期进行合并，以去除重复的数据并保持层级之间的平衡。

  7. 查询优化:

    • 为了提高查询效率，MemTable和SSTable都会采用各种技术，比如缓存机制、布隆过滤器、多级索引等。

    • 布隆过滤器可以帮助快速判断某个键是否存在于SSTable中，避免不必要的I/O操作。

    • 多级索引使得可以从大量数据中快速定位到所需的键值对。

综上所述，LSM树的设计充分考虑了写密集型工作负载的特点，并通过多种手段保证了良好的读性能。这种结构非常适合需要处理大量写入请求的应用场景，例如时间序列数据库或实时分析平台。

以下是对 LSM 架构中各个部分的详细介绍：

一、CURRENT 文件

CURRENT 文件是一个文本文件，其主要作用是记录当前可用的 MANIFEST 文件的名称。它就像是一个指针，指向系统正在使用的元数据文件，确保系统在需要获取集群元数据时能够快速准确地找到正确的文件。在系统运行过程中，当 MANIFEST 文件发生更新时，CURRENT 文件也会相应地进行修改，以始终保持对最新元数据文件的引用。

二、MANIFEST 文件

MANIFEST 是一个二进制文件，存储着整个集群的元数据。它包含了关于数据存储结构、各个数据文件的位置和状态、表结构信息、索引信息等关键数据。可以将其视为整个存储系统的 “地图”，系统通过读取和解析这个文件，能够了解数据的组织方式和存储位置，从而高效地进行数据的读写操作。

三、log 文件（Write-Ahead Log，WAL）

log 文件作为 WAL，在 LSM 架构中起着至关重要的作用。它是承接用户写 IO 的文件，直接关联着用户的写性能。每当有新的写操作发生时，首先会将操作记录顺序写入到这个日志文件中，以确保数据的持久性。在系统出现故障（如断电、进程崩溃等）时，通过回放 WAL 中的日志，可以将系统恢复到故障发生前的状态，从而保证数据不会丢失。由于写日志是顺序写入操作，相比随机写入磁盘，它具有较高的性能。

四、Memtable 和 Immutable Memtable

  1. 内存结构特点：

    • Memtable 和 Immutable Memtable 是内存中的数据结构，一般实现为具备高效查询效率的数据结构，比如跳表结构。跳表通过在链表的基础上增加多层索引，能够快速地进行插入、删除和查找操作。这种数据结构非常适合用于缓冲写入操作和快速响应查询请求。

    • Memtable 是可写的内存结构，新的数据首先被写入到 Memtable 中，并按照键的顺序进行排序。当 Memtable 达到一定大小限制时，它会被转换为 Immutable Memtable，不再接受新的写入操作。

  2. 承接用户读 IO 的作用：

    • 由于它们存储在内存中，读取速度非常快。因此，Memtable（还有 Immutable Memtable）需要承接用户的读 IO 请求。为了提升查询效率，它们通常采用了一些优化手段。例如，可能会使用缓存机制，将最近访问过的数据缓存起来，以便下次快速访问；还可能会使用索引结构，进一步加快查找特定键值对的速度。

五、SSTable 文件

  1. 文件特点：

    • SSTable 文件是内部生成的文件，每个文件都是按照键排序的文件。这意味着在读取数据时，可以通过二分查找等高效算法快速定位到所需的键值对。SSTable 的内容格式都是一样的，但是大小不一定，这取决于写入的数据量和合并操作的时机。

  2. 承接用户读 IO 的优化：

    • SSTable 也需要承接用户读 IO，因此也采用了大量提升查询效率的手段。例如，每个 SSTable 文件可能会包含一个索引结构，记录键的范围和对应的文件位置，以便快速定位数据。此外，还可能会使用压缩算法来减少文件大小，提高读取性能。同时，系统可能会根据访问频率和时间等因素，将热数据缓存在内存中，进一步加快读取速度。

从数据的格式转变来讲：

log 的数据和 memtable 的数据是对应起来的（同一份数据），log 的数据结构本质是无序的，所以必须依赖于 memtable 的查询效率； log 和 memtable 的这份数据下一步的去路就是 sstable 文件喽，这些个 sstable 文件属于 Level 0 ； Level 0 的 sstable 文件的去路是更底层 Level 的 sstable 文件喽，小的合并成大的，不断的往下沉喽；

思考一个小问题：log 存储的数据和 memtable 存储的数据量一般是一样大的？为什么？

log 是时间上有序但是内容上无序的格式，它上面的数据就只能依赖于 memtable 来提高查询效率。换句话说，它两就是一份数据，自然一样大。

写的流程

看了整体架构之后，简单看一眼用户的数据怎么存到系统的。步骤只有两步：

数据先写 log 文件；

数据再插入 memtable 结构中；

就这样，用户的写流程就算完了。由于 log 是持久化的，所以能确保数据不丢。这是对写流程的极致优化，只有一个写 log 的 io 消耗，并且是永远的 append 写入，简直是最理想的写流程。

读的流程

数据读的流程就略显复杂了，因为数据的范围太大了，那么多 sst 文件，那么多 key 的范围，可得好好查一查。

当然了，先从 memtable 开始，查不到就一步步往底层查，也就是到 Level 0，再到 Level 1，Level 2 等等。这里耗费的 IO 次数就不好说了，读的性能远比写要差多了。

既然聊到这里，大家都知道 sst 的读性能很差，那咋办？

加“索引”喽。和数据库的索引效果类似，都是为了提高读和查询效率的方法。所以，你仔细看会发现，在 leveldb，rocksdb 的实现离，有大量的索引结构。比如：

leveldb 把整个 sst 文件划分成一个个 block 小段，然后在 sst 尾端都有一个 index block，用来索引数据块。这样就能快速定位到 key 在哪一个 block 里； sst 文件中还有个 bloom filter 的小块，布隆过滤器喽，又给读提升了一点性能； 每个 block 里面呢，还有个 restart point 的数组，也能提高读性能；

比如，sst 的图示如下：

整体设计就是把 sst 切成一个个有序的小块，极大的提高查询的效率。每一个 block 里面又有按照 restart point 数组划分：


其实，还有很多讲究哦，这就不提了，太多了，很多都是为了 查询效率。

compact 的流程

leveldb 的 compact 分为两种：

minor compact ：这个是 memtable 到 Level 0 的转变； major compact ：这个是 Level 0 到底层或者底下的 Level 的 sstable 的相互转变；

这里值得提一点的是，sstable 每个都是有序的。但是呢，Level 0 的文件之间可能是有范围交叉的，但是 Level 0 之下的 sstable 文件则绝对没有交叉。正因如此，Level 0 的文件个数就不能太多，不然会影响查询效率（因为相互覆盖嘛，所以每一个都要查的）。

为什么会这样呢？

因为 Level 0 的文件是直接来源于 memtable，而没有去做合并。

优秀的开源实现
Leveldb

leveldb 是谷歌开源的一个 key/value 存储引擎，github 地址：https://github.com/google/leveldb 。由大佬 Sanjay Ghemawat 和 Jeff Dean 开发并开源。整个项目 c++ 实现，代码精致优雅，值得学习。

rocksdb

rocksdb 是 facebook 开源的一个 key/value 存储引擎，github 地址：https://github.com/facebook/rocksdb 。是基于 leveldb 项目的优化实现，适配 facebook 数据库团队的实际场景，特性要比 leveldb 多。整个项目 c++ 实现，代码实现也非常优秀，值得学习。

goleveldb

考虑到我们的读者很多都是 gopher ，那自然要推荐一个 golang 的版本，就是 goleveldb ，github 地址：https://github.com/syndtr/goleveldb ，这个项目实现的更小巧，值得学习推荐。

如果说，你是个 gopher，并且对 LSM Tree 感兴趣，那么完全可以去撸一撸 goleveldb 的源码。只要撸懂一个，那以后再深入就得心应手了。

更好的学习选择？用 Python 解析 LSM ？

其实，还有一个好选择，我们 fork 了 goleveldb ，会不定期更新一些代码注释，感兴趣的也可以看下，Github 地址：https://github.com/liqingqiya/readcode-goleveldb-master。

为什么越来越多“唱衰” LSM 的声音呢？

归根结底还是硬件发展起来了。在原先的机械盘（ HDD ）时代，leveldb/rocksdb 的最佳实践就是一个磁盘只有一个写入源（ wal ），所有的写请求都由这一个线程递交。这个是合理的，因为 HDD 最好的优化就是顺序化，并且一个线程串行递交请求也足以把 HDD 跑满。

但是自从 SSD 这种介质普及之后，一切都变了，单线程串行递交请求已经跑不满硬件了，比如 pcie 盘的通道就非常多，要并发全力压才能压的满。

还有就是 SSD 盘随机性能太好了，单就性能数据来讲和顺序的差不多。那这个时候 LSM Tree 为了顺序化而做的复杂的东西可能就显得优先多余了，反倒让系统变得复杂。

划重点：SSD 多通道并发、超高的随机性能是变革的核心因素。

那存储引擎的架构会怎么演进呢？

演进方向笔者也不确定。不过有一篇很出名的 FAST 上的论文 ：《WiscKey: Separating Keys from Values in SSD-Conscious Storage》就讨论了在 SSD 时代，LSM 架构的优化思路。

并且立马就有开源的实现跟进了这个思路，比如 go 的 badger ，rocksdb 本身也有个集成了 BlobDB 的实验版本。

但实话说，LSM Tree 的架构会持续的优化，但会长时间持续存在，因为并不是所有场景都要用 SSD ，并且它不便宜。

总结

LSM Tree 是把写性能优化到极致的结构，当然了，这个极致的考虑就在于： 顺序 IO、批量操作 ； 当顺序并不是性能的关键因素的时候，LSM Tree 的架构就有点冗余。这个想想最近不断出现的针对 SSD 盘的优化思路就知道了； LSM Tree 的架构中没有覆盖写 ，log 永远 append，sst 也是读旧的写新的。CURRENT，MANIFEST 也是先写临时文件，最后 rename 一下。所以 LSM Tree 的安全、一致性就得到了保证； LSM 牺牲了的读性能就靠 各种“索引”结构 、各种 cache 来解决； compact 有两种：minor，major compact 。minor compact 是有序的 mem 数据（对应无序的 log 文件）到 sst 的转变。major compact 是 sst 内部之间的转变； 在 SSD 没出来之前， 写的有效优化手段只有顺序+批量，读的优化手段千奇百怪，从 LSM 的实现就可以窥见一二；

后记

今天聊聊 LSM Tree 的架构，分享一些设计思考，希望能帮到大家。点赞、在看是对我们最大的支持。

文章摘自：https://www.sohu.com/a/514685786_121124360 有改动

好了，今天的内容就先讲到这里。我们一起来回顾一下，你要掌握的重点内容。

在写大于读的应用场景下，尤其是在日志系统和监控系统这类应用中，我们可以选用基于LSM树的NoSQL数据库，这是比B+树更合适的技术方案。

LSM树具有以下3个特点：

  1. 将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；

  2. 用批量写入代替随机写入，并且用预写日志WAL技术保证内存数据，在系统崩溃后可以被恢复；

  3. 数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写入效率。

LSM树的这些特点，使得它相对于B+树，在写入性能上有大幅提升。所以，许多NoSQL系统都使用LSM树作为检索引擎，而且还对LSM树进行了优化以提升检索性能。在后面的章节中我们会介绍，工业界中实际使用的LSM树是如何实现的，帮助你对LSM树有更深入的认识。

  1. 索引的内存 - 磁盘划分与树合并机制

    • 索引的划分优势：

      • 将索引分为内存和磁盘两部分是一种高效的设计策略。内存部分（如 MemTable）能够快速响应写入和查询操作。因为内存的读写速度比磁盘快得多，所以在内存中存储的索引可以迅速处理新数据的插入和近期数据的查询。例如，在一个高并发的日志存储系统中，新产生的日志记录首先插入到内存索引部分，能够快速完成写入操作，并且在短时间内查询这些新记录时，也可以直接从内存中获取，大大提高了系统的响应速度。

    • 树合并的过程和重要性：

      • 当内存中的索引结构达到阈值时启动树合并操作。这个过程涉及将内存中的数据与磁盘中的数据进行整合。在合并过程中，系统会读取内存和磁盘中的相关数据部分，按照一定的规则（如键的顺序）重新组织数据。例如，对于相同键的记录，如果存在更新操作，会保留最新的值。通过合并，可以优化数据存储结构，减少磁盘上 SSTables（Sorted String Tables）的数量，避免磁盘空间的过度碎片化，同时也有助于提高后续的数据读取效率。

  2. 批量写入与 WAL 技术保障数据恢复

    • 批量写入的性能提升：

      • 用批量写入代替随机写入是 LSM 树提高写入性能的关键手段。操作系统对磁盘的读写是以块为单位的，批量写入利用了这一特性。例如，当内存中的数据积累到一定程度后，将这些数据组成磁盘块，然后一次性写入磁盘。与随机写入相比，批量写入大大减少了磁盘寻道次数，因为磁盘寻道时间在磁盘操作中占据了相当大的比例。顺序写入的性能要比随机写入高很多，这样就可以有效提高系统的整体写入速度。

    • WAL 技术的原理和作用：

      • 预写日志（WAL）技术是保证数据可靠性的重要手段。WAL 是一个顺序写入的日志文件，它记录了所有的写入操作。每一个写入操作在真正修改数据之前，会先在 WAL 中记录操作的详细信息，包括操作类型（如插入、更新、删除）和对应的键值对信息。在系统崩溃后，通过回放 WAL 中的日志，可以将系统恢复到一个一致的状态。例如，如果在将内存数据写入磁盘的过程中系统崩溃，重新启动后可以根据 WAL 中的记录重新构建内存数据结构，确保数据不会丢失。

  3. 日志追加写与顺序写提高效率

    • 日志追加写的方式：

      • 数据采取类似日志追加写的方式写入磁盘是 LSM 树的一个重要特点。这种方式就像在日志文件中不断添加新的记录一样，新的数据总是追加在已有数据的末尾。例如，在存储日志数据的应用场景中，新的日志条目按照时间顺序依次写入磁盘，而不是像传统的数据库那样可能需要在磁盘的不同位置进行插入操作。

    • 顺序写的性能优势：

      • 以顺序写的方式进行数据写入能够充分利用磁盘的性能。磁盘在顺序写入时，读写头可以沿着磁道连续地写入数据，不需要频繁地移动位置。这样可以大大提高磁盘的写入带宽利用率，减少写入时间。与随机写入相比，顺序写入的速度可以提高数倍甚至更多，尤其在写入大量数据的情况下，这种性能优势更加明显，使得 LSM 树能够高效地处理持续大量生成的数据，如日志系统、监控系统中的数据写入。

您提到的这三个特点是LSM树（Log-Structured Merge Tree）的核心设计原则，这些特点共同作用使得LSM树在处理大量写入操作时表现出色。下面我将对每个特点进行详细解释：

1. 索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并

内存部分 (C0 树 - MemTable):

  • 数据首先被写入到位于内存中的数据结构，通常是一个跳表或平衡二叉查找树。

  • 这种内存结构支持高效的插入、删除和查询操作。

  • 当MemTable的大小达到预设的阈值时，它会被标记为Immutable MemTable，并且系统会创建一个新的空MemTable来继续接收新的写入。

磁盘部分 (C1 及更高层级树 - SSTable):

  • Immutable MemTable随后会被异步地转储到磁盘上，形成一个SSTable。

  • 每个SSTable都是按Key排序的数据文件，它们可以进一步被分层管理。

  • 随着更多的数据到来，多个SSTable可能会进行合并（Compaction），以去除过期的数据并保持层级之间的平衡。

2. 用批量写入代替随机写入，并且用预写日志WAL技术保证内存数据，在系统崩溃后可以被恢复

批量写入:

  • LSM树通过将多个写入请求缓存在内存中，然后一次性批量写入磁盘，从而减少了磁盘I/O次数。

  • 批量写入通常是顺序写入，这比随机写入更高效，因为磁盘在顺序写入时能够达到更高的吞吐量。

预写日志（Write-Ahead Log, WAL）:

  • 为了确保数据的一致性和持久性，LSM树使用了WAL机制。

  • 在数据写入MemTable之前，先将数据记录到WAL中。

  • 如果系统发生崩溃，可以通过重放WAL来恢复未持久化到磁盘的数据，从而保证不会丢失任何已提交的写入。

3. 数据采取类似日志追加写的方式写入磁盘，以顺序写的方式提高写入效率

日志追加写（Append-Only Writes）:

  • 新的数据总是追加到现有数据的末尾，而不是覆盖旧的数据。

  • 这种方式避免了随机写入带来的性能问题，提高了写入效率。

  • 由于新数据总是按时间顺序添加，因此也便于实现基于时间戳的数据检索。

顺序写入:

  • LSM树利用磁盘顺序写入比随机写入更快的特点，通过批量写入和追加写的方式来提高整体写入性能。

  • 顺序写入不仅减少了磁头移动的时间，还允许磁盘缓存更有效地工作。

总结

LSM树通过将索引分为内存和磁盘两部分、采用批量写入和预写日志技术以及使用日志追加写的方式，实现了高效的写入性能和良好的数据一致性。这种设计特别适用于写密集型的应用场景，如日志系统、监控系统等。同时，通过定期的树合并（Compaction）过程，LSM树还能保持数据的紧凑性和读取效率。

  1. 预写日志（WAL）技术的具体实现方式

    • 日志结构：

      • WAL 是一种顺序写入的日志文件。它的结构通常是一系列按照时间顺序记录的操作日志，每个日志条目包含操作类型（如插入、更新、删除）和对应的键值对信息。例如，在数据库应用中，一个插入操作的日志条目可能包含 “INSERT” 操作类型标识，以及要插入的键值对的具体内容。

    • 写入过程：

      • 每当有新的写入操作（包括插入、更新、删除）发生时，系统首先会将该操作记录到 WAL 中。这个过程是同步的，即写入操作必须等待 WAL 记录完成后才能继续。例如，在一个存储系统中，用户发起一个更新键值对的请求，系统会先在 WAL 中记录类似 “UPDATE, [key], [new_value]” 的信息，确保这个记录被安全地写入磁盘（或可靠的存储介质）后，才会对实际的数据存储区域（如内存中的 MemTable 或磁盘中的 SSTables）进行更新操作。

    • 恢复机制：

      • 在系统出现故障（如断电、进程崩溃等）后，系统通过回放 WAL 中的日志来恢复数据。在恢复过程中，系统会按照日志条目的时间顺序依次处理每个操作。例如，如果日志中有一系列的插入操作记录，系统会在重启后重新执行这些插入操作，将数据插入到相应的数据结构中。对于更新和删除操作也是如此，通过这种方式可以将系统恢复到一个一致的状态，确保数据不会丢失。

  2. 除了 LSM 树之外的数据存储结构

    • B + 树：

      • B + 树是一种平衡的多路查找树，在关系型数据库中被广泛应用。它的特点是所有的数据都存储在叶子节点，非叶子节点只用于索引。这种结构使得 B + 树能够保持较好的平衡性，从而保证查询操作的时间复杂度为对数级别。例如，在一个大型的关系型数据库中，使用 B + 树来存储数据表的索引，能够在对数时间内找到特定记录所在的磁盘位置，从而实现高效的查询。但是，B + 树在频繁写入操作时，由于需要频繁地在磁盘上进行随机写入（因为数据存储在叶子节点，每次插入可能需要在磁盘上找到合适的位置插入新数据），性能会受到较大影响。

    • 哈希表：

      • 哈希表是一种基于哈希函数实现的数据结构，通过将键映射到一个固定大小的数组槽位来存储数据。它的优点是插入和查找操作在理想情况下具有常数时间复杂度。例如，在一个缓存系统中，使用哈希表来存储缓存数据，当需要查找一个键对应的缓存值时，通过哈希函数快速计算出存储位置，直接获取数据。然而，哈希表的缺点是不支持范围查询，而且在处理哈希冲突时可能会影响性能。此外，哈希表在存储大量数据时，可能需要频繁地进行扩容操作，这也会带来一定的性能开销。

    • 红黑树：

      • 红黑树是一种自平衡二叉查找树，它在保持二叉树的基本结构的同时，通过特定的规则（如节点颜色的标记和调整）来保证树的平衡性。红黑树的插入、删除和查找操作的时间复杂度都是对数级别。它适用于一些需要动态维护有序数据集合的场景。例如，在一些编程语言的标准库中，红黑树被用于实现有序集合或映射。但是，红黑树在存储大规模数据时，由于树的高度可能会增加，导致查询和更新操作的性能相对较低，而且它的实现相对复杂，在磁盘存储方面没有像 B + 树和 LSM 树那样专门的优化。

  3. 衡量 LSM 树性能和效率的方法

    • 写入性能：

      • 吞吐量：衡量单位时间内能够成功写入的数据量。例如，可以通过在一定时间内（如 1 秒）统计写入的键值对数量来计算吞吐量。高吞吐量表示 LSM 树能够快速地处理大量的写入请求，这在日志系统、监控系统等写入密集型应用场景中非常重要。

      • 写入延迟：指从发起写入请求到写入操作实际完成所经历的时间。较低的写入延迟意味着系统能够快速响应写入操作，提升用户体验。可以通过记录每个写入操作的开始时间和结束时间来计算写入延迟。

    • 读取性能：

      • 读取吞吐量：与写入吞吐量类似，衡量单位时间内能够成功读取的数据量。通过统计在一定时间内读取的键值对数量来确定。高读取吞吐量表示 LSM 树在处理大量读取请求时具有良好的性能。

      • 读取延迟：从发起读取请求到获取到所需数据所花费的时间。这取决于数据在内存还是磁盘中的位置、索引结构的有效性以及是否需要进行合并操作等因素。较低的读取延迟对于需要快速响应查询的应用场景（如实时监控系统中的数据查询）至关重要。

    • 空间利用率：

      • 衡量 LSM 树存储数据所占用的磁盘空间与实际数据量的比例。通过比较存储系统中数据的实际大小和分配的磁盘空间大小来计算。高空间利用率表示 LSM 树能够有效地利用磁盘空间，减少磁盘浪费。例如，通过合理的合并操作和数据压缩技术，可以提高空间利用率。

    • 合并操作性能：

      • 合并频率：统计单位时间内进行合并操作的次数。如果合并频率过高，可能会影响系统的读写性能，因为合并操作需要消耗系统资源（如 CPU、磁盘 I/O）。

      • 合并时间：每次合并操作所花费的时间。较短的合并时间表示系统能够快速地完成数据的整合和优化，减少对正常读写操作的干扰。可以通过记录合并操作的开始时间和结束时间来计算合并时间。

预写日志（WAL）技术的具体实现方式

预写日志（Write-Ahead Logging, WAL）是一种常见的数据持久化技术，用于确保在系统崩溃后数据的一致性和可恢复性。WAL的基本思想是在修改内存中的数据之前，先将这些修改记录到一个持久化的日志文件中。以下是WAL技术的具体实现步骤：

  1. 日志记录:

    • 在进行任何数据修改操作前，系统首先将要执行的操作记录到WAL文件中。

    • 记录通常包括操作类型（如插入、更新或删除）、操作涉及的数据项等信息。

  2. 同步到磁盘:

    • 为了保证日志的持久性，WAL文件需要定期或按需被同步到磁盘上。

    • 这个过程可以通过操作系统提供的fsync()或fdatasync()等函数来完成，以确保日志已经真正写入磁盘。

  3. 内存操作:

    • 一旦WAL记录被成功写入磁盘，系统就可以安全地对内存中的数据结构（如MemTable）进行相应的修改。

    • 如果在修改内存数据的过程中发生系统崩溃，未完成的事务可以从WAL中恢复。

  4. 日志清理:

    • 当内存中的数据最终被持久化到磁盘（例如，在LSM树中，当MemTable被转储为SSTable时），相关联的WAL记录可以被标记为已处理，并在适当的时候从WAL文件中移除。

    • 清理过程有助于保持WAL文件的大小在一个合理的范围内，避免无限增长。

  5. 恢复机制:

    • 系统重启后，会检查WAL文件并重放其中的所有未完成的日志记录，以恢复内存中的状态。

    • 这一过程确保了即使在系统崩溃的情况下，也不会丢失任何已提交的数据。

其他的数据存储结构

除了LSM树之外，还有多种常用的数据存储结构，每种都有其特定的应用场景和优势：

  1. B+树:

    • B+树是一种自平衡的搜索树，常用于关系型数据库中作为索引结构。

    • 它支持高效的范围查询和顺序访问，并且能够很好地处理随机读写。

  2. 哈希表:

    • 哈希表通过哈希函数将键映射到固定大小的数组中，提供平均时间复杂度为O(1)的查找性能。

    • 适用于需要快速查找但不需要排序或范围查询的场景。

  3. 跳表（Skip List）:

    • 跳表是一种基于概率的有序数据结构，它允许快速的查找、插入和删除操作。

    • 跳表通过多层链表的方式提供了接近于二叉查找树的性能，同时比AVL树或红黑树更容易实现。

  4. Trie（字典树）:

    • Trie是一种树形数据结构，特别适合存储字符串键值对。

    • 它支持高效的前缀匹配和范围查询，常用于文本搜索和自动补全功能。

  5. 图数据库:

    • 图数据库使用图结构来表示数据及其关系。

    • 适用于社交网络分析、推荐系统等具有复杂关联性的数据集。

  6. 列式存储:

    • 列式存储将数据按列而不是行组织，提高了聚合查询的效率。

    • 适用于数据分析和大数据处理场景。

衡量LSM树的性能和效率

衡量LSM树的性能和效率可以从以下几个方面考虑：

  1. 写入吞吐量:

    • 测量单位时间内可以处理的写入请求的数量。

    • 通常用每秒写入次数（writes per second, WPS）来衡量。

  2. 读取延迟:

    • 测量从发出读取请求到返回结果的时间。

    • 可以通过平均延迟、最大延迟和第99百分位延迟等指标来评估。

  3. 空间利用率:

    • 检查数据存储所需的磁盘空间与实际存储的数据量之间的比例。

    • 高效的压缩算法和合并策略可以帮助提高空间利用率。

  4. 写放大:

    • 写放大是指每次逻辑写入导致的实际物理写入量。

    • 低写放大意味着更少的I/O操作，从而提高整体性能。

  5. 读放大:

    • 读放大是指为了满足一个读取请求而必须读取的数据量。

    • 优化索引和布隆过滤器的使用可以减少不必要的读取操作。

  6. 合并频率:

    • 合并操作是LSM树维护的关键过程，但它也会消耗大量的资源。

    • 适当的合并策略可以减少合并频率，从而降低后台开销。

  7. 缓存命中率:

    • 使用缓存可以显著提高读取性能。

    • 缓存命中率越高，表明更多的读取请求可以直接从缓存中得到满足，减少了磁盘访问。

通过上述指标，可以全面评估LSM树在不同工作负载下的表现，并根据具体需求调整参数和配置，以达到最佳性能。