{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T14:26:43Z","timestamp":1762180003211,"version":"build-2065373602"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62472002 and 62072001"],"award-info":[{"award-number":["62472002 and 62072001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["IIS-1618669 and OAC-1642133"],"award-info":[{"award-number":["IIS-1618669 and OAC-1642133"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000104","name":"National Aeronautics and Space Administration","doi-asserted-by":"crossref","award":["80NSSC20M0044"],"award-info":[{"award-number":["80NSSC20M0044"]}],"id":[{"id":"10.13039\/100000104","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008760","name":"National Highway Traffic Safety Administration","doi-asserted-by":"crossref","award":["451861-19158"],"award-info":[{"award-number":["451861-19158"]}],"id":[{"id":"10.13039\/100008760","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Wright Media, LLC","award":["240250 and 240311"],"award-info":[{"award-number":["240250 and 240311"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>\n                    Key-value stores (KV stores) anchored on log-structured merge trees (LSM-tree) provide much improved performance under write-intensive workloads but exhibit significant write amplification (WA). The tiering compaction strategy is widely adopted in KV stores to reduce the WA. However, there are three imminent issues in tiering-based KV stores. First, excessive levels in the LSM-tree structure result in high read and write amplification. Second, without key partitioning support, these KV stores increase write tail latency. Relying solely on a hash-based key partitioning scheme is insufficient, as it does not support range queries. Furthermore, a KV store with only a key range-based partitioning scheme overlooks the distribution of keys within the key space. Third, existing KV stores with level optimization can incur high costs. A common approach to reducing the number of LSM-tree levels is to increase the MemTable\u00a0size. While this reduces the number of levels, it requires more memory, leading to higher costs. Therefore, it is crucial to balance the tradeoff between level optimization and monetary expenses. To address these issues, we propose a tiering-based key-value store, leveraging high-performance hierarchical data management. The key space of our proposed KV store is partitioned into\n                    <jats:underline>\n                      <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    <\/jats:underline>\n                    ultiple partitions based on key ranges, with an LSM-\n                    <jats:underline>\n                      <jats:italic toggle=\"yes\">tree<\/jats:italic>\n                    <\/jats:underline>\n                    in each partition. We refer to this KV store as\n                    <jats:italic toggle=\"yes\">MTree<\/jats:italic>\n                    in this article. MTree reduces the number of levels in the LSM-Tree structure close to one without increasing the monetary cost. In MTree, a hierarchical structure that combines the log and LSM-tree curtails the number of levels in the LSM-tree by accumulating the data in the log without increasing the cost. With the hierarchical structure in place, we devise a long- and short-term key density distribution-aware partitioning scheme for the key range. This scheme dynamically adjusts the size of partitioning, balancing data in the partition and storing most data in large-sized logs. Then, MTree reduces the number of levels in the LSM-tree, thereby optimizing the read\/write amplification. The experimental results show that MTree limits the WA to as low as two. MTree enhances the random write throughput of the state-of-the-art KV stores by up to 6.9\u00d7.\n                  <\/jats:p>","DOI":"10.1145\/3736587","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T07:14:56Z","timestamp":1747725296000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["MTree: A Tiering-based Key-Value Store Powered by High-performance Hierarchical Data Management"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1811-1318","authenticated-orcid":false,"given":"Hui","family":"Sun","sequence":"first","affiliation":[{"name":"computer science and technology, Anhui University","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4728-6631","authenticated-orcid":false,"given":"Yinhui","family":"Chen","sequence":"additional","affiliation":[{"name":"computer science and technology, Anhui University","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9226-8621","authenticated-orcid":false,"given":"Yonwei","family":"Yu","sequence":"additional","affiliation":[{"name":"Anhui University","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0850-7774","authenticated-orcid":false,"given":"Yajie","family":"Deng","sequence":"additional","affiliation":[{"name":"Anhui University","place":["Hefei, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8417-2234","authenticated-orcid":false,"given":"Yinliang","family":"Yue","sequence":"additional","affiliation":[{"name":"Zhongguancun Laboratory","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1681-9008","authenticated-orcid":false,"given":"Song","family":"Jiang","sequence":"additional","affiliation":[{"name":"Electrical and Computer Engineering Department, The University of Texas at Arlington","place":["Arlington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8345-3587","authenticated-orcid":false,"given":"Xiao","family":"Qin","sequence":"additional","affiliation":[{"name":"Computer Science and Software Engineering, Auburn University","place":["Auburn, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,3]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201919)","author":"Ahn Jung-Sang","year":"2019","unstructured":"Jung-Sang Ahn, Mohiuddin Abdul Qader, Woon-Hak Kang, Hieu Nguyen, Guogen Zhang, and Sami Ben-Romdhane. 2019. Jungle: Towards dynamically adjustable \\(\\lbrace\\) Key-Value \\(\\rbrace\\) store by combining \\(\\lbrace\\) LSM-Tree \\(\\rbrace\\) and \\(\\lbrace\\) Copy-On-Write \\(\\rbrace\\) \\(\\lbrace\\) B+-Tree \\(\\rbrace\\) . In Proceedings of the 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201919)."},{"key":"e_1_3_2_3_2","unstructured":"Reed Allman. 2014. Rock Solid Queues @ Iron.io. Retrieved June 4 2025 from https:\/\/www.youtube.com\/watch?v=HTjt6oj-RL4"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_3_2_5_2","unstructured":"Betterbq. 2024. YCSB-OPENALEX. GitHub Repository. Retrieved June 4 2025 from https:\/\/github.com\/betterbq\/YCSB-OPENALEX"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36318-4_3"},{"key":"e_1_3_2_8_2","first-page":"546","volume-title":"Proceedings of the SODA","author":"Brodal Gerth St\u00f8lting","year":"2003","unstructured":"Gerth St\u00f8lting Brodal and Rolf Fagerberg. 2003. Lower bounds for external memory dictionaries.. In Proceedings of the SODA. 546\u2013554."},{"key":"e_1_3_2_9_2","first-page":"209","volume-title":"Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST\u201920)","author":"Cao Zhichao","year":"2020","unstructured":"Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Characterizing, modeling, and benchmarking \\(\\lbrace\\) RocksDB \\(\\rbrace\\) \\(\\lbrace\\) Key-Value \\(\\rbrace\\) workloads at facebook. In Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST\u201920). 209\u2013223."},{"issue":"6","key":"e_1_3_2_10_2","first-page":"2595","article-title":"Adaptive lower-level driven compaction to optimize LSM-tree key-value stores","volume":"34","author":"Chai Yunpeng","year":"2020","unstructured":"Yunpeng Chai, Yanfeng Chai, Xin Wang, Haocheng Wei, and Yangyang Wang. 2020. Adaptive lower-level driven compaction to optimize LSM-tree key-value stores. IEEE Transactions on Knowledge and Data Engineering 34, 6 (2020), 2595\u20132609.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_11_2","first-page":"1007","volume-title":"Proceedings of the 2018  \\(\\lbrace\\) USENIX \\(\\rbrace\\)  Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\)  \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201918)","author":"Chan Helen H. W.","year":"2018","unstructured":"Helen H. W. Chan, Yongkun Li, Patrick P. C. Lee, and Yinlong Xu. 2018. Hashkv: Enabling efficient updates in \\(\\lbrace\\) KV \\(\\rbrace\\) storage via hashing. In Proceedings of the 2018 \\(\\lbrace\\) USENIX \\(\\rbrace\\) Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\) \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201918). 1007\u20131019."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"key":"e_1_3_2_15_2","first-page":"49","volume-title":"Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920)","author":"Conway Alexander","year":"2020","unstructured":"Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard Spillane, Amy Tai, and Rob Johnson. 2020. \\(\\lbrace\\) SplinterDB \\(\\rbrace\\) : closing the bandwidth gap for \\(\\lbrace\\) NVMe \\(\\rbrace\\) \\(\\lbrace\\) Key-Value \\(\\rbrace\\) stores. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). 49\u201363."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551853"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_3_2_21_2","unstructured":"Facebook. 2019. Rocksdb a persistent key-value store for fast storage environments 2019. [Online]. Available: http:\/\/rocksdb.org\/"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_3_2_23_2","unstructured":"B. Fitzpatrick and A. Vorobey. 2011. Memcached: a distributed memory object caching system[EB\/OL].(2011-1)."},{"key":"e_1_3_2_24_2","volume-title":"Proceedings of the 36th International Conference on Massive Storage Systems and Technology (MSST\u201920)","author":"Han Shukai","year":"2020","unstructured":"Shukai Han, Dejun Jiang, and Jin Xiong. 2020. Lightkv: A cross media key value store with persistent memory to cut long tail latency. In Proceedings of the 36th International Conference on Massive Storage Systems and Technology (MSST\u201920)."},{"key":"e_1_3_2_25_2","unstructured":"Yupeng Hou Jiacheng Li Zhankui He An Yan Xiusi Chen and Julian McAuley. 2024. Bridging language and items for retrieval and recommendation. CoRR (2024)."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2798729"},{"key":"e_1_3_2_27_2","unstructured":"O. Kaiyrakhmet S. Lee B. Nam et\u00a0al. 2019. SLM-DB: Single-LevelKey-Value store with persistent memory. 17th USENIX Conference on File and Storage Technologies (FAST 19). 191\u2013205."},{"key":"e_1_3_2_28_2","first-page":"993","volume-title":"Proceedings of the 2018  \\(\\lbrace\\) USENIX \\(\\rbrace\\)  Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\)  \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201918)","author":"Kannan Sudarsun","year":"2018","unstructured":"Sudarsun Kannan, Nitish Bhat, Ada Gavrilovska, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2018. Redesigning LSMs for nonvolatile memory with NoveLSM. In Proceedings of the 2018 \\(\\lbrace\\) USENIX \\(\\rbrace\\) Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\) \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201918). 993\u20131005."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1985.6313426"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/3477.764879"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"Andrew Lamb Matt Fuller Ramakrishna Varadarajan Nga Tran Ben Vandier Lyric Doshi and Chuck Bear. 2012. The vertica analytic database: C-store 7 years later. Proceedings of the VLDB Endowment 5 12 (2012) 1790\u20131801.","DOI":"10.14778\/2367502.2367518"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","unstructured":"Per-\u00c5ke Larson Spyros Blanas Cristian Diaconu Craig Freedman Jignesh M. Patel and Mike Zwilling. 2011. High-performance concurrency control mechanisms for main-memory databases. Proceedings of the VLDB Endowment 5 4 (2011) 327\u2013338.","DOI":"10.14778\/2095686.2095689"},{"key":"e_1_3_2_34_2","unstructured":"Leveldb. 2018. Fast and Lightweight Key\/value Database Library by Google. Retrieved June 4 2025 from http:\/\/code.google.com\/p\/leveldb"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489512"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483568"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267829"},{"key":"e_1_3_2_39_2","first-page":"449","volume-title":"Proceedings of the 2019 International Conference on Management of Data","author":"Idreos N. Dayan and S.","year":"2019","unstructured":"N. Dayan and S. Idreos. 2019. The log-structured merge-bush and the wacky continuum. In Proceedings of the 2019 International Conference on Management of Data. 449\u2013466."},{"key":"e_1_3_2_40_2","first-page":"183","volume-title":"Proceedings of the USENIX Annual Technical Conference, FREENIX Track","author":"Olson Michael A.","year":"1999","unstructured":"Michael A. Olson, Keith Bostic, and Margo I. Seltzer. 1999. Berkeley DB.. In Proceedings of the USENIX Annual Technical Conference, FREENIX Track. 183\u2013191."},{"key":"e_1_3_2_41_2","unstructured":"OpenAlex. 2024. OpenAlex: An Open Index of Scholarly Works. Retrieved June 4 2025 from https:\/\/openalex.org"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-016-0472-z"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_3_2_46_2","first-page":"145","volume-title":"Proceedings of the 2013  \\(\\lbrace\\) USENIX \\(\\rbrace\\)  Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\)  \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201913)","author":"Ren Kai","year":"2013","unstructured":"Kai Ren and Garth Gibson. 2013. \\(\\lbrace\\) TABLEFS \\(\\rbrace\\) : Enhancing metadata efficiency in the local file system. In Proceedings of the 2013 \\(\\lbrace\\) USENIX \\(\\rbrace\\) Annual Technical Conference ( \\(\\lbrace\\) USENIX \\(\\rbrace\\) \\(\\lbrace\\) ATC \\(\\rbrace\\) \u201913). 145\u2013156."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2023.3329646"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3149003"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_3_2_50_2","first-page":"71","volume-title":"Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference","author":"Wu Xingbo","year":"2015","unstructured":"Xingbo Wu, Yuehai Xu, Zili Shao, and Song Jiang. 2015. LSM-trie: An LSM-tree-based ultra-large key-value store for small data. In Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. USENIX Association, 71\u201382."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472883.3487012"},{"key":"e_1_3_2_52_2","unstructured":"Yahoo!2019. YCSB-C a C++ Version of YCSB. Retrieved June 4 2025 from https:\/\/github.com\/brianfrankcooper\/YCSB"},{"key":"e_1_3_2_53_2","first-page":"1","volume-title":"Proceedings of the 33rd International Conference on Massive Storage Systems and Technologies (MSST\u201917)","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 Proceedings of the 33rd International Conference on Massive Storage Systems and Technologies (MSST\u201917). 1\u201313."},{"key":"e_1_3_2_54_2","first-page":"17","volume-title":"Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference","author":"Yao Ting","year":"2020","unstructured":"Ting Yao, Yiwen Zhang, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang, Changsheng Xie, and Xubin He. 2020. MatrixKV: Reducing write stalls and write amplification in LSM-tree based KV stores with a matrix container in NVM. In Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference. 17\u201331."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2609912"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3234510"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456237"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00125"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T13:36:55Z","timestamp":1762177015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,3]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3736587"],"URL":"https:\/\/doi.org\/10.1145\/3736587","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2025,11,3]]},"assertion":[{"value":"2024-06-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}