DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awareness
Open Access
- 3 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 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).Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- On Deletions in Open Addressing Hashing2018
- Asynchronized Concurrency2015
- Dynamic-sized nonblocking hash tables2014
- Shared-Memory Synchronization2013
- Benchmarking cloud serving systems with YCSB2010
- Serializable isolation for snapshot databasesACM Transactions on Database Systems, 2009
- Split-ordered listsJournal of the ACM, 2006
- Lock-free dynamic hash tables with open addressingDistributed Computing, 2005
- Hitting the memory wallACM SIGARCH Computer Architecture News, 1995
- Hiding memory latency using dynamic scheduling in shared-memory multiprocessors1992