Lock Free Data Structures in Trading Systems

Lock free structures replace mutexes with atomics because a descheduled lock holder stalls every other thread, and this covers the ring buffer that results.

Lock free data structures replace an operating system mutex with atomic operations because a mutex introduces a failure mode a trading hot path cannot tolerate: the thread holding the lock can be descheduled by the kernel at an arbitrary point, and every other thread waiting on that lock now stalls for however long it takes the scheduler to give the holder its turn back. A lock free structure never blocks a thread on another thread's progress, so the worst case latency is bounded by the algorithm itself rather than by the operating system scheduler.

The building block underneath almost every lock free structure is the compare and swap instruction, often written as CAS, which the processor executes atomically: it reads a memory location, compares it to an expected value, and writes a new value only if the comparison succeeds, all as one indivisible hardware operation. A thread that loses the race simply retries with the new current value, and because the operation either fully succeeds or fully fails with no intermediate state ever visible to another thread, no lock is ever needed to protect the update.

Correct use of compare and swap also requires reasoning about memory ordering. std::atomic in C++ exposes acquire, release and relaxed ordering, and a candidate who gets this wrong will write code that compiles and passes a simple test but breaks under real contention because the processor and compiler are both permitted to reorder instructions unless the ordering explicitly forbids it.

The single producer single consumer ring buffer is the structure most low latency systems reach for first, since it covers the common case of one thread reading market data and one thread consuming it. The buffer is a fixed size array with a head index the producer advances and a tail index the consumer advances, and because only one thread ever writes each index, the two threads need no compare and swap loop at all, only a correctly ordered atomic load and store on each index.

The head and tail indices are deliberately placed on separate 64 byte cache lines through padding, because if they shared a line the producer and consumer would trigger false sharing on every update even though the two indices are logically independent, a mechanism covered in more depth in the piece on cache locality and trading code performance.