single · hierarchical · ring buffer

时间轮 Timing Wheel

管理成千上万个定时器，朴素做法（有序链表、最小堆）的添加与删除是 $O(n)$ 或 $O(\log n)$ 。时间轮 (timing wheel) 把这两个操作压到 $O(1)$ ：一个环形数组，每格 (slot) 代表一个时间刻度 tick、挂一条到期定时器的链表 (bucket)，一根指针随真实时间每 tick 前进一格，只处理当前格——结构与钟表表盘同构。

需要澄清的是： $O(1)$ 说的是对它做添加、删除、触发这几类操作的复杂度，不是「数据结构本身」的复杂度——复杂度永远是操作的属性。时间轮借了这三个操作的 $O(1)$ 给自己贴标签，底层机件则是环形缓冲区 (ring buffer)：固定数组加取模回绕的指针。

1 · 单层时间轮的三样机件

核心机件只有三样：一个环形数组，每格代表一个时间刻度 tick；每格挂一条 bucket，即到期定时器的链表；一根指针随真实时间每 tick 前进一格，到头绕回 0。添加一个延迟 delay 的定时器，只需算出落点槽位 (pointer + delay) % slots、挂进那一格， $O(1)$ ；推进时指针走一格，只处理当前格里到期的定时器，不扫描其余格子。延迟超过一圈（ $delay \ge slots$ ）的定时器，靠 rounds（还要绕几圈）留在同一槽。

图 1-1 · 单层轮的添加与推进。可自定延迟添加定时器，单步推进指针，观察 bucket 增删与代码逐行高亮。

1.1 · rounds 的代价

设 slots = 8，添加一个 delay = 20 的定时器：落点槽位是 (pointer + 20) % 8，即第 4 格，而 $rounds = \lfloor (20-1)/8 \rfloor = 2$ ——指针要两次经过该槽（每次把 rounds 减一）才在第三次触发。减一那个偏移不能省：delay = 8 时 $\lfloor 7/8 \rfloor = 0$ ，指针第一次绕回原槽就该触发，写成 $\lfloor 8/8 \rfloor$ 会白等一圈。

rounds 让单层轮能表示任意远的延迟，但代价藏在 tick 里：每次推进都要遍历当前整槽给计数减一，于是触发不再是干净的 $O(1)$ ，而退化为「当前槽元素数」量级。

警示 · 这正是单层轮的关键局限。要表示「最长 $N$ 个 tick」的延迟，单层轮要么让 rounds 退化 tick，要么把格数铺到 $N$ 个，而绝大多数格子永远为空。分层时间轮用「钟表的时、分、秒三个盘」化解：远期定时器先挂粗粒度高层，临近触发才 cascade 降级到细粒度低层——几百个格子覆盖极大范围，且全程 $O(1)$ 摊还。

注 · 删除同样是 $O(1)$ ：每个 slot 的 bucket 是一条链表，持有定时器节点时直接摘除即可，与定时器总数 $n$ 无关。本页为聚焦核心，只演示添加与触发，删除的链表摘除见链表系列。

2 · 分层时间轮与 cascade

设精度 1ms、范围 1 天，单层轮就得开 86400000 个格子。分层时间轮像钟表的时、分、秒三个盘：每升一层，一格的跨度乘以 slots。远期定时器先挂粗粒度的高层轮；高层指针每推进一格，就把到期那一槽的定时器 cascade（降级）重新分发到低层——越临近触发被搬到越细的轮，最终落到底层 L0 精确触发。

图 2-1 · 用 slots = 4、3 层演示：L0 每格跨 1 个 tick（覆盖 0–3）、L1 每格跨 4（覆盖 4–15）、L2 每格跨 16（覆盖 16–63）。共 12 个格子却覆盖 64 个 tick。可添加远期定时器，看它逐层降级。

$4 \times 3 = 12$ 个格子覆盖 $4^3 = 64$ 个 tick——用层数换格数，正是进位制压缩。Kafka 的 TimingWheel 即此思路。

建议 · 盯住一个远期定时器看整条轨迹最有效。以 delay = 40 为例，它先落在 L2 第 2 槽；now 走到 32 时 L2 指针跨槽，把它降级到 L1 第 2 槽；now 走到 40 时再从 L1 降到 L0，随即由 L0 精确触发。一个定时器一生最多被搬运「层数减一」次，与定时器总数无关，因此是摊还 $O(1)$ 。真实场景里大量定时器在触发前就被取消，连这点搬运都省了。

精度与范围就此解耦：底层 L0 决定精度（最小一格多大），层数决定范围（覆盖多久）。要毫秒精度、覆盖一天，4 层乘每层 100 格共约 400 个格子即可（ $100^4$ 毫秒约 27.7 小时），而非 8640 万——与朴素铺满的差距，就是写「86400000」只用 8 个数字位、而非画 8640 万个点。

3 · 三种实现的添加代价

管理海量定时器，核心操作是添加、删除、推进触发。图 3-1 把同一批定时器分别交给有序链表、最小堆、时间轮三种实现，实时累计它们「添加一个定时器」消耗的基本操作数（比较加移动或交换）。

图 3-1 · 三种实现的添加代价累计对比。可点「连加 20 个」，看有序链表线性飙升、最小堆对数增长、时间轮始终常数。

建议 · 这就是为什么高频、短延迟、且大量提前取消的场景（如每个网络连接一个超时定时器）几乎都用时间轮，Netty、Kafka、Dubbo 皆然。但要记住时间轮也有代价：延迟超出范围要靠分层 cascade 搬运，且精度受 tick 粒度限制——Netty 的 HashedWheelTimer 默认一格 100ms，不保证精确到点。

3.1 · 一件机件的两类用途

时间轮底层是环形缓冲区：固定数组加取模回绕的指针。把它当调度盘（槽位按时间寻址、装到期任务）就是时间轮；把它当滑动窗口（只留最近 $N$ 项）就是另一大类用途。两类都建立在同一机件上。

3.2 · 环形缓冲区的四类场景

有界事件 / 日志留存

只留最近 $N$ 条事件，满了覆盖最旧。dmesg 内核环形日志、各类 ring log、晚注册订阅者的回填快照都是它。

无锁生产者-消费者队列

一写一读的固定容量队列。LMAX Disruptor 的核心就是一个 ring buffer，支撑每秒千万级消息。

流 / 音视频缓冲 · 硬件 I/O 环

音频采集、抓包 buffer、网卡 RX / TX ring、磁盘 DMA 描述符环：数据持续流入，只关心最近一段，旧的被覆盖。

滑动窗口统计

保留最近 $N$ 个采样算移动平均、P99 或 QPS。把每格当一个时间片计数桶，指针走过就清空过期桶——这与时间轮在此交汇。

3.3 · 时间轮的四类场景

连接 / 会话超时管理

Netty HashedWheelTimer 管海量 TCP 连接的 idle 与读写超时；RPC 框架（Dubbo 等）同理。

延迟队列 / 重试退避

Kafka TimingWheel 实现延迟生产与拉取、事务超时；「失败后 3 秒、再 30 秒重试」按下次执行时刻挂入轮中。

限流 · 缓存 TTL 批量清理

滑动窗口限流器把每格当时间片计数桶；缓存项按过期时刻分桶，指针到哪桶就批量淘汰，免去逐个扫描查 TTL。

对比：最小堆做定时器

事件驱动模拟、OS 定时器队列也常用最小堆按触发时间排序、每次 extract-min 取下一个该发生的事件。

同一圈格子，装事件是历史缓冲、装计数是限流器、装到期任务是定时器——结构同源，语义取决于往槽位里放什么。