【Nahla介绍】有一个名为Nahla的平台其官网可访问。在该平台上有主页、关于我、博客、版权声明、联系方式等内容。【女孩实现有界等待快速MPMC队列】2026年3月12日一位女孩着手编写一个数据结构以实现多个线程之间对缓冲区的可变共享逐渐对无锁数据结构产生兴趣决定实现一个无等待队列。她认为这个队列速度不错值得写篇文章分享且想在长篇文章后写点简洁内容。她强调这只是对无锁/无等待编程的实践探索减少对其他相关工作的引用仅在自己机器上对其他队列实现进行基准测试希望得到专家反馈。【设计】【理论】该队列基于票务锁等待系统工作有两个票务分发器一个供生产者一个供消费者还有一组编号从0到N - 1的N个盒子每个盒子上方有显示屏显示轮到谁操作。消费者和生产者操作流程是从相应票务分发器取票找到对应盒子等待预订号码显示后执行操作。预订系统能确保盒子初始为空、第一个被叫到的票是生产者的票号、同一类型的票不会连续被叫到两次保证生产者总有空盒子消费者总有满盒子。【实际实现】实际实现使用两个AtomicUsize计数器和两个环形缓冲区一个“数据”缓冲区传递物品一个“状态”缓冲区记录归属权。使用的结构体如下// 为防止伪共享添加缓存填充/// 一个基于数组的无等待有界队列pub struct WFQueueT, const N: usize { // 使用 NonNull 指针而非 Box以避免意外解引用导致未定义行为UB。 // 使用手动分配内存避免在不再拥有值的所有权时Box 在析构时意外调用 drop 方法。 data: NonNull[CachePaddedT; N], state: NonNull[CachePaddedAtomicTicket; N], prod_reserve: CachePaddedAtomicUsize, cons_reserve: CachePaddedAtomicUsize,}AtomicTicket类型是对AtomicUsize的简单封装用最低63位存储票号/预订号码最高位表示票的类型。状态缓冲区条目的值表示拥有相应预订号码和票类型的人对数据缓冲区中相同索引条目的独占读写权限。预订号码由原子计数器通过fetch add操作递增1产生对应的状态和数据缓冲区索引通过将预订号码对N取模得到采用优化方法使缓冲区大小为2的幂次方。生产者入队过程是先将生产者计数器加1保存预订号码等待状态缓冲区条目匹配且轮到生产者操作存储值到数据缓冲区槽切换状态缓冲区条目状态位。消费者出队过程是先将消费者计数器加1保存预订号码等待状态缓冲区条目匹配且轮到消费者操作读取值设置状态缓冲区条目值和状态位。【优点】【无CAS循环最小化缓存争用】该系统无CAS循环通过不断从状态缓冲区读取等待操作使槽的缓存保持共享状态最小化争用只有操作完成后所有权状态才改变。【有界等待】除线程挂起或失败情况外对该数据结构的操作有时间上限能保证无消费者或生产者饥饿所有入队和出队操作最终完成但需同时有消费者和生产者运行。参与者等待时间取决于其在轮询队列中的位置和相反类型的活跃参与者数量等待成本会随相反类型参与者数量线性下降。【最小化队首阻塞】该实现通过允许消费者和生产者相互竞争最小化队首阻塞某个消费者或生产者操作变慢只影响自身槽。【可驱动的入队/出队操作】默认入队或出队操作会自旋等待也提供可驱动版本返回借用队列的结构体有drive方法可在事件循环或异步处理中使用对其他队列操作干扰程度因参与者数量和驱动/轮询频率而异。【技术限制与显著特性】【可能但不太可能出现的未定义行为】该队列设计虽考虑整数溢出但仍存在未定义行为风险在usize类型为n位的系统中入队2^(n - 1) 1个物品且第一次入队操作未完成时会出现竞态条件。若队列传输的数据类型不能被多次复制出队2^(n - 1) 1个物品也会产生竞态条件。这种情况极不可能发生在32位系统中约20亿多个物品64位系统中约9220万亿个物品才可能触发。【可驱动操作丢弃成本高】丢弃可驱动操作结构体成本不低因为必须将操作驱动至完成否则缓冲区槽将永久禁用后续操作会被卡住。【基准测试】【方法】为测试系统吞吐量设计合成基准测试测量入队和出队2^24个usize类型物品所需时间。基准测试分为N个消费者和N个生产者N从1到8、1个消费者和N个生产者N从2到15、1个生产者和N个消费者N从2到15三类。使用criterion库/框架获取结果测量时尽量减少运行程序数量测量系统规格包括CPU为Ryzen 7 7800x3D、内存为32GiB DDR5、操作系统为Fedora Linux 44、Rust版本为稳定版1.95.0。【结果】不同情况下的测试结果如下【N个消费者和N个生产者】生产者/消费者数量平均时间吞吐量百万元素/秒1273.83 ms245.0821.6282 s41.21731.5460 s43.40941.1904 s56.37651.3291 s50.49161.2740 s52.67671.2557 s53.44481.2323 s54.458【1个生产者和N个消费者】消费者数量平均时间吞吐量百万元素/秒21.7334 s38.71531.4798 s45.35041.3076 s51.32451.3209 s50.80461.3080 s51.30671.3108 s51.19881.2972 s51.73491.2118 s55.378101.1153 s60.168111.0780 s62.251121.0267 s65.36213979.17 ms68.53714946.06 ms70.93515908.89 ms73.836【1个消费者和N个生产者】生产者数量平均时间吞吐量百万元素/秒21.6983 s39.51631.3665 s49.11041.2241 s54.82351.2093 s55.49561.2463 s53.84571.2616 s53.19381.2981 s51.69991.1763 s57.049101.1314 s59.317111.0601 s63.302121.0314 s65.06413958.98 ms69.98014936.77 ms71.63915911.65 ms73.612【分析与结论】与其他队列相比这个队列性能不错在1个消费者和1个生产者时稍逊一筹但随着消费者和生产者数量增加扩展性良好。在N个消费者和N个生产者测试中性能在N 4时达到峰值后下降又提升不同的消费者与生产者比例可能带来更高的最大吞吐量作者想后续再深入研究。【源代码】实现的源代码以及单元测试和基准测试代码可在相关链接找到。