Multi-Reader, Multi-Writer Parallel Cuckoo Hashing

Abstract

In 2001, Pagh and Rodler described a single-threaded hash table design called cuckoo hashing (R. Pagh & Rodler, 2001). Since then, the rise of multi-core processors and large datasets have motivated the development and refinement of concurrent hash tables. We (a) give a brief review of relevant theory of hash functions and hash algorithms; (b) describe a multi-reader, multi-writer parallel cuckoo hash table design; and (c) describe the results of experiments with changing parameters including number of threads, failure criteria, and bucket selection strategies. We suggest multiple areas for future work, including experiments with lock granularity, varying the number of slots per bucket, and determining whether the depth-first approach of classic cuckoo hashing can have competitive performance under the proposed algorithm compared to a breadth-first approach.