无锁编程的内存困境：为什么最难的竟不是算法本身

2015年，Rust核心团队成员Aaron Turon发布了一个名为Crossbeam的库。他在博客中写道：“如果我问Rust社区，构建锁-free数据结构最大的障碍是什么，答案几乎总是一样的——内存管理。”

这不是一个简单的工程问题。在无锁编程的世界里，一个被删除的节点可能正被另一个线程读取；一个CAS操作成功的瞬间，内存可能已经被释放并重新分配。这些问题在单线程代码中完全不存在，但在多线程环境中，它们会导致数据竞争、内存破坏，甚至崩溃——而且难以复现和调试。

更令人意外的是，学术界在发表论文时，几乎从不详细讨论内存回收。他们会说"这是一个实现细节"，然后假设读者使用的是带有垃圾回收的语言。但如果你想在C++或Rust中实现一个生产级的无锁数据结构，内存回收恰恰是最困难的部分。

无锁编程的隐形杀手：ABA问题

理解无锁编程的内存困境，必须从一个经典问题开始：ABA问题。

假设有一个简单的无锁栈，使用CAS（Compare-and-Swap）操作来更新栈顶指针。线程1想要执行pop操作，它读取栈顶指针为A，准备将栈顶更新为A的下一个节点B。就在CAS执行之前，线程1被中断。

此时线程2开始工作。它完整执行了两次pop，将A和B都弹出并释放了它们的内存。然后线程2分配了一个新节点，巧合的是，内存分配器将新节点分配在原来A的位置（这在实践中非常常见，称为MRU分配策略）。线程2将新节点压入栈中。

当线程1恢复执行时，它的CAS操作发现栈顶指针确实等于A——CAS成功！线程1将栈顶更新为它之前读取的B->next。但问题是：B已经被释放了。线程1实际上将栈顶指向了一个无效的地址。

这就是ABA问题的本质：CAS只比较值，不关心这个值在两次读取之间是否发生过变化。指针的值相同，但语义完全不同。

CAS的根本局限

CAS指令的语义是：当且仅当内存位置的值等于预期值时，将其更新为新值。 这个语义在单线程环境下完美工作，但在多线程环境中存在盲区。

// 经典的ABA问题场景
bool pop() {
    Node* old_head = head.load();  // 第一次读取，值为A
    // ... 此时被中断 ...
    // 其他线程可能：删除A，删除B，在A的原地址分配新节点
    Node* new_head = old_head->next;  // 如果A已被释放，这里就是Use-After-Free
    return head.compare_exchange_weak(old_head, new_head);
}

问题在于，CAS无法区分"值从未改变"和"值改变后又改回"这两种情况。在第二种情况下，内存可能已经被释放和重新分配，指向的数据结构可能已经完全不同。

为什么垃圾回收语言更"幸运"

如果你使用Java或Go这类带有垃圾回收的语言，ABA问题会自动消失——因为被引用的对象不会被回收。当一个线程持有对节点A的引用时，即使其他线程从数据结构中移除了A，垃圾回收器也不会回收它，直到所有引用都消失。

但这带来一个有趣的悖论：垃圾回收器本身通常不是无锁的。如果GC触发了一次Stop-The-World的暂停，整个程序的进度保证就会失效。正如并发专家Pedro Ramalhete指出的：“即使你有GC，没有已知的GC是无锁的（更不用说wait-free了）。”

对于C++和Rust这样的系统编程语言，我们必须手动解决这个问题。这就引出了无锁编程中最核心的技术挑战：安全内存回收（Safe Memory Reclamation, SMR）。

四个维度，三大家族

Pedro Ramalhete在博客中将内存回收问题分解为四个关键维度：

进度保证：如果你费尽心思设计了一个lock-free的数据结构，却在上面叠加了一个阻塞的内存回收机制，那么整个系统仍然是阻塞的。内存回收必须至少具有与数据结构相同的进度保证。

吞吐量：内存回收机制不能成为性能瓶颈。如果你的无锁数据结构每秒处理百万次操作，但内存回收每秒只能处理十万次，那么整个系统的吞吐量就被拖垮了。

易用性：这可能是最被低估的维度。Hazard Pointers虽然强大，但正确使用它需要对数据结构有专家级的理解。很多论文的作者甚至不会在论文中展示如何集成内存回收——“太复杂了，读者自己想吧”。

容错性：无锁数据结构的一大优势是线程失败不会阻塞其他线程。但如果内存回收机制依赖于所有线程都正常工作（比如定期报告状态），一个线程崩溃可能导致整个系统的内存回收停滞。

三大技术家族

所有手动内存回收技术都属于以下三个家族之一：

引用计数族：最直观的方法，每个对象维护一个引用计数器。但问题是，在无锁环境下实现原子引用计数非常困难——你需要在遍历链表时对每个节点原子地增减计数器，这不仅慢，而且无法处理循环引用。更致命的是，引用计数本身可能引发ABA问题：两个线程同时读取计数器值A，都认为可以安全释放对象。

静止状态族（Quiescent-State-Based）：包括Epoch-Based Reclamation（EBR）和Userspace RCU。这是读性能最高的方法，因为读者几乎不需要任何同步操作。但代价是内存回收可能会被阻塞——如果一个线程长时间不报告静止状态，所有待回收的内存都无法释放。这类方法本质上是阻塞的。

指针保护族（Pointer-Based）：包括Hazard Pointers、Hazard Eras等。这是唯一能提供真正无锁内存回收的方法。每个线程声明它正在访问的指针，其他线程在回收内存前检查这些声明。缺点是需要额外的内存访问来保护指针，而且使用起来比较复杂。

Hazard Pointers：精确但昂贵

2004年，IBM研究员Maged Michael在IEEE Transactions on Parallel and Distributed Systems上发表了"Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"。这篇论文提出了第一个真正实用的无锁内存回收方案。

核心思想

Hazard Pointers的核心思想非常简洁：每个线程维护一组"危险指针"，在访问共享数据结构中的节点之前，先将指向该节点的指针写入危险指针槽。当任何线程想要释放一个节点时，它必须先检查所有线程的危险指针——如果任何一个危险指针指向该节点，就不能释放。

// 危险指针的伪代码
struct HazardPointer {
    atomic<Node*> pointer;
};

HazardPointer hp[MAX_THREADS][K];  // 每个线程K个危险指针槽

Node* pop() {
    Node* old_head;
    do {
        old_head = head.load();
        hp[my_thread_id][0].store(old_head);  // 保护old_head
        // 关键：必须重新读取，因为可能在store之前old_head就被释放了
        if (head.load() != old_head) continue;
        Node* next = old_head->next;
    } while (!head.compare_exchange_weak(old_head, next));
    
    hp[my_thread_id][0].store(nullptr);  // 解除保护
    // 将old_head加入待回收列表
    retire_node(old_head);
    return old_head;
}

void retire_node(Node* node) {
    retired_list.push(node);
    if (retired_list.size() > threshold) {
        scan_and_reclaim();  // 检查所有危险指针，释放安全节点
    }
}

微妙的正确性

Hazard Pointers的正确性依赖于一个关键细节：在设置危险指针后，必须重新检查数据结构的指针是否仍然指向同一个节点。这看似多余，但实际上至关重要。

考虑以下场景：线程1读取了head为A，正准备设置危险指针。此时线程2将A从栈中移除并释放。线程3分配新内存，巧合地分配在A的原地址。线程1设置危险指针，指向的恰好是线程3的新节点。线程1继续执行，访问A->next——但它访问的是线程3的新节点，而不是原来的节点A。

这就是为什么必须在设置危险指针后重新验证数据结构的指针。只有当两个读取返回相同的值，且中间设置了危险指针，才能保证节点不会被释放。

性能代价

Hazard Pointers的主要性能代价在于：每次访问节点都需要写入共享内存（危险指针槽）。虽然这个写入是线程本地的，但它仍然会导致缓存行的独占访问。在高竞争场景下，多个线程频繁更新危险指针槽可能导致缓存行在核心之间来回"乒乓"。

Trevor Brown在DEBRA论文中报告，Hazard Pointers的开销可以使某些数据结构的吞吐量下降50%以上。这就是为什么尽管Hazard Pointers提供了最强的进度保证，很多高性能系统仍然选择使用EBR。

Epoch-Based Reclamation：快速但阻塞

Epoch-Based Reclamation（EBR）是另一种流行的内存回收技术，最早由Keir Fraser在其博士论文中描述。Rust的Crossbeam库就使用了这种技术。

核心机制

EBR使用一个全局纪元计数器（通常只有3个值：0、1、2循环），每个线程维护一个本地纪元。当线程进入数据结构的操作时，它会：

设置自己的本地纪元为当前全局纪元
执行操作
将移除的节点加入当前纪元的垃圾列表
离开时清除活跃标记

当所有活跃线程都在同一个纪元时，可以安全地递增全局纪元，并释放两个纪元前的垃圾。

sequenceDiagram
    participant G as Global Epoch
    participant T1 as Thread 1
    participant T2 as Thread 2
    participant GL as Garbage Lists
    
    Note over G: Global Epoch = 0
    T1->>G: Enter epoch 0
    T2->>G: Enter epoch 0
    T1->>GL: Retire node (epoch 0)
    T2->>G: Exit
    T1->>G: Exit
    Note over G: All threads inactive
    G->>G: Advance to epoch 1
    Note over GL: Cannot free epoch 0 yet (need 2 epochs gap)

为什么需要三个纪元？

EBR使用三个纪元而不是两个，原因非常巧妙：当全局纪元从0变为1时，可能有线程仍然在纪元0执行（它读取了全局纪元但还没来得及更新本地纪元）。此时这些线程是"旧的活跃线程"。

我们需要等待所有"旧的活跃线程"完成才能回收内存。但与此同时，可能有新的线程进入，它们会进入纪元1。如果我们只有两个纪元，就无法区分"仍在纪元0的旧线程"和"已经进入新纪元但纪元号相同的线程"。

使用三个纪元，当我们递增到纪元1时，我们知道：

纪元1的线程是新进入的，安全
纪元0的线程是"旧的活跃线程"，需要等待
纪元2的垃圾可以安全释放，因为不可能还有线程在那里

阻塞的本质

EBR的一个根本问题是：它是阻塞的。如果一个线程进入临界区后挂起（比如由于调度器抢占、页面错误或信号处理），所有后续的内存回收都会停滞。垃圾列表会无限增长，直到耗尽内存。

这不仅是理论上的问题。在实际系统中，线程可能因为各种原因长时间停留在临界区：阻塞的系统调用、CPU调度延迟、甚至调试器的断点。当这种情况发生时，整个系统的内存使用会急剧上升。

Crossbeam的实现通过在每个线程本地维护垃圾列表来缓解这个问题：即使全局纪元无法前进，线程也可以继续回收自己本地的"安全"垃圾。但这只是缓解，不是根本解决。

QSBR：最简洁的方案

Quiescent State-Based Reclamation（QSBR）是EBR的一种变体，在Linux内核的RCU子系统中得到广泛应用。

QSBR的核心概念是"静止状态"（Quiescent State）——一个线程不在访问任何共享数据结构的时刻。线程在进入静止状态时主动报告，当所有线程都报告了静止状态，就形成了一个"静默期"（Grace Period），在此期间之前被删除的对象可以安全回收。

// QSBR的基本模式
void thread_loop() {
    while (running) {
        // 临界区：访问共享数据结构
        access_shared_data();
        
        // 离开临界区，报告静止状态
        rcu_quiescent_state();
        
        // 做其他工作...
    }
}

void delete_node(Node* node) {
    // 从数据结构中移除节点
    unlink(node);
    // 稍后回收（等所有线程都经过静止状态）
    call_rcu(free_node, node);
}

QSBR的优雅之处在于：读者完全不需要任何同步操作。不需要设置危险指针，不需要参与纪元，只需要定期报告静止状态。这使它成为读性能最高的内存回收方案。

但代价是：线程必须主动配合。如果一个线程忘记报告静止状态，整个系统的内存回收就会停滞。这使得QSBR不适合通用库，更适合在应用层完全控制线程行为的场景。

NBR：折中之道

2020年，Waterloo大学的研究团队提出了NBR（Neutralization-Based Reclamation），试图在EBR的效率和Hazard Pointers的无阻塞之间找到平衡。

NBR的核心创新是使用POSIX信号来"中和"长时间运行的线程。当一个线程想要回收内存但发现有线程长时间处于活跃状态时，它可以向这些线程发送信号。信号处理函数会安全地将线程从活跃状态中移除，允许内存回收继续进行。

这种方法保持了EBR的大部分性能优势（读者只需要检查一个全局变量），同时在理论上保证了有界的内存使用。但代价是引入了信号处理的复杂性，而且在某些平台上信号可能带来性能开销。

C++26：标准化的尝试

经过多年的讨论，Hazard Pointers终于被纳入C++26标准（std::hazard_pointer）。这是继C++11引入原子操作之后，并发编程基础设施的又一次重要升级。

C++26的Hazard Pointers API设计借鉴了Facebook Folly库的实现经验。主要组件包括：

std::hazard_pointer_obj_base<T>：可以被Hazard Pointer保护的对象基类
std::hazard_pointer：危险指针本身，用于保护对象
std::make_hazard_pointer()：创建危险指针

// C++26 Hazard Pointers示例
struct Node : std::hazard_pointer_obj_base<Node> {
    int data;
    Node* next;
};

std::atomic<Node*> head;

Node* find(int value) {
    std::hazard_pointer hp = std::make_hazard_pointer();
    Node* current = head.load();
    while (current) {
        hp.protect(current);  // 保护当前节点
        if (current->data == value) {
            return current;    // 调用者可以安全访问current
        }
        current = current->next;
    }
    return nullptr;
}

void remove(Node* node) {
    // 从数据结构中移除...
    node->retire();  // 标记为待回收
}

然而，标准化的只是接口，不是实现。不同的标准库实现可能选择不同的底层策略（Hazard Pointers、Hazard Eras或混合方案），性能特征可能差异很大。

权衡的艺术

没有完美的内存回收方案。每种技术都有其适用场景：

方案	读开销	写开销	内存有界	进度保证	易用性
Hazard Pointers	高	低	是	无锁	中等
EBR	极低	极低	否	阻塞	高
QSBR	零	极低	否	阻塞	高
NBR	低	中	是	无锁	中等
引用计数	极高	中	是	阻塞	极高

在选择方案时，需要回答几个关键问题：

你的数据结构是什么进度级别？ 如果只是lock-free，那么阻塞的EBR可能足够。如果是wait-free，则需要Hazard Pointers或其变体。

你的负载特征是什么？ 如果读远多于写，EBR或QSBR是更好的选择。如果写操作频繁，Hazard Pointers的写低开销可能更重要。

你的系统有多可靠？ 如果线程可能崩溃或长时间挂起，EBR和QSBR可能导致内存无限增长。需要选择有界的方案。

你的开发团队有多专业？ 正确使用Hazard Pointers需要对数据结构有深刻理解。如果你的团队不熟悉这些概念，EBR的错误率可能更低。

来自生产的教训

Aaron Turon在Crossbeam的基准测试中发现了一个有趣的现象：在某些场景下，Rust的EBR实现甚至击败了Java的ConcurrentLinkedQueue。原因不是Rust的无锁算法更先进，而是Java的垃圾回收器在有大量存活数据时性能下降——GC的代价与存活数据量成正比，而EBR的代价只与线程数成正比。

这揭示了一个深刻的洞察：内存回收不仅是正确性问题，也是性能问题。选择正确的方案，可能比优化数据结构本身带来更大的收益。

Facebook在Folly库中实现Hazard Pointers时，选择了非常激进的设计：每个线程可以拥有多个危险指针槽，以支持复杂的遍历模式。但这也带来了内存开销。在生产环境中，他们发现超过2个危险指针的场景非常罕见，大多数情况下1-2个就足够了。

另一个教训来自Linux内核社区。RCU在内核中使用了几十年，但仍然有人误用。最常见的错误是：在RCU临界区内调用可能睡眠的函数，或者忘记调用rcu_read_unlock()。这提醒我们，即使有简洁的API，正确使用仍然需要专业知识。

结语

无锁编程的内存回收问题，本质上是一个协调问题：如何让多个线程就"何时可以安全回收内存"达成共识，同时最小化同步开销。

这个问题的困难程度，解释了为什么大多数无锁数据结构的论文选择忽略它。但如果你想在生产环境中使用这些数据结构，这就是一个无法回避的问题。

理解这些技术的权衡，是成为高级并发程序员的必经之路。选择错误的方案，可能导致难以发现的bug或灾难性的性能问题。选择正确的方案，则可以在保证正确性的同时，充分发挥无锁数据结构的性能优势。

最后，记住Pedro Ramalhete的忠告：“内存回收机制需要具有与数据结构相同或更好的进度保证，而且速度不能拖后腿。否则，你花费在设计无锁数据结构上的所有努力，都会付诸东流。”

无锁编程的隐形杀手：ABA问题#

CAS的根本局限#

为什么垃圾回收语言更"幸运"#

四个维度，三大家族#

三大技术家族#

Hazard Pointers：精确但昂贵#

核心思想#

微妙的正确性#

性能代价#

Epoch-Based Reclamation：快速但阻塞#

核心机制#

为什么需要三个纪元？#

阻塞的本质#

QSBR：最简洁的方案#

NBR：折中之道#

C++26：标准化的尝试#

权衡的艺术#

来自生产的教训#

结语#

更多精彩内容

ConcurrentHashMap的十五年演进：从分段锁到CAS如何重塑Java并发基石

一个int变量如何支撑起Java并发包的半壁江山：AQS的设计哲学与实现原理

分布式锁为何成了生产事故的隐形杀手——从Martin Kleppmann与antirez的论战说起

协程调度：从用户态线程到Go GMP模型的二十年演进

MESI协议：多核处理器如何在"看不见"彼此的情况下保持数据一致