基于日志结构合并树（Log Structured Merge Tree，以下简称为LSM-tree）的键值存储被广泛应用于各类存储系统，以支持更新、点查询、范围查询等多种操作。传统的LSM-tree的合并策略将数据组织到容量呈指数级增长的多个层级中，从而实现高速写入，但是往往在层级容量的分配上不够灵活，且缺乏对读取操作的优化，在读性能上存在短板。为解决上述问题，研究者们提出了一种名为Autumn的LSM-tree键值存储系统，其核心是通过“随数据量增加动态调整相邻层级容量比例”的策略优化读取性能，较低层级会逐步扩容且合并更频繁，同时还引入了创新的Garnering合并策略，使得系统在最坏情况下的点查询和范围查询成本接近最优。本次为大家带来“全球数据库顶会”ICDE收录的的文章《Autumn: A Scalable Read Optimized LSM-tree based Key-Value Stores with Fast Point and Range Read Speed》。
一、 引入
LSM-tree是现代键值存储及大规模数据系统中存储层的常用结构。它会将所有更新操作缓冲在内存中，同时将这些更新存储到预写日志（write-ahead log，简称WAL）；当内存缓冲区达到容量上限时，便会将缓冲的所有更新以“有序运行段”的形式批量刷写到磁盘。这一过程将随机磁盘写入转化为顺序磁盘写入，大幅提升了写入性能，实现了稳定的高写入吞吐量。也正是因此，LSM-tree已成为工业界键值存储引擎的核心基础，广泛应用于HBase、RocksDB等系统。此外，基于LSM-tree的存储还常见于流处理、OLTP及HTAP等场景。
合并策略是LSM-tree组织与存储数据的核心，其既明确了数据在相邻层级间的迁移时机，也间接决定存储效率、更新与读取I/O成本的权衡关系。然而，现有研究多围绕“最小化空间放大率”、“降低写入放大率”、“优化点查询”提出新合并策略，大多忽视了读取性能的提升。同时，主流LSM-tree存储引擎常用分层合并（Leveling）和分桶合并（Tiering），在范围查询性能上非最优。
除合并策略外，现有读优化依赖缓存策略与概率性数据过滤器，存在明显不足：一是当所有运行段可能含范围查询结果时，范围过滤器无法提升性能；二是内存预算固定时，范围过滤器无法兼顾范围过滤功能与点过滤低误报率，点查询性能差于传统点过滤器，故含大量点查询的场景中难以替代传统点过滤器。
为解决上述问题，研究者们应用磁盘I/O成本模型，对范围查询、点查询、写入放大率和空间放大率的复杂度进行了全面的理论分析，重新设计了LSM-tree的数据组织方式，提出了Autumn键值存储系统。其采用全新的Garnering策略优化范围查询，在现有合并策略中实现了最优的范围查询复杂度；同时，研究者们借鉴Monkey的布隆过滤器优化思路，实现了当前最优的点查询性能。布隆过滤器的核心优势是通过大幅减少无效磁盘I/O来针对性优化读取性能，与LSM-tree“写优读弱”的特性形成互补；同时，布隆过滤器存储成本极低（通常每键仅需几比特），可嵌入SSTable元数据，几乎不增加额外负担。基准测试验证了这一新的存储系统在提升读取性能的同时，也能够维持较低的空间放大率和良好的更新性能（即优异的可扩展性）。
二、 LSM-tree预备知识
2.1 设计背景及要点
1996年O‘Neil等人提出LSM-tree，以异地更新减少数据库索引更新时的随机磁盘访问。此前异地更新虽在差分文件、Postgres项目等中应用，但会影响查询性能，且缺乏读写与空间利用率权衡的系统性成本分析。
首先给出分析LSM-tree的关键符号：
表1：分析LSM-tree的关键符号
LSM-tree提供了读写与空间利用率权衡的系统分析方法：数据物理存储于多层级，第0层在内存，其余在持久化存储，第i层容量为第i-1层的T倍，即：
Ci/Ci-1=T
在现代LSM-tree中，更新先存于内存表（常用跳表实现），存满后刷写为磁盘第1层的有序运行段（逻辑是键排序数组、物理层面由SST文件构成）；第i层数据到达最大容量则合并至第i+1层，合并时保留新值、丢弃旧值或标记删除键。
2.2 并发控制与恢复机制
存储引擎需在并发请求（读取和更新）及机器崩溃时保证数据正确性，LSM-tree通常采用多版本并发控制协议而非加锁机制来避免竞争，即在刷写或压缩操作后生成涉及文件的新版本，旧版本过期文件可通过垃圾回收机制清理，查询通过最新版本文件集合返回一致结果。
而为了保障机器故障时的数据持久性，LSM-tree将所有更新先缓存于内存，同时借助预写日志（WAL）记录；另有元数据日志存储树结构状态。在恢复阶段，键值存储会重做事务日志中已提交的事务，并通过元数据日志恢复磁盘文件。
2.3 放大率
2.3.1 写入放大率
写入放大率用来衡量将数据条目写入LSM-tree时的平均磁盘写入次数。因数据需在多层级间合并迁移，会被多次写入存储，这会缩短SSD的寿命。现有的降低写入放大率的机制包括键值分离存储、引入NVM层等。同时，为避免大层级长时间合并导致写入停滞，LevelDB、RocksDB采用部分合并（迁移单个2~64MB的SST文件），但可能影响最坏情况更新I/O成本；而Cassandra、HBase默认用完全合并（一次性合并相邻层级完整运行段）。研究者讨论的合并操作复杂度均以运行段为粒度。
2.3.2 点查询放大率
点查询需遍历LSM-tree的所有层级，找到数据的最新版本（找到匹配键即终止）。这一过程常用内存中的布隆过滤器提速——该过滤器无假阴性、假阳性率可调整，能减少无需访问的磁盘运行段，其中假阳性率计算公式：
2.3.3 范围查询放大率
范围查询需遍历LSM-tree所有层级，收集各有序运行段的最新条目，确保不遗漏目标键范围内数据，与点查询找到键即终止不同。这一过程常用内存中存储边界指针来提速，即记录每个运行段各数据块的首个键，通过1次磁盘I/O即可定位相关键范围，减少迭代器查找耗时。
2.3.4 空间放大率
LSM-tree因异地更新，过期数据条目会留存在磁盘中，导致物理存储大于逻辑数据规模，而空间放大率即为二者比值。在传统场景中由于存储成本低，该指标未受重视；但在云原生数据库时代，其会增加运营成本。所以这也是研究者要控制的指标。
2.4 合并策略
2.4.1 分层合并与分桶合并
二者均采用相邻层级容量差为恒定系数T（T>1）的指数级增长设计；且层级总数：
由内存表大小B、数据规模N及系数T决定，最后一层存储大部分数据。
它们的区别可以总结如下：分层合并每层级最多1个有序运行段，新运行段触发合并，写入放大率O(T*L)，范围查询成本O(L)次磁盘I/O，减少了运行段总数，更偏向读优化；分桶合并每层级最多T个有序运行段，满后合并至下一层，写入放大率O(L)，范围查询成本O(T*L)次磁盘I/O，降低了更新成本，更偏向写优化。
另外，二者在经过布隆过滤器优化后的点查询最坏成本分别为和，仅取决于过滤器内存预算。
2.4.2 其他合并策略
Lazy-Leveling策略结合分层与分桶合并思路，仅最后一层为1个有序运行段，性能介于分层与分桶合并之间。QLSM Bush策略通过低层双指数增长运行段数量实现最优写入放大率，但牺牲了范围查询性能。而研究者提出的Autumn引入的Garnering合并策略，在层级间加了额外缩放因子，在有无布隆过滤器时均匹配最优点查询成本，同时实现最优范围查询最坏性能，且保持可扩展的空间与写入放大率。
图1：现有策略与Garnering策略在最大三个层级中的结构示意图
表2：现有策略与Garnering策略的复杂度分析
三、 Autumn存储模型
3.1 关于新设计的一些要点
3.1.1 Garnering策略的高层设计
不同于传统合并策略，Garnering策略通过仅将最后一层与第L-1层的容量比固定为T，并引入小于1的缩放因子c来增大低层间的容量比，即：
Ci/Ci-1=T/cL-i
由此可得出，容量层级比随层级i的减小而增大，并且第i层的容量即为：
Ci=Ti/c(2L-1-i)i/2*B
本质上，随着数据存储量增加相邻层级间的容量比会动态变化，而由于之前已提到当第i层存储的数据达到容量上限时，该层级的文件会合并至第i+1层，因此Garnering策略通过这样的方式实现了LSM-Tree结构的扁平化，相比传统数据组织方式，Autumn中低层的容量会更大。
3.1.2 延迟最后一层压缩
上一点提到，在Garnering策略中，低层容量会随数据存储量增加逐步增大，当Autumn的第L层（当前最后一层）数据量达到容量上限时，系统新建第L+1层作为新最后一层；此时原第L层的容量会基于新总层级数（L+1）重新计算，且新容量严格大于原第L层当前数据量，因此无需压缩原第L层，仅将其压缩操作延迟至下一周期，避免大层级压缩占用过多I/O资源。
3.1.3 空间放大率
由于 Garnering 策略中每个层级仅包含一个有序运行段，所以假设所有层级均存储满数据，在最坏情况下，第1层至第L-1层存储的所有条目均为第L层现有数据条目的更新版本。又因为第1层至第L-1层的总数据量由第L-1层的容量主导，且最后一层容量为第L-1层的T倍，因此最坏情况下第L层中约有1/T的条目为过期数据，空间放大率约为1+1/T。
3.1.4 层级数量
由以上公式可知，最后一层的容量约为：
TL/c(L(L-1)/2)*B
而最后一层的数据量约为：
N*(T-1)/T
通过求解上述两个公式联立的等式即可得出使用Garnering策略的层级数量：
3.1.5 点查询
因为在LSM-tree中，点查询的最坏情况成本需遍历所有层级。所以由层级数量可知，Autumn可以将点查询性能提升至复杂度。
3.1.6 布隆过滤器优化
无匹配键的点查询中，无效探测次数等于所有布隆过滤器FPR的总和。Garnering策略中每个层级仅含一个有序运行段，点查询成本：
而总过滤器内存为各层级过滤器内存之和：
由此，最优过滤器内存分配可转化为优化问题：在总内存预算固定的前提下，最小化点查询成本即可。通过拉格朗日乘数法可得出各层级最优假阳性率关系：
则各层级最优假阳性率：
又因为在过滤器内存预算固定的情况下，随着数据量增长，假阳性率会升高并最终趋近于1。因此，分析“每数据条目比特数”很重要。将最优分配代入公式，并取求和项中的主导项，可得出每数据条目比特数的近似表达式：
在每数据条目1.52比特时函数取得最大值。而工业界中，主流LSM-tree键值存储通常为每个数据条目分配10比特，以确保假阳性率低于1。相比较而言，Garnering策略的布隆过滤器优化可显著加快点查询速度。
3.1.7 CPU优化
每个运行段均关联一个存储在内存（DRAM）中的布隆过滤器，以减少磁盘I/O。研究者并未设计新的过滤器降低CPU开销，而是通过减少内存中布隆过滤器的数量直接降低CPU开销。因此，尽管Garnering与分层合并策略的点查询最坏情况磁盘I/O复杂度相同，但Garnering的CPU开销更低。
3.1.8 范围查询
Autumn也致力于范围查询的优化，在短范围查询（目标键范围内的数据条目平均仅存储在每个运行段的一个数据块中）中，由于Garnering策略的层级数量少于传统策略，查询复杂度降至；而在长范围查询（目标键范围内的数据条目平均存储在每个运行段的多个数据块中）中，Garnering策略减少了“查找I/O”的次数，从而也优化了性能。
3.1.9 写入放大率
由于第L层的数据条目平均需压缩T次，第L-i层的数据条目平均需压缩T/ci次，因此，第1层的合并操作主导写入放大率，每个数据条目的总压缩次数约为：
深入分析复杂度边界可发现，其实际为相对于数据规模N的亚线性复杂度。这是因为对于任意常数c（0<c<1），1/c可表示为某个常数k，因此：
T/ci=T*ki
由于这些复杂度均以k为底，所以只需比较指数部分。显然Garnering策略的指数小于传统分层合并策略的指数，因此写入放大率复杂度为亚线性且低于任何固定次数的多项式复杂度，说明了Autumn在更新操作方面具有可扩展性。
3.1.10 Autumn对低层压缩的隐式优先级
因为Autumn中，数据量增多和层级扩展会使各层级容量增大且高层级增长更快，导致低层压缩更频繁、高层级压缩更少；虽可能略微升高写入放大率，但能提升整体写入吞吐量。同时，LSM-tree需靠速率限制器避免未刷写文件过多导致数据丢失，而优先处理低层刷写可提升写入吞吐量。Autumn让低层承担更多压缩操作，从而减少写入停滞、提升写入吞吐量。
3.2 性能的进一步优化
Autumn 可以通过让第0层保留固定数量有序运行段且不触发内部压缩，避免该层高频压缩带来的高写入成本，从而降低总写入放大率；同时可借助RocksDB等引擎的块缓存固定第0层元数据，提升读取速度且不影响缓存分配。此外，虽未与“将低层存于NVM”的特殊硬件方案对比，但Autumn低层压缩更密集的特性，在NVM场景下仍有望提升性能。
四、 实验与评估
4.1 实现细节
研究者基于RocksDB构建了Autumn，并修改了MaxByteForLevel函数来存储max_level_in_use_变量，并在每个文件上附加层级信息以便计算层级容量。此外，为充分观察层级间容量比变化的效果，研究者还禁用了查找合并优化。研究者也基于LevelDB构建了Autumn，这主要是为了主要是为了与Monkey进行公平的点查询性能对比。
4.2 微基准测试
4.2.1 测试准备
为对比Autumn与RocksDB的性能，研究者首先使用默认基准测试工具db_bench在AWS i3en.large EC2实例上开展小规模微基准测试，并禁用了数据压缩和布隆过滤器，以便更清晰地分析性能表现。在配置上，存储引擎被设置为OptimizeForSmallDb配置，该配置将目标文件大小设为2MB，最大基础容量设为10MB。
微基准测试共包含以下6种操作：
FillSeq：按顺序写入数据条目。
FillRandom：随机写入数据条目。
ReadRandom：执行随机点查询。
SeekRandom：执行随机查找操作。
SeekRandomNext10：执行随机短范围查询。
SeekRandomNext100：执行随机长范围查询。
4.2.2 不同键值大小下的操作性能
在采用默认策略参数T=2的情况下，研究者参考Facebook生产系统中不同数据负载的平均大小，将键值大小分别设置为50字节、100字节和200字节。
对于写入性能，研究者通过FillSeq和FillRandom两个操作衡量，并以单次操作平均延迟为指标，延迟越低表示性能越好。由图2（a）的结果得出，在不同值大小和写入模式下，Autumn与RocksDB的写入延迟相近。
对于点查询性能，研究者通过ReadRandom操作衡量，同样以单次操作平均延迟为指标，结果如图2（b）所示，在所有值大小下，Autumn的点查询性能均优于RocksDB。
对于范围查询性能，研究者通过Seek、SeekAndNext10和SeekAndNext100三个操作衡量，仍采取相同指标。由图2（c）的结果可知，在所有值大小和三种操作中，Autumn的性能均优于RocksDB。三种操作的性能提升分别约为19%、9%和5%。
图2：RocksDB与Autumn在微基准测试六种不同操作下的评估结果（c=0.8）
4.2.3 写入与读取性能对参数c和T的敏感性
因为Garnering策略包含两个关键参数c和T，于是，研究者固定了其中一个参数，调整另一个参数，通过FillRandom操作写入2GB键值对，分析其对随机写入和短范围查询性能的影响。实验结果如图3所示。总体而言，当T固定时，c越小，读取性能越好，但写入性能越差。此外，T增大也会减少层级数量，从而进一步优化短范围查询性能。
图3：c和T对随机写入短范围查询的影响
4.3 宏基准测试
4.3.1 测试准备
研究者还使用了YCSB基准测试工具，使用了与微基准测试相同的AWS EC2实例环境在大规模数据场景下对比Autumn与RocksDB的性能，以模拟真实工作负载。
同样的，为更好分析性能，实验采用YCSB默认配置和工作负载，设置T=5，禁用数据压缩和块缓存，并为Autumn设置c=0.8和c=0.4两个参数。
4.3.2 核心工作负载A-F
研究者写入80GB数据集，并执行A（更新密集型）、B（读多写少型）、C（纯读型）、D（读最新型）、E（范围查询型）、F（读-改-写型）六种工作负载测试。结果表明，Autumn在所有YCSB默认工作负载中，性能均与RocksDB持平或更优。这主要得益于Autumn在写入吞吐量上的提升和更高的键命中概率。
图4：Autumn与RocksDB在各类YCSB核心工作负载下的性能对比
4.3.2 平均延迟与尾部延迟
点查询和范围查询的平均延迟与尾部延迟是衡量系统对用户服务质量的关键指标。实验表明，在工作负载A、C、E下，RocksDB的99%分位延迟分别是Autumn的1.2 倍、1.3倍和1.1倍。这些延迟改进能有效提升用户体验质量。
表3：三种工作负载下的平均延迟与尾部延迟
4.4 布隆过滤器优化
研究者将基于LevelDB分支的Autumn与其原生版本进行对比。与之前的基准测试流程一致，二者分别创建四个数据库实例，通过FillRandom操作分别写入不同大小的数据集，然后收集写入操作、未启用布隆过滤器的点查询、启用布隆过滤器的点查询以及短范围查询的平均延迟。图5的结果表明，无论是否启用布隆过滤器，Autumn的性能均优于LevelDB。
图5：不同数据库大小与不同操作下的LevelDB db_bench宏基准测试性能
五、 总结
新的键值存储系统Autumn通过采用创新性的Garnering合并策略，以及重新定义LSM-tree内部的数据组织方式，提升了点查询与范围查询的最坏情况复杂度。此外，延迟合并机制的引入，以及Garnering策略对小层级合并的优先级设定也显著提升了Autumn的读写性能效率。研究者使用db_bench和YCSB基准测试工具，将Autumn与LevelDB、RocksDB进行了全面的性能对比评估。结果表明，Autumn不仅优化了读取操作，还保持了稳定的写入性能，非常适用于OLTP和HTAP工作负载。
 |
图文｜沈祺昊
校稿｜鲁茹芸
编辑｜刘苧锐
审核｜李瑞远
审核｜杨广超
