基于日志结构合并树(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 有限的存储空间配额下实现了更好的前台性能,在不限制空间的场景中显著减小了空间放大,从而实现了性能和存储空间之间更好的平衡。
![33285 33285](/__local/0/86/AF/E09101D8AB1A7A4F2C276E2B0A4_6C90B1E0_33285.png)
图 1:Scavenger 架构图
![96EA 96EA](/__local/B/8B/70/73B39B1CC95350C43838EB60436_5009B960_96EA.png)
图 2:限制空间 1.5x 下的 YCSB 前台性能吞吐
![1118E 1118E](/__local/7/C0/A1/A70D1E2FF4B554C9C7AD0BD5858_E5C9484D_1118E.png)
图 3:不限制空间下的 YCSB-A 的吞吐和空间放大
该研究成果以“Scavenger: Better Space-Time Trade-Offs for Key-Value Separated LSM-trees”为题,被数据库领域三大顶会之一的 ICDE 2024 (CCF-A 类论文)录用(录稿率 22%)。该研究工作得到了国家自然科学基金(U22A2027 和 61832020)、深圳科技计划项目(JCYJ20210324141601005)以及字节跳动校企合作项目的支持。