在构建高吞吐的多版本并发控制MVCC存储引擎、内存时序数据库或高性能分布式索引时红黑树和 B 树往往因其自平衡操作如树旋转、节点分裂与合并带来的大范围锁竞争成为多核并行扩展的严重瓶颈。相比之下跳表SkipList凭借概率平衡的层次化链表结构不仅实现逻辑更为直观更具备天然的细粒度并发与无锁化潜力。然而在无锁环境下构建支持并发读写与范围遍历的有序跳表面临着极其凶险的工程挑战。最核心的死结在于如何原子地删除一个包含多层前驱与后继指针的跳表节点同时杜绝并发插入或后继节点遍历导致的悬垂指针Use-After-Free与幽灵节点读写本文将从硬件原子指令与内存模型出发系统剖析经典 Harris-Michael 无锁链表与无锁跳表的核心架构。我们将通过 Rust 手写一套基于标记指针Marked Pointers与分步删除协议的并发有序跳表核心算子彻底打通无锁数据结构的底层逻辑。一、无锁链表删除的核心痛点ABA 与并发竞争裂痕在经典的无锁单链表中插入一个新节点只需执行一次原子比较并交换CAS// 伪代码在 A 和 B 之间插入新节点 X X.next.store(B, Ordering::Release); CAS(A.next, B, X);如果 CAS 失败说明有其他线程在 A 之后插入了其他节点当前线程只需刷新局部指针重试即可。然而删除操作绝非单次 CAS 所能解决。设想以下交错时序线程 1 试图删除节点 B链表当前为A - B - C。线程 1 准备执行CAS(A.next, B, C)。就在 CAS 执行前的一瞬间线程 2 抢先在 B 和 C 之间插入了新节点 X链表变为A - B - X - C。随后线程 1 的 CAS 命中将A.next修改为 C。灾难发生了新插入的有效节点 X 被线程 1 连带物理切除彻底从链表中神秘失踪为了解决该并发冲突Timothy Harris 提出了无锁单链表删除标准协议将删除操作拆解为两阶段——逻辑删除Logical Deletion与物理摘除Physical Removal。逻辑删除利用底层指针的低位对齐冗余位对齐字节通常为 8 字节低 3 位恒为 0通过 CAS 将目标节点 B 的next指针打上标记Marking。一旦指针被打上删除标记任何试图在 B 之后挂载新节点的插入线程都会在 CAS 时因地址不匹配而立即失败。物理摘除由删除线程或后续路过该节点的任意读写遍历线程协助执行 CAS 将前驱节点 A 的后继直接跨过 B 指向 C完成垃圾节点的物理剥离。在跳表中一个节点横跨多个高度层级Tower逻辑删除必须在底层Layer 0完成而物理摘除则需要自顶向下或自底向上逐层解耦。二、标记指针Marked Pointer与原子位运算设计在 64 位现代硬件架构上堆分配对象的地址通常按 8 字节甚至 16 字节对齐。这意味着有效指针地址的最低 3 位永远是 0。我们可以无损借用最低有效位Bit 0作为“逻辑已删除”标志位。在 Rust 中我们必须在保持最高性能的同时严密封装 unsafe 裸指针位操作确保对无锁内存的操作绝不违反 Rust 的指针语义。use std::sync::atomic::{AtomicPtr, Ordering}; use std::ptr; /// 封装带标记的原子裸指针 pub struct MarkedAtomicPtrT { inner: AtomicPtrT, } const MARK_MASK: usize 1; const PTR_MASK: usize !MARK_MASK; implT MarkedAtomicPtrT { pub fn new(ptr: *mut T) - Self { Self { inner: AtomicPtr::new(ptr), } } /// 解包当前指针值与标记状态 #[inline(always)] pub fn load_marked(self, order: Ordering) - (*mut T, bool) { let raw self.inner.load(order) as usize; let is_marked (raw MARK_MASK) ! 0; let clean_ptr (raw PTR_MASK) as *mut T; (clean_ptr, is_marked) } /// 仅获取有效地址指针 #[inline(always)] pub fn load_clean(self, order: Ordering) - *mut T { let raw self.inner.load(order) as usize; (raw PTR_MASK) as *mut T } /// 尝试原子地为当前指针打上删除标记 #[inline(always)] pub fn mark_node(self, expected_clean: *mut T) - Result*mut T, *mut T { let current_clean (expected_clean as usize PTR_MASK) as *mut T; let marked ((expected_clean as usize PTR_MASK) | MARK_MASK) as *mut T; self.inner.compare_exchange_weak( current_clean, marked, Ordering::AcqRel, Ordering::Acquire, ) } /// 原子比较并交换干净指针要求前置状态未被标记 #[inline(always)] pub fn compare_exchange_clean( self, current: *mut T, new: *mut T, success: Ordering, failure: Ordering, ) - Result*mut T, *mut T { let current_clean (current as usize PTR_MASK) as *mut T; let new_clean (new as usize PTR_MASK) as *mut T; self.inner.compare_exchange_weak( current_clean, new_clean, success, failure, ) } }三、跳表节点与 Tower 塔式层级布局跳表节点不仅包含 Key 和 Value还包含一个变长或固定最大高度的“塔”Tower其中每一层对应一个MarkedAtomicPtr分别指向该层右侧的后继节点。pub const MAX_HEIGHT: usize 16; pub struct SkipNodeK, V { pub key: K, pub val: V, pub height: usize, /// 每一层的后继指针数组 pub next: [MarkedAtomicPtrSkipNodeK, V; MAX_HEIGHT], } implK, V SkipNodeK, V { pub fn new(key: K, val: V, height: usize) - *mut Self { assert!(height 0 height MAX_HEIGHT); let mut node Box::new(Self { key, val, height, next: unsafe { // 安全初始化固定长度数组中的原子指针 let mut arr: [MarkedAtomicPtrSkipNodeK, V; MAX_HEIGHT] std::mem::MaybeUninit::uninit().assume_init(); for slot in arr.iter_mut() { ptr::write(slot, MarkedAtomicPtr::new(ptr::null_mut())); } arr }, }); Box::into_raw(node) } }四、核心搜索与协助物理清理机制Find Help Clean无锁跳表最精妙的算子是find_position。该算子不仅用于查找键更在遍历过程中承担了**协助清理Help Clean**的职责当遍历层级链表遇到已经被打上标记的节点时当前线程绝不绕道逃避而是主动协助执行前驱节点的 CAS物理摘除被标记的僵尸节点恢复链表健康的拓扑结构。pub struct SearchResultK, V { /// 每一层的前驱有效节点指针 pub preds: [*mut SkipNodeK, V; MAX_HEIGHT], /// 每一层的后继有效节点指针 pub succs: [*mut SkipNodeK, V; MAX_HEIGHT], } implK: Ord, V SearchResultK, V { pub fn empty() - Self { Self { preds: [ptr::null_mut(); MAX_HEIGHT], succs: [ptr::null_mut(); MAX_HEIGHT], } } } pub struct LockFreeSkipListK, V { head: *mut SkipNodeK, V, } implK: Ord Default, V: Default LockFreeSkipListK, V { pub fn new() - Self { let head SkipNode::new(K::default(), V::default(), MAX_HEIGHT); Self { head } } /// 无锁搜索并就地清理幽灵节点 pub fn find(self, key: K, result: mut SearchResultK, V) - bool { restart: loop { let mut pred self.head; let mut found false; // 自顶向下逐层检索 for level in (0..MAX_HEIGHT).rev() { let mut curr unsafe { (*pred).next[level].load_clean(Ordering::Acquire) }; loop { if curr.is_null() { result.preds[level] pred; result.succs[level] ptr::null_mut(); break; } // 获取当前节点的后继指针及标记状态 let (next_ptr, is_marked) unsafe { (*curr).next[level].load_marked(Ordering::Acquire) }; // 如果当前节点已被标记删除当前线程主动协助执行物理摘除 if is_marked { let cas_result unsafe { (*pred).next[level].compare_exchange_clean( curr, next_ptr, Ordering::AcqRel, Ordering::Acquire, ) }; if cas_result.is_err() { // 前驱发生剧烈竞争必须从头重启搜索 continue restart; } // 物理摘除成功前驱不变推进当前指针 curr next_ptr; continue; } // 当前节点是有效节点对比 Key let curr_key unsafe { (*curr).key }; if curr_key key { pred curr; curr next_ptr; } else { if curr_key key { found true; } result.preds[level] pred; result.succs[level] curr; break; } } } return found; } } }五、无锁插入协议自底向上的层级建立插入新节点必须严格遵循自底向上的挂载原则先利用find找到目标键在每一层应该插入的位置记录前驱preds与后继succs。如果键已存在且有效直接返回存在或 CAS 更新值。随机生成新节点的高度 $H$。将新节点在各层的后继指针预先指向对应的succs。在 Level 0 执行决胜 CAS将preds[0].next指向新节点。一旦 Level 0 CAS 成功该节点在逻辑上便宣告正式入驻跳表随后自 Level 1 向上逐层建立链接。如果在高层 CAS 失败说明前驱发生变动当前线程只需重新调用find刷新该层前驱后继重试直至顶层。implK: Ord Default, V: Default LockFreeSkipListK, V { pub fn insert(self, key: K, val: V, height: usize) - bool { let mut result SearchResult::empty(); loop { if self.find(key, mut result) { // 键已存在插入失败 return false; } let new_node SkipNode::new(key, val, height); // 1. 初始化新节点的所有层后继指针 for level in 0..height { unsafe { (*new_node).next[level] MarkedAtomicPtr::new(result.succs[level]); } } // 2. 关键决胜点在 Level 0 尝试挂载 let pred_0 result.preds[0]; let succ_0 result.succs[0]; let cas_0 unsafe { (*pred_0).next[0].compare_exchange_clean( succ_0, new_node, Ordering::AcqRel, Ordering::Acquire, ) }; if cas_0.is_err() { // Level 0 挂载失败说明有其他线程在此期间抢先插入或标记销毁孤儿节点重试 unsafe { drop(Box::from_raw(new_node)); } continue; } // 3. Level 0 成功节点已生效开始自底向上逐层链接高层 for level in 1..height { loop { let pred result.preds[level]; let succ result.succs[level]; // 检查新节点自身在该层是否已经被其他并发删除线程打上了删除标记 let (_, self_marked) unsafe { (*new_node).next[level].load_marked(Ordering::Acquire) }; if self_marked { // 刚插入就被并发删除无需继续向上连接 return true; } unsafe { (*new_node).next[level] MarkedAtomicPtr::new(succ); let cas_res (*pred).next[level].compare_exchange_clean( succ, new_node, Ordering::AcqRel, Ordering::Acquire, ); if cas_res.is_ok() { break; // 本层挂载成功进入上一层 } } // 本层挂载失败重新通过 find 检索本层最新前驱 self.find(unsafe { (*new_node).key }, mut result); } } return true; } } }六、无锁删除协议自顶向下标记与原子物理切除与插入恰好相反删除操作必须遵循自顶向下的标记锁定自底向上的物理剥除调用find找到目标节点。如果未找到直接返回 false。从该节点的最高层开始向下逐层为其next指针打上标记Mark Bit 1。关键决胜点为 Level 0 打上标记。一旦 Level 0 标记成功该节点正式从逻辑上被消灭。再次调用find触发协助物理切除算子彻底摘除该节点在各层中的物理拓扑连接。implK: Ord Default, V: Default LockFreeSkipListK, V { pub fn remove(self, key: K) - bool { let mut result SearchResult::empty(); loop { if !self.find(key, mut result) { // 节点不存在或已被逻辑删除 return false; } let target result.succs[0]; if target.is_null() { return false; } let node_height unsafe { (*target).height }; // 1. 自顶向下逐层打上删除标记 for level in (1..node_height).rev() { loop { let (clean_next, is_marked) unsafe { (*target).next[level].load_marked(Ordering::Acquire) }; if is_marked { // 已被其他并发删除线程标记 break; } if unsafe { (*target).next[level].mark_node(clean_next).is_ok() } { break; } } } // 2. 最终决胜点在 Level 0 打上删除标记 loop { let (clean_next, is_marked) unsafe { (*target).next[0].load_marked(Ordering::Acquire) }; if is_marked { // 并发竞争中其他删除者抢先完成了 Level 0 标记 return false; } if unsafe { (*target).next[0].mark_node(clean_next).is_ok() } { // Level 0 逻辑删除成功主动调用一次 find 触发全局物理协助摘除 self.find(key, mut result); return true; } } } } }七、内存回收防线Epoch-Based Reclamation (EBR)在无锁数据结构中代码将节点物理摘除后绝不能立即调用drop(Box::from_raw(target))释放内存因为此时可能有其他只读线程如无锁并发范围扫描正持有着该节点的裸指针在 CPU 流水线中进行寻址。如果立即释放将瞬间引发最致命的野指针段错误Segmentation Fault / Use-After-Free。工业级 Rust 无锁数据结构如crossbeam-skiplist必须配合基于代际的内存回收机制Epoch-Based Reclamation, EBR读写线程进入关键区前向全局注册当前 Epoch 屏障Pin。被物理摘除的节点压入延迟释放队列Garbage Bag。仅当全局所有活跃线程的 Epoch 均超越了该垃圾产生时的代际该节点才会被安全执行内存析构。八、总结与性能反思从自旋互斥锁Mutex到读写锁RwLock再到底层基于标记指针与协助清理的无锁跳表我们付出了极其可观的代码复杂度代价。但换来的是多核高并发压测下近乎完美线性的扩展能力读操作全无锁遍历链表无需任何锁与原子写入开销仅依赖纯 Acquire 内存顺序的 Load。写冲突局部化插入与删除的 CAS 仅发生在局部相邻节点避免了全树旋转造成的全局雪崩。优雅的故障自愈利用“路过清理”的协作式设计将并发竞争的损耗均摊到了每个遍历线程中。搞懂无锁跳表中的标记指针与内存屏障你就真正站在了 Rust 底层系统编程与高并发架构的最前沿。在现代大规模分布式系统的数据基座中这才是支撑千万级 QPS 不倒的钢铁龙骨。
