DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awareness
Pages 186 - 199
Abstract
This paper presents DLHT, a concurrent in-memory hashtable. Despite efforts to optimize hashtables, that go as far as sacrificing core functionality, state-of-the-art designs still incur multiple memory accesses per request and block request processing in three cases. First, most hashtables block while waiting for data to be retrieved from memory. Second, open-addressing designs, which represent the current state-of-the-art, either cannot free index slots on deletes or must block all requests to do so. Third, index resizes block every request until all objects are copied to the new index. Defying folklore wisdom, DLHT forgoes open-addressing and adopts a fully-featured and memory-aware closed-addressing design based on bounded cache-line-chaining. This design offers (1) lock-free operations and deletes that free slots instantly, (2) completes most requests with a single memory access, (3) utilizes software prefetching to hide memory latencies, and (4) employs a novel non-blocking and parallel resizing. In a commodity server and a memory-resident workload, DLHT surpasses 1.6B requests per second and provides 3.5× (12×) the throughput of the state-of-the-art closed-addressing (open-addressing) resizable hashtable on Gets (Deletes).
References
[1]
Abseil. 2023. Abseil C++ library: An open-source collection of C++ libraries from Google. https://github.com/abseil/abseil-cpp.
[2]
Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul. 2021. Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2021), 1171--1182.
[3]
Alex D. Breslow, Dong Ping Zhang, Joseph L. Greathouse, Nuwan Jayasena, and Dean M. Tullsen. 2016. Horton Tables: Fast Hash Tables for in-Memory Data-Intensive Computing. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC '16). USENIX Association, USA, 281--294.
[4]
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's Distributed Data Store for the Social Graph. In Proceedings of the 2013 Conference on Annual Technical Conference (ATC'13). USENIX, Berkeley, 49--60.
[5]
Michael J Cahill, Uwe Röhm, and Alan D Fekete. 2009. Serializable isolation for snapshot databases. ACM Transactions on Database Systems (TODS) 34, 4 (2009), 1--42.
[6]
Sai Rahul Chalamalasetti, Kevin Lim, Mitch Wright, Alvin AuYoung, Parthasarathy Ranganathan, and Martin Margala. 2013. An FPGA Memcached Appliance. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA '13). Association for Computing Machinery, New York, NY, USA, 245--254.
[7]
Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. 2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD '18). Association for Computing Machinery, New York, NY, USA, 275--290.
[8]
Zhangyu Chen, Yu Hua, Bo Ding, and Pengfei Zuo. 2020. Lock-Free Concurrent Level Hashing for Persistent Memory. In Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC'20). USENIX Association, USA, Article 55, 14 pages.
[9]
Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC '10). ACM, New York, NY, USA, 143--154.
[10]
Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '15). Association for Computing Machinery, New York, NY, USA, 631--644.
[11]
Tudor Alexandru David, Rachid Guerraoui, Tong Che, and Vasileios Trigonakis. 2014. Designing ASCY-compliant Concurrent Search Data Structures. (2014), 23. http://infoscience.epfl.ch/record/203822
[12]
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: Amazon's Highly Available Key-value Store. SIGOPS Oper. Sys. 41, 6 (2007), 5--20.
[13]
Aleksandar Dragojević, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. 2014. FaRM: Fast Remote Memory. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14). USENIX Association, Seattle, WA, 401--414.
[14]
Mostafa Elhemali, Niall Gallagher, Nick Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somasundaram Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. 2022. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service. In 2022 USENIX Annual Technical Conference (USENIX ATC 22). USENIX Association, Carlsbad, CA, 1037--1048. https://www.usenix.org/conference/atc22/presentation/elhemali
[15]
Facebook. 2023. Folly: An open-source C++ library developed and used at Facebook. https://github.com/facebook/folly.
[16]
Bin Fan. 2013. libcuckoo: A high-performance concurrent hash table. https://github.com/efficient/libcuckoo.
[17]
Bin Fan, David Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (nsdi'13). USENIX Association, Berkeley, CA, USA, 371--384. http://dl.acm.org/citation.cfm?id=2482626.2482662
[18]
Panagiota Fatourou, Nikolaos D. Kallimanis, and Thomas Ropars. 2018. An Efficient Wait-Free Resizable Hash Table. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA '18). Association for Computing Machinery, New York, NY, USA, 111--120.
[19]
H. Gao, J.F. Groote, and W.H. Hesselink. 2004. Almost wait-free resizable hashtables. In 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings. 50--.
[20]
H. Gao, J. F. Groote, and W. H. Hesselink. 2005. Lock-Free Dynamic Hash Tables with Open Addressing. Distrib. Comput. 18, 1 (jul 2005), 21--42.
[21]
K. Gharachorloo, A. Gupta, and J. Hennessy. 1992. Hiding Memory Latency using Dynamic Scheduling in Shared-Memory Multiprocessors. In [1992] Proceedings the 19th Annual International Symposium on Computer Architecture. 22--33.
[22]
Michael Greenwald. 2002. Two-Handed Emulation: How to Build Non-Blocking Implementations of Complex Data-Structures Using DCAS. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing (PODC '02). Association for Computing Machinery, New York, NY, USA, 260--269.
[23]
Tim Harris, James Larus, and Ravi Rajwar. 2010. Transactional Memory, 2nd Edition (2nd ed.). Morgan and Claypool Publishers.
[24]
Yongjun He, Jiacheng Lu, and Tianzheng Wang. 2020. CoroBase: Coroutine-Oriented Main-Memory Database Engine. Proc. VLDB Endow. 14, 3 (nov 2020), 431--444.
[25]
Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., USA.
[26]
Maurice Herlihy and Jeannette Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463--492.
[27]
Tayler H. Hetherington, Mike O'Connor, and Tor M. Aamodt. 2015. MemcachedGPU: Scaling-up Scale-out Key-Value Stores. In Proceedings of the Sixth ACM Symposium on Cloud Computing (SoCC '15). Association for Computing Machinery, New York, NY, USA, 43--57.
[28]
Daokun Hu, Zhiwen Chen, Jianbing Wu, Jianhua Sun, and Hao Chen. 2021. Persistent Memory Hash Indexes: An Experimental Evaluation. 14, 5 (jan 2021), 785--798.
[29]
Intel Corporation. 2023. oneTBB: Intel oneAPI Threading Building Blocks. https://github.com/oneapi-src/oneTBB.
[30]
Zsolt István, Gustavo Alonso, Michaela Blott, and Kees Vissers. 2015. A Hash Table for Line-Rate Data Processing. ACM Trans. Reconfigurable Technol. Syst. 8, 2, Article 13 (mar 2015), 15 pages.
[31]
Rosa M. Jiménez and Conrado Martínez. [n.d.]. On Deletions in Open Addressing Hashing. 23--31.
[32]
Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., USA.
[33]
Christoph Lameter. 2005. Effective synchronization on Linux/NUMA systems.
[34]
Maysam Lavasani, Hari Angepat, and Derek Chiou. 2014. An FPGA-Based In-Line Accelerator for Memcached. IEEE Comput. Archit. Lett. 13, 2 (jul 2014), 57--60.
[35]
Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. 2019. Recipe: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP '19). Association for Computing Machinery, New York, NY, USA, 462--477.
[36]
Bojie Li, Zhenyuan Ruan, Wencong Xiao, Yuanwei Lu, Yongqiang Xiong, Andrew Putnam, Enhong Chen, and Lintao Zhang. 2017. KV-Direct: High-Performance In-Memory Key-Value Store with Programmable NIC. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). ACM, New York, NY, USA, 137--152.
[37]
Huaicheng Li, Daniel S. Berger, Lisa Hsu, Daniel Ernst, Pantea Zardoshti, Stanko Novakovic, Monish Shah, Samir Rajadnya, Scott Lee, Ishwar Agarwal, Mark D. Hill, Marcus Fontoura, and Ricardo Bianchini. 2023. Pond: CXL-Based Memory Pooling Systems for Cloud Platforms. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS 2023). Association for Computing Machinery, New York, NY, USA, 574--587.
[38]
Sheng Li, Hyeontaek Lim, Victor W. Lee, Jung Ho Ahn, Anuj Kalia, Michael Kaminsky, David Andersen, Seongil O, Sukhan Lee, and Pradeep Dubey. 2016. Full-Stack Architecting to Achieve a Billion-Requests-Per-Second Throughput on a Single Key-Value Store Server Platform. ACM Trans. Comput. Syst. 34, 2, Article 5 (April 2016), 30 pages.
[39]
Sheng Li, Hyeontaek Lim, Victor W. Lee, Jung Ho Ahn, Anuj Kalia, Michael Kaminsky, David G. Andersen, O. Seongil, Sukhan Lee, and Pradeep Dubey. 2015. Architecting to Achieve a Billion Requests per Second Throughput on a Single Key-Value Store Server Platform. SIGARCH Comput. Archit. News 43, 3S (jun 2015), 476--488.
[40]
Hyeontaek Lim. 2017. MICA2: A fast in-memory key-value store. https://github.com/efficient/mica2.
[41]
Hyeontaek Lim, Dongsu Han, David Andersen, and Michael Kaminsky. 2014. MICA: A Holistic Approach to Fast In-memory Key-value Storage. In Proceedings of the 11th Networked Systems Design and Implementation (NSDI'14). USENIX Association, USA, 429--444.
[42]
Yujie Liu, Kunlong Zhang, and Michael Spear. 2014. Dynamic-Sized Nonblocking Hash Tables. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC '14). Association for Computing Machinery, New York, NY, USA, 242--251.
[43]
Baotong Lu, Xiangpeng Hao, Tianzheng Wang, and Eric Lo. 2020. Dash: Scalable Hashing on Persistent Memory. Proc. VLDB Endow. 13, 8 (apr 2020), 1147--1161.
[44]
Clemens Lutz, Sebastian Breß, Steffen Zeuch, Tilmann Rabl, and Volker Markl. 2020. Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD '20). Association for Computing Machinery, New York, NY, USA, 1633--1649.
[45]
Clemens Lutz, Sebastian Breß, Steffen Zeuch, Tilmann Rabl, and Volker Markl. 2022. Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 1017--1032.
[46]
Tobias Maier. 2023. growt: A concurrent growing hash table. https://github.com/TooBiased/growt.
[47]
Tobias Maier, Peter Sanders, and Roman Dementiev. 2019. Concurrent Hash Tables: Fast and General(?)! ACM Trans. Parallel Comput. 5, 4, Article 16 (feb 2019), 32 pages.
[48]
Hasan Al Maruf, Hao Wang, Abhishek Dhanotia, Johannes Weiner, Niket Agarwal, Pallab Bhattacharya, Chris Petersen, Mosharaf Chowdhury, Shobhit Kanaujia, and Prakash Chauhan. 2023. TPP: Transparent Page Placement for CXL-Enabled Tiered-Memory. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (ASPLOS 2023). Association for Computing Machinery, New York, NY, USA, 742--755.
[49]
Microsoft. 2023. mimalloc: A general purpose allocator with excellent performance. https://github.com/microsoft/mimalloc.
[50]
Moohyeon Nam, Hokeun Cha, Young-Ri Choi, Sam H. Noh, and Beomseok Nam. 2019. Write-Optimized Dynamic Hashing for Persistent Memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST'19). USENIX Association, USA, 31--44.
[51]
Vikram Narayanan, David Detweiler, Tianjiao Huang, and Anton Burtsev. 2023. DRAMHiT: A Hash Table Architected for the Speed of DRAM. In Proceedings of the Eighteenth European Conference on Computer Systems (EuroSys '23). Association for Computing Machinery, New York, NY, USA, 817--834.
[52]
Simo Neuvonen, Antoni Wolski, Markku Manner, and Vilho Raatikka. 2009. Telecom Application Transaction Processing Benchmark. http://tatpbenchmark.sourceforge.netl.
[53]
W. W. Peterson. 1957. Addressing for Random-Access Storage. IBM Journal of Research and Development 1, 2 (1957), 130--146.
[54]
Jeff Preshing. 2016. New Concurrent Hash Maps for C++. https://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/.
[55]
Jeff Preshing. 2018. junction: A library of concurrent data structures in C++. https://github.com/preshing/junction.
[56]
Mars Research. 2023. DRAMHiT. https://github.com/mars-research/DRAMHiT
[57]
Stefan Schuh, Xiao Chen, and Jens Dittrich. 2016. An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 1961--1976.
[58]
Michael L. Scott. 2013. Shared-Memory Synchronization.
[59]
Ori Shalev and Nir Shavit. 2006. Split-Ordered Lists: Lock-Free Extensible Hash Tables. J. ACM 53, 3 (may 2006), 379--405.
[60]
Panagiotis Sioulas, Periklis Chrysogelos, Manos Karpathiotakis, Raja Appuswamy, and Anastasia Ailamaki. 2019. Hardware-Conscious Hash-Joins on GPUs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE).
[61]
Alex Stivala, Peter J. Stuckey, Maria Garcia de la Banda, Manuel Hermenegildo, and Anthony Wirth. 2010. Lock-Free Parallel Dynamic Programming. J. Parallel Distrib. Comput. 70, 8 (aug 2010), 839--848.
[62]
Vasileios Trigonakis. 2021. CLHT: Cache-Line Hash Table. https://github.com/LPD-EPFL/CLHT.
[63]
Junchang Wang, Xiong Fu, Fu Xiao, and Chen Tian. 2020. DHash: Enabling Dynamic and Efficient Hash Tables. arXiv:cs.DC/2006.00819
[64]
Yi Wang. 2023. wyhash: ultra fast hash. https://github.com/wangyi-fudan/wyhash.
[65]
Wm A Wulf and Sally A McKee. 1995. Hitting the memory wall: Implications of the obvious. ACM SIGARCH computer architecture news 23, 1 (1995), 20--24.
[66]
Kai Zhang, Kaibo Wang, Yuan Yuan, Lei Guo, Rubao Lee, and Xiaodong Zhang. 2015. Mega-KV: A Case for GPUs to Maximize the Throughput of in-Memory Key-Value Stores. Proc. VLDB Endow. 8, 11 (jul 2015), 1226--1237.
[67]
Xingsheng Zhao, Chen Zhong, and Song Jiang. 2023. TurboHash: A Hash Table for Key-Value Store on Persistent Memory. In Proceedings of the 16th ACM International Conference on Systems and Storage (SYSTOR '23). Association for Computing Machinery, New York, NY, USA, 35--48.
Index Terms
- DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awareness
Recommendations
Grasping the gap between blocking and non-blocking transactional memories
Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using ...
Designing a Modern Memory Hierarchy with Hardware Prefetching
In this paper, we address the severe performance gap caused by high processor clock rates and slow DRAM accesses. We show that, even with an aggressive, next-generation memory system using four Direct Rambus channels and an integrated one-megabyte level-...
Prefetch-Aware Memory Controllers
Existing DRAM controllers employ rigid, nonadaptive scheduling and buffer management policies when servicing prefetch requests. Some controllers treat prefetches the same as demand requests, and others always prioritize demands over prefetches. However, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
436 pages
ISBN:9798400704130
DOI:10.1145/3625549
- Chair:
- Patrizio Dazzi,
- Co-chair:
- Gabriele Mencagli,
- Program Chair:
- David Lowenthal,
- Program Co-chair:
- Rosa M Badia
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
HPDC '24
Sponsor:
HPDC '24: 33rd International Symposium on High-Performance Parallel and Distributed Computing
June 3 - 7, 2024
Pisa, Italy
Acceptance Rates
Overall Acceptance Rate 166 of 966 submissions, 17%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 111Total Downloads
- Downloads (Last 12 months)111
- Downloads (Last 6 weeks)17
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in