LSM 树：为写入而生的存储结构

在数据库存储引擎领域，B+ 树长期占据主导地位。它在读取性能和范围查询方面表现出色，是绝大多数关系型数据库的默认选择。然而，随着日志采集、监控指标、物联网、消息系统等写入密集型应用的兴起，B+ 树在高强度写入下的局限逐渐显现。

LSM 树（Log-Structured Merge-Tree，日志结构合并树）是另一种重要的存储结构。它通过将随机写转换为顺序写，大幅提升了写入吞吐量，已成为众多键值存储、分布式数据库和时序数据库的核心。本文介绍 LSM 树的设计动机、基本结构、读写流程、压缩策略，以及围绕它展开的各种权衡与优化。

一、设计动机：随机写的代价

B+ 树的写入方式

B+ 树是一种原地更新（In-place Update）的结构。写入一条数据时，需要先从根节点向下查找，定位到该键所在的叶子页，然后在页内修改数据，再将整个页写回磁盘。

这种方式存在几个问题：

• 随机写入：不同的键分布在不同的页中，连续写入的数据会落在磁盘的不同位置，形成大量随机 I/O；
• 写放大：即使只修改一条几十字节的记录，也需要写回整个数据页，通常为 4KB 或 16KB；
• 页分裂：当页满时需要分裂，进一步产生额外的写入，并可能导致数据页在磁盘上不连续。

顺序写与随机写的差距

无论是机械硬盘还是固态硬盘，顺序写的性能都明显优于随机写。

对于机械硬盘，随机写需要频繁寻道，每秒只能完成数百次操作，而顺序写可以达到每秒数百 MB 的吞吐量，差距可达数百倍。

对于固态硬盘，虽然没有机械寻道的开销，但其内部以页为单位写入、以块为单位擦除，且不能原地覆盖。大量随机小写入会加重内部的垃圾回收负担，降低性能并加速闪存磨损。

核心思想

LSM 树的核心思想可以概括为一句话：不在原地修改数据，而是把所有写入都追加到新的位置，再在后台批量整理。

写入时只做顺序追加，将代价推迟到后台的合并过程中，以批量、顺序的方式完成。这是一种典型的以读取性能和后台开销换取写入性能的设计。

二、基本结构

一个典型的 LSM 树存储引擎由以下几个部分组成。

1. 预写日志

预写日志（Write-Ahead Log，WAL）是一个只追加写入的磁盘文件。每次写入数据时，首先将操作记录追加到预写日志中。

由于内存中的数据在进程崩溃或断电时会丢失，预写日志用于在重启时恢复这部分数据。追加写入是顺序 I/O，代价很低。

2. 内存表

内存表（MemTable）是位于内存中的有序数据结构，通常使用跳表或平衡树实现。写入操作在追加预写日志之后，直接插入内存表。

由于内存表在内存中，写入速度极快。同时它保持键的有序性，便于后续按顺序写入磁盘。

当内存表的大小达到阈值时，它会被转为不可变内存表（Immutable MemTable），不再接收新的写入。同时创建一个新的内存表接收后续写入。不可变内存表随后被后台线程写入磁盘。

3. 有序字符串表

内存表写入磁盘后，形成一个有序字符串表（Sorted String Table，SSTable）文件。SSTable 具有以下特点：

• 文件中的键值对按键有序排列；
• 文件一旦写入，永不修改，只会被整体删除；
• 写入过程是一次完整的顺序写。

一个 SSTable 文件内部通常包含以下组成部分：

• 数据块：存储实际的键值对，每个块通常为几 KB 到几十 KB，可以单独压缩；
• 索引块：记录每个数据块中的最大键（或最小键）及其在文件中的偏移量，用于快速定位数据块；
• 过滤器块：通常是布隆过滤器，用于快速判断某个键是否可能存在于该文件中；
• 元数据和文件尾：记录各部分的位置信息。

一个 SSTable 写入完成后，对应的预写日志段就可以删除了。

4. 分层组织

随着写入的持续进行，磁盘上会产生越来越多的 SSTable 文件。LSM 树将这些文件组织为多个层级（Level），通常记为 L0、L1、L2 等：

• L0 层：直接由内存表写出的文件。由于每个文件独立生成，不同文件之间的键范围可能相互重叠；
• L1 及以下各层：由后台合并生成。在大多数策略下，同一层内的文件键范围互不重叠，整层可以看作一个大的有序序列，被切分为多个文件；
• 层级容量：每一层的总容量通常是上一层的若干倍，例如 10 倍。数据从上层逐步向下层迁移，越往下的层级数据越旧、容量越大。

三、写入流程

LSM 树的写入流程非常简洁：

1. 将写入操作追加到预写日志；
2. 将键值对插入内存表；
3. 返回写入成功。

整个过程只涉及一次顺序的磁盘追加和一次内存操作，没有任何随机磁盘 I/O。这正是 LSM 树写入性能高的根本原因。

更新与删除

在 LSM 树中，更新和插入没有区别，都是写入一条新的键值对。新写入的版本会遮盖旧版本，旧版本在后续的合并过程中被清除。

删除同样不是真正删除数据，而是写入一条特殊的记录，称为墓碑（Tombstone），标记该键已被删除。读取时遇到墓碑，即认为该键不存在。墓碑本身和被它遮盖的旧数据，都要等到合并过程中才会被真正清除。

为了区分同一个键的多个版本，每条写入记录通常会附带一个单调递增的序列号。序列号还被用于实现多版本并发控制和快照读取。

四、读取流程

LSM 树的读取比写入复杂得多。由于同一个键的不同版本可能分散在内存表和多个层级的文件中，读取时必须从新到旧依次查找，找到的第一个版本即为最新版本。

点查询

查询单个键时，查找顺序为：

1. 查找当前的内存表；
2. 查找不可变内存表；
3. 查找 L0 层的所有文件，由于文件之间键范围重叠，需要按从新到旧的顺序逐个检查；
4. 依次查找 L1、L2 等层级。由于同一层内文件键范围不重叠，每层只需检查一个文件。

一旦在某处找到该键（或其墓碑），就立即返回。如果查到最底层仍未找到，则该键不存在。

在最坏情况下，例如查询一个根本不存在的键，需要检查每一层，产生多次磁盘读取。这是 LSM 树读取性能的主要瓶颈。

布隆过滤器的作用

为了减少无效的磁盘读取，每个 SSTable 文件都附带一个布隆过滤器。

布隆过滤器是一种空间效率很高的概率型数据结构，它可以判断一个元素"一定不存在"或"可能存在"。在查找某个文件之前，先检查其布隆过滤器：如果判断为一定不存在，就直接跳过该文件，无需任何磁盘读取。

布隆过滤器通常常驻内存。以每个键分配约 10 个比特计算，误判率可以控制在 1% 左右。这使得点查询在绝大多数情况下，只需要对真正包含目标键的那一个文件进行磁盘读取。

范围查询

范围查询需要返回某个键区间内的所有数据。由于数据分散在多个层级，需要为内存表和每一层分别创建迭代器，再通过多路归并的方式，按键的顺序合并输出，同一个键只保留最新版本，并跳过被墓碑标记的键。

布隆过滤器对范围查询没有帮助，因为它只能判断单个键是否存在。因此范围查询需要访问每个层级中与查询范围重叠的文件，开销比点查询大。一些实现提供了前缀布隆过滤器，对于具有共同前缀的范围查询，可以起到一定的过滤作用。

五、压缩：LSM 树的核心机制

如果只有写入没有整理，磁盘上的文件会越来越多，读取需要检查的文件随之增加，过期的旧版本和已删除的数据也会持续占用空间。

压缩（Compaction）是 LSM 树的后台整理过程：选取若干个 SSTable 文件，对其进行多路归并排序，丢弃被覆盖的旧版本和可以清除的墓碑，生成新的 SSTable 文件，然后删除旧文件。

压缩是 LSM 树设计中最关键、也最复杂的部分。不同的压缩策略，决定了存储引擎在读、写、空间三方面的性能表现。

三种放大

衡量 LSM 树性能时，通常使用三个指标：

• 写放大：实际写入磁盘的数据量与用户写入的数据量之比。由于一条数据可能在压缩过程中被多次重写，写放大可能达到数十倍；
• 读放大：完成一次查询实际读取的数据量或 I/O 次数与目标数据量之比；
• 空间放大：实际占用的存储空间与有效数据量之比，多出来的部分来自尚未清除的旧版本和墓碑。

这三者之间存在此消彼长的关系。理论研究表明，无法同时将三者都优化到最低，任何压缩策略都只能在其中进行取舍。

分层压缩

分层压缩（Leveled Compaction）是最常用的策略之一，其规则如下：

• 每一层（除 L0 外）内部的文件键范围互不重叠；
• 每一层有容量上限，且逐层按固定倍数递增；
• 当某一层超过容量上限时，从中选出一个文件，找出下一层中与其键范围重叠的所有文件，将它们一起合并，生成的新文件放入下一层。

分层压缩的特点：

• 读放大低：每层只需检查一个文件；
• 空间放大低：同一个键在每层最多只有一个版本，过期数据能够较快被清除，空间放大通常约为 1.1 倍；
• 写放大高：一个文件与下一层合并时，下一层中有大约等于层间倍数个文件参与重写。数据每下沉一层，就要被重写约十次，总的写放大可能达到数十倍。

分层压缩适合读多写少或对空间较为敏感的场景。

分级压缩

分级压缩（Tiered Compaction，也称 Size-Tiered Compaction）采用了不同的思路：

• 允许同一层内存在多个键范围重叠的文件，称为多个"段"；
• 当一层中积累了一定数量、大小相近的段时，将它们一起合并成一个更大的段，放入下一层。

分级压缩的特点：

• 写放大低：每条数据在每一层只被合并一次；
• 读放大高：同一层内有多个重叠的段，查询需要逐个检查；
• 空间放大高：同一个键可能在多个段中同时存在旧版本；合并时新旧文件同时存在，可能临时需要接近两倍的存储空间。

分级压缩适合写多读少的场景，例如日志和监控数据的写入。

混合策略

许多实际系统采用混合策略，例如在较上层使用分级压缩以降低写放大，在最底层使用分层压缩以控制空间放大和读放大。还有一些系统针对时序数据，按时间窗口组织文件，整个窗口过期后直接删除对应文件，几乎无需压缩。

压缩带来的工程问题

资源争用。 压缩需要大量的磁盘读写和 CPU 计算（排序、解压、压缩、校验）。如果压缩速度跟不上写入速度，L0 层的文件会不断堆积，读性能急剧下降。

写入停顿。 为防止上述情况恶化，存储引擎通常会在 L0 文件数量或待压缩数据量超过阈值时，主动减慢甚至暂停前台写入，等待压缩追上。这会导致写入延迟出现明显的毛刺。

限速与调度。 实践中需要对压缩的 I/O 速率进行限制，在保证压缩能够追上写入的同时，避免它占用过多资源、影响前台请求。压缩任务的优先级调度、并发度设置，都是调优的重点。

六、墓碑与删除的难题

在 LSM 树中，删除数据并不能立即释放空间，墓碑本身也需要被妥善处理。

一个墓碑只有在确认更下层不再存在被它遮盖的旧数据时，才能被安全丢弃。如果过早丢弃，下层的旧数据就会"复活"，被错误地读取出来。因此，墓碑通常只有在被合并到最底层时，才能被真正清除。

这带来了一些实际问题：

• 大量删除导致读取变慢：如果在一个范围内删除了大量键，范围查询需要扫描并跳过这些墓碑，即使返回的结果很少，耗时也可能很长；
• 空间回收滞后：被删除的数据要等到压缩到达相应层级后才能释放空间；
• 队列类场景表现不佳：先写入、再按顺序读取并删除的使用模式，会不断产生墓碑，在 LSM 树上效率较低。

一些实现提供了范围删除，用一条记录标记整个键区间被删除，避免为每个键单独写入墓碑；也有实现会优先压缩墓碑比例较高的文件，加快空间回收。

七、常见优化

围绕 LSM 树的读写放大问题，业界提出了许多优化方法。

键值分离。 当值较大时，压缩过程中反复重写值会造成严重的写放大。键值分离的思路是：LSM 树中只存储键和指向值的位置信息，值单独存放在一个只追加写入的日志文件中。这样压缩时只需要移动较小的键和指针，写放大显著降低。代价是范围查询需要额外的随机读取来获取值，并且值日志需要单独的垃圾回收机制。

块缓存与表缓存。 将频繁访问的数据块、索引块和过滤器块缓存在内存中，减少磁盘读取。将打开的 SSTable 文件句柄和元数据缓存起来，避免重复打开文件。

分区索引与过滤器。 当文件很大时，其索引块和过滤器块也会很大，全部常驻内存代价高昂。将它们进一步分区，并建立一个顶层索引，可以按需加载。

数据压缩。 对数据块使用通用压缩算法进行压缩，减少存储空间和磁盘 I/O。由于 SSTable 中的键是有序排列的，相邻键之间往往有较长的公共前缀，前缀压缩可以只存储与前一个键不同的部分，效果显著。较上层的数据访问频繁，可使用速度快的压缩算法；底层数据量大、访问较少，可使用压缩率更高的算法。

并行与子压缩。 将一次大的压缩任务按键范围拆分为多个子任务并行执行，提高压缩速度。

八、LSM 树与 B+ 树的对比

两者并没有绝对的优劣之分：

• B+ 树更适合读多写少、需要稳定低延迟、频繁进行范围查询的场景，例如传统的在线事务处理；
• LSM 树更适合写入密集、数据量大、对存储成本敏感的场景，例如日志存储、时序数据、消息系统、分布式数据库的底层存储。

随着技术发展，两者也在相互借鉴。一些 B+ 树实现引入了写缓冲和日志结构的思想来提升写入性能；一些 LSM 树实现则通过更精细的压缩策略和缓存设计，不断缩小读取性能上的差距。

九、应用与选型建议

LSM 树已被广泛应用于各类存储系统中，包括嵌入式键值存储库、分布式宽列数据库、分布式关系型数据库的存储层、时序数据库，以及搜索引擎的索引结构等。搜索引擎中不可变的索引段与后台段合并机制，本质上也遵循了与 LSM 树相同的思想。

在实际使用基于 LSM 树的存储系统时，可以关注以下几点：

根据负载选择压缩策略。 写入密集、读取较少时，优先考虑分级压缩；读取频繁、对空间敏感时，优先考虑分层压缩。

监控压缩积压。 待压缩的数据量、L0 层文件数量、写入停顿次数，是判断系统是否健康的关键指标。压缩积压往往是写入延迟升高和读取变慢的先兆。

避免大量随机删除和队列式用法。 对于需要频繁删除大量数据的场景，优先考虑按时间或按前缀组织数据，以便批量删除整个文件或整个范围。

合理配置内存。 内存表大小、块缓存大小、布隆过滤器的比特数，都直接影响读写性能。内存表越大，写入时生成的文件越大，L0 层文件越少，但崩溃恢复时需要重放的日志也越多。

预留足够的磁盘空间和 I/O 余量。 压缩过程需要临时空间，也会消耗大量磁盘带宽。磁盘接近写满或 I/O 已经饱和时，压缩可能无法正常进行，导致系统性能持续恶化。

结语

LSM 树的设计体现了一个朴素而有力的思想：既然随机写代价高昂，那就不做随机写。通过将所有写入转换为顺序追加，并把整理工作推迟到后台批量完成，LSM 树在写入性能上取得了显著优势。

但这种优势并非没有代价。读取需要跨越多个层级，压缩带来写放大和资源争用，删除操作的处理也变得复杂。LSM 树的大量工程实践，本质上都是在读放大、写放大和空间放大之间寻找适合具体场景的平衡点。

理解了这些权衡，也就能理解为什么不存在一种在所有场景下都最优的存储结构，以及为什么在选择和调优存储系统时，首先需要弄清楚的是自己的数据访问模式。