上个月发了一篇讲队列的文章，标题里大大方方挂着"wait-free"，正文里还义正词严地分析了一通为什么它 wait-free。当时我真心觉得这队列设计得挺好——每个操作我都自己捋过好几遍，没有任何线程会卡在另一个线程身上，完全没有。
结果一个 Reddit 用户在评论区贴了一句话，我盯着屏幕看了半分钟。
他说：wait-free 的定义是——任何线程的失败或挂起，不能导致其他线程的失败或挂起。你的队列，一个线程跑到一半挂了，另一个线程会在它留下的状态上永远转圈。
我心想，这不叫"挂起"吧，这是"等待"。
对，问题就在这。wait-free 里的 "wait"，说的不是"等一会儿"，是"绝对不等"。不是"通常不需要等"，不是"大多数情况下不用等"，是永远不需要等。我那个队列，生产者死了，消费者就在它没做完的操作上原地打转——这他妈就是 wait。
我盯着那行评论看了半分钟，脑子里一片空白。然后我把文章里专门讲 wait-free 的那一节删了，删完又看了一眼，整段都不对劲，最后全删了。但更难受的东西在评论区底下等着我。
r/rust 那帮人，是真的较真。matthieum 自己写了一长串，把我那队列的几个隐蔽问题挨个指出来。我没全看明白，到现在也没全看明白，但那句"任何线程的失败或挂起不能导致其他线程的失败或挂起"我记住了。这辈子都忘不掉。
评论区里有人提到 LCRQ，说这个算法原本依赖双宽度 CAS，近几年才有人把那个依赖去掉，让它能移植到更多硬件上。还有一篇 PPoPP 2023 的论文，写的是 LPRQ，跟改进的 lock-free 队列有关。我好几年前读过 LCRQ——当时觉得，"哦，一个更快的 MPMC 队列"，讲完了。这次被人点醒之后重新想了想那篇论文里那些近乎偏执的细节——为什么预留槽位、怎么处理空循环——才意识到人家为了消除那几个瓶颈，花了多少年。
然后我就开始怀疑人生了。我凭什么觉得我随手写的一个队列，比这帮做无锁数据结构做了十年的人更接近 wait-free？
更让我清醒的是另一个评论。一个做过硬实时工业自动化的哥们说，他职业生涯里只需要过一次 wait-free 保证，然后补了一句——那是他做过最糟糕的工作。
画外音：注意，是"最糟糕的工作"，不是"最有趣的工作"。
嵌入式那套工具链有多烂他不说我也知道。他还吐槽了 MISRA 静态分析工具的质量，说完全忽略了学术界和工业界的现状。那个我确实想展开聊，但算了，跑题了。
他那个点特别扎人：wait-free 不是免费的。你为了一个"任何线程都不等待"的保证，得牺牲吞吐、牺牲内存占用、牺牲可维护性——换来的东西，绝大多数情况下你根本用不上。他后来其他项目都用 Vyukov MPMC cycle queue 的后代，因为那玩意儿在速度等指标上好得多。
评论区好几个人都是这说法。用了好几年 Vyukov 的后代，试过别的，最后还是回到它上面来。这让我想起一个老段子：lock-free 和 wait-free 是具体且昂贵的属性，你选它不是因为"它是最好的"，而是因为"你需要它"。多数人的队列跑在十六核的机器上，吞吐才是真需求，争那一个"任何情况下都不会等"的名分，毫无意义。
然后有哥们把有界队列的底层约束摆出来了——慢消费者会阻塞生产者，这是物理规律，跟无锁不无锁没关系。想要全局 FIFO 加多生产者？那慢生产者就会阻塞消费者，躲不掉的。想要原子提交？你就不能有单独的预留阶段，否则要么内存无界要么 ABA 问题出来找你。这几条他写得清清楚楚，我读了好几遍。
我原来以为这些问题我有答案。现在我知道了：我连问题都没问到。
哦对，评论区还帮我校验了一遍代码。有人在我那个 WFQueue 库的一个文件里发现了个翻大车的写法：
unsafe impl Sync for WFQueue<T> { }
unsafe impl Send for WFQueue<T> { }
这两行看着平平无奇，对吧？问题是 T。这个 impl 是给所有 T 强上的，包括 Rc<T> 这种不该跨线程的东西。你以为你在对一个队列做 Sync 的保证，实际上你是把对 T 的约束完全丢了，帮人家把 Rc<T> 跨线程传递的大门给踹开了。那哥们给的修正也很直接：
unsafe impl<T: Sync> Sync for WFQueue<T> { }
unsafe impl<T: Send> Send for WFQueue<T> { }
就多个约束。但就是这俩约束，你的库才不是"随时烧穿你内存的 C 代码"。评论区还有一层更细的讨论，说这队列不对外提供 &T 的引用，所以 T: Send 就够，Sync 那侧也得写 T: Send——我记得貌似是这么说的。那种讨论，就是你写一个库、贴到 Reddit 上之后，等着别人来帮你找补的东西。
说实话，看到那个 unsafe impl 的时候我反而松了一口气——好歹是个具体的问题，能修。比"wait-free"这种从概念上理解错了的东西好对付多了。一个多打两个约束就行，一个得把一整套理论重新学一遍。
后来我又翻到一条评论，说有两种技术开始被越来越多的人用了：不对称栅栏和 membarrier()，比十年前常见多了。还说 Nathan Bronson 在斯坦福的工作到现在还是这个领域的地基。
那个名字戳到我了。好几年前读 RocksDB 源码的时候见过这个名字，于是又去翻了一遍他讲无锁数据结构的那些东西。
写到这里我想说句话，虽然可能有点绕：评论区里最让我难受的，不是"我说错了"，是"评论区里随便一条评论都比我研究得深"。有人提到一篇 2022 年的 arXiv 论文，编号 2201.02179，讲低复杂度 wait-free 队列，评论者说这个方向的搜索空间已经基本耗尽了。注意，"基本耗尽"——不是"没人做了"，是"能做的大概都做完了"。我在这边写博客声称自己搞定了 wait-free，那边几万块拼图已经拼得七七八八。我以为我那块拼图能塞进去，只是因为我根本不知道拼图长什么样。
所以以后见到"wait-free"这三个字母轮到我用的时候，我会先复制一遍那个定义，再问自己三个问题：这个数据结构在什么情况下会等？我等得起吗？等不起的话，用别的方案行不行？
如果你的答案是"一个线程死了会导致另一个线程永远转圈"，那你就封顶到 lock-free。别管那个词听起来多好吃。
本期缴税：一个被我误用了一整年的术语，加一次在公共场合被纠正的社死。
下次见。