A Wait-Free Hash Map

Keywords

Concurrency; Data Structures; Hash map; Lock-free; Non-blocking; Parallel programming; Wait-free

Abstract

In this work we present the first design and implementation of a wait-free hash map. Our multiprocessor data structure allows a large number of threads to concurrently insert, get, and remove information. Wait-freedom means that all threads make progress in a finite amount of time—an attribute that can be critical in real-time environments. This is opposed to the traditional blocking implementations of shared data structures which suffer from the negative impact of deadlock and related correctness and performance issues. We only use atomic operations that are provided by the hardware; therefore, our hash map can be utilized by a variety of data-intensive applications including those within the domains of embedded systems and supercomputers. The challenges of providing this guarantee make the design and implementation of wait-free objects difficult. As such, there are few wait-free data structures described in the literature; in particular, there are no wait-free hash maps. It often becomes necessary to sacrifice performance in order to achieve wait-freedom. However, our experimental evaluation shows that our hash map design is, on average, 7 times faster than a traditional blocking design. Our solution outperforms the best available alternative non-blocking designs in a large majority of cases, typically by a factor of 15 or higher.

Publication Date

6-1-2017

Publication Title

International Journal of Parallel Programming

Volume

45

Issue

3

Number of Pages

421-448

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10766-015-0376-3

Socpus ID

84939480948 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84939480948

This document is currently not available here.

Share

COinS