name: 无锁数据结构 description: “实现无锁和无等待数据结构，用于高并发系统。” version: “1.0.0” tags: [并发, 无锁, 数据结构, oopsla] difficulty: 高级 languages: [Rust, C++, Java] dependencies: [并发验证器, 内存分配器]
无锁数据结构
无锁数据结构允许多个线程在不使用锁的情况下访问共享数据，从而提供更好的可扩展性并避免死锁和优先级反转等问题。
何时使用此技能
- 构建高性能并发系统
- 避免与锁相关的问题（死锁、车队效应）
- 需要无等待保证的实时系统
- 高竞争场景
- 可扩展的服务器应用程序
此技能的作用
- CAS操作：使用比较并交换进行原子更新
- 内存回收：安全的内存回收（危险指针，RCU）
- ABA预防：处理无锁算法中的ABA问题
- 进度保证：确保无锁或无等待进度
- 正确性验证：证明线性化性
关键概念
| 概念 | 描述 |
|---|---|
| CAS | 比较并交换原子操作 |
| 无锁 | 至少一个线程取得进展 |
| 无等待 | 每个线程在有限步骤内完成 |
| 线性化性 | 操作表现为原子操作 |
| ABA问题 | 值从A变B再变A，CAS不正确成功 |
| 危险指针 | 安全内存回收方案 |
提示
- 使用原子原语（CAS，FAA）进行无锁编码
- 实现安全内存回收（危险指针，EBR）
- 注意ABA问题
- 使用线程消毒剂进行广泛测试
- 考虑使用现有库（crossbeam，kotlinx）
常见用例
- 高吞吐量消息队列
- 并发缓存
- 实时交易系统
- 游戏引擎
- 数据库系统
相关技能
concurrency-verifier- 验证正确性message-passing-system- 替代并发模型memory-allocator- 无锁分配器transactional-memory- 无锁替代方案
经典参考
| 参考 | 重要性 |
|---|---|
| Herlihy & Shavit “多处理器编程的艺术” | 全面论述 |
| Maged M. Michael & Michael L. Scott “简单、快速、实用的非阻塞和阻塞并发队列算法” (PODC 1996) | 经典队列算法 |
| Michael “危险指针：无锁对象的安全内存回收” (TPDS 2004) | 内存回收 |
权衡与限制
方法权衡
| 方法 | 优点 | 缺点 |
|---|---|---|
| 无锁 | 无死锁，可扩展 | 复杂，ABA问题 |
| 无等待 | 保证进展 | 非常复杂 |
| 基于锁 | 简单 | 死锁，竞争 |
何时不使用此技能
- 低竞争场景（锁即可）
- 当简单性比性能更重要时
- 当内存顺序是平台特定时
限制
- 内存回收棘手
- ABA问题需要仔细处理
- 并非所有算法都有无锁版本
评估标准
高质量实现应具备：
| 标准 | 寻找点 |
|---|---|
| 正确性 | 线性化操作 |
| 进度 | 无锁或无等待 |
| 安全性 | 无释放后使用 |
| 性能 | 随线程数量扩展 |
质量指标
✅ 良好：线性化，适当内存回收，处理ABA ⚠️ 警告：工作但存在内存安全问题 ❌ 差：竞态条件，内存泄漏，实际上并非无锁
研究工具与工件
现实世界无锁数据结构：
| 工具 | 重要性 |
|---|---|
| crossbeam (Rust) | 无锁数据结构 |
| ConcurrentSkipList | Java并发跳表 |
| ConcurrentHashMap | Java CHM |
| boost.lockfree | C++无锁 |
| disruptor | LMAX Disruptor |
关键库
- crossbeam：Rust并发
- java.util.concurrent：Java并发
研究前沿
当前无锁研究：
| 方向 | 关键论文 | 挑战 |
|---|---|---|
| 线性化性 | “线性化性” (1990) | 验证 |
| 基于纪元 | “纪元回收” | 内存回收 |
| 混合 | “混合回收” | 组合方法 |
热点话题
- 无锁用于Wasm：WebAssembly并发
- 量子无锁：量子数据结构
实现陷阱
常见无锁错误：
| 陷阱 | 真实示例 | 预防 |
|---|---|---|
| ABA | CAS在重用节点上成功 | 标签指针 |
| 内存 | 释放后使用 | 危险指针 |
| 顺序 | 错误内存顺序 | 小心顺序 |