侵入式链表与无锁队列：高并发核心原理与工程实战

侵入式链表和无锁队列这俩名字放在一起看起来像是教科书里的基础概念但真正把它们用起来、用对地方中间隔着的不是一层窗户纸而是一整套关于内存布局、原子操作和并发协调的工程经验。如果你正在做高并发的消息中间件、任务调度器、事件循环或者任何一个性能敏感的系统组件迟早会遇到这两个东西。这篇我把核心原理、实现路径和踩过的坑一次讲透希望能帮你把自己的链路真正搭起来。1. 侵入式链表把节点嵌进对象而不是给对象包一层壳1.1 非侵入式与侵入式的本质区别先看一个最常见的链表实现方式。大多数人在学习阶段写的链表容器内部维护一个Node结构Node 里面既有next指针也有可能存储一份数据本身或者指向真实数据对象的指针struct Node { Node* next; int data; // 要么存数据要么存指针但节点归容器所有 };这种设计里的节点是容器的财产对象和你业务数据之间的绑定关系需要通过“复制进节点”或者“指针指向对象”来完成。它的优点是安全对象能脱离容器独立存在缺点也很明显每一次插入容器都要给新节点分配一块内存删除时又要释放内存分配器在高频操作下会成为很大的瓶颈。更麻烦的是如果业务对象本身很大、经常被放进多个容器你需要在多个容器之间来回搬运数据或管理多份节点。侵入式链表换了个思路节点不归容器所有节点字段直接定义在业务对象内部。struct Message { Message* next; // 侵入式链表节点对象自己携带 uint32_t payload; // 其他业务字段 };这时候链表操作函数接收的是Message*通过next指针把对象串起来不需要额外分配节点内存也不需要把数据拷贝进什么容器内部结构。人话版本就是普通链表给每个住客单独准备一间房侵入式链表让住客自己背着房卡房卡就挂在身上。这个区别有多重要看几个实际场景就明白了。1.2 少了两次内存操作多了缓存友好最直接的好处是消除了节点分配的频率。在高吞吐场景下如果每秒操作几十万条消息每条消息进出队列都需要malloc和free一次再优秀的分配器也会在锁竞争、内存碎片上拖慢整体速度。侵入式链表把节点分配这件事完全省略掉了因为节点是对象本身的一部分到了工程里你会发现连“分配一个节点再把数据填进去”这行代码都不需要写。第二个隐藏优势是缓存局部性。非侵入式容器下Node和数据对象之间往往隔着一层间接引用CPU 读取Node-data时大概率发生一次缓存未命中如果数据本身很大或散布在不同内存页还会触发更多缺页。侵入式设计把next指针放在对象的开头或固定偏移处一次加载对象头就能顺带读出链表指针遍历时的访存效率高出一截。我自己实测过的简单遍历里链表较长时侵入式版本访问一次的耗时能做到非侵入式版本的一半左右数据量越大、节点越密集差距越明显。第三个特性是O(1)删除已知对象。这个在非侵入式链表里不是做不到而是要做些额外功夫——通常你得先找到该节点在链表里的位置或者用一个复杂结构记录节点和对象之间的映射。侵入式链表则很自然你要删除某个对象它带着next指针只要你不在算法过程中把前后指针弄丢直接把前驱节点的next指向当前节点的next即可不需要知道它排第几个。1.3 生命周期的账要自己算清楚我经常提醒第一次用侵入式链表的人容器不再拥有节点你的业务代码必须保证两件事一个是对象在链表中期间不能被销毁另一个是删除时要把next指针正确摘除避免悬挂指针。社区里通常把保护裸指针的工作交给更高级的机制比如延迟回收、引用计数或 ring buffer 内存池这些和侵入式链表配合使用正好形成一套完整方案。如果你只是打算写个简单的单线程侵入式链表代码可以很短struct ListNode { ListNode* next; }; template typename T class IntrusiveList { private: ListNode* head_; public: void push_front(T* item) { item-next head_; head_ item; } T* pop_front() { if (!head_) return nullptr; T* item static_castT*(head_); head_ head_-next; return item; } };这里T继承自ListNode借助基类子对象把next嵌进对象内部。这套代码看着简单但它把容器和所有权的语义标得很清楚容器只是帮你维护链表的顺序关系节点的内存分配与释放都由你的业务逻辑决定。说它是“基石”并不是因为我喜欢概念上的优雅而是因为后续所有无锁结构都会基于这个核心模型继续演进——CAS 指令操作的是某个对象的地址对象地址和链表节点的地址若分离每次操作里都要多一次间接转换。把所有并发操作建立在一个节点内嵌、地址稳定、生命周期可控的结构上才是无锁队列能落地的基础。2. 从插入和删除看侵入式链表的并发潜能2.1 单线程下侵入式链表为什么会快看完上一节你可能觉得侵入式链表只是省了内存分配这对单线程场景已经足够有意义了。不要小看这一点大部分业务对象本身已经从某个池或簿记结构里创建出来了把它们挂进一个列表很多时候只是顺手的事。单线程下侵入式链表循环遍历时预取友好删除已知节点也不用扫描整体代码分支也更少编译后指令数明显少于非侵入式容器。有人可能会提出C 风格的定制链表也能做到类似效果——对侵入式链表本来就是 C 语言时代就在用的方式内核里大量对象都在使用“结构体内嵌链表节点”的思路。只是到了现代 C 里由于模板泛型、继承和定制化手段的增强侵入式链表依然保留很高的竞争力。2.2 单写多读场景下的 release/acquire 组合如果项目允许你只用一个线程写、多个线程读一个链表那就要认真考虑要不要上真正的无锁。这时候std::atomic里的release和acquire语义就是你的第一梯队武器。用前面那个IntrusiveList做基础想象这样一个场景生产者线程把Message对象推进链表消费者线程从链表里取出来。因为只有一个写者我们不需要在push内部做 CAS 循环只要用release发布新的头部class IntrusiveMPSCList { private: std::atomicMessage* head_{nullptr}; public: void push(Message* msg) { msg-next head_.load(std::memory_order_relaxed); head_.store(msg, std::memory_order_release); } Message* pop() { Message* h head_.load(std::memory_order_acquire); while (h) { // 单线程写者下head 只会被一个线程推进 if (head_.compare_exchange_weak(h, h-next, std::memory_order_acquire, std::memory_order_relaxed)) return h; } return nullptr; } };这里的关键是release保证写者把msg-next和msg的其他字段写入完成后再发布head_消费者用acquire读取head_由此能看见对应的那次写操作“之前”所有内存写入。不熟悉内存序的人经常在这里栽跟头——以为 atomic 本身保证了可见性其实真正保证顺序的是你指定的内存序。2.3 把 push/pop 变成原子指令一个简易的无锁栈雏形真正的多写者场景下每个线程都要能独立调用push。这时要在push上做一次 CAS 重试循环void push(Message* msg) { Message* old head_.load(std::memory_order_relaxed); do { msg-next old; } while (!head_.compare_exchange_weak(old, msg, std::memory_order_release, std::memory_order_relaxed)); }整个过程听着非常轻松读取当前头把新节点 next 指向它CAS 替换头。这也是最经典的无锁栈思路。但很多人在这个跨门槛的时候没意识到栈和队列虽然只有一字之差无锁化的难度却不在一个量级。栈的并发操作只需要竞争一个共享指针head队列则需要同时维护头部和尾部两个共享指针还要处理“头部和尾部之间的空窗口期”。这也是标题里“基石”二字的真正含义——先掌握这套原子化的操作思路才有资格接着去啃队列这个硬骨头。3. 无锁队列的核心矛盾FIFO语义与内存安全3.1 无锁队列需要回答的三个关键问题队列本身的语义很简单先进先出。但站在并发环境下它要同时回答三个问题顺序正确多个生产者完成的插入顺序消费者必须按某种一致的全局顺序取出。状态一致消费者看到的“空队列”不能是某个生产者还没写完时的假象。内存安全一个节点被消费者取走后不能立刻释放因为可能还有其他线程正持有着对这个节点的指针做 CAS 操作。这三个问题互相关联任何一个没想清楚队列跑起来就会以极其诡异的方式崩溃或丢数据。3.2 一个经典的哨兵节点模型我常给团队里的新人用这个模型讲无锁队列队列中始终维持一个持久化的哑节点dummy nodehead永远指向这个哑节点tail指向链表的最后一个有效节点。struct Queue { std::atomicNode* head_; std::atomicNode* tail_; Node dummy_; Queue() : head_(dummy_), tail_(dummy_) {} };生产者的操作可以拆成两步把新节点的next置为nullptr尝试 CAS 把它挂到tail当前指向节点的next上。挂载成功后尝试把tail推进到新节点。消费者的操作则可以拆成读取head指向的哑节点。读取它的next若为空说明队列为空若非空把新头 CAS 过去并返回数据节点。哑节点设计最大的好处是即便队列只剩一个节点head和tail也不会碰撞到同一个真实数据节点上从而避免了一些极端竞态条件。如果你直接把head指向第一个数据节点那么最后一个数据被取走时head 和 tail 都想指向nullptr此时没有任何一个稳定存在的地址可以充当“中间状态”所有比较都会变得很麻烦。3.3 ABA 问题的根源地址复用聊无锁队列不能不提 ABA 问题。我不知道用文字描述大家能不能一下记住举个例子最快有一个栈顶部是节点 AA 的地址是0x1000A 指向 B。线程 M 读取top A(0x1000)它准备把head改成 B。此时线程 N 抢先完成一次pop取走了 A然后push(A)和push(D)结果栈顶变成了新节点D。假设 D 恰好被分配在同一个地址0x1000注意内存复用是完全可能的尤其在有内存池的场景下。然后线程 M 终于执行 CAS把栈顶从0x1000改为 B。问题来了线程 M 认为从它读取到 CAS 执行这段时间里栈顶从未变过所以可以放心替换。可实际上栈顶已经经历了 A→空→D→A这样的完整轮回链表结构早已不是它读到的那个模样。这种错误就叫 ABA 问题发生的充分条件和必要条件就是那个地址被复用、又被放回原位。时间点栈顶内容线程 M 视角T0A读到 top Anext BT1B线程 N pop AT2空线程 N pop BT3D线程 N push DT4A线程 N push AA 地址复用T5B其他M 执行 CAS(A→B) 成功但链表已经全变了解决 ABA 问题最常用的办法是给指针打包一个修改计数每次修改栈顶时不仅更新指针地址还要把计数器加一。CAS 比较的是“地址 计数器”组成的整个字。这样一来即使节点地址复用计数不同CAS 也会失败不会错误地覆盖新结构。这个方案有一个工程约束你得有足够宽的原子变量。64 位系统上指针本身占 48 位地址空间相关剩下十几位可以放计数有些平台还提供双字 CAS。不过实践中我建议先把语义做好再考虑计数位宽不然优化过度反而难排查问题。如果你的系统里没有内存池、所有节点都来自new那 ABA 问题可能出现得更无规律因为地址复用的模式更随机。3.4 释放安全无锁队列的第二颗毒药即使解决了 ABA还有一个容易被忽略的大坑节点被消费者取走后你能不能立刻delete答案是通常不能。为什么可能有另一个生产者线程已经读到了这个节点的地址正拿它做 CAS 的旧值比较。如果你把这个节点释放了在它上执行的 CAS 会读到一段已经还给分配器的内存可能出现数据竞争或未定义行为。安全释放的三种典型方案延迟释放节点下来之后先进一个回收队列等过一段足够长的时间确认所有线程都不再持有它再真正释放。实现简单但延迟不可控。Hazard 指针每个线程维护自己的危险指针列表消费者取节点之前把地址登记到列表里这样其他线程看到这个地址还在列表里就知道不能释放。实现稍重但回收时机很及时。基于代际的 Epoch 回收用版本号标记阶段等到所有线程都在同一个较新版本里旧节点就可以安全释放。这类方案在维护大量线程时开销比较低。从工程角度说如果你只是构建一个中等规模的应用先用延迟释放或 HAZARD能让你把精力集中在队列核心逻辑上。等真遇到延迟不可接受的性能瓶颈再上更精细的回收机制不迟。3.5 SPSC 和 MPMC 是两个物种写无锁队列之前一定要先确认并发模型否则代码复杂度会失控。SPSC单生产者单消费者是最容易的。因为只有一个写者和一个读者大多数情况下不需要 CAS只需要用读写索引和 memory_order甚至可以直接用环形缓冲区实现性能非常高。MPSC多生产者单消费者稍微难一点需要解决多个生产者竞争尾部的问题但消费者的读取路径仍相对简单。MPMC多生产者多消费者是最难的。生产者和消费者都要对 head/tail 做原子操作还要处理中间状态和释放安全。我见过很多人一开始就直接上 MPMC然后被 ABA、假空和释放问题绕晕。正确路线是先实现一个正确的 SPSC再扩展成 MPSC搞懂了生产者之间的竞争最后再上 MPMC。这条路线每一层的复杂度都是可驾驭的不至于一次性碰到所有坑。4. 一块实战实现MPMC无锁队列的完整链路4.1 总体设计侵入式链表 头部尾部分别原子化既然标题是“基石篇”我就把 MPMC 无锁队列的骨架完整写出来虽然它是后续章节会进一步优化的基础但这份骨架值得你反复咀嚼。核心思路沿用哑节点思想把head_和tail_都做成原子指针pusher 和 popper 各自在自己的端点上工作。class MPMCQueue { private: struct Node { std::atomicNode* next; int data; }; std::atomicNode* head_; std::atomicNode* tail_; Node dummy_; public: MPMCQueue() : head_(dummy_), tail_(dummy_) {} void push(Node* node) { node-next.store(nullptr, std::memory_order_relaxed); Node* tail nullptr; Node* next nullptr; while (true) { tail tail_.load(std::memory_order_relaxed); next tail-next.load(std::memory_order_acquire); if (tail ! tail_.load(std::memory_order_relaxed)) { continue; // tail 改变了重来 } if (next nullptr) { // 期望的尾节点尝试挂载 if (tail-next.compare_exchange_weak(next, node, std::memory_order_release, std::memory_order_relaxed)) { break; // 挂载成功 } } else { // tail 已过期帮它推进 tail_.compare_exchange_weak(tail, next, std::memory_order_release, std::memory_order_relaxed); } } // 挂载成功后尝试推进 tail tail_.compare_exchange_weak(tail, node, std::memory_order_release, std::memory_order_relaxed); } Node* pop() { while (true) { Node* head head_.load(std::memory_order_relaxed); Node* next head-next.load(std::memory_order_acquire); if (head ! head_.load(std::memory_order_relaxed)) { continue; } if (next nullptr) { return nullptr; // 队列为空 } if (head_.compare_exchange_weak(head, next, std::memory_order_release, std::memory_order_relaxed)) { // 取出 next 的有效数据 return next; } } } };这段代码看着不长但每一步都值得展开讲清楚。4.2 push 端为什么需要帮忙推进 tail生产者 push 的第一个动作是把tail-next挂到新节点上。问题在于tail可能已经被其他生产者推进一步了此时tail-next不再是nullptr而指向某个新节点。这时候当前线程不能假装没看到而应该主动帮人家收尾把tail_修正到那个next节点上然后再重新读取 tail 重试。这个“帮忙”语义是 MPMC 队列的关键。它保证了队列不会因为某个生产者线程在挂载节点后、推进 tail 前被调度器剥夺执行权而形成较长的不一致窗口。极端情况下另一个生产者会接手推进 tail但最后的顺序仍然是正确的。4.3 pop 端假空与一致性窗口pop 的逻辑看起来更简单读 head读 head-next如果为空就返回空。但真正要紧的是“读 head 之后head 是否变了”的判断。代码里head ! head_.load(...)这行比较就是为了防止读到过期的 head导致把已经不在队列里的哑节点拿去取 next。另一个经典问题是“假空”pusher 已经把新节点挂上了 tail但还没推进 tail而当前 head 和 tail 都指向旧尾节点此时 pop 可能读到 head-next 为空认为队列空。这会算错吗如果业务允许暂时看到空严格来说没问题因为“队列存在一个瞬间为空”的状态但如果要求严格不阻塞、绝不漏数据就需要在 pop 里再加入“帮助推进 tail”的逻辑把窗口缩到最小。绝大多数业务场景下短暂“假空”不会引起丢数据因为消费者下次循环再来时新节点就已经可见了。前提是外层调用者必须在自己控制的循环里反复调用 pop时刻准备拿到新数据。4.4 节点复用与 ABA 的配套方案上面的实现里push 结束时取走了tail的旧值pop 时又取走了head的旧值这些旧值随时可能因为另一个线程释放节点而失效。所以再强调一次**队列代码本身不能 delete 节点节点释放必须交给延迟回收或 Hazard 机制。**这是无锁队列所有实现共用的潜规则不是某个具体实现的缺陷。如果要用计数方案解决 ABA一种最简洁的实现是把 head/tail 都维护成指针 计数器的复合原子变量。但注意计数器必须和指针在同一个原子存储单元里否则 CAS 无法一次性比较两者。64 位系统上实现这种东西常常要考虑 16 字节对齐和编译器提供的内建原子操作这超出本文范围后续的“进阶篇”我会专门展开。4.5 我踩过的一个典型坑哑节点不能丢第一次写这个队列时我犯过一个非常隐蔽的错误pop 成功返回next后顺手把head指到的旧节点标记成“可复用”并在下一次 pop 时把它当作新的哑节点继续使用。看起来没问题但在 MPMC 下某个消费者线程可能正在基于这个旧哑节点做比较交换一旦这个哑节点被另一个消费者线程复用并写入新数据整个 CAS 基准就全乱了。正确做法是**在整个队列生命周期里哑节点必须保持地址稳定不能回收不能复用。**它就是为了无锁结构提供那个永不改变的“基准地址”。你要么静态分配要么在队列构造时new一个并永不释放。理解了这一点你会发现无锁队列的设计其实处处都在回应同一个问题谁提供稳定的公共锚点5. 性能验证与上线前的检查清单5.1 先证正确性再谈性能无锁代码最怕的不是慢而是“看起来正常但偶尔出错”。所以在跑性能之前我强烈建议先做三类正确性验证多线程随机操作 对拍用一个全局互斥锁保护的普通队列作为参考实现两组线程分别执行完全相同的随机 push/pop 操作最后比较二者拿到的数据序列是否完全一致。数据竞争检测用编译器或运行时提供的检测工具跑一轮压力测试确认没有任何未受内存序保护的共享访问。长时间混沌测试用随机延迟、随机线程数、随机操作比例跑压测几小时甚至在低配环境下故意制造调度不均衡观察是否有崩溃或超时。我自己在测试中会特意压低内存池大小让节点频繁复用、地址反复循环这会放大 ABA 问题的暴露概率。如果这套环境跑不出问题队列核心基本可以放心。5.2 性能到底能差多少一旦正确性过关就可以上性能测试。基准测试最好用四个维度对比单线程调用的理论吞吐、SPSC 并发、MPSC 并发、MPMC 并发以及一个“用互斥锁保护普通 intrusive list”的对照组。场景锁保护链表吞吐/s无锁队列吞吐/sP99 延迟抖动SPSC800万3000万明显降低MPSC300万900万大幅降低MPMC150万400万大幅降低抖动更小这些数字是典型量级具体多少取决于你的机器、编译选项和操作系统调度策略。但方向很一致无锁实现特别能拉开“延迟均匀度”的差距。锁保护方案在竞争激烈时线程切换和等待带来的尾部延迟经常会比均值高二三个数量级而无锁队列的 P99 通常压在均值的几倍以内。有些场景下无锁是不是一定更好不一定。如果你只有一个生产者和一个消费者消息间隔又足够大用环形缓冲实现的 SPSC 会比侵入式链表无锁队列更好——这是另一套实现思路但性能天花板更高。无锁链表版的优势主要在通用性和灵活性适合那些节点必须在线、可以动态插入的复杂任务。5.3 内存序的精细调节代码贴出来是为了让你看懂语义但真正上线前还要过一遍内存序。我的经验是数据本身写入node-next时用release读取时用acquire——这是最基本的发布订阅对。在 CAS 循环里失败的读取可以直接用relaxed因为失败意味着这个值马上会被丢弃重试不承载任何同步义务。在“帮忙推进 tail”的 CAS 里用release是必要的因为推进 tail 的线程要保证自己已经看到了被推进的节点及其内容后续消费者才能安全地读取它。不需要seq_cst的地方千万别用。seq_cst会给所有参与线程建立全局一致顺序编译器生成的指令更多缓存一致性协议的压力也更大无锁性能优势一大半都会因此被吞掉。5.4 上线前 checklist如果要把这套队列接进真实系统我一般会过一遍这样的清单队列的哑节点是否保证地址稳定、不被释放或复用节点的释放是否发生在所有读者都可能持有该指针的时间窗之后push 路径里是否存在长期不推进 tail 的阻塞场景是否有“帮忙”逻辑兜底pop 路径里是否区分了“真空”和“假空”业务上能否容忍短暂的假空CAS 失败的重试是否会无限循环极端调度下有没有活锁可能是否关闭了编译器对共享变量的过度优化原子变量本身会处理但要注意非原子字段写在 CAS 前后的顺序性能压测是否跑到了真实并发线程数和节点复用模式下每一条都对应过真实事故。比如第 2 条早期版本里我用delete释放节点结果线上偶发崩溃最后排查到正是 Hazard 指针机制没做好。第 6 条也很常见——过度信任编译器把一个普通字段的写入放在 CAS 之后造成消费者读到一半状态。写在最后的实操体会我得强调一句侵入式链表 无锁队列并不是所有场景的万能答案。如果队列是有界的数组环形缓冲往往更容易写出极致性能如果节点数量很小、锁竞争很低简单的互斥锁方案反而更好实现、更好调试。这套组件真正的价值在于它为你提供了一个地址稳定、行为可预测、可扩展成多种并发模型的底层骨架。我把“基石篇”这三个字放在标题里意思就是希望你先把这条链路里最底层、最核心的思维模型吃透。后续无论是做内存池、任务调度、事件循环还是消息总线这套基础都会不断被复用。