文档目录

一、优先队列定时器的瓶颈在哪?

如果你的系统有百万级定时器(比如网络服务器有 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)$ 重要。