{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T17:09:18Z","timestamp":1783184958157,"version":"3.54.6"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T00:00:00Z","timestamp":1706572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Institute of Information & Communications Technology Planning & Evaluation","award":["2021-0-00853"],"award-info":[{"award-number":["2021-0-00853"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>\n            Modern log-structured merge (LSM) tree-based key-value stores are widely used to process update-heavy workloads effectively as the LSM tree sequentializes write requests to a storage device to maximize storage performance. However, this append-only approach leaves many outdated copies of frequently updated key-value pairs, which need to be routinely cleaned up through the operation called\n            <jats:italic>compaction<\/jats:italic>\n            . When the system load is modest, compaction happens in background. However, at a high system load, it can quickly become the major performance bottleneck. To address this compaction bottleneck and further improve the write throughput of LSM tree-based key-value stores, we propose LAB-DB, which augments the existing LSM tree with a pair of B\n            <jats:sup>+<\/jats:sup>\n            trees on byte-addressable nonvolatile memory (NVM). The auxiliary B\n            <jats:sup>+<\/jats:sup>\n            trees on NVM reduce both compaction frequency and compaction time, hence leading to lower compaction overhead for writes and fewer storage accesses for reads. According to our evaluation of LAB-DB on RocksDB with YCSB benchmarks, LAB-DB achieves 94% and 67% speedups on two write-intensive workloads (Workload A and F), and also a 43% geomean speedup on read-intensive YCSB Workload B, C, D, and E. This performance gain comes with a low cost of NVM whose size is just 0.6% of the entire dataset to demonstrate the scalability of LAB-DB with an ever increasing volume of future datasets.\n          <\/jats:p>","DOI":"10.1145\/3633475","type":"journal-article","created":{"date-parts":[[2023,12,2]],"date-time":"2023-12-02T12:02:37Z","timestamp":1701518557000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["An LSM Tree Augmented with B\n            <sup>+<\/sup>\n            Tree on Nonvolatile Memory"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5716-9948","authenticated-orcid":false,"given":"Donguk","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University and Samsung Electronics, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4080-0611","authenticated-orcid":false,"given":"Jongsung","family":"Lee","sequence":"additional","affiliation":[{"name":"Seoul National University and Samsung Electronics, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2290-8931","authenticated-orcid":false,"given":"Keun Soo","family":"Lim","sequence":"additional","affiliation":[{"name":"Seoul National University, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7452-3030","authenticated-orcid":false,"given":"Jun","family":"Heo","sequence":"additional","affiliation":[{"name":"Seoul National University, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2669-6849","authenticated-orcid":false,"given":"Tae Jun","family":"Ham","sequence":"additional","affiliation":[{"name":"Seoul National University, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4266-4919","authenticated-orcid":false,"given":"Jae W.","family":"Lee","sequence":"additional","affiliation":[{"name":"Seoul National University, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,30]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Apache. 2012. Cassandra. Retrieved December 16 2023 from http:\/\/https:\/\/cassandra.apache.org\/"},{"key":"e_1_3_1_3_2","unstructured":"Apache. 2012. HBase. Retrieved December 16 2023 from http:\/\/hbase.apache.org\/"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00043"},{"key":"e_1_3_1_5_2","first-page":"363","volume-title":"Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201917)","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 Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201917). USENIX Association, 363\u2013375. Retrieved from https:\/\/www.usenix.org\/conference\/atc17\/technical-sessions\/presentation\/balmau"},{"key":"e_1_3_1_6_2","first-page":"753","volume-title":"Proceedings of the 2019 USENIX Annual Technical Conference (USENIX ATC\u201919)","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 Proceedings of the 2019 USENIX Annual Technical Conference (USENIX ATC\u201919). USENIX Association, Renton, WA, 753\u2013766. Retrieved from https:\/\/www.usenix.org\/conference\/atc19\/presentation\/balmau"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378504"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993843"},{"key":"e_1_3_1_9_2","unstructured":"C. Cantalupo V. Venkatesan J. Hammond K. Czurlyo and S. Hammond. 2015. Memkind Library. Retrieved December 16 2023 from https:\/\/github.com\/memkind\/memkind"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1811.10000"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_3_1_12_2","first-page":"17","volume-title":"Proceedings of the19th USENIX Conference on File and Storage Technologies (FAST\u201921)","author":"Chen Hao","year":"2021","unstructured":"Hao Chen, Chaoyi Ruan, Cheng Li, Xiaosong Ma, and Yinlong Xu. 2021. SpanDB: A fast, cost-effective LSM-tree based KV store on hybrid storage. In Proceedings of the19th USENIX Conference on File and Storage Technologies (FAST\u201921). USENIX Association, 17\u201332. Retrieved from https:\/\/www.usenix.org\/conference\/fast21\/presentation\/chen-hao"},{"key":"e_1_3_1_13_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. SplinterDB: Closing the bandwidth gap for NVMe key-value stores. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). USENIX Association, 49\u201363. Retrieved from https:\/\/www.usenix.org\/conference\/atc20\/presentation\/conway"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_1_15_2","first-page":"155","volume-title":"Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation","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 Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation. USENIX Association, 155\u2013171. Retrieved from https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/dai"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2819001.2819002"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989327"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190524"},{"key":"e_1_3_1_23_2","unstructured":"Facebook. 2017. RocksDB. Retrieved December 16 2023 from https:\/\/rocksdb.org\/"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_3_1_25_2","unstructured":"Google. 2014. LevelDB. Retrieved December 16 2023 from https:\/\/github.com\/google\/leveldb"},{"key":"e_1_3_1_26_2","first-page":"967","volume-title":"Proceedings of the 2018 USENIX Annual Technical Conference (USENIX ATC\u201918)","author":"Huang Yihe","year":"2018","unstructured":"Yihe Huang, Matej Pavlovic, Virendra Marathe, Margo Seltzer, Tim Harris, and Steve Byan. 2018. Closing the performance gap between volatile and persistent key-value stores using cross-referencing logs. In Proceedings of the 2018 USENIX Annual Technical Conference (USENIX ATC\u201918). 967\u2013979. Retrieved from https:\/\/www.usenix.org\/conference\/atc18\/presentation\/huang"},{"key":"e_1_3_1_27_2","first-page":"187","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918)","author":"Hwang Deukyeon","year":"2018","unstructured":"Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam. 2018. Endurable transient inconsistency in byte-addressable persistent B+-Tree. In Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918). USENIX Association, Oakland, CA, 187\u2013200. Retrieved from https:\/\/www.usenix.org\/conference\/fast18\/presentation\/hwang"},{"key":"e_1_3_1_28_2","first-page":"173","volume-title":"Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920)","year":"2020","unstructured":"Junsu Im, Jinwook Bae, Chanwoo Chung, Arvind, and Sungjin Lee. 2020. PinK: High-speed in-storage key-value store with bounded tails. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). 173\u2013187. Retrieved from https:\/\/www.usenix.org\/conference\/atc20\/presentation\/im"},{"key":"e_1_3_1_29_2","unstructured":"Intel. 2019. pmemkv. Retrieved December 16 2023 from https:\/\/github.com\/pmem\/pmemkv"},{"key":"e_1_3_1_30_2","unstructured":"Intel. 2019. Technology Brief: Intel Optane Technology. Retrieved October 12 2020 from https:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/technology-briefs\/what-is-optane-technology-brief.pdf"},{"key":"e_1_3_1_31_2","volume-title":"Basic Performance Measurements of the Intel Optane DC Persistent Memory Module","author":"Izraelevitz Joseph","year":"2019","unstructured":"Joseph Izraelevitz, Jian Yang, Lu Zhang, Juno Kim, Xiao Liu, Amirsaman Memaripour, Yun Joon Soh, Zixuan Wang, Yi Xu, Subramanya R. Dulloor, Jishen Zhao, and Steven Swanson. 2019. Basic Performance Measurements of the Intel Optane DC Persistent Memory Module. Technical Report. University of California, San Diego. Retrieved from http:\/\/arxiv.org\/abs\/1903.05714"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.15"},{"key":"e_1_3_1_33_2","first-page":"191","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Kaiyrakhmet Olzhas","year":"2019","unstructured":"Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H. Noh, and Young ri Choi. 2019. SLM-DB: Single-level key-value store with persistent memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919). USENIX Association, Boston, MA, 191\u2013205. Retrieved from https:\/\/www.usenix.org\/conference\/fast19\/presentation\/kaiyrakhmet"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277450"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126943"},{"key":"e_1_3_1_36_2","unstructured":"Redis Labs. 2009. Redis. Retrieved December 16 2023 from https:\/\/github.com\/redis\/redis"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359628"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66917-5_22"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3387902.3392621"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043558"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033273"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_1_43_2","first-page":"207","volume-title":"Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC\u201915)","author":"Marmol Leonardo","year":"2015","unstructured":"Leonardo Marmol, Swaminathan Sundararaman, Nisha Talagala, and Raju Rangaswami. 2015. NVMKV: A scalable, lightweight, FTL-aware key-value store. In Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC\u201915). 207\u2013219. Retrieved from https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/marmol"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-016-0472-z"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_3_1_48_2","unstructured":"Jeff Dean Sanjay Ghemawat. 2019. HyperLevelDB. Retrieved from https:\/\/github.com\/rescrv\/HyperLevelDB"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00113"},{"key":"e_1_3_1_51_2","first-page":"61","volume-title":"Proceedings of the FAST","year":"2011","unstructured":"Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and durable data structures for non-volatile byte-addressable memory. In Proceedings of the FAST. 61\u201375. Retrieved from https:\/\/www.usenix.org\/conference\/fast11\/consistent-and-durable-data-structures-non-volatile-byte-addressable-memory"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_3_1_53_2","first-page":"71","volume-title":"Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC\u201915)","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 Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC\u201915). USENIX Association, Santa Clara, CA, 71\u201382. Retrieved from https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/wu"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472883.3487012"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139922"},{"key":"e_1_3_1_56_2","first-page":"17","volume-title":"Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920)","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 matrix container in NVM. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC\u201920). USENIX Association, 17\u201331. Retrieved from https:\/\/www.usenix.org\/conference\/atc20\/presentation\/yao"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00063"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453300"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386713"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3633475","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3633475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:01Z","timestamp":1750287241000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3633475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,30]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1145\/3633475"],"URL":"https:\/\/doi.org\/10.1145\/3633475","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,30]]},"assertion":[{"value":"2022-11-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-28","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}