并发协调的代价

A Mutex is SlowMutex 到底慢不慢Mutex 本身并不慢问题的根源在于CPU 缓存一致性协议一个简单的基准测试演示这个问题// 使用原子引用计数的计数器多个线程读取letcounterArc::clone(shared_counter);for_in0..n{// 获取读锁并读取计数器let_guardblack_box(counter).lock().unwrap();let_valuecounter.load(Ordering::SeqCst);}black_box用于防止编译器优化掉这个循环因为如果没有实际使用读取的值编译器可能会将整个循环视为无操作。结果线程数吞吐量单线程基准1 线程~250 million ops/sec约每 10 条指令完成一次加锁读取2 线程~25 million ops/sec下降约 10 倍更多线程几乎持平略微下降违反直觉增加线程后性能反而下降。按理说互斥锁只允许一个线程执行其他线程应该等待——性能应该保持不变而不是变差。这说明存在其他影响因素。CPU 缓存的三层要理解这个问题需要先了解 CPU 缓存的工作方式层级延迟特点L1 Cache~1 ns离 CPU 最近直接焊在 CPU 上非常小L2 Cache~3-5 ns比 L1 大比 L3 小L3 Cache~10-20 ns多个核心共享距离主存更近主存 (RAM)~100 ns距离 CPU 最远延迟极高主存访问对于 CPU 来说「极其漫长」——在等待主存响应的同时CPU 可以执行数百条指令。缓存行 (Cache Line)CPU 将主存划分为64 字节的块来管理每个块称为一个缓存行 (cache line)。所有缓存一致性的协调都基于缓存行而非单个字节。MESI 协议缓存一致性当多个 CPU 核心需要访问同一块内存时需要一个协议来协调——这就是MESI 协议。四种状态状态含义Modified (M)当前核心持有唯一副本且数据与主存不一致脏数据。需要写回主存才能让其他核心读取Exclusive (E)当前核心持有唯一副本数据与主存一致。其他核心没有这个缓存行时处于此状态Shared (S)多个核心都持有该缓存行且数据值相同Invalid (I)当前核心没有该缓存行的有效副本当一个核心要将Shared状态的缓存行改为可写时核心必须与所有其他核心通信 → 确认它们都已经放弃对该行的修改权限 → 将状态转为 Exclusive → 然后才能写入这就是跨核心通信的来源——每次协调都需要在核心之间「ping-pong」传递缓存行。延迟数据操作延迟L1 Cache 访问~1 ns跨核心通信 (cache line transfer)~30 nsRAM 访问~100 ns跨核心通信的延迟是 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);letdataatomic_pointer.load(Ordering::SeqCst).data;reader_counter.fetch_add(1,Ordering::SeqCst);// 写者切换指针后遍历所有读者计数器// 如果某个计数器的值变化了至少 1说明该读者已经看到新指针forreaderinall_readers{ifcurrent_value-previous_value1{// 该读者已切换可以安全修改旧副本}}性能结果线程数吞吐量1 线程~250 million ops/sec基准N 线程线性增长接近 N × 基准读者之间完全独立不需要任何协调。读操作是无锁的 (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)即使没有使用锁内存布局和缓存一致性机制仍然会对性能产生重大影响。选择并发原语的决策框架需要问自己的问题读写比例是多少读多写少→ Left-Right 可能适合读写均衡→ 互斥锁可能是更好的选择临界区有多长短临界区 → 锁开销占比高需要仔细选择长临界区 → 大多数并发原语都足够好需要多少线程少量线程 3→ 大多数情况下不需要特别优化高并发 → 协调成本急剧增加能否容忍最终一致性Left-Right 保证最终一致性不保证线性一致性金融交易等场景需要强一致性保证不适合需要线性化保证吗某些场景需要严格的interleaving约束需要了解具体的一致性语义需求各方案的平衡方案优点缺点适用场景Mutex简单正确性好强保证高竞争下性能差大多数场景Reader-Writer Lock读多写少时理论上高效读者多时彼此竞争读密集但写不频繁Left-Right读者完全并行无锁读取写操作成本高需要两份数据不保证立即可见性极稀疏的写操作Lock-Free 数据结构不阻塞线程实现复杂需要精心设计高性能关键路径Left-Right 数据结构的额外限制单写者限制只允许一个写者。如果需要多个写者必须在 Left-Right 外层再加互斥锁操作必须是确定性的需要能够将操作记录为日志并重放因为写者需要将同一批操作应用到两个副本写者需要等待所有读者离开写者不能立即开始修改必须等待所有读者切换到新副本不是线性可化的只保证最终一致性不适合所有场景硬件层面的演进MESI 协议的演进最初MSI 协议后来添加了E (Exclusive)状态可以避免一半的缓存行竞争现代 CPU已经有 7-8 个状态的变体但具体实现是专有的3D V-Cache 技术AMD 的 3D V-Cache 技术将 L3 缓存堆叠在 CPU 上方缩短了物理距离有助于减少某些场景下的延迟。Fetch-Add 优化Fetch-Add 操作是可交换的 (commutative)理论上可以让多个 CPU 批量执行后再统一通信。但这种优化目前似乎没有在实际平台中使用。协调是昂贵的不是因为锁本身慢而是因为缓存一致性协议需要在核心之间传递缓存行没有银弹——每种并发方案都有权衡。选择的关键是理解你的应用特征读写比例、临界区长度、一致性需求然后选择与这些特征匹配的数据结构性能 选择与你的数据访问模式相匹配的算法 利用你的工作负载的所有特征 消除不必要的跨核心通信永远要**先测量再优化**理解你正在优化的具体瓶颈是什么。