时间轮Timing wheel
按时间槽组织定时事件，指针随时钟推进处理到期槽。
- 核心约束
- 事件按截止时间映射到槽；多层或轮次信息区分远期事件。
- 适用问题
- 大量普通超时、可接受时间粒度的定时任务。
- 边界与取舍
- 时间精度、层级迁移、长暂停和单槽拥挤影响成本。
常见操作#
n 为待处理计时器数，W 为槽数，H 为轮层数，k 为本次到期或迁移的计时器数。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 单层轮插入 | 到期时间能映射到目标槽，未要求槽内排序；超出覆盖周期需另作处理。 | |
| 取消已知计时器 | 计时器保存可摘除的链表节点或等价句柄；若需在槽内找目标，则与槽长有关。 | |
| 层级轮插入 | 查找合适层级；固定层数的实现可视作常数成本。 | |
| 推进一个 tick | 单层 / 固定层数 ；一般层级检查 | k 包括本次处理或迁移的条目；跨越层级边界还可能检查 H 层，定时器回调自身运行时间另计。 |
| 遍历 / 清理全部计时器 | 逐层扫描槽和链接；具体结构可跳过空槽。 |
时间与空间#
- 时间复杂度
- 插入 / 取消可为 ，到期批次成本不可忽略
- 存储空间
分辨率、覆盖时长、层级迁移和集中到期决定延迟；时间轮不承诺每个 tick 总工作恒定。
工程中的应用#
1 个案例 · 附源码Linux 普通定时器把较近超时放进细粒度槽，远期超时放进粗粒度槽，使用位图寻找待处理槽。v6.12 的这套时间轮不再逐层级联迁移。
附源码片段 · 调度与资源分配
基础原理参考资料
Varghese & Lauck · Hashed and Hierarchical Timing Wheels比较简单、哈希与层级时间轮的启动、停止和推进成本。