几乎每个长连接服务里都藏着十万个定时任务：连接超时、心跳检测、订单关单、缓存过期。
如果底层结构选得不对，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>,
}
对应的 cancel 实现：
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) 的堆调整。而且堆的内存分布比较分散，对 CPU 缓存不友好。
版本二：时间轮
时间轮的思路完全不同：不按到期时间排序，而是把任务放进"时间槽"里。
可以把它想象成一个时钟的刻度盘，分成 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)，代价是精度和范围的取舍；分层时间轮是两者之间的平衡点。
最后一个提醒：定时器代码最难的从来不是数据结构，而是取消路径。任务被取消、连接被关闭、服务要退出——这些路径有没有正确清理注册的任务，决定了服务能不能长期稳定运行。如果你在实现中遇到具体问题，也欢迎到 云栈社区 一起交流。
发表于 前天 13:05
|
查看: 10|
回复: 0
