Skip to main content

Algorithmic improvements for fast concurrent Cuckoo hashing

Author(s): Li, Xiaozhou; Andersen, David G; Kaminsky, Michael; Freedman, Michael J

To refer to this page use:
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.
Publication Date: Apr-2014
Citation: Li, Xiaozhou, David G. Andersen, Michael Kaminsky, and Michael J. Freedman. "Algorithmic improvements for fast concurrent Cuckoo hashing." In Proceedings of the Ninth European Conference on Computer Systems (2014): pp. 1-14. doi:10.1145/2592798.2592820
DOI: 10.1145/2592798.2592820
Pages: 1 - 14
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Ninth European Conference on Computer Systems
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.