Lock-Free Queues, in depth: what FIFO means under concurrency, the SPSC-to-MPMC ladder, Vyukov's MPSC queue, fetch-and-add designs and a stress harness

What a correct concurrent queue promises

The standard correctness condition is linearizability (Herlihy and Wing, 1990). Every operation must appear to take effect at a single instant between its call and its return, and the resulting order must be a legal sequential queue history. Two things follow that people forget. First, FIFO is only defined between operations that do not overlap in time. If two producers call offer at the same moment, either order is correct. What you can promise is that items from a single producer come out in the order that producer put them in. Second, "empty" is a statement about an instant. By the time poll() returns null, a producer may already have finished an enqueue, so code that treats null as "the work is done" has a race.

Progress guarantees are a separate axis. Lock-free means that some thread always completes an operation in a finite number of steps, even if others are suspended. Wait-free means every thread does. Obstruction-free only promises completion to a thread running alone. Many fast queues are none of these: they are non-blocking in the common case but contain a window where a suspended thread stalls others. Calling those queues lock-free is common and imprecise. The difference matters if your threads can be descheduled for milliseconds, as they can in a container with a CPU quota.

The SPSC-to-MPMC ladder

Every restriction on who may call which end removes a contention point, and the speed differences are large. Choose the most restricted variant your topology allows, and enforce the restriction in code, because an SPSC queue used by two producers corrupts silently.

Each variant also comes bounded (a ring buffer of fixed capacity) or unbounded (linked nodes or linked array chunks). Bounded queues allocate nothing in steady state and give you backpressure for free: offer fails when the ring is full. Unbounded queues never reject work, so overload shows up as heap growth, not as an error you can handle.

The Michael-Scott queue (PODC 1996) is the reference MPMC linked design. A dummy node separates head from tail. Enqueue CASes the last node's next from null to the new node, then tries to swing tail forward. Any thread that finds the tail lagging helps by advancing it first, and that helping is what makes it lock-free. Dequeue CASes head to its successor. The lock-free data structures architecture article traces it line by line, and the introductory builds article implements the bounded MPMC ring with per-cell sequence numbers, so neither is repeated here.

Vyukov's intrusive MPSC queue

Dmitry Vyukov's intrusive MPSC queue is the fastest linked design in common use, and it shows how fine-grained progress guarantees are. Producers do one atomic exchange on tail and one plain store. They never retry, so the producer side is wait-free. The consumer owns head outright and needs no atomic read-modify-write at all.

final class MpscQueue<T> {
    static final class Node<T> {
        final T value; volatile Node<T> next;
        Node(T v) { value = v; }
    }
    private final AtomicReference<Node<T>> tail;
    private Node<T> head;                         // consumer-only field

    MpscQueue() { Node<T> stub = new Node<>(null); head = stub; tail = new AtomicReference<>(stub); }

    void offer(T v) {
        Node<T> n = new Node<>(v);
        Node<T> prev = tail.getAndSet(n);         // fixes this item's position in the order
        prev.next = n;                            // until this store, the chain is broken
    }

    T poll() {                                    // call from ONE thread only
        Node<T> next = head.next;
        if (next == null) return null;            // empty, or a producer is mid-offer
        head = next;
        return next.value;
    }
}

The exchange is the linearization point: it fixes each item's position in the order. The cost is the gap between the exchange and prev.next = n. If a producer is descheduled there, the consumer reaches prev, reads a null next and reports empty, even though later producers may have finished and their nodes are queued behind the gap. Nothing is lost: the items reappear when the suspended producer runs again. But the consumer cannot make progress past the gap, so the queue as a whole is not lock-free. In practice the window is two instructions long and this is the right trade for actor mailboxes and event loops. It is the wrong trade if a producer can be suspended for a long time, for example in a signal handler or across a page fault on a memory-mapped node pool. Use it with a wake-up protocol: the consumer parks after seeing null, and a producer that finds the consumer parked unparks it.

Fetch-and-add: why CAS loops collapse

Under heavy contention, CAS loops degrade. All producers read the same tail, all CAS it, one wins, and the losers have pulled the cache line into their cores for nothing before retrying. The more threads you add, the more of the line's time goes to failed attempts. Fetch-and-add (LOCK XADD on x86, LDADD on Armv8.1 LSE) always succeeds. Every caller gets a distinct ticket in one round trip, so the line still bounces but no work is thrown away.

The FAA queue literature starts from an idealized queue over an infinite array, sketched below. It is not production code: the array is unbounded and the empty check is simplified.

enqueue(x):
    loop:
        t = FAA(tail, 1)                    # private ticket, never retried
        if CAS(cell[t], EMPTY, x): return   # fails only if a dequeuer poisoned the cell
dequeue():
    loop:
        h = FAA(head, 1)
        v = SWAP(cell[h], TAKEN)            # poison the cell if the enqueuer is late
        if v != EMPTY: return v
        if load(tail) <= h + 1: return EMPTY

A dequeuer that overtakes its matching enqueuer poisons the cell, and the enqueuer then takes a new ticket. Morrison and Afek's LCRQ (PPoPP 2013) makes this practical with ring segments linked into a list, at the price of a double-width CAS. Yang and Mellor-Crummey (PPoPP 2016) built a wait-free queue on the same fetch-and-add backbone. The practical message: under heavy MPMC contention, a queue built on FAA tickets scales where CAS-on-tail designs flatten. Below a handful of contending threads the difference is small. Measure before you switch.

Worked example: a harness that catches lost items

Correctness claims need a harness that checks the two properties that matter: every item arrives exactly once, and each producer's items arrive in order. Encode the producer id in the high 32 bits and a per-producer sequence number in the low bits. The single consumer then checks both properties with one array and no locks:

static String run(String name, Q q, int producers, int perProducer) throws Exception {
    Thread[] ts = new Thread[producers];
    for (int p = 0; p < producers; p++) {
        final long base = (long) p << 32;
        ts[p] = new Thread(() -> { for (int i = 0; i < perProducer; i++) q.offer(base | i); });
    }
    for (Thread t : ts) t.start();
    long[] lastSeen = new long[producers];
    Arrays.fill(lastSeen, -1);
    long total = (long) producers * perProducer, got = 0, orderErrors = 0;
    long deadline = System.nanoTime() + 5_000_000_000L;      // a lost link must not hang CI
    while (got < total && System.nanoTime() < deadline) {
        Long v = q.poll();
        if (v == null) { Thread.onSpinWait(); continue; }
        int p = (int) (v >>> 32); long seq = v & 0xFFFFFFFFL;
        if (seq != lastSeen[p] + 1) orderErrors++;
        lastSeen[p] = seq; got++;
    }
    for (Thread t : ts) t.join();
    return name + " received=" + got + "/" + total + " orderErrors=" + orderErrors;
}

Run with four producers and one million items each on Java 23 (32 hardware threads), the queue above passed three rounds: 4,000,000 received, zero order errors. So did ConcurrentLinkedQueue. Wall-clock time was 0.4 to 1.2 seconds for the MPSC queue and 1.9 to 2.3 seconds for ConcurrentLinkedQueue. That is one noisy machine, so read it as a direction, not a benchmark.

Then the harness ran a broken variant that replaces tail.getAndSet(n) with prev = tail.get(); tail.set(n);, with a spin hint between them to widen the race window. Two producers can now read the same prev, and one link overwrites the other. The consumer received 232 of 4,000,000 items before the five-second deadline. A whole branch of the chain was orphaned, and the consumer was stuck at a null next for good. A unit test that enqueues ten items on one thread would never see this. For memory-model bugs that only appear on weakly ordered hardware, add jcstress (Java) or ThreadSanitizer (C++) to this harness. The lock-free stack article shows a jcstress setup.

What the libraries ship

Writing your own is rarely justified. What ships:

• Java: ConcurrentLinkedQueue (unbounded MPMC, Michael-Scott based; its size() walks the list and is not exact under concurrency). JCTools provides SPSC, MPSC, SPMC and MPMC array queues plus linked and chunked unbounded MPSC variants, and Netty ships a shaded copy for its event loops.
• C++: Boost.Lockfree has boost::lockfree::queue (MPMC, element type must be trivially copyable and destructible) and spsc_queue. Both can run from a fixed node pool so the hot path never allocates. Check is_lock_free() on your target, because the guarantee depends on the platform's atomics.
• Rust: crossbeam's ArrayQueue (bounded MPMC) and SegQueue (unbounded, segmented).
• Ring-buffer pipelines: the LMAX Disruptor replaces the queue abstraction with sequences and barriers when consumers form a graph.

Operational guidance

• Prefer bounded. Size the ring for the burst you must absorb. On a full ring, decide explicitly whether to drop, block or shed load, and count every rejection.
• Do not spin forever. Busy-polling burns a core. Combine a short spin with onSpinWait or PAUSE, then park, with a waiting flag the producer checks after it publishes.
• Pad the hot indices. Head and tail on the same cache line ping-pong between producer and consumer cores. JCTools pads them with inheritance-based field layout. In C++, use alignas(64) or std::hardware_destructive_interference_size.
• Batch. Drain many items per wake-up and publish an index once per batch. This often helps more than a cleverer algorithm.
• Reclaim memory safely in non-GC languages. A linked MPMC queue in C++ needs hazard pointers or epochs before a dequeued node can be freed. See the hazard pointers article.
• Observe depth cheaply. Export tail minus head as a sampled gauge, not a per-operation counter. A shared atomic counter reintroduces the contention you removed.

Failure modes

• Topology violation: a second producer on an SPSC queue, or two consumers on an MPSC queue. Data is silently duplicated or lost. Assert the owning thread in debug builds.
• Missing release/acquire: the consumer sees the published index before the item's fields. This is invisible on x86 and shows up on Arm servers and phones.
• ABA in C/C++: a freed and reused node passes a CAS that should fail. Tagged pointers, hazard pointers or epochs prevent it. A GC prevents it only for references, not for recycled array indices.
• Treating null as done: shutdown code that stops on the first empty poll drops items still in flight. Drain until producers have exited and the queue reads empty after a final fence.
• Unbounded growth: a slow consumer behind an unbounded queue turns latency into memory and then into an out-of-memory kill.
• Preemption windows: the MPSC gap or a Vyukov ring cell claimed by a descheduled thread stalls consumers. Tail latency spikes line up with CPU-quota throttling.

What to do next

1. Write down your producer and consumer counts and pick the most restricted queue that fits, from a library.
2. Copy the harness above, run it against your chosen queue with more producers than cores, and add it to CI with a deadline.
3. Make the queue bounded unless you can justify unbounded memory growth. Implement and count the full-queue policy.
4. Add a park/unpark wait strategy and measure CPU use at idle.
5. On Arm hardware, run the same harness, plus jcstress or ThreadSanitizer, before trusting a hand-written queue.