Lock-Free Data Structures Explained: How Compare-And-Swap Powers Concurrent Programming Without Mutexes

Mutexes are the easy answer to “how do multiple threads touch the same data safely,” but they come with a cost: any thread that can’t get the lock simply stops, and if the thread holding the lock gets preempted, descheduled, or crashes mid-critical-section, every other thread waiting on it stalls too. Lock-free data structures solve the same safety problem without ever making a thread wait for another thread to finish — and the mechanism that makes that possible, in nearly every real implementation, is a single hardware instruction: compare-and-swap.

What Compare-And-Swap Actually Does

Compare-and-swap (CAS) is an atomic CPU instruction with three inputs: a memory location, an expected old value, and a new value. The hardware checks, as one indivisible operation, whether the memory location still holds the expected old value; if it does, it writes the new value and reports success, and if it doesn’t (because some other thread changed it first), it reports failure and changes nothing. No lock is taken at any point — the atomicity comes directly from the CPU, not from blocking other threads.

The standard pattern built on top of CAS is “read, compute, try to commit, retry on failure”:

def atomic_increment(counter):
    while True:
        old_value = counter.load()
        new_value = old_value + 1
        if counter.compare_and_swap(old_value, new_value):
            return new_value
        # else: another thread won the race, retry with a fresh read

Every thread doing this is making genuine progress on every attempt, even the failed ones — a failed CAS only happens because some other thread’s CAS just succeeded. That’s the core guarantee of lock-freedom: the system as a whole always makes progress, even though any individual thread could, in a worst case, keep losing the race indefinitely.

Lock-Free vs. Wait-Free vs. Obstruction-Free

These terms get used loosely, but they describe a strict hierarchy of guarantees:

• Obstruction-free: a thread running completely alone (no contention) is guaranteed to finish in a bounded number of steps. Under contention, it might never finish.
• Lock-free: the system as a whole is guaranteed to make progress — at least one thread always succeeds eventually — but no individual thread is guaranteed to ever succeed; it can theoretically keep losing CAS races forever (this is called “starvation,” and is a real, if rare, risk in practice).
• Wait-free: every individual thread is guaranteed to finish in a bounded number of steps, regardless of what any other thread does. This is the strongest guarantee and the hardest to implement; wait-free algorithms exist for specific structures but are far less common than lock-free ones.

Most of what’s loosely called “lock-free programming” in production systems — lock-free queues, lock-free hash tables, lock-free linked lists — is lock-free in this specific technical sense, not wait-free.

The ABA Problem

CAS has a well-known correctness trap called the ABA problem. CAS only checks that a memory location’s value matches what you expect — it has no way to know whether that value changed and changed back in between your read and your CAS. Concretely: thread 1 reads a pointer pointing at node A, gets preempted; thread 2 removes A, frees it, and later allocates a new node that happens to get the same memory address and value, call it A again; thread 1 resumes and its CAS succeeds because the value matches A — even though the actual node it was targeting was freed and replaced in between. The fix is usually to pair every pointer with a version counter (a “tagged pointer” or “stamped reference”) and CAS the pair together, so a value can never silently reappear as itself without the version also changing.

Why Reach for This At All

Lock-free structures earn their complexity in a specific situation: high-contention, low-latency paths where a blocked thread is unacceptably expensive — think a shared counter or queue hit by many threads per microsecond, a real-time audio or trading pipeline that can’t tolerate priority inversion (a low-priority thread holding a lock a high-priority thread needs), or kernel and allocator internals where a deadlocked lock could hang the whole system. They are not generally a free performance win: CAS retries under heavy contention can burn more CPU cycles than a well-tuned mutex would, and lock-free code is considerably harder to write correctly and reason about than lock-based code. Most application code should reach for a mutex, a well-tested concurrent collection from the standard library, or message-passing concurrency (channels, actors) long before reaching for hand-rolled CAS loops.

Bottom Line

Lock-free data structures trade the simplicity of “one thread at a time” for a guarantee that no thread ever blocks waiting on another — built almost entirely on the atomic compare-and-swap instruction and a retry loop. That guarantee is valuable in specific high-contention, latency-sensitive contexts, and is paid for with real correctness hazards (the ABA problem chief among them) and implementation difficulty that make it a specialist’s tool rather than a default.

FAQ

Is lock-free code always faster than using a mutex?

Not always. Under heavy contention, repeated failed CAS attempts can waste more CPU time than a mutex would, which blocks waiting threads instead of spinning. Lock-free structures tend to win specifically when avoiding blocking (not raw throughput) is the priority.

What’s the difference between lock-free and wait-free?

Lock-free guarantees the overall system keeps making progress, but an individual thread could theoretically keep losing races and never finish. Wait-free guarantees every individual thread finishes in a bounded number of steps regardless of other threads — a strictly stronger and harder-to-achieve property.

What is the ABA problem in one sentence?

It’s the failure mode where a memory location’s value changes away from A and back to A between a thread’s read and its CAS, causing the CAS to wrongly succeed as if nothing had happened in between; it’s typically fixed by pairing the value with a version counter.