Lock-free queues: SPSC and MPSC ring buffers

Why does a single writer per location need no atomics, and what really sets a queue's throughput?

A ring buffer is a fixed-size array used as a queue. Two indexes move around it in a circle: a tail (where the producer writes the next item) and a head (where the consumer reads the next item). When an index reaches the end of the array, it wraps to the start. A queue is "full" when the tail is one full lap ahead of the head, and "empty" when head equals tail.

SPSC means single producer, single consumer: exactly one thread writes and exactly one thread reads. MPSC means multiple producers, single consumer.

SPSC: the purest case

Start with SPSC, because its derivation is exact. It needs no atomic read-modify-write instruction at all. It needs only plain stores and loads with release/acquire ordering.

The reason is a principle worth remembering:

CAS exists to arbitrate between writers. With one writer per location, there is nothing to arbitrate. In an SPSC ring, only the producer writes tail and only the consumer writes head. Each side only reads the other's index.

#include <stdatomic.h>
#include <stdalign.h>
#include <stdbool.h>
#include <stddef.h>

#define CAP 1024                       /* power of two, so we can wrap with & */

typedef struct {
    alignas(64) _Atomic size_t head;   /* written only by the consumer */
    alignas(64) _Atomic size_t tail;   /* written only by the producer */
    alignas(64) long buf[CAP];
} Ring;

bool push(Ring *r, long v) {           /* producer thread only */
    size_t t = atomic_load_explicit(&r->tail, memory_order_relaxed);
    size_t h = atomic_load_explicit(&r->head, memory_order_acquire);
    if (t - h == CAP) return false;    /* full */
    r->buf[t & (CAP - 1)] = v;
    atomic_store_explicit(&r->tail, t + 1, memory_order_release); /* publish */
    return true;
}

bool pop(Ring *r, long *out) {         /* consumer thread only */
    size_t h = atomic_load_explicit(&r->head, memory_order_relaxed);
    size_t t = atomic_load_explicit(&r->tail, memory_order_acquire);
    if (h == t) return false;          /* empty */
    *out = r->buf[h & (CAP - 1)];
    atomic_store_explicit(&r->head, h + 1, memory_order_release);
    return true;
}

Note the alignas(64) lines. They are the most important lines in the code, as the next paragraph explains.

The dominant cost is false sharing, and the fix is padding

If head and tail sit in the same cache line, then every producer store invalidates the consumer's copy of the line it is reading, for every single item. Put them on separate lines and throughput improves by roughly an order of magnitude: from tens of millions of items per second to hundreds of millions. This is the central finding of the LMAX Disruptor, a well-known high-speed queue library from a trading firm. It is a layout result, not an algorithm result.

The second optimization: batch the publication

The producer does not need to publish every item. If it publishes every k items, one cache-line transfer is spread over k items. The fixed cost that sets the batch size is now a coherence transaction. This is the Batch-size law at nanosecond scale. The same law set the B-tree fanout (about 680 for a 16 KB page) and the merge fan-in (memory divided by an efficient read size). Here it sets the publish granularity against a 64-byte line.

The fixed cost has moved from the disk platter all the way into the cache coherence protocol, and the law survived the journey unchanged. This is the most complete example here of the clause "as hardware gets faster, the fixed cost migrates upward".

MPSC: arbitration, and the choice of primitive

With several producers, they must claim slots atomically so two producers never write the same slot. There are two common primitives.

• A CAS loop: read the tail, try to CAS it to tail+1, and if another producer won, try again. It works, but under contention the failure rate rises with utilization ρ. Retry storms are the 1/(1 − ρ) curve again: threads burn CPU and make no progress.
• Fetch-and-add: slot = atomic_fetch_add(&tail, 1). It never fails. The hardware serializes the callers and each gets a distinct slot in one instruction.

Prefer FAA over CAS wherever the operation permits it. It is also the difference between wait-free and merely lock-free (defined next).

Progress guarantees: get them right

Folklore mixes up three different promises.

("Descheduled" or "preempted" means the operating system paused the thread to run another one.)

"Lock-free is faster" is false as a general claim. What lock-free buys is immunity to one pathology: a thread is descheduled while it holds a lock, and the whole system stops. Under real contention, a lock-free structure spends CPU on failed retries, where a lock would have parked the waiting thread and let other work run. Its p99.9 latency can be worse than that of a well-implemented mutex. An uncontended lock acquisition takes about 20 ns, and it is often the right engineering choice. Choose lock-free for predictability under preemption, not for throughput.

Where this lives in data engineering

Kafka's producer record accumulator (the buffer that collects records before sending), Netty's event-loop queues, Flink and Spark network-buffer handoffs, log appenders, and the Disruptor pattern in exchange and trading infrastructure.

Also note: a bounded ring buffer is a backpressure mechanism. "Full" means the producer must block or drop. That is credit-based flow control (the sender may send only as much as the receiver has granted) implemented in memory. Sizing it is Little's Law: depth = arrival rate × service time. So the buffer size is set by the latency you are willing to hold, not by a round number.