MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads
Daniel Manor, Mor Perry, Moshe Sulamy · 2025
Read MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads by Daniel Manor, Mor Perry, Moshe Sulamy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20041.txt.
Introduction
Daniel Manor, Mor Perry, and Moshe Sulamy present a concurrent data structure for sets that stays fast when updates dominate and range questions must be answered atomically. Most concurrent sets are tuned for read-heavy work and sag under heavy writing, while the update-tuned rivals handle range queries poorly. Writing in twenty twenty-five, the team builds on a balanced (a,b)-tree design that splits nodes within a size band. Their structure guarantees linearizability, the formal promise that every operation appears to happen at a single instant between its start and finish.
In head-to-head tests on range query operations, the new set beat leading update-optimized rivals by up to double, according to the authors. The paper speaks to builders of in-memory databases and other shared-state systems where writers and range scans collide constantly.
Catalog record
| CREATOR | Daniel Manor, Mor Perry, Moshe Sulamy |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20041
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads Daniel Manor, Mor Perry, Moshe Sulamy Abstract In concurrent data structures, the efficiency of set operations can vary significantly depending on the workload characteristics. Numerous concurrent set implementations are optimized and fine-tuned to excel in scenarios characterized by predominant read operations. However, they often perform poorly when confronted with workloads that heavily prioritize updates. Additionally, current leading-edge concurrent sets optimized for update-heavy tasks typically lack efficiency in handling atomic range queries. This study introduces the MTASet, which leverages a concurrent (a,b)-tree implementation. Engineered to accommodate update-heavy workloads and facilitate atomic range queries, MTASet surpasses existing counterparts optimized for tasks in range query operations by up to 2x. Notably, MTASet ensures linearizability. I Introduction Given the inherent challenges of concurrent programming, developers often use various concurrent data structures to build applications and complex systems, such as modern database engines designed for multicore hardware. These structures enable safe utilization in multithreaded environments through sophisticated synchronization algorithms optimized for performance. The rise of multicore hardware has spurred the development of numerous new concurrent data structure designs, including dictionaries [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] and sets [ 9 , 10 , 11 ] . These innovations consistently enhance performance over existing solutions and introduce features like atomic range scan operations (i.e., range queries). Existing concurrent set or dictionary implementations typically excel in scenarios with low contention and predominantly read-oriented workloads, often neglecting the demands of update-intensive environments. Conversely, implementations optimized for update-heavy workloads frequently struggle with efficient range queries. For example, in experiments by Kobus et al. [ 8 ] , SnapTree [ 3 ] performs relatively well on update operations but exhibits poor performance on scan operations. Our research aims to address this issue by enhancing the scalability of range queries within a concurrent set optimized for update-heavy workloads, ensuring robust performance across diverse workload types. Scaling range queries in concurrent data structures is inherently challenging due to the extensive coordination needed across elements. Unlike single-key operations, atomic range queries must traverse multiple nodes, risking inconsistent results if other threads update the data during the query, thus adding further complexity to manage manage concurrent updates. While locking or snapshotting methods can help maintain consistency, they impose synchronization overhead and lead to contention, especially in update-heavy environments. These issues make it difficult to efficiently support range queries at scale without compromising performance or data accuracy. In response, we introduce MTASet, a concurrent set and dictionary with high update throughput that stores keys and their associated values and supports essential operations such as insertion, deletion, and lookup. In addition to high update throughput, MTASet is optimized for atomic range queries, which retrieve values for a specified range of keys. MTASet uses a tailored multi-versioning approach [ 12 ] for atomic range queries, maintaining only the versions required for ongoing scans and managing version numbers through scans rather than updates. This significantly enhances the throughput of range query operations, especially under concurrent update-heavy workloads. Inspired by KiWi [ 2 ] , MTASet’s range query demonstrates substantial performance gains in experimental evaluations, outperforming many state-of-the-art data structures in both read-mostly and update-heavy workloads. MTASet is an (a,b)-tree, a variant of B-trees that allows between a and b keys per node, where a\leq\frac{b}{2} . It is based on a concurrent version of Larsen and Fagerberg’s relaxed (a,b)-tree [ 13 ] , specifically the OCC-ABtree [ 14 ] . MTASet employs fine-grained versioned locks to ensure atomic sub-operations and uses version-based validation in leaf nodes to guarantee correct searches. To manage overhead, MTASet incorporates established techniques, such as avoiding key sorting in leaves and minimizing unnecessary node copying. The core philosophy of MTASet is to promptly handle client operations while deferring data structure optimizations to an occasional maintenance procedure. This procedure, called rebalance , aims to balance MTASet’s (a,b)-tree for faster access and to eliminate obsolete keys through compaction. I-A Background A set data structure stores unique elements without any particular order. It supports three operations: Insert adds an element to the set if it is not already in the set, delete removes an element from the set if it exists, and contains tests whether an element is in the set. An (a,b) -tree [ 15 ] is a balanced leaf-oriented search tree where each node can have between a and b children, and 2\leq a\leq\frac{b}{2} . This tree structure optimizes operations by maintaining logarithmic height with respect to the number of elements, ensuring efficient data retrieval, insertion, and deletion. The balanced structure of the (a,b) -tree ensures logarithmic time complexity for all operations, making it suitable for applications requiring frequent insertions, deletions, and lookups, such as database indexing. MTASet utilizes a concurrent (a,b) -tree data structure, based on OCC-ABtree [ 14 ] , which includes optimizations tailored for update-heavy workloads. OCC-ABtree does not include a range query operation. However, it was noted in [ 14 ] that a range query capability could be implemented for the OCC-ABtree using the following technique detailed in [ 16 ] : In OCC-ABtree, leaf nodes are interconnected in a linked list, with each leaf node storing keys along with insertionTime and deletionTime fields indicating when keys were added and removed, respectively. A global variable TS is incremented atomically by a range query from time t to t^{\prime} . During insertion, TS is read and written to the insertionTime field of the new key atomically. During deletion TS is read and written to the deletionTime field of the deleted key, and stored in the thread that executes the deletion in a list of deleted keys accessible for other threads to read. Special precautions are taken during deletion to prevent race conditions. A range query traverses leaf node lists, collecting keys with insertionTime less than or equal to t . It subsequently checks thread-specific lists for keys deleted after time t , using each key’s deletionTime to identify missed deletions during traversal. MTASet’s range query introduces significant improvements, detailed in Section IV , that enhance the range query operation throughput beyond this technique, while maintaining the performance advantages of the OCC-ABtree on update-heavy workloads. Our correctness notion is linearizability , which intuitively means that the object ”appears to be” executing sequentially. It is defined for a history , which is a sequence of operation invoke and return steps, possibly by multiple threads. A history partially orders operations: operation op1 precedes operation op2 in a history if op1 ’s return precedes op2 ’s invoke; two operations that do not precede each other are concurrent . An object is specified using a sequential specification , which is the set of its allowed sequential histories. Roughly speaking, a history \sigma is linearizable [ 17 ] if it has a sequential permutation that preserves \sigma ’s precedence relation and satisfies the object’s sequential specification. I-B Contributions The primary contribution of this paper is the development and analysis of MTASet, a concurrent set specifically optimized for high update throughput and frequent range queries. MTASet enhances performance by leveraging a tailored multi-versioning approach, which maintains only the necessary versions of keys for ongoing scans, thus minimizing overhead