三大家都不做的东西，我们写了四版

上一篇讲了地址。这篇讲另一个轮子——无锁优先级队列。它没那么幸运：市场上真的没有现成的。我们查遍了官方库、开源实现和商用方案，最后只能自己写；而自己写的过程，又反过来解释了”为什么没有现成的”。

需求长什么样

TC.Tier 需要一个优先级队列原语，给后台任务循环这类场景用：

多生产者多消费者（MPMC）；
严格优先级（不是”近似”或”松弛”）；
支持异步等待；
零外部依赖。

先看现成的有什么。

官方库：三家都没有

库	优先级队列	并发版本？
.NET	`PriorityQueue<T,P>`	无——非线程安全，BCL 里没有并发版本
Java	`PriorityBlockingQueue`	有，但是单把 `ReentrantLock` 的二叉堆
C++	`std::priority_queue`（STL）／`concurrent_priority_queue`（TBB）	STL 非线程安全；TBB 的也是锁实现

这里有个耐人寻味的对比：三大家都在无锁数据结构上投了注——Java 有无锁的 ConcurrentLinkedQueue、ConcurrentLinkedDeque、ConcurrentSkipListMap；.NET 有 ConcurrentQueue/ConcurrentStack/ConcurrentBag；TBB 也有一整套——唯独优先级队列，三家给的都是锁或非线程安全版本。

这不是疏忽，是共同的判断。

Java 的”无锁优先队列”其实是个 map

Java 生态里最接近”无锁优先队列”的是 ConcurrentSkipListMap：基于跳表的并发有序映射，读路径无锁、写用 CAS，可以当优先队列用（pollFirstEntry 就是删最小）。

但注意它的身份：它是 map，不是 queue。JDK 的并发包里从来没有一个叫”无锁优先队列”的东西。

为什么 JDK 选跳表而不是堆？因为堆的结构天生反对无锁化：sift-up/sift-down 会牵连一条路径上的多个节点、还要动根——插入删除常常需要”全局调整”，并发环境下只能用全局锁。跳表只需要局部更新——改几条链的指针就行，天然适配 CAS。所以 JDK 把”并发有序”这个能力放在了跳表上。

顺带一个细节能看出堆方案的妥协：PriorityBlockingQueue 唯一无锁的地方是扩容——数组分配太慢，它会在分配期间释放主锁，用一个 CAS 自旋锁保证只有一个线程在分配。就这样，主路径还是老实一把大锁。

论文里有，落地没有

学术界早就给过答案。最著名的是 Sundell & Tsigas 的《Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems》：

基于跳表、完全无锁、有线性化证明；
自带无锁内存回收方案；
论文实测：3 线程以上比锁实现更快。

此外还有 Lotan & Shavit 的细粒度锁跳表版本、Linden & Jonsson 的缓存友好变体，以及 MultiQueue 这类松弛语义（relaxed）方案——不保证拿到全局最小，只保证”接近最小”，用语义换扩展性。

所以是”只有论文，没有落地”吗？基本是。唯一的例外是论文作者自己的商业库，但它始终是学术/商业小众产品；主流三家到今天都没有采用。

为什么落不了地：四个原因

一、实现复杂且脆弱。 有人尝试把 Sundell 的伪代码复刻成 C++，评价是”非常复杂、混乱、易错”。无锁算法的正确性论证和实现之间的距离，往往比想象的大——我们自己的经历可以作证（见下文）。

二、安全内存回收是真正的硬骨头。 论文假设手工内存管理：节点删除后不能立即释放（其他线程可能还持有引用），必须上 hazard pointer / epoch / 引用计数。这一层往复杂度上再加一个量级，而且写错了是静默的数据损坏，不是崩溃。

三、最根本的：删最小本质是单点串行。 这条最关键，也最容易被忽略。

严格优先级队列有两个天然热点：

所有消费者抢同一个最小元素（队头）；
同优先级的入队全部打到同一个尾插点。

也就是说，热点是不是”单点”决定了扩展性，而不是你用锁还是 CAS。无锁只解决”锁的争用”，解决不了”大家都要碰同一个元素”这件事。我们实测印证了这一点：跳表优先队列在纯出队负载下，细粒度锁的”区间并行”收益为零——所有操作都打在队头上。“无锁”属性本身不带来扩展性——热点是不是单点才带来。

更扎心的对照：我们自建”一把大锁 + 内置堆”，在部分负载下全面胜出无锁跳表（8 线程 32.0 Mops/s vs 12.6、单线程 305ns vs 423ns、think-time 尾延迟全场最优）。大锁的边界是”持锁者被外部长延迟阻塞时全队放大”（毒丸测试里 max/p50 放大 20 万倍、p999 放大 94 倍）——但只要临界区短、持锁者不被抢占，它反而更快。

四、松弛语义的替代品更划算。 既然严格语义注定单点，不严格的应用就干脆用松弛方案（多个子队列并行、取到的可能不是全局最小）换扩展性；而需要严格语义的应用，多数用”一把锁 + 堆”就够了。“严格的、无锁的、高吞吐的”这个组合，需求本身就窄。

我们自己的验证

明知如此，我们还是自己写了——因为需求里”严格 + 异步 + 零依赖”三条都不能让步。结果是把”论文到落地”的距离亲测了一遍。

跳表选型没什么悬念（Fraser & Harris 的纯无锁版本；设计目标是”最高层直链 → 删最小期望 O(1)”）。难的是我们在论文前提之外多要了两样：零分配池化（论文假设 GC）和微秒级内存回收（论文交给 GC/hazard pointer）。根因档案里记下了这个难度的本质：

难的不是跳表，是我们同时要三样论文没一起证明过的东西：lock-free（论文有）+ 零分配池化（论文假设 GC，没有）+ 微秒级节点回收（论文交给 GC/hazard pointer，没有）。

这两样一叠加，论文的五条不变式我们实测只满足了一条，另外四条各缺一角：

论文不变式	我们的偏离 → 失效模式
节点身份不可变（一次链入，key/next 终身不改）	池化复用改了节点的字段：复用窗口内别人读到新旧混合状态
mark 与指针同原子域	✅ 这条做对了（128 位 CAS 的功劳）
splice 永远能读到死节点的 next	边存索引经表间接寻址，回收可与 splice 并发 → 只能拔链 → 后缀整段丢失
回收迟后于最后一个读者	epoch 没覆盖”回收与 splice 的交错”
插入全层原子发布	高层 best-effort 发布 → 悬空捷径永久指向旧拓扑

四种失效模式（错位链接、断链丢后缀、热自旋、僵尸捷径）正好各对应一条缺失——不是巧合，是必然。

然后是打地鼠：每次修复都对，但只关掉一种交织，下一种换个马甲回来。最后靠一次楔死现场 dump 才定位到根因：

_count = 4（只消费了 4 个，已入队 406）
head.F0 = (0, unmarked)    ← 0 层主链从根断了
head.F5 = (id=522)         ← 唯一活着的入口是条悬空捷径
3 个生产者都卡在 get_Key    ← 热自旋，CPU 累计 1517 秒

链条是这样断的：某个节点被标记删除后，标记的后继指向了它自己，形成后向边；搜索逻辑去清理它，把前驱的边改成指向自己且未标记——成环。然后 key 步进循环就在自环里永远转下去。教训写进了档案：修复都发生在”行级 CAS”层面，而缺陷在”协议不变式”层面。

四条路线都试过：回归论文前提（现在生产用的，接受每操作一次分配）、非托管内存 + 代数 + epoch（零分配达成，但回收协议仍有余洞）、入边计数、Hazard Pointers。没有一条同时做到”正确 + 零分配”。

最后那条值得单独讲，因为它最容易被误读成”想了想没做”。事实是：我们连原语都自己写出来了——一个通用的无锁回收原语（Hazard Pointers），带独立测试和一套调试仪器（解引用点校验）。用它实现的版本把删除协议整体移植到”槽位世界”，17/20 个测试形态转绿（含零分配、守恒排空、楔死看门狗），过程中还揪出过真正的 use-after-free（释放顺序颠倒，AccessViolation 实证）。但最后卡在”并发双重归还”：2 线程、260ms 就能稳定复现，排除了五个候选根因之后仍未定位。

收档记录留了一句方法论的账：“取证应一次实验一个判别维度”。

而最扎的是：这套通用 HP 原语目前唯一的消费方，就是它自己那个未解决的问题。“没解决”不是缺工具——工具是我们自己写的；缺的是让协议自身可以被证明的能力。 这才是论文与落地之间那段距离的真实质地。

结论

如果今天有人问我”要不要用无锁优先队列”，答案取决于三件事：

优先级是否必须严格——如果不严格，松弛方案（或离散分桶）在扩展性上赢很多；
延迟敏感度与临界区长度——如果临界区短，一把锁 + 堆往往是被低估的答案；
是否非要零分配——如果要，请准备好面对内存回收这只真正的拦路虎。

业界三大家不给无锁优先队列，不是做不到，是算过账：严格的单点热点吃掉了无锁的收益，内存回收抬高了成本，松弛替代品在多数场景更划算。这个账我们自己也算了一遍，结论一样。

本文事实来自 TC.Tier 的优先队列使用文档、性能基准与那份并发正确性根因档案。