Search: onr:"swepub:oai:DiVA.org:uu-455997" >
Lock-free Contentio...
Lock-free Contention Adapting Search Trees
-
- Winblad, Kjell (author)
- Ericsson AB, Isafjordsgatan 10, S-16440 Kista, Sweden.
-
- Sagonas, Konstantinos (author)
- Uppsala universitet,Datalogi
-
- Jonsson, Bengt, 1957- (author)
- Uppsala universitet,Datorteknik
-
Ericsson AB, Isafjordsgatan 10, S-16440 Kista, Sweden Datalogi (creator_code:org_t)
- 2021-07-22
- 2021
- English.
-
In: ACM TRANSACTIONS ON PARALLEL COMPUTING. - : Association for Computing Machinery (ACM). - 2329-4949 .- 2329-4957. ; 8:2
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Concurrent key-value stores with range query support are crucial for the scalability and performance ofmany applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity in a concurrent key-value store with range query support is problematic as the best performing synchronization granularity depends on a number of factors that are difficult to predict, such as the level of contention and the number of items that are accessed by range queries. We present the first linearizable lock-free key-value store with range query support that dynamically adapts its synchronization granularity. This data structure is called the lock-free contention adapting search tree (LFCA tree). An LFCA tree automatically performs local adaptations of its synchronization granularity based on heuristics that take contention and the performance of range queries into account. We show that the operations of LFCA trees are linearizable, that the lookup operation is wait-free, and that the remaining operations (insert, remove and range query) are lock-free. Our experimental evaluation shows that LFCA trees achieve more than twice the throughput of related lock-free data structures in many scenarios. Furthermore, LFCA trees are able to perform substantially better than data structures with a fixed synchronization granularity over a wide range of scenarios due to their ability to adapt to the scenario at hand.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Annan data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Other Computer and Information Science (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Concurrent data structure
- range query
- lock-freedom
- wait-freedom
- linearizability
- adaptivity
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database