用 Rust 从零实现无锁队列:内存序到底在说什么
Ordering::Acquire、Ordering::Release、Ordering::SeqCst——这三个词大概劝退了 80% 想学无锁编程的人。
它们难受的地方在于:你写错了,程序在 x86 上大概率还能跑对。 只有到了 ARM,或者编译器某次优化变了,才会突然出错。没有反例,就没有直觉。
这篇从零写一个 SPSC(单生产者单消费者)环形队列,重点是故意先写错,再看它为什么会错。
为什么选 SPSC
无锁队列分好几种:
| 类型 | 生产者 | 消费者 | 难度 |
|---|---|---|---|
| SPSC | 1 | 1 | 低 |
| MPSC | 多 | 1 | 中 |
| MPMC | 多 | 多 | 高(ABA 问题) |
从 SPSC 入手,是因为它只需要两个原子变量,不用处理 CAS 回环和 ABA。但即使这么简单的结构,内存序写错一样会出问题。
环形缓冲区的结构
use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicUsize, Ordering};
pub struct RingBuffer<T> {
buffer: Box<[UnsafeCell<Option<T>>]>,
capacity: usize,
// 只有生产者写
head: AtomicUsize,
// 只有消费者写
tail: AtomicUsize,
}约定:head 是生产者下一个要写的下标,tail 是消费者下一个要读的下标。队列为空时 head == tail。
用 UnsafeCell 是因为要在 &self 的情况下写数据——这正是 Sync 需要 unsafe 实现的原因。
unsafe impl<T: Send> Sync for RingBuffer<T> {}
unsafe impl<T: Send> Send for RingBuffer<T> {}生产者:写入并发布
impl<T> RingBuffer<T> {
pub fn push(&self, value: T) -> Result<(), T> {
let head = self.head.load(Ordering::Relaxed);
let next = (head + 1) % self.capacity;
// 队列满判断:追上了 tail
if next == self.tail.load(Ordering::Acquire) {
return Err(value);
}
// 写入数据
unsafe {
*self.buffer[head].get() = Some(value);
}
// 关键:发布 head,让消费者能看到
self.head.store(next, Ordering::Release);
Ok(())
}
}消费者:
pub fn pop(&self) -> Option<T> {
let tail = self.tail.load(Ordering::Relaxed);
// 空判断:追上了 head
if tail == self.head.load(Ordering::Acquire) {
return None;
}
let value = unsafe { (*self.buffer[tail].get()).take() };
self.tail.store((tail + 1) % self.capacity, Ordering::Release);
value
}
}代码不长,但每一处 Ordering 都不是随便写的。下面逐个拆。
内存序到底在保证什么
先说一个大多数人没意识到的事实:CPU 和编译器都会重排你的指令。
看这段代码:
x = 1;
ready = true;在单线程视角里,这两句有先后顺序。但:
- 编译器可能认为
ready = true和x = 1无关,调换顺序 - CPU 可能先写
ready,再写x(这叫 Store Buffer,x86 上也有)
如果别的线程看到 ready == true 就去读 x,它可能读到旧值。
内存序(memory ordering)就是给编译器和 CPU 划定的重排边界。
Release / Acquire 配对
回到队列。生产者的顺序是:
*self.buffer[head].get() = Some(value); // 1. 写数据
self.head.store(next, Ordering::Release); // 2. 发布下标这两句绝对不能调换。如果先发布了 head,消费者可能看到一个还没写入数据的槽位,读到 None。
Ordering::Release 的语义是:在这一句之前的所有内存操作,都不能被重排到它之后。
消费者的顺序是:
if tail == self.head.load(Ordering::Acquire) { return None; } // 1. 读下标
let value = unsafe { (*self.buffer[tail].get()).take() }; // 2. 读数据Ordering::Acquire 的语义是:在这一句之后的所有内存操作,都不能被重排到它之前。
两者配对,就形成了一个同步关系(synchronize-with):
生产者: [写数据] --Release--> [写 head]
|
| (跨线程可见)
v
消费者: [读 head] --Acquire--> [读数据]Release 保证"我前面的写都做完了才发布",Acquire 保证"我拿到发布值后,前面的写我都看得到"。缺任何一个,配对就断了。
为什么满/空判断用 Acquire,自己的下标用 Relaxed
看这一句:
let head = self.head.load(Ordering::Relaxed);head 只有生产者会写,生产者读自己的值,不存在跨线程同步问题——用 Relaxed 就够了,因为 Relaxed 只保证原子性,不保证顺序。
但这一句:
if next == self.tail.load(Ordering::Acquire) {tail 是消费者写的。生产者要读它来判断空满,必须用 Acquire——否则可能读到过期的 tail,把"满"误判成"不满",覆盖未读数据。
规律:只被自己写的变量用 Relaxed;可能读到别人写的变量,读用 Acquire。
SeqCst:最省事也最慢
还有第四个选项 Ordering::SeqCst。它保证了所有线程看到的总顺序一致:
self.head.store(next, Ordering::SeqCst);SeqCst 的特点是在 x86 上要加 mfence 指令(或者用 lock 前缀),代价比 Acquire/Release 高。但它的好处是写错了也不会错(在顺序上)。
工程实践里的经验法则是:
| 场景 | 选择 |
|---|---|
| 计数器、统计 | Relaxed |
| 单写单读的发布-订阅 | Release / Acquire |
| 需要多变量全局顺序一致 | SeqCst |
| 拿不准 | 先用 SeqCst,验证正确后再降级 |
先写对,再写快。 无锁代码里,正确性不能用性能来换。
经典的错误示范
把 Release 改成 Relaxed,会怎样?
// 错误:这里丢了 Release
self.head.store(next, Ordering::Relaxed);
// 更糟:连数据写入都可能被重排到发布之后
self.head.store(next, Ordering::Relaxed);
*self.buffer[head].get() = Some(value);结果就是消费者可能读到 Some(None) 或者旧的 None——数据丢失,而且在 x86 上很可能测不出来,因为 x86 是强内存模型(TSO),只有 Store-Load 会被重排。
这也是为什么很多无锁 bug 在开发机上正常,一上 ARM 服务器就出问题。测试环境跑不出来,不代表代码是对的。
用 loom 验证
Rust 生态里有个专门测并发正确性的工具叫 loom。它会穷举所有可能的线程交错,把上面那些"偶发" bug 变成必现。
#[cfg(test)]
mod tests {
use loom::sync::atomic::{AtomicUsize, Ordering};
use loom::thread;
#[test]
fn spsc_no_lost_items() {
loom::model(|| {
let head = loom::sync::Arc::new(AtomicUsize::new(0));
let tail = loom::sync::Arc::new(AtomicUsize::new(0));
let h = head.clone();
let t = tail.clone();
let producer = thread::spawn(move || {
h.store(1, Ordering::Release);
});
let consumer = thread::spawn(move || {
while t.load(Ordering::Acquire) == 0 {
thread::yield_now();
}
});
producer.join().unwrap();
consumer.join().unwrap();
});
}
}loom 的价值在于:它把"内存模型"这个抽象概念,变成了一个可以跑测试验证的东西。无锁代码不上 loom,基本等于裸奔。
什么时候该用无锁
最后泼点冷水。无锁队列不是万能的:
1. 竞争激烈时更慢。 无锁在高竞争下会不停 CAS 自旋,空烧 CPU。有锁至少会让线程休眠。低竞争用无锁,高竞争反而常常是锁更好。
2. 内存回收难。 SPSC 简单是因为没有 ABA,但 MPMC 里"一个线程刚读到的节点可能已被别人释放",需要 epoch-based reclamation 或者 hazard pointer。这是另一个量级的复杂度。
3. 正确性验证成本高。 有锁代码看一眼就知道对不对,无锁代码要推导 happens-before 关系。
所以我的建议是:优先用 channel 和 Mutex,只在性能剖析明确指到锁竞争时,才上手无锁。 而且一定要配 loom。
结论
内存序不是玄学,它只是在回答一个问题:"我这次写,什么时候能被别人看见?"
Release 管"我前面的写别乱跑";Acquire 管"我后面的读别提前";Relaxed 只管原子性;SeqCst 管全局顺序。SPSC 队列里,发布用 Release,订阅用 Acquire,独占变量用 Relaxed。
把 SPSC 队列写一遍,再用 loom 折磨它一遍,你对内存模型的理解就不是"背下来的八个字",而是能看到那个 StoreLoad 屏障站在哪里。