时间轮(Timing Wheel)

定义

时间轮(Timing Wheel)由 Varghese 和 Lauck 于 1987 年的论文提出,是管理大量定时器的经典结构:一个环形槽数组配合一个随时钟前进的指针,每个槽挂一条到期任务链表,任务按"到期时间对轮长取模"放入对应槽位。

原理

指针每个 tick 前进一格,处理当前槽中到期的任务,插入和取消定时器都是 O(1) 的链表操作。超出一轮范围的任务有两种处理:记录剩余圈数,指针扫到时圈数减一;或采用层级时间轮(hierarchical timing wheel),类似钟表的秒轮、分轮、时轮,高层轮的任务到期后降级重新散列到低层轮,以少量槽位覆盖很长的时间跨度。

应用

Linux 内核的传统定时器机制基于时间轮;Netty 的 HashedWheelTimer、Kafka 的延迟操作(purgatory)、XXL-JOB 等调度系统,以及各类连接超时管理、心跳检测都采用时间轮,替代按到期时间排序的堆(堆的插入删除为 O(log n))。

优缺点

优点是插入删除 O(1)、吞吐高;缺点是精度受 tick 粒度限制,空转时指针仍需推进,层级设计增加实现复杂度。