Skip to content

ADR 0001: Lock-Free SPSC Ring Buffer for Thread Synchronization

Status

Approved

Context

In a multi-threaded network packet processing pipeline, packet references must be passed rapidly from the ingestion reader thread, to the load balancer, and then to the fast-path worker threads. The baseline implementation uses a mutex-based thread-safe queue. Mutex lock acquisition takes substantial CPU cycles and may put threads to sleep under contention, causing latency spikes and context switch overhead.

Decision

We will implement a bounded Single-Producer Single-Consumer (SPSC) lock-free ring buffer queue for the primary data transmission paths.

Design Constraints:

  • The queue must be bounded to keep memory usage static.
  • Head and tail indices must be stored in atomic variables (std::atomic<size_t>).
  • To prevent cache thrashing (false sharing), head and tail indices must be aligned to separate 64-byte boundaries (alignas(64)).
  • The queue capacity must be a power of 2 to allow fast bitwise modulo operations.

Options Considered

  1. Mutex-Guarded std::queue: Simple, but introduces context switch overhead (futex) and is not suitable for nanosecond-level packet processing.
  2. Lock-Free MPMC (Multi-Producer Multi-Consumer) Queue: Support multiple workers pushing/popping from a single queue. Highly complex, requiring CAS loops which suffer from contention overhead under heavy traffic.
  3. Lock-Free SPSC Queue: Supports exactly one producer and one consumer thread. Executes push/pop in 10-30 nanoseconds with zero locks and zero CAS loops.

Consequences

  • Positive: Sub-100ns enqueue/dequeue times, predictable latency distribution (low jitter), zero kernel sleep cycles on the data path.
  • Negative: Bounded capacity. If the queue is full, the producer must wait (spin/yield), requiring careful sizing of the queues.