Designing MPMC Queues: Balancing Bounded Waiting and High-Performance Concurrency

Why Concurrent Queues Are the Cornerstone of High-Performance Systems

In modern high-performance systems, the Multi-Producer Multi-Consumer (MPMC) queue is one of the most fundamental data structures in concurrent programming. Whether in message middleware, task schedulers, or high-frequency trading systems, the MPMC queue plays the critical role of connecting execution threads and coordinating data flow. Research in this area dates back to the rise of multiprocessor systems in the 1980s—the MS queue proposed by Michael & Scott in 1996 was a milestone in lock-free queues, and the bounded MPMC implementation released by Dmitry Vyukov around 2010 remains the most widely referenced benchmark in industry to this day. Well-known modern implementations include the LMAX Disruptor (a financial trading framework), Intel TBB's concurrent_queue, and Java's LinkedTransferQueue, all of which draw deeply on the core design ideas in this field. However, simultaneously achieving "high throughput" and "bounded waiting" while guaranteeing correctness has always been a classic challenge in the concurrency domain.

The talk Girls Just Wanna Have Fast MPMC Queues with Bounded Waiting has a somewhat playful title, but it addresses a rather hardcore problem: how to design a multithreaded queue that is both fast and provides fairness guarantees. This article explores this topic in depth, analyzing the design challenges and key trade-offs of MPMC queues.

What Is "Bounded Waiting," and Why Does It Matter

Lock-Free Does Not Mean Wait-Free

Many developers habitually equate "lock-free" with "never blocks," but this is a common misconception. In concurrency theory, progress guarantees are divided into the following levels:

• Obstruction-free: A single thread can complete its operation when there is no interference.
• Lock-free: The system as a whole always has some thread making progress, but certain threads may be delayed indefinitely.
• Wait-free: Every thread can complete its operation in a finite number of steps.

The formal definition of wait-free algorithms was established by Maurice Herlihy in his 1991 paper Wait-Free Synchronization. Herlihy also introduced the concept of "consensus number": the consensus number of the CAS operation is infinite, meaning that CAS alone can be used to construct wait-free algorithms for any number of threads. However, there is a vast gap between theoretical feasibility and efficient engineering implementation—early wait-free queue algorithms (such as the WF queue by Kogan & Petrank in 2011) often had lower actual throughput than lock-free implementations due to the constant-factor overhead introduced by helping mechanisms, until subsequent research introduced fast/slow path separation to gradually close the gap.

Bounded waiting sits precisely between lock-free and wait-free—it guarantees that any thread's waiting time has a clearly defined upper bound, thereby fundamentally eliminating the starvation problem. For systems with real-time or fairness requirements, this property is of great significance.

Why Bounded Waiting Is Hard to Achieve

High throughput typically relies on an optimistic CAS (Compare-And-Swap) retry mechanism, which inherently may cause certain threads to fail repeatedly. CAS is an atomic instruction provided by modern CPUs and is the cornerstone of lock-free concurrent algorithms. Its semantics are: only when the current value at a memory address equals an expected value is it updated to a new value, and the entire operation is indivisible. The x86 architecture implements it via the CMPXCHG instruction, while the ARM architecture uses the LDREX/STREX instruction pair. The core problems with CAS are the ABA problem (a value changes from A to B and back to A, which CAS cannot detect) and the risk of livelock under high contention—when contention is intense, an "unlucky" thread may be unable to complete an enqueue or dequeue for a long time, undermining fairness. Therefore, designers must find a delicate balance between performance and fairness.

Core Design Challenges of MPMC Queues

Contention Hotspots and False Sharing

The performance bottleneck of MPMC queues usually concentrates on contention over the head and tail pointers. When multiple producers update the tail pointer and multiple consumers update the head pointer simultaneously, CPU cache lines are frequently transferred between cores, creating the "cache line ping-pong" phenomenon that severely drags down throughput.

Understanding this phenomenon requires a deep understanding of how modern CPU caches work: caches transfer data in units of cache lines (typically 64 bytes), and the MESI protocol is responsible for maintaining cache coherence across multiple cores. The four states of the MESI protocol (Modified/Exclusive/Shared/Invalid) describe the state machine of cache line sharing across cores—when a core acquires a cache line for a write operation, all other cores holding that cache line must set it to the Invalid state. This process is implemented by broadcasting RFO (Request For Ownership) messages over the on-chip interconnect bus. On a 64-core server, a single cache line invalidation propagation may trigger dozens of cross-NUMA-node message transfers, with latency as high as 300–500 nanoseconds—far exceeding the 4-nanosecond access time of the L1 cache. When multiple cores simultaneously modify different variables within the same cache line, even if these variables are logically independent, the cache coherence protocol forces the cache line to be repeatedly invalidated and transferred between cores—a phenomenon known as False Sharing. Solutions include using __attribute__((aligned(64))) or C++17's std::hardware_destructive_interference_size to align data structures to cache lines, and padding hotspot variables with padding bytes to ensure they occupy separate cache lines.

Mainstream high-performance queues (such as Dmitry Vyukov's classic bounded MPMC implementation) address this with a sequence-number-based slot mechanism: each slot in the ring buffer carries an independent sequence number. Before enqueuing, a producer finds the target slot by taking the tail pointer modulo the queue capacity, then checks whether the slot's sequence number matches the tail pointer value; if it matches, it advances the tail pointer via CAS and writes the data, while updating the sequence number to tail+1. The consumer logic is symmetric: it checks whether the sequence number equals head+1, and if it matches, reads the data and updates the sequence number to head+capacity. This design distributes the write contention on the global head and tail pointers across the sequence numbers of individual slots, significantly reducing cache line conflicts.

Ring Buffers and Memory Reclamation

Bounded queues are typically implemented on top of ring buffers, combining the advantages of fixed memory footprint and good cache locality. Unbounded queues, on the other hand, face the thornier problem of memory reclamation—how to safely free already-dequeued nodes while preventing "use-after-free" when other threads are still accessing them.

Such problems usually require dedicated techniques to solve. Hazard Pointers, proposed by Maged Michael in 2004: each thread maintains a set of "hazard pointers," recording the address of a shared node before accessing it; the reclaimer must scan the hazard pointer lists of all threads and confirm the node is no longer referenced before freeing it. The memory overhead of hazard pointers grows linearly with the number of threads, and reclamation requires O(N×K) scanning overhead (N being the number of threads, K being the maximum number of nodes held simultaneously in a single operation). Epoch-Based Reclamation (EBR) divides time into epochs, and the system waits until all threads have advanced to a new epoch before batch-reclaiming old objects, yielding higher overall throughput. Both Facebook's Folly library and Rust's crossbeam library adopt EBR variants; however, its fatal weakness is that if a thread is blocked for a long time, the system's epoch cannot advance, causing memory backlog to keep growing. The Rust community developed hybrid solutions such as "seize" for this, combining the advantages of both. Each solution has its own focus, and the choice should be weighed according to the specific scenario.

The Art of Trading Off Performance and Fairness

Dual-Track Design: Fast Path and Slow Path

A common strategy for achieving "both fast and fair" is the dual-path design:

• Fast path: Under low contention, threads take the optimistic CAS path, achieving extremely high throughput.
• Slow path: When repeated failures are detected (indicating intense contention or potential starvation), threads switch to a path with queuing or helping mechanisms to guarantee bounded waiting.

This design philosophy is widely applied in modern concurrent algorithms—pairing "high performance under normal conditions" with "progress guarantees in extreme cases," avoiding sacrificing the practical performance of the vast majority of scenarios for a theoretical worst case.

The Helping Mechanism

To achieve bounded waiting, some algorithms introduce a helping mechanism: when a thread discovers that another thread's operation is blocking its own progress, it actively helps the other thread complete its operation before continuing with its own task. This mechanism can provide strong progress guarantees but also introduces additional complexity, so precisely controlling the timing of helping is key to implementation efficiency. The design of the helping mechanism's trigger condition is especially subtle: triggering too early causes the fast path to frequently degrade, while triggering too late fails to effectively guarantee fairness—this is precisely why early wait-free queue implementations had lower throughput than lock-free queues under normal load. Modern implementations typically combine exponential backoff with contention detection to make dynamic decisions.

Practical Engineering Recommendations

Theoretical Guarantees vs. Actual Performance

For the vast majority of applications, a pure lock-free queue is sufficient. But in scenarios sensitive to tail latency—such as financial trading and real-time audio/video processing—the value of bounded waiting becomes particularly prominent. Tail latency refers to the latency values at high percentiles (p99, p999, p9999) in the request response time distribution. In large-scale distributed systems, a single user request often requires parallel calls to dozens of downstream services, and the fan-out amplification effect makes tail latency a more critical metric than average throughput: if a single service has a 1% probability of exceeding its p99 latency, then when calling N independent services in parallel, the probability that at least one exceeds it is 1-(0.99)^N—about 39.5% when N=50, and about 63.4% when N=100. Google's Jeff Dean provided an in-depth analysis of this in The Tail at Scale (2013) and proposed mitigation strategies such as hedged requests. It is precisely this "fan-out amplification effect" that makes systems with strict real-time requirements pay closer attention to p99 and p999 latency and be willing to pay a certain performance price for fairness.

How to Choose the Right Queue Implementation

Based on specific scenarios, here are recommended selection approaches:

• Fixed capacity, pursuing ultimate throughput: Prefer a bounded MPMC queue based on sequence-number slots.
• Strict fairness and latency bounds: Choose an implementation that provides bounded-waiting or wait-free guarantees.
• Dynamic capacity requirements: Consider an unbounded queue, but fully evaluate the complexity and overhead introduced by memory reclamation (hazard pointers or EBR).

Summary

Designing concurrent data structures is never a one-dimensional optimization of "faster is better," but rather a multi-objective balance among performance, correctness, and fairness. Clearly distinguishing the essential difference between "lock-free" and "bounded waiting," mastering core techniques such as sequence-number slots, dual-path design, and helping mechanisms, as well as understanding the hardware semantics of the CAS primitive, the cost of the MESI cache coherence protocol, and the engineering trade-offs of safe memory reclamation (hazard pointers and EBR)—these are essential lessons for every systems engineer delving into concurrent programming.

As multi-core architectures continue to evolve and real-time application scenarios keep expanding, designing MPMC queues that balance speed and fairness will remain a challenging and highly valuable engineering direction.