女孩们只想要具有有界等待的快速MPMC队列

# 女孩只想拥有带有限等待的无锁 MPMC 队列 · Nahla 来源：https://nahla.dev/blog/waitfree_queue/ 2026年3月12日，星期四 - [设计](#design) - [理论](#theory) - [实现](#reality) - [优势](#advantages) - [技术限制与值得注意的行为](#technical-limitations-notable-behaviors) - [基准测试](#benchmarks) - [方法](#methodology) - [结果](#results) - [分析与结论](#analysisconclusions) - [源代码](#source-code) > 免责声明：本文早期版本声称该结构是无等待的（wait-free），这是不正确的。无等待要求任何线程的故障或挂起不会导致另一个线程的故障或挂起。这个队列实际上并不满足这一要求。讨论队列操作等待界限的主要部分已作相应修改，但本文其他部分尚未修改。因此，文中可能有部分内容将其称为无等待队列，但实际上它不是。我选择保留这些部分，以避免在文章发布后重写大量内容。感谢 Reddit 用户 matthieum 的纠正！ 在上一篇文章之后，我开始着手编写一个数据结构，以便在多个线程之间可变地共享缓冲区。一个分支引出另一个分支，这让我对无锁数据结构产生了浓厚的兴趣，于是我决定制作一个无等待队列。在我看来这个东西速度还不错，我为此感到自豪，所以我觉得值得写一写。另外，在上一部长篇小说之后，我想写点短小精悍的东西。 需要明确的是，我并非声称这个数据结构在有任何方面具有开创性意义。这仅仅是我在测试自己对无锁/无等待编程的直觉。为此，我尽量减少对其他工作的交叉引用，只在我的机器上对其他一些队列实现*进行了基准测试，而没有查看它们的内部实现。我希望能从比我更了解这方面知识的人那里得到反馈，如果你就是这样的人，请不要犹豫，分享你的想法！ > * 每当提到“其他队列”的基准测试时，我指的是通过 max0x7ba 的优秀 atomic_queue（https://github.com/max0x7ba/atomic_queue）仓库获得的基准测试结果。它提供了一套脚本和 make 文件，让我能够非常容易地获得各种流行队列实现的综合基准测试集合。 ## 设计 ## 理论 该队列基于一种票锁等待系统工作。设想有两个取号机，一个给生产者使用，一个给消费者使用，还有一组 N 个相邻的盒子，编号从 0 到 N-1。每个盒子上方都有一个显示屏，显示当前轮到谁，它显示一个预约号和一个字母，指示是消费者还是生产者的回合。每张票上印有两个号码：一个是盒子编号，另一个是预约号。 消费者或生产者的流程都很简单：从相应的取号机取一张票，找到票上编号所示的盒子，等待票上的预约号显示在盒子上方。一旦预约号显示出来，就可以执行其票允许的操作：要么取走（消费），要么放入（生产）一个物品。 值得注意的是，这里的预约系统会确保对于任何一个盒子，以下条件成立： - 盒子初始是空的。 - 第一个被叫到的票是生产者的票号。 - 同一票种不会连续被叫两次（例如生产者之后又是生产者）。这确保了生产者始终有空的盒子放入物品，消费者始终有满的盒子取出物品。 ## 实现 虽然理论上很美好，但我们需要回到现实世界，实际实现这个系统。为此，我们将使用两个 `AtomicUsize` 计数器，一个用于生产者，一个用于消费者，以及两个环形缓冲区。一个缓冲区（“数据”缓冲区）用于实际传递队列中的物品，另一个缓冲区（“状态”缓冲区）跟踪数据缓冲区中每个条目的所有者。在这里，计数器就是取号机，数据缓冲区条目就是盒子，而状态缓冲区条目就是每个盒子上方的显示屏。 我们将使用的结构体如下： ```rust // 添加缓存填充以防止伪共享 /// 一个基于数组的有界等待队列 pub struct WFQueue<const N: usize, T> { // 使用 NonNull 指针而不是 Box，以避免意外解引用导致未定义行为。 // 使用手动分配是为了避免在不再拥有值的所有权时意外调用 drop（Box 在 drop 时会调用 drop）。 data: NonNull<[CachePadded<T>; N]>, state: NonNull<[CachePadded<AtomicTicket>; N]>, prod_reserve: CachePadded<AtomicUsize>, cons_reserve: CachePadded<AtomicUsize>, } ``` > 注意：除非特别说明，我假设系统 `usize` 类型为 8 字节/64 位。虽然这里的思路在任何 `usize` 类型的系统上都适用，但给定具体大小讨论起来容易得多。另外，老是说“在 `usize` 类型为 `N` 位的系统上，低 `N-1` 位用于 blah blah blah”很快就会让人厌烦，而我又很懒。 `AtomicTicket` 类型只是 `AtomicUsize` 的一个薄封装。`AtomicTicket` 使用最低的 63 位存储票号/预约号，并使用最高位表示票的类型（消费者/生产者）。状态缓冲区条目的值被解释为：持有相应预约号和票类型的线程对该状态条目索引相同的数据缓冲区条目拥有独占读/写权限。 > 注意：由于我们使用最高位来存储票的状态（如上所述），这意味着预约号将在 \(2^{63}\) 边界处溢出，而不是 \(2^{64}\)。 预约号由原子计数器通过 fetch_add 递增 1 产生。预约号对应的状态和数据缓冲区索引通过将预约号取模 `N` 获得，其中 `N` 是缓冲区大小。但是，由于除法/取模运算开销较大，我们采用常见优化：强制缓冲区大小为 2 的幂。通过强制 `N` 为 2 的幂，我们可以使用 `N - 1` 作为位掩码，使得对于任何整数 `x` 都有：`(x & (N - 1)) == x % N`。 实际上，“票”并没有同时包含盒子编号和预约号，预约号的低 `N` 位给出了盒子编号（状态/数据缓冲区索引），我们通过位与运算获得。 生产者入队一个物品的流程如下： 1. 使用 fetch_add 将生产者计数器加 1，保存操作前的值作为预约号。 2. 等待，直到状态缓冲区条目的值（仅低 63 位）与预约号匹配，且状态位指示是生产者回合。 3. 将所需值存储到对应的数据缓冲区槽位。 4. 切换状态缓冲区条目中的状态位，指示该槽位现在是消费者的回合。 消费者出队一个物品的流程如下： 1. 使用 fetch_add 将消费者计数器加 1，保存操作前的值作为预约号。 2. 等待，直到状态缓冲区条目的值（仅低 63 位）与预约号匹配，且状态位指示是消费者回合。 3. 从对应的环形缓冲区槽位读取值。 4. 将状态缓冲区条目的值设置为预约号 `reservation_number + N`，状态位指示现在是生产者回合。这里的 `reservation_number` 是步骤 1 中获得的号码。 下图显示状态缓冲区中的一个条目如何与数据缓冲区中对应的条目关联，以及状态缓冲区位域的分解。 ``` +---+---+---+-----+-------+-------+-------+ | 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- 数据缓冲区 +---+---+---+-----+-------+-------+-------+ ^ ^ ^ ^ ^ ^ ^ 具有匹配值的 | | | | | | | <-- 状态缓冲区条目意味着 | | | | | | | 拥有数据缓冲区槽位的所有权。 +---+---+---+-----+-------+-------+-------+ | 0 | 1 | 2 | ... | n - 3 | n - 2 | n - 1 | <-- 状态缓冲区 +---+---+---+-----+-------+-------+-------+ \ / \ / \ / +------------------------------+ | 63 | 62:0 | +-------------+----------------+ | status_bit | reservation_num | +-------------+----------------+ ``` ## 优势 ### 无 CAS 循环，最小化缓存争用 该系统的一大优势是没有 CAS 循环。通过反复读取状态缓冲区来等待自己的回合，可以使该槽位的缓存保持在共享状态（假设 MESI 缓存模型），从而最小化争用。所有权状态仅在某个参与者完成其操作时发生变化，此时它们会写入他们操作的数据缓冲区槽位对应的状态缓冲区条目，将其推进到下一个预约号。 ### 有限等待 除了线程挂起或故障之外，此结构上的任何操作都有一个时间上限。这意味着我们保证没有消费者或生产者会饿死，并且所有入队和出队操作最终都会完成。然而，这有一个前提：你*必须*同时运行消费者和生产者，并且上限不考虑由 OS 线程挂起或某种故障导致的等待。例如，如果队列已满，且没有消费者在运行，则无论等待多久，都无法完成任何入队操作。 由于系统是基于预约号排序的回合制，某种类型参与者（生产者或消费者）的等待时间取决于它在回合队列中的位置，以及活跃* 的另一种类型参与者的数量。以容量 \(N = 64\) 的队列为例。如果我们尝试将 128 个物品入队，前 64 个将无延迟入队。然而，后续的 64 个必须等到前 64 个物品被消费。对于第 128 个入队操作，这意味着要等到第 64 个物品被消费。由于状态缓冲区的结构，存在一种“提前退出”条件。这个例子中的第 65 个入队操作只需等待第一个出队操作完成，因为它们都映射到第一个槽位。一般来说，如果我们在队列中的位置距离起点为 \(kN + l\)（其中 \(k \geq 0\) 且 \(0 \leq l < N\)），那么我们将等待 \((\max(k - 1, 0) \cdot N) + kl\) 次操作。从上面的例子来看，我们排在队列的第 65 位。代入 \(k = 1\)、\(l = 1\)、\(N = 64\)，可以看出预测的等待时间为 \(0 \cdot 64 + 1 \cdot 1 = 1\)，这正是轮到我们之前发生的出队操作次数。可以轻易证明这对消费者也是同样的。 此外，这个开销将随着等待者对面类型的参与者数量线性减少**。这意味着我们的等待时间上限可以表示为 \(((\max(k - 1, 0) \cdot N) + kl) / j\)，其中 \(j\) 是相对于等待者而言另一种类型的活跃参与者数量。 > * “活跃”是指正在执行其操作的参与者。稍后我们会看到，我们还提供了“可驱动”的操作。这样的操作如果不定期驱动，会导致死锁。 > ** 不考虑缓存争用以及多个核心/线程访问同一内存带来的开销。 ### 最小化队头阻塞 这个实现还通过允许消费者和生产者相互超越来最小化队头阻塞。由于状态缓冲区的结构，经历减速的消费者或生产者只会影响自己的槽位。例如，如果有 2 个生产者正在入队物品，第一个在第一次入队操作时减速或暂时挂起，第二个生产者仍然可以自由地入队最多 \(N - 1\) 个物品* 而不会阻塞。只有当第一个生产者的入队未完成，或者已完成但物品未被出队消费时，第二个生产者才会在第 \(N\) 次操作时被阻塞。类似地，如果有 2 个消费者在运行，第一个由于某种原因减速或停止，那么另一个将不受影响，持续 \(N - 1\) 次操作*。 > * 对于生产者的情况，我们假设队列完全为空；对于消费者的情况，假设队列完全满。 ### 可驱动的入队/出队操作 默认情况下，入队或出队操作会自旋等待直到轮到自己，然后执行所需的操作。这并不总是可取的。作为替代，提供了每个操作的“可驱动”版本。可驱动版本返回一个结构体，该结构体借用了队列，并有一个方法 `drive`，该方法接受参数 `num_attempts`，即尝试操作的次数，如果失败则返回给调用者。由于队头阻塞的影响被最小化，可以在事件循环或其他某种异步处理中使用此功能，而不会严重影响其他队列操作。当然，它对其他队列操作的干扰程度因执行队列操作的参与者数量以及驱动/轮询的频率而异。 ## 技术限制与值得注意的行为 ### 可能（但不太可能）的未定义行为 虽然队列在设计上即使在整数溢出时也能工作，但*理论上*仍然存在未定义行为的风险。简而言之：在一个 `usize` 类型大小为 \(n\) 位的系统上，如果尝试入队 \(2^{n-1} + 1\) 个物品，并且在最后一次操作运行时第一次入队操作尚未完成，则会出现竞态条件。这种情况发生在 \(2^{n-1}\) 边界处，因为如前所述，我们屏蔽了预约号的最高位并用它来表示票的类型。因此，预约号比正常的 `usize` 类型更早溢出。这种溢出导致第 \(2^{n-1} + 1\) 次入队操作的预约号为 0，与第一次操作的号码相同。这触发了竞态条件，因为两个生产者都试图对同一内存地址进行非原子写入。如果队列传输的数据类型不能复制多次，这个问题也很相关。出队操作是对数据缓冲区条目的按位复制，对于像 `Box` 或 `Vec` 这样的类型来说，这很成问题。存在两个或多个按位相同的此类类型副本可能导致各种错误和未定义行为，例如双重释放和访问无效内存。因此，尝试一次出队 \(2^{n-1} + 1\) 个物品也存在第一次和最后一次操作之间的竞态条件风险。 这种行为显然极其不可能。它需要生成 \(2^{n-1} + 1\) 个线程，并让它们同时尝试入队，或者创建 \(2^{n-1} + 1\) 个可驱动操作，然后依次驱动它们完成。