Lock-Free Data Structures

Every synchronization primitive we’ve studied so far—mutexes, semaphores, condition variables—solves the concurrency problem by making threads wait. A thread that can’t acquire a lock goes to sleep. The scheduler will eventually wake it up. This blocking approach is simple, correct, and general: you can protect any data structure with a mutex.

But blocking has costs. Context switches are expensive. Under high contention, threads spend more time sleeping and waking than doing useful work. In latency-sensitive systems (real-time trading, operating system kernels, high-frequency data pipelines), the unpredictability of blocking synchronization is unacceptable. And for some problems—particularly in multi-core systems with many CPUs—you simply cannot afford to serialize access through a lock.

Lock-free data structures take a different approach: instead of using locks to ensure that only one thread accesses a data structure at a time, they use atomic hardware instructions to make concurrent access safe. A thread never blocks; instead, if it detects that another thread modified the data structure in a conflicting way, it retries the operation.

Overview

Lock-free data structures achieve thread safety without locks by using atomic operations provided by the hardware—instructions like Compare-And-Swap (CAS), Fetch-And-Add, Load-Linked/Store-Conditional. These instructions are implemented in hardware and guarantee that certain read-modify-write sequences happen atomically, even across multiple CPU cores.

The key property of lock-free algorithms is progress guarantee: some thread will make progress in a finite number of steps, regardless of what other threads are doing. This is stronger than lock-based algorithms, where if one thread holding a lock is preempted, all other threads waiting for that lock are blocked indefinitely. Lock-free algorithms are immune to priority inversion and scheduler latency.

─────────────────────────────────────────────

When to Use / When Not to Use

Use lock-free data structures when: you need maximum throughput and minimum latency in a concurrent system, you’re on a multi-core system where lock contention is a bottleneck, you’re writing kernel code or real-time systems where blocking is unacceptable, or you’re implementing high-performance queues and counters.

Practical use cases:

• High-performance message queues (Disruptor pattern in LMAX trading systems)
• Non-blocking counters and accumulators
• Lock-free stacks and linked lists
• Hazard pointer-based memory management for read-heavy data

Do not use lock-free data structures when: your team lacks experience debugging memory order issues (the bugs are subtle and extremely hard to reproduce), your data structure is simple enough that a mutex is faster and clearer, or your platform lacks atomic instructions (though this is rare on modern hardware).

The complexity cost: A mutex-protected data structure with a simple implementation will often outperform a poorly implemented lock-free version. Lock-free algorithms require careful reasoning about memory ordering, handle ABA problems, and can have worse worst-case performance than lock-based alternatives due to retry loops. Benchmark before committing.

Architecture or Flow Diagram

graph TD
    A[Thread A: CAS ptr from OLD to NEW] --> B{CAS succeeds?}
    B -->|yes| C[Node linked, operation complete]
    B -->|no| D[Re-read ptr<br/>Retry with updated value]
    A2[Thread B: CAS ptr from OLD to NEW] --> B2{CAS succeeds?}
    B2 -->|yes| E[Node linked, operation complete]
    B2 -->|no| F[Re-read ptr<br/>Retry with updated value]
    D --> A
    F --> A2

Two threads attempt to modify the head pointer simultaneously. Only the one with the correct “old” value succeeds. The loser retries with the new value it observed, which may have changed from another thread’s update.

Core Concepts

Atomic Operations and Memory Order

Modern CPUs provide atomic instructions that perform read-modify-write operations atomically:

• CAS (Compare-And-Swap): Reads a memory location, compares it to an expected value, and if equal, writes a new value. Returns true if the swap happened, false otherwise. This is the workhorse of lock-free algorithms.

• Fetch-And-Add: Atomically increment a value and return the old value.

• Load-Linked / Store-Conditional (LL/SC): ARM’s alternative to CAS. Load-Linked loads a value and starts a transaction; Store-Conditional attempts to store, failing if the location was modified by another core. More flexible than CAS but less widely available.

Memory ordering is the critical subtlety. CPUs can reorder memory operations for performance (store buffering, write combining). A CAS that succeeds on one core may not be immediately visible to other cores due to store buffers. To write correct lock-free algorithms, you must specify memory ordering semantics:

• Seq_cst (sequentially consistent): The strongest guarantee—all threads see all operations in the same total order. Easy to reason about but slowest.
• Acq_rel (acquire/release): A write to a location becomes visible to other threads at the release (e.g., when a lock is released), and subsequent reads see the writes that preceded that release.
• Relaxed: Only atomicity is guaranteed, not ordering. Fastest but hardest to reason about.

// Seq_cst example (C11 atomics)
atomic_int counter = ATOMIC_VAR_INIT(0);

// This has full memory barrier semantics
int old = atomic_fetch_add_explicit(&counter, 1, memory_order_seq_cst);

The ABA Problem

The ABA problem is the most notorious challenge in lock-free programming. Consider a lock-free stack push operation:

// Thread A: pop head
node_t *head = atomic_load(&stack_head);
node_t *next = head->next;
// Context switch here

// Thread B: pop head twice, push one back (reuses the node)
// head is now back at the same address with new next
node_t *new_head = next;  // This is the same address as head!

// Thread A resumes: CAS from head to next
// CAS sees head still equals head, but the stack state has changed!
atomic_compare_exchange_strong(&stack_head, &head, next);  // WRONG!

The classic solution is tagged pointers or versioned references: add a counter that increments each time the pointer is modified. The CAS checks both the pointer and the version number, so a recycled node with the same address but a higher version will be detected.

typedef struct {
    void *ptr;
    uintptr_t tag;
} tagged_ptr_t;

atomic_uintptr_t head;  // The tag is stored in the upper bits on 64-bit systems

// ABA-safe CAS
int tagged_cas(atomic_uintptr_t *addr, tagged_ptr_t *old, tagged_ptr_t *new) {
    uintptr_t old_val = (old->tag << 48) | (uintptr_t)old->ptr;
    uintptr_t new_val = (new->tag << 48) | (uintptr_t)new->ptr;
    return atomic_compare_exchange_strong(addr, &old_val, new_val);
}

Michael-Scott Lock-Free Queue

The most widely used lock-free queue algorithm, introduced by Maged Michael and Michael Scott in 1996, handles the ABA problem through careful pointer management and a dummy node at the head.

typedef struct node_t {
    void *data;
    _Atomic struct node_t *next;
} node_t;

typedef struct {
    _Atomic struct node_t *head;  // Dummy node, never NULL
    _Atomic struct node_t *tail;
} mpmc_queue_t;

void queue_init(mpmc_queue_t *q) {
    node_t *dummy = malloc(sizeof(node_t));
    dummy->data = NULL;
    dummy->next = NULL;
    atomic_store(&q->head, dummy);
    atomic_store(&q->tail, dummy);
}

void queue_push(mpmc_queue_t *q, void *data) {
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = NULL;

    while (1) {
        node_t *tail = atomic_load(&q->tail);
        node_t *next = atomic_load(&tail->next);
        if (tail == atomic_load(&q->tail)) {  // Re-check tail hasn't moved
            if (next == NULL) {
                // Try to append at tail
                if (atomic_compare_exchange_strong(&tail->next, &next, node)) {
                    // Success: now update tail
                    atomic_compare_exchange_strong(&q->tail, &tail, node);
                    return;
                }
            } else {
                // Tail fell behind, advance it
                atomic_compare_exchange_strong(&q->tail, &tail, next);
            }
        }
    }
}

void *queue_pop(mpmc_queue_t *q) {
    while (1) {
        node_t *head = atomic_load(&q->head);
        node_t *tail = atomic_load(&q->tail);
        node_t *next = atomic_load(&head->next);
        if (head == atomic_load(&q->head)) {  // Re-check
            if (head == tail) {
                if (next == NULL) return NULL;  // Empty
                atomic_compare_exchange_strong(&q->tail, &tail, next);
            } else {
                void *data = next->data;
                if (atomic_compare_exchange_strong(&q->head, &head, next)) {
                    free(head);  // Free old dummy
                    return data;
                }
            }
        }
    }
}

Production Failure Scenarios + Mitigations

The LMAX Disruptor Incident

LMAX’s Disruptor—a high-performance inter-thread messaging library—had a subtle bug where a memory fence operation was accidentally removed during an optimization. On x86, stores can be reordered by the store buffer, meaning that a value written to a ring buffer slot might not be visible to the reading thread even after the sequence number was updated. The result was intermittent corrupted reads where consumers saw stale data.

Mitigation: Always use explicit memory orderings in lock-free code. Do not rely on default atomic behavior without understanding your hardware’s memory model. On x86, use memory_order_seq_cst for stores that must be visible to other cores before dependent stores.

ABA Corruption in Linux Kernel’s RCU Implementation

The Linux kernel’s RCU (Read-Copy-Update) mechanism had a production incident where the ABA problem in a linked list traversal caused a use-after-free. A reader traversing a list saw a node’s next pointer, was preempted, and upon resumption found the pointer had been reused for a new node. The RCU grace period mechanism was supposed to prevent reuse until all readers finished, but a bug in the grace period tracking allowed a node to be freed while a reader still held a reference to it.

Mitigation: In production lock-free code, rigorous memory reclamation strategies are essential. Use hazard pointers (each thread declares which nodes it is accessing, preventing their reclamation), RCU (kernel), or epoch-based reclamation (userspace). Never assume that CAS success means the node is safe to reclaim.

Python’s Queue Module Memory Corruption

Python’s queue.Queue uses a mutex + condition variable approach internally. However, some third-party “lock-free” Python extensions claiming high performance had an ABA bug in their CAS loop: they used a Python object reference directly as the CAS value but didn’t account for the fact that Python can GC and reuse an object at the same address within a single CAS operation window. The result was data corruption that manifested as intermittent crashes in production.

Mitigation: In managed memory environments (Python, Java, Go), ensure your lock-free primitives account for garbage collection or use higher-level abstractions that do. Never use raw pointer addresses as CAS values in languages with GC unless the runtime provides a safe mechanism (like Java’s AtomicMarkableReference).

Trade-off Table

Implementation Snippets

C: Lock-Free Counter with Fetch-And-Add

#include <stdatomic.h>
#include <stdio.h>

_Atomic long long counter = 0;

// Increment without any lock
void increment() {
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
}

// Get current value
long long get() {
    return atomic_load_explicit(&counter, memory_order_relaxed);
}

C++11: Lock-Free Stack (Treiber Stack)

#include <atomic>
#include <memory>
#include <iostream>

template<typename T>
struct node {
    T data;
    node* next;
    node(T d) : data(std::move(d)), next(nullptr) {}
};

template<typename T>
class lock_free_stack {
    std::atomic<node<T>*> head;

public:
    void push(T data) {
        node<T>* new_node = new node<T>(std::move(data));
        new_node->next = head.load(std::memory_order_relaxed);
        // CAS until we successfully link the new node
        while (!head.compare_exchange_weak(
            new_node->next,
            new_node,
            std::memory_order_release,
            std::memory_order_relaxed
        )) {
            // new_node->next is updated by compare_exchange_weak on failure
            // Retry with updated new_node->next
        }
    }

    std::optional<T> pop() {
        node<T>* old_head = head.load(std::memory_order_acquire);
        while (old_head && !head.compare_exchange_weak(
            old_head,
            old_head->next,
            std::memory_order_acquire,
            std::memory_order_relaxed
        )) {
            // Retry with updated old_head
        }
        if (!old_head) return std::nullopt;
        T result = std::move(old_head->data);
        delete old_head;  // Memory reclamation: safe because no other thread holds a reference
        return result;
    }
};

Python: Using ctypes for Atomic CAS

import ctypes
import threading

class LockFreeCounter:
    def __init__(self):
        # 64-bit atomic counter using ctypes
        self._value = threading.Lock()  # Fallback to mutex if no atomic support
        self._count = 0

    def increment(self):
        # Using a simple mutex fallback for demonstration
        # Production: use ctypes with inline assembly or cffi for real atomic CAS
        with self._value:
            self._count += 1

    def get(self):
        with self._value:
            return self._count

Observability Checklist

• CAS failure rate: Count how often compare_exchange_strong returns false (retry needed). High failure rate (> 10%) indicates high contention or poor algorithm design
• Retry loop iteration count: Track how many iterations of a retry loop are needed per operation. Growing retries indicate contention
• Memory barrier cost: On high-core-count systems, seq_cst barriers can be expensive; measure with perf counters
• Hazard pointer scans: If using hazard pointer reclamation, measure the cost of scanning hazard pointer arrays on each operation
• ABA collision rate: Track how often the CAS fails due to tag mismatch (ABA detection). High rate indicates insufficient tag bits
• Cache line contention: Lock-free data structures sharing cache lines between atomic variables can cause false sharing; measure cache miss rates

Security/Compliance Notes

Linearizability and data security: Lock-free algorithms are typically linearizable (each operation appears to happen atomically at some point between invocation and response). For security-sensitive data, this ordering guarantee matters: if you’re using lock-free structures to manage authentication tokens or session state, ensure the memory ordering semantics are strong enough to prevent one thread from observing partially updated state.

Memory reclamation exploits: Lock-free algorithms that use hazard pointers or epoch-based reclamation must carefully track which threads are still accessing data before reclaiming it. A bug in the reclamation logic can cause use-after-free, which is a memory corruption vulnerability. Use well-tested libraries (like Facebook’s Folly for C++) rather than implementing your own.

Side-channel timing leaks: Lock-free data structures with secret-dependent access patterns (e.g., a lock-free hash table whose probing pattern depends on key value) can leak sensitive information through timing side channels. This is especially relevant in cryptography or authentication systems.

For compliance: if your lock-free data structure processes PII or financial data, ensure that the linearizability guarantee holds under all contention scenarios. A dropped update in a lock-free system is not just a performance bug—it can be a data integrity violation.

Common Pitfalls / Anti-patterns

1. Ignoring memory ordering. Using memory_order_relaxed when you need memory_order_seq_cst will cause your algorithm to fail on weakly ordered architectures (ARM, POWER) while working correctly on x86. Always reason about what ordering your algorithm requires and specify it explicitly.

2. ABA problem causing data corruption. Failing to handle the ABA problem will silently corrupt data on some workload patterns. Use tagged pointers, versioned references, or a memory reclamation scheme (hazard pointers, RCU, epochs) that prevents reuse until all possible readers have finished.

3. Assuming hardware CAS is always available. Some embedded processors lack CAS instructions. Use compile-time detection (__sync_bool_compare_and_set or C++11 atomics) and fall back to mutex-based implementations for platforms without hardware atomic support.

4. Writing lock-free algorithms without hazard pointer reclamation. You cannot safely free a node after a CAS succeeds—the old value’s node might still be referenced by another thread that read it before the CAS. You need a memory reclamation strategy. The most common mistake is calling free() immediately after a successful CAS, causing use-after-free in the other thread.

5. Over-using retry loops under high contention. If the CAS keeps failing due to high contention, retry loops can cause livelock (wasting CPU with no progress). Use exponential back-off in retry loops for high-contention scenarios, and benchmark against lock-based alternatives.

Quick Recap Checklist

• Lock-free data structures use atomic hardware instructions (CAS, Fetch-And-Add) instead of locks
• CAS is the fundamental building block: atomically compare a value and swap if it matches
• The ABA problem (detecting reused memory locations) requires tagged pointers or versioned references
• Memory ordering semantics must be explicitly specified to ensure correctness on weakly ordered architectures
• Lock-free algorithms require a memory reclamation strategy (hazard pointers, RCU, epoch-based) to safely free nodes
• CAS retry loops under high contention can cause livelock; use back-off strategies
• Lock-free is not always faster than lock-based: benchmark your specific workload before committing
• Implementation complexity is high; use well-tested library implementations where possible

Interview Questions

Further Reading

• Concurrency Fundamentals — The problem space and why synchronization is needed
• Mutex Implementation — How mutexes are implemented in userspace and kernel
• Semaphores — Counting semaphores for resource management
• Readers-Writer Locks — Optimizing for read-heavy workloads
• Lock-Free Structures — Advanced techniques for highly concurrent systems

Conclusion

Lock-free data structures change how you think about concurrency. Instead of coordinating through waiting, lock-free approaches let threads make progress independently, using atomic hardware instructions to serialize conflicting updates. This gives better latency and throughput under contention—but getting it right requires careful attention to memory ordering, ABA prevention, and memory reclamation.

The world of concurrent programming spans from simple mutexes to exotic wait-free algorithms. Lock-free structures sit toward the advanced end. They’re the right tool when blocking costs are genuinely unacceptable and your team can implement and verify the implementation correctly. For most applications, a well-designed lock-based structure with good contention characteristics will beat a poorly implemented lock-free alternative every time.

For continued learning, explore how real systems apply these concepts: the Linux kernel’s RCU implementation, the LMAX Disruptor pattern for high-throughput messaging, and research on hazard pointer reclamation schemes for userspace lock-free programming.