深入 Tokio 的 work-stealing 调度器任务窃取算法与 CPU 缓存的亲和性分析一、性能火焰图中Tokio 的任务窃取开销占了总 CPU 的 8%在对一个高频 RPC 框架进行 perf 分析时。火焰图中的tokio::runtime::scheduler::multi_thread::worker::try_steal_task调用栈引起了注意。这个函数在 CPU 上的开销占到了 8%。对于一个调度器的基础设施来说。这个占比偏高。追踪发现问题在于过度的任务窃取。某些 worker 线程频繁地从其他 worker 的本地队列中窃取任务。而这些窃取来的任务的数据布局与当前 CPU 缓存不匹配。每次窃取都伴随着缓存失效。本来是为负载均衡而设计的窃取机制。反而因为缓存亲和性破坏而拖累了整体性能。需要深入理解 Tokio 的 work-stealing 算法的内部机制。特别是窃取策略与 CPU 缓存之间的交互关系。才能找到优化的正确方向。二、Tokio 调度器的注入器、本地队列与全局队列三层架构Tokio 多线程调度器的核心结构分为三层注入队列Inject Queue、每 worker 的本地队列、以及 worker 之间的窃取机制。graph TD subgraph 调度器三层架构 A[外部提交 spawn()] -- B[注入队列 Inject Queuebr/全局、MPMC] B -- C1[Worker 0br/本地队列 LIFO] B -- C2[Worker 1br/本地队列 LIFO] B -- C3[Worker 2br/本地队列 LIFO] B -- C4[Worker Nbr/本地队列 LIFO] C1 -.-|work-stealing FIFO| C2 C2 -.-|work-stealing FIFO| C3 C3 -.-|work-stealing FIFO| C4 C4 -.-|work-stealing FIFO| C1 end subgraph 任务生命周期 D1[spawn(task)] -- D2[Inject Queue 入队] D2 -- D3[Worker 从 Inject Queue 取一批任务] D3 -- D4[推入本地队列后半部分] D3 -- D5[Worker 处理队列前半部分] end subgraph 窃取策略 E1[Worker 本地队列为空] E1 -- E2[尝试从 Inject Queue 获取] E2 --|为空| E3[尝试从其他 Worker 窃取] E3 -- E4[随机选择目标 Worker] E4 -- E5[从目标本地队列尾部偷取FIFO] E5 -- E6[窃取 128 个任务中的一半61 个] end核心设计要点。Worker 自己的本地队列使用 LIFO后进先出策略。这最大化了缓存亲和性——刚刚产生的任务及其数据很可能还在 CPU 缓存中。窃取时使用 FIFO先进先出策略。从目标 worker 的本地队列头部取任务而不是尾部。这样既能窃取到任务又最小化对被窃取 worker 的干扰。因为取走的是最老的任务。这些任务大概率已经不在 CPU 缓存中。每次窃取不是取一个任务。而是一次取走目标 worker 本地队列的一半最多 61 个单 Worker 队列容量为 256。批量窃取减少了跨 worker 的同步次数。摊销了窃取操作的固定开销。三、调度器行为与缓存亲和性分析/// 模拟 Tokio 调度器核心结构的简化实现 /// 用于展示任务窃取算法与缓存亲和性的关系 use std::cell::UnsafeCell; use std::sync::Arc; use std::sync::atomic::{AtomicUsize, Ordering}; /// Worker 的本地任务队列 /// /// 为什么用 UnsafeCell 而非 Mutex /// - 本地队列主要被当前 worker 访问LIFO push/pop /// - 仅在窃取时才被其他 worker 访问FIFO steal /// - Mutex 的开销在无竞争场景下仍然存在Atomic 操作 /// - 使用无锁设计可以消除这些开销 struct LocalQueueT { /// 环形缓冲区容量为 2^N buffer: Box[UnsafeCellOptionT], /// 头部索引窃取者从这里取FIFO head: AtomicUsize, /// 尾部索引所有者从这里放入LIFO tail: AtomicUsize, /// 掩码用于快速取模容量为 2 的幂时 mask % capacity mask: usize, } implT LocalQueueT { /// 本地 push当前 worker 使用 /// 操作 tailLIFO 顺序 fn push_local(self, task: T) - Result(), T { let tail self.tail.load(Ordering::Relaxed); let head self.head.load(Ordering::Acquire); let next_tail tail.wrapping_add(1); // 队列满 if next_tail.wrapping_sub(head) self.mask { return Err(task); } // 写入新任务仅当前 worker 在此位置写入 unsafe { (*self.buffer[tail self.mask].get()) Some(task); } // 需要确保写入在 tail 更新之前完成 self.tail.store(next_tail, Ordering::Release); Ok(()) } /// 本地 pop当前 worker 使用 /// 操作 tail-1LIFO 顺序最大缓存亲和性 fn pop_local(self) - OptionT { let tail self.tail.load(Ordering::Relaxed); if tail self.head.load(Ordering::Acquire) { return None; // 队列空 } let prev_tail tail.wrapping_sub(1); self.tail.store(prev_tail, Ordering::Release); let idx prev_tail self.mask; let task unsafe { (*self.buffer[idx].get()).take() }; // 为什么 LIFO 有更好的缓存亲和性 // 任务的产生顺序通常是Task A 产生 Task B // B 更可能使用 A 的输出数据这些数据仍在 CPU 缓存中 // LIFO 保证 B 在 A 之前执行 → 更好的缓存命中率 task } /// 远程窃取其他 worker 使用 /// 操作 headFIFO 顺序 fn steal(self) - OptionT { let head self.head.load(Ordering::Acquire); let tail self.tail.load(Ordering::Acquire); if head tail { return None; // 队列空 } let idx head self.mask; // 注意窃取者在 head 位置读取这是最老的任务 let task unsafe { (*self.buffer[idx].get()).take() }; // CAS 确保窃取的原子性 // 如果多个窃取者同时尝试从同一个 worker 偷取 // 只有一个能成功更新 head match self.head.compare_exchange( head, head.wrapping_add(1), Ordering::Release, Ordering::Relaxed, ) { Ok(_) task, Err(_) None, // 被其他窃取者抢先 } } } /// 模拟的 Worker 结构 struct WorkerT { /// 本地队列 local_queue: LocalQueueT, /// 全局注入队列的引用 inject_queue: Arccrossbeam_queue::SegQueueT, /// Worker 索引用于随机窃取时的目标选择 index: usize, } implT: Send static WorkerT { /// 调度循环的简化实现 fn run(self) { loop { // 步骤一优先从本地队列取任务LIFO缓存友好 if let Some(task) self.local_queue.pop_local() { // 直接执行数据大概率在 L1/L2 缓存中 self.execute(task); continue; } // 步骤二本地队列空尝试从全局注入队列取 if let Some(task) self.inject_queue.pop() { // 从注入队列取到的任务缓存可能已失效 // 这是因为任务被放入注入队列是在另一个 core 上 self.execute(task); continue; } // 步骤三尝试从其他 Worker 窃取 // 随机选择一个 worker 作为窃取目标 // 随机选择的目的是避免多个空闲 worker 同时窃取同一个目标 if let Some(task) self.try_steal() { self.execute(task); continue; } // 步骤四所有队列都空进入休眠 // 在实际 Tokio 中这里会 park 当前线程 // 等待有新的任务被提交时被唤醒 std::thread::park(); } } fn try_steal(self) - OptionT { // 简化随机尝试一个 worker // 实际 Tokio 使用随机起始索引 轮询的方式 None } fn execute(self, task: T) { // 执行任务 let _ task; } }窃取策略与缓存亲和性的核心矛盾在于。从其他 worker 偷来的任务其关联数据大概率不在当前 CPU 的 L1/L2 缓存中。处理这些任务时会发生缓存失效Cache Miss。这就是为什么窃取开销占了 8% 的原因。不仅仅是窃取操作本身的同步开销。更包括窃取后执行任务时的缓存失效代价。优化方向有两类。第一是减少窃取的发生。通过调整 Inject Queue 到本地队列的分配量。避免 worker 频繁耗尽本地队列。第二是在窃取时尽可能地保持局部性。窃取时间上相邻的任务减少跨缓存行的访问。四、调度器调优的适用条件与建议Tokio 调度器的默认配置适合通用场景。但特定负载下需要调优。首先如果应用的任务粒度非常细微秒级。窃取的开销相对占比增大。应增大event_interval参数。让 worker 在检查全局队列和窃取之前。先处理本地队列中的更多任务。减少窃取频率。其次如果任务之间有强依赖关系父任务 spawn 子任务。使用 LIFO 的本地队列效果最好。子任务大概率访问父任务产生在缓存中的数据。不要设置global_queue_interval过小。否则任务会被过早推入注入队列。第三对于 IO 密集型服务。worker 频繁处于等待状态。窃取发生的概率较低。调度器的默认配置即可。不需要额外调优。最后是 CPU 亲和性的显式绑定。Tokio 本身不管理线程到 CPU 核心的绑定。需要上层使用core_affinitycrate 来做。将 Tokio worker 绑定到固定的 CPU 核心上。减少 OS 调度器的迁移。五、总结Tokio 的 work-stealing 调度器通过三层架构注入队列、本地 LIFO 队列、FIFO 窃取平衡负载均衡与缓存亲和性。本地队列的 LIFO 策略利用了任务间的时间局部性。刚产生的任务数据大概率在 CPU 缓存中。窃取的 FIFO 策略取走最老的任务。这些任务数据大概率已经不在缓存中。减少了窃取对缓存亲和性的破坏。窃取开销不仅仅是同步操作本身的成本。更包括执行窃取任务时的缓存失效代价。对于任务粒度细、依赖关系强的负载。增大event_interval减少窃取频率。可以降低调度开销占比。