返回文章列表

用 Rust 从零实现无锁队列:内存序到底在说什么

393 字·3 分钟阅读
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 屏障站在哪里。