Concurrency: atomics, memory ordering and lock-free queues

Trading systems are pipelines of threads: one reading the network, one decoding, one deciding, one sending. The handoffs between them are where concurrency shows up, and they must be both correct and free of any construct that could block.

Definition 3.1

A data race

Data race — Two threads access the same location, at least one writes, and nothing orders them. In C++ that is undefined behaviour — not "you get one value or the other", but a programme the compiler may transform arbitrarily. The compiler is entitled to assume no races exist, so a racy read can be hoisted out of a loop and never re-read at all.

Why a mutex is disqualifying on a hot path. A mutex is fast when uncontended — a single atomic operation. The problem is what happens when it is contended: the thread blocks, the kernel is involved, and it may not be rescheduled for microseconds. Worse is priority inversion, where a low-priority thread holding the lock is descheduled and the critical path waits for it. Neither is a problem for throughput and both are fatal for a tail-latency target, which is why hot paths use lock-free structures even though they are much harder to write.

Proposition 3.2

Atomics and ordering

An atomic operation is indivisible, and it also constrains how other memory operations may be reordered around it. That second part is the subtle one: compilers and processors both reorder freely, and the memory ordering you request is what stops them doing so in ways that break your logic.

Holds when

relaxed: atomic, but no ordering guarantees — safe only for counters nobody synchronises on.
acquire / release: a release store is visible to any acquire load that reads it, along with everything written before it. This is the pairing that makes a queue work.
seq_cst: a single global order, the default, and the most expensive.

Proposition 3.3

The single-producer single-consumer ring

A fixed-size array with a write index and a read index, each written by exactly one thread. The producer publishes data then releases the write index; the consumer acquires the write index then reads the data. Because each index has a single writer there is no contention at all, and no compare-and-swap is needed.

Holds when

Pad the two indices onto separate cache lines, or false sharing destroys the performance.
The release–acquire pair is what guarantees the consumer sees the data, not just the index.
It is wait-free for both sides, which is the strongest guarantee available.

// Producer: write the slot, then publish the index.
buffer[write_idx % N] = message;
write.store(write_idx + 1, std::memory_order_release);

// Consumer: read the index, then the slot it guarantees.
auto w = write.load(std::memory_order_acquire);
if (read_idx < w) {
    auto msg = buffer[read_idx % N];
    read.store(read_idx + 1, std::memory_order_release);
}

Listing 3.4 · The ordering that makes it work. The release store guarantees that everything written *before* it — the message itself — is visible to any thread whose acquire load sees the new index. Use relaxed instead and the consumer can observe the index update before the data, which is a real failure on a weakly ordered processor and unreproducible on a strongly ordered one. Time O(1) per message, wait-free · Space O(N).

Concurrency: atomics, memory ordering and lock-free queues

After this lesson you should be able to

A data race

Atomics and ordering

The single-producer single-consumer ring

The rest of this lesson is in Premium