multithreading · advanced

Lock-Free SPSC Ring Buffer

A single-producer/single-consumer (SPSC) ring buffer is the workhorse low-latency queue. Because exactly one thread writes the head index and exactly one writes the tail, there is no contention on either, so no locks and no compare-and-swap are required — only plain atomic loads and stores over a fixed array whose power-of-two size lets index & (N-1) replace a modulo for wrapping (empty when head==tail, full when head-tail==N). Correctness rests on memory ordering: the producer writes the slot and then does head.store(release), while the consumer does head.load(acquire) before reading the slot; that release-acquire pair establishes a happens-before edge guaranteeing the consumer observes the fully written element with no torn or stale reads, and the producer's own read of head can be relaxed since it is the sole writer. It is fast because there are no locks, no CAS retry loops, and the contiguous storage is cache-friendly; the classic pitfall is false sharing — if head and tail occupy the same cache line, the producer's and consumer's writes ping-pong that line between cores, so pad each index onto its own 64-byte cache line with alignas(64), keep the element type small and trivially copyable, and batch operations where possible. (Multi-producer/multi-consumer queues, by contrast, do require CAS — see the Michael-Scott lock-free queue.)

The code

template <class T, size_t N> // N must be a power of two
struct SpscRing {
    alignas(64) std::atomic<size_t> head{0}; // producer writes
    alignas(64) std::atomic<size_t> tail{0}; // consumer writes
    T buf[N];
    bool push(const T& v) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h - tail.load(std::memory_order_acquire) == N)
            return false; // full
        buf[h & (N - 1)] = v;
        head.store(h + 1, std::memory_order_release); // publish
        return true;
    }
};

What this lesson walks through

1. 01One producer, one consumer → no CAS
2. 02Write the data, THEN publish head (release)
3. 03Full / empty from head − tail
4. 04Why it's fast — and the false-sharing trap

Exactly one thread writes head (the producer) and one writes tail (the consumer). Because each index has a single writer, plain atomic loads/stores suffice — no compare-and-swap, no locks.