An Efficient Lock-Free Logarithmic Search Data Structure Based On Multi-Dimensional List

Keywords

Concurrent Data Structure; Dictionary; Lock-free; Multi-dimensional List; Search Tree; Skiplist

Abstract

Logarithmic search data structures, such as search trees and skiplists, are fundamental building blocks of many applications. Although the self-balancing binary search trees are among the most ubiquitous sequential search data structures, designing non-blocking rebalancing algorithms is challenging due to the required structural alternation, which may stall other concurrent operations. Skiplists, which probabilistically create multiple levels of shortcuts in an ordered list, provide practical alternatives to balanced search trees. The use of skiplists eliminates the need of rebalancing and ensures amortized logarithmic sequential search time, but concurrency is limited under write-dominated workload because the linkage between multiple distant nodes must be updated. In this paper, we present a linearizable lock-free dictionary design based on a multi-dimensional list (MDList). A node in an MDList arranges its child nodes by their dimensionality and order them by coordinate prefixes. The search operation works by first generating a one-to-one mapping from the scalar keys to a high-dimensional vectors space, then uniquely locating the target position by using the vector as coordinates. Our algorithm guarantees worst-case search time of O(log N) where N is the size of key space. Moreover, the ordering property of the data structure is readily maintained during mutations without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our dictionary outperforms the state of the art approaches by as much as 100% when the key universe is large and an average of 30% across all scenarios.

Publication Date

8-8-2016

Publication Title

Proceedings - International Conference on Distributed Computing Systems

Volume

2016-August

Number of Pages

281-292

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICDCS.2016.19

Socpus ID

84985993186 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS