Wait-Free Updates and Range Search using Uruv

Gaurav Bhardwaj, Abhay Jain, Bapi Chatterjee, Sathya Peri

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.

Introduction

In the landscape of parallel computing, the efficiency of concurrent data structures is often measured by their progress guarantees. While most high-performance structures utilize lock-free designs—ensuring that at least one thread in the system always makes progress—they do not prevent individual threads from being starved or delayed indefinitely by contention. The gold standard is wait-freedom, a guarantee that every non-faulty thread will complete its operation in a finite number of steps.

Historically, wait-free structures were dismissed as too complex or too slow for practical use, particularly for complex types like B+ Trees. B+ Trees are the backbone of modern databases, yet maintaining consistency during simultaneous updates and range searches (e.g., "find all keys between 10 and 100") has remained a significant hurdle. This paper introduces Uruv, the first practical, wait-free concurrent B+ Tree that supports both CRUD operations and linearizable range searches.

The Uruv Architecture

Uruv (named after the Sanskrit word for "wide" or "spacious") achieves its performance and progress guarantees through four primary architectural innovations:

1. Proactive Maintenance

Traditional B+ Trees typically perform structural modifications, such as splits or merges, after an operation violates a node's capacity threshold. This reactive approach can lead to cascading changes up the tree, causing significant delays for concurrent threads. Uruv instead employs a proactive balancing strategy. During the downward traversal of the tree, if a thread encounters a node that is near its capacity limit, it performs the necessary split or merge immediately. This keeps restructuring localized and predictable, preventing the massive tree-wide reorganizations that often degrade performance in concurrent environments.

2. Multi-Versioned Leaf Nodes

To support linearizable range searches without blocking concurrent updates, Uruv utilizes a multi-versioned linked list at the leaf level. Each update creates a new version of a node associated with a timestamp. When a range search begins, it captures a global timestamp and reads only the versions of keys that were valid at that specific moment. This allows readers to see a consistent snapshot of the data without requiring locks or halting update operations.

3. Fast-Path-Slow-Path Helping

Uruv implements a sophisticated helping mechanism to ensure wait-freedom. An operation initially attempts a "fast path" using standard lock-free execution. If the operation fails repeatedly due to high contention, the thread enters a "slow path" by announcing its intent in a global array. Other active threads are then required to "help" the stalled thread complete its task before proceeding with their own operations. This ensures that no single thread is left behind, regardless of system load.

4. Hybrid Node Structure

To optimize for modern hardware, Uruv uses "fat" internal nodes (array-based) to improve CPU cache performance during traversals. Meanwhile, leaf nodes remain linked to facilitate the versioning required for efficient range searches.

Experimental Evaluation

The authors evaluated Uruv on an IBM Power9 system with 40 physical cores (160 logical threads) using a key space of 500 million keys. The data structures were pre-filled with 100 million keys and tested against various workload mixes (Reads vs. Updates) and range query sizes (1% to 10% of the key range).

Performance Results

Uruv was compared against state-of-the-art structures, including the LF B+Tree, Open BwTree, and VCAS-BST. The results were definitive:

  • Dictionary Operations: For standard Insert, Delete, and Search operations, Uruv outperformed the standard lock-free B+ Tree by a factor of 44x to 95x.
  • Range Searches: In workloads involving range queries, Uruv outperformed its closest competitor (VCAS-BST) by 1.38x to 1.68x.
  • Scalability: Uruv demonstrated excellent linear scaling. As the thread count increased from 1 to 80, throughput increased by 46x to 61x, while many competitors plateaued early due to contention overhead.

Insights and Future Work

The success of Uruv challenges the long-held belief that wait-freedom imposes a "performance tax." By optimizing the helping protocol and localizing structural changes through proactive balancing, Uruv proves that wait-free structures can actually exceed the performance of lock-free counterparts.

Future research directions include refining memory reclamation strategies to manage the overhead of multi-versioning under extreme update pressure. Additionally, the authors suggest exploring "relaxed" tree structures—which allow for temporary imbalances—and incorporating interpolation search to further accelerate internal node traversals. Uruv stands as a significant step forward in making robust, wait-free guarantees practical for high-performance database systems.

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 Abhay Jain and Bapi Chatterjee and Sathya Peri},
  title = {{Wait-Free Updates and Range Search using Uruv}},
  booktitle = {SSS},
  year = {2023},
  url = {https://openreview.net/forum?id=v2bzEfnFJW},
}
Figure