Publishing data between threads

3.8 Publishing: handing data from one thread to another

Threads usually need to hand over more than one atomic word: a message, a set of prices, a configuration. Three protocols cover most cases. They differ in how many threads write, how many read, and whether readers need every value or only the latest. This section covers each protocol’s ordering and what it costs in lines.

One to one, every item: the single-producer single-consumer protocol

A ring buffer is a fixed array of N slots and two counters. head counts the items the producer has written, and only the producer writes it. tail counts the items the consumer has read, and only the consumer writes it. Both only grow, and an item’s slot is its count modulo N.

The two synchronises-with links run in opposite directions:

The producer writes the slot and then stores head with Release. The consumer loads head with Acquire and then reads the slot. When the consumer’s load sees the new head, the write of the slot happens-before the read of the slot, so the consumer reads the whole message and never an older one. The slot itself is ordinary memory, written and read without atomics; the pair is what keeps those two plain accesses from being a data race.

The second pair runs the other way, and it is the one most often got wrong. The consumer stores tail with Release after reading the slot, and the producer loads tail with Acquire before deciding there is room. That makes the consumer’s read of a slot happen-before the producer’s next write to the same slot, N items later. Without it, on AArch64 the consumer’s store of tail could become visible before its read of the slot had completed, a load followed by a store to a different address, which that architecture may reorder. The producer would then see room, overwrite the slot, and the consumer would read the new message in place of the old. On x86-64 all six accesses are plain movs, and the pairs cost nothing in hardware.

Chapter 5 builds this ring in full: its capacity, its padding, cached copies of the other side’s counter, and batching. Here, only its ordering matters.

One writer, many readers, only the latest: seqlocks

Some data has one writer and several readers that want only its current value, never a history: a set of prices, a position, a clock. A seqlock serves them without readers writing anything shared. Beside the data sits a sequence counter. The writer makes the counter odd before it writes and even again after. A reader reads the counter, then the data, then the counter again, and keeps the data only if the two readings were equal and even; otherwise a write overlapped, and it tries again. The writer never waits for readers, and readers never write, so readers on different cores never move a line between them.

Two details are particular to Rust. The data must itself be atomics, read with Relaxed: a plain read that races with a write is undefined behaviour even if the reader then throws the value away. And the orderings take two fences. For one writer and atomic data words, the protocol is:

This assumes the sequence cannot wrap through a full cycle during one read. A reusable implementation must encode that assumption and the single-writer rule.

The Release fence makes any reader that saw even one new data word also see the odd counter on its second check, so a mixed read is always detected. The final Release store and the reader’s first Acquire load make a clean read see all of the data written before the counter went even. On x86-64 every one of these is a plain mov and neither fence emits an instruction.

Many readers, a large value: snapshots

When the value is too large to copy on every read, such as a table of a thousand settings, the writer does not overwrite it at all. It builds a complete new copy elsewhere, then publishes a pointer to it with one Release store, or a swap, on an AtomicPtr. Readers load the pointer with Acquire and read through it, and because nobody ever changes a copy once it is published, they never retry. The hard part is the old copy. The writer cannot free it while any reader may still be reading it, and it cannot know when that stops unless readers tell it, which is a write to a shared line. Arc makes every reader increment and decrement one shared count, an RMW on one line from every reader’s core. The arc-swap crate and epoch-based reclamation spread or defer that bookkeeping. A fixed set of buffers avoids freeing only if a protocol confirms that readers have released a buffer before the writer reuses it; a timing guess about reader speed is insufficient.

What it costs

The ring costs a transfer of the slot’s line and of the head line from producer to consumer per item, and of the tail line back, unless one side reads the other’s counter less often than every item. A seqlock costs its readers nothing while the data is still: the lines sit in every reader’s cache in the shared state, and a read is a few nanoseconds of hits. Each write invalidates every reader’s copy, so each reader’s next read misses on each line the write touched, 50–100 ns per line. A reader that polls while a write is in progress pulls the line away halfway through, and the writer pays the transfer again for its next store. A snapshot costs each reader a transfer of the pointer’s line per update, plus misses on the new copy, which another core has just written, plus whatever its reclamation costs.

Worked example: top of book to three strategies

A feed thread on core 2 maintains the best bid and ask, four u64 fields: bid price, bid quantity, ask price, ask quantity. Three strategy threads on cores 3, 4 and 5 each want the current values and none needs the history, so the feed publishes through a SeqLock<4>: 32 bytes of data and an 8-byte counter, aligned into one 64-byte line.

In a burst the book changes a million times a second. Each change, the feed’s first store needs the line back in its own cache: one request for ownership that invalidates three shared copies, 50–100 ns that the feed’s store buffer absorbs while it moves on. Each strategy’s next read misses: one transfer per strategy, 50–100 ns each, three per change. A write takes 20–50 ns from the odd store to the even one, so the counter is odd for 2–5% of a busy second, and a strategy polling without pause retries a few per cent of its reads. Three rings, one per strategy, would deliver every intermediate change and cost about two transfers per strategy per change; the seqlock skips stale intermediate states and costs one. Either way the line traffic is paid at the moment the book changes, which is exactly when the strategies want to look.

Seeing it

A seqlock is checked with a torture test: the writer stores [k, k, k, k] for k counting up from 1, readers assert that every read returns four equal values, and each reader counts its retries. With both fences in place the torn-read count is zero on every architecture; delete either fence and run it on an AArch64 box, and torn reads appear. perf c2c shows the seqlock’s line with HITMs from each reader’s core and none between readers, and Lab 3.4 checks small bounded executions of the ring with loom. Passing those models supports a happens-before argument; it does not prove every capacity, schedule or unsafe invariant. Retries per read and HITMs per update are the two numbers that price a seqlock: the first is reader time thrown away, the second is one 50–100 ns transfer per reader for every change the writer makes.