用 Rust 从零实现工作窃取调度器:为什么每个线程都要有自己的队列
前面写过线程池,用的是
Arc<Mutex<Receiver>>。它在低并发下没问题,但有一个致命瓶颈:所有工作线程抢同一把锁。
锁竞争的代价随核数增加而非线性恶化。8 核时还能忍,64 核时大部分 CPU 都花在等锁上。这就是为什么所有高性能运行时(tokio、Rayon、Go runtime、Java ForkJoinPool)都用同一种结构:工作窃取(work-stealing)。
全局队列的问题在哪
先看清问题的形状:
┌─────────────────┐
生产者 ->│ 全局任务队列 │<- 所有 worker 在这里抢
└─────────────────┘
↑ ↑ ↑ ↑ ↑ ↑
w w w w w w w w (每个 worker 都要拿锁)每次取任务都要:
- 拿锁
- 从队列弹出
- 释放锁
三个步骤都很快,但 8 个线程每秒各取 100 万次,就是 800 万次锁操作。锁本身的开销(cache line 争抢、上下文切换)会占掉相当一部分 CPU。
更糟的是"锁被某个线程长时间持有"时的** convoy effect**:其他所有线程排队等待,吞吐骤降。
工作窃取的核心:每线程一个队列
工作窃取的思路很直接:不共享队列,每个 worker 有自己的队列。
┌──────────┐ ┌──────────┐ ┌──────────┐
worker0│ 队列 [..] │ │ 队列 [..] │ │ 队列 [..] │worker2
└──────────┘ └──────────┘ └──────────┘
↑ ↑ ↑
本地 push/pop 本地 push/pop 本地 push/pop
(无锁) (无锁) (无锁)
偷不到 → 从别人的队列尾部拿规则是:
- 每个 worker 从自己队列的一端取任务(叫"头")
- 空闲的 worker 从别人队列的另一端偷(叫"尾")
- 本地操作占绝大多数,几乎不需要同步
为什么本地和窃取要用不同的端? 这是整个设计最关键的一点:
worker A 的队列: [头 .......... 尾]
↑ ↑
A 自己在这里 别人从这里偷
push / pop如果两端都从同一端操作,本地线程和窃取线程会频繁争抢同一个位置。分两端之后,只有队列接近空或接近满时才会真正冲突。
工作窃取的本质是"用队列分离换取无锁",而两端分离是把冲突降到最低的关键技巧。
那个特殊的 deque
工作窃取需要的队列不是普通的 VecDeque,而是一个两端并发访问语义不同的 deque:
| 端 | 谁访问 | 并发度 |
|---|---|---|
| 头(本地) | 只有 owner | 无锁,但必须和"最后一个元素"的窃取处理竞争 |
| 尾(窃取) | 任意其他 worker | CAS 循环 |
这就是 Chase-Lev deque。它有一条非常精妙的规则:
当头尾只差一个元素时,本地取任务要用 CAS,而且要和其他窃取者竞争。
use std::sync::atomic::{AtomicIsize, Ordering};
pub struct Worker<T> {
/// 环形缓冲区
slots: Box<[std::cell::UnsafeCell<Option<T>>]>,
/// 头指针:只有 owner 修改
head: AtomicIsize,
/// 尾指针:owner 和窃取者都可能修改
tail: AtomicIsize,
mask: isize,
capacity: isize,
}先实现那个"环形缓冲区 + 位掩码"的容量计算:
impl<T> Worker<T> {
pub fn new(capacity: usize) -> Self {
// 容量必须是 2 的幂,这样可以用 & 代替 %
assert!(capacity.is_power_of_two());
let slots = (0..capacity)
.map(|_| std::cell::UnsafeCell::new(None))
.collect::<Vec<_>>()
.into_boxed_slice();
Self {
slots,
head: AtomicIsize::new(0),
tail: AtomicIsize::new(0),
mask: (capacity - 1) as isize,
capacity: capacity as isize,
}
}
fn index(&self, pos: isize) -> usize {
(pos as usize) & (self.mask as usize)
}
}容量必须是 2 的幂——这样就可以用位与代替取模。这是所有环形缓冲区的通用技巧。
本地 push:只有自己写
/// 只有 owner 调用,不需要任何原子操作(除了 tail 的发布)
pub fn push(&self, task: T) -> Result<(), T> {
let head = self.head.load(Ordering::Relaxed);
let tail = self.tail.load(Ordering::Relaxed);
if head - tail >= self.capacity {
return Err(task); // 满了
}
unsafe {
*self.slots[self.index(head)].get() = Some(task);
}
// Release:让窃取者能看到刚写入的内容
self.head.store(head + 1, Ordering::Release);
Ok(())
}注意 head 用 Relaxed 读、Release 写。 读的时候只有自己写,不用同步;写的时候要发布给窃取者,必须 Release。
本地 pop:从头部取
/// owner 从头部取任务
pub fn pop(&self) -> Option<T> {
let head = self.head.load(Ordering::Relaxed) - 1;
self.head.store(head, Ordering::Relaxed);
// 关键:写完之后要 fence,保证和窃取者的 CAS 有序
std::sync::atomic::fence(Ordering::SeqCst);
let tail = self.tail.load(Ordering::Relaxed);
if tail <= head {
// 队列非空,且不是"最后一个元素"
let task = unsafe { (*self.slots[self.index(head)].get()).take() };
return task;
}
if tail == head + 1 {
// 这是最后一个元素,可能正在被窃取者拿
return self.pop_last(head, tail);
}
// 队列空,把 head 恢复
self.head.store(head + 1, Ordering::Relaxed);
None
}
/// 处理"最后一个元素"的竞争
fn pop_last(&self, head: isize, _tail: isize) -> Option<T> {
// 尝试把 tail 推进一格,标记"这个位置被你占了"
let new_tail = head + 1;
if self.tail
.compare_exchange(new_tail, new_tail + 1, Ordering::SeqCst, Ordering::SeqCst)
.is_ok()
{
// CAS 成功:窃取者没抢到,这个元素归我
unsafe { (*self.slots[self.index(head)].get()).take() }
} else {
// CAS 失败:窃取者抢先了,队列已空
self.head.store(head + 1, Ordering::Relaxed);
None
}
}pop_last 就是 Chase-Lev deque 的精髓。 当只剩一个元素时,本地 pop 和窃取者可能同时想拿:
- 本地想"从头部取"
- 窃取者想"从尾部取"
- 但队里只有一个——它既是头也是尾
解法是让 tail 成为仲裁点:本地 pop 通过 CAS 争抢 tail 的所有权。抢到就归自己,抢输就说明被偷走了。
fence(SeqCst) 那一步不能省。 它的作用是保证"减小 head"和"读取 tail"之间有一个全序屏障——否则在某些架构上,窃取者可能看到旧的 tail 值而误判。
Chase-Lev deque 最反直觉的地方是:本地 pop 也需要 CAS,但只在"最后一个元素"时。 这是它比"全程加锁"快几个数量级的原因。
窃取:从尾部 CAS 抢
/// 任意线程调用,从尾部偷一个
pub fn steal(&self) -> Option<T> {
loop {
let tail = self.tail.load(Ordering::Acquire);
let head = self.head.load(Ordering::Acquire);
if tail >= head {
return None; // 空
}
let task = unsafe { (*self.slots[self.index(tail)].get()).take() };
// CAS:只有我能把这个尾位置"占掉"
if self.tail
.compare_exchange(tail, tail + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok()
{
return task;
}
// CAS 失败说明有人抢先了,重试
}
}Acquire 读 head 是必需的:如果看到 head 已经推进,就要能看到 owner 写入的任务内容(push 里用的是 Release,两者配对)。
把 worker 和 stealer 分离
有个 Rust 类型系统上的细节需要注意:pop 和 steal 不能同时持有同一个 Worker 的可变引用。
标准做法是把它们拆成两个类型:
pub struct Worker<T> {
inner: std::sync::Arc<Deque<T>>,
}
pub struct Stealer<T> {
inner: std::sync::Arc<Deque<T>>,
}
impl<T> Worker<T> {
/// 每个队列只能有一个 Worker
pub fn new(capacity: usize) -> (Worker<T>, Stealer<T>) {
let deque = std::sync::Arc::new(Deque::new(capacity));
(Worker { inner: deque.clone() }, Stealer { inner: deque })
}
}Stealer 是 Clone + Send + Sync 的,可以分发给其他线程;Worker 不实现 Clone,保证"每个队列只有一个本地所有者"。
这是"用类型系统表达并发约束"的典型例子——不用文档说"每个队列只能一个 owner",编译器直接保证。
调度器主循环
pub struct Scheduler {
workers: Vec<Worker<Job>>,
stealers: Vec<Stealer<Job>>,
}
impl Scheduler {
pub fn run(self, worker_id: usize) {
let worker = &self.workers[worker_id];
loop {
// 1. 先看自己的队列
if let Some(job) = worker.pop() {
job();
continue;
}
// 2. 自己空了,去做别的事(比如处理 IO、检查关闭信号)
if let Some(job) = self.poll_external() {
job();
continue;
}
// 3. 还是没有,去偷
let mut stolen = false;
for i in 0..self.stealers.len() {
let victim = (worker_id + i + 1) % self.stealers.len();
if let Some(job) = self.stealers[victim].steal() {
job();
stolen = true;
break;
}
}
// 4. 偷不到,短暂让出
if !stolen {
std::hint::spin_loop();
std::thread::yield_now();
}
}
}
}窃取的顺序:轮询而不是随机
上面用的是 (worker_id + i + 1) % n——从自己的下一个开始,依次轮询。
为什么不随机?因为局部性好。相邻的 worker 通常在同一个 NUMA 节点上,偷它们的任务,数据更可能还在缓存里。
窃取顺序的选择对大规模系统影响不小:
| 策略 | 优点 | 缺点 |
|---|---|---|
| 随机 | 简单,负载分散快 | 缓存局部性差 |
| 轮询(顺序) | 局部性好 | 可能导致"互相偷" |
| 优先偷"最忙的" | 平衡快 | 需要额外维护负载信息 |
Go runtime 用的是"随机起点 + 遍历",tokio 用的是 worker 之间的直接 steal 循环。 顺序遍历自己的邻居通常是更好的默认选择。
一个容易忽略的点:任务本地性
工作窃取有个隐含的假设:任务最好在被提交的那个 worker 上执行。
这带来的一个重要性质是"亲和性":如果任务 A 创建了任务 B,B 会被 push 到 A 所在 worker 的队列头部,下一次就优先执行。
这个性质对"任务树"特别有用:
任务 A 拆分成 B、C、D
├── B 执行完,可能会再拆出 B1、B2
└── 这些都在同一个 worker 的队列里,LIFO 顺序用 LIFO(后进先出,从头部取)而不是 FIFO,能保证"深度优先"的遍历顺序,从而让相关任务在同一个 worker 上连续执行,缓存友好。
这也是为什么工作窃取的本地端是"栈",窃取端是"队列"——本地 LIFO 保证局部性,窃取 FIFO 保证最早提交的任务先被执行。
背压与有界队列
前面实现里 push 返回 Result<(), T>,满了就失败。真实调度器怎么处理?
方案一:让 push 阻塞。 但阻塞会卡住整个 worker 线程,而在工作窃取里,worker 阻塞是灾难——它会让所有想偷它任务的线程也拿不到东西。
方案二:溢出到全局队列。 本地队列满了,把新任务放进共享的全局队列,由空闲 worker 去取。
pub fn spawn(&self, job: Job) {
// 1. 优先放本地
if self.local.push(job.clone()).is_ok() {
return;
}
// 2. 本地满,放全局
self.global_queue.lock().unwrap().push_back(job);
}方案三:让提交方感知背压。 返回失败,由调用方决定重试还是降级。这是最可控的做法,适合已有背压机制的系统。
关键原则:worker 线程本身永远不能因为队列满而阻塞。 因为工作窃取的调度依赖"其他 worker 主动来偷",一个卡住的 worker 会拖累整个池。
在工作窃取模型里,阻塞是"传染"的。 这也是为什么 tokio 明确区分了"异步任务"和"阻塞任务"(
spawn_blocking会放进完全独立的线程池)。
和全局队列的实测差异
用一个简单的对比来感受差距(8 核,每任务极短):
| 结构 | 吞吐 | 说明 |
|---|---|---|
Mutex<VecDeque> |
1× | 基准 |
| 分片(N 个 Mutex 队列) | 3-4× | 锁竞争降低 |
| 工作窃取 | 5-8× | 几乎无锁 |
差距的来源很明确:全局队列时,每次取任务都要经过一次 cache line 的争抢(锁变量所在的缓存行会在多个核之间来回弹跳)。工作窃取时,本地操作只碰自己的缓存行。
什么时候不该用工作窃取
工作窃取不是万能的:
1. 任务粒度太粗时没收益。 如果每个任务要跑 100ms,任务队列的同步开销占比微乎其微,全局队列完全够用。工作窃取是为"百万级/秒的细粒度任务"准备的。
2. 任务是 IO 密集时会被浪费。 工作窃取假设"任务都是 CPU 密集",被偷走的任务能在别的核上真正并行跑。如果任务是阻塞 IO,偷来也只是换个线程挂起——这时应该用异步 IO,而不是加更多线程。
3. 调试难度显著上升。 任务在哪执行变得不确定,任务顺序也不确定。追踪一个"偶发只在某台机器上出现"的任务顺序 bug,成本很高。
结论
工作窃取把"避免锁竞争"这个目标推到了极致:
每线程一个队列 → 本地操作无锁 → 只在空闲时跨线程偷 → 用两端分离(本地头、窃取尾)把冲突降到最低 → 用 Chase-Lev 的 CAS 处理"最后一个元素"的竞争。
它的三个设计要点值得记住:
- 本地 LIFO,窃取 FIFO:前者保证缓存局部性(深度优先),后者保证任务大致按提交顺序执行
- 本地 pop 只在"最后一个元素"时用 CAS:这是它无锁的前提
- worker 永远不能阻塞:否则会传染整个池
理解了这些,你再看 rayon 的 join、tokio 的 work-stealing runtime、Go 的 GMP 调度——它们都是在 Chase-Lev deque 这个底座上,各自加上了自己的任务类型和窃取策略。 下一篇我们看一个更底层的问题:如果没有操作系统线程的帮助,怎么在自己的用户态实现"协程"。