Lock-Free Data Structures Architecture in Depth

Progress guarantees: what lock-free actually buys

Concurrency papers classify algorithms by what they promise about progress, and the classification is the real reason to choose lock-free code. A blocking algorithm, anything built on a mutex, promises nothing if the lock holder stops running: every other thread waits until it resumes. An obstruction-free algorithm promises that a thread running alone finishes in a bounded number of steps. A lock-free algorithm promises that, among all threads, at least one completes an operation in a bounded number of steps, so the system as a whole always advances even though an unlucky individual thread may retry indefinitely. A wait-free algorithm promises every thread finishes in bounded steps, which removes starvation as well.

Notice what is missing from that list: speed. Lock-free does not mean faster. An uncontended mutex in a good runtime is a single atomic instruction to acquire and one to release, the same cost as one successful CAS. Under heavy contention a lock-free structure can be slower than a well-tuned lock, because every failed CAS still moved a cache line between cores. An older version of this page quoted a tenfold advantage for lock-free queues; no such general number exists. Choose lock-free code for its guarantees: no priority inversion, no convoying behind a preempted holder, safety in signal handlers and interrupt-like contexts, and latency tails that do not depend on the scheduler.

Progress guarantees: what lock-free actually buys

Concurrency papers classify algorithms by what they promise about progress, and the classification is the real reason to choose lock-free code. A blocking algorithm, anything built on a mutex, promises nothing if the lock holder stops running: every other thread waits until it resumes. An obstruction-free algorithm promises that a thread running alone finishes in a bounded number of steps. A lock-free algorithm promises that, among all threads, at least one completes an operation in a bounded number of steps, so the system as a whole always advances even though an unlucky individual thread may retry indefinitely. A wait-free algorithm promises every thread finishes in bounded steps, which removes starvation as well.

Notice what is missing from that list: speed. Lock-free does not mean faster. An uncontended mutex in a good runtime is a single atomic instruction to acquire and one to release, the same cost as one successful CAS. Under heavy contention a lock-free structure can be slower than a well-tuned lock, because every failed CAS still moved a cache line between cores. An older version of this page quoted a tenfold advantage for lock-free queues; no such general number exists. Choose lock-free code for its guarantees: no priority inversion, no convoying behind a preempted holder, safety in signal handlers and interrupt-like contexts, and latency tails that do not depend on the scheduler.

The primitive and the hardware under it

Every lock-free algorithm reduces to one read-modify-write primitive. On x86-64 it is LOCK CMPXCHG, which compares a memory word with an expected value and, only if they match, stores a new one, atomically and with a full fence. ARMv8.0 and RISC-V provide load-linked/store-conditional pairs (LDXR/STXR on ARM, LR/SC on RISC-V): the store fails if anything touched the reservation since the load. ARMv8.1 added the LSE instructions, including a single-instruction CAS. Languages hide the difference: C++ std::atomic<T>::compare_exchange_weak, Java AtomicReference.compareAndSet and VarHandle, Rust AtomicPtr::compare_exchange_weak. The weak form may fail spuriously, which LL/SC needs, so use it inside retry loops and the strong form when a single attempt matters.

The cost model lives in the cache coherence protocol. To execute an atomic RMW a core must own the cache line exclusively. If the line sits in another core's cache, the request crosses the interconnect, invalidates the other copy and waits for the data, which is tens of nanoseconds on one socket and more across sockets. When sixteen threads hammer one head pointer, the line ping-pongs and throughput collapses toward one successful operation per transfer. So the best optimisations avoid sharing: pad hot fields onto separate 64-byte lines (128 on some CPUs) and split counters per thread.

Memory ordering: the half x86 hides

Atomicity is half the contract. The other half is ordering: when thread A writes a node's fields and then publishes a pointer to it, thread B must not see the pointer before it sees the fields. Compilers and CPUs both reorder ordinary loads and stores, so the publication needs a release store (or a successful CAS with release semantics), and the reader needs an acquire load. Release and acquire pair up: everything A wrote before the release is visible to B after its acquire reads the published value. The full rules are in the memory model deep dive.

x86 makes ordering bugs easy to ship, because its total-store-order model already gives every plain load acquire semantics and every plain store release semantics. Code with the wrong memory_order passes every test on a developer laptop and then corrupts data on ARM servers, where loads and stores really are reordered. Default to seq_cst until a profiler proves the fence matters, and when you weaken an ordering, write a comment naming the release that each acquire synchronises with. In Java, volatile is sequentially consistent and VarHandle offers acquire and release modes.

A Treiber stack, line by line

The Treiber stack is the smallest complete lock-free structure: a singly linked list whose head is an atomic pointer. Push links a new node in front of the current head and CASes the head to it; pop CASes the head to its successor. The linearization point of each operation is its successful CAS, the instant the change becomes visible to everyone.

template <typename T>
class TreiberStack {
    struct Node { T value; Node* next; };
    std::atomic<Node*> head_{nullptr};
public:
    void push(T v) {
        Node* n = new Node{std::move(v), head_.load(std::memory_order_relaxed)};
        // On failure, compare_exchange_weak reloads the current head into n->next.
        while (!head_.compare_exchange_weak(n->next, n,
                   std::memory_order_release,      // publish n's fields
                   std::memory_order_relaxed)) {
            // retry: n->next now holds the fresh head
        }
    }
    std::optional<T> pop() {
        Node* h = head_.load(std::memory_order_acquire);
        while (h && !head_.compare_exchange_weak(h, h->next,   // reads h->next: h must still be alive
                   std::memory_order_acquire,
                   std::memory_order_acquire)) {
        }
        if (!h) return std::nullopt;
        T v = std::move(h->value);
        retire(h);              // NOT delete h: another popper may be reading h->next right now
        return v;
    }
};

Two lines carry the whole difficulty. In pop, h->next is dereferenced after another thread may already have popped and freed h, which is a use-after-free. And the CAS compares only the pointer value, so if h was popped, freed, and a new node happened to be allocated at the same address and pushed, the CAS succeeds against a head that merely looks unchanged. That is the ABA problem, and it installs a stale next pointer into the stack. Both problems come from freeing memory too early, which is why the code calls retire instead of delete.

The Michael-Scott queue and helping

The Michael-Scott queue (1996) is the basis of Java's ConcurrentLinkedQueue and many C++ libraries. It keeps a dummy node so that head and tail never point at nothing, and it needs two CASes to enqueue: one to link the new node after the last node, one to swing the tail pointer forward. Between those two steps the tail lags. Instead of waiting for the enqueuer to finish, any thread that sees a lagging tail advances it itself. This helping is the signature technique of lock-free design: no operation is ever stuck behind a half-finished one, because the half-finished state is valid and anyone can complete it.

enqueue(v):
    node = new Node(v, next = null)
    loop:
        t    = tail.load(acquire)
        next = t.next.load(acquire)
        if t != tail.load(acquire): continue            # tail moved under us
        if next == null:
            if CAS(t.next, null, node):                 # linearization point
                CAS(tail, t, node)                      # may fail: someone helped
                return
        else:
            CAS(tail, t, next)                          # help the lagging enqueuer

dequeue():
    loop:
        h = head.load(acquire); t = tail.load(acquire); next = h.next.load(acquire)
        if h != head.load(acquire): continue
        if next == null: return EMPTY
        if h == t: CAS(tail, t, next); continue         # tail lagging behind head
        v = next.value                                  # read BEFORE the CAS
        if CAS(head, h, next):
            retire(h)                                   # old dummy, reclaimed later
            return v

The re-reads of tail and head guard against acting on a snapshot that became inconsistent between loads. The value is read before the dequeue CAS because afterwards another dequeuer may retire that node.

ABA and safe memory reclamation

In a garbage-collected runtime, reclamation is solved for you: a node cannot be reused while any thread holds a reference, which also removes the pointer-reuse form of ABA. That is a large part of why lock-free code is so much more common in Java than in C++. Without a collector you choose one of three families.

• Tagged pointers. Pair the pointer with a counter that increments on every update and CAS both together, using a double-width CAS (CMPXCHG16B on x86-64) or spare high bits. Fixes ABA, but not use-after-free, so it suits pools that never return memory to the allocator.
• Hazard pointers. Each reader publishes the pointer it is about to dereference in a per-thread slot, then re-checks that the source still points to it. A retiring thread frees a node only when no slot holds it. Memory overhead is bounded, at the price of a store-load fence per protected read. Details in the hazard pointers article.
• Epoch-based reclamation and RCU. Readers announce entry into a critical region; retired nodes are freed after every thread has passed through a later epoch. Reads are nearly free, but one stalled reader blocks all reclamation and memory grows without bound.

C++26 standardises both std::hazard_pointer (paper P2530) and RCU (P2545), based on Folly's production implementations. Until your toolchain ships them, use Folly, libcds, or Rust's crossbeam-epoch rather than inventing a scheme.

Worked example: a wait-free SPSC ring buffer

Most systems that need lock-free behaviour do not need a general queue; they need to hand items from one thread to another without blocking, as in an audio callback, a network poll loop or a logger. A bounded single-producer single-consumer ring buffer does that with no CAS at all, just acquire and release on two indices, and it is wait-free on both sides.

template <typename T, size_t N>            // N must be a power of two
class SpscRing {
    static_assert((N & (N - 1)) == 0);
    alignas(64) std::atomic<size_t> head_{0};   // written only by the consumer
    alignas(64) std::atomic<size_t> tail_{0};   // written only by the producer
    alignas(64) T buf_[N];
public:
    bool try_push(const T& v) {                               // producer thread only
        size_t t = tail_.load(std::memory_order_relaxed);     // our own index
        if (t - head_.load(std::memory_order_acquire) == N) return false;   // full
        buf_[t & (N - 1)] = v;
        tail_.store(t + 1, std::memory_order_release);        // publishes buf_[t]
        return true;
    }
    bool try_pop(T& out) {                                    // consumer thread only
        size_t h = head_.load(std::memory_order_relaxed);
        if (tail_.load(std::memory_order_acquire) == h) return false;       // empty
        out = buf_[h & (N - 1)];
        head_.store(h + 1, std::memory_order_release);        // frees the slot
        return true;
    }
};

Trace one item. The producer writes slot 0, then release-stores tail_ = 1. The consumer acquire-loads tail_, sees 1, and is therefore guaranteed to see the bytes of slot 0. It copies them out and release-stores head_ = 1, which the producer's acquire load uses to know the slot may be overwritten. Indices grow without wrapping logic because unsigned subtraction handles overflow. The alignas(64) keeps the two indices on different cache lines, so the producer and consumer stop invalidating each other on every operation; removing it is a classic way to lose most of the throughput. For many producers, the usual next step is a sequence-numbered slot array in the style of Dmitry Vyukov's bounded MPMC queue, where each slot carries its own counter and producers claim slots with one fetch-add or CAS.

Failure modes

• ABA. A CAS succeeds against a recycled address and splices in stale links. Symptom: lost or duplicated elements under load, never in unit tests. Fix with safe reclamation or tagged pointers.
• Use-after-free during traversal. A reader dereferences a node another thread freed. Often reads garbage silently and crashes far away. AddressSanitizer with stress tests finds many cases.
• Weak ordering that works on x86. Relaxed loads where acquire was needed. Run the test suite on ARM hardware in CI, not only on developer machines.
• Retry storms. Under contention most CAS attempts fail and each failure costs a cache-line transfer. Add exponential backoff, or shard the structure so threads rarely collide.
• Unbounded memory. An epoch scheme with a stalled reader, or an unbounded queue with a slow consumer, grows until the process is killed. Bound queues and alert on the retire-list length.

Testing, operations and trade-offs

Test lock-free code with tools that explore interleavings rather than hoping for them: ThreadSanitizer for data races, Relacy or CDSChecker for C++, loom for Rust, and jcstress for Java. Then benchmark at your deployed thread counts against a plain mutex version; the guide to diagnosing lock contention shows how to tell whether the lock was ever your bottleneck. In production, export the CAS retry rate and queue depth. A rising retry rate is the earliest sign that contention, not work, is consuming your cores.

What to do next

1. Prove the need first: profile, and confirm a lock is the bottleneck or that blocking is unacceptable.
2. Prefer a library structure (java.util.concurrent, Folly, crossbeam, Boost.Lockfree) over your own.
3. If you write one, start from an SPSC ring or a published algorithm, not a design of your own.
4. Choose the reclamation scheme before writing the first CAS.
5. Use seq_cst first; weaken orderings only with a benchmark and a comment naming each pairing.
6. Pad hot atomics to separate cache lines.
7. Run ThreadSanitizer, a model checker or jcstress, and run CI on ARM as well as x86.
8. Export retry counts and queue depth so contention shows up on a dashboard, not in an incident.