Lock-free data structures

Problems with locks

Bugs associated with locks depend on the timing of operations and code paths (for example deadlocks). Debugging is quite daunting.

Locks require extra memory and CPU to init, destroy, acquire, and release. Contention can be rare, but you pay in performance even when there is none. The more fine-grained the lock, the less the contention, but the higher the overhead.

If a thread or process dies while holding a lock, it brings down the entire system: no other thread that needs the lock can make progress (kill tolerance).

Priority inversion is a scenario where a low-priority thread holds a lock that a high-priority thread needs. The scheduler prioritizes the high-priority thread, which is in turn blocked by the low-priority one. Priority inheritance or ceiling protocols solve for this, but they have their own costs. This leads to convoying, where the speed of the processes is slowed down to the level of the slowest one.

Lock-free

Lock-free data structures maximize concurrency. A thread makes progress each time it runs. Underneath them there is a spin-lock implementation: instead of blocking, it repeatedly checks if the lock is available (busy spin).

Ring buffers

Ring buffers are the data structure of choice. A ring buffer is a linear structure with the end pointing back to the beginning. It acts as a queue but does not have the issues of a queue, which uses locks and is either mostly empty or mostly full, and rarely in the middle where the number of writes matches the number of reads. Locks in queues cause context switching in the kernel.

Ring buffers have read and write positions, which producers and consumers use in parallel.

To optimize caching, a single-core writer is best. If two cores are writing, each core will invalidate the cache line of the other.

If a reader is slower than the writer, there are two solutions:

• overwrite the data if it is not needed
• block the writer (potentially having a write buffer)

Common implementations: LMAX Disruptor, Conversant Disruptor, Agrona circular buffer.