{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:43Z","timestamp":1787017423808,"version":"build-2736575974"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61772212"],"award-info":[{"award-number":["61772212"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"13th USENIX Symposium on Operating Systems Design and Implementation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2019,5,31]]},"abstract":"<jats:p>\n                    Non-volatile memory (NVM) technologies as persistent memory are promising candidates to complement or replace DRAM for building future memory systems, due to having the advantages of high density, low power, and non-volatility. In main memory systems, hashing index structures are fundamental building blocks to provide fast query responses. However, hashing index structures originally designed for dynamic random access memory (DRAM) become inefficient for persistent memory due to new challenges including hardware limitations of NVM and the requirement of data consistency. To address these challenges, this article proposes\n                    <jats:italic>level hashing<\/jats:italic>\n                    , a write-optimized and high-performance hashing index scheme with low-overhead consistency guarantee and cost-efficient resizing. Level hashing provides a sharing-based two-level hash table, which achieves constant-scale worst-case time complexity for search, insertion, deletion, and update operations, and rarely incurs extra NVM writes. To guarantee the consistency with low overhead, level hashing leverages log-free consistency schemes for deletion, insertion, and resizing operations, and an opportunistic log-free scheme for update operation. To cost-efficiently resize this hash table, level hashing leverages an in-place resizing scheme that only needs to rehash 1\/3 of buckets instead of the entire table to expand a hash table and rehash 2\/3 of buckets to shrink a hash table, thus significantly improving the resizing performance and reducing the number of rehashed buckets. Extensive experimental results show that the level hashing speeds up insertions by 1.4\u00d7\u22123.0\u00d7, updates by 1.2\u00d7\u22122.1\u00d7, expanding by over 4.3\u00d7, and shrinking by over 1.4\u00d7 while maintaining high search and deletion performance compared with start-of-the-art hashing schemes.\n                  <\/jats:p>","DOI":"10.1145\/3322096","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T08:38:56Z","timestamp":1561106336000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Level Hashing"],"prefix":"10.1145","volume":"15","author":[{"given":"Pengfei","family":"Zuo","sequence":"first","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics, School of Computer, Huazhong University of Science and Technology, Wuhan, Hubei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Hua","sequence":"additional","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics, School of Computer, Huazhong University of Science and Technology, Wuhan, Hubei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics, School of Computer, Huazhong University of Science and Technology, Wuhan, Hubei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2070830"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463585.2463589"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_5_1","volume-title":"USENIX Annual Technical Conference (USENIX ATC). 281--294","author":"Breslow Alex D."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037721"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR). 21--31","author":"Chen Shimin","year":"2011"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950380"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629589"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2819001.2819002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602261"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592814"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI). 371--384","author":"Fan Bin","year":"2013"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS).","author":"Gao Hui"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.180602"},{"key":"e_1_2_1_20_1","volume-title":"USENIX Annual Technical Conference (USENIX ATC). 1--15","author":"Guerra Jorge","year":"2012"},{"key":"e_1_2_1_21_1","volume-title":"Path Hashing: A Write-friendly Hashing Scheme for Non-volatile Memory Systems.","author":"Hashing Path","year":"2017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_24"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST). 187--200","author":"Hwang Deukyeon","year":"2018"},{"key":"e_1_2_1_24_1","unstructured":"Intel. 2015. Introducing Intel Optane Technology - Bringing 3D XPoint Memory to Storage and Memory Products. Retrieved from https:\/\/newsroom.intel.com\/press-kits\/introducing-intel-optane-technology-bringing-3d-xpoint-memory-to-storage-and-memory-products\/.  Intel. 2015. Introducing Intel Optane Technology - Bringing 3D XPoint Memory to Storage and Memory Products. Retrieved from https:\/\/newsroom.intel.com\/press-kits\/introducing-intel-optane-technology-bringing-3d-xpoint-memory-to-storage-and-memory-products\/."},{"key":"e_1_2_1_25_1","unstructured":"Intel. 2017. Intel Threading Building Blocks. Retrieved from https:\/\/www.threadingbuildingblocks.org\/.  Intel. 2017. Intel Threading Building Blocks. Retrieved from https:\/\/www.threadingbuildingblocks.org\/."},{"key":"e_1_2_1_26_1","unstructured":"Intel. 2018. Intel Architecture Instruction Set Extensions Programming Reference. Retrieved from https:\/\/software.intel.com\/en-us\/isa-extensions.  Intel. 2018. Intel Architecture Instruction Set Extensions Programming Reference. Retrieved from https:\/\/software.intel.com\/en-us\/isa-extensions."},{"key":"e_1_2_1_27_1","unstructured":"Java. 2018. Java HashMap. Retrieved from http:\/\/www.docjar.com\/html\/api\/java\/util\/HashMap.java.html.  Java. 2018. Java HashMap. Retrieved from http:\/\/www.docjar.com\/html\/api\/java\/util\/HashMap.java.html."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872392"},{"key":"e_1_2_1_29_1","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co. Inc. Redwood City CA.   Donald E. Knuth. 1998. The Art of Computer Programming Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co. Inc. Redwood City CA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540748"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2015.7208288"},{"key":"e_1_2_1_32_1","volume-title":"Proceeding of the USENIX Conference on File and Storage Technologies (FAST). 257--270","author":"Lee Se Kwon"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750416"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_1_35_1","volume-title":"Libcuckoo: A high-performance, concurrent hash table.","year":"2018"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD). 21--35","author":"Lim Hyeontaek"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037714"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611495"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087582"},{"key":"e_1_2_1_40_1","unstructured":"Memcached. 2018. Memcached. Retrieved from https:\/\/memcached.org\/.  Memcached. 2018. Memcached. Retrieved from https:\/\/memcached.org\/."},{"key":"e_1_2_1_41_1","volume-title":"IEEE International Electron Devices Meeting (IEDM).","author":"Mueller W."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151018"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915251"},{"key":"e_1_2_1_44_1","volume-title":"Quartz: A DRAM-based performance emulator for NVM.","author":"Packard Hewlett","year":"2015"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740481"},{"key":"e_1_2_1_46_1","unstructured":"Nick Piggin. 2008. ddds: \u201cdynamic dynamic data structure\u201d algorithm for adaptive dcache hash table sizing. Linux kernel mailing list. Retrieved from https:\/\/lwn.net\/Articles\/302132\/.  Nick Piggin. 2008. ddds: \u201cdynamic dynamic data structure\u201d algorithm for adaptive dcache hash table sizing. Linux kernel mailing list. Retrieved from https:\/\/lwn.net\/Articles\/302132\/."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90040-X"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the Annual International Symposium on Computer Architecture (ISCA). 24--33","author":"Qureshi Moinuddin K."},{"key":"e_1_2_1_49_1","unstructured":"Redis. 2018. Redis. Retrieved from https:\/\/redis.io\/.  Redis. 2018. Redis. Retrieved from https:\/\/redis.io\/."},{"key":"e_1_2_1_50_1","volume-title":"Proceeding of the USENIX Conference on File and Storage Technologies (FAST). 1--16","author":"Rumble Stephen M."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 91--104","author":"Seo Jihye"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147958"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 96--107","author":"Shun Julian"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC). 553--565","author":"Sun Yuanyuan","year":"2017"},{"key":"e_1_2_1_55_1","volume-title":"International Symposium on Computer Architecture (ISCA). 51--62","author":"Thoziyoor Shyamkumar"},{"key":"e_1_2_1_56_1","volume-title":"USENIX Annual Technical Conference (USENIX ATC). 1--14","author":"Triplett Josh","year":"2011"},{"key":"e_1_2_1_57_1","volume-title":"Proceeding of the USENIX Conference on File and Storage Technologies (FAST). 5.","author":"Venkataraman Shivaram"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814576.2814806"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 91--103","author":"Volos Haris"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2070050"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC). 349--362","author":"Xia Fei","year":"2017"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 323--338","author":"Xu Jian","year":"2016"},{"key":"e_1_2_1_63_1","volume-title":"Proceeding of the USENIX Conference on File and Storage Technologies (FAST). 167--181","author":"Yang Jun","year":"2015"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735511"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809984"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555759"},{"key":"e_1_2_1_67_1","volume-title":"Proceedings of the 33rd International Conference on Massive Storage Systems and Technology (MSST). 1--10","author":"Zuo Pengfei","year":"2017"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2782251"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 461--476","author":"Zuo Pengfei","year":"2018"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322096","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:49:04Z","timestamp":1750254544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322096"}},"subtitle":["A High-performance and Flexible-resizing Persistent Hashing Index Structure"],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,5,31]]}},"alternative-id":["10.1145\/3322096"],"URL":"https:\/\/doi.org\/10.1145\/3322096","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}