系统与数据库2016chaoran.me
一种与 Fetch-And-Add 同样快的无等待队列
A Wait-Free Queue as Fast as Fetch-And-Add
专业 · 约 75 分钟读完前置知识：并发编程基础、无锁数据结构、原子操作与内存序
导读
论文提出一种新的 wait-free 队列，宣称性能可与 fetch-and-add 相当。评论围绕它是否支持 MPMC、为何采用链式结构而非 ring buffer，以及其“双端 wait-free”是否只是用 helping 把自旋限制在 O(#threads^4) 展开；作者也公开了 MIT 许可的实现。
HN 关注点：wait-free 队列能否在保持高性能的同时真正实现多生产者/多消费者，以及论文的 wait-free 声明在 helping/自旋上是否站得住。
后来怎么样
提出了性能可与 fetch-and-add 相比的 wait-free MPMC 队列，其 helping 思路和 MIT 许可开源实现成为后续 wait-free 队列研究的重要参考与性能基线。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
质疑询问论文是否真正支持 MPMC，并肯定开源实现易读且采用 MIT 许可。
我以前玩过一阵 wait-free 算法，但一直没做出什么有意义的东西。支持多消费者多生产者（MPMC）的 wait-free 队列可以说是 wait-free 数据结构的圣杯。不过它真的是 MPMC 吗？我翻了下 PDF，没找到明确说法……另外给 Chaoran 点赞，把实现放到了 GitHub：https://github.com/chaoran/fast-wait-free-queue，代码看起来易读，而且是 MIT 许可。
svckr查看英文原文
I've been playing with wait-free algorithms some time ago but never got anywhere meaningful. A wait-free queue for multiple consumers and multiple producers would be kind of the holy grail when it comes to wait free data structures. Is it MPMC though? I skipped through the PDF and could not find a definitive claim… Also, big thumbs up to Chaoran for putting the implementation on GitHub: https://github.com/chaoran/fast-wait-free-queue The code looks like it is easy to follow and it's MIT licensed.
补充质疑为何 lock-free 队列文献多用链式结构而非 ring buffer，并指出 ring buffer 通常受单读单写限制。
我最近刚了解到，一个相当简单的 ring buffer 实现就是 lock-free 的，甚至不需要 CAS 这类原语（虽然需要内存屏障）。尽管如此，我看到的 lock-free 队列文献（包括这篇）都是某种链式结构。为什么呢？我猜 ring buffer 的一大限制是只适用于单读单写；不过也许可以用 CAS 原语绕过去……
adrianratnapala查看英文原文
So I just recently learned how a rather simple ring buffer implementation is lock-free and doesn't even need primitives like CAS (although it does need memory barriers). In spite of this, all the literature about lock-free queues that I see (including this one) is for some kind of linked structure. Any reason for that? I guess one big limitation of the ring buffer is that it only works for a single reader and single writer. Although maybe you can work around that using CAS primitves...
补充指出“双端 wait-free”依赖 helping，并非无自旋，且自旋上界为 O(#threads^4)。
补充背景：传统 wait-free 队列只对写或读一侧是 wait-free，另一侧必须在原子 fetch 循环里自旋，等待那个多步操作完成。论文里的 double wait-free 队列是用一个技术性手段取得这个名号的：它把自旋换成了遍历所有线程、替可能卡在多步操作中间的线程完成操作。并不是没有自旋，而是自旋被线程数限界了。更正：按论文说法，自旋上界是 O(#threads^4)。
kbwt查看英文原文
For context, the traditional wait-free queues are only wait-free for one side, writing or reading. The other side has to spin in an atomic fetch loop, waiting for the wait-free multi-step operation to complete. The double wait-free queue from the paper is using a technicality to achieve its status. The spinning operation is replaced with a loop over all the threads doing opposite (multi-step) operations, finishing them for threads that may be blocked in the middle of the steps. It's not that it doesn't spin, but the spinning is bounded by the number of threads. Edit: Actually, spinning is bounded by O(#threads^4) according to the paper.
亲历亲历称该算法带来数量级性能提升，并已在系统中使用多年。
有意思，我几年前有个同事就实现了这个算法。我们系统的性能确实提升了几个数量级。我已经偷偷把它塞进系统里好几年了 :D
swalsh查看英文原文
Funny, I had a coworker several years ago whom built this exact algorithm. The performance of our system increased literally orders of magnitude. I've been slipping it into systems for a couple years now :D
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖169 分 · 31 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选