The question this answers
What are the actual requirements on the queue between these two stages, and which of them is the one nobody wrote down?
Choosing the structure that sits between eight request threads producing audit records and two writer threads batching them to storage. Roughly 4 000 records per second, records are small, losing one is unacceptable, order within a session matters.
The queue's buffer and its head and tail indices — the only state shared between the eight producers and the two consumers. Records themselves transfer ownership on dequeue.
Every record enqueued is dequeued exactly once; head and tail are only ever observed in states consistent with the items actually present; and records with the same session id are dequeued in enqueue order.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The four requirements, stated before the implementation
A plain queue — the one in Queue in Data Structures & Algorithms — is a sequence with push at one end and pop at the other. Making it concurrent adds four independent decisions, and the reason so many pipelines have subtle bugs is that teams pick a class name and inherit four defaults instead of making four choices.
Thread safety, and for what shape. "Thread-safe" is not one property. Single-producer/single-consumer queues can be implemented with no locks at all and a couple of atomic index updates; multi-producer/multi-consumer queues need considerably more. A structure documented as safe for one producer is *not* safe for eight, and the failure is silent — it is the lost-update schedule from Producer / Consumer.
Ordering. FIFO is the default and often not the requirement. Sometimes you need priority (Priority Queue), sometimes LIFO is better under backlog because the newest item is the freshest, and very often — as here — you need per-key ordering rather than global ordering, which means partitioning by key rather than ordering the whole queue.
Blocking or not. A blocking take parks the consumer until an item arrives, which is efficient and makes shutdown a design problem. A non-blocking poll returns immediately with nothing, which makes the consumer a spin loop unless it has something else to do (Busy Waiting). A timed poll is the compromise and is usually the right default for a worker loop.
Capacity. Covered in full in Bounded vs Unbounded Queues, and it is the requirement most often left at "unlimited" by accident.
| Requirement | Options | What picking wrong looks like |
|---|---|---|
| Producer / consumer count | SPSC · SPMC · MPSC · MPMC | An SPSC ring used by eight producers: items silently overwritten, indices corrupt, no exception ever thrown |
| Ordering | FIFO · LIFO · priority · per-key FIFO | Global FIFO chosen when per-key was needed: correct, and a needless serialisation point across unrelated keys |
| Blocking behaviour | blocking take · non-blocking poll · timed poll | Non-blocking poll in a tight loop: one core pinned at 100% doing nothing at 3 a.m. |
| Capacity | bounded (count) · bounded (bytes) · unbounded | Unbounded: no enqueue ever fails and the process dies under load |
| Full-queue policy | block · reject · drop oldest · drop newest | Library default silently drops the newest item and returns success |
| Close / end-of-stream | built-in close · poison pill · external flag | No signal at all: consumers block forever on shutdown |
| Fairness | fair lock · unfair lock | Unfair by default: one producer starves under sustained load from others |
Why "thread-safe" is not a property of the queue alone
A queue whose every method is individually atomic still lets callers build races out of them. if (!q.isEmpty()) process(q.take()) is two atomic operations and one check-then-act race: between the check and the take, another consumer empties the queue. The queue behaved perfectly. The caller's invariant did not survive.
This is the general lesson of The Atomicity Illusion applied to a data structure: atomic *operations* do not compose into atomic *sequences*. The fix is not a better queue, it is an API that expresses the sequence as one operation — take() that blocks, or poll() that returns an optional — so there is no gap to interleave into.
The same trap appears with size(). Any value it returns is stale the instant it is returned, so if (q.size() < limit) q.put(x) is check-then-act with a capacity check bolted on outside the queue's own critical section. If you want a capacity check, it has to be inside the queue, which is what a bounded queue's offer() is for.
1// BROKEN — check-then-act. Two consumers pass isEmpty(), one gets nothing.2if (!queue.isEmpty()) {3 const job = queue.take() // may block forever, or return undefined4 process(job)5}6 7// BROKEN — capacity check outside the queue's critical section.8// Between size() and put(), seven other producers can fill the remaining slot.9if (queue.size() < CAPACITY) {10 queue.put(job) // may exceed CAPACITY, or throw, or block11}12 13// CORRECT — one operation, one decision, no gap to interleave into.14const job = await queue.poll({ timeoutMs: 250 })15if (job === undefined) {16 if (shuttingDown) return // the timed poll is also the shutdown check17 continue18}19process(job)20 21// CORRECT — the capacity decision happens inside the queue's own lock.22const accepted = queue.offer(job)23if (!accepted) metrics.rejected.inc()Lock-based, lock-free, and how to choose without folklore
A lock-based queue takes a mutex around the head/tail update. A lock-free queue uses compare-and-swap loops so that no single thread's suspension can block the others (Compare-and-Swap and the Retry Loop, Lock-Free Is a Progress Guarantee). The important thing to be clear about: lock-free is a progress guarantee, not a performance claim. It says some thread always makes progress. It does not say the queue is faster, and under high contention a CAS loop can retry many times and do worse than a well-implemented lock.
Choose by the requirement that actually applies. If a consumer might be descheduled while holding the lock and that is unacceptable — a real-time audio callback, a signal handler, an interrupt-adjacent path — you need lock-free because blocking there is a correctness failure, not a slowness. Otherwise use the well-tested bounded blocking queue in your standard library, and spend the attention you saved on capacity and shutdown, which is where the real bugs are.
The one case where lock-free is both easy and clearly worth it is single-producer/single-consumer over a ring buffer: two atomic indices, no CAS loop, no ABA problem, and a genuinely simple implementation. Anything beyond SPSC is subtle enough — memory ordering, the ABA problem, reclamation of popped nodes — that writing your own is a project, not a function (The ABA Problem: The Value Came Back, What a Memory Model Defines).
| # | Thread 1 | Thread 2 | Thread 3 | State |
|---|---|---|---|---|
| 1 | read tail (= node-40) | · | · | tail=node-40 |
| 2 | · | read tail (= node-40) | · | tail=node-40 |
| 3 | · | · | read tail (= node-40) | tail=node-40 |
| 4 | CAS tail: node-40 → node-41 — succeeds | · | · | tail=node-41 pushes=1 |
| 5 | · | CAS tail: node-40 → node-41b — FAILS (tail moved) | · | tail=node-41 pushes=1 |
| 6 | · | · | CAS tail: node-40 → node-41c — FAILS | tail=node-41 pushes=1 |
| 7 | · | re-read tail; CAS node-41 → node-42 — succeeds | · | tail=node-42 pushes=2 |
| 8 | · | · | re-read tail; CAS node-41 → node-42c — FAILS again | tail=node-42 pushes=2 |
| 9 | · | · | re-read tail; CAS node-42 → node-43 — succeeds | tail=node-43 pushes=3 |
Key points
- "Thread-safe" is not one property: SPSC, MPSC and MPMC are different structures, and using a single-producer queue with eight producers fails silently.
- Atomic operations do not compose —
isEmpty()thentake()is a check-then-act race even when both methods are individually correct. size()is stale the instant it returns; a capacity check belongs inside the queue, which is whatoffer()is.- The ordering requirement is usually per-key, not global; global FIFO over unrelated keys is a needless serialisation point.
- Lock-free is a progress guarantee, not a performance promise. Choose it when blocking is a correctness failure, not because it sounds faster.
- A timed poll is the pragmatic default for a worker loop: it avoids the spin of non-blocking and gives shutdown a natural check point.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • A lock-based queue takes one mutex, checks capacity or emptiness against a condition variable, mutates the buffer and indices, signals the opposite condition, and releases.
- • A bounded implementation keeps the capacity check inside that critical section so check and insert cannot be separated.
- • A blocking take waits on a "not empty" predicate in a loop — not an
if— because wakeups can be spurious and another consumer may have taken the item first (Spurious Wakeups: Why It Is `while`, Not `if`). - • A lock-free MPMC queue publishes nodes with compare-and-swap on head and tail, retrying on failure, and must solve safe reclamation of popped nodes and the ABA problem.
- • An SPSC ring buffer needs only two atomic indices with acquire/release ordering: the producer writes the slot then publishes the index, the consumer reads the index then the slot (Happens-Before: The Edge That Makes a Write Visible, Safe Publication: Handing Over a Finished Object).
- • C1 calls isEmpty() → false; C2 calls isEmpty() → false; C2 takes the only item; C1 takes and blocks forever (blocking API) or receives undefined and dereferences it (non-blocking). Check-then-act.
- • P1 reads size() = 99 against a limit of 100; P2 through P8 do the same; all eight put; the queue holds 107 items. The capacity check was outside the lock.
- • Eight producers CAS the tail: one succeeds per round, seven retry. No corruption, and seven threads did redundant work — the throughput cost of lock-free under contention.
- • SPSC used by two producers: both write slot[t] and both advance t. One item lost, one slot holding a stale entry, no error. The structure was correct for the shape it documented.
- • Blocking take with no close signal: producer exits, two consumers remain parked on "not empty", process never terminates cleanly (Draining a Pipeline).
- • The safe schedule: every operation is a single queue call whose check and mutation share one critical section, so no caller-level sequence exists to interleave into.
- • A well-implemented MPMC queue guarantees each item is returned to exactly one consumer, and that no consumer observes a partially constructed item.
- • It guarantees FIFO with respect to *enqueue completion order*, which for concurrent producers is whatever order their critical sections completed in — not the order the calls started.
- • It does NOT guarantee that a sequence of your calls is atomic. Composition is your problem.
- • It does NOT guarantee
size()is meaningful for a decision; it is a diagnostic, not a control input. - • A lock-free queue guarantees system-wide progress: some thread completes. It does NOT guarantee any particular thread completes, so starvation is possible (Wait-Free vs Lock-Free: Whose Progress Is Guaranteed).
- • A blocking queue does NOT guarantee a waiting consumer is ever woken if nothing signals it — the shutdown path is not the queue's responsibility unless it has a close.
- • Every enqueue and dequeue serialises on the same lock or the same cache line, making the queue the pipeline's single hottest structure (What Contention Actually Costs).
- • Head and tail sharing a cache line causes producers and consumers to invalidate each other's lines on every operation, even with a nearly-full buffer — pad them apart (False Sharing: Different Variables, Same Cache Line).
- • Lock-free CAS loops convert waiting into retrying: threads stay runnable and burn CPU rather than parking, which is better for latency and worse for total throughput under load.
- • A fair lock reduces starvation and costs throughput, because it forces handoff to the longest waiter instead of letting a running thread reacquire (Fairness).
- • Sharding — several queues keyed by hash — is the standard escape hatch, and it works precisely because the ordering requirement was per-key all along.
- • Silent corruption from using a single-producer structure with multiple producers.
- • Check-then-act races built from individually correct methods.
- • Lost wakeup when a signal fires before the waiter registers, leaving a consumer parked on a non-empty queue (Lost Wakeups: The Notify That Arrived Before the Wait).
- • Busy-wait CPU burn from a non-blocking poll in a tight loop.
- • ABA in hand-rolled lock-free queues: a pointer matches the expected value but the node it points to has been freed and reused (The ABA Problem: The Value Came Back).
- • Starvation of a producer or consumer under an unfair lock and sustained contention.
- • Shutdown hang from a blocking take with no end-of-stream signal.
- • When the two stages genuinely have different rates and different lifecycles — that is what a queue is for, and a correct one removes a whole class of coordination code.
- • When you use the library one, which has been tested at contention levels your test suite will never reach.
- • When ordering can be relaxed to per-key: sharding turns one contended queue into N uncontended ones and usually removes the bottleneck entirely.
- • When SPSC applies: a ring buffer between exactly two threads is fast, simple, and the one lock-free structure worth writing yourself.
- • When the handoff cost exceeds the work. Queueing a 200-nanosecond task costs more than doing it (Parallel Overhead).
- • When fan-in is extreme: 64 threads on one queue spend more time contending than working, and the fix is sharding, not a cleverer queue.
- • When you write your own MPMC lock-free queue. Memory ordering plus reclamation plus ABA is a research-grade problem and the bugs are unreproducible.
- • When a queue is used to hide a synchronous dependency: if the producer waits for the result, you built an RPC with worse error handling.
- • Depth and head age — depth for memory, age for latency, and neither substitutes for the other (Depth Is Not an Emergency; Age Is in Performance).
- • Enqueue and dequeue rates separately; equal rates with rising depth is arithmetically impossible, so a divergence means one of your counters is wrong.
- • Lock wait time on the queue lock, which distinguishes "the consumers are slow" from "the queue is the bottleneck" (Low CPU, High Latency: Lock Contention in Performance).
- • CAS retry count for lock-free implementations — the direct measure of wasted work under contention.
- • Consumer CPU while depth is zero: non-trivial CPU there means a spin loop instead of a blocking or timed wait (Busy Waiting).
- • Four requirements have to be decided and documented, and each one is a place a future change can silently violate an assumption.
- • Composition rules must be understood by everyone touching the queue, because the queue cannot protect callers from their own check-then-act sequences.
- • Sharding by key adds a routing function, N sets of metrics, and a rebalancing question when the key distribution is skewed (Hot Keys: When Aggregate Metrics Hide a Saturated Node in Performance).
- • Any hand-rolled lock-free implementation adds a permanent maintenance liability: the code cannot be reasoned about locally and cannot be tested into confidence.
- • A channel, when the language has one — same structure with close semantics and select already solved (Channels).
- • A semaphore around direct execution, when what you needed was a concurrency limit and not a buffer (Semaphores: Counting Permits as a Resource Limit).
- • Per-thread queues with work stealing, when contention on a single shared queue is the actual bottleneck (Work Stealing).
- • No queue: call the function. If the stages have the same rate and the same lifetime, the queue adds latency, memory and a shutdown protocol for nothing (Concurrency Is Always Bought With Complexity).
What people believe, and what is true
The class is documented thread-safe, so my usage is safe.
Each method is atomic; your sequence of methods is not. isEmpty() followed by take() is a race the queue cannot prevent.
Lock-free queues are faster.
Lock-free is a progress guarantee. Under contention CAS retries can make it slower than a blocking queue that parks the losers instead of spinning them.
We need global FIFO.
Usually the requirement is per-key FIFO. Assuming global order imposes a serialisation point across keys that have nothing to do with each other, and it is the most common cause of queue contention.