LazyStore:基于混合存储架构的写优化键值存储系统  

LazyStore:Write-optimized Key-value Storage System Based on Hybrid Storage Architecture

作　　者：杜云箫 陈珂[1,3] 寿黎但[1,3] 江大伟 骆歆远[1,3] 陈刚 DU Yun-Xiao;CHEN Ke;SHOU Li-Dan;JIANG Da-Wei;LUO Xin-Yuan;CHEN Gang(College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China;School of Software Technology,Zhejiang University,Hangzhou 310027,China;Key Laboratory of Big Data Intelligent Computing of Zhejiang Province(Zhejiang University),Hangzhou 310027,China)

机构地区：[1]浙江大学计算机科学与技术学院,浙江杭州310027 [2]浙江大学软件学院,浙江杭州310027 [3]浙江省大数据智能计算重点实验室(浙江大学),浙江杭州310027

出　　处：《软件学报》2025年第2期805-829,共25页Journal of Software

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

摘　　要：基于日志合并树(LSM-tree)的键值(key-value)存储由于其出色的读写性能而被广泛用于许多应用中.大多数现有的日志合并树采用多层结构来存储数据.尽管多层数据结构可以很好地服务于适度的写密集型应用,但这种结构并不十分适合高写密集型应用.这是因为以多层方式保存数据会引入写放大问题,即新的数据插入会引发很大一部分已经存储在多层中的数据被重组的问题.这种巨大的(有时是频繁的)数据重组是昂贵的,并且在许多高写密集型的应用中降低了写入性能.此外,多层结构不能为热数据持续提供出色的读取性能.这是因为多级结构不能通过及时合并重叠的范围来优化热数据的读取操作.为了解决上述两个问题,提出LazyStore,一种基于混合存储架构的新型单层日志合并树.LazyStore通过将数据存储在单一逻辑层而不是多个逻辑层来解决写放大的问题.因此,昂贵的多级数据重组在很大程度上被消除.为了进一步提高写入性能,LazyStore根据每个存储设备的容量和读/写性能,将逻辑层中的数据分布到多个存储设备中,如内存、非易失性内存和闪存.此外,LazyStore引入实时合并操作,以提高热数据范围的读取性能.实验表明,与其他多级日志合并树相比,LazyStore最多将写入性能提高3倍,并将写入放大率降低至1/4.而对于热门范围的读取,LazyStore的实时数据合并优化可以将范围查询处理的延迟降低一半.Log-structured merge-tree(LSM-tree)based key-value storage is widely used in many applications due to its excellent read and write performance.Most existing LSM-trees utilize a multi-level structure to store data.Although the multi-level data structure can serve moderately write-intensive applications well,this structure is not well suited for highly write-intensive applications.This is because storing data in multi-levels introduces the write amplification problem,where new data insertion triggers the reorganization of a large portion of the data already stored in multiple levels.This huge(and sometimes frequent)data reorganization is expensive and degrades write performance in many highly write-intensive applications.In addition,the multi-level structure does not provide consistently excellent read performance for hot data.This is because the multi-level structure cannot optimize the read operation of hot data by merging overlapping ranges in a timely manner.To address the above two challenges,this study proposes LazyStore,a novel single-level LSM-tree based on a hybrid storage architecture.LazyStore solves the write amplification problem by storing data in a single logical level instead of multiple logical levels.As a result,expensive multi-level data reorganization is largely eliminated.To further improve write performance,LazyStore distributes data at the logical level to multiple storage devices,such as DRAM,NVM,and SSD,based on the capacity and read/write performance of each storage device.Furthermore,LazyStore introduces real-time merge operations to improve the read performance of hot data ranges.Experiments show that LazyStore improves write performance by 3 times and reduces write amplification by nearly 4 times compared to other multi-level LSM-trees.For hot range reads,LazyStore’s real-time data merge optimization can reduce the latency of range query processing by a factor of two.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]