无锁队列
Mpsc Lock Free Queue
题目详情
高频交易和量化执行系统常需要多个策略线程向单个执行引擎提交订单而不引入延迟或抖动。MPSC（多生产者单消费者）无锁队列使用 CAS 操作实现无锁写入和读取。
任务：实现 MPSCQueue 类，多生产者线程并发 push() 使用 CAS 链接节点到队列尾部。单消费者线程 pop() 从队列头部取出节点。push() wait-free，pop() 可能需要等待生产者完成链接操作。
英文原题
High-frequency trading (HFT) and quantitative execution systems often require multiple strategy threads to submit orders to a single execution engine without introducing latency or jitter. A Multi-Producer, Single-Consumer (MPSC) lock-free queue utilizes atomic Compare-And-Swap (CAS) operations to eliminate thread contention and context switching. This pattern is essential for achieving ultra-low latency, lock-free order submission in concurrent trading environments.
Task
Implement a LockFreeMP
解析
问题分析
MPSC（多生产者单消费者）无锁队列适合订单入口场景：多个策略线程生产订单，单个网关线程消费并发送到交易所。相比 SPSC，增加的生产者间同步通过原子 CAS 实现。
实现
template<typename T, size_t N>
class MPSCQueue {
struct Node { std::atomic<size_t> seq; T data; };
Node buffer_[N];
std::atomic<size_t> write_pos_{0}, read_pos_{0};
public:
bool push(T v) {
size_t w = write_pos_.fetch_add(1, std::memory_order_relaxed); // 原子预留槽位
auto& node = buffer_[w % N];
while (node.seq.load(std::memory_order_acquire) != w)
std::this_thread::yield(); // 等待槽位可写
node.data = std::move(v);
node.seq.store(w + 1, std::memory_order_release);
return true;
}
bool pop(T& out) {
size_t r = read_pos_.load(std::memory_order_relaxed);
auto& node = buffer_[r % N];
if (node.seq.load(std::memory_order_acquire) != r + 1) return false;
out = std::move(node.data);
read_pos_.store(r + 1, std::memory_order_release);
return true;
}
};复杂度与边界
- 时间复杂度：push/pop O(1)（push 在竞争时需自旋等待槽位）
- 空间复杂度：O(N)
- 边界条件：(1) N 须为 2 的幂 (2) write_pos 回绕通过 seq 号而非位置判断 (3) 生产者过多时 write_pos 争用成为瓶颈
英文解析
Analysis
An MPSC (Multiple Producer Single Consumer) lock-free queue suits the order entry scenario: multiple strategy threads produce orders while a single gateway thread consumes and sends them to the exchange. Compared to SPSC, the added producer-side synchronization is achieved through atomic CAS operations.
Solution
template<typename T, size_t N>
class MPSCQueue {
struct Node { std::atomic<size_t> seq; T data; };
Node buffer_[N];
std::atomic<size_t> write_pos_{0}, read_pos_{0};
public:
bool push(T v) {
size_t w = write_pos_.fetch_add(1, std::memory_order_relaxed);
auto& node = buffer_[w % N];
while (node.seq.load(std::memory_order_acquire) != w)
std::this_thread::yield();
node.data = std::move(v);
node.seq.store(w + 1, std::memory_order_release);
return true;
}
bool pop(T& out) {
size_t r = read_pos_.load(std::memory_order_relaxed);
auto& node = buffer_[r % N];
if (node.seq.load(std::memory_order_acquire) != r + 1) return false;
out = std::move(node.data);
read_pos_.store(r + 1, std::memory_order_release);
return true;
}
};Complexity & Edge Cases
- Time complexity: push/pop O(1) (push spins under contention waiting for slot availability)
- Space complexity: O(N)
- Edge cases: (1) N must be a power of 2 (2) write_pos wrapping is handled via sequence numbers rather than position (3) With many producers, write_pos contention becomes a bottleneck
Verification
Push from multiple threads concurrently, pop from single consumer. Verify no order loss, no double-consumption, and that the queue handles wrap-around correctly after N pushes.
Key Considerations
The sequence-based design avoids ABA problems common in lock-free queues. In order entry systems, MPSC queues are preferred over mutex-based queues because the gateway thread (consumer) never blocks - it either gets an order or moves on, critical for low-latency order routing.