Efficient and Robust Lock-Free Multi-Word Compare-and-Swap via Contention-Aware Helping

Jul 16, 2026

Upload by Levi

Efficient concurrent access to shared memory is critical for high-performance data structures, where lock-based synchronization can limit scalability and threaten liveness through deadlocks. Lock-free designs using single-word CAS avoid locks but face complexity from unavoidable intermediate states. Multi-word compare-and-swap (MCAS) provides an atomic primitive for updating multiple memory locations, yet under high contention it suffers from helping-induced cache invalidations and performance loss, and may be vulnerable to the ABA problem. This work proposes a new lock-free MCAS algorithm introducing contention-aware helping, fast garbage collection counters, and version embedding for consistency and ABA suppression, achieving up to 3× throughput over state of the art.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

Introduction

Motivation: lock-based vs lock-free synchronization

CAS and the need for MCAS

Challenges in current lock-free MCAS

Proposed direction

IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x 1 PAPER Efficient and Robust Lock-Free Multi-Word Compare-and-Swap via Contention-Aware Helping Motoki UNNO†, Kento SUGIURA†, Nonmembers, and Yoshiharu ISHIKAWA†, Member arXiv :2607 .06034v 1 [ cs .DB] 7 Jul 2026 SUMMARY Efficient concurrent access to shared memory remains a central focus for researchers seeking to enhance data structure performance. Lock-based synchronization often limits scalability and introduces liveness issues such as deadlocks. In contrast, implementing non-blocking structures with single-word compare-and-swap (CAS) instructions increases algorithmic complexity because of unavoidable intermediate states. Multi-word compare-and-swap (MCAS) operations offer a practical primitive for atomically updating multiple discrete memory locations, thereby addressing these challenges. However, under high contention, helping mechanisms designed to guarantee lock-freedom may cause excessive cache invalidations and significant performance degradation. Furthermore, existing approaches are vulnerable to the ABA problem. Current lock-free MCAS algorithms may duplicate the execution of the same operation, leading to inconsistent states in certain edge cases. To address these challenges, this paper introducesa new lock-free MCAS algorithm that achieves both efficiency and consistency. First, we propose a contention-aware helping mechanism that dynamically regulates the number of concurrent helpers through exponential backoff and embedded entry counters. These counters also enable a fast garbage-collection path, significantly reducing memory management overhead. Second, we introduce a version embedding approach to suppress the ABA problem during MCAS operations. Although version embedding requires several bits per target memory region to store version information, embedded versions allow helpers to avoid duplicated MCAS executions. Experimental results show that the proposed method achieves up to three times the throughput of the state-of-the-art lock-free MCAS algorithm. Moreover, the results indicate that version embedding is sufficient to prevent the ABA problem in practical scenarios. key words: lock-free algorithm, multi-word compare-and-swap (MCAS), contention-aware optimization, ABA problem prevention 1. Introduction Efficient concurrent access to shared data structures is essential for achieving high performance in in-memory databases [1] and complex index structures [2] . Although many systems employ lock-based synchronization, this approach incurs performance overheads and liveness issues, such as deadlocks, which can constrain overall scalability. In contrast, algorithms utilizing the compare-and-swap (CAS) instruction can eliminate the need for locks and facilitate the construction of non-blocking data structures. Such algorithms and structures are considered lock-free if they guarantee system progress as long as at least one thread remains active [3] . For example, most lock-based structures possess the deadlock-free property, which requires that all threads remain active to guarantee progress; if a lock holder halts or terminates unexpectedly, other threads may be unable to pro- Manuscript received January 1, 2024 . Manuscript revised January 1, 2024 . †Graduate School of Informatics, Nagoya University, Nagoyashi DOI: 10.1587/trans.E0.??.1 ceed because of an abandoned lock. Lock-free algorithms maintain progress even in the presence of inactive threads, thereby providing more robust processing. Although lock-freedom is a highly desirable property, designing correct lock-free algorithms remains a significant challenge. The CAS instruction atomically compares a single memory word with an expected value and, only if they match, stores the desired value in the target region. Additionally, because the CAS instruction returns the current (pre-swapped) value, a thread can determine whether the operation succeeded: if the returned value matches t

FAQs

为什么需要用MCAS而不是只用单词级CAS？

单词级CAS在跨多个内存位置保持一致性时会引入不可避免的中间状态，显著增加算法复杂度；MCAS能同时交换多个位置，从而消除中间状态并简化一致性实现。

当前锁自由MCAS在高竞争下会遇到哪些性能问题？

为保证锁自由，MCAS依赖helping机制推进中间状态；在高竞争时，helpers会并发修改相同目标内存区域，导致CPU缓存失效频繁，从而造成性能显著下降。

论文如何抑制MCAS中的ABA问题？

论文提出version embedding，通过在目标内存区域嵌入版本信息抑制ABA；嵌入版本使helpers能够避免重复执行MCAS，从而在实际场景中足以防止ABA问题。

Jul 16, 2026

Upload by Levi