{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:14:08Z","timestamp":1767183248621,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"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":["62125202"],"award-info":[{"award-number":["62125202"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Laboratory of Information Storage System, Ministry of Education of China"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>\n            Persistent memory (PM) provides large-scale non-volatile memory (NVM) with DRAM-comparable performance. The non-volatility and other unique characteristics of PM architecture bring new opportunities and challenges for the efficient storage system design. For example, some recent crash-consistent and write-friendly hashing schemes are proposed to provide fast queries for PM systems. However, existing PM hashing indexes suffer from the concurrency bottleneck due to the blocking resizing and expensive lock-based concurrency control for queries. Moreover, the lack of PM awareness and systematical design further increases the query latency. To address the concurrency bottleneck of lock contention in PM hashing, we propose clevel hashing, a lock-free concurrent level hashing scheme that provides non-blocking resizing via background threads and lock-free search\/insertion\/update\/deletion using atomic primitives to enable high concurrency for PM hashing. By exploiting the PM characteristics, we present a holistic approach to building clevel hashing for high throughput and low tail latency via the PM-aware index\/allocator co-design. The proposed\n            <jats:italic>volatile announcement array<\/jats:italic>\n            with a helping mechanism coordinates lock-free insertions and guarantees a strong consistency model. Our experiments using real-world YCSB workloads on Intel Optane DC PMM show that clevel hashing, respectively, achieves up to 5.7\u00d7 and 1.6\u00d7 higher throughput than state-of-the-art P-CLHT and Dash while guaranteeing low tail latency, e.g., 1.9\u00d7\u20137.2\u00d7 speedup for the p99 latency with the insert-only workload.\n          <\/jats:p>","DOI":"10.1145\/3561651","type":"journal-article","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T11:51:59Z","timestamp":1662465119000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Lock-Free High-performance Hashing for Persistent Memory via PM-aware Holistic Optimization"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9020-3693","authenticated-orcid":false,"given":"Zhangyu","family":"Chen","sequence":"first","affiliation":[{"name":"WNLO, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7730-3796","authenticated-orcid":false,"given":"Yu","family":"Hua","sequence":"additional","affiliation":[{"name":"WNLO, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4927-4398","authenticated-orcid":false,"given":"Luochangqi","family":"Ding","sequence":"additional","affiliation":[{"name":"WNLO, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7588-0140","authenticated-orcid":false,"given":"Bo","family":"Ding","sequence":"additional","affiliation":[{"name":"WNLO, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9982-5130","authenticated-orcid":false,"given":"Pengfei","family":"Zuo","sequence":"additional","affiliation":[{"name":"WNLO, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5252-3442","authenticated-orcid":false,"given":"Xue","family":"Liu","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Intel. 2022. eADR: New Opportunities for Persistent Memory Applications. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/articles\/technical\/eadr-new-opportunities-for-persistent-memory-applications.html."},{"key":"e_1_3_2_3_2","unstructured":"Intel. 2022. Intel Optane Persistent Memory 200 Series Brief. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/products\/docs\/memory-storage\/optane-persistent-memory\/optane-persistent-memory-200-series-brief.html."},{"key":"e_1_3_2_4_2","unstructured":"Intel. 2022. Intel\u00aeArchitecture Instruction Set Extensions Programming Reference. Retrieved from https:\/\/www.intel.com\/content\/dam\/develop\/external\/us\/en\/documents\/architecture-instruction-set-extensions-programming-reference.pdf."},{"key":"e_1_3_2_5_2","unstructured":"Intel. 2022. Intel\u00aeOptane\u2122DC persistent memory. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/products\/details\/memory-storage\/optane-dc-persistent-memory.html."},{"key":"e_1_3_2_6_2","unstructured":"Intel. 2022. Intel\u00aeThreading Building Blocks. Retrieved from https:\/\/github.com\/intel\/tbb."},{"key":"e_1_3_2_7_2","unstructured":"Intel. 2022. IPMCTL User Guide. Retrieved from https:\/\/docs.pmem.io\/ipmctl-user-guide\/."},{"key":"e_1_3_2_8_2","unstructured":"Brad Fitzpatrick. 2022. Memcached. Retrieved from https:\/\/memcached.org\/."},{"key":"e_1_3_2_9_2","unstructured":"Linux. 2022. perf: Linux profiling with performance counter. Retrieved from https:\/\/perf.wiki.kernel.org\/index.php\/Main_Page."},{"key":"e_1_3_2_10_2","unstructured":"Intel. 2022. Persistent Memory Development Kit. Retrieved from http:\/\/pmem.io\/."},{"key":"e_1_3_2_11_2","unstructured":"Intel. 2022. pmemkv. Retrieved from http:\/\/pmem.io\/pmemkv\/index.html."},{"key":"e_1_3_2_12_2","unstructured":"Redis Ltd. 2022. Redis. Retrieved from https:\/\/redis.io\/."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3451342"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3164147"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037721"},{"key":"e_1_3_2_17_2","first-page":"799","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"Chen Zhangyu","year":"2020","unstructured":"Zhangyu Chen, Yu Hua, Bo Ding, and Pengfei Zuo. 2020. Lock-free concurrent level hashing for persistent memory. In USENIX Annual Technical Conference (USENIX ATC). USENIX, 799\u2013812."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2512899"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/1807128.1807152","volume-title":"1st ACM Symposium on Cloud Computing (SoCC)","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In 1st ACM Symposium on Cloud Computing (SoCC). ACM, 143\u2013154."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507743"},{"key":"e_1_3_2_21_2","first-page":"373","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"David Tudor","year":"2018","unstructured":"Tudor David, Aleksandar Dragojevic, Rachid Guerraoui, and Igor Zablotchi. 2018. Log-free concurrent data structures. In USENIX Annual Technical Conference (USENIX ATC). USENIX, 373\u2013386."},{"key":"e_1_3_2_22_2","first-page":"371","volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI)","author":"Fan Bin","year":"2013","unstructured":"Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and concurrent MemCache with dumber caching and smarter hashing. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI). USENIX, 371\u2013384."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9491-y"},{"key":"e_1_3_2_24_2","first-page":"111","volume-title":"30th on Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Fatourou Panagiota","year":"2018","unstructured":"Panagiota Fatourou, Nikolaos D. Kallimanis, and Thomas Ropars. 2018. An efficient wait-free resizable hash table. In 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 111\u2013120."},{"key":"e_1_3_2_25_2","first-page":"100","volume-title":"ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP)","author":"Fu Xinwei","year":"2021","unstructured":"Xinwei Fu, Wook-Hee Kim, Ajay Paddayuru Shreepathi, Mohannad Ismail, Sunny Wadkar, Dongyoon Lee, and Changwoo Min. 2021. Witcher: Systematic crash consistency testing for non-volatile memory key-value stores. In ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP). ACM, 100\u2013115."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436921"},{"key":"e_1_3_2_27_2","first-page":"300","volume-title":"15th International Symposium on Distributed Computing (DISC)","author":"Harris Timothy L.","year":"2001","unstructured":"Timothy L. Harris. 2001. A pragmatic implementation of non-blocking linked-lists. In 15th International Symposium on Distributed Computing (DISC). Springer, 300\u2013314."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_29_2","first-page":"187","volume-title":"16th USENIX Conference on File and Storage Technologies (FAST)","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 16th USENIX Conference on File and Storage Technologies (FAST). USENIX, 187\u2013200."},{"key":"e_1_3_2_30_2","first-page":"313","volume-title":"30th International Symposium on Distributed Computing (DISC)","author":"Izraelevitz Joseph","year":"2016","unstructured":"Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 2016. Linearizability of persistent memory objects under a full-system-crash failure model. In 30th International Symposium on Distributed Computing (DISC). Springer, 313\u2013327."},{"key":"e_1_3_2_31_2","article-title":"Basic performance measurements of the Intel Optane DC persistent memory module","volume":"1903","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. CoRR abs\/1903.05714 (2019).","journal-title":"CoRR"},{"key":"e_1_3_2_32_2","first-page":"804","volume-title":"ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP)","author":"Kadekodi Rohan","year":"2021","unstructured":"Rohan Kadekodi, Saurabh Kadekodi, Soujanya Ponnapalli, Harshad Shirwadkar, Gregory R. Ganger, Aasheesh Kolli, and Vijay Chidambaram. 2021. WineFS: A hugepage-aware file system for persistent memory that ages gracefully. In ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP). ACM, 804\u2013818."},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1145\/3341301.3359631","volume-title":"27th ACM Symposium on Operating Systems Principles (SOSP)","author":"Kadekodi Rohan","year":"2019","unstructured":"Rohan Kadekodi, Se Kwon Lee, Sanidhya Kashyap, Taesoo Kim, Aasheesh Kolli, and Vijay Chidambaram. 2019. SplitFS: Reducing software overhead in file systems for persistent memory. In 27th ACM Symposium on Operating Systems Principles (SOSP). ACM, 494\u2013508."},{"key":"e_1_3_2_34_2","first-page":"424","volume-title":"ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP)","author":"Kim Wook-Hee","year":"2021","unstructured":"Wook-Hee Kim, Madhava Krishnan Ramanathan, Xinwei Fu, Sanidhya Kashyap, and Changwoo Min. 2021. PACTree: A high performance persistent range index using PAC guidelines. In ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP). ACM, 424\u2013439."},{"key":"e_1_3_2_35_2","first-page":"257","volume-title":"15th USENIX Conference on File and Storage Technologies (FAST)","author":"Lee Se Kwon","year":"2017","unstructured":"Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh. 2017. WORT: Write optimal radix tree for persistent memory storage systems. In 15th USENIX Conference on File and Storage Technologies (FAST). USENIX, 257\u2013270."},{"key":"e_1_3_2_36_2","first-page":"462","volume-title":"27th ACM Symposium on Operating Systems Principles (SOSP)","author":"Lee Se Kwon","year":"2019","unstructured":"Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. 2019. RECIPE: Converting concurrent DRAM indexes to persistent-memory indexes. In 27th ACM Symposium on Operating Systems Principles (SOSP). ACM, 462\u2013477."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3488724"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389134"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_3_2_41_2","first-page":"73","volume-title":"14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"Michael Maged M.","year":"2002","unstructured":"Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. In 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 73\u201382."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323302"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2014.70"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3050440"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-4932-1_2"},{"key":"e_1_3_2_47_2","first-page":"329","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"Sun Yuanyuan","year":"2019","unstructured":"Yuanyuan Sun, Yu Hua, Zhangyu Chen, and Yuncheng Guo. 2019. Mitigating asymmetric read and write costs in cuckoo hashing for storage systems. In USENIX Annual Technical Conference (USENIX ATC). USENIX, 329\u2013344."},{"key":"e_1_3_2_48_2","first-page":"93","volume-title":"15th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Wang Qing","year":"2021","unstructured":"Qing Wang, Youyou Lu, Junru Li, and Jiwu Shu. 2021. NAP: A black-box approach to NUMA-aware persistent memory indexes. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX, 93\u2013111."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00049"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2012.2190369"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2070050"},{"key":"e_1_3_2_52_2","first-page":"1","volume-title":"20th USENIX Conference on File and Storage Technologies (FAST)","author":"Wu Kan","year":"2022","unstructured":"Kan Wu, Kaiwei Tu, Yuvraj Patel, Rathijit Sen, Kwanghyun Park, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2022. NyxCache: Flexible and efficient multi-tenant persistent memory caching. In 20th USENIX Conference on File and Storage Technologies (FAST). USENIX, 1\u201316."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386708"},{"key":"e_1_3_2_54_2","first-page":"17","volume-title":"20th USENIX Conference on File and Storage Technologies (FAST)","author":"Yi Jifei","year":"2022","unstructured":"Jifei Yi, Mingkai Dong, Fangnuo Wu, and Haibo Chen. 2022. HTMFS: Strong consistency comes for free with hardware transactional memory in persistent memory file systems. In 20th USENIX Conference on File and Storage Technologies (FAST). USENIX, 17\u201334."},{"key":"e_1_3_2_55_2","first-page":"897","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"Zhang Lu","year":"2019","unstructured":"Lu Zhang and Steven Swanson. 2019. Pangolin: A fault-tolerant persistent memory programming library. In USENIX Annual Technical Conference (USENIX ATC). USENIX, 897\u2013912."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2782251"},{"key":"e_1_3_2_57_2","first-page":"461","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Zuo Pengfei","year":"2018","unstructured":"Pengfei Zuo, Yu Hua, and Jie Wu. 2018. Write-optimized and high-performance hashing index scheme for persistent memory. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX, 461\u2013476."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561651","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561651","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:24Z","timestamp":1750186944000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561651"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3561651"],"URL":"https:\/\/doi.org\/10.1145\/3561651","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2022-05-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}