并发协调的代价

A Mutex is Slow

Mutex 到底慢不慢？

Mutex 本身并不慢，问题的根源在于CPU 缓存一致性协议

一个简单的基准测试演示这个问题：

// 使用原子引用计数的计数器，多个线程读取letcounter=Arc::clone(&shared_counter);for_in0..n{// 获取读锁并读取计数器let_guard=black_box(&counter).lock().unwrap();let_value=counter.load(Ordering::SeqCst);}

black_box用于防止编译器优化掉这个循环，因为如果没有实际使用读取的值，编译器可能会将整个循环视为无操作。

结果

违反直觉：增加线程后性能反而下降。按理说互斥锁只允许一个线程执行，其他线程应该等待——性能应该保持不变，而不是变差。这说明存在其他影响因素。

CPU 缓存的三层

要理解这个问题，需要先了解 CPU 缓存的工作方式

主存访问对于 CPU 来说「极其漫长」——在等待主存响应的同时，CPU 可以执行数百条指令。

缓存行 (Cache Line)

CPU 将主存划分为64 字节的块来管理，每个块称为一个缓存行 (cache line)。所有缓存一致性的协调都基于缓存行而非单个字节。

MESI 协议：缓存一致性

当多个 CPU 核心需要访问同一块内存时，需要一个协议来协调——这就是MESI 协议。

四种状态

当一个核心要将Shared状态的缓存行改为可写时：

核心必须与所有其他核心通信 → 确认它们都已经放弃对该行的修改权限 → 将状态转为 Exclusive → 然后才能写入

这就是跨核心通信的来源——每次协调都需要在核心之间「ping-pong」传递缓存行。

延迟数据

跨核心通信的延迟是 L1 缓存访问的 30 倍，几乎达到主存延迟的三分之一

读写锁的隐藏成本

Reader-Writer Lock 的问题

读写锁的实现内部有一个读者计数器。获取读锁时需要对这个计数器执行fetch_add（原子加一）操作。

问题在于：如果 100 个线程都要获取读锁，它们都在对**同一个共享字段**执行写操作

线程 0: 获取 Exclusive → 修改计数器 → 转为 Shared 线程 1: 观察到 Modified → 核心 0 写回数据给核心 1 → 核心 1 变为 Modified 线程 0: 释放锁 → 核心 1 写回 → 核心 0 变为 Modified 线程 2: ... ...（每个读者都需要一次 cache line ping-pong）

• 单线程：~250 million ops/sec（与 Mutex 相同）
• 单线程 Mutex：性能随线程增加而下降，最终稳定在低水平
• Reader-Writer Lock：开始时与 Mutex 相同，但随着读者增加，性能比 Mutex 更差

原因：

对于互斥锁，持有锁的线程可以一直保持 Exclusive 状态直到释放

对于读写锁，每个读者都需要修改共享计数器，导致频繁的缓存行争夺

Reader-Writer Lock在读多写少场景下「理应」更快，但实际上随着读者数量增加，它们彼此之间的竞争反而更严重

什么时候锁的开销真正成为问题

当锁保护的代码（临界区）很短时，锁的开销才会成为瓶颈。

短代码（如简单计数），锁开销可能超过执行时间，成为主要成本

这解释了为什么大多数代码不会遇到这个问题——只有在高度专业化的hot path代码中，这个问题才会显现。

方案：Left-Right数据结构

设计思想

问题：所有读者为什么要访问同一个共享缓存行？如果读者之间不需要协调，它们的缓存行应该保持独立。

Left-Right 数据结构保留两份数据副本：

┌─────────────────────────────────────────┐ │ Atomic Pointer │ │ (指向 left 或 right 副本) │ └─────────────────────────────────────────┘ │ │ ▼ ▼ ┌─────────┐ ┌─────────┐ │ Left │ │ Right │ │ Copy │ │ Copy │ └─────────┘ └─────────┘

• 读者：通过原子指针读取当前激活的副本
• 写者：修改非激活的副本，然后切换指针

读者计数器机制

读者需要通知写者「我已经看到新指针了」才能安全地开始修改旧副本。实现方式：

每个读者维护自己的计数器，每个计数器独占一个缓存行（通过#[repr(align(64))]对齐）。

// 读者每次读取前递增计数器reader_counter.fetch_add(1,Ordering::SeqCst);letdata=atomic_pointer.load(Ordering::SeqCst).data;reader_counter.fetch_add(1,Ordering::SeqCst);// 写者切换指针后，遍历所有读者计数器// 如果某个计数器的值变化了至少 1，说明该读者已经看到新指针forreaderinall_readers{ifcurrent_value-previous_value>=1{// 该读者已切换，可以安全修改旧副本}}

性能结果

读者之间完全独立，不需要任何协调。读操作是无锁的 (lock-free)和无等待的 (wait-free)——不需要获取任何锁，不需要等待写者完成。

调试：False Sharing（伪共享）

在测试 Left-Right 数据结构时，发现当线程数达到 4 时，性能突然下降 10 倍——而不是预期的线性增长。

原因

缓存行大小是 64 字节。如果多个线程的计数器碰巧落在**同一个缓存行**上：

[线程 0 计数器][线程 1 计数器][线程 2 计数器][线程 3 计数器] <---------------------- 同一缓存行 ----------------------->

即使每个线程只修改自己的计数器，由于它们在同一个缓存行上，MESI 协议仍然会将缓存行在核心之间来回传递。

修复

// 一行修复：将计数器类型对齐到 64 字节#[repr(align(64))]structReaderCounter{value:AtomicUsize,}

现在每个计数器必须位于独立的缓存行上，问题消失。

总结

无锁 (lock-free) ≠ 无竞争 (contention-free)

即使没有使用锁，内存布局和缓存一致性机制仍然会对性能产生重大影响。

选择并发原语的决策框架

需要问自己的问题

1. 读写比例是多少？

   • 读多写少→ Left-Right 可能适合
   • 读写均衡→ 互斥锁可能是更好的选择

2. 临界区有多长？

   • 短临界区 → 锁开销占比高，需要仔细选择
   • 长临界区 → 大多数并发原语都足够好

3. 需要多少线程？

   • 少量线程（< 3）→ 大多数情况下不需要特别优化
   • 高并发 → 协调成本急剧增加

4. 能否容忍最终一致性？

   • Left-Right 保证最终一致性，不保证线性一致性
   • 金融交易等场景需要强一致性保证，不适合

5. 需要线性化保证吗？

   • 某些场景需要严格的interleaving约束
   • 需要了解具体的一致性语义需求

各方案的平衡

Left-Right 数据结构的额外限制

1. 单写者限制

   • 只允许一个写者。如果需要多个写者，必须在 Left-Right 外层再加互斥锁

2. 操作必须是确定性的

   • 需要能够将操作记录为日志并重放
   • 因为写者需要将同一批操作应用到两个副本

3. 写者需要等待所有读者离开

   • 写者不能立即开始修改，必须等待所有读者切换到新副本

4. 不是线性可化的

   • 只保证最终一致性，不适合所有场景

硬件层面的演进

MESI 协议的演进

• 最初：MSI 协议
• 后来：添加了E (Exclusive)状态，可以避免一半的缓存行竞争
• 现代 CPU：已经有 7-8 个状态的变体（但具体实现是专有的）

3D V-Cache 技术

AMD 的 3D V-Cache 技术将 L3 缓存堆叠在 CPU 上方，缩短了物理距离，有助于减少某些场景下的延迟。

Fetch-Add 优化

Fetch-Add 操作是可交换的 (commutative)，理论上可以让多个 CPU 批量执行后再统一通信。但这种优化目前似乎没有在实际平台中使用。

• 协调是昂贵的，不是因为锁本身慢，而是因为缓存一致性协议需要在核心之间传递缓存行
• 没有银弹——每种并发方案都有权衡。选择的关键是理解你的应用特征（读写比例、临界区长度、一致性需求），然后选择与这些特征匹配的数据结构

性能 = 选择与你的数据访问模式相匹配的算法 + 利用你的工作负载的所有特征 + 消除不必要的跨核心通信

永远要**先测量再优化**，理解你正在优化的具体瓶颈是什么。