{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T19:18:51Z","timestamp":1774120731277,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T00:00:00Z","timestamp":1687132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Samsung, Los Alamos National Lab and NSF","award":["1439722, 1823403, 2203033"],"award-info":[{"award-number":["1439722, 1823403, 2203033"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>Key\u2013value (KV) software has proven useful to a wide variety of applications including analytics, time-series databases, and distributed file systems. To satisfy the requirements of diverse workloads, KV stores have been carefully tailored to best match the performance characteristics of underlying solid-state block devices. Emerging KV storage device is a promising technology for both simplifying the KV software stack and improving the performance of persistent storage-based applications. However, while providing fast, predictable put and get operations, existing KV storage devices do not natively support range queries that are critical to all three types of applications described above.<\/jats:p>\n          <jats:p>In this article, we present KVRangeDB, a software layer that enables processing range queries for existing hash-based KV solid-state disks (KVSSDs). As an effort to adapt to the performance characteristics of emerging KVSSDs, KVRangeDB implements log-structured merge tree key index that reduces compaction I\/O, merges keys when possible, and provides separate caches for indexes and values. We evaluated the KVRangeDB under a set of representative workloads, and compared its performance with two existing database solutions: a Rocksdb variant ported to work with the KVSSD, and Wisckey, a key\u2013value database that is carefully tuned for conventional block devices. On filesystem aging workloads, KVRangeDB outperforms Wisckey by 23.7\u00d7 in terms of throughput and reduce CPU usage and external write amplifications by 14.3\u00d7 and 9.8\u00d7, respectively.<\/jats:p>","DOI":"10.1145\/3582013","type":"journal-article","created":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T11:46:21Z","timestamp":1674301581000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["KVRangeDB: Range Queries for a Hash-based Key\u2013Value Device"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1753-3914","authenticated-orcid":false,"given":"Mian","family":"Qin","sequence":"first","affiliation":[{"name":"Texas A&amp;M University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7457-9874","authenticated-orcid":false,"given":"Qing","family":"Zheng","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1604-1395","authenticated-orcid":false,"given":"Jason","family":"Lee","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9299-2654","authenticated-orcid":false,"given":"Bradley","family":"Settlemyer","sequence":"additional","affiliation":[{"name":"Nvidia, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8789-8495","authenticated-orcid":false,"given":"Fei","family":"Wen","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4625-8819","authenticated-orcid":false,"given":"Narasimha","family":"Reddy","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7120-7189","authenticated-orcid":false,"given":"Paul","family":"Gratz","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,19]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2020. NVMe Command Set Specifications. https:\/\/nvmexpress.org\/."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359656"},{"key":"e_1_3_1_4_2","unstructured":"Apache. 2013. HBase. Retrieved from https:\/\/hbase.apache.org\/."},{"key":"e_1_3_1_5_2","unstructured":"Jens Axboe. 2020. Key Value Storage API Specification\u2014SNIA. Retrieved from https:\/\/www.snia.org\/keyvalue."},{"key":"e_1_3_1_6_2","unstructured":"Matias Bj\u00f8rling. 2020. Zone Append: A new way of writing to zoned storage. In Linux Storage and Filesystems Conference (VAULT\u201920) . USENIX Association Santa Clara CA."},{"key":"e_1_3_1_7_2","first-page":"359","volume-title":"Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST 17)","author":"Bj\u00f8rling Matias","year":"2017","unstructured":"Matias Bj\u00f8rling, Javier Gonzalez, and Philippe Bonnet. 2017. LightNVM: The Linux open-channel SSD subsystem. In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST 17). USENIX Association, Berkeley, CA, 359\u2013374. https:\/\/www.usenix.org\/conference\/fast17\/technical-sessions\/presentation\/bjorling."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_1_9_2","first-page":"49","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201913)","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. 2013. TAO: Facebook\u2019s distributed data store for the social graph. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201913). USENIX, Berkeley, CA, 49\u201360. https:\/\/www.usenix.org\/conference\/atc13\/technicalsessions\/presentation\/bronson."},{"key":"e_1_3_1_10_2","volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Chang Fay","year":"2006","unstructured":"Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2006. Bigtable: A distributed storage system for structured data. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906). USENIX Association, Berkeley, CA."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378515"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_1_13_2","article-title":"LevelDB: Google\u2019s fast key value store library","author":"Dean J.","year":"2017","unstructured":"J. Dean and S. Ghemawat. 2017. LevelDB: Google\u2019s fast key value store library. Github Release 1.2.","journal-title":"Github Release 1.2"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_3_1_15_2","unstructured":"Facebook. 2015. Rocksdb. Retrieved from https:\/\/rocksdb.org\/."},{"key":"e_1_3_1_16_2","first-page":"173","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201920)","author":"Im Junsu","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 USENIX Annual Technical Conference (USENIX ATC\u201920). USENIX Association, Berkeley, CA, 173\u2013187. https:\/\/www.usenix.org\/conference\/atc20\/presentation\/im."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.15"},{"key":"e_1_3_1_18_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, Berkeley, CA, 191\u2013205. https:\/\/www.usenix.org\/conference\/fast19\/presentation\/kaiyrakhmet."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319647.3325831"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/3357062.3357064"},{"key":"e_1_3_1_21_2","first-page":"427","volume-title":"Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201918)","author":"Klimovic Ana","year":"2018","unstructured":"Ana Klimovic, Yawen Wang, Patrick Stuedi, Animesh Trivedi, Jonas Pfefferle, and Christos Kozyrakis. 2018. Pocket: Elastic ephemeral storage for serverless analytics. In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201918). USENIX Association, Berkeley, CA, 427\u2013444. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/klimovic."},{"key":"e_1_3_1_22_2","first-page":"75","volume-title":"Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201921)","author":"Koo Jinhyung","year":"2021","unstructured":"Jinhyung Koo, Junsu Im, Jooyoung Song, Juhyung Park, Eunji Lee, Bryan S. Kim, and Sungjin Lee. 2021. Modernizing file system through in-storage indexing. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201921). USENIX Association, Berkeley, CA, 75\u201392. https:\/\/www.usenix.org\/conference\/osdi21\/presentation\/koo."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132756"},{"key":"e_1_3_1_24_2","first-page":"133","volume-title":"Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST 16)","author":"Lu Lanyue","year":"2016","unstructured":"Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2016. WiscKey: Separating keys from values in SSD-conscious storage. In Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST 16). USENIX Association, Berkeley, CA, 133\u2013148. https:\/\/www.usenix.org\/conference\/fast16\/technical-sessions\/presentation\/lu."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_3_1_26_2","first-page":"207","volume-title":"Proceedings of the 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 USENIX Annual Technical Conference (USENIX ATC\u201915). USENIX Association, Berkeley, CA, 207\u2013219. https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/marmol."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_3_1_28_2","first-page":"217","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST\u201921)","author":"Pan Satadru","year":"2021","unstructured":"Satadru Pan, Theano Stavrinos, Yunqiao Zhang, Atul Sikaria, Pavel Zakharov, Abhinav Sharma, Shiva Shankar P., Mike Shuey, Richard Wareing, Monika Gangapuram, Guanglei Cao, Christian Preseau, Pratap Singh, Kestutis Patiejunas, J. R. Tipton, Ethan Katz-Bassett, and Wyatt Lloyd. 2021. Facebook\u2019s tectonic filesystem: Efficiency from exascale. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST\u201921). USENIX Association, Berkeley, CA, 217\u2013231. https:\/\/www.usenix.org\/conference\/fast21\/presentation\/pan."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137659"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386721"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3456727.3463781"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_3_1_33_2","first-page":"145","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201913)","author":"Ren Kai","year":"2013","unstructured":"Kai Ren and Garth Gibson. 2013. TABLEFS: Enhancing metadata efficiency in the local file system. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201913). USENIX Association, Berkeley, CA, 145\u2013156. https:\/\/www.usenix.org\/conference\/atc13\/technical-sessions\/presentation\/ren."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.25"},{"key":"e_1_3_1_35_2","unstructured":"CMU\/PDL File Systems. 2013. Fast and Efficient Filesystem Metadata through LSM-Trees. Retrieved from https:\/\/github.com\/pdlfs\/tablefs\/."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_3_1_37_2","first-page":"117","volume-title":"Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920)","author":"Wei Xingda","year":"2020","unstructured":"Xingda Wei, Rong Chen, and Haibo Chen. 2020. Fast RDMA-based ordered key-value store using remote learned cache. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920). USENIX Association, Berkeley, CA, 117\u2013135. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/wei."},{"key":"e_1_3_1_38_2","first-page":"307","volume-title":"Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Weil Sage A.","year":"2006","unstructured":"Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos Maltzahn. 2006. Ceph: A scalable, high-performance distributed file system. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI\u201906). USENIX Association, Berkeley, CA, 307\u2013320. http:\/\/dl.acm.org\/citation.cfm?id=1298455.1298485."},{"key":"e_1_3_1_39_2","first-page":"191","volume-title":"Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920)","author":"Yang Juncheng","year":"2020","unstructured":"Juncheng Yang, Yao Yue, and K. V. Rashmi. 2020. A large scale analysis of hundreds of in-memory cache clusters at Twitter. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920). USENIX Association, Berkeley, CA, 191\u2013208. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/yang."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_3_1_41_2","volume-title":"Scaling Embedded In-Situ Indexing with DeltaFS","author":"Zheng Qing","year":"2018","unstructured":"Qing Zheng, Charles D. Cranor, Danhao Guo, Gregory R. Ganger, George Amvrosiadis, Garth A. Gibson, Bradley W. Settlemyer, Gary Grider, and Fan Guo. 2018. Scaling Embedded In-Situ Indexing with DeltaFS. IEEE Press."},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386712"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582013","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:44Z","timestamp":1750178804000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,19]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3582013"],"URL":"https:\/\/doi.org\/10.1145\/3582013","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,19]]},"assertion":[{"value":"2022-06-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}