Ph.D Thesis

Ph.D StudentRaviv Maya
SubjectTheoretical and Experimental Methods for Concurrent
Search Trees
DepartmentDepartment of Computer Science
Supervisors PROF. Hagit Attiya


With the rise of multiprocessor systems, the construction of efficient multi-threaded code has become a central issue for the performance of programs and services. Concurrent search trees serve as the main data structures in multi-core applications, such as in-memory databases, key/value stores, and operating systems' address space management.  The problem of designing fast and scalable concurrent search trees, particularly binary search trees (BSTs), has received significant attention. The importance of BSTs calls for efficient BST implementations as well as methodologies for evaluating them. This thesis considers both issues.

This thesis starts by presenting innovative uses of epoch-based synchronization that elegantly solve challenging synchronization problems that arise when developing concurrent BSTs. Specifically, we show how two epoch-based synchronization schemes, read copy update (RCU) and epoch-based reclamation (EBR), can be used beyond memory reclamation.

The first epoch-based synchronization scheme, RCU, provides scalable synchronization-free reads that execute concurrently with updates. To guarantee the consistency of such reads, an RCU update transitioning the data structure between certain states must wait for the completion of all existing reads. This thesis presents Citrus, the first RCU-based data structure that allows concurrent updaters.   The use of RCU synchronization leads to a simple design that greatly resembles sequential BST. We also present Predicate RCU (PRCU), an RCU variant in which an update waits only for the reads whose consistency it affects. We explore the trade-offs in implementing PRCU, describing implementations that reduce wait times with varying overhead on readers. We apply PRCU to Citrus and show experimentally that PRCU improves the performance of Citrus in update heavy workloads.

The second epoch-based synchronization scheme, EBR, is an efficient memory reclamation scheme that can be applied to any data structure in an unmanaged programing language. This thesis presents novel technique to add range query operations to existing concurrent data structures that use EBR. The idea is to use information regarding deleted nodes that is naturally stored in the EBR scheme. We produce three range query algorithms, which use locks, transactional memory and lock-free techniques, respectively. We apply our range query technique to a variety of concurrent BSTs, which cannot be used with previous techniques. Experimental evaluation shows that our range query technique outperforms previous solutions.  

The last part of this thesis focuses on experimental evaluation of concurrent BSTs. We perform a detailed performance analysis of ten state-of-the-art BSTs, using both microbenchmarks and an in-memory database system benchmarks. We find and explain significant unexpected performance differences between BSTs with similar tree structure and search implementations, which we trace to subtle performance-degrading interactions of BSTs with systems software and hardware subsystems.  We further derive a prescriptive approach to avoid this performance degradation, as well as algorithmic insights on concurrent BST design.