{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:33:19Z","timestamp":1753439599347,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T00:00:00Z","timestamp":1565654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61772484, 61772486"],"award-info":[{"award-number":["61772484, 61772486"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Grants Council of Hong Kong","award":["CRF C7036-15G"],"award-info":[{"award-number":["CRF C7036-15G"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>\n            Persistent key-value (KV) stores mostly build on the Log-Structured Merge (LSM) tree for high write performance, yet the LSM-tree suffers from the inherently high I\/O amplification. KV separation mitigates I\/O amplification by storing only keys in the LSM-tree and values in separate storage. However, the current KV separation design remains inefficient under update-intensive workloads due to its high garbage collection (GC) overhead in value storage. We propose HashKV, which aims for high update performance atop KV separation under update-intensive workloads. HashKV uses\n            <jats:italic>hash-based data grouping<\/jats:italic>\n            , which deterministically maps values to storage space to make both updates and GC efficient. We further relax the restriction of such deterministic mappings via simple but useful design extensions. We extensively evaluate various design aspects of HashKV. We show that HashKV achieves 4.6\u00d7 update throughput and 53.4% less write traffic compared to the current KV separation design. In addition, we demonstrate that we can integrate the design of HashKV with state-of-the-art KV stores and improve their respective performance.\n          <\/jats:p>","DOI":"10.1145\/3340287","type":"journal-article","created":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T14:41:50Z","timestamp":1565707310000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Enabling Efficient Updates in KV Storage via Hashing"],"prefix":"10.1145","volume":"15","author":[{"given":"Yongkun","family":"Li","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Hefei, Anhui, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4466-8534","authenticated-orcid":false,"given":"Helen H. W.","family":"Chan","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4501-4364","authenticated-orcid":false,"given":"Patrick P. C.","family":"Lee","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]},{"given":"Yinlong","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, Anhui, China"}]}],"member":"320","published-online":{"date-parts":[[2019,8,13]]},"reference":[{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201908)","year":"2008","author":"Agrawal Nitin","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/2254756.2254766"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201917)","year":"2017","author":"Balmau Oana","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)","year":"2010","author":"Beaver Doug","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201918)","year":"2018","author":"Chan Helen H. W.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Chang Fay","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201917)","year":"2017","author":"Chen Yu Lin","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1807128.1807152"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.14778\/1920841.1921015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1989323.1989327"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1294261.1294281"},{"unstructured":"Dgraph Labs. 2019. BadgerDB. Retrieved from https:\/\/github.com\/dgraph-io\/badger\/.  Dgraph Labs. 2019. BadgerDB. Retrieved from https:\/\/github.com\/dgraph-io\/badger\/.","key":"e_1_2_1_12_1"},{"unstructured":"Robert Escriva. 2019. HyperLevelDB. Retrieved from https:\/\/github.com\/rescrv\/HyperLevelDB\/.  Robert Escriva. 2019. HyperLevelDB. Retrieved from https:\/\/github.com\/rescrv\/HyperLevelDB\/.","key":"e_1_2_1_13_1"},{"unstructured":"Facebook. 2019. RocksDB. Retrieved from https:\/\/rocksdb.org.  Facebook. 2019. RocksDB. Retrieved from https:\/\/rocksdb.org.","key":"e_1_2_1_14_1"},{"unstructured":"Facebook. 2019. RocksDB Features that are not in LevelDB. Retrieved from https:\/\/github.com\/facebook\/rocksdb\/wiki\/Features-Not-in-LevelDB.  Facebook. 2019. RocksDB Features that are not in LevelDB. Retrieved from https:\/\/github.com\/facebook\/rocksdb\/wiki\/Features-Not-in-LevelDB.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201913)","year":"2013","author":"Fan Bin","key":"e_1_2_1_16_1"},{"volume-title":"Distributed caching with memcached. Linux J","year":"2004","author":"Fitzpatrick Brad","key":"e_1_2_1_17_1"},{"unstructured":"S. Ghemawat and J. Dean. 2019. LevelDB. Retrieved from https:\/\/leveldb.org.  S. Ghemawat and J. Dean. 2019. LevelDB. Retrieved from https:\/\/leveldb.org.","key":"e_1_2_1_18_1"},{"unstructured":"Nigel Griffiths. 2019. nmon for Linux. Retrieved from http:\/\/nmon.sourceforge.net\/.  Nigel Griffiths. 2019. nmon for Linux. Retrieved from http:\/\/nmon.sourceforge.net\/.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1138041.1138043"},{"volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908)","author":"Kavalanekar S.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 31st Symposium on Mass Storage Systems and Technologies (MSST\u201915)","author":"Lai C.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/2485732.2485745"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/2668930.2688036"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/2043556.2043558"},{"volume-title":"Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201914)","year":"2014","author":"Lim Hyeontaek","key":"e_1_2_1_26_1"},{"unstructured":"Linux Raid Wiki. 2019. RAID setup. Retrieved from https:\/\/raid.wiki.kernel.org\/index.php\/RAID_setup.  Linux Raid Wiki. 2019. RAID setup. Retrieved from https:\/\/raid.wiki.kernel.org\/index.php\/RAID_setup.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/3033273"},{"volume-title":"Carey","year":"2018","author":"Luo Chen","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/1480439.1480440"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201915)","year":"2015","author":"Marmol Leonardo","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/268998.266700"},{"volume-title":"Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST\u201912)","year":"2012","author":"Min Changwoo","key":"e_1_2_1_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/2482626.2482663"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1007\/s002360050048"},{"volume-title":"Oracle Berkeley DB","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201916)","year":"2016","author":"Papagiannis Anastasios","key":"e_1_2_1_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/3132747.3132765"},{"volume-title":"Retrieved","year":"2019","key":"e_1_2_1_39_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/146941.146943"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.5555\/2591305.2591307"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/2213836.2213862"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/3203410"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.5555\/2591272.2591275"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/3162615"},{"volume-title":"Retrieved","year":"2019","key":"e_1_2_1_46_1"},{"unstructured":"TPC. Retrieved in June 2019. TPC-C is an On-Line Transaction Processing Benchmark. Retrieved from http:\/\/www.tpc.org\/tpcc\/.  TPC. Retrieved in June 2019. TPC-C is an On-Line Transaction Processing Benchmark. Retrieved from http:\/\/www.tpc.org\/tpcc\/.","key":"e_1_2_1_47_1"},{"volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201906)","year":"2006","author":"Weil Sage A.","key":"e_1_2_1_48_1"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201915)","year":"2015","author":"Wu Xingbo","key":"e_1_2_1_49_1"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201917)","year":"2017","author":"Xia Fei","key":"e_1_2_1_50_1"},{"volume-title":"Proceedings of the 33rd International Conference on Massive Storage Systems and Technology (MSST\u201917)","year":"2017","author":"Yao Ting","key":"e_1_2_1_51_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1109\/TPDS.2016.2609912"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1145\/3129900"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340287","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340287"}},"subtitle":["Design and Performance Evaluation"],"short-title":[],"issued":{"date-parts":[[2019,8,13]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3340287"],"URL":"https:\/\/doi.org\/10.1145\/3340287","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2019,8,13]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}