{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T16:14:09Z","timestamp":1792253649023,"version":"4.4.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Mainstream LSM-tree-based key-value stores face challenges in optimizing performance for point lookup, range lookup, and update operations concurrently due to their constrained configurations. They typically follow fixed patterns to specify the level capacity and the number of sorted runs per-level. This confines their designs to a restricted space, limiting opportunities for broader optimizations.<\/jats:p>\n                  <jats:p>To address this challenge, we consider a more flexible configuration that enables independent adjustments of the number of runs per-level, size ratio, and Bloom filter settings at each LSM-tree level. By carefully analyzing the cost of each operation based on the new design space, we unveil two critical insights for optimizing the tradeoff among the three operations. Firstly, achieving efficient point lookup requires a large last level. Secondly, there is a specific correlation between the number of runs per level and size ratio that is advantageous for overall update and range lookup performance.<\/jats:p>\n                  <jats:p>Based on these insights, we introduce Moose, a structure delivering an impressive overall performance for point lookup, range lookup, and update concurrently. Furthermore, we also introduce a new framework, Smoose, to navigate the design space for adapting specific workloads. We implemented Moose and Smoose on top of RocksDB and experimental results demonstrate that our proposed approach outperforms state-of-the-art LSM-tree structures across diverse workloads.<\/jats:p>","DOI":"10.1145\/3654978","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":15,"title":["Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in a Colossal Configuration Space"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4570-5043","authenticated-orcid":false,"given":"Junfeng","family":"Liu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4786-6796","authenticated-orcid":false,"given":"Fan","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9588-1036","authenticated-orcid":false,"given":"Dingheng","family":"Mo","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8197-0903","authenticated-orcid":false,"given":"Siqiang","family":"Luo","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757810"},{"key":"e_1_2_1_2_1","volume-title":"An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version). arXiv preprint arXiv:1910.08185","author":"Alkowaileet Wail Y","year":"2019","unstructured":"Wail Y Alkowaileet, Sattam Alsubaiee, and Michael J Carey. 2019. An LSM-based Tuple Compaction Framework for Apache AsterixDB (Extended Version). arXiv preprint arXiv:1910.08185 (2019)."},{"key":"e_1_2_1_3_1","volume-title":"Columnar formats for schemaless LSM-based document stores. arXiv preprint arXiv:2111.11517","author":"Alkowaileet Wail Y","year":"2021","unstructured":"Wail Y Alkowaileet and Michael J Carey. 2021. Columnar formats for schemaless LSM-based document stores. arXiv preprint arXiv:2111.11517 (2021)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Timothy G Armstrong Vamsi Ponnekanti Dhruba Borthakur and Mark Callaghan. 2013. Linkbench: a database benchmark based on the facebook social graph. In SIGMOD. 1185--1196.","DOI":"10.1145\/2463676.2465296"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056103"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461543"},{"key":"e_1_2_1_7_1","volume-title":"2018 USENIX Annual Technical Conference (USENIX ATC 18)","author":"Chan Helen HW","year":"2018","unstructured":"Helen HW Chan, Chieh-Jan Mike Liang, Yongkun Li, Wenjia He, Patrick PC Lee, Lianjie Zhu, Yaozu Dong, Yinlong Xu, Yu Xu, Jin Jiang, et al. 2018. HashKV: Enabling Efficient Updates in KV Storage via Hashing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 1007--1019."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485461"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659447"},{"key":"e_1_2_1_10_1","unstructured":"Source Code. 2022. WiredTiger. https:\/\/github.com\/wiredtiger\/wiredtiger."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639258"},{"key":"e_1_2_1_13_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Dai Yifan","year":"2020","unstructured":"Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2020. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 155--171."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319903"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457273"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551853"},{"key":"e_1_2_1_19_1","first-page":"3","article-title":"Optimizing Space Amplification in RocksDB","volume":"3","author":"Dong Siying","year":"2017","unstructured":"Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB.. In CIDR, Vol. 3. 3.","journal-title":"CIDR"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583167"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481897"},{"key":"e_1_2_1_22_1","unstructured":"Facebook. 2022. RocksDB. https:\/\/github.com\/facebook\/rocksdb."},{"key":"e_1_2_1_23_1","unstructured":"Google. 2022. LevelDB. https:\/\/github.com\/google\/leveldb\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314041"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457297"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529345"},{"key":"e_1_2_1_27_1","volume-title":"Towards flexibility and robustness of LSM trees. The VLDB Journal","author":"Huynh Andy","year":"2024","unstructured":"Andy Huynh, Harshal A Chaudhari, Evimaria Terzi, and Manos Athanassoulis. 2024. Towards flexibility and robustness of LSM trees. The VLDB Journal (2024), 1--24."},{"key":"e_1_2_1_28_1","unstructured":"Stratos Idreos Niv Dayan Wilson Qin Mali Akmanalp Sophie Hilgard Andrew Ross James Lennon Varun Jain Harshita Gupta David Li et al. 2019. Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn.. In CIDR."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2799"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526167"},{"key":"e_1_2_1_31_1","first-page":"677","article-title":"Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes","volume":"11","author":"Kondylakis Haridimos","year":"2018","unstructured":"Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas. 2018. Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes. PVLDB 11, 6 (2018), 677--690.","journal-title":"PVLDB"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565854"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511996"},{"key":"e_1_2_1_35_1","unstructured":"LinkedIn. 2022. Voldemort. http:\/\/www.project-voldemort.com."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430916"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177736"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData50022.2020.9377919"},{"key":"e_1_2_1_41_1","volume-title":"Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads. arXiv preprint arXiv:2308.07013","author":"Mo Dingheng","year":"2023","unstructured":"Dingheng Mo, Fanchao Chen, Siqiang Luo, and Caihua Shan. 2023. Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads. arXiv preprint arXiv:2308.07013 (2023)."},{"key":"e_1_2_1_42_1","volume-title":"Advances in database technology: Proceedings of the 26th International Conference on Extending database Technology (EDBT), 28th March-31st","author":"M\u00f6\u00dfner Bernhard","year":"2023","unstructured":"Bernhard M\u00f6\u00dfner, Christian Riegger, Arthur Bernhardt, and Ilia Petrov. 2023. bloomRF: On performing range-queries in Bloom-Filters with piecewise-monotone hash functions and prefix hashing. In Advances in database technology: Proceedings of the 26th International Conference on Extending database Technology (EDBT), 28th March-31st March 2023, Ioannina, Greece, Vol. 26. Open Proceedings. org, Univ. of Konstanz, 131--143."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-016-0472-z"},{"key":"e_1_2_1_45_1","volume-title":"10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)","author":"Raju Pandian","year":"2018","unstructured":"Pandian Raju, Soujanya Ponnapalli, Evan Kaminsky, Gilad Oved, Zachary Keener, Vijay Chidambaram, and Ittai Abraham. 2018. $$mLSM$$: Making Authenticated Storage Faster in Ethereum. In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056102"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389757"},{"key":"e_1_2_1_48_1","volume-title":"Constructing and Analyzing the LSM Compaction Design Space (Updated Version). arXiv preprint arXiv:2202.04522","author":"Sarkar Subhadeep","year":"2022","unstructured":"Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. 2022. Constructing and Analyzing the LSM Compaction Design Space (Updated Version). arXiv preprint arXiv:2202.04522 (2022)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403231"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561270"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.121"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_1_55_1","volume-title":"Noftl-kv: Tackling write-amplification on kv-stores with native storage management. In Advances in database technology-EDBT 2018: 21st International Conference on Extending Database Technology","author":"Tobias Vincc","year":"2018","unstructured":"Tobias Vincc on, Sergej Hardock, Christian Riegger, Julian Oppermann, Andreas Koch, and Ilia Petrov. 2018. Noftl-kv: Tackling write-amplification on kv-stores with native storage management. In Advances in database technology-EDBT 2018: 21st International Conference on Extending Database Technology, Vienna, Austria, March 26--29, 2018. proceedings. University of Konstanz, University Library, 457--460."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494150"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00217"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00158"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467875"},{"key":"e_1_2_1_61_1","volume-title":"Proc. 33rd Int. Conf. Massive Storage Syst. Technol.(MSST). 1--13","author":"Yao Ting","year":"2017","unstructured":"Ting Yao, Jiguang Wan, Ping Huang, Xubin He, Qingxin Gui, Fei Wu, and Changsheng Xie. 2017. A light-weight compaction tree to reduce I\/O amplification toward efficient key-value stores. In Proc. 33rd Int. Conf. Massive Storage Syst. Technol.(MSST). 1--13."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547320"},{"key":"e_1_2_1_64_1","volume-title":"FPGA-Accelerated Compactions for LSM-based Key-Value Store. In 18th USENIX Conference on File and Storage Technologies (FAST 20)","author":"Zhang Teng","year":"2020","unstructured":"Teng Zhang, Jianying Wang, Xuntao Cheng, Hao Xu, Nanlong Yu, Gui Huang, Tieying Zhang, Dengcheng He, Feifei Li, Wei Cao, et al. 2020. FPGA-Accelerated Compactions for LSM-based Key-Value Store. In 18th USENIX Conference on File and Storage Technologies (FAST 20). 225--237."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538712.3538730"},{"key":"e_1_2_1_66_1","volume-title":"PM-Blade: A Persistent Memory Augmented LSM-tree Storage for Database. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 3363--3375","author":"Zhang Yinan","year":"2023","unstructured":"Yinan Zhang, Huiqi Hu, Xuan Zhou, Enlong Xie, Hongdi Ren, and Le Jin. 2023. PM-Blade: A Persistent Memory Augmented LSM-tree Storage for Database. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 3363--3375."},{"key":"e_1_2_1_67_1","volume-title":"ElasticBF: Fine-grained and Elastic Bloom Filter Towards Efficient Read for LSM-tree-based KV Stores. In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)","author":"Zhang Yueming","year":"2018","unstructured":"Yueming Zhang, Yongkun Li, Fan Guo, Cheng Li, and Yinlong Xu. 2018a. ElasticBF: Fine-grained and Elastic Bloom Filter Towards Efficient Read for LSM-tree-based KV Stores. In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)."},{"key":"e_1_2_1_68_1","volume-title":"Redesigning High-Performance LSM-based Key-Value Stores with Persistent CPU Caches. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 1098--1111","author":"Zhong Yijie","year":"2023","unstructured":"Yijie Zhong, Zhirong Shen, Zixiang Yu, and Jiwu Shu. 2023. Redesigning High-Performance LSM-based Key-Value Stores with Persistent CPU Caches. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 1098--1111."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466002"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654978","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:36:31Z","timestamp":1755786991000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654978"],"URL":"https:\/\/doi.org\/10.1145\/3654978","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}