Transactional Interference-less Balanced Tree

Ahmed Hassan (1) , Roberto Palmieri (1) , Binoy Ravindran (1)

1 Department of Computer Sciences [Blacksburg]

In this paper, we present TxCF-Tree, a balanced tree whose design is optimized to support transactional accesses. The core optimizations of TxCF-Tree’s operations are: providing a traversal phase that does not use any lock and/or speculation, and deferring the lock acquisition or physical modification to the transaction’s commit phase; isolating the structural operations (such as re-balancing) in an interference-less housekeeping thread; and minimizing the interference between structural operations and the critical path of semantic operations (i.e., additions and removals on the tree). We evaluated TxCF-Tree against the state- of-the-art general methodologies for designing transactional trees and we show that TxCF-Tree’s design pays off in most of workloads.

Keywords: Balanced Trees; Transactional Memory; Semantic Synchronization; Concurrent Data Structures

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Ahmed Hassan, Roberto Palmieri, Binoy Ravindran. Transactional Interference-less Balanced Tree . DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_22⟩. ⟨hal-01206580⟩