Tokio 的定时器实现原理时间轮算法与 HashedWheelTimer 的精度与性能权衡一、生产环境的定时器噩梦10 万个并发定时器如何不拖垮事件循环一个连接池管理系统为每个 TCP 连接设置 30 秒空闲超时10 万个连接意味着 10 万个定时器。最朴素的实现——将所有定时器放入二叉堆——每次 tick 的检查复杂度为 O(1) 获取最近到期、O(log n) 插入。但 10 万连接的插入频率高达每秒数千次堆操作的开销已不可忽视。更糟的是二叉堆不能高效地批量处理到期定时器。如果短时间内积累了 5000 个到期定时器逐个从堆顶弹出 O(log n)总复杂度 O(5000 × log 100000) ≈ 83000 次比较。时间轮的批量处理则只需 O(1) 遍历当前槽位的链表。Tokio 的定时器实现采用了层级时间轮Hashed Wheel Timer将不同的时间粒度分布到多层轮盘上。第一层覆盖 01 秒毫秒精度第二层 164 秒第三层 64~4096 秒。定时器在插入时计算所属层级和槽位到期时只需检查当前指针所在的槽位链表。二、层级时间轮的数据结构与调度时序定时器插入的算法若超时 64ms第一层覆盖范围放入第一层对应槽位若 64ms 超时 4096ms放入第二层并在第二层指针到达该槽位时降级到第一层若超时 4096ms放入第三层逐级降级降级Cascade是层级时间轮的核心操作当上层指针移动到一个槽位时该槽位中的所有定时器被重新计算剩余时间移入下层对应的槽位。这个分摊成本很低——每个定时器平均被降级 1~2 次就到期了。Tick 操作每次毫秒推进:第一层指针前进一格若指针回到 0一轮完成第二层指针前进一格并触发降级同理第二层指针回到 0 时第三层推进三、Rust 中时间轮的实现要点use std::collections::VecDeque; use std::sync::Arc; use std::time::{Duration, Instant}; use tokio::sync::Notify; /// 定时器条目 struct TimerEntry { /// 到期时间绝对时间 deadline: Instant, /// 回调通知实际使用 Waker notify: ArcNotify, /// 是否已取消 cancelled: bool, } /// 时间轮槽位链表持有定时器条目 type TimerSlot VecArcstd::sync::MutexTimerEntry; /// 单层时间轮 struct WheelLevel { /// 槽位数组 slots: VecTimerSlot, /// 当前指针位置 cursor: usize, /// 每个槽位的时间跨度 tick_duration: Duration, } /// 三层时间轮 struct HashedWheelTimer { /// 第一层毫秒精度64 槽 × 1ms 64ms 覆盖 level1: WheelLevel, /// 第二层64ms 精度64 槽 × 64ms 4096ms 覆盖 level2: WheelLevel, /// 第三层4096ms 精度64 槽 × 4096ms 262s 覆盖 level3: WheelLevel, /// 启动时间用于计算相对时间 start_time: Instant, /// 总定时器计数 total_timers: std::sync::atomic::AtomicUsize, } impl HashedWheelTimer { fn new() - Self { HashedWheelTimer { level1: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(1), }, level2: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(64), }, level3: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(4096), }, start_time: Instant::now(), total_timers: std::sync::atomic::AtomicUsize::new(0), } } /// 调度一个定时器 fn schedule(mut self, delay: Duration, notify: ArcNotify) { let deadline Instant::now() delay; let entry Arc::new(std::sync::Mutex::new(TimerEntry { deadline, notify, cancelled: false, })); let delay_ms delay.as_millis() as u64; // 选择层级和槽位 if delay_ms 64 { // 第一层毫秒精度 let idx (self.level1.cursor delay_ms as usize) % 64; self.level1.slots[idx].push(entry); } else if delay_ms 4096 { // 第二层需计算 (delay / 64ms) 映射到槽位 let ticks (delay_ms / 64) as usize; let idx (self.level2.cursor ticks) % 64; self.level2.slots[idx].push(entry); } else if delay_ms 262_144 { // 第三层 let ticks (delay_ms / 4096) as usize; let idx (self.level3.cursor ticks) % 64; self.level3.slots[idx].push(entry); } else { // 超出最大范围262 秒直接放入第三层最后槽位 self.level3.slots[63].push(entry); } self.total_timers.fetch_add(1, std::sync::atomic::Ordering::Relaxed); } /// Tick推进时间轮一格1ms /// 返回到期的定时器列表 fn tick(mut self) - VecArcNotify { let mut expired Vec::new(); // 第一层永远推进 self.level1.cursor (self.level1.cursor 1) % 64; // 处理第一层当前槽位的到期定时器 let now Instant::now(); let slot mut self.level1.slots[self.level1.cursor]; slot.retain(|entry| { let mut e entry.lock().unwrap(); if e.cancelled { return false; // 移除已取消的 } if e.deadline now { expired.push(e.notify.clone()); false // 移出槽位 } else { true // 保留 } }); // 第一层完成一轮 → 第二层推进 if self.level1.cursor 0 { self.cascade_level2(mut expired); } expired } /// 第二层推进 降级到第一层 fn cascade_level2(mut self, expired: mut VecArcNotify) { self.level2.cursor (self.level2.cursor 1) % 64; // 取出当前槽位的所有定时器重新分配到第一层 let slot std::mem::replace( mut self.level2.slots[self.level2.cursor], Vec::new(), ); let now Instant::now(); for entry in slot { let e entry.lock().unwrap(); if e.cancelled { continue; } // 计算剩余时间放入第一层 if e.deadline now Duration::from_millis(1) { // 即将到期直接触发 expired.push(e.notify.clone()); } else { let remaining e.deadline.duration_since(now); let ms remaining.as_millis() as usize; let idx (self.level1.cursor ms) % 64; drop(e); self.level1.slots[idx].push(entry); } } // 第二层完成一轮 → 第三层推进同理略 } /// 取消定时器 fn cancel(self, notify: ArcNotify) { // 通过 notify 指针在所有层级中查找并标记取消 // 实际实现使用 HashMap 做 O(1) 查找 // 此处简化 } }槽位数选择 64 是基于 CPU 缓存行的考虑——64 个指针恰好占用一个缓存行64 × 8 512 字节即 8 个缓存行在 x86_64 上。指针推进操作频繁访问当前槽位将其保持在 L1 缓存中至关重要。total_timers使用Relaxed排序而非SeqCst因为定时器计数仅用于监控不参与同步决策。这节省了不必要的内存屏障开销在 x86 上RelaxedvsSeqCst差距约 4 倍延迟。四、时间轮的精度损失与适用边界精度损失分析第一层槽位粒度 1ms实际到期误差 ≤ 1ms降级操作发生在槽位边界每 64ms 一次降级中的定时器延迟额外 ≤ 1ms总精度损失 ≤ 2ms对于超时场景可接受不适合的定时场景高精度定时需求如音频采样同步需要 μs 级精度绝对的单调时间语义时间轮依赖系统时钟NTP 跳变会影响精度性能数据10 万定时器插入Amortized O(1)约 50ns/次Tick 操作O(1 k)k 为当前槽位的到期定时器数对比二叉堆插入 O(log n) ≈ 800ns/次10 万节点五、总结时间轮将定时器按超时长度分布到多层槽位中插入和 tick 都是摊销 O(1) 复杂度适合 10 万级别的大量定时器场景。层级设计64 槽 × 3 层覆盖 0~262 秒毫秒轮 1ms 精度秒轮 64ms 精度分级轮 4s 精度通过级联降级将长超时定时器逐层转移。降级的摊销成本极低——每个定时器平均降级 1~2 次就到期相比二叉堆的每 tick O(log n) 弹出具备显著性能优势。时间轮的精度损失 ≤ 2ms槽位粒度 降级延迟对网络超时、会话管理场景完全可接受。Tokio 的时间轮使用Relaxed排序优化热点路径64 槽设计对齐 CPU 缓存行最大化 L1 命中率。
Tokio 的定时器实现原理：时间轮算法与 HashedWheelTimer 的精度与性能权衡
Tokio 的定时器实现原理时间轮算法与 HashedWheelTimer 的精度与性能权衡一、生产环境的定时器噩梦10 万个并发定时器如何不拖垮事件循环一个连接池管理系统为每个 TCP 连接设置 30 秒空闲超时10 万个连接意味着 10 万个定时器。最朴素的实现——将所有定时器放入二叉堆——每次 tick 的检查复杂度为 O(1) 获取最近到期、O(log n) 插入。但 10 万连接的插入频率高达每秒数千次堆操作的开销已不可忽视。更糟的是二叉堆不能高效地批量处理到期定时器。如果短时间内积累了 5000 个到期定时器逐个从堆顶弹出 O(log n)总复杂度 O(5000 × log 100000) ≈ 83000 次比较。时间轮的批量处理则只需 O(1) 遍历当前槽位的链表。Tokio 的定时器实现采用了层级时间轮Hashed Wheel Timer将不同的时间粒度分布到多层轮盘上。第一层覆盖 01 秒毫秒精度第二层 164 秒第三层 64~4096 秒。定时器在插入时计算所属层级和槽位到期时只需检查当前指针所在的槽位链表。二、层级时间轮的数据结构与调度时序定时器插入的算法若超时 64ms第一层覆盖范围放入第一层对应槽位若 64ms 超时 4096ms放入第二层并在第二层指针到达该槽位时降级到第一层若超时 4096ms放入第三层逐级降级降级Cascade是层级时间轮的核心操作当上层指针移动到一个槽位时该槽位中的所有定时器被重新计算剩余时间移入下层对应的槽位。这个分摊成本很低——每个定时器平均被降级 1~2 次就到期了。Tick 操作每次毫秒推进:第一层指针前进一格若指针回到 0一轮完成第二层指针前进一格并触发降级同理第二层指针回到 0 时第三层推进三、Rust 中时间轮的实现要点use std::collections::VecDeque; use std::sync::Arc; use std::time::{Duration, Instant}; use tokio::sync::Notify; /// 定时器条目 struct TimerEntry { /// 到期时间绝对时间 deadline: Instant, /// 回调通知实际使用 Waker notify: ArcNotify, /// 是否已取消 cancelled: bool, } /// 时间轮槽位链表持有定时器条目 type TimerSlot VecArcstd::sync::MutexTimerEntry; /// 单层时间轮 struct WheelLevel { /// 槽位数组 slots: VecTimerSlot, /// 当前指针位置 cursor: usize, /// 每个槽位的时间跨度 tick_duration: Duration, } /// 三层时间轮 struct HashedWheelTimer { /// 第一层毫秒精度64 槽 × 1ms 64ms 覆盖 level1: WheelLevel, /// 第二层64ms 精度64 槽 × 64ms 4096ms 覆盖 level2: WheelLevel, /// 第三层4096ms 精度64 槽 × 4096ms 262s 覆盖 level3: WheelLevel, /// 启动时间用于计算相对时间 start_time: Instant, /// 总定时器计数 total_timers: std::sync::atomic::AtomicUsize, } impl HashedWheelTimer { fn new() - Self { HashedWheelTimer { level1: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(1), }, level2: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(64), }, level3: WheelLevel { slots: (0..64).map(|_| Vec::new()).collect(), cursor: 0, tick_duration: Duration::from_millis(4096), }, start_time: Instant::now(), total_timers: std::sync::atomic::AtomicUsize::new(0), } } /// 调度一个定时器 fn schedule(mut self, delay: Duration, notify: ArcNotify) { let deadline Instant::now() delay; let entry Arc::new(std::sync::Mutex::new(TimerEntry { deadline, notify, cancelled: false, })); let delay_ms delay.as_millis() as u64; // 选择层级和槽位 if delay_ms 64 { // 第一层毫秒精度 let idx (self.level1.cursor delay_ms as usize) % 64; self.level1.slots[idx].push(entry); } else if delay_ms 4096 { // 第二层需计算 (delay / 64ms) 映射到槽位 let ticks (delay_ms / 64) as usize; let idx (self.level2.cursor ticks) % 64; self.level2.slots[idx].push(entry); } else if delay_ms 262_144 { // 第三层 let ticks (delay_ms / 4096) as usize; let idx (self.level3.cursor ticks) % 64; self.level3.slots[idx].push(entry); } else { // 超出最大范围262 秒直接放入第三层最后槽位 self.level3.slots[63].push(entry); } self.total_timers.fetch_add(1, std::sync::atomic::Ordering::Relaxed); } /// Tick推进时间轮一格1ms /// 返回到期的定时器列表 fn tick(mut self) - VecArcNotify { let mut expired Vec::new(); // 第一层永远推进 self.level1.cursor (self.level1.cursor 1) % 64; // 处理第一层当前槽位的到期定时器 let now Instant::now(); let slot mut self.level1.slots[self.level1.cursor]; slot.retain(|entry| { let mut e entry.lock().unwrap(); if e.cancelled { return false; // 移除已取消的 } if e.deadline now { expired.push(e.notify.clone()); false // 移出槽位 } else { true // 保留 } }); // 第一层完成一轮 → 第二层推进 if self.level1.cursor 0 { self.cascade_level2(mut expired); } expired } /// 第二层推进 降级到第一层 fn cascade_level2(mut self, expired: mut VecArcNotify) { self.level2.cursor (self.level2.cursor 1) % 64; // 取出当前槽位的所有定时器重新分配到第一层 let slot std::mem::replace( mut self.level2.slots[self.level2.cursor], Vec::new(), ); let now Instant::now(); for entry in slot { let e entry.lock().unwrap(); if e.cancelled { continue; } // 计算剩余时间放入第一层 if e.deadline now Duration::from_millis(1) { // 即将到期直接触发 expired.push(e.notify.clone()); } else { let remaining e.deadline.duration_since(now); let ms remaining.as_millis() as usize; let idx (self.level1.cursor ms) % 64; drop(e); self.level1.slots[idx].push(entry); } } // 第二层完成一轮 → 第三层推进同理略 } /// 取消定时器 fn cancel(self, notify: ArcNotify) { // 通过 notify 指针在所有层级中查找并标记取消 // 实际实现使用 HashMap 做 O(1) 查找 // 此处简化 } }槽位数选择 64 是基于 CPU 缓存行的考虑——64 个指针恰好占用一个缓存行64 × 8 512 字节即 8 个缓存行在 x86_64 上。指针推进操作频繁访问当前槽位将其保持在 L1 缓存中至关重要。total_timers使用Relaxed排序而非SeqCst因为定时器计数仅用于监控不参与同步决策。这节省了不必要的内存屏障开销在 x86 上RelaxedvsSeqCst差距约 4 倍延迟。四、时间轮的精度损失与适用边界精度损失分析第一层槽位粒度 1ms实际到期误差 ≤ 1ms降级操作发生在槽位边界每 64ms 一次降级中的定时器延迟额外 ≤ 1ms总精度损失 ≤ 2ms对于超时场景可接受不适合的定时场景高精度定时需求如音频采样同步需要 μs 级精度绝对的单调时间语义时间轮依赖系统时钟NTP 跳变会影响精度性能数据10 万定时器插入Amortized O(1)约 50ns/次Tick 操作O(1 k)k 为当前槽位的到期定时器数对比二叉堆插入 O(log n) ≈ 800ns/次10 万节点五、总结时间轮将定时器按超时长度分布到多层槽位中插入和 tick 都是摊销 O(1) 复杂度适合 10 万级别的大量定时器场景。层级设计64 槽 × 3 层覆盖 0~262 秒毫秒轮 1ms 精度秒轮 64ms 精度分级轮 4s 精度通过级联降级将长超时定时器逐层转移。降级的摊销成本极低——每个定时器平均降级 1~2 次就到期相比二叉堆的每 tick O(log n) 弹出具备显著性能优势。时间轮的精度损失 ≤ 2ms槽位粒度 降级延迟对网络超时、会话管理场景完全可接受。Tokio 的时间轮使用Relaxed排序优化热点路径64 槽设计对齐 CPU 缓存行最大化 L1 命中率。
