手写基于纪元EBR的无锁内存回收器在手写无锁并发数据结构如无锁并发哈希表、无锁跳表、无锁二叉树时最大的阿喀琉斯之踵不是如何用 CAS 插入或删除节点而是何时才能安全地free物理释放一个被逻辑删除的节点如果线程 A 将一个节点从链表中解引用剔除后立即调用drop释放其内存此时可能正有一个并发的读取线程 B 已经拿到了该节点的裸指针、正准备读取其中的数据线程 A 的贸然释放会瞬间导致线程 B 触发释放后使用Use-After-Free, UAF并在内核中引发SIGSEGV段错误为了解决无锁安全内存回收学术界与工业界提出了多种方案Hazard Pointers 风险指针、RCU 读取-复制-更新、EBR 纪元回收。其中基于纪元的内存回收Epoch-Based Reclamation, EBR /crossbeam-epoch以其接近于零的读取开销成为高性能无锁数据结构的事实标准。深入推导 EBR 的三代纪元状态机并手写一个最小可用的安全回收器是掌握无锁并发编程的终极高地。-------------------------------------------------------------------------- | EBR 基于纪元的无锁内存回收状态机 | -------------------------------------------------------------------------- | 全局纪元计数器 (Global Epoch: 0, 1, 2 循环轮转) | | | | 1. 读取线程进入临界区: pin() | | - 记录本地线程持有的纪元: local_epoch Global_Epoch | | | | 2. 写入线程逻辑删除节点 Node X: | | - 不直接释放而是将 Node X 放入当前纪元的垃圾箱 (Garbage Bag[Global_Epoch])| | | | 3. 推进全局纪元: advance_epoch() | | - 检查所有活跃线程: 若没有任何线程还停留在 Epoch - 2 纪元 | | - 安全物理回收 Garbage Bag[Epoch - 2] 中的所有历史垃圾节点 | --------------------------------------------------------------------------1. EBR 的核心数学定理为什么只需要 3 个纪元Epoch 0, 1, 2EBR 将全局时间离散化为循环递增的三代纪元$e \in {0, 1, 2}$。核心不变量证明当一个节点在全局纪元 $E$ 被逻辑删除时全网只有当前处于纪元 $E$ 或纪元 $E-1$ 的读取线程可能持有该节点的指针随后全局纪元推进到 $E1$。此时所有新进入临界区的线程只能看到纪元 $E1$绝不可能再获取到已被删除的节点指针当全局纪元再次推进到 $E2$ 时只要所有活跃线程的本地纪元都 $\ge E1$说明在纪元 $E$ 期间进入的所有老读取线程均已退出临界区此时在全宇宙中绝对不存在任何一个线程还持有该节点的引用结论挂载在纪元 $E$ 垃圾箱中的所有对象可以在纪元推进到 $E2$ 时被 100% 绝对安全地物理销毁free2. 基于 Rust 的最小可用 EBR 内存回收器实现use std::sync::atomic::{AtomicUsize, Ordering}; use std::sync::Mutex; const EPOCH_MASK: usize 3; pub struct EpochManager { global_epoch: AtomicUsize, // 三个代际的垃圾回收袋 retired_bags: Mutex[Vec*mut u8; 3], } unsafe impl Sync for EpochManager {} impl EpochManager { pub fn new() - Self { Self { global_epoch: AtomicUsize::new(0), retired_bags: Mutex::new([Vec::new(), Vec::new(), Vec::new()]), } } /// 获取当前全局纪元读取操作极其轻量仅一条 Relaxed/Acquire 指令 #[inline(always)] pub fn current_epoch(self) - usize { self.global_epoch.load(Ordering::Acquire) } /// 延迟退役一个节点放入当前纪元的垃圾暂存袋 pub fn retire_node(self, ptr: *mut u8) { let epoch self.current_epoch() % EPOCH_MASK; let mut bags self.retired_bags.lock().unwrap(); bags[epoch].push(ptr); } /// 尝试推进全局纪元并物理回收隔代垃圾 pub fn try_advance_and_collect(self) { let current self.global_epoch.load(Ordering::Relaxed); let next_epoch current 1; // 推进全局纪元 self.global_epoch.store(next_epoch, Ordering::Release); // 计算可以安全物理释放的隔代纪元下标: (current - 1) % 3 let safe_epoch_idx (current 2) % EPOCH_MASK; let mut bags self.retired_bags.lock().unwrap(); let garbage_to_free std::mem::take(mut bags[safe_epoch_idx]); // 物理释放所有无害垃圾节点 for ptr in garbage_to_free { unsafe { // 调用具体的物理 dealloc 释放内存 let layout std::alloc::Layout::new::usize(); std::alloc::dealloc(ptr, layout); } } } }3. EBR vs 传统方案对比内存回收机制读取操作性能损耗实现复杂度内存释放及时性适用场景互斥锁 / RwLock极高 (锁争用)极低即时低并发普通场景引用计数 Arc高 (高频原子操作争用)低即时简单对象共享Hazard Pointers中等 (需逐指针写屏障)极高极其及时极高可靠实时系统EBR (纪元回收)接近 0 (单条原子读)中等平滑分批回收极致无锁并发首选通过将物理释放与逻辑删除在时间维度上解耦为三代纪元流转EBR 彻底攻克了无锁并发编程的内存安全难题赋予了底层系统纯粹的无锁极速。
