Low-Latency Software · Technology

12Queues, Ring Buffers and Shared Memory

In 2011 the engineers of a retail exchange published the numbers that had made them redesign their system. Passing an event through a three-stage pipeline built on the standard Java blocking queue took 32 757 nanoseconds per hop on average, and its 99.99th percentile was over four milliseconds; through the ring buffer they built instead, 52 nanoseconds on average and under 8 192 at the 99.99th percentile (Thompson et al., 2011). The work in each stage was the same; the queues were the latency. A trading process is a pipeline of threads (feed handler, book, strategy, gateway, logger), and how data moves between them decides much of its tail. This chapter builds the structures that move it: the single-producer single-consumer ring, the broadcast ring of the “disruptor” pattern, the sequence lock for data where only the latest value matters, and the same structures across processes in shared memory, with what to do when a consumer cannot keep up.

12.1 The single-producer single-consumer ring

Definition 12.1 (Ring buffer, single-producer single-consumer queue)

A ring buffer is a fixed array of slots used circularly: a writer’s position and a reader’s position increase forever and index the array modulo its size, a power of two so that the modulo is a mask. A single-producer single-consumer queue (SPSC) is a ring with exactly one writing thread and one reading thread; each position is written by one thread only, so no compare-and-swap is needed.

The producer writes the slot at its position and then publishes the new position with a release store; the consumer loads the producer’s position with acquire, reads every slot before it, and publishes its own position the same way, handing the slots back (chapter 11). Both operations are wait-free. Lamport proved such a queue correct without locks in 1983; what decades of practice added are the details that make it fast. The two positions live on separate cache lines, so that the producer’s writes do not invalidate the consumer’s position (chapter 3). And each side keeps a private copy of the other’s position and refreshes it only when the ring looks full or empty: while the ring is neither, a message costs one cache line transfer (the slot) instead of three.

A ring of eight slots after five messages were written and two read (the state of the build’s shared fixture). The producer’s and consumer’s positions each sit on a cache line of their own and only grow; the slot of position p is p 8. — **Figure 12.1.** A ring of eight slots after five messages were written and two read (the state of the build’s shared fixture). The producer’s and consumer’s positions each sit on a cache line of their own and only grow; the slot of position $p$ is $p \bmod 8$ .

Figure 12.2 measures a round trip between two pinned threads: one sends an eight-byte message through a ring, the other sends it back through a second ring. About $200\,\mathrm{n}\mathrm{s}$ at the median: four cache-line transfers between cores. The same round trip through a queue protected by a mutex and a condition variable costs about $30\,\text{µ}\mathrm{s}$ , over a hundred times more, because the waiting thread goes to sleep in the kernel and must be woken. One-way, the ring streams about 250 million eight-byte messages a second on this laptop.

Round trips of an eight-byte message between two pinned threads (or processes) through two SPSC rings, and through two queues protected by a mutex and a condition variable; 100 000 round trips each. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_rings.py. — **Figure 12.2.** Round trips of an eight-byte message between two pinned threads (or processes) through two SPSC rings, and through two queues protected by a mutex and a condition variable; 100 000 round trips each. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_rings.py`.

12.2 Many readers: the disruptor pattern

Definition 12.2 (Disruptor pattern)

In the disruptor pattern one ring carries every event to several consumers, each reading at its own position; consumers that depend on each other wait on each other’s positions rather than on queues between them, so a pipeline of stages becomes one ring with several cursors and no copies.

Market data is the natural case: one feed handler, several consumers (the book builder, a second strategy, the recorder, a risk monitor), each needing every message. Two policies differ in who waits. With back-pressure (next section) the producer waits for the slowest consumer, which is right for an order path, where nothing may be lost. For market data the producer must not wait: the exchange will not slow down. The build’s broadcast ring therefore never blocks its producer; each slot carries the sequence number of the message it holds, so a reader that has been lapped sees a later sequence than it expected and knows it lost messages, instead of reading a mixture.

**Figure 12.3.** A broadcast ring of eight slots after 16 messages. Each reader keeps its own position; the producer never waits. A reader at position 6 finds slot 6 holding message 14, a later sequence than it expects: it has been lapped (a slow consumer) and must resynchronise.

12.3 Sequence locks for last-value data

Definition 12.3 (Sequence lock)

A sequence lock publishes a small value that one writer updates and many readers read: the writer increments a counter to an odd value, writes the value, and increments it again to an even value; a reader reads the counter, copies the value, reads the counter again, and retries if the two readings differ or are odd.

The Linux kernel documentation describes the mechanism as having lockless readers with read-only retry loops and no writer starvation, for data rarely written relative to how often it is read. In trading the pattern suits the top of the book or a reference price, where readers want the latest consistent value, not every intermediate one. Two details make it correct in C++ as well as on x86: the value must be copied with atomic operations (relaxed ones suffice), since a copy that races with the writer’s non-atomic stores is a data race and undefined behaviour (Boehm, 2012); and the reader’s second counter read must be ordered after the copy by an acquire fence. The build’s test runs a writer in a tight loop against a reader that checks two hundred thousand pairs for tearing.

12.4 Shared memory between processes

Definition 12.4 (Shared-memory transport)

A shared-memory transport carries messages between processes through a region of memory that each maps into its address space (on Linux, a POSIX shared-memory object from shm_open, or a file on a memory filesystem), laid out as rings whose positions are atomics; no system call is made per message.

Processes isolate failures: a strategy that crashes need not take the feed handler with it, and components written in different languages can share a feed. The ring does not care: Figure 12.2 shows the same round trip between two processes as between two threads. What changes is the contract between the processes: the layout must be specified to the byte and versioned, since two binaries built at different times read it; every field must be of fixed size and alignment; and nothing in the region may be a pointer, which means nothing in the other process. The build’s layout is a 192-byte header (magic number, version, slot size, capacity, then the two positions on their own lines) followed by the slots, and its C++ and Rust implementations both reproduce the same byte image of a ring, written independently from the specification by a script.

12.5 Back-pressure, slow consumers and conflation

Definition 12.5 (Back-pressure, slow consumer, conflation)

Back-pressure is the propagation of a consumer’s slowness to its producer, which must wait or refuse new work when the queue between them is full. A slow consumer is a consumer whose rate is below its input’s, so that its queue grows or, on a ring that does not wait, it is lapped. Conflation is the deliberate delivery of only the latest value of each item (a price level, a quote) to a consumer that cannot take every update.

A queue’s size is a statement about bursts. One Quant Book 4, chapter 8, gives the M/M/1 answer for a stage with Poisson arrivals at rate $\lambda$ and exponential service at rate $\mu$ : with utilisation $\rho = \lambda/\mu$ , the stationary number in the system exceeds $n$ with probability $\rho^n$ . A ring that must overflow less than once in a billion messages at $\rho = 0.9$ therefore needs $n$ with $0.9^n < 10^{-9}$ , about 197 slots, 256 as a power of two. Market data is burstier than Poisson: the sizing starts from the M/M/1 figure and is checked against recorded bursts (chapter 18).

Proposition 12.6 (Time before a slow consumer is lapped)

A broadcast ring of $N$ slots whose producer writes at rate $\lambda_b$ during a burst, read by a consumer at rate $\mu < \lambda_b$ that starts the burst with an empty backlog, laps the consumer after $N/(\lambda_b - \mu)$ seconds.

Proof. The consumer’s backlog grows at $\lambda_b - \mu$ messages a second; the producer overwrites the consumer’s next unread slot when the backlog reaches $N$ . ∎

A ring of 65 536 slots, a burst at 2 million messages a second and a monitor that reads 1.5 million gives the monitor 131 milliseconds; an opening burst lasting longer laps it. The design answers are to give such consumers conflated views (a sequence lock per instrument instead of every message), to size their rings for measured bursts, or to let them fall behind by design and resynchronise from a snapshot, as the feed handler of chapter 18 does from the exchange.

12.6 Tutorial: rings in threads, processes and two languages

Goal. Build the rings, check the shared layout in C++ and Rust against one fixture, and measure round trips and throughput. End state: Figure 12.2, a throughput figure, and green tests in both languages.

Write and publish. The producer copies the message into its slot and publishes its position with a release store; it reads the consumer’s position only when the ring looks full.

    bool try_write(const void* msg, std::uint32_t len) {  // producer thread only
        if (len > h_.slot_size - 4) return false;
        const std::uint64_t w = word(base_, 64).load(std::memory_order_relaxed);
        if (w - read_cache_ == h_.capacity) {  // looks full: refresh the cached read position once
            read_cache_ = word(base_, 128).load(std::memory_order_acquire);
            if (w - read_cache_ == h_.capacity) return false;
        }
        std::uint8_t* slot = base_ + kHeader + (w & mask_) * h_.slot_size;
        std::memcpy(slot, &len, 4);
        std::memcpy(slot + 4, msg, len);
        word(base_, 64).store(w + 1, std::memory_order_release);  // publish
        return true;
    }

    int try_read(void* out, std::uint32_t cap) {  // consumer thread only; length, or -1 when empty
        const std::uint64_t r = word(base_, 128).load(std::memory_order_relaxed);
        if (r == write_cache_) {
            write_cache_ = word(base_, 64).load(std::memory_order_acquire);
            if (r == write_cache_) return -1;
        }
        const std::uint8_t* slot = base_ + kHeader + (r & mask_) * h_.slot_size;
        std::uint32_t len;
        std::memcpy(&len, slot, 4);
        if (len > cap) len = cap;
        std::memcpy(out, slot + 4, len);
        word(base_, 128).store(r + 1, std::memory_order_release);  // hand the slot back
        return static_cast<int>(len);
    }

Listing 12.1. The SPSC ring’s producer and consumer. code/firm/ring/cpp/firm_ring.hpp

The same in Rust, over the same bytes: a region of atomic words, written through their interior mutability.

    pub fn try_write(&mut self, msg: &[u8]) -> bool {
        if msg.len() > self.slot - 4 {
            return false;
        }
        let w = self.r.atomic(64).load(Ordering::Relaxed);
        if w - self.read_cache == self.cap {
            self.read_cache = self.r.atomic(128).load(Ordering::Acquire);
            if w - self.read_cache == self.cap {
                return false;
            }
        }
        let at = HEADER + ((w & (self.cap - 1)) as usize) * self.slot;
        // SAFETY: the producer owns slot w until the release store below; the consumer does not read it before.
        unsafe {
            let p = self.r.raw().add(at);
            std::ptr::copy_nonoverlapping((msg.len() as u32).to_le_bytes().as_ptr(), p, 4);
            std::ptr::copy_nonoverlapping(msg.as_ptr(), p.add(4), msg.len());
        }
        self.r.atomic(64).store(w + 1, Ordering::Release);
        true
    }

Listing 12.2. The Rust producer, writing the layout the C++ reader expects. code/firm/ring/rust/src/lib.rs

A sequence lock whose value is copied as relaxed atomic words.

    void store(const T& v) {  // single writer
        const std::uint64_t s = seq_.load(std::memory_order_relaxed);
        seq_.store(s + 1, std::memory_order_relaxed);
        std::atomic_thread_fence(std::memory_order_release);
        std::uint64_t w[kWords];
        std::memcpy(w, &v, sizeof v);
        for (std::size_t i = 0; i < kWords; ++i) words_[i].store(w[i], std::memory_order_relaxed);
        seq_.store(s + 2, std::memory_order_release);
    }

    T load(std::uint64_t* retries = nullptr) const {
        for (;;) {
            const std::uint64_t s1 = seq_.load(std::memory_order_acquire);
            if (s1 & 1) { if (retries) ++*retries; continue; }
            std::uint64_t w[kWords];
            for (std::size_t i = 0; i < kWords; ++i) w[i] = words_[i].load(std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_acquire);
            if (seq_.load(std::memory_order_relaxed) == s1) {
                T v;
                std::memcpy(&v, w, sizeof v);
                return v;
            }
            if (retries) ++*retries;
        }
    }

Listing 12.3. Writer and reader of the sequence lock. code/firm/ring/cpp/firm_ring.hpp

Check the layout. make_ring_fixture.py writes the byte image of a ring from the specification; both test suites build the same ring and compare, then consume the fixture.
Measure with python bench_rings.py: round trips between two threads on two pairs of CPUs, between two processes, and through a locked queue, then one-way throughput.

What to change next. Remove the cached copies of the other side’s position and measure the throughput again; put the two positions on the same cache line and measure the round trip.

12.7 Build: the firm’s rings

Purpose. The transport of every Part IV component: the feed handler publishes normalised events on a broadcast ring (chapter 18), the strategy engine reads them and hands orders to the gateway through an SPSC ring (chapters 20–21), the binary logger drains a ring (chapter 23), and the top of each book is published with a sequence lock.

Interface. C++20 firm::ring: format(base, capacity, slot_size), region_size, Spsc(base) with try_write(msg, len) and try_read(out, cap); Broadcast(base) with write, read(pos, out, len) returning Ok, Empty or Overrun, and head(); SeqLock<T> with store and load; Segment(name, bytes, create). Rust firm_ring: Region, format, Spsc::attach with try_write and try_read, SeqLock2.

Rules. The byte layout above, little-endian, versioned by a magic number and a version; capacities are powers of two; positions on separate cache lines; the SPSC ring reports full and empty, the broadcast ring never waits and reports overruns; no allocation after construction.

Acceptance tests. code/firm/ring/: the fixture’s bytes reproduced and consumed in C++ and Rust; 200 000 messages in order across two threads in both; broadcast overrun detection and resynchronisation; no torn read in 200 000 sequence-lock reads under a writer in a tight loop; 1 000 messages from a child process over shared memory.

Stretch. A broadcast ring with a declared slowest-consumer policy (wait, drop, conflate); a ring in a file on a huge-page filesystem.

Sources and further reading

M. Thompson, D. Farley, M. Barker, P. Gee and A. Stewart, Disruptor: high performance alternative to bounded queues for exchanging data between concurrent threads, 2011.
L. Lamport, “Specifying concurrent program modules”, ACM TOPLAS 5(2), 1983.
H.-J. Boehm, “Can seqlocks get along with programming language memory models?”, MSPC 2012; Linux kernel documentation, “Sequence counters and sequential locks”.
Linux man page shm_open(3).

12.8 Exercises

Exercise 12.1 ★

A ring has 1 024 slots; the producer’s position is 70 001 and the consumer’s 69 500. How many messages are waiting, which slot will the producer write next, and how many more can it write before the ring is full?

Solution

Solution of Exercise 12.1.

$70\,001 - 69\,500 = 501$ messages wait. The next write goes to slot $70\,001 \bmod 1\,024 = 369$ . The ring is full at 1 024 waiting, so $1\,024 - 501 = 523$ more.

Exercise 12.2 ★

At 250 million messages a second, how long does a 64-bit position take to wrap? And a 32-bit one?

Solution

Solution of Exercise 12.2.

$2^{64}/(2.5 \times 10^8)$ seconds is about 2 338 years: never. A 32-bit position wraps in 17.2 seconds, which is why positions are 64 bits and only the slot index is taken modulo the size.

Exercise 12.3 ★

A stage runs at $\rho = 0.8$ . What ring size makes an M/M/1 overflow rarer than one in a million?

Solution

Solution of Exercise 12.3.

$0.8^n < 10^{-6}$ for $n \ge 62$ ; the next power of two is 64 slots.

Exercise 12.4 ★★

Why does each side of the SPSC ring keep a private copy of the other’s position? What does removing the copies cost per message?

Solution

Solution of Exercise 12.4.

Reading the other side’s position means reading a line the other core writes at every message, so it moves between the cores each time. With the copies, each side reads the other’s line only when the ring looks full or empty; without them every message adds one or two line transfers, tens of nanoseconds under contention.

Exercise 12.5 ★★

A risk monitor reads the broadcast ring at 400 000 messages a second. A burst of 3 million messages a second lasts 80 milliseconds on a ring of 131 072 slots. Is the monitor lapped, and if so when?

Solution

Solution of Exercise 12.5.

The backlog grows at $3\,000\,000 - 400\,000 = 2.6$ million a second and reaches 131 072 after 50.4 milliseconds: the monitor is lapped about 30 milliseconds before the burst ends.

Exercise 12.6 ★★

Why must the sequence lock’s value be copied with atomic operations in C++, although the reader discards any copy taken during a write?

Solution

Solution of Exercise 12.6.

In the C++ memory model a non-atomic read that races with a write is a data race, which is undefined behaviour whatever is done with the value afterwards; the compiler may assume it does not happen. Relaxed atomic loads and stores of the words make the race defined, and the sequence check makes the result consistent.

Exercise 12.7 ★★★

Coding. Put the producer’s and consumer’s positions on the same cache line (edit the header offsets in a copy of firm_ring.hpp) and rerun the round-trip and throughput benchmarks. What changes, and why?

Solution

Solution of Exercise 12.7.

Both positions then share a line that the producer writes at every message and the consumer at every message: false sharing (chapter 3). Throughput should fall, since every write invalidates the other core’s copy of the line, and the round trip changes less, since in a ping-pong the lines move anyway; the measurement decides by how much.

Exercise 12.8 ★★★

Find the flaw. “Our shared-memory ring stores a pointer to the head message and a std::string for the instrument name in its header.”

Solution

Solution of Exercise 12.8.

A pointer is an address in one process’s address space and means nothing, or something else, in the other; a std::string holds such a pointer to memory that is not in the region at all. Shared layouts hold offsets and fixed-size fields only (a fixed character array for the name), with a version number.

12.9 Problem: Three Strategies, One Feed

Problem 12.1

Weekend problem — sizing a broadcast ring

A feed handler publishes normalised events on a broadcast ring of 65 536 slots of 64 bytes. Three consumers read it: a book builder at up to 4 million events a second, a strategy at 2.5 million, and a monitor at 1.5 million. On an ordinary day the feed averages 300 000 events a second; at the open, bursts reach 2 million a second for up to half a second.

Part I — The ring.

How many bytes does the ring occupy, and does it fit the second-level cache of chapter 3?
What is each consumer’s utilisation on an ordinary day?
Which consumers can fall behind during a burst?
Why does the producer never wait for them?

Part II — The burst.

How long before the monitor is lapped (Proposition 12.6)?
Is it lapped during a half-second burst?
What ring size would carry the monitor through the burst?
How much memory would that cost?

Part III — The alternatives.

The monitor needs only the latest price of each of 5 000 instruments. What does a sequence lock per instrument cost in memory, and what share of updates does the monitor skip during the burst?
What does the monitor do when it detects an overrun on the ring?
Why is back-pressure wrong for this producer and right for the order path?
What does the M/M/1 model say about the strategy’s ring at 300 000 events a second, and why is it optimistic?

Part IV — The verdict.

State the named result: the time before the monitor is lapped in a burst, and the share of updates a conflating monitor skips.
What does the measured round trip say about the cost of adding a consumer?
Why is the ring’s layout versioned?
What would the published comparison of a blocking queue and a ring predict for a blocking queue here?
Which placement rule of chapter 4 applies to the feed handler and the book builder?
How would you record the burst sizes that the ring must carry?
What must the strategy do after a gap in its input?
In one sentence: what is a ring buffer’s size a statement about?

Solution

Solution of Problem 12.1.

$65\,536 \times 64 = 4$ MiB plus the header: twice a 2 MiB second-level cache; the ring’s hot part is its recent slots.
7.5%, 12% and 20%.
The monitor, the only consumer slower than 2 million a second.
The exchange will not wait: a producer that blocked on its slowest reader would drop packets at the socket instead.
$65\,536/(2\,000\,000 - 1\,500\,000) = 131$ milliseconds.
Yes, after 131 milliseconds of a 500-millisecond burst.
At least $0.5 \times 500\,000 = 250\,000$ slots: 262 144 as a power of two.
16 MiB.
5 000 lines of 64 bytes, 320 000 bytes; at 2 million updates a second against 1.5 million reads, it skips a quarter of them, seeing only the latest.
It reports the gap, jumps to a recent position and rebuilds its view (from its own snapshot or the book builder’s).
Losing market data is recoverable (snapshots, conflation) and waiting is not; losing or reordering an order is neither, so the order path waits or refuses.
$\P(N \ge n) = 0.12^n$ , negligible for any reasonable $n$ ; optimistic because arrivals come in bursts far from Poisson.
Named result. The monitor is lapped 131 milliseconds into a 2-million-a-second burst on a 65 536-slot ring; reading through per-instrument sequence locks instead, it skips 25% of the updates and is never lapped.
About $200\,\mathrm{n}\mathrm{s}$ per round trip on this laptop: a consumer adds a cursor, not a queue, and its cost is its own reading.
Because two binaries built at different times, or in different languages, read it: a change must be detected, not misread.
Hundreds of times the ring’s latency per hop, with a tail in milliseconds, as the published comparison found.
Both on the network card’s node, on cores that hand lines over fastest (chapter 4).
Record the arrival rate per millisecond from the capture at the wire (chapter 23) and keep the distribution of burst lengths and peaks.
Invalidate the affected state and wait for, or request, a resynchronisation, as the book builder does on a gap (chapter 19).
The bursts it must absorb.

12.10 Interview questions

Interview question 12.1 ★ developer

Implement a single-producer single-consumer ring buffer. Which memory orderings does it need?

Solution

Solution of Interview question 12.1.

A power-of-two array, a producer position and a consumer position on separate cache lines, each written by one side. The producer writes the slot, then stores its position with release; the consumer loads it with acquire, reads, and stores its own with release, which the producer loads with acquire before reusing slots. Cache the other side’s position.

What the interviewer is looking for: release/acquire pairs, separate lines, cached positions.

Interview question 12.2 ★★ developer

Why is a ring buffer faster than a queue protected by a mutex and a condition variable?

Solution

Solution of Interview question 12.2.

No lock to contend for and no sleeping: the consumer spins on a position in its cache and sees the producer’s write as a cache line transfer, a hundred nanoseconds or so, where a condition variable puts the thread to sleep in the kernel and wakes it with a system call and a context switch, tens of microseconds.

What the interviewer is looking for: kernel involvement versus cache-coherence cost.

Interview question 12.3 ★★ developer

What is a sequence lock, when would you use one, and what are its pitfalls?

Solution

Solution of Interview question 12.3.

A counter made odd during a write and even after; readers copy and retry if the counter changed or was odd. For small values with one writer and many readers who want only the latest (top of book). Pitfalls: the copy must use atomic loads in C++ to avoid a data race; readers can starve under constant writes; the writer must be single.

What the interviewer is looking for: the retry protocol and the language-level data race.

Interview question 12.4 ★★ developer

One market-data feed, three consumers of different speeds. Design the distribution.

Solution

Solution of Interview question 12.4.

One broadcast ring written by the feed handler, each consumer at its own position, the producer never waiting; consumers that cannot keep up get conflated views (latest value per instrument) or detect overruns and resynchronise from a snapshot; sizes set from recorded bursts.

What the interviewer is looking for: a policy for the slowest consumer.

Interview question 12.5 ★★ developer

What must a data structure in shared memory between two processes avoid?

Solution

Solution of Interview question 12.5.

Pointers and anything that contains them (strings, containers, virtual tables), fields whose size or alignment depends on the compiler, and layouts without a version; locks that cannot be recovered if the holder dies.

What the interviewer is looking for: address-space independence and versioning.

Interview question 12.6 ★★★ developer, researcher

How would you size the queue in front of a stage whose input is bursty? What does queueing theory give you, and what does it miss?

Solution

Solution of Interview question 12.6.

Start from the M/M/1 tail $\P(N \ge n) = \rho^n$ for a target overflow probability; then check against recorded bursts, which are far from Poisson and last seconds; size for the worst burst plus margin, and design what happens on overflow. Queueing theory gives the order of magnitude and the effect of utilisation; it misses correlation and bursts.

What the interviewer is looking for: theory for the shape, data for the size.

Terms defined in this chapter

See all 2333 terms in the glossary