Kwant Atlas

Explorer

2.9.4 Lock-Free Channels & Ring Buffers

Basic Prerequisites: 03 · System Architecture. Language-level atomics/memory-ordering are covered cross-pillar in Concurrency & Lockless Programming - this page gives the architecture reason, not the C++.

1. Intuition & Practical Objective

Between the three stages of the pipeline there is always a channel - a way for the feed handler to hand a decoded tick to the strategy without the two ever touching the same lock. The canonical channel is the single-producer/single-consumer (SPSC) ring buffer: a fixed-size array with two indices, head (consumer’s read position) and tail (producer’s write position), wrapped around so the array is reused forever. It is lock-free in the precise sense that a thread can never block another thread: the producer only ever writes tail, the consumer only ever writes head, and each publishes its index with a single atomic store.

The objective of this page is to explain why the ring buffer - not a lock, not a std::queue, not a socket - is the right channel for a hot path, to give the exact memory-ordering contract that makes it correct, and to quantify the two design knobs that matter: bounded capacity and busy-wait vs blocking.

The one-sentence essence. “A ring buffer is a fixed array plus two monotonically increasing counters; because exactly one thread writes each counter, there is no mutual exclusion to acquire - only a release/acquire handshake - so passing a message costs a few nanoseconds instead of a lock’s tens-of-nanoseconds-plus-contention.”

2. Mathematical Ground Truth & Derivations

2.1 The structure and its invariants

Let the buffer be an array of capacity (a power of two, so wrapping is a bit-mask rather than a division), and let head, tail be unsigned 64-bit counters that only ever increase. The producer writes to slot and then increments tail; the consumer reads slot and then increments head. The invariants are:

Note that the counters are monotonic (never wrapped), so wrap is handled by the mask and “full” is distinguishable from “empty” without wasting a slot. Correctness under concurrency requires release/acquire ordering: the producer must publish the payload before the atomic store of tail (store-release), and the consumer must load tail with acquire semantics before reading the payload - otherwise the CPU or compiler may reorder the write of the data after the write of the index, and the consumer will read garbage.

  • Producer publish: store_release(tail, tail+1) after writing B[tail & (C-1)].
  • Consumer observe: t = load_acquire(tail); if load_acquire(head) != t, read B[head & (C-1)], then store_release(head, head+1).

This is the whole protocol. (The C++ realisation - std::atomic, fences, alignas(64) - is in Concurrency & Lockless Programming; do not duplicate it here.)

2.2 Why a lock is the wrong tool

A mutex costs a compare-and-swap plus, under contention, a cache-line bounce between cores. Even uncontended, an atomic RMW is ~10–20 ns and serialises the two cores’ caches; under contention, the MESI protocol can cost hundreds of ns and the failed waiter may be descheduled entirely. An SPSC ring avoids all of it: the producer touches only tail and its own slot; the consumer touches only head and its own slot. Their working sets are disjoint - zero sharing except the handshake counters, and those are read-mostly. The idiom that makes this work is padding: head and tail should sit on separate 64-byte cache lines (alignas(64)), or they suffer false sharing and every producer store invalidates the consumer’s cache line.

2.3 Busy-wait, interrupts, and the wake-up tax

A consumer has two ways to wait for work:

  • Busy-poll (spin): repeatedly load the index. It sees new work within a few ns of publication, but it burns a whole core and can generate cache/memory traffic.
  • Blocking (sleep/wake, futex/condition variable): the consumer yields the core, but the producer must then wake it - a syscall plus a scheduler decision, measured in microseconds.

The trade is stark: spinning costs a core continuously; blocking costs a wake-up on every idle→busy transition. For a low-latency engine the answer is almost always spin on a dedicated, pinned core - the core is cheap, the microsecond is not. (The optimal middle ground is adaptive: spin for a bounded window, then sleep - the strategy used by kernel-bypass stacks and SO_BUSY_POLL.)

2.4 Capacity is a latency/drop trade

A bounded ring of capacity can absorb a burst of messages arriving together. If the producer outruns the consumer for longer than messages, the ring is full and the producer must either drop (staleness signal) or block (back-pressure that propagates latency upstream). Little’s law again bounds what must be: the burst size the system must survive equals the arrival rate times the burst duration, . Size the ring for the burst, not the average - and remember that a larger does not change the steady-state arrival/service ratio (see the measurements below).

3. Computational Implementation - busy-poll vs blocking, and capacity

Standard library only. We model the SPSC channel as a discrete-event single-server system with a bounded ring (WIP = work accepted but not yet completed). Two experiments: (a) low load, busy-poll vs blocking consumer; (b) sustained overload, capacity sweep.

Read the result. (a) At low load the busy-poll consumer sees each message ~60 ns after it is produced; the blocking consumer pays 1 086 ns - an ~18x penalty - purely for the wake-up handshake on every idle→busy transition. That is the price of sleeping. (b) Under sustained overload the drop rate (~19 %, ≈ ) is set by the arrival/service ratio, not by capacity - a bigger ring does not help the steady state; it merely hides the backlog longer, converting drops into ever-growing queueing latency (mean climbs from 1 782 ns at C=16 to 475 000 ns at C=4096). Capacity is a burst-absorber, not a throughput fix; the only throughput fix is making the consumer faster or shedding load.

4. Failure Modes & First-Principles Breakdowns

  1. False sharing on the counters. head and tail on the same cache line means every producer publish invalidates the consumer’s line; latency jumps from ~60 ns to hundreds/thousands. Fix: alignas(64) (see Concurrency & Lockless Programming).
  2. Missing the release/acquire ordering. Without the store-release/load-acquire handshake, the CPU may publish the index before the payload is visible - a data race that shows up as a “corrupt tick” once in a million messages. This is a correctness bug, not a performance one.
  3. Unbounded growth. A ring that silently grows to absorb overload converts a capacity problem into an unbounded-latency problem. Bounded ring + explicit drop is the honest contract.
  4. Mixing multiple producers or consumers onto one ring. SPSC correctness depends on exactly one writer per index. A multi-producer ring needs compare-and-swap on tail and a fallback - acceptable, but slower and no longer lock-free in the simple sense. Do not “just add a writer”.
  5. Spinning without a plan. Busy-polling a ring that is empty 99 % of the time wastes cores and generates memory traffic; the adaptive spin-then-sleep policy exists for that regime.

5. References

  • LMAX Disruptor paper + library, and Fowler, Martin - The LMAX Architecture. The foundational treatment of ring-buffer channels, batching, and single-writer design.
  • Thompson, Martin - Mechanical Sympathy (blog/talks). Cache-line padding, false sharing, memory-mapped I/O.
  • Herlihy, Maurice & Shavit, Nir - The Art of Multiprocessor Programming (rev. ed.). The formal definitions of blocking/lock-free/wait-free progress and the semantics of the handshake above.
  • Preshing, Jeff - An Introduction to Lock-Free Programming. The clearest free exposition of atomics, ordering, and lock-free structure.
  • Williams, Anthony - C++ Concurrency in Action (2
  • DPDK and Solarflare/OpenOnload (EF_VI) documentation. Production, hardware-backed versions of the same ring, used for the NIC receive path.

6. Connected Graph Bridges

Graph View

Backlinks