面向计算存储技术的日志结构合并树优化研究综述

doi:10.19678/j.issn.1000-3428.0252595

摘要/Abstract

摘要： 日志结构合并树(LSM-tree)被广泛用于键值存储系统,凭借顺序写入机制实现高效的写入性能,但同时也带来了读写放大率高、合并任务开销大、数据冗余等问题。传统优化方案通过调整树结构、优化合并策略、采用键值分离机制等方式提升系统性能。然而,在大数据时代,数据规模急剧飙升,LSM-tree需要处理更频繁的写入与合并任务,导致CPU计算资源持续紧张,逐渐成为系统性能提升的瓶颈。此外,传统优化方案未能避免主机与存储设备间大量的I/O操作,仍面临高昂的冗余数据迁移开销。计算存储技术为应对上述挑战带来了新思路,该技术在存储层部署额外算力资源,通过任务卸载减轻CPU负担,进一步通过近数据处理降低数据迁移带来的性能损耗。聚焦基于计算存储技术的LSM-tree优化研究。首先,对计算存储技术架构进行梳理;然后,针对大数据背景下系统面临的主要瓶颈,从合并任务优化、数据迁移优化2个方面对现有方案进行分类和对比;最后,结合当前研究的局限性与发展趋势,对未来的研究方向进行展望。

关键词: 计算存储技术, 日志结构合并树, 键值存储, 存内处理, 数据迁移

Abstract: The Log-Structured Merge-tree (LSM-tree) is widely employed in key—value storage systems, leveraging its sequential write mechanism to achieve efficient write performance. However, it also introduces challenges such as high read—write amplification, significant overhead from merge operations, and data redundancy. Traditional optimization approaches enhance the system performance by adjusting tree structures, refining merge strategies, and adopting key—value separation mechanisms. Nevertheless, in the era of big data, with the explosive growth in data volume, LSM-tree must handle more frequent write and merge operations, leading to a sustained strain on CPU computing resources, which gradually becomes a bottleneck for system performance improvement. Furthermore, traditional optimization methods fail to eliminate the substantial I/O operations between the host and storage devices and still face high costs associated with redundant data migration. Computational storage technology offers new perspectives for addressing these challenges by deploying additional computational resources at the storage layer, alleviating CPU burdens through task offloading and further reducing performance degradation caused by data migration through near-data processing. This study focuses on the optimization of an LSM-tree based on computational storage technology. First, it outlines the architecture of computational storage technology. Subsequently, it categorizes and compares existing solutions from two perspectives—merge operation optimization and data migration optimization—to address the primary bottlenecks faced by systems in the context of big data. Finally, considering the limitations and developmental trends of the current research, this study provides insights into future research directions.

Key words: computational storage technology, Log-Structured Merge-tree (LSM-tree), key—value storage, In-Storage Processing(ISP), data migration

中图分类号:

TP391

刘颖, 张润宇, 杨朝树. 面向计算存储技术的日志结构合并树优化研究综述[J]. 计算机工程, 2026, 52(10): 18-30.

LIU Ying, ZHANG Runyu, YANG Chaoshu. Survey on Optimizing Log-Structured Merge-tree Based on Computational Storage Technology[J]. Computer Engineering, 2026, 52(10): 18-30.

https://www.ecice06.com/CN/Y2026/V52/I10/18

参考文献

[1] International Data Corporation. Worldwide IDC global DataSphere forecast, 2024-2028: AI everywhere, but upsurge in data will take time[EB/OL].[2025-03-05]. https://www.marketresearch.com/IDC-v2477/Worldwide-IDC-Global-DataSphere-Forecast-36971010/.
[2] SUN H, LOU B D, ZHAO C, et al. Asynchronous compaction acceleration scheme for near-data processing-enabled LSM-tree-based KV stores[J]. ACM Transactions on Embedded Computing Systems, 2024, 23(6): 1-33.
[3] Google. LeveIDB[EB/OL].[2025-03-05].https://github.com/google/leveldb/.
[4] Facebook. RocksDB[EB/OL].[2025-03-05].https://github.com/facebook/rocksdb.
[5] HUANG G, CHENG X T, WANG J Y, et al. X-engine: an optimized storage engine for large-scale E-commerce transaction processing[C]//Proceedings of the 2019 International Conference on Management of Data. New York,USA:ACM Press,2019: 651-665.
[6] AMUR H, ANDERSEN D G, KAMINSKY M, et al. Design of a write-optimized data store[EB/OL].[2025-03-05]. https://repository.gatech.edu/server/api/core/bitstreams/79429d60-38b7-4885-9a88-c8211c7acba8/content.
[7] YAO T, WAN J G, HUANG P, et al. Building efficient key—value stores via a lightweight compaction tree[J]. ACM Transactions on Storage, 2017, 13(4): 1-28.
[8] RAJU P, KADEKODI R, CHIDAMBARAM V, et al. PebblesDB: building key—value stores using fragmented log-structured merge trees[C]//Proceedings of the 26th Symposium on Operating Systems Principles. New York,USA:ACM Press,2017: 497-514.
[9] OANA B, DIEGO D, RACHID G, et al. TRIAD: creating synergies between memory, disk and log in log structured key—value stores[C]//Proceedings of the 2017 USENIX Annual Technical Conference (ATC’17). Berkeley, CA: USENIX Association, 2017: 363-375.
[10] MEI F, CAO Q, JIANG H, et al. SifrDB: a unified solution for write-optimized key—value stores in large datacenter[C]//Proceedings of the ACM Symposium on Cloud Computing. New York,USA:ACM Press,2018: 477-489.
[11] CHAI Y P, CHAI Y F, WANG X, et al. LDC: a lower-level driven compaction method to optimize SSD-oriented key—value stores[C]//Proceedings of the IEEE 35th International Conference on Data Engineering (ICDE). Washington D.C.,USA:IEEE Press,2019: 722-733.
[12] OANA B, FLORIN D, WILLY Z, et al. SILK: preventing latency spikes in log-structured merge key—value stores[C]//Proceedings of 2019 USENIX Annual Technical Conference (ATC’19). Berkeley, CA: USENIX Association, 2019: 753-766.
[13] ZHANG Q, LI Y K, LEE P P C, et al. UniKV: toward high-performance and scalable KV storage in mixed workloads via unified indexing[C]//Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE). Washington D.C.,USA:IEEE Press,2020: 313-324.
[14] DAI Y, XU Y, GANESAN A, et al. From WiscKey to Bourbon: a learned index for log-structured merge trees[C]//Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI’20). Berkeley, CA: USENIX Association, 2020:155-171.
[15] LI F, LU Y Y, YANG Z, et al. SineKV: decoupled secondary indexing for LSM-based key—value stores[C]//Proceedings of the IEEE 40th International Conference on Distributed Computing Systems (ICDCS). Washington D.C.,USA:IEEE Press,2021: 1112-1122.
[16] ZHANG J S, WANG F, QIU S, et al. Scavenger: better space-time trade-offs for key—value separated LSM-trees[C]//Proceedings of the IEEE 40th International Conference on Data Engineering (ICDE). Washington D.C.,USA:IEEE Press,2024: 4072-4085.
[17] SHEN C, LU Y, LI F, et al. NovKV: efficient garbage collection for key—value separated LSM-stores[C]//Proceedings of the 36th Symposium on Mass Storage Systems and Technologies (MSST’20). Washington D.C.,USA:IEEE Press,2020: 1-8.
[18] SHETTY P A, SPILLANE R P, MALPANI R, et al. Building workload-independent storage with VT-trees[EB/OL].[2025-03-05]. https://www.usenix.org/system/files/conference/fast13/fast13-final165_0.pdf.
[19] SEARS R, RAMAKRISHNAN R. bLSM: a general purpose log structured merge tree[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York,USA:ACM Press,2012: 217-228.
[20] PAN F F, YUE Y L, XIONG J. dCompaction: speeding up compaction of the LSM-tree via delayed compaction[J]. Journal of Computer Science and Technology, 2017, 32(1): 41-54.
[21] YUE Y L, HE B S, LI Y Z, et al. Building an efficient put-intensive key—value store with skip-tree[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(4): 961-973.
[22] LU L Y, PILLAI T S, GOPALAKRISHNAN H, et al. WiscKey: separating keys from values in SSD-conscious storage[J]. ACM Transactions on Storage, 2017, 13(1): 1-28.
[23] CHAN H H W, LI Y, LEE P P C, et al. HashKV: enabling efficient updates in KV storage via hashing[EB/OL].[2025-03-05]. https://arxiv.org/pdf/1811.10000.
[24] TANG C L, WAN J G, XIE C S. FenceKV: enabling efficient range query for key—value separation[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(12): 3375-3386.
[25] XANTHAKIS G, SALOUSTROS G, BATSARAS N, et al. Parallax: hybrid key—value placement in LSM-based key—value stores[C]//Proceedings of the ACM Symposium on Cloud Computing. New York,USA:ACM Press,2021: 305-318.
[26] CHEN H, RUAN C Y, LI C, et al. SpanDB: a fast, cost-effective LSM-tree based KV store on hybrid storage[EB/OL].[2025-03-05]. https://www.usenix.org/conference/fast21/presentation/chen-hao.
[27] PAPAGIANNIS A, SALOUSTROS G, GONZÁLEZ-FÉREZ P, et al. An efficient memory-mapped key—value store for flash storage[C]//Proceedings of the ACM Symposium on Cloud Computing. New York,USA:ACM Press,2018: 490-502.
[28] DUAN Z H, YAO J B, LIU H K, et al. Revisiting log-structured merging for KV stores in hybrid memory systems[C]//Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. New York,USA:ACM Press,2023: 674-687.
[29] HUANG D, FENG D, LIU Q K, et al. SplitZNS: towards an efficient LSM-tree on zoned namespace SSDs[J]. ACM Transactions on Architecture and Code Optimization, 2023, 20(3): 1-26.
[30] LEE J, KIM D, LEE J W. WALTZ: leveraging zone append to tighten the tail latency of LSM tree on ZNS SSD[J]. Proceedings of the VLDB Endowment, 2023, 16(11): 2884-2896.
[31] LONG L B, HE S Y, SHEN J C, et al. WA-zone: wear-aware zone management optimization for LSM-tree on ZNS SSDs[J]. ACM Transactions on Architecture and Code Optimization, 2024, 21(1): 1-23.
[32] LIU R P, CHEN J H, CHEN P, et al. Hi-ZNS: high space efficiency and zero-copy LSM-tree based stores on ZNS SSDs[C]//Proceedings of the 53rd International Conference on Parallel Processing. New York,USA:ACM Press,2024: 1217-1226.
[33] SHEN J C, YANG L, LONG L B, et al. Overlapping aware zone allocation for LSM tree-based store on ZNS SSDs[C]//Proceedings of the 29th Asia and South Pacific Design Automation Conference (ASP-DAC). Washington D.C.,USA:IEEE Press,2024: 448-453.
[34] LU A, NARENDRA A J, FANG Z. SQL2FPGA: automated acceleration of SQL query processing on modern CPU-FPGA platforms[J]. ACM Transactions on Reconfigurable Technology and Systems, 2024, 17(3): 1-28.
[35] SOLTANIYEH M, LAGRANGE M D R V, BRYSON M, et al. Near-storage processing for solid state drive based recommendation inference with SmartSSDs^®[C]//Proceedings of the 2022 ACM/SPEC International Conference on Performance Engineering. New York,USA:ACM Press,2022: 177-186.
[36] KE L, GUPTA U, CHO B Y, et al. RecNMP: accelerating personalized recommendation with near-memory processing[C]//Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). Washington D.C.,USA:IEEE Press,2020: 790-803.
[37] LI S Y, WANG Y T, HANSON E, et al. NDRec: a near-data processing system for training large-scale recommendation models[J]. IEEE Transactions on Computers, 2024, 73(5): 1248-1261.
[38] ZHENG Y, FIXELLE J, CHALLAPALLE N, et al. ISKEVA: in-SSD key—value database engine for video analytics applications[C]//Proceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems. New York,USA:ACM Press,2022: 50-60.
[39] DANN J, RITTER D, FRÖNING H. Non-relational databases on FPGAs: survey, design decisions, challenges[J]. ACM Computing Surveys, 2023, 55(11): 1-37.
[40] The storage networking industry association, 2023, SNIA[EB/OL].[2025-03-05].https://www.snia.org/.
[41] SUN X, XUE C J, YU J H, et al. Accelerating data filtering for database using FPGA[J]. Journal of Systems Architecture, 2021, 114: 101908.
[42] 刘忠沛, 吕高锋, 王继昌, 等. 专用数据处理器综述[J]. 计算机工程与科学, 2023, 45(2): 215-227. LIU Z P, LÜ G F, WANG J C, et al. Review on data processing unit[J]. Computer Engineering & Science, 2023, 45(2): 215-227. (in Chinese)
[43] 蓝龙英, 宋程霖, 左石凯, 等. 存算一体技术研究进展与挑战[J]. 半导体技术, 2025, 50(9): 873-884. LAN L Y, SONG C L, ZUO S K, et al. Research progress and challenge of compute-in-memory technology[J]. Semiconductor Technology, 2025, 50(9): 873-884. (in Chinese)
[44] WOODS L, ISTVÁN Z, ALONSO G. Ibex: an intelligent storage engine with support for advanced SQL offloading[J]. Proceedings of the VLDB Endowment, 2014, 7(11): 963-974.
[45] LEE J H, ZHANG H, LAGRANGE V, et al. SmartSSD: FPGA accelerated near-storage data analytics on SSD[J]. IEEE Computer Architecture Letters, 2020, 19(2): 110-113.
[46] KWAK J, LEE S, PARK K, et al. Cosmos+ OpenSSD: rapid prototype for flash storage systems[J]. ACM Transactions on Storage, 2020, 16(3): 1-35.
[47] ZHANG T, WANG J Y, CHENG X T, et al. FPGA-accelerated compactions for LSM-based key—value store[EB/OL].[2025-03-05]. https://www.usenix.org/system/files/fast20-zhang_teng.pdf.
[48] SUN X, YU J H, ZHOU Z M, et al. FPGA-based compaction engine for accelerating LSM-tree key—value stores[C]//Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE). Washington D.C.,USA:IEEE Press,2020: 1261-1272.
[49] TANG D D, WANG W L, MAO Y, et al. STEM: streaming-based FPGA acceleration for large-scale compactions in LSM KV[C]//Proceedings of the IEEE 40th International Conference on Data Engineering (ICDE). Washington D.C.,USA:IEEE Press,2024: 3893-3905.
[50] XU P, WAN J G, HUANG P, et al. LUDA: boost LSM key value store compactions with GPUs[EB/OL].[2025-03-05].https://arxiv.org/abs/2004.03054.
[51] CHOI W G, KIM D, ROH H, et al. OurRocks: offloading disk scan directly to GPU in write-optimized database system[J]. IEEE Transactions on Computers, 2021, 70(11): 1831-1844.
[52] SUN H, XU J F, JIANG X X, et al. gLSM: using GPGPU to accelerate compactions in LSM-tree-based key—value stores[J]. ACM Transactions on Storage, 2024, 20(1): 1-41.
[53] CHEN J H, WANG S Z, ZHANG Z H, et al. iKnowFirst: an efficient DPU-assisted compaction for LSM-tree-based key—value stores[C]//Proceedings of the IEEE 34th International Conference on Application-specific Systems, Architectures and Processors (ASAP). Washington D.C.,USA:IEEE Press,2023: 53-60.
[54] 李迦雳, 刘铎, 陈咸彰, 等. 基于闪存存储的近数据处理技术综述[J]. 集成技术, 2022, 11(3): 23-41. LI J L, LIU D, CHEN X Z, et al. A survey of flash memory based near-data processing technology[J]. Journal of Integration Technology, 2022, 11(3): 23-41. (in Chinese)
[55] 谢洋, 李晨, 陈小文. 面向数据密集型应用的近数据处理架构设计[J]. 计算机工程与科学, 2025, 47(5): 797-810. XIE Y, LI C, CHEN X W. A near-data processing architecture for data-intensive applications[J]. Computer Engineering and Science, 2025, 47(5): 797-810. (in Chinese)
[56] FAKHRY D, ABDELSALAM M, EL-KHARASHI M W, et al. A review on computational storage devices and near memory computing for high performance applications[J]. Memories-Materials, Devices, Circuits and Systems, 2023, 4: 100051.
[57] DING C, ZHOU J, WAN J G, et al. DComp: efficient offload of LSM-tree compaction with data processing units[C]//Proceedings of the 52nd International Conference on Parallel Processing. Washington D.C.,USA:IEEE Press,2023: 233-243.
[58] DING C, ZHOU J, LU K, et al. D²Comp: efficient offload of LSM-tree compaction with data processing units on disaggregated storage[J]. ACM Transactions on Architecture and Code Optimization, 2024, 21(3): 1-22.
[59] ZHOU H, CHEN Y H, ZENG W, et al. GPComp: using GPU and SSD-GPU peer to peer DMA to accelerate LSM-tree compaction for key—value store[J]. IEEE Transactions on Parallel and Distributed Systems, 2025, 36(9): 1920-1936.
[60] SUN H, JIANG X X, YUE Y L, et al. RGKV: a GPGPU-empowered compaction framework for LSM-tree-based KV stores with optimized data transfer and parallel processing[J]. IEEE Transactions on Computers, 2025, 74(5): 1605-1619.
[61] GU B, YOON A S, BAE D H, et al. Biscuit: a framework for near-data processing of big data workloads[C]//Proceedings of the ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA). Washington D.C.,USA:IEEE Press,2016: 153-165.
[62] WU S M, LIN K H, CHANG L P. KVSSD: close integration of LSM trees and flash translation layer for write-efficient KV store[C]//Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE). Washington D.C.,USA:IEEE Press,2018: 563-568.
[63] IM J, BAE J, CHUNG C, et al. Design of LSM-tree-based key—value SSDs with bounded tails[J]. ACM Transactions on Storage, 2021, 17(2): 1-27.
[64] LEE S, LEE C G, MIN D, et al. Iterator interface extended LSM-tree-based KVSSD for range queries[C]//Proceedings of the 16th ACM International Conference on Systems and Storage. New York,USA:ACM Press,2023: 60-70.
[65] LIM M, JUNG J, SHIN D. LSM-tree compaction acceleration using in-storage processing[C]//Proceedings of the IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia). Washington D.C.,USA:IEEE Press,2021: 1-3.
[66] SUN H, LIU W, HUANG J Z, et al. Collaborative compaction optimization system using near-data processing for LSM-tree-based key—value stores[J]. Journal of Parallel and Distributed Computing, 2019, 131: 29-43.
[67] SUN H, LIU W, HUANG J Z, et al. Near-data processing-enabled and time-aware compaction optimization for LSM-tree-based key—value stores[C]//Proceedings of the 48th International Conference on Parallel Processing. New York,USA:ACM Press,2019: 1-11.
[68] SUN H, WANG Q, YUE Y L, et al. A storage computing architecture with multiple NDP devices for accelerating compaction performance in LSM-tree based KV stores[J]. Journal of Systems Architecture, 2022, 130: 102681.
[69] JARANILLA C, CHOI J. Requirements and trade-offs of compression techniques in key—value stores: a survey[J]. Electronics, 2023, 12(20): 4280.
[70] SUN H, ZHAO C, YUE Y L, et al. ProckStore: an NDP-empowered key—value store with asynchronous and multi-threaded compaction scheme for optimized performance[J]. Journal of Systems Architecture, 2025, 160: 103342.
[71] PARK I, ZHENG Q, MANNO D, et al. KV-CSD: a hardware-accelerated key—value store for data-intensive applications[C]//Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER). Washington D.C.,USA:IEEE Press,2023: 132-144.
[72] DUAN Z, FENG H, LIU H, et al. AegonKV: a high bandwidth, low tail latency, and low storage cost KV-separated LSM store with SmartSSD-based GC offloading[C]//Proceedings of the 23rd USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2025: 321-335.

选择文件类型/文献管理软件名称

选择包含的内容