Wait-Free Updates and Range Search Using Uruv

Gaurav Bhardwaj, Bapi Chatterjee, Abhay Jain, Sathya Peri

This paper, presented at a recent systems conference, introduces Uruv, a novel concurrent data structure designed to solve a long-standing challenge in parallel computing: providing "wait-free" guarantees for complex data operations like range searches and updates.

TL;DR

Uruv is the first practical, wait-free concurrent B+ Tree that supports both CRUD operations and linearizable range searches. By combining a proactive balancing strategy with a multi-versioned linked list, it achieves up to 95x better performance than existing lock-free B+ Trees while ensuring every thread makes progress regardless of system contention.

What Problem Does This Paper Address?

In the world of concurrent programming, there are different levels of "progress guarantees." Most modern high-performance data structures are lock-free, meaning at least one thread in the system is always making progress. However, individual threads can still be "starved" or delayed indefinitely if they are constantly interrupted by others.

The gold standard is wait-freedom, where every non-faulty thread is guaranteed to complete its operation in a finite number of steps. Historically, wait-free structures were considered too complex to implement or too slow for practical use. This is especially true for B+ Trees—the backbone of most databases—when they need to handle "range searches" (e.g., "find all keys between 10 and 100") alongside frequent updates. Existing solutions either lacked wait-freedom or struggled with the performance overhead of maintaining consistency during range scans.

Methods

The authors built Uruv (Sanskrit for "wide" or "spacious," often associated with the "Uruvriksha" or wide-spreading tree) using several clever architectural choices:

  1. Proactive Maintenance: Traditional B+ Trees split or merge nodes after an operation violates a threshold, which can lead to cascading changes up the tree. Uruv performs "proactive" splits and merges during the downward traversal. If a thread sees a node is near its limit, it fixes it immediately, keeping restructuring localized and predictable.
  2. Multi-Versioned Leaf Nodes: To allow range searches to happen without blocking updates, Uruv stores keys in a versioned linked list. Each update creates a new version of a node with a timestamp. A range search simply picks a "global" timestamp when it starts and reads the versions of keys that were valid at that specific moment.
  3. Fast-Path-Slow-Path Helping: Uruv uses a common wait-free technique where an operation first tries a "fast path" (standard lock-free execution). If it fails multiple times due to contention, it enters a "slow path" by announcing its intent in a global array. Other threads then "help" the stalled thread finish its task before moving on to their own.
  4. Fat Nodes: Internal nodes are "fat" (array-based) to improve CPU cache performance during traversal, while leaf nodes remain linked to facilitate the versioning required for range searches.

Datasets

The authors evaluated Uruv using synthetic benchmarks designed to simulate high-concurrency database workloads:

  • Key Space: A universe of 500 million keys.
  • Initial Load: Data structures were pre-filled with 100 million keys.
  • Workload Mixes: They tested various ratios of Reads vs. Updates (100/0, 95/5, 50/50) and varying range query sizes (1% to 10% of the key range).
  • Hardware: An IBM Power9 system with 40 physical cores (160 logical threads).

Key Insights and Ideas

  • Wait-freedom doesn't have to be a "performance tax": By optimizing the helping mechanism and using proactive balancing, Uruv actually outperforms many lock-free structures that don't have the same progress guarantees.
  • Versioning is the key to Range Searches: The "Aha!" moment is realizing that range searches are inherently difficult to linearize in a moving target. By using a versioned linked list at the leaves, Uruv allows readers to see a consistent "snapshot" of the data without ever needing to acquire a lock or stop an updater.
  • Localization of Change: Proactive balancing ensures that a thread never has to "restart" a massive tree-wide reorganization, which is the primary killer of performance in concurrent trees.

Key Results

Uruv was compared against several state-of-the-art structures, including the LF B+Tree, Open BwTree, and VCAS-BST:

  • Massive Speedups: For dictionary operations (Insert/Delete/Search), Uruv outperformed the standard lock-free B+ Tree by 44x to 95x.
  • Superior Range Search: In workloads involving range queries, Uruv beat the best-performing competitor (VCAS-BST) by 1.38x to 1.68x.
  • Scalability: Uruv showed excellent linear scaling. As the number of threads increased from 1 to 80, its throughput increased by roughly 46x to 61x, whereas competitors often plateaued much earlier.

Limitations and Future Work

  • Memory Reclamation: While the paper mentions retaining records of active range queries to safely delete old versions, the long-term memory overhead of multi-versioning under extreme update pressure is an area for further study.
  • Relaxed Tree Structures: The authors note that "relaxed" trees (which allow the tree to be slightly out of balance temporarily) might offer even higher raw throughput, though they currently lack the wait-free guarantees Uruv provides. Adapting Uruv's proactive design to these relaxed models is a suggested future direction.
  • Interpolation Search: The authors suggest that incorporating "interpolation search" (as seen in structures like C-IST) could further speed up internal node traversals.

Summary updated

Abstract

CRUD operations, along with range queries make a highly useful abstract data type (ADT), employed by many dynamic analytics tasks. Despite its wide applications, to our knowledge, no fully wait-free data structure is known to support this ADT. In this paper, we introduce Uruv, a proactive linearizable and practical wait-free concurrent data structure that implements the ADT mentioned above. Structurally, Uruv installs a balanced search index on the nodes of a linked list. Uruv is the first wait-free and proactive solution for concurrent B\(^+\)tree. Experiments show that Uruv significantly outperforms previously proposed lock-free B\(^+\)trees for dictionary operations and a recently proposed lock-free method to implement the ADT mentioned above.
BibTeX
@inproceedings{bhardwaj2023wait,
  author = {Gaurav Bhardwaj and Bapi Chatterjee and Abhay Jain and Sathya Peri},
  title = {{Wait-Free Updates and Range Search Using Uruv}},
  booktitle = {SSS},
  year = {2023},
  url = {https://openreview.net/forum?id=v2bzEfnFJW},
}

Loading related content...

Figure