软件学报

作者：杜云箫，陈珂，寿黎但，江大伟，骆歆远，陈刚

单位：杜云箫，浙江大学 软件学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002711,陈珂，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002702,寿黎但，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002703,江大伟，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002704,骆歆远，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002705,陈刚，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 31002706

关键词：键值存储;日志合并树;非易失性内存

基金：国家重点研发计划(2022YFB2703100); 浙江省“尖兵”计划(2024C01021)

基于日志合并树(LSM-tree)的键值(key-value)存储由于其出色的读写性能而被广泛用于许多应用中. 大多数现有的日志合并树采用多层结构来存储数据. 尽管多层数据结构可以很好地服务于适度的写密集型应用, 但这种结构并不十分适合高写密集型应用. 这是因为以多层方式保存数据会引入写放大问题, 即新的数据插入会引发很大一部分已经存储在多层中的数据被重组的问题. 这种巨大的(有时是频繁的)数据重组是昂贵的, 并且在许多高写密集型的应用中降低了写入性能. 此外, 多层结构不能为热数据持续提供出色的读取性能. 这是因为多级结构不能通过及时合并重叠的范围来优化热数据的读取操作. 为了解决上述两个问题, 提出LazyStore, 一种基于混合存储架构的新型单层日志合并树. LazyStore通过将数据存储在单一逻辑层而不是多个逻辑层来解决写放大的问题. 因此, 昂贵的多级数据重组在很大程度上被消除. 为了进一步提高写入性能, LazyStore根据每个存储设备的容量和读/写性能, 将逻辑层中的数据分布到多个存储设备中, 如内存、非易失性内存和闪存. 此外, LazyStore引入实时合并操作, 以提高热数据范围的读取性能. 实验表明, 与其他多级日志合并树相比, LazyStore最多将写入性能提高3倍, 并将写入放大率降低至1/4. 而对于热门范围的读取, LazyStore的实时数据合并优化可以将范围查询处理的延迟降低一半.

来源：2025年第2期

《软件学报》期刊编辑部

查看软件学报杂志2025年第2期