Lock-Free Data Structures

A mutex solves concurrency by refusing to let two threads touch shared data at once. That is simple and almost always correct, but it has a specific failure mode: if the thread holding the lock gets paused — descheduled by the OS, stalled on a page fault, or just slow — every other thread waiting on that lock stalls too. On a market-data thread feeding a pricing engine, one unlucky pause can turn into a multi-millisecond gap in the book. Lock-free data structures avoid that by never letting one thread's pause block another's progress: at least one thread is always guaranteed to make forward progress, no matter what the others are doing.

The idea: hardware does the "locking" atomically

The building block is a single CPU instruction, compare-and-swap (CAS): "if this memory location still holds the value I expect, replace it with a new value — atomically, as one indivisible step." No other thread can see a half-finished update. A lock-free structure is built entirely out of operations like this instead of lock()/unlock().

The classic example is a lock-free stack (a Treiber stack). Pushing a node means: read the current top, point the new node at it, then CAS the top pointer from the old value to the new node. If another thread pushed in between, the CAS fails — because the "expected" value no longer matches — and the thread simply retries with the new top. Nobody blocks; the loser of the race just loops again.

struct Node { int value; Node* next; };
std::atomic<Node*> top{nullptr};

void push(Node* n) {
    n->next = top.load(std::memory_order_relaxed);
    while (!top.compare_exchange_weak(
               n->next, n,
               std::memory_order_release,
               std::memory_order_relaxed)) {
        // n->next was updated to the current top by the failed CAS; retry
    }
}

Worked example: two threads racing to push

Stack starts empty (top = null). Thread A wants to push node X, thread B wants to push node Y, at nearly the same instant.

1. A reads top = null, sets X->next = null.
2. B reads top = null too (A hasn't written yet), sets Y->next = null.
3. A's CAS runs first: "is top still null? Yes." top becomes X. A's push succeeds.
4. B's CAS runs: "is top still null?" No — it's X now. CAS fails. B does not corrupt anything; it silently retries.
5. B reloads top = X, sets Y->next = X, retries the CAS: "is top still X? Yes." top becomes Y. B's push succeeds.

Final state: top = Y → X → null. Both pushes landed, in some serial order, with zero mutex and zero thread ever blocked waiting on the other.

Lock-free A: CAS ok B: CAS fails B: retry ok Both threads finish in roughly the same span; neither ever sleeps waiting for the other.

Where it shows up

Interviewers use "implement a thread-safe counter/stack/queue without a mutex" to check whether you understand CAS, the ABA problem (a value changes from A to B and back to A between your read and your CAS, so the check passes even though the structure changed underneath you — fixed with tagged pointers or hazard pointers), and memory ordering.

In a real system, lock-free structures live on the narrow set of paths where a mutex's worst case is unacceptable: the single-producer/single-consumer queue between a market-data thread and a strategy thread (see Single-Producer Single-Consumer Ring Buffers), atomic counters updated from an interrupt handler, and the hot path of an order gateway where one thread being descheduled must never stall another. Everywhere else — configuration, logging, anything off the hot path — a plain mutex is simpler, easier to reason about, and just as fast in practice.