Department of Information Technology

Contention Adapting Search Trees

A contention adapting search tree is a concurrent ordered set data structure that adapts its synchronization granularity according to the contention level. We have described two types of contention adapting search trees. One of them is lock-based and one is lock-free. This page contains links to contention adapting search tree related papers, implementations, benchmarks and performance graphs.

Publications

The lock-free contention adapting search tree (LFCA tree) is described in the following publication:

A comprehensive description of the lock-based contention adapting search tree (CA tree) with support for the operations insert, delete, lookup and range query is given in the journal publication below. This publication contains a detailed description of the data structure including pseudo-code and proofs for the correctness properties (linearizability, deadlock freedom and livelock freedom).

The journal publication above is built upon the following two conference publications. The first of those papers describes CA trees with support for single-element operations (insert, delete, and lookup). This paper contains two experimental evaluations of CA tree optimizations that are not included in the journal paper above. One of these optimzations is for use cases with very high contention. The other one combines a CA tree with hardware lock elision. The second paper evaluates and describes a CA tree extension to support linearizable range operations (range queries and range updates) and bulk operations. The technical report that is referred to in these two papers has been replaced by the journal publication above.

The publication below describes an optimization for CA trees that is enabled by using an immutable data structure internally. This optimization is especially beneficial for range queries when contention is high. The experimental results presented in the paper show that the optimized CA tree variant outperform many recently proposed data structures in many scenarios. The benchmark code and the code for the optimized CA tree variant is available here.

The publication below describes how CA trees can be used to improve the scalability of the Erlang Term Storage.

Benchmarks and Code

The code used to obtain the experimental results included in the CA tree papers can be found by following the links with the text "code" that can be found next to the citations above.

Updated  2018-07-22 12:06:05 by Kjell Winblad.