Efficient Lock-free B+trees
📜 Abstract
As computer systems scale in the number of processors, data structures with good parallel performance become increasingly important. Lock-free data structures promise improved parallel performance at the expense of higher complexity and sequential execution time. We present ELB-trees, a new lock-free dictionary with simple synchronization in the common case, making it almost 30 times faster than sequential library implementations at 24 threads.
✨ Summary
Summary
The paper introduces ELB-trees, a lock-free dictionary structurally related to B+trees. Entries in leaf nodes are intentionally unordered, allowing common insertions and removals to complete with a single compare-and-swap operation. Internal nodes retain sorted separator entries for navigation. Structural changes are handled through a helping-based rebalancing protocol: operations temporarily prevent modifications to related nodes, publish enough state for other threads to continue the operation, and replace affected nodes using compare-and-swap. Hazard pointers are used for safe memory reclamation.
The evaluation uses two older multiprocessor systems and workloads containing 20% insertions, 20% removals, and 60% searches. The reported peak speedups over the single-threaded ELB-tree are 12.1× on one platform and 17.6× on the other for one-million-entry workloads. At 24 threads, ELB-trees are reported to be almost 30× faster than GCC’s sequential std::multimap implementation. The paper also reports that ELB-trees use less memory than the competing structure in the tested workloads and become relatively more advantageous for larger dictionaries because of cache and translation-lookaside-buffer behavior.
Subsequent research and influence
The work was followed by a longer technical report that formally addresses the correctness of ELB-tree operation semantics and their lock-free progress properties. (arxiv.org) Later work by the same research group discusses ELB-trees as part of a broader family of relaxed-balancing concurrent search trees and compares their balancing approach with related structures such as BT-trees and SF-trees. (backend.orbit.dtu.dk) ELB-trees have also been used as a comparison point in subsequent concurrent data-structure research, including work on lock-free scheduling structures. (doaj.org) The available evidence shows continued academic reference and comparison, but no clear evidence of direct industrial adoption or deployment was identified.