多线程环境下想维护一个全局的任务栈第一反应基本都是“加把锁”。互斥锁确实简单可一旦压测线程数上来锁竞争导致的线程切换和阻塞延迟就会让人头疼。我之前在一个并发任务池项目里被这个问题折腾过后来用 CAS 实现了一个无锁原子栈把关键路径上的锁彻底摘掉线程安全照样保证延迟还稳了不少。这篇就把完整的设计思路、实现代码和踩过的坑一起整理出来。1. 先搞清楚为什么要折腾无锁栈1.1 锁到底贵在哪很多人对 std::mutex 的性能印象停留在“加锁解锁就几十纳秒”实际上那是在没有竞争的理想情况下。一旦两个线程同时抢同一把锁情况就完全不一样了。锁的代价主要体现在三块第一线程被挂起后需要内核态调度从阻塞到唤醒一次上下文切换通常在 1-5 微秒级别在高频 push/pop 场景下这个开销会被放大到失控。第二锁的公平性策略可能导致“惊群”效应大量线程同时醒来抢锁又绝大部分空转回去。第三锁还会引入优先级反转低优先级线程持锁时高优先级线程只能干等。我之前那个项目里压测 8 线程并发操作一个由 mutex 保护的栈p99 延迟会周期性地飙到几十甚至上百微秒。用 perf 一看大量时间耗在 futex 相关的系统调用和线程调度上。这个问题在低并发、低竞争场景下完全不明显但只要业务流量大了锁就会变成瓶颈。1.2 CAS 的思路乐观并发CAS 的全称是 Compare-And-Swap翻译过来就是“比较并交换”。它是一条 CPU 指令级别的原子操作做的事情很简单但非常关键给定一个内存地址、一个期望值、一个新值如果内存当前值等于期望值就把新值写进去返回成功否则什么都不做返回失败把这个逻辑放到并发场景里就形成了一种完全不同于锁的思维锁是悲观并发假定冲突总会发生所以先堵住门口再加锁CAS 是乐观并发假定大多数时候没人捣乱先直接操作操作完用一条原子指令验证一下有没有被别的线程改过被改了重来一遍。C11 里把这个能力封装成了 std::atomic核心就是 compare_exchange_weak 和 compare_exchange_strong。关于这两个的差别后面单独说这里先记住一个简单的类比你拿着快递单去取快递CAS 就是柜员先核对单号单号对得上就给你取对不上就告诉你取错了你自己重新排单号再来。有了 CAS 这个小小的原语一个没有锁、靠自旋重试来保证原子性的数据结构就有了地基。2. 无锁栈的骨架Treiber Stack 设计拆解2.1 数据结构与 push 循环无锁栈的经典实现叫 Treiber Stack上世纪 80 年代就有人提出来了思路极其简洁用一个单向链表头部指针 head 作为并发操作的唯一入口。因为栈的 LIFO 特性天然适合链表头操作push 和 pop 都只需要改 head 一个指针。先看数据结构template typename T class LockFreeStack { private: struct Node { T value; Node* next; }; std::atomicNode* head_{nullptr}; };核心就一个 head 原子指针。push 的逻辑可以分为三步创建一个新节点把它维护的 next 指到当前 head用 CAS 尝试把 head 更新为新节点如果 CAS 失败说明 head 被别的线程改了回到第 1 步重新拿新的 head 再试写成代码就是void push(const T value) { Node* new_node new Node{value, nullptr}; new_node-next head_.load(std::memory_order_relaxed); while (!head_.compare_exchange_weak( new_node-next, new_node, std::memory_order_release, std::memory_order_relaxed)) { // CAS 失败时new_node-next 会被自动更新为当前 head // 所以这里什么都不用写直接继续循环 } }这里有一个容易忽略的细节compare_exchange_weak 的第一个参数是引用类型失败时会自动把期望值刷新成当前内存里的实际值。也就是说 new_node-next 会被自动更新为最新的 head循环体里连手动重新 load 都省了。这是无锁代码里一个非常常见的写法能少写一行是一个微小的优化但更重要的是让逻辑更紧凑、不容易漏刷新。2.2 pop 循环与一个容易跳进去的坑pop 的对称逻辑是这样读 head尝试把 head 换成 head-next。如果 CAS 成功说明这个节点被当前线程“摘”下来了然后取 value 返回。bool pop(T out) { Node* old_head head_.load(std::memory_order_relaxed); while (old_head !head_.compare_exchange_weak( old_head, old_head-next, std::memory_order_acquire, std::memory_order_relaxed)) { // 失败了就继续循环old_head 已经自动更新为新 head } if (!old_head) { return false; } out std::move(old_head-value); delete old_head; return true; }这一段看起来人畜无害但里面藏着一个巨大的坑当线程 A 在循环里 CAS 成功、把 old_head 从栈上摘下来之后另一个线程 B 可能也恰好正在处理这个节点不会因为节点一旦被摘下来只有 A 持有它的指针B 不可能通过 head 再拿到它。真正的坑在 ABA 问题。假设线程 A 读取到 head 为节点 X然后停住了线程 B 弹出 X把它删掉又压入一个新节点 X2而 X2 的地址恰好就是 X因为 new 又把同一块内存分配回来了。此时 A 重新开始 CAS它期望的 head 还是 X实际 head 也是 XCAS 成功了但 A 手里的这个“X”已经是 X2不再是它当初读到的那个 X。A 接下来读 X-next 或写 X 时操作的就是一个语义完全不同的节点。这就是经典的 ABA 问题后面专门讲怎么解。先接受一个结论这个简单版本只在“完全不删节点”的前提下才是安全的。很多教学材料不写 delete或者用某种永久节点池都是因为这个原因。2.3 compare_exchange_weak 和 strong 怎么选这两个函数的区别要讲透因为它们的选择会影响性能和正确性。weak 版本在 x86 上几乎没有差别但在 ARM 等弱内存序平台上编译器可能把它编译成 LL/SCLoad-Linked / Store-Conditional指令。LL/SC 在某些情况下会“假失败”——内存值压根没变但 CPU 因为缓存行被其他核触碰等原因返回失败。weak 允许这种假失败发生代价是调用方必须放在循环里重试。strong 版本则保证成功返回一定对应实际值变化它内部会把假失败处理掉所以在某些架构上会有额外的指令开销。无锁数据结构里CAS 基本都套在循环里因此选 weak 更合适失败了大不了再试一次。如果不打算用循环保护比如只做一次性的条件更新那就要用 strong。我自己的习惯是循环重试结构一律 weak单次尝试一律 strong。3. 内存序没那么玄release/acquire 的实际用法3.1 四种内存序的直观理解C11 给 std::atomic 提供了六种 memory_order实际工程里用到的核心是四种relaxed、release、acquire、seq_cst。它们解决的核心问题是一个线程写入的值什么条件下对另一个线程可见。我自己的理解方式是把它类比成发布消息。relaxed 就是“我随手贴个告示不保证别人什么时候看到也不保证看到的是不是最新版”release 是“我把所有之前写好的内容都打包放进这封信里寄出去”acquire 是“我收到信的同时也知道寄信人寄信之前的状态”seq_cst 则是所有人都在同一个广播频道里说话全局只有一个顺序。从 CPU 角度讲relaxed 允许指令被重排release 保证它之前的写操作不会被重排到它后面acquire 保证它之后的读操作不会被重排到它前面。简单说release 只管“前面”acquire 只管“后面”两者配合形成一对同步关系。3.2 push 为什么用 releasepop 为什么用 acquire无锁栈里真正需要同步的是 push 写入的节点数据对 pop 线程可见。push 线程做了两件事给 new_node-value 赋值、给 new_node-next 赋值然后把 head 指针 CAS 成 new_node。这个 CAS 是写操作我们用 release 语义发布。pop 线程通过 CAS 把 head 从 old_head 改成 old_head-next这个操作是读 old_head 的旧值并写 head 的新值。我们用 acquire 语义读取。当 pop 线程的 CAS 观察到 head 是某个 push 线程发布的 new_node 时release-acquire 配对形成push 写入 value 的所有操作对 pop 都是可见的。这就是为什么可以放心地读取节点里的 value。如果这里把顺序放宽成 relaxed理论上 push 的 value 写入可能被重排到 head 发布之后pop 线程可能看到一个半初始化的节点这是未定义行为里最隐蔽的一种。所以 push 的 success_order 用 release、pop 的 success_order 用 acquire是这条链路上的标准做法。3.3 什么时候可以偷懒用 relaxed上面代码里 load head 用的是 relaxedCAS 的 failure_order 也是 relaxed有人可能会质疑这样安全吗安全。因为 load head 只是一个“试探性”读取读到的值可能已经过期但这无伤大雅CAS 成功时天然的 acquire/release 语义会把正确性补回来。失败时 relaxed 也没问题因为失败本身不产生任何同步需求只是让调用方重新循环。failure_order 还有一个限制它不能比 success_order 更强比如 success 用了 releasefailure 就不能用 seq_cst。这在很多帖子里出现实际原因从现在忽略就好记住“失败路径不需要太强”这个原则即可。为了省事也有不少人直接全程用 seq_cst能跑但性能会吃一点亏。我的建议是先把 release/acquire 用对再考虑优化到 relaxed顺序反过来容易踩坑。4. 从教学代码到能用的版本ABA 与内存回收4.1 教学版代码与它的致命伤前面给出的 pop 代码里有一行 delete old_head它让这个版本在教学场景外直接不可用。原因就是 ABA 加悬空指针的组合线程 A 读 head 为节点 X进入 CAS 循环线程 B 弹出 Xdelete 掉紧接着线程 C 又 push 了一个新节点地址恰好复用为 X。此时 A 的 CAS 期望值是 Xhead 实际也是 XCAS 成功A 开始读 X-next。但这个 X 是 C 刚创建的新节点甚至可能已经被另一个线程 D 弹走删除了A 读的就是一块已经释放的内存。轻则读到脏数据重则程序崩溃。解决这个问题的思路有两条线一是让删除不立即发生把节点回收延迟到所有可能引用它的线程都安全之后再删二是让“地址相同”不足以让 CAS 误判给指针附加一个版本戳。工程上真正可靠的是前者后者的版本戳能压缩 ABA 的发生概率但不能根除。4.2 ABA 问题与 tagged pointerTagged pointer 的思路是把“指针”和“代数编号”打包进一个原子变量。每次 CAS 修改 head 结构时不但比较地址还比较代数成功时代数加一。ABA 发生时地址虽然相同但代数一定不同CAS 失败问题就躲过去了。做法大体是把节点地址按 16 字节对齐这样指针的低 4 位永远为 0可以腾出来放代数struct alignas(16) Node { T value; Node* next; }; std::atomicuintptr_t head_{0}; Node* get_ptr(uintptr_t v) { return reinterpret_castNode*(v ~uintptr_t{0xF}); } uintptr_t get_tag(uintptr_t v) { return v uintptr_t{0xF}; } void push(const T value) { Node* node new Node{value, nullptr}; uintptr_t old head_.load(std::memory_order_relaxed); uintptr_t desired; do { node-next get_ptr(old); uintptr_t tag get_tag(old) 1; desired reinterpret_castuintptr_t(node) | tag; } while (!head_.compare_exchange_weak(old, desired, std::memory_order_release, std::memory_order_relaxed)); }这个版本的代价是 4 位 tag 溢出很快高并发下可能出现 tag 绕回ABA 依然有机可乘。另一种做法是使用 16 字节的原子结构64 位指针加 64 位计数器溢出概率低到可以忽略但 std::atomic 是否真正 lock-free 依赖编译器和平台需要现场验证。总之 tag 方案适合降低概率不适合追求绝对正确。4.3 工程上的回收方案hazard pointer 思路真正能在生产环境放心用的方案是把“节点释放”延迟到没有线程再引用它的时候。业内比较成熟的做法有两种hazard pointer 和基于 epoch 的延迟回收。这里把 hazard pointer 的核心思路讲清楚。每个线程预分配一个全局可见的槽位叫 hazard pointer在线程准备访问某个节点之前先把节点地址发布到自己的槽位里其他线程回收节点之前扫描所有槽位只要发现该地址还在某个槽位中就推迟回收这个机制保证了只要一个线程还握着一个节点的指针这个节点就绝不会被物理删除。这是从根上解决 use-after-free 的方案代价是每次 pop 都要多一次“发布预告”操作并且释放节点前要扫描所有线程的槽位。扫描开销在线程数少时可以接受但线程数上百时就会变成负担。我实际在项目里用的是一种简化变体pop 出来的节点不立刻释放而是先放进一个全局退役列表等到列表长度超过一定阈值后触发一次性回收。回收时检查所有 hazard 槽位可以安全释放的直接删还被引用的继续留在退役列表里等下一轮再处理。这样既控制了内存增长又把释放频率降了下来。实现代码比较长核心是先用架构图式的思维理解“延迟回收”这个动作细节在具体业务里可以灵活裁剪。5. 实测数据无锁栈真的更快吗5.1 测试方法与环境理论讲得再好也要落地验证。我用一个模拟任务池做了对比测试机上 8 核分别跑两个版本std::mutex 保护 std::stack以及前面的 Tagged 无锁栈。每个版本起 8 个线程每个线程执行 50 万次 push 和 50 万次 pop操作内容只是一个整数出入栈节点内存用预分配池管理避免内存分配本身干扰结果。测试时把 mutex 版本和无锁版本放在同样的编译选项下开 -O2压测前先跑一轮热身让缓存和调度稳定下来。最终数据只记录稳定阶段的吞吐量不记录首次运行的波动。5.2 数据对比与结论下面是我这边跑出来的相对数据。注意这体现的是相对趋势绝对值跟 CPU、编译器、系统版本都有关系。版本总操作数万次吞吐量万次/秒p99 延迟微秒std::mutex std::stack800约 210约 4.8Tagged 无锁栈教学版800约 480约 1.9无锁版本在吞吐量上大约有 2 倍左右的优势延迟也更集中。实际操作中 p99 从 4.8 微秒降到 1.9 微秒对依赖低延迟的业务来说意义很大。但我要泼一盆冷水这个优势是有前提的。当 push/pop 比例不均衡、节点内存需要频繁分配回收、或者线程数超过 16 之后纯无锁栈的优势会缩小。尤其是 pop 里如果涉及 value 的深拷贝拷贝成本会直接淹没无锁带来的收益。无锁栈优化的是“并发访问”这一段它救不了数据复制本身的开销。5.3 is_lock_free 检查与 false sharing 注意点每一次写基于 std::atomic 的无锁结构都应该先确认目标平台的原子操作真的是无锁的。标准库提供了一个很有用的接口static_assert(std::atomicNode*::is_always_lock_free, this platforms pointer atomic is not lock-free); if (!std::atomicuintptr_t::is_lock_free()) { // 兜底逻辑 }is_always_lock_free 是编译期常量is_lock_free 是运行期判断。如果是 false说明标准库内部用了锁你的“无锁”栈实际上还是锁栈性能预期全盘作废。还有一个很容易忽视的坑是 false sharing。head_ 和别的热点变量如果落在同一个缓存行里一个线程改 head 会导致另一个线程的缓存行失效性能断崖式下降。我调试过的一个案例把 head_ 旁边加了一个统计用的计数器压测吞吐量直接掉了三成。解决办法是让热点变量各自独占缓存行或者至少把它们分开存放struct alignas(64) LockFreeStackState { std::atomicuintptr_t head_{0}; };64 字节对齐是常见做法因为主流 CPU 的缓存行是 64 字节。6. 常见问题与排查经验速查表现象常见原因处理思路线程数增加后性能反而变差false sharing 或 CAS 竞争过热检查热点变量对齐引入退避策略pop 返回了错误值或崩溃节点提前释放导致悬空指针禁止裸 delete改用延迟回收或 hazard pointerCAS 一直失败CPU 占用居高不下竞争太激烈且没有退避机制在 CAS 循环里加 pause 指令或短暂退避push 之后数据偶尔丢失CAS 的 expected 参数没有正确刷新确保 CAS 失败后使用自动刷新的 expected 值程序内存持续增长退役列表或回收列表没有触发回收设置回收阈值定期触发扫描原子结构体不生效std::atomic 内部退化为互斥锁用 is_always_lock_free 验证并换用指针或 uintptr_t除了表里的问题还有几个实战中特别容易踩的细节。第一个是不要在 CAS 循环里傻等。高竞争下纯自旋会烧满 CPU正确的做法是加入退避。最简单的是执行几条 CPU pause 指令while (!head_.compare_exchange_weak(expected, desired, std::memory_order_release, std::memory_order_relaxed)) { for (int i 0; i 4; i) { __builtin_ia32_pause(); } }pause 指令在 Intel/AMD 上都有效它是忙等场景下的推荐指令比空循环效果好很多。也可以在退避次数变多时升级为 yield但 yield 会触发调度代价更高一般留给极端情况。第二个细节是 pop 里先摘节点再拷贝值顺序绝对不能反。先读 value 再 CAS 的话节点可能在你读 value 的瞬间被其他线程摘走删除还没开始 CAS 就已经悬空了。必须先 CAS 拿节点再动节点里的数据。第三个细节是当 T 是复杂对象时把值移出节点的过程要考虑异常安全。std::move 赋值本身可能抛出异常这时节点已经被摘掉栈状态是安全的但如果节点没有被回收就会造成泄漏。稳妥的做法是 pop 接受一个引用参数并且确保异常抛出时节点进入退役列表不至于直接丢。第四个细节是栈的 size 查询能力。无锁栈想在 push/pop 之外再维护一个原子计数器会让每一次操作多一次原子更新而且计数器的竞争会拖慢整体。如果业务确实需要 size可以考虑用近似计数或者直接把 size 交给上层单独维护。写无锁代码最考验人的地方不是代码本身而是思维方式的转变。锁的思维方式是“我先把东西锁住别人别碰”CAS 的思维方式是“我直接改改错了再来”。这不仅是数据结构的区别更是对并发模型理解的提升。我经历过几次 ABA 导致的诡异崩溃花了两天才定位到是节点提前释放也经历过 false sharing 让性能白掉了三成的尴尬。但把这些坑一个个填平之后再看其他并发场景比如无锁队列、引用计数、内存分配器的空闲链表底层的判断逻辑都是相通的。把这个栈吃透后面做更复杂的无锁结构会顺利很多。