Traditional mutual exclusion primitives like locks and latches guarantee data consistency by forcing threads to wait. In highly parallel environments—such as modern multi-core CPUs and massively parallel GPUs—this waiting leads to severe bottlenecks: thread stalling, context switching overhead, and cache coherence storms.
To unlock true hardware scalability, modern systems increasingly transition to lock-free and latch-free concurrency control. By utilizing hardware-level atomic instructions, these architectures allow multiple threads to modify shared state concurrently without global blocking.
The Mechanics of Atomic Primitives and Indirection
How do we update a complex data structure without locking it? The foundational tool is the Compare-and-Swap (CAS) operation, which atomically updates a memory location only if its current value matches an expected state. However, directly applying CAS to complex structures like B-trees introduces a major challenge: structural modifications (such as page splits) require changing multiple pointers simultaneously, which a single standard CAS cannot do.
To solve this, Justin J. Levandoski introduced the Bw-Tree in The BW-Tree: A Latch-Free B-Tree for Log-Structured Flash Storage, which decouples logical page identities from physical memory locations using a central indirection mapping table. Instead of modifying a page in place, a thread creates a "delta record" representing the change and uses a single CAS to swap the pointer in the mapping table. This ensures that updates are isolated, atomic, and instantaneous.
Traditional In-Place Update (Requires Locks):
[Page Ptr] ---> [ Physical Page Data (Modified in place) ]
Latch-Free Delta Update via Indirection Table (CAS):
[Mapping Table Slot] ---> [ Delta Record ] ---> [ Physical Page Data ]
|
+---(Atomic CAS swaps this pointer to install new delta)
Yet, under extreme contention, CAS loops can suffer from "cache coherence storms" because multiple threads repeatedly try and fail to update the same pointer, forcing expensive cache invalidations across cores. To mitigate this, Justin J. Levandoski et al. demonstrated in High Performance Transactions in Deuteronomy that replacing CAS loops with atomic addition (Fetch-and-Add, or FAA) for resource allocation ensures that every thread succeeds on its first attempt, drastically reducing cache contention. Similarly, Zhuoyue Zhao et al. leveraged FAA in the AB-tree (AB-tree: Index for Concurrent Random Sampling and Updates) to update aggregate weights concurrently without exclusive latches.
Progress Guarantees and Cooperative Execution
Lock-free structures guarantee that at least one thread makes progress, but they can still allow individual threads to starve. To achieve robust performance, researchers design systems around stronger progress guarantees and cooperative execution models:
- Cooperative Assistance: In the Bw-Tree architecture (The BW-Tree: A Latch-Free B-Tree for Log-Structured Flash Storage), if a thread encounters a page split initiated by another thread, it does not wait or abort. Instead, it actively assists in completing the structural change before proceeding with its own operation. This cooperative model prevents long-running operations from becoming system-wide bottlenecks.
- Obstruction-Free and Multi-Word CAS: When data structures require shifting multiple elements—such as in a Robin Hood hash table—a standard single-word CAS is insufficient. Robert Kelly et al. addressed this in Concurrent Robin Hood Hashing by utilizing a multi-word compare-and-swap ($K$-CAS) primitive alongside an obstruction-free design. This allows threads to execute complex multi-element shifts without global locks, aborting and retrying only if they detect a direct conflict via shared descriptors.
- Wait-Free Progress: The gold standard of concurrency is wait-freedom, where every thread is guaranteed to finish its operation in a bounded number of steps. Gaurav Bhardwaj et al. demonstrated in Wait-Free Updates and Range Search using Uruv that wait-free designs can significantly outperform traditional lock-free structures in complex dictionary and range search operations, proving that strict progress guarantees do not require sacrificing practical throughput.
Scaling Graphs and Hash Tables
Graph algorithms and knowledge base materialization present unique concurrency challenges because multiple parallel paths frequently converge on the same nodes, creating hot spots.
In main-memory RDF and Datalog systems, Boris Motik et al. bypassed global mutexes in Parallel OWL 2 RL Materialisation in Centralised, Main-Memory RDF Systems by designing hash-based indexing structures that use localized markers and atomic CAS operations. When resolving equivalent entities in parallel, Boris Motik et al. employed a lock-free identifier rewriting mechanism using atomic compare-and-set primitives (Handling Owl: sameAs via Rewriting), preventing data explosion without synchronization overhead.
On massively parallel hardware like GPUs, managing write conflicts at scale is even more critical. Vibhav Vineet et al. (CUDA cuts: Fast graph cuts on the GPU) and Jike Chong et al. (A fully data parallel WFST-based large vocabulary continuous speech recognition on a graphics processing unit) utilized hardware-level atomic operations to handle converging search paths, allowing thousands of threads to update node flow values and state probabilities simultaneously without complex locking structures.
Alternatively, Aydin Buluc et al. highlighted the power of idempotent state updates in Parallel Breadth-First Search on Distributed Memory Systems: if multiple threads write the exact same value (such as a search level) to a shared memory location, they can do so without any atomic operations or locks at all, bypassing synchronization costs entirely.
Optimistic Concurrency Control and Validation
When operations are highly complex or distributed, maintaining fine-grained atomic updates across the entire structure becomes impractical. In these scenarios, systems turn to Optimistic Concurrency Control (OCC).
As Mohsen Lesani explained in a comprehensive paradigm comparison (Concurrent Programming Paradigms, A Comparison in Scala), OCC operates on the assumption that conflicts are rare. Threads execute transactions completely lock-free on local views of the data, followed by a strict validation phase before the final commit. If a conflict is detected during validation, the transaction rolls back and retries.
Magdalena Balazinska et al. noted in Editorial for S.I.: VLDB 2020 that implementing OCC in multicore main-memory systems maximizes throughput by eliminating lock overhead during the execution phase. However, as Mohsen Lesani pointed out, OCC's performance is highly sensitive to workload skew; under high contention, frequent transaction aborts and rollbacks can introduce substantial overhead, shifting the design preference back toward fine-grained lock-free or wait-free primitives.