{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T02:05:05Z","timestamp":1791425105946,"version":"4.3.3"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"Nanyang Technological University","doi-asserted-by":"publisher","award":["SUG-NAP (022029-00001)"],"award-info":[{"award-number":["SUG-NAP (022029-00001)"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    LSM-tree based key-value stores are widely adopted as the data storage backend in modern big data applications. The LSM-tree\n                    <jats:italic toggle=\"yes\">grows<\/jats:italic>\n                    with data ingestion, by either adding levels with fixed level capacities (dubbed as vertical scheme) or increasing level capacities with fixed number of levels (dubbed as horizontal scheme). The vertical scheme leads the trend in recent system designs in RocksDB, LevelDB, and WiredTiger, whereas the horizontal scheme shows a decline in being adopted in the industry. The growth scheme profoundly impacts the LSM system performance in various aspects such as read, write and space costs. This paper attempts to give a new insight into a fundamental design question --\n                    <jats:italic toggle=\"yes\">how to grow an LSM-tree<\/jats:italic>\n                    to attain more desirable performance?\n                  <\/jats:p>\n                  <jats:p>Our analysis highlights the limitations of the vertical scheme in achieving an optimal read-write trade-off and the horizontal scheme in managing space cost effectively. Building on the analysis, we present a novel approach, Vertiorizon, which combines the strengths of both the vertical and horizontal schemes to achieve a superior balance between lookup, update, and space costs. Its adaptive design makes it highly compatible with a wide spectrum of workloads. Compared to the vertical scheme, Vertiorizon significantly improves the read-write performance trade-off. In contrast to the horizontal scheme, Vertiorizon greatly extends the trade-off range by a non-trivial generalization of Bentley and Saxe's theory, while substantially reducing space costs. When integrated with RocksDB, Vertiorizon demonstrates better write performance than the vertical scheme, while incurring about six times less additional space cost compared to the horizontal scheme.<\/jats:p>","DOI":"10.1145\/3725310","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-25","source":"Crossref","is-referenced-by-count":6,"title":["How to Grow an LSM-tree? Towards Bridging the Gap Between Theory and Practice"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9588-1036","authenticated-orcid":false,"given":"Dingheng","family":"Mo","sequence":"first","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8271-9187","authenticated-orcid":false,"given":"Stratos","family":"Idreos","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. Technical Report. https:\/\/sites.google.com\/view\/lsm-scheme-technical-report."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183761"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2757807.2757810"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Sattam Alsubaiee Yasser Altowim Hotham Altwaijry Alexander Behm Vinayak Borkar Yingyi Bu Michael Carey Inci Cetindil Madhusudan Cheelangi Khurram Faraaz et al. 2014. AsterixDB: A scalable open source BDMS. arXiv preprint arXiv:1407.0454 (2014).","DOI":"10.14778\/2733085.2733096"},{"key":"e_1_2_1_5_1","first-page":"363","volume-title":"Disk and Log in Log Structured Key-Value Stores. In 2017 USENIX Annual Technical Conference (USENIX ATC 17)","author":"Balmau Oana","year":"2017","unstructured":"Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017. TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores. In 2017 USENIX Annual Technical Conference (USENIX ATC 17). 363-375."},{"key":"e_1_2_1_6_1","first-page":"753","volume-title":"SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Balmau Oana","year":"2019","unstructured":"Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 753-766."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229873"},{"key":"e_1_2_1_9_1","first-page":"1007","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_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485461"},{"key":"e_1_2_1_12_1","unstructured":"Source Code. 2024a. BadgerDB. https:\/\/github.com\/dgraph-io\/badger."},{"key":"e_1_2_1_13_1","unstructured":"Source Code. 2024b. WiredTiger. https:\/\/github.com\/wiredtiger\/wiredtiger."},{"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","unstructured":"DGraph. 2024. DGraph. https:\/\/dgraph.io\/."},{"key":"e_1_2_1_20_1","unstructured":"Facebook. 2024a. RocksDB. https:\/\/github.com\/facebook\/rocksdb."},{"key":"e_1_2_1_21_1","unstructured":"Facebook. 2024b. RocksDB tuning guide. https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide."},{"key":"e_1_2_1_22_1","unstructured":"Facebook. 2024c. Universal Compaction in RocksDB. https:\/\/github.com\/facebook\/rocksdb\/wiki\/universal-compaction."},{"key":"e_1_2_1_23_1","volume-title":"HBase: the definitive guide: random access to your planet-size data. \"O'Reilly Media","author":"George Lars","unstructured":"Lars George. 2011. HBase: the definitive guide: random access to your planet-size data. \"O'Reilly Media, Inc.\"."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_25_1","unstructured":"Google. 2024. LevelDB. https:\/\/github.com\/google\/leveldb\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314041"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314041"},{"key":"e_1_2_1_28_1","volume-title":"Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty. arXiv preprint arXiv:2110.13801","author":"Huynh Andy","year":"2021","unstructured":"Andy Huynh, Harshal Chaudhari, Evimaria Terzi, and Manos Athanassoulis. 2021. Endure: A Robust Tuning Paradigm for LSM Trees Under Workload Uncertainty. arXiv preprint arXiv:2110.13801, (2021)."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR).","author":"Idreos Stratos","year":"2019","unstructured":"Stratos Idreos, Niv Dayan, Wilson Qin, Mali Akmanalp, Sophie Hilgard, Andrew Slavin Ross, James Lennon, Varun Jain, Harshita Gupta, David Li, and Zichen Zhu. 2019. Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR)."},{"key":"e_1_2_1_30_1","unstructured":"Influxdata. 2024. InfluxDB. https:\/\/https:\/\/www.influxdata.com\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2799"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526167"},{"key":"e_1_2_1_33_1","unstructured":"Cockroach Labs. 2024. CockroachDB. https:\/\/github.com\/cockroachdb\/cockroach."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930583.2930595"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654978"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_2_1_38_1","unstructured":"Chen Luo and Michael J Carey. 2019. On performance stability in LSM-based storage systems (extended version). arXiv preprint arXiv:1906.09667 (2019)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430916"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9006240"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00638-1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-023-00734-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.135"},{"key":"e_1_2_1_45_1","unstructured":"Claire Mathieu Carl Staelin Neal E Young and Arman Yousefi. 2014. Bigtable merge compaction. arXiv preprint arXiv:1407.3008 (2014)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_47_1","unstructured":"PingCAP. 2024. TiDB. https:\/\/github.com\/pingcap\/tidb."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389757"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_52_1","first-page":"17","volume-title":"Building Workload-Independent Storage with VT-Trees. In 11th USENIX Conference on File and Storage Technologies (FAST 13)","author":"Shetty Pradeep J","year":"2013","unstructured":"Pradeep J Shetty, Richard P Spillane, Ravikant R Malpani, Binesh Andrews, Justin Seyster, and Erez Zadok. 2013. Building Workload-Independent Storage with VT-Trees. In 11th USENIX Conference on File and Storage Technologies (FAST 13). 17-30."},{"key":"e_1_2_1_53_1","unstructured":"Cloudius Systems. 2024. ScyllaDB. https:\/\/www.scylladb.com\/."},{"key":"e_1_2_1_54_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":"Vin\u00e7on Tobias","year":"2018","unstructured":"Tobias Vin\u00e7on, 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_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654944"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_2_1_57_1","first-page":"71","volume-title":"LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data Items. In 2015 USENIX Annual Technical Conference (USENIX ATC 15)","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 Items. In 2015 USENIX Annual Technical Conference (USENIX ATC 15). 71-82."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407803"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3561261.3561270"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_61_1","first-page":"225","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_62_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_63_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\/pdf\/10.1145\/3725310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:16Z","timestamp":1774983256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725310"],"URL":"https:\/\/doi.org\/10.1145\/3725310","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}