Multiverse: Transactional Memory with Dynamic Multiversioning Conference: ; ; CCS: Computing methodologies Concurrent algorithms

Gaetano Coccimiglio, Trevor Brown, Srivatsan Ravi · 2026

Read Multiverse: Transactional Memory with Dynamic Multiversioning Conference: ; ; CCS: Computing methodologies Concurrent algorithms by Gaetano Coccimiglio, Trevor Brown, Srivatsan Ravi (2026) 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-2601-09735.txt.

Introduction

Gaetano Coccimiglio, Trevor Brown, and Srivatsan Ravi extend software transactional memory with dynamic multiversioning. Their 2026 arXiv paper presents Multiverse. Transactional memory lets programmers build concurrent data structures with atomic blocks, easing parallel coding.

Recent systems perform well on some workloads but share a limit. They struggle with long-running reads that touch many addresses which keep changing. Multiversioning keeps older versions alive so such reads can finish. The authors aim to bring that support without losing speed. Concurrent data structures underpin servers and databases alike, so the stakes here are broad.

Catalog record

CREATORGaetano Coccimiglio, Trevor Brown, Srivatsan Ravi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-09735

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multiverse: Transactional Memory with Dynamic Multiversioning Conference: ; ; CCS: Computing methodologies Concurrent algorithms Gaetano Coccimiglio, Trevor Brown, Srivatsan Ravi Abstract . Software transactional memory (STM) allows programmers to easily implement concurrent data structures. STMs simplify atomicity. Recent STMs can achieve good performance for some workloads but they have some limitations. In particular, STMs typically cannot support long-running reads which access a large number of addresses that are frequently updated. Multiversioning is a common approach used to support this type of workload. However, multiversioning is often expensive and can reduce the performance of transactions where versioning is not necessary. In this work we present Multiverse, a new STM that combines the best of both unversioned TM and multiversioning. Multiverse features versioned and unversioned transactions which can execute concurrently. A main goal of Multiverse is to ensure that unversioned transactions achieve performance comparable to the state of the art unversioned STM while still supporting fast versioned transactions needed to enable long running reads. We implement Multiverse and compare it against several STMs. Our experiments demonstrate that Multiverse achieves comparable or better performance for common case workloads where there are no long running reads. For workloads with long running reads and frequent updates Multiverse significantly outperforms existing STMS. In several cases for these workloads the throughput of Multiverse is several orders of magnitude faster than other STMs. 1. Introduction Software transactional memory (STM) is a synchronization mechanism that allows users to execute sequences of memory accesses as atomic transactions . STMs make atomicity easy but not necessarily fast. STMs typically perform read-only transactions using optimistic synchronization. In such STMs ( 21 ; 14 ; 23 ; 29 ; 17 ; 18 ; 19 ; 16 ; 31 ) , memory addresses are typically associated with version numbers that are used to determine whether a transaction’s reads are consistent. If not, a transaction aborts and retries. For workloads where transactions are small (accessing few addresses) and contention is low, TMs can typically achieve good performance. On the other hand, STMs often struggle to handle transactions that read a large number of addresses that are frequently updated. This type of transaction is very likely to repeatedly abort. A classical solution in data structures and databases for supporting large read-only operations is to utilize multiversioned concurrency control (MVCC) , which allows one to take atomic snapshots of memory ( 1 ; 34 ) . Much of the early work on MVCC focused on maintaining consistent versions and avoiding an unbounded number of versions per address. Many of these MVCC designs which focus only on providing atomic snapshots are typically expensive. Recent work has made significant practical improvements to MVCC ( 6 ; 33 ) . There have been some attempts to combine multiversioning with STM ( 24 ; 26 ; 30 ) . These existing approaches typically guarantee the weaker correctness conditions of snapshot isolation ( 3 ) or serializability ( 4 ) , as opposed to (the stronger) opacity ( 20 ) . Without opacity, aborted transactions are allowed to observe inconsistent state which can lead to various problems ( 13 ) . Furthermore, maintaining multiple versions can incur substantial overhead, reducing performance in the case where versioning is not required. In such cases, traditional unversioned TMs are preferable. In this work we present Multiverse, a new opaque STM that leverages recent advancements in MVCC ( 6 ) to enable read-only transactions that access a large number of addresses to commit even in the presence of many concurrent updates that would otherwise cause potentially unbounded aborts. Unlike prior multiversioned STMs, our primary design goal is to ensure that our unversioned transactions are competitive with the fastest unversioned STM , Deferred Clock Transactional Locking (DCTL) at present ( 29 ) , while also ensuring that our versioned transactions are fast as possible subject to the constraint that they do not add substantial overhead to unversioned transactions. As Figure 1 shows, Multiverse can outperform the fastest unversioned STM even for workloads with very few range queries (RQs), where versioning is not always necessary. Our algorithm features unversioned and versioned transactional code paths. Transactions begin as unversioned, and transition to the versioned code path based on a heuristic function that considers the number of times the transaction has aborted, the thread’s recent transactions’ behavior, and the recent behavior of other transactions in the TM system. Our design associates versions with individual addresses at the word level of granularity. We dynamically switch addresses between versioned and unversioned states. Switching addresses between unversioned and versioned states is subtle and deeply connected to both correctness and performance. Figure 1 . (a,b)-tree benchmark with an 89.99% search, 0.01% RQ, 5% insert, 5% delete workload using a uniform key access pattern. RQ size is 10k (1% of prefill size). Y-axis is ops/sec. X-axis is number of threads. A key insight in our work is that versioning of addresses should be done quite differently in different workloads. More specifically, if a versioned transaction only needs to access a small number of addresses under low contention, it is most efficient to leave most addresses unversioned, and allow concurrent non-versioned update transactions to proceed with as little overhead as possible. On the other hand, if a versioned transaction needs to access a very large number of addresses under high contention, it is more efficient to preemptively (and globally) force all concurrent updating transactions to preserve old versions of all addresses. Our TM thus features two global modes that we switch between based on a heuristic. In Mode Q , transactions on the versioned code path are responsible for marking addresses as versioned , and transactions on the unversioned code path can be largely oblivious to versioned transactions. A versioned transaction in Mode Q that encounters an unversioned address will abort if the address has changed since the transaction began. So, this mode is suitable when transactions that require multiversioning only access relatively few memory addresses, and/or are infrequent. If aborts due to encountering unversioned addresses are frequent, then Mode U can help substantially. In Mode U , transactions on the unversioned code path that write to memory are responsible for marking addresses as versioned, and transactions on the versioned code path can simply behave as if all relevant addresses are already versioned. Mode U is crucial for enabling high performance when versioned transactions perform a large number of accesses that are likely to be aborted by concurrent updates. The complexities of versioning are completely hidden from the user, and Multiverse does not require any modifications to a program’s memory layout—only replacement of variable types with analogous transactional types. This is the gold standard in TM. By avoiding changes to the memory layout, we preserve the cache behavior of the underlying program as much as possible, limit intrusive changes to the program, and allow standard object serialization techniques for disk storage or network transfer of transactional objects. We utilize separate parallel lock- and version-tables so that when the versioning mechanism is not actively engaged, the cache behavior of unversioned transactions is as similar as possible to the state of the art in unversioned STM. Contributions: • We introduce Multiverse, a novel opaque STM that combines unversioned

Read the complete text