8.3.3 Lock-Free Data Structures

Basic Prerequisites: 02 · Why Locks Are Slow and 04 · Memory Model & Ordering. Know what an atomic instruction is.

---

1. Intuition & Practical Objective

A lock-free data structure guarantees that if several threads contend, at least one makes progress - no thread is ever blocked on another. It does this by replacing mutual exclusion with two tools:

• Atomics - reads/writes/RMWs that the hardware guarantees to be atomic (indivisible), so no two threads can tear them.
• CAS (compare-and-swap) - if (ptr == expected) ptr = new; else fail executed atomically, so a thread can optimistically attempt an update and retry on failure instead of blocking.

The workhorse of a trading engine is the SPSC ring buffer: one producer, one consumer, a fixed array, two monotonic counters. It is lock-free in the strongest practical sense because it never even needs CAS - the single-writer invariant means each counter is written by exactly one thread, so there is no contention to arbitrate, only a release/acquire handshake (the ordering contract lives in 04 · Memory Model & Ordering; the architecture of where it sits in the pipeline is Pillar 2 · 04 Lock-Free & Ring Buffers).

The one-sentence essence. “A lock-free structure lets every thread try and retry on conflict instead of waiting; an SPSC ring goes further and designs the conflict out entirely by giving each counter a single writer, so passing a message is two stores plus a release/acquire handshake - a few nanoseconds, no blocking, no CAS.”

Why SPSC beats MPMC. Multiple producers must share the tail counter, which forces a CAS (an atomic RMW that serialises all producers on one cache line) and introduces the ABA problem. The Disruptor’s design insight is to stay single-writer: one producer, one (or a few) consumers with a shared read cursor that the producers read-mostly and consumers update - CAS appears only when you add multiple producers.

Progress guarantees (Herlihy & Shavit). Blocking (a thread can wait forever) → lock-free (some thread advances every step) → wait-free (every thread advances in bounded steps). The SPSC ring is lock-free; a fetch_add counter is wait-free.

---

2. Mathematical Ground Truth & Derivations

The ring and its invariants. Array $B$ of capacity $C=2^k$ (power of two ⇒ wrapping is a bit-mask, no division), monotonic unsigned counters head (consumer) and tail (producer):

$$\text{head}\le \text{tail},\text{occupancy}=\text{tail}-\text{head}\le C,\text{slot}=\text{index}\&(C-1).$$

Monotonic counters never wrap, so “full” ($\text{tail}-\text{head}=C$) and “empty” ($\text{tail}=\text{head}$) are distinguishable without wasting a slot. Correctness requires release/acquire ordering: the producer must publish the payload before the atomic store of tail (store-release), and the consumer must load tail with acquire semantics before reading the payload - otherwise a weakly-ordered CPU may make the consumer see the new tail before the payload bytes, reading garbage.

The atomic-RMW cost of MPMC. With $P$ producers sharing tail, every push needs a CAS or fetch_add that is an atomic RMW on one cache line - the same serialisation the lock had, just without blocking. Expected number of CAS retries under $P$ producers with collision probability $p$ is geometric: $\mathbb{E}[\text{retries}]=\frac{p}{1-p}$, growing with $P$. This is why “just add a producer” to an SPSC ring silently downgrades it to a contended structure.

Lock-free ≠ wait-free. A lock-free structure guarantees system-wide progress; an individual thread could in principle starve. Wait-free bounds per-thread steps. For hard real-time (a kill switch that must fire within a deadline) prefer wait-free or bounded-helping designs (06 · Advanced Extensions).

---

3. Computational Implementation - a runnable SPSC ring

Standard library only. This is a faithful simulation of the C++ SPSC protocol in CPython: under the GIL each integer read/write is atomic, so the single-writer handshake models the release/acquire contract - the producer writes the payload before advancing tail; the consumer reads head-then-tail. A producer thread and a consumer thread shuttle 100 000 items through a capacity-1024 ring.

All 100 000 items pass through exactly once, in order, with no loss and no duplication. (Wall time in CPython’s GIL sim is ~10 µs/item on this box - the GIL serialises the two threads, so the timing is not the point; what the sim proves is correctness: exact-once, in-order transfer. A real C++ std::atomic ring at the same capacity runs at true single-digit nanoseconds per item.) The producer and consumer never block each other - the only coordination is the two monotonic counters, each owned by one thread. In real C++ with std::atomic and alignas(64) the same protocol runs at true nanoseconds (see High-Performance C++ for the C++ realisation; the flat concurrency file carries the C++ class).

---

4. Failure Modes & First-Principles Breakdowns

1. Missing the release/acquire handshake. Publish the payload after advancing tail and the CPU may reorder; the consumer reads the new index and stale data - a “corrupt tick” once in a million messages. This is a correctness bug, not performance (see 04 · Memory Model).
2. False sharing on head/tail. Both counters on one cache line: every producer store invalidates the consumer’s line and vice-versa. Fix: alignas(64) padding (04 · Memory Model quantifies the 18x cost).
3. Silently adding a producer/consumer. SPSC correctness depends on exactly one writer per counter. A second producer breaks the invariant and requires CAS + ABA handling. Do not “just add a writer.”
4. ABA in a lock-free stack. A pointer goes A→B→A between the load and the CAS, so the CAS succeeds against a node that was deallocated and reused. Fix: tagged/DCAS pointers or a monotonic generation counter.
5. Unbounded growth or drop ambiguity. A ring that grows to absorb overload converts a bounded-latency problem into an unbounded one; a ring that drops must signal staleness explicitly (see the capacity trade in Pillar 2 · 04 Lock-Free & Ring Buffers).

---

5. References

• Herlihy & Shavit, The Art of Multiprocessor Programming
• Williams, C++ Concurrency in Action
• Preshing, Jeff - An Introduction to Lock-Free Programming
• LMAX, The Disruptor (paper + library) and Fowler, The LMAX Architecture
• Thompson, Martin - Mechanical Sympathy (cache-line effects and false sharing in lock-free structures).

---

6. Connected Graph Bridges

• Back: 02 · Why Locks Are Slow · Index Hub
• Forward: 04 · Memory Model & Ordering · 05 · Failure Modes
• Cross-pillar (architecture, not duplicate): 04 · Lock-Free & Ring Buffers · Low-Latency Systems Architecture
• Base: High-Performance C++ for Trading (the C++ realisation)