A Multiple-Producer Multiple-Consumer (MPMC) lock-free ring buffer is a bounded, concurrent queue where any number of threads may enqueue and dequeue simultaneously without ever acquiring a mutex or blocking on a condition variable. In HFT systems, it serves as the backbone for inter-thread communication between market-data ingestors, order-routing engines, risk engines, and execution handlers — all operating on nanosecond timescales.
template <typename T, std::size_t Capacity>
class MPMCRingBuffer {
static_assert((Capacity & (Capacity - 1)) == 0,
"Capacity must be a power of two");
struct alignas(64) Slot { // one full cache line per slot
std::atomic<std::size_t> sequence;
T data;
};
alignas(64) Slot slots_[Capacity];
alignas(64) std::atomic<std::size_t> head_; // producer cursor
alignas(64) std::atomic<std::size_t> tail_; // consumer cursor
};Three key design choices are visible immediately:
- Power-of-two capacity enables wrapping via bitwise AND (
index & (Capacity-1)) rather than modulo, eliminating division on the hot path. alignas(64)on every cursor and every slot places each in its own cache line, preventing false sharing between producers and consumers — one of the most destructive sources of latency variance in NUMA systems.- Per-slot sequence numbers (rather than one global version counter) are the defining feature distinguishing an MPMC buffer from an SPSC one.
Each slot carries an std::atomic<std::size_t> sequence that encodes the slot's generation relative to the global cursors. This is the crux of the algorithm (originally by Dmitry Vyukov):
| Slot state | sequence value |
|---|---|
| Empty, ready to be written by generation g | g * Capacity + index |
| Written, ready to be read | g * Capacity + index + 1 |
bool try_enqueue(T&& item) {
std::size_t pos = head_.load(std::memory_order_relaxed);
for (;;) {
Slot& slot = slots_[pos & (Capacity - 1)];
std::size_t seq = slot.sequence.load(std::memory_order_acquire);
std::intptr_t diff = (std::intptr_t)seq - (std::intptr_t)pos;
if (diff == 0) {
// Slot is free for this generation — try to claim it
if (head_.compare_exchange_weak(pos, pos + 1,
std::memory_order_relaxed))
{
new (&slot.data) T(std::forward<T>(item));
slot.sequence.store(pos + 1, std::memory_order_release);
return true;
}
// CAS failed — another producer claimed it; retry with updated pos
} else if (diff < 0) {
return false; // buffer full
} else {
pos = head_.load(std::memory_order_relaxed); // lap behind, reload
}
}
}The diff discriminant is the core insight:
diff == 0: the slot belongs to the current lap and no one owns it. A CAS onhead_races all other producers for this slot.diff < 0: this slot is from a future lap — the buffer is full.diff > 0: this slot is from a past lap — a stalepos; reloadhead_.
bool try_dequeue(T& item) {
std::size_t pos = tail_.load(std::memory_order_relaxed);
for (;;) {
Slot& slot = slots_[pos & (Capacity - 1)];
std::size_t seq = slot.sequence.load(std::memory_order_acquire);
std::intptr_t diff = (std::intptr_t)seq - (std::intptr_t)(pos + 1);
if (diff == 0) {
if (tail_.compare_exchange_weak(pos, pos + 1,
std::memory_order_relaxed))
{
item = std::move(slot.data);
slot.data.~T();
// Advance sequence to the *next* generation's write-ready value
slot.sequence.store(pos + Capacity, std::memory_order_release);
return true;
}
} else if (diff < 0) {
return false; // buffer empty
} else {
pos = tail_.load(std::memory_order_relaxed);
}
}
}The consumer checks for seq == pos + 1 (written state). On success it resets sequence to pos + Capacity, preparing the slot for the next wrap-around generation.
The buffer uses a deliberate, minimal ordering strategy:
| Operation | Ordering | Rationale |
|---|---|---|
head_ / tail_ CAS |
relaxed |
Cursor advancement doesn't need to synchronize data |
sequence load (check) |
acquire |
Synchronizes-with the preceding release store on the same slot |
sequence store (publish) |
release |
Publishes the slot's data to the peer thread |
head_ / tail_ initial load |
relaxed |
Local speculative read, retried on CAS failure |
The acquire/release pair on sequence is the only inter-thread synchronization. This is the minimum required by the C++ memory model to guarantee that a consumer reading slot.data sees the fully-constructed object the producer wrote. On x86-64 (TSO architecture), acquire and release compile to no additional fence instructions — the hardware enforces them for free. On ARM/POWER, these become ldar/stlr or lwsync/isync instructions, which are measurably cheaper than full sequential-consistency fences (mfence / dmb ish).
Classical lock-free structures (pointer-based stacks, lists) suffer from the ABA problem: a pointer returns to value A after being B, causing a CAS to incorrectly succeed. The ring buffer sidesteps ABA entirely by using monotonically increasing sequence numbers. The CAS operates on the integer head_ or tail_, which never decreases. A slot's sequence encodes its generation, making every state globally unique.
With a 64-bit sequence, wrap-around occurs at 2⁶⁴ ≈ 1.84 × 10¹⁹ operations. At 100 million enqueues per second — a plausible HFT throughput — this is approximately 5,800 years before any counter rolls over. Practically, it is never a concern.
If sizeof(T) is small (e.g., 8 bytes for a market-data pointer), the Slot struct should be padded to 64 bytes so that adjacent slots don't share a cache line. Without this, two producers writing neighboring slots will generate mutual invalidations — the dreaded false sharing — causing cache-coherency traffic on the interconnect even though they are logically independent.
struct alignas(64) Slot {
std::atomic<std::size_t> sequence;
T data;
char pad[64 - sizeof(std::atomic<std::size_t>)
- sizeof(T)];
};In a two-socket NUMA server (typical in co-location racks), the ring buffer should be allocated on the NUMA node whose cores own both ends wherever possible. Cross-socket cache-line transfers traverse the QPI/UPI interconnect at ~40–90 ns versus ~5 ns for same-socket L3 hits. numa_alloc_onnode() or mbind() should be used for the buffer's backing memory.
This is where the design choices pay off measurably.
| Source of latency | Mutex queue | MPMC ring buffer |
|---|---|---|
| Lock acquisition (uncontended) | ~25–40 ns | 0 ns |
| Lock acquisition (contended) | ~200–800 ns | 0 ns |
| OS scheduler involvement | Yes (futex) | Never |
| Cache line round-trip (CAS) | 1 per operation | 1–2 per operation |
| Memory fence cost (x86-64) | Implicit in lock prefix | 0 (TSO gives it free) |
The total one-way latency for a well-tuned MPMC ring buffer on x86-64 between a producer and a consumer pinned to the same L3 domain is typically 20–60 ns under moderate contention, versus 200–2000 ns for a mutex-protected std::queue.
Jitter is the enemy in HFT: a strategy that is right on average but wrong at the P99.9 percentile loses money. The ring buffer reduces jitter through several mechanisms:
-
No OS involvement. Mutexes devolve into
futexsyscalls under contention, invoking the scheduler. A context switch costs 1–10 µs and its timing is non-deterministic. The ring buffer's spin-CAS loop stays entirely in userspace. -
Wait-freedom is not achieved, but obstruction-freedom is. Under the CAS retry loop, a thread is obstructed only if another thread is mid-CAS on the same cursor — a window of roughly 1–5 clock cycles. This is bounded and hardware-serialized, producing tight, low-variance retry counts.
-
Bounded memory allocation. The ring buffer is statically sized at construction. No dynamic allocation occurs on the enqueue or dequeue path.
malloc/newon the hot path would inject non-deterministic jitter from the allocator's internal locking and potentialmmapsyscalls. -
Predictable cache behavior. The access pattern (sequential slot advancement, wrapping at a power of two) is highly amenable to hardware prefetchers. Modern Intel prefetchers recognize stride-1 sequential patterns and prefetch into L1 before the thread requests the line, keeping steady-state latency in the 4–5 ns range for cache-warm operation.
-
No priority inversion. A high-priority consumer thread can never be blocked by a low-priority producer holding a lock. All threads share equal access to the CAS hardware instruction, which the memory controller serializes in arrival order.
The ring buffer is not without a failure mode: CAS contention under extreme producer fan-in. When N producers simultaneously attempt a CAS on head_, only one succeeds per round; the rest retry. Retry counts scale roughly as O(N), and latency grows super-linearly with thread count. This manifests as a sharp jitter increase (the "contention cliff") when the number of producers exceeds the number of physical cores sharing an L3 cache, because CAS RTT rises from ~5 ns (L3 hit) to ~40–90 ns (cross-socket) or even higher under sustained load.
Mitigation strategies used in production HFT systems:
- Sharding: Multiple independent ring buffers, with producers hashing to a shard. Reduces per-shard N.
- Batching: Producers claim a range of positions with a single
fetch_add, then fill slots independently — eliminating per-element CAS. - SPSC specialization: Where the topology permits (one producer, one consumer), degrade to a simpler SPSC queue that requires no CAS at all, only a
store/loadpair withrelease/acquireordering.
The MPMC lock-free ring buffer achieves its performance profile through a precise set of co-designed decisions: power-of-two capacity for branchless wrapping, cache-line isolation for false-sharing elimination, per-slot sequence numbers for ABA-free slot ownership, and minimal acquire/release ordering that is free on TSO hardware. The result is a data structure whose steady-state latency is bounded by cache-coherency hardware rather than OS scheduling, and whose jitter is determined by CAS retry contention rather than lock convoy effects or priority inversion — properties that are essential when the cost of a microsecond of extra latency is measured in basis points of P&L.
Note
Generated by Claude.ai
Model: Sonet 4.6
Prompt: Provide a thorough description of the multiple-producer multiple-consumer (MPMC) lock-free ring buffer implemented in C++ code for a high-frequency trading system. This description is intended for a computer science expert. Explain how this data structure affects latency and jitter.