Lock-free Contention Adapting Search Trees
| Autor: | SagonasKonstantinos, WinbladKjell, JonssonBengt |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Linearizability
Range query (data structures) Computer science Concurrent data structure Distributed computing 020207 software engineering 0102 computer and information sciences 02 engineering and technology Data structure 01 natural sciences Computer Science Applications Computational Theory and Mathematics 010201 computation theory & mathematics Hardware and Architecture Modeling and Simulation Scalability 0202 electrical engineering electronic engineering information engineering Non-blocking algorithm Software |
| Zdroj: | ACM Transactions on Parallel Computing. 8:1-38 |
| ISSN: | 2329-4957 2329-4949 |
| DOI: | 10.1145/3460874 |
| Popis: | Concurrent key-value stores with range query support are crucial for the scalability and performance of many 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|