Array-Based MPSC Lock-Free Queue

Overview

This is a lock-free ring buffer that supports:

• Multiple concurrent producers
• A single consumer

This data structure is commonly used in low-latency systems, including:

• Loggers
• Telemetry collectors
• Market data pipelines
• Kernel-user queues (Linux perf, BPF maps, etc.)

---

Requirements

• The queue must be bounded and implemented using a circular array.
• push() must be lock-free and thread-safe across multiple threads.
• pop() must be safe but is only called from a single thread.

---

Design Hints

• Use an atomic tail index for concurrent producers.
• Use a regular head index for the single consumer.
• Ensure tail - head < capacity for enqueue safety.
• Use padding (optional) to avoid false sharing of cache lines.
• Atomic writes and reads must be done with correct memory orderings.

---

Do Not Use

• std::mutex
• std::condition_variable
• Dynamic memory allocation

This queue is non-blocking and drops writes (or spins) when full.

Implement an array-based, lock-free queue with multiple producers and a single consumer.

#include <atomic>
#include <vector>

template <typename T>
class MPSCArrayQueue {
public:
    MPSCArrayQueue(size_t capacity)
        : buffer_(capacity), capacity_(capacity), head_(0), tail_(0) {}

    bool push(const T& item) {
        // TODO
        return false;
    }

    bool pop(T& item) {
        // TODO
        return false;
    }

private:
    std::vector<T> buffer_;
    const size_t capacity_;
    std::atomic<size_t> tail_;
    size_t head_; // only used by consumer
};