Algorithmic improvements for fast concurrent cuckoo hashing

Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman

Research output: Contribution to conferencePaper

67 Scopus citations

Abstract

Fast concurrent hash tables are an increasingly important building block as we scale systems to greater numbers of cores and threads. This paper presents the design, implementation, and evaluation of a high-throughput and memory-efficient concurrent hash table that supports multiple readers and writers. The design arises from careful attention to systems-level optimizations such as minimizing critical section length and reducing interprocessor coherence traffic through algorithm re-engineering. As part of the architectural basis for this engineering, we include a discussion of our experience and results adopting Intel's recent hardware transactional memory (HTM) support to this critical building block. We find that naively allowing concurrent access using a coarse-grained lock on existing data structures reduces overall performance with more threads. While HTM mitigates this slowdown somewhat, it does not eliminate it. Algorithmic optimizations that benefit both HTM and designs for fine-grained locking are needed to achieve high performance. Our performance results demonstrate that our new hash table design-based around optimistic cuckoo hashing- outperforms other optimized concurrent hash tables by up to 2.5x for write-heavy workloads, even while using substantially less memory for small key-value items. On a 16-core machine, our hash table executes almost 40 million insert and more than 70 million lookup operations per second.

Original languageEnglish (US)
DOIs
StatePublished - Jan 1 2014
Event9th ACM European Conference on Computer Systems, EuroSys 2014 - Amsterdam, Netherlands
Duration: Apr 14 2014Apr 16 2014

Other

Other9th ACM European Conference on Computer Systems, EuroSys 2014
CountryNetherlands
CityAmsterdam
Period4/14/144/16/14

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Algorithmic improvements for fast concurrent cuckoo hashing'. Together they form a unique fingerprint.

  • Cite this

    Li, X., Andersen, D. G., Kaminsky, M., & Freedman, M. J. (2014). Algorithmic improvements for fast concurrent cuckoo hashing. Paper presented at 9th ACM European Conference on Computer Systems, EuroSys 2014, Amsterdam, Netherlands. https://doi.org/10.1145/2592798.2592820