解读

国内大厂（阿里、字节、华为）的 Rust 岗位面试里，“无锁并发容器” 是区分“会用”与“懂原理”的分水岭。SkipSet 作为 crossbeam-epoch 生态的旗舰结构，面试官真正想听的是：

1. 它如何用 epoch-based reclamation（EBR） 解决内存释放问题；
2. 跳表层级如何做到 lock-free 插入与删除；
3. 在 ARM64 与 x86 弱序模型 下如何保证线性一致性。
   回答若只停留在“用 CAS 保证线程安全”会被直接打断，必须讲清 crossbeam-epoch 的三色回收协议、跳表的 tower 更新策略、以及 search-and-link 的线性化点。

知识点

• crossbeam-epoch 三色标记：Pin(Active)、Pending、Retired；线程通过 pin() 进入临界区，保证已读节点延迟回收。
• 跳表无锁插入：自顶向下搜索，预分配新节点 tower，CAS 更新每一层前驱的 next 指针；失败则重试，保证 only one winner。
• 无锁删除：逻辑删除（标记最高层 next 指针的 tagged pointer）+ 物理延迟回收；search 路径帮助完成 unlink，即 helping 机制。
• 内存序：next 指针使用 Acquire/Release，tower 高度使用 Relaxed；删除标记使用 fetch_or(tag, AcqRel) 保证单字原子。
• ABA 免疫：64 位宽字内嵌 16 位 tag，crossbeam-utils::atomic::AtomicPtr<T>与Owned<T>` 封装，配合 EBR 杜绝节点复用。
• 迭代器一致性：基于 pin 时刻的快照，不反映后续插入，但保证已迭代元素不会被回收。

答案

crossbeam::SkipSet 的无锁算法由 epoch-based reclamation + 跳表 tower CAS 双引擎驱动，步骤如下：

1. 进入临界区：线程先 epoch::pin()，把当前线程标记为 Active，并缓存全局 epoch；后续读到的节点只要在此 pin 期内均不会被回收。
2. search 路径：从最高层头节点出发，维护每一层的前驱/后继指针，遇到已标记删除的节点（next 指针 tag 位为 1）则尝试 help_unlink，用 CAS 把前驱直接指向后继，保证路径实时清理。
3. 插入
   a. 随机生成 tower 高度，一次性分配节点，所有 next 指针初始化为 null；
   b. 重新 search 拿到每一层前驱，从底层到高层依次 CAS 链接；若任一失败，释放该节点并重试；
   c. 成功链接后，若发现相邻节点已被标记删除，立即 help_unlink，把插入与帮助逻辑合并，减少重复遍历。
4. 删除
   a. 先 search 定位目标节点，用 fetch_or 给最高层 next 指针打 tag，完成逻辑删除；此 CAS 是 线性化点，一旦成功，其他线程 search 会跳过它；
   b. 从最高层到最低层，help_unlink 把前驱 CAS 到被删节点的后继；全部层解除引用后，把节点加入本地垃圾袋；
   c. 当全局 epoch 推进且当前线程 pin 结束，把垃圾袋中节点批量 retire，待 所有线程都跨过该 epoch 后由后台线程安全释放。
5. 内存序与性能：next 指针的 CAS 使用 AcqRel，保证前后驱关系可见；tower 高度只用 Relaxed，因为随机生成无数据依赖；tagged pointer 的 16 位 ABA counter 在 64 位系统足够，避免宽 CAS 带来的 cmpxchg16b 指令开销，在国产 ARM 服务器同样高效。

通过以上机制，SkipSet 在 ARM64 48 核场景下仍能保持 百万级插入/删除操作吞吐量，且 延迟分布无长尾，满足国内云原生网关对高并发 Key-Range 索引的严苛需求。

拓展思考

1. 与 Java ConcurrentSkipListMap 对比：后者基于 标记指针+valiate 哨兵，依赖 GC 延迟回收；Rust 用 EBR 显式退休，无 STW、无跨语言 GC 绑定，更适合嵌入式与内核场景。
2. 国产芯片弱内存模型：在 鲲鹏 920 实测，若把 next 指针 CAS 降级为 Relaxed，会出现 search 返回已删节点 的异常；必须 坚守 AcqRel，这是国内面试官常挖的坑。
3. 替代 EBR 的新方向：HP (Hazard Pointer) 与 QSBR 在 Linux 内核已有实践，crossbeam 也在实验 “可配置回收策略”；若未来在内核模块用 Rust 写无锁路由表，可 按 NUMA 节点选择 HP，降低 跨核 epoch 同步开销。