Lock-free queues, ABA and seqlocks

Three terms, often confused:

• Blocking. A thread that is suspended at the wrong moment, holding a lock, can stop every other thread.
• Lock-free. Some thread always makes progress: if threads keep running, the system as a whole does not stall, though an individual thread can be made to retry indefinitely.
• Wait-free. Every thread completes its operation in a bounded number of its own steps, whatever the others do.

The SPSC ring is wait-free: push and pop are a fixed sequence of instructions. A typical multi-producer queue is lock-free: a producer may lose a race and retry.

Lock-free is a statement about progress, not about speed. A well-designed mutex queue can outperform a lock-free one under contention, because the lock-free queue's atomics all hit the same cache line.

With several producers, the tail is no longer owned by one thread; producers must claim slots without clashing. The common bounded design gives each slot a sequence number:

// multi-producer, single-consumer bounded ring (sketch)
struct Slot { std::atomic<std::uint64_t> seq; Order value; };

bool push(const Order& o) {
    std::uint64_t pos = tail_.load(std::memory_order_relaxed);
    for (;;) {
        Slot& s = slots_[pos & (N - 1)];
        auto seq = s.seq.load(std::memory_order_acquire);
        if (seq == pos) {                                         // slot free for this lap
            if (tail_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) {
                s.value = o;
                s.seq.store(pos + 1, std::memory_order_release);  // publish to the consumer
                return true;
            }                                                     // lost the race: pos reloaded, retry
        } else if (seq < pos) return false;                       // full
        else pos = tail_.load(std::memory_order_relaxed);         // another producer moved on
    }
}

Producers compete only for the tail with a compare-and-swap; once a producer has claimed a position, it fills the slot and publishes it through the slot's own sequence number. The consumer waits on the sequence number of the slot it wants next. This is the design behind several widely used bounded queues.

Its weakness is the shared tail: every producer's CAS touches the same cache line, so throughput falls as producers are added. In trading systems a frequent alternative is one SPSC ring per producer, with the consumer polling each in turn. That keeps every queue wait-free and every line owned by two threads.

Unbounded lock-free structures built from linked nodes hit a classic bug. Take a lock-free stack with pop written as a compare-and-swap on the top pointer:

Node* pop() {
    Node* old = top_.load();
    while (old && !top_.compare_exchange_weak(old, old->next)) {}
    return old;
}

Thread 1 reads top = A and A's next = B, then is preempted. Thread 2 pops A, pops B (freeing it), and pushes A back, perhaps reusing the same node. Thread 1 resumes: the top is A again, so its CAS succeeds and sets top to B, a node that has been freed. The CAS checked that the value was the same, not that nothing had happened.

Fixes:

• Tagged pointers. Pair the pointer with a counter incremented on every change and CAS both together (a 16-byte CAS, or spare bits of the pointer). A recycled A has a different tag.
• Safe memory reclamation. Never free or reuse a node while another thread might still hold a pointer to it. Hazard pointers (each thread announces the pointers it is using), epoch-based reclamation and RCU all do this, and C++26 adds std::hazard_pointer and std::rcu.
• Avoid the problem. Bounded rings over preallocated arrays use indices and sequence numbers, not freed nodes, which is one reason they dominate in latency-sensitive code.

A different and very common pattern: one thread maintains a small piece of state, say the top of the book for an instrument, and many threads read it whenever they like. Readers must never slow the writer down.

A seqlock pairs the data with a sequence counter. The writer increments the counter to an odd number, writes the data, then increments it to an even number. A reader reads the counter, copies the data, reads the counter again, and keeps the copy only if both reads were equal and even; otherwise it retries.

struct TopOfBook { std::int64_t bid, ask; std::int32_t bid_qty, ask_qty; };

class SeqTop {
    std::atomic<std::uint64_t> seq_{0};
    TopOfBook data_;                    // see the note below on how it is copied
public:
    void write(const TopOfBook& t) {                      // single writer
        auto s = seq_.load(std::memory_order_relaxed);
        seq_.store(s + 1, std::memory_order_relaxed);     // odd: write in progress
        std::atomic_thread_fence(std::memory_order_release);
        data_ = t;
        seq_.store(s + 2, std::memory_order_release);     // even: done
    }
    TopOfBook read() const {
        for (;;) {
            auto s1 = seq_.load(std::memory_order_acquire);
            if (s1 & 1) continue;                         // writer busy
            TopOfBook copy = data_;
            std::atomic_thread_fence(std::memory_order_acquire);
            if (seq_.load(std::memory_order_relaxed) == s1) return copy;
        }
    }
};

The writer never waits for readers. Readers may retry, but a reader cannot block the writer, which is exactly the right trade for market data. One subtlety: the reader copies data_ while it may be being written, which is formally a data race on a non-atomic object even though the torn copy is then discarded. Production implementations copy the data through relaxed atomic word-sized loads, or use the compiler-specific guarantees their codebase relies on. Saying that out loud shows you know the memory model, not just the pattern.