日志结构合并树通常简称为 LSM 树,是一种数据结构,用于在频繁插入、更新和删除的情况下维护键及其关联值的有序集合。它不会立即修改每条记录的最终存储位置,而是先在内存中积累变更,再将其批量写入存储设备,并逐步合并由此产生的有序组件。这种组织方式将大量可能涉及随机访问的小规模写入转换为较大规模的数据传输,并将维护工作分摊到多次更新中。
LSM 树广泛应用于数据库管理系统、持久化键值存储和分布式存储服务。其核心权衡在于,低开销的前台写入会留下延后处理的工作:读取时可能需要查询多个组件,而后台合并则会反复重写数据。因此,性能不仅取决于树的逻辑组织方式,还取决于合并策略、内存分配、持久性要求、工作负载和存储硬件。
这一术语指的是一组相互关联的设计,而非某种标准化的文件格式或算法。最初的方案采用一棵驻留内存的小型树和规模更大的驻留磁盘组件;许多现代实现则改用可变的内存缓冲区,以及按层级或大小分组组织的不可变有序文件。
起源与设计思路
LSM树由帕特里克·奥尼尔、爱德华·程、迪特尔·加夫利克和伊丽莎白·奥尼尔在1996年发表于《Acta Informatica》的论文《日志结构合并树(LSM树)》中提出。其出发点是在记录高速插入的情况下,如何降低维护数据库索引的成本。在磁盘上,即使一条记录实际只占磁盘块的一小部分,一次小规模更新仍可能需要机械寻道并等待盘片旋转。先积累大量变更,再将其传输到磁盘,可以摊薄这些成本。
最初的方案描述了一个常驻内存的组件,通常称为 ,以及一个更大的常驻磁盘的组件 ,并可扩展为包含更多组件的结构。条目通过滚动合并逐步迁移,而不是逐一写入其最终的磁盘位置。关键并不在于每次更新在任何情况下都能避免随机访问,而在于索引维护中的大量工作可以通过有序的批量处理来完成。摊还分析明确揭示了这一区别:一次插入可能触发大量工作,但在多次插入中,平均成本仍然较低。
其主要比较对象是B树,后者会随着记录的变化而更新相应的页面。B树提供较为直接的查找路径,而且通常为每个索引条目保留一个表示其当前状态的逻辑位置。LSM树则允许近期变更与较早的表示形式在不同组件中共存,随后再进行整合。这两种组织方式都不具有普遍优势。缓冲池可以有效地合并B树更新,而LSM树可能会消耗大量带宽,反复重写同一批仍需保留的数据。
“日志结构”指的是先积累变更,再以大批量传输的方式处理这些变更的策略。这并不意味着LSM树只是一个仅追加日志,也不意味着它与日志结构文件系统具有相同的组织方式。有序性仍是其基础:它支持高效合并、文件内的单点查找以及有序遍历。实践中通常还会使用独立的恢复日志,但恢复日志本身并不是这个有序索引。
随着大型存储系统需要在多台机器上持续接收并写入数据,这一设计的影响力日益扩大。谷歌在2006年对Bigtable的介绍中,记载了一种采用内存缓冲区、有序持久化表和压实操作的架构。后来的开源实现将类似机制以嵌入式存储引擎的形式提供出来。这些发展拓宽了“LSM树”一词的含义,使其涵盖了许多实际设计;这些设计在文件组织、合并调度和并发机制方面,与最初的滚动合并方案存在显著差异。
写入缓冲与持久化布局
典型的现代 LSM 写入流程会先将数据写入预写日志,以及一个称为 内存表的内存有序缓冲区。日志为尚未写入持久化有序文件的变更提供可供恢复的记录;内存表则支持对这些变更的高效访问。具体何时确认写入成功,取决于系统承诺的持久性保证。写入操作系统缓冲区并不等同于强制将日志写入持久化存储,而有些应用会明确选择较弱的持久性保证,以换取更高的吞吐量。
内存表通常采用跳表、平衡搜索树,或其他支持更新和有序遍历的数据结构。更新操作一般会插入一条新的内部记录,其中包含用户键、版本或序列标识符、操作类型,以及适用时的值。删除操作通常以删除标记表示,而不是立即查找所有旧副本。因此,内存中的数据表示可能包含同一用户键的多个版本。
当内存表达到大小阈值时,引擎通常会将其设为不可变,并创建一个新的可变内存表。后台刷写操作会将不可变内存表的内容写入一个或多个有序字符串表文件,这类文件常称为 SSTable。这样的分离使系统能够在持久化前一个缓冲区的同时,继续接收新的写入。如果刷写速度跟不上写入速度,不可变缓冲区就会不断积压;引擎会限制其数量或总内存占用,并最终降低前台写入速度或暂停前台写入。
SSTable 通常是一个按内部比较器排序的不可变记录序列。其物理布局往往包含数据块、索引块、过滤器信息、校验和,以及标明重要偏移量的文件尾部。块级数据压缩十分常见,因为读取时只需解压所需的块。索引将键范围映射到数据块,而文件中的最小键和最大键则使引擎无需读取文件内容,就能排除无关文件。“SSTable”的确切含义和编码方式因系统而异。
数据库的当前有效状态不只是其数据文件的集合。持久化的元数据记录了哪些文件属于数据库的当前版本、这些文件所在的层级及其键范围,以及相关的恢复日志状态。新文件可以先创建而暂不可见,随后通过元数据变更纳入当前版本。旧文件则会一直保留,直到使用早期版本的读取操作不再需要它们。因此,不可变性虽然简化了共享,但安全地发布新文件和回收旧文件仍是存储引擎不可或缺的工作。
点查询、过滤器与有序扫描
点查询必须确定某个键的哪些可见记录具有最终效力。通常,它会搜索可变内存表、所有不可变内存表,以及相关的持久化组件。在不提供版本语义的接口中,以最新的适用值为准;如果最新记录是删除标记,就表示该键不存在。在快照读取中,“最新”则指快照可见性规则允许的最新版本。通过安排搜索顺序并利用文件元数据,通常可以跳过那些不可能包含更相关结果的组件。
持久化文件通常配有布隆过滤器。这是一种紧凑的概率型数据结构,无须加载数据块就能排除某个键存在的可能性。只要针对查询所用的键表示形式正确构建,传统布隆过滤器就不会出现假阴性,但可能将不存在的键报告为可能存在。如果它用 位表示 个不同的键,并为每个键通过哈希确定 个位位置,则其假阳性概率近似为
这一近似假定使用了合适的哈希方法,并采用通常的独立性模型。近似最优值为 ;在每个键分配十位的情况下,参数配置合理的过滤器,其假阳性率约为百分之一。
过滤器对未命中的点查询尤其有用,否则可能需要检查许多文件才能确定键不存在。过滤器不会给出存储的值,也不会选出最新版本;即使某个文件通过了过滤器检查,仍然需要使用该文件内部的索引。过滤器还会消耗内存或存储带宽。存储引擎可以按文件或数据块粒度进行过滤,也可以对过滤器分区,或为不同层级分配不同大小的过滤器。如果获取过滤器本身代价高昂,那么它实际节省的资源可能比其标称假阳性率所暗示的更少。
有序范围扫描的访问模式则不同。每个相关组件都提供一个定位在范围下界附近的迭代器,存储引擎再按键的顺序合并这些数据流。优先队列是选择下一条候选记录的常用机制之一。对于每个用户键,扫描必须先排除被遮蔽的版本,并遵循删除标记的语义,然后才能返回可见值。归并排序技术可以高效地完成这种合并,但相互重叠的组件仍会增加迭代器状态、比较次数、数据块读取量和解压缩开销。
缓存进一步将逻辑搜索工作与物理设备访问区分开来。文件索引、过滤器和数据块可能已经位于存储引擎管理的数据块缓存或操作系统的页缓存中。因此,一次查询即使检查了多个组件,也不一定会发起同等次数的存储读取。反过来,对大型工作集进行扫描也可能挤出缓存中有用的数据块。有意义的性能描述应区分候选文件、过滤器探测、缓存未命中、物理读取和返回记录,而不是将它们统统视为一种“读取成本”。
合并策略及其影响
合并会合并有序组件,在条件允许时消除冗余记录,并生成替代原有组件的新组件。其算法核心是有序归并,但具体策略决定了哪些文件参与合并、何时执行,以及合并后还保留多少重叠。合并并非可有可无的维护工作:如果不进行合并,持续更新的 LSM 树就会不断积累文件、过期版本和删除标记,直至查询和存储成本变得难以接受。不过,合并可以延后,也可以调整其组织方式,而不同策略在各方面的取舍有着显著差异。
**分层合并(Leveled compaction)**将大部分持久化数据组织到多个层级中,各层的目标容量按几何级数增长。在普通的非零层级内,各文件覆盖的用户键范围通常互不重叠,因此,单点查询在该层至多只需检查一个候选文件,具体仍取决于实现细节。接收新刷盘数据的层级通常称为第 0 层,一般允许文件之间存在重叠。为将数据向下层移动,存储引擎会选取源文件,将其与下一层中键范围重叠的文件进行合并。这限制了读取时需要考虑的持久化有序段数量,但也可能反复重写已有数据。
**分级合并(Tiered compaction)**保留多个大小相近的有序段,并在数量或大小达到阈值时将它们合并。由于新写入的数据不必立即在每个大小尺度上归并为单个有序段,一条记录经历的重写次数可能更少。代价是查询时需要搜索更多相互重叠的有序段,而且通常需要更多临时空间,或占用更多空间来保存过期数据。“按大小分级”“通用合并”等相关名称指的是特定实现,而不是完全可以互换的算法;它们的触发规则和文件分组方式可能不同。
一个简单的例子可以说明两者的区别。假设新生成的四个有序段覆盖了相同的较大键范围。分级策略可以先保留这四个有序段,等到适合将它们一起合并时再处理。分层策略则可能更早地将每批数据并入已有的下层数据,从而减少读取时的候选文件数量,但会多次重写部分旧记录。如果相同的热点键被反复覆盖,延迟合并可能一次性丢弃多个中间版本。如果读取操作经常扫描这些范围,那么较早整合数据反而可能更有利。
合并任务还可以根据时间窗口、键范围、删除密度或工作负载特有的优先级来选择。对于数据过期规律和访问模式与事件时间密切相关的数据,按时间窗口分组很有用,但乱序写入会使设计变得复杂。输出文件通常会被拆分,使每个文件的大小不超过设定上限,以便后续维护能够针对较小的键范围进行。当各项合并的输入和输出范围满足存储引擎的安全规则时,就可以并行执行。调度必须在当前读取需求与长期维护之间取得平衡,因为即使某种策略的总工作量较低,也仍可能出现影响正常运行的突发负载。
放大效应与解析成本模型
LSM 的性能通常通过写放大、读放大和空间放大来描述。写放大比较存储引擎写入的字节数与应用逻辑更新的字节数。读放大描述回答查询所需的额外工作量,但必须明确其计量单位:候选有序段数、块读取次数、传输字节数,或检查的记录数。空间放大比较实际存储占用与某个明确定义的逻辑基准,例如当前有效记录的大小。对于同一个数据库,不同的定义可能得出不同的数值结果。
设 为持久化数据量, 为以相同单位计量的有效内存缓冲区容量, 为相邻层之间的目标大小比。当 时,理想化的几何级数布局大约具有
个持久化存储规模层级。这一估算忽略了未填满的层、元数据、多个内存缓冲区、压缩以及预留容量。它有助于分析规模变化的影响,但不能用于预测确切的文件数量或延迟。
在常见的简化模型中,分层策略(tiering)允许每个规模层级存在 数量级的有序段,因此,不使用过滤器的单点查询大约需要考虑 个候选有序段,而每条保留下来的记录会被重写约 次。分级策略(leveling)可将候选有序段数量降至 左右,但与更大层的数据重叠可能使写入工作量达到 数量级。这些只是基于数据均匀性、合并选择和填充率等特定假设得出的大致趋势,并非适用于所有实现或工作负载的普遍界限。过滤器和缓存可以在不改变底层有序段数量的情况下,大幅降低物理读取成本。
衡量放大效应时,分母的定义至关重要。如果应用反复修改一个长键对应的小值,那么逻辑字节数是否包含键、操作元数据和事务日志,会使计算出的比率有所不同。引擎层面的写放大可能不计入恢复日志,而设备层面的放大则包含存储设备内部的额外重写。同样,具有长期存续快照的数据库可能会有意保留旧版本;将这些版本占用的存储空间称为“已失效空间”,会曲解其语义。
可用的维护带宽会对实际吞吐量构成约束。如果引擎每摄取一个逻辑字节,就必须写入约 个存储字节,而其可用的持续写入带宽为每秒 字节,那么仅就这一约束而言,稳态摄取速率就不能超过约 。压实还需要读取数据并消耗处理器时间,因此这并不是完整的吞吐量模型。短时间基准测试可能通过积累待处理工作,达到高于可持续速率的表现,因此,压实积欠和最终存储状态都是任何性能测量中不可忽视的部分。
恢复、快照与删除安全性
LSM 树采用延迟写入,因此需要一套恢复协议,将日志、内存状态和持久化文件集合衔接起来。常见的流程是:先将更新写入恢复日志,再应用到内存表,将内存表刷写为新的有序文件,在数据库元数据中持久化登记这些文件,最后才淘汰不再需要的日志段。恢复时,系统会重建当前文件集合,并重放必要的日志记录。校验和与记录分帧有助于识别不完整或已损坏的日志记录,但正确处理各项操作的持久化顺序仍然至关重要。
合并压缩采用类似的发布协议。系统先写入替代文件,再通过一次元数据操作,用新的输出文件替换旧的输入文件。如果在发布前崩溃,可能会留下未使用的输出文件;如果在发布后崩溃,则可能会留下尚待删除的旧文件。无论哪种情况,持久化元数据都必须指向一个一致的逻辑状态。文件创建、重命名、元数据日志记录以及同步所能提供的保证,都取决于底层平台。文件不可变,并不意味着可以不再仔细分析这些操作之间发生故障的情形。
许多 LSM 引擎采用多版本并发控制,或类似的基于序列号的可见性机制。内部键可以由用户键、序列号和记录类型组合而成,使多个历史版本能够按序共存。快照会固定一个可见性边界,从而使后续写入不会改变其查询结果。只有在所有相关快照和其他保留规则都不再需要某个已被取代的版本时,合并压缩才能将其丢弃。因此,长期存在的快照可能增加磁盘占用,并减少合并压缩能够回收的数据量。
删除标记通常称为墓碑,用于防止旧值重新出现。仅仅因为墓碑所在的文件已完成合并压缩,就将墓碑移除,是不安全的:旧值可能仍存在于其他组件中。要安全地移除墓碑,必须证明在此次合并压缩覆盖范围之外,不可能残留任何相关的旧版本,而且没有快照需要被删除的历史数据。范围墓碑通过删除一个键区间引入了另一个维度;扫描和合并压缩都必须考虑相互重叠的区间及其可见性边界。
本地存储的正确性不同于数据库复制的正确性。在分布式数据库中,遗漏了某次删除操作的副本,之后可能重新引入旧值,除非修复、版本协调和删除保留规则能够防止这种情况。同样,LSM 树本身并不提供 ACID特性,也不提供涉及多个键的数据库事务。事务系统需要额外加入锁、冲突检测、事务记录和提交协议等机制。LSM 引擎提供持久化的有序存储,这些机制可以在其上构建。
存储硬件与值的存放位置
LSM 树最初的吸引力与磁盘的性能特性密切相关。顺序传输可以将寻道和旋转延迟分摊到大量记录上,而互不相关的小规模更新则可能主要耗时于磁头定位。批量合并正是利用了这种差异。不过,“顺序”并不是整个引擎固有的绝对属性:并发的刷盘、压实、日志写入和前台读取可能在设备上交错进行。文件碎片和调度方式会影响逻辑上有序的操作能否转化为高效的物理数据传输。
固态硬盘改变了这些权衡,但并未将其消除。闪存支持相对快速的随机读取,但写入和擦除受到页和擦除块的约束。闪存转换层会重新映射逻辑地址,并执行自身的垃圾回收。因此,反复进行的 LSM 压实可能与设备内部的重写叠加,增加物理写入量。引擎的写放大与设备内部的写放大是两个独立的量;二者都会影响带宽消耗和设备寿命。
随着存储速度提高,处理器和内存方面的开销日益突出。键比较、过滤器哈希计算、块解压缩、迭代器维护和数据复制,都可能成为延迟的主要来源,或占用大量中央处理器资源。较大的值会增加压实过程中的数据搬移量,而较长的公共键前缀则会提高前缀压缩的效果。如何在内存表、过滤器、索引和数据缓存之间分配内存也很重要:增大写缓冲区可能降低刷盘频率,却会压缩用于缓存高频读取数据块的空间。
应对大值工作负载的一种方法是键值分离。有序结构存储键和引用,而值则存放在单独的日志或存储区域中。2016 年提出的 WiscKey 是一个有代表性的研究实例。由于压实搬移的是相对较小的索引项,而非完整的值,这种设计可以减少重写。不过,它也引入了值日志垃圾回收、引用管理和额外的间接访问。范围扫描可能失去相邻键值共同存放时所具有的物理局部性。
分离式存储和对象存储带来了更多约束。不可变的有序文件很适合作为对象进行上传、共享、缓存,并通过元数据引用,但请求延迟、传输粒度和网络成本可能使小规模随机读取代价高昂。预取、本地缓存、更大的读取单元,以及独立的压实工作进程,都是可能的应对方式。针对特定设备的设计还可以利用数据放置控制功能或顺序写入分区。这些适配保留了缓冲与合并这一核心原则,同时改变了数据搬移发生的位置,以及限制性能的资源类型。
主要实现与数据库集成
Google 于 2006 年介绍的 Bigtable,是在分布式数据服务中采用 LSM 风格存储的一个颇具影响力的实例。其公开设计使用提交日志、内存中的 memtable 和不可变的 SSTable,通过压实合并已存储的数据,并清除符合清理条件的已删除信息。该系统将有序的行空间划分为多个 tablet。这体现了一项重要的分层:类 LSM 结构负责管理本地持久化数据的组织形式,而 tablet 分配、故障处理和分布式协调则由另一层负责。
Google 于 2011 年以开源软件形式发布的 LevelDB,是一个嵌入式有序键值存储库,采用 memtable、日志、SSTable 和分层压实。它的接口精简,使这种架构更容易应用于大型分布式服务以外的场景。它在应用进程内部提供存储功能,而不是充当完整的分布式数据库服务器。使用此类库的应用仍须自行决定如何实现网络通信、授权、超出库自身能力的事务语义,以及运维管理。
Facebook 基于 LevelDB 开发、于 2013 年发布的 RocksDB 延续并扩展了这一技术路线,尤其注重生产环境中的存储工作负载和高速设备。它提供多种压实方式、可配置的内存结构和缓存、列族,以及控制后台任务的机制。列族在数据库内部提供可单独配置的逻辑键空间,同时也可以共享预写日志等资源。这些特性使 LSM 引擎的实际性能高度依赖具体配置,而非仅由其采用的数据结构决定。
Apache Cassandra 和 Apache HBase 都在分布式数据库架构中采用 LSM 风格的存储,但两者的数据模型、一致性机制和运行设计各不相同。Cassandra 结合使用提交日志、memtable、SSTable 和可配置的压实策略。HBase 属于 Hadoop 生态系统,采用预写日志、memstore 和持久化的 HFile。不能仅凭这些本地存储方面的相似之处推断它们的分布式行为:分区、修复、副本协调和故障恢复都是独立的设计选择。
LSM 存储并不限于以 NoSQL数据库名义推广的系统。关系数据库可以将主记录和二级索引存放在基于 LSM 的引擎中,分布式 SQL 系统也可以在事务性键值层之下使用这样的引擎。关系模型和 SQL结构化查询语言规定的是数据的逻辑组织与访问方式,并不强制要求采用某种物理索引格式。二级索引可能使写入工作量成倍增加,因为一次逻辑行变更可能产生多个独立存储的键更新。事务处理和查询执行都必须将这种物理层面的成本纳入考虑。
运行特性与持续研究
运行中的一个关键问题是压缩债务:为维持预期的存储组织方式,最终必须完成但尚未执行的维护工作。如果写入流量超过刷盘和压缩所能处理的速率,上层文件和不可变内存缓冲区就会不断积累。存储引擎通常会通过降低写入速度或暂停写入来应对。这些机制能够将内存占用控制在限额内,并保障读取性能,但也会让延后执行的维护工作转化为前台操作的延迟。因此,要维持持续吞吐量,就必须在数据写入与后台处理能力之间取得平衡,而不能仅仅加快初始写入路径。
工作负载的分布会显著影响这种平衡。向新的键范围顺序插入数据,与均匀随机更新数据,可能产生不同的数据重叠模式。一个较小的热点数据集可能产生大量过时版本,而这些版本可以一并清除;但长期保留的快照会阻止此类清除。大批量操作可以摊薄日志记录和同步的开销,但也可能造成内存需求和压缩工作的突发增长。生存时间到期后,记录在逻辑上已不可见,但其占用的存储空间不一定已被回收;如果记录的分组方式合适,有时可以直接回收整个文件,而无须重写其内容。
压缩调度是一个多目标问题。存储引擎可能优先处理对读取延迟影响最大的文件、接近容量上限的数据,或包含大量过时记录的键范围。增加后台并发度可以提高设备利用率,但并发度过高时,就会与前台读取激烈争夺带宽、处理器时间或缓存容量。速率限制和资源隔离旨在控制这些相互影响。仅看平均操作吞吐量,可能会掩盖严重的高百分位延迟问题,因此评估通常还需要考察延迟分布、工作负载的持续时间、缓存状况,以及尚未完成的维护工作量。
已有研究探索了对合并策略和过滤器内存分配进行联合优化,而不是分别调优。2017 年提出的 Monkey 表明,应根据各层对查找成本的贡献来分配布隆过滤器内存,而不是在所有层中都为每个键分配相同的位数,这一点十分重要。2018 年提出的 Dostoevsky 探索了惰性分层策略,以及传统分级策略与分层策略之间更广阔的设计空间。这些方法说明,读写之间的权衡取决于整体配置,包括内存预算,以及查找、扫描和更新操作的相对频率。
其他研究方向包括减少值数据的搬移、并行执行压缩、改进范围删除的处理、采用更新的过滤器结构,以及实现存算分离。自动调优十分困难,因为最佳配置可能随键分布、值大小、设备特性和数据保留要求而变化。评估还必须区分两种情况:数据库是暂时利用富余容量吸收写入,还是已经进入稳态。尤其对于删除密集型或覆盖写入密集型工作负载,必须报告最终的有效数据量、实际占用的存储空间,以及剩余的压缩工作量,才能正确解读看似很高的数据写入速率。