Coding interview: How would you implement a bounded MPMC ring queue with sequence slots?

Prompt and context

Multiple producers and consumers share a fixed-capacity in-memory queue. Producers must not overwrite unconsumed items, and consumers must not read unpublished items. The fast path should avoid a mutex, while full and empty states may wait. Design the slot layout, enqueue/dequeue positions, memory orders, and close behavior.

What the interviewer evaluates

• Whether you use monotonic positions and per-slot sequences to distinguish empty, reserved, published, and consumed states.
• Whether CAS and acquire/release correctly make non-atomic payload data visible.
• Whether you handle non-power-of-two capacities, producer and consumer contention, and false sharing.
• Whether you explain waiting, timeouts, close, reclamation, and ABA boundaries.

Clarifying questions

1. Are elements fixed-size, movable objects, or pointers with external ownership?
2. Should full and empty return immediately, block, or time out?
3. After close, may consumers drain already-enqueued elements?
4. Does the runtime provide C++20 atomic::wait and notify?
5. Is the queue process-local or shared across processes?

30-second answer

I would keep monotonically increasing enqueue and dequeue positions, with a sequence tied to the absolute position in each slot. A producer CAS-reserves a position, writes the non-atomic payload, and release-stores a published sequence. A consumer acquire-loads that sequence, reads the payload, then release-stores the next writable sequence. Sequence differences distinguish full and empty states. Failed fast paths wait with atomic::wait or bounded backoff, and close state is part of the result contract.

Deep-dive answer

Step 1: Design slots and positions

For capacity N, maintain monotonic enqueuePos and dequeuePos; map a position to a slot with modulo. Each slot contains a sequence and payload. The sequence carries the slot’s round, so an index alone cannot mistake old data for a new item. Use safe modulo arithmetic for non-power-of-two capacities rather than a bit mask.

Step 2: Reserve a producer position

The producer reads the sequence for its candidate position. If it equals the expected writable value, the slot is available and the producer competes for enqueuePos with CAS. On CAS failure, reload and retry. If the sequence is behind the expected value, the queue may be full; return full, wait, or time out instead of advancing into future positions.

Step 3: Publish the payload

After reserving a position, the producer exclusively owns that slot and writes the payload. It then release-stores a sequence meaning “published at this position.” The consumer must acquire-load the sequence before reading a non-atomic payload; an atomic index alone does not prove that object initialization is visible.

Step 4: Consume and release

The consumer similarly CAS-reserves dequeuePos. It may read only when the slot sequence equals the expected published value. After reading, it release-stores the sequence for the next writable round. The next producer acquire-loads that value before overwriting the slot.

Step 5: Define memory order and false sharing

Position CAS provides atomic index updates; release/acquire on publish and release sequences create happens-before edges for the payload. Relaxed operations alone can expose unpublished data. Place producer and consumer positions, and hot sequences, on separate cache lines to reduce write invalidation.

Step 6: Handle waiting and close

When the fast path cannot proceed, wait on a position or sequence with atomic::wait; successful enqueue or dequeue calls notify_one or notify_all. The loop must handle timeouts and spurious wakeups. Publish close atomically: producers reject new items, while consumers either drain published slots or return closed according to the contract.

Step 7: Test contention and lifetime

Test capacity one, non-power-of-two capacity, more producers or consumers than slots, long full/empty alternation, and randomized delays. Use sequence numbers to check no loss, no duplicates, FIFO scope, and drain-on-close. Run ThreadSanitizer and stress tests for data races. If payloads are pointers, specify ownership and reclamation timing.

Model answer

Each slot stores a payload and monotonic sequence; the queue stores monotonic enqueue and dequeue positions. A producer CAS-reserves only when the sequence equals the current writable value, writes the payload, then release-publishes the sequence. A consumer acquire-observes the published value, reads the payload, and release-stores the next writable value. Sequence rounds distinguish empty, full, and reused slots; modulo handles non-power-of-two capacity. Separate cache lines reduce false sharing. Failed fast paths use atomic::wait with timeouts and spurious-wakeup loops. Close rejects new producers and drains published items according to the contract. Stress tests, ThreadSanitizer, and sequence checks cover contention and lifetime.

Common mistakes

• Using only head and tail indices, which cannot distinguish slot rounds and stale data.
• Letting a consumer read after a producer reserves but before it publishes the payload.
• Using relaxed publication without acquire/release visibility for the payload.
• Continuing to reserve positions after the queue is full and overwriting unconsumed data.
• Ignoring spurious wakeups, timeouts, and close in atomic::wait loops.
• Forgetting non-power-of-two capacity, false sharing, or pointer reclamation.

Follow-up questions

Follow-up 1: Why does every slot need a sequence?

An index is reused across rounds. The sequence binds a slot to an absolute position and distinguishes writable, published, and next-round states, preventing stale values from being accepted.

Follow-up 2: Why not make only the payload atomic?

Payloads can be composite objects; an atomic index does not mean initialization is visible. Release publication and acquire observation establish visibility for the complete non-atomic payload.

Follow-up 3: How long should a failed CAS spin?

There is no universal value. Spin briefly for short contention, then yield or wait for notification. Tune the policy with core count, capacity, and latency-target load tests.

Follow-up 4: How do you close without losing items?

Stop new producers first, then acquire-observe and drain published slots. Consumers return closed only after positions converge and no producer still owns a reserved slot.

Follow-up 5: Is this always lock-free?

The fast path avoids a mutex, but atomic::wait may block a runtime thread. Describe it accurately as a lock-free data structure with optional blocking waits rather than promising every path is lock-free.

Follow-up 6: How do you test ABA risk?

Use monotonic positions and a round sequence in each slot, then stress wraparound, delayed threads, and repeated CAS. An old observation must not regain eligibility after the slot has advanced rounds.