一、优先队列定时器的瓶颈在哪?
如果你的系统有百万级定时器(比如网络服务器有 100 万个连接,每个连接保活定时器 60s),优先队列的 $O(\log N)$ 插入可能成为瓶颈。
时间轮把插入降到 $O(1)$。
二、简单时间轮
一个简单的单层时间轮(假设精度 1 秒,共 8 个槽):
槽 0: [任务A(8s后)] ← 指针 current
槽 1: []
槽 2: [任务B(2s后)]
槽 3: []
槽 4: []
槽 5: [任务C(5s后)]
槽 6: []
槽 7: []
指针每秒转动一格:
current=0 → 执行槽0里的任务
current=1 → 执行槽1里的任务
...
插入任务时:计算 expiry = now + delay
槽位 = (current + delay) % 8
直接放入对应槽 → O(1)
三、分层时间轮
单层时间轮的槽数 = 最大延迟。如果需要 1 小时半的定时器,单层需要 3600 个槽。分层时间轮用多层来解决:
分层时间轮(类比钟表):
秒针轮:60 槽,每槽 1 秒,一圈 60 秒
分针轮:60 槽,每槽 1 分,一圈 60 分
时针轮:12 槽,每槽 1 时,一圈 12 时
添加一个 70 秒的定时器:
→ 先放入秒针轮的 10 秒位置(70-60=10,因为第一圈到不了)
→ 秒针轮转一圈时,把这个任务降级到"分钟轮的第 1 分钟"
→ 分针走到第 1 个槽时,把它重新放入秒针轮的 10 秒位置
→ 秒针走到第 10 秒时,执行
性能对比:
| 操作 | 优先队列 | 时间轮 |
|---|---|---|
| 添加定时器 | $O(\log N)$ | $O(1)$ |
| 到期检查 | $O(1)$(看堆顶) | $O(1)$(当前槽) |
| 取消 | $O(\log N)$(需要惰性删除) | $O(1)$(惰性标记) |
| 精度 | 高(任意时间) | 有限(槽大小决定精度) |
Netty、Nginx、Linux 内核的定时器都用的是时间轮,因为网络服务有大量连接,每个连接有定时器。插入 $O(1)$ 比 $O(\log N)$ 重要。