CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Lock-free linearizable 1-dimensional range queries

Bapi Chatterjee (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
ACM International Conference Proceeding Series Vol. Part F125794 (2017), p. Article no: a 9.
[Konferensbidrag, refereegranskat]

© 2016 ACM.Efficient concurrent data structures that support range queries are highly sought-after in a number of application areas. For example, the contemporary big-data processing platforms employ them as in-memory index structures for fast and scalable real-time updates and analytics, where analytics utilizes the range queries. In this paper, we present a generic algorithm to perform linearizable range queries in lock-free ordered 1-dimensional data structures. The algorithm requires single-word atomic compare-and-swap (CAS) primitives. Our method generalizes the lock-free data structure snapshot of Petrank et al. [25]. Fundamentally, we utilize a partial snapshot object derived from the snapshot object of Jayanti [20]. We experimentally evaluate the proposed algorithm in a lock-free linked-list, skip-list and binary search tree (BST). The experiments demonstrate that our algorithm is scalable even in the presence of high percentage of concurrent modify operations and outperforms an existing range search algorithm in lock-free k-ary trees in several scenarios.

Nyckelord: Concurrency , Data structure , Linearizability , Lockfree , Range query , Range search

Denna post skapades 2017-03-30.
CPL Pubid: 248722


Läs direkt!

Länk till annan sajt (kan kräva inloggning)