用 Rust 从零实现定时器:时间轮和最小堆各适合什么
几乎每个长连接服务里都藏着十万个定时任务:连接超时、心跳检测、订单关单、缓存过期。
管理这些任务的结构选错了,CPU 会有相当一部分花在"找下一个到期任务"上。这篇写两个最主流的方案:最小堆和时间轮,并说清楚它们各自适合什么。
先说结论:
| 结构 | 插入 | 取出最早到期 | 适合 |
|---|---|---|---|
| 最小堆 | O(log n) | O(log n) | 任务数量中等、到期时间分散 |
| 时间轮 | O(1) | O(1) | 任务多、时间粒度固定、大量任务集中在同一时刻 |
接口先定下来
不管底层怎么实现,对外就是三个动作:
pub trait Timer {
type Handle: Copy + Eq;
/// 注册一个 timeout 后触发的任务,返回可取消的句柄
fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> Self::Handle;
/// 取消一个还没触发的任务
fn cancel(&mut self, handle: Self::Handle) -> bool;
/// 取出所有已到期的任务并执行
fn tick(&mut self, now: Instant);
}cancel 是这个接口里最容易被忽略、也最关键的部分。 一个连接提前关闭了,它注册的超时任务必须能撤掉,否则就是内存泄漏。
版本一:最小堆
最小堆的思路:按到期时间排序,堆顶永远是最近要触发的那个。
Rust 的 BinaryHeap 是最大堆,用它做最小堆要反转比较:
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::time::{Duration, Instant};
struct Scheduled {
deadline: Instant,
seq: u64, // 打破同 deadline 的平局,保证 FIFO
id: u64,
task: Option<Box<dyn FnOnce() + Send>>,
cancelled: bool,
}
impl PartialEq for Scheduled {
fn eq(&self, other: &Self) -> bool { self.deadline == other.deadline && self.seq == other.seq }
}
impl Eq for Scheduled {}
impl Ord for Scheduled {
fn cmp(&self, other: &Self) -> Ordering {
// 反转:deadline 早的排前面;相同则 seq 小的靠前
other
.deadline
.cmp(&self.deadline)
.then_with(|| other.seq.cmp(&self.seq))
}
}
impl PartialOrd for Scheduled {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}为什么要有 seq?因为 Instant 可能相同(同一毫秒内注册多个),如果只比 deadline,堆的顺序不稳定,等于破坏了"先注册先触发"的直觉。
定时器主体:
pub struct HeapTimer {
heap: BinaryHeap<Scheduled>,
tasks: std::collections::HashMap<u64, ()>, // 记录有效 id,用于取消
next_id: u64,
seq: u64,
}
impl HeapTimer {
pub fn new() -> Self {
Self {
heap: BinaryHeap::new(),
tasks: Default::default(),
next_id: 0,
seq: 0,
}
}
pub fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> u64 {
let id = self.next_id;
self.next_id += 1;
self.seq += 1;
self.heap.push(Scheduled {
deadline: Instant::now() + timeout,
seq: self.seq,
id,
task: Some(task),
cancelled: false,
});
self.tasks.insert(id, ());
id
}
}tick 就是不断弹出堆顶,直到堆顶还没到期:
pub fn tick(&mut self, now: Instant) {
while let Some(top) = self.heap.peek() {
if top.deadline > now {
break; // 堆顶没到期,后面的更没到期
}
let mut item = self.heap.pop().unwrap();
self.tasks.remove(&item.id);
if !item.cancelled {
if let Some(task) = item.task.take() {
task();
}
}
}
}取消:惰性删除
BinaryHeap 没有办法"删除任意元素"(只能删堆顶)。所以要取消一个任务,标准做法是惰性删除:不真删,只打个标记,等它冒到堆顶时再丢掉。
pub fn cancel(&mut self, handle: u64) -> bool {
if self.tasks.remove(&handle).is_some() {
// 只从索引里移除;堆里的节点等 tick 时自然丢弃
return true;
}
false
}但上面的代码有个问题:cancelled 字段其实没被设置。真正的实现要么在 tasks 里存 Arc<AtomicBool>,要么让 cancel 扫描堆(O(n),不可接受)。
更干净的做法是用 Arc<AtomicBool>:
struct Scheduled {
deadline: Instant,
seq: u64,
task: Option<Box<dyn FnOnce() + Send>>,
cancelled: std::sync::Arc<std::sync::atomic::AtomicBool>,
} pub fn cancel(&mut self, handle: u64) -> bool {
if let Some(flag) = self.tasks.remove(&handle) {
flag.store(true, std::sync::atomic::Ordering::Release);
return true;
}
false
}惰性删除是无处不在的模式:主动删除代价高时,就先标记,等结构自然经过时再清理。 时间轮的取消也是同一个思路。
最小堆的问题在于:大量任务同时到期时,每次 tick 都要做 O(log n) 的堆调整。而且堆的内存是分散的,缓存不友好。
版本二:时间轮
时间轮的思路完全不同:不按时间排序,而是把任务放进"时间槽"里。
想象一个时钟的刻度盘,分成 N 个槽。每个槽代表一个时间窗口。指针每走一格就触发对应槽里的所有任务。
const SLOTS: usize = 512;
pub struct TimeWheel {
slots: Vec<Vec<Entry>>,
current: usize,
tick_duration: Duration,
last_tick: Instant,
}
struct Entry {
rounds: usize, // 还要转多少圈才触发
task: Box<dyn FnOnce() + Send>,
cancelled: std::sync::Arc<std::sync::atomic::AtomicBool>,
}注册任务时,算出它应该落在哪个槽、还要转几圈:
impl TimeWheel {
pub fn schedule(&mut self, timeout: Duration, task: Box<dyn FnOnce() + Send>) -> u64 {
let ticks = (timeout.as_nanos() / self.tick_duration.as_nanos()) as usize;
let slot = (self.current + ticks) % SLOTS;
let rounds = ticks / SLOTS;
let flag = std::sync::Arc::new(std::sync::atomic::AtomicBool::new(false));
self.slots[slot].push(Entry {
rounds,
task,
cancelled: flag.clone(),
});
// 返回句柄...
0
}
pub fn advance(&mut self, now: Instant) {
while now.duration_since(self.last_tick) >= self.tick_duration {
self.last_tick += self.tick_duration;
self.current = (self.current + 1) % SLOTS;
// 把当前槽里的任务取出来处理
let entries = std::mem::take(&mut self.slots[self.current]);
for mut entry in entries {
if entry.rounds > 0 {
// 还没到,放回同一个槽,圈数减一
entry.rounds -= 1;
self.slots[self.current].push(entry);
} else if !entry.cancelled.load(std::sync::atomic::Ordering::Acquire) {
(entry.task)();
}
}
}
}
}注意 rounds 的处理:这是单层时间轮能覆盖超过一圈时间范围的关键。一个 1 小时后触发的任务,放在 512 槽、每槽 1 秒的轮子里,"轮"是 512 秒,它要转 7 圈。
单层时间轮的问题是:时间精度和覆盖范围互相拉扯。要覆盖 1 天、精度 1 秒,就需要 86400 个槽。内存扛不住。
解法是分层时间轮(Hierarchical Timing Wheel):
秒轮: 60 槽,每槽 1 秒 -> 覆盖 1 分钟
分轮: 60 槽,每槽 1 分 -> 覆盖 1 小时
时轮: 24 槽,每槽 1 小时 -> 覆盖 1 天任务先放最细的轮。秒轮转完一圈,把"该进分轮"的任务降级进去;分轮转完一圈,再降级到时轮。这也是 Linux 内核定时器和 Kafka 的 TimerWheel 用的方案。
Kafka 的 Purgatory 就是分层时间轮:绝大多数请求的超时时间都是几秒到几十秒,集中在一个槽里,插入和触发都是 O(1),比堆快得多。 这是时间轮最大的胜利场景。
两者怎么选
任务数量少(< 1万)、时间分布散 -> 最小堆
任务数量大、超时时间集中在少数档位 -> 时间轮
需要精确到毫秒、且数量不大 -> 最小堆
需要覆盖从毫秒到天的范围 -> 分层时间轮还有一个现实角度:最小堆几乎不用自己写——BinaryHeap 就在标准库里,几十行能用。时间轮要自己处理槽、圈数、降级,代码量高一个量级。
所以我的经验是:先上最小堆,profile 发现 tick 成为热点,再换时间轮。
两个必须处理的工程细节
1. 定时器的驱动方式。 tick 谁来调?
- 专门一个线程
sleep到下一个到期时间,然后tick - 事件循环(epoll/kqueue)的 timeout 参数
- tokio 里是
tokio::time内部集成到 reactor 的
用独立线程最简单,但它引入了额外的线程和调度延迟。高精度场景要把它并进事件循环。
2. 时间回拨。 用 Instant 而不是 SystemTime,就是为了避开这个问题。Instant 是单调时钟,NTP 校时不会让它倒退。定时器里出现 SystemTime::now() 基本就是 bug。
结论
定时器的核心矛盾是"找下一个到期任务"的成本:
最小堆用 O(log n) 的代价维持有序,写起来便宜;时间轮用固定槽位把插入和触发都做成 O(1),代价是精度和范围的取舍;分层时间轮是两者之间的平衡点。
最后一个提醒:定时器代码最难的从来不是数据结构,而是取消路径。任务被取消、连接被关闭、服务要退出——这些路径有没有正确清理注册的任务,决定了服务能不能长期稳定运行。