实现有界等待的高性能MPMC队列

背景

原文作者在上一篇博文之后开始着手设计一种能在多线程间可变共享缓冲区的数据结构。在这一过程中，他深入研究了无锁（lock-free）数据结构，并决定尝试实现一个具有**有界等待（bounded waiting）**特性的多生产者多消费者（MPMC）队列。文章标题借用了流行歌曲《Girls Just Want to Have Fun》的句式，以幽默的方式表达了作者对高性能队列的追求。作者明确声明，该数据结构并非革命性创新，而是用于检验自己对无锁/免等待（wait-free）编程直觉的练习。他尽可能避免参考其他已有实现，仅在自己机器上通过 max0x7ba 的 atomic_queue 仓库对一些流行队列实现进行了基准测试，并希望获得更懂行人士的反馈。

需要特别注意的是：作者在论文中最初声称该结构是**免等待（wait-free）**的，但在 Reddit 用户 matthieum 的指正下承认了这一错误。免等待要求任何线程的失败或挂起不会导致其他线程失败或挂起，而该队列不满足该要求。因此文中部分提及“wait-free”的地方实际上应为“有界等待（bounded waiting）”，作者选择保留这些段落以避免大规模重写。

核心内容

设计理论

队列基于票锁等待系统（ticket lock wait system）。想象有两个票务分发器，一个给生产者，一个给消费者，以及一组编号为 0 到 N-1 的相邻箱子。每个箱子上方有一个显示器，显示当前轮到谁的保留号（reservation number）和类型（生产者或消费者）。每个票上印有两个数字：箱子编号和保留号。

生产者或消费者的流程很简单：从对应的分发器取一张票，找到票上显示的箱子编号，等待该箱子上方显示与票面保留号匹配的号码。一旦显示，就可以执行相应操作（生产：放置物品；消费：取出物品）。

该保留系统确保对任意箱子满足以下不变式：

• 箱子初始为空；
• 被调用的第一个票是生产者的票；
• 同一类型的票永远不会被连续调用两次（例如不会出现生产者接着生产者）。

这保证了生产者总有一个空箱子放入物品，消费者总有一个满箱子取出物品。

实际实现

在实际实现中，使用两个 AtomicUsize 计数器（分别对应生产者和消费者）以及两个环形缓冲区（ring buffer）。一个缓冲区（data buffer）用于实际传递物品，另一个缓冲区（state buffer）跟踪 data buffer 中每个条目的所有权。计数器扮演票务分发器，data buffer 条目是箱子，state buffer 条目是箱子顶部的显示器。

核心结构体定义如下（已简化缓存行填充以避免伪共享）：

pub struct WFQueue<T, const N: usize> {
    data: NonNull<[CachePadded<T>; N]>,
    state: NonNull<[CachePadded<AtomicTicket>; N]>,
    prod_reserve: CachePadded<AtomicUsize>,
    cons_reserve: CachePadded<AtomicUsize>,
}

其中 AtomicTicket 是对 AtomicUsize 的薄封装：使用最低 63 位存储票号/保留号，最高位表示类型（生产者或消费者）。state buffer 条目的值解释为：持有对应保留号和票类型的线程对该 data buffer 条目拥有排他读写权限。

由于保留号通过 fetch-add 操作递增，需要从保留号映射到缓冲区索引：取保留号模 N。为优化除法运算，强制 N 为 2 的幂，从而可以用位掩码 (x & (N - 1)) 代替取模。因此，票号上没有同时印箱子号和保留号，而是保留号的最低 N 位通过位与运算给出箱子号。

生产者入队流程

1. 对生产者计数器执行 fetch-add 加 1，将加法前的值作为保留号。
2. 等待直到 state buffer 对应条目（索引 = 保留号 & (N-1)）的值与保留号（仅低 63 位）匹配，且状态位表示当前是生产者的轮次。
3. 将值存入 data buffer 的对应槽位。
4. 翻转 state buffer 条目的状态位，表示该槽位现在轮到消费者。

消费者出队流程

1. 对消费者计数器执行 fetch-add 加 1，将加法前的值作为保留号。
2. 等待直到 state buffer 对应条目的值与保留号（仅低 63 位）匹配，且状态位表示当前是消费者的轮次。
3. 从 data buffer 对应槽位读取值。
4. 将 state buffer 条目的值设置为 保留号 + N，且状态位表示轮到生产者。其中保留号来自步骤 1。

下图展示了 state buffer 条目与 data buffer 条目的关联，以及 state buffer 的位域划分：

+---+---+---+-----+-------+-------+-------+
| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 |  <-- data buffer
+---+---+---+-----+-------+-------+-------+
    ^   ^   ^         ^       ^       ^
    |   |   |         |       |       |  state buffer 条目值匹配时
    |   |   |         |       |       |  表示拥有该 data buffer 槽
+---+---+---+-----+-------+-------+-------+
| 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 |  <-- state buffer
+---+---+---+-----+-------+-------+-------+

关键要点

• 队列类型：有界等待（bounded waiting）的 MPMC 队列，非免等待（wait-free）。
• 核心机制：基于票锁（ticket lock）思想的保留系统，每个槽位在任意时刻只允许一个生产者或消费者操作。
• 数据结构：使用两个环形缓冲区：data buffer（存实际数据）和 state buffer（存所有权标记）；计数器作为票务分发器。
• 不变式保证：槽位状态交替为生产者和消费者轮次，不会出现同一类型连续占用，从而避免竞争和死锁。
• 优化技巧：缓冲区大小强制为 2 的幂，通过位与运算快速计算索引；使用 CachePadded 避免伪共享；使用 NonNull 和手动分配管理内存以避免 UB。
• 性能表现：作者表示在其机器上对比 atomic_queue 仓库中的其他实现，该队列速度“相当不错”（decently fast），但未给出具体数据。
• 限制与缺陷：不满足免等待，因为线程挂起可能导致其他线程无限等待（例如持有保留号的线程被挂起，其他线程只能等待该槽位）；保留号在 2^63 处溢出（而非 2^64），因为最高位被用作类型位。

意义与影响

该文章的意义在于提供了一个有界等待 MPMC 队列的简洁设计思路，并公开了实现细节。对于学习无锁编程的开发者来说，这是一个很好的教学案例：它将复杂的并发问题分解为 ticket lock 的简单比喻，并展示了如何在实际代码中处理缓存行对齐、位域编码、手动内存管理等底层问题。作者诚实面对错误并修正，体现了技术社区中开放讨论和纠错的价值。

该队列适用于需要高吞吐量的多生产者多消费者场景（如日志系统、事件总线、任务队列），但需注意其有界等待而非免等待的特性，在实时性要求极高的系统中可能无法满足。此外，该设计强制缓冲区大小为 2 的幂，可能带来内存浪费。

从更广的视角看，这种基于保留号与状态位结合的思路，与经典的无锁队列（如 Michael-Scott 队列）有所不同，为相关领域提供了一种新的候选方案。未来工作可能包括基于此构造更一般的无等待结构，或将其扩展到无界队列。