基于日志结构合并树(LSM-tree)的键值存储(KVS)在存储系统中因为其优异的写性能得到了广泛应用。尽管如此，LSM-tree 内部合并过程导致的高写入放大也提出了新的挑战。而 KV 分离的 LSM-tree 成功地减小了写放大，但也带来了严峻的空间放大问题，这在成本敏感的场景中不容忽视。虽然垃圾回收(GC)操作能够减小空间放大，但是现有的 GC 策略仍然存在不足，缺乏对工作负载特征的全面考虑。此外，目前 KV 分离的 LSM-tree 也忽略了索引 LSM-tree 中空间放大带来的不利影响，难以实现性能和存储空间的平衡。

实验室博士生张健顺，在王芳教授的指导下，针对以上问题，提出了一种新的基于 KV 分离的键值存储系统 Scavenger。Scavenger 对 KV 分离的 LSM-tree 系统的空间放大来源进行了系统的建模和量化分析，确定了空间放大的两个主要来源：低效的 GC 和延迟的 Compaction。针对两个关键操作分别提出了新的设计：对于 GC 操作而言，Scavenger 识别出了 GC 在不同负载下的性能瓶颈，为索引数据和值数据分别设计了新的表结构 DTable 和 RTable 来改善 GC-Lookup 和 GC-Read 操作；同时还提出了一种轻量级的热点感知的写入策略来提升 GC 执行效率；对于 Compaction 操作而言，Scavenger 提出了基于补偿大小的 Compaction 策略来让索引 LSM-tree 重新获得感知空间的能力，及时地触发 Compaction 从而提升系统整体的垃圾率，以改善 GC 执行效率。此外，Scavenger 还提出了空间感知的限流策略，基于实际生产环境中有限的存储空间配额，在达到空间配额限制以后限流前台写入，从而确保服务的可用性。Scavenger 有限的存储空间配额下实现了更好的前台性能，在不限制空间的场景中显著减小了空间放大，从而实现了性能和存储空间之间更好的平衡。

图 1：Scavenger 架构图

图 2：限制空间 1.5x 下的 YCSB 前台性能吞吐

图 3：不限制空间下的 YCSB-A 的吞吐和空间放大

该研究成果以“Scavenger: Better Space-Time Trade-Offs for Key-Value Separated LSM-trees”为题，被数据库领域三大顶会之一的 ICDE 2024 （CCF-A 类论文）录用（录稿率 22%）。该研究工作得到了国家自然科学基金（U22A2027 和 61832020）、深圳科技计划项目（JCYJ20210324141601005）以及字节跳动校企合作项目的支持。