阿男聊技术

从 O(n) 到 O(1)：经典定时器论文《Hashed and Hierarchical Timing Wheels》的七种设计

TCP 超时重传、时钟信号、异步 I/O 超时——一个操作系统内核里同时活跃着成千上万个定时器。如果每次时钟 tick 都要遍历所有定时器才能知道谁该到期，系统会随着并发量增加越跑越慢。这个问题直到 1996 年才被一篇论文系统性地解决。

引言

先想象一个具体的场景。一个网络服务器上有 5 万个并发 TCP 连接，每个连接都有一个自己的超时定时器。你的操作系统每秒会产生 1000 次时钟中断（HZ=1000）。如果每次中断都要遍历全部 5 万个定时器，那每秒仅仅是检查定时器就要做 5000 万次操作。

这恰好是 Varghese 和 Lauck 在 1996 年论文¹里定义的问题起点。

这篇论文的贡献不在于提出了一个全新的算法——时间轮的思想此前已有萌芽——而在于它系统性地遍历了整个定时器实现的设计空间，从最简单粗暴的 Scheme 1 到精巧的分层时间轮 Scheme 7，完整地展示了不同约束下的最优选择。

概念先行：时间轮的直觉

论文的核心思想可以用一句话概括：将定时器按到期时间散列到环形数组的不同槽位中，每 tick 只处理当前指针指向的槽位，从而让 per-tick 的工作量与定时器总数解耦。

朴素做法（Scheme 1）：  每个 tick 遍历所有 50000 个定时器 → O(n)
                         ↓
时间轮（Scheme 4）：    每个 tick 只检查 1 个槽位       → 平均 O(1)

这个对比锚定了整篇论文的动机——在定时器数量达到数万时，O(n) 和 O(1) 的差距不是常数倍的，而是能否工作的区别。

定时器模块的四个基本操作

论文首先建立了一个通用分析框架：任何定时器模块都由四个基本例程组成¹。

sequenceDiagram
    participant App as 应用程序
    participant Timer as 定时器模块
    participant Clock as 硬件时钟
    participant Handler as 回调函数

    App->>Timer: STARTTIMER(100ms, id, callback)
    Note over Timer: 将定时器插入数据结构
    App->>App: 继续执行其他工作

    loop 每 tick
        Clock->>Timer: 时钟中断
        Timer->>Timer: PERTICKBOOKKEEPING()
        alt 有到期定时器
            Timer->>Handler: EXPIRYPROCESSING(callback)
        end
    end

    App->>Timer: STOPTIMER(id)
    Note over Timer: 从数据结构中移除

七种方案的本质，就是在 STARTTIMER 的延迟和 PERTICKBOOKKEEPING 的工作量之间做取舍。

方案 1-3：论文之前的设计

在引入时间轮之前，论文列举了三种已有的实现方式。它们构成了”对照组”。

Scheme 1：直白法

数据结构：无序定时器列表。 做法：每 tick 遍历所有定时器，逐个递减计数器。

// Scheme 1 的 PERTICKBOOKKEEPING
void per_tick_bookkeeping() {
    for (每个定时器 t in 链表) {
        t->counter--;
        if (t->counter == 0) {
            EXPIRYPROCESSING(t);
        }
    }
}

每 tick O(n) 是灾难性的。但它有一个优势：实现最简单，内存占用最小。

Scheme 2：有序链表

数据结构：按绝对过期时间排序的链表。 做法：每 tick 只检查链表头。

相当于把 per-tick 的 O(n) 转嫁到了 STARTTIMER 上。适合定时器启动频率低的场景。

Scheme 3：树结构

数据结构：平衡树（红黑树）或堆。

虽然三个操作都是对数复杂度，但论文指出其常数较大，而且 O(log n) 在定时器数量极大时依然不够理想。

这三种方案的共同问题是：当定时器数量 n 增大时，至少有一个操作的时间复杂度随 n 增长。

方案 4：基本时间轮——论文的核心创新

Scheme 4 是整篇论文的突破点，后两个方案都是它的变体。

数据结构

一个大小为 N 的环形数组（circular buffer），每个槽位是一个定时器链表：

       当前指针
          │
          ▼
    ┌───┬───┬───┬───┬───┬───┬───┬───┐
    │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │    ... 环形数组（N=8）
    └───┴───┴───┴───┴───┴───┴───┴───┘
      │           │           │
      ▼           ▼           ▼
   链表1        链表2        链表3

操作

• STARTTIMER：slot = (current_pointer + Interval) % N，直接插入该槽位的链表。O(1)
• PERTICKBOOKKEEPING：移动指针到下一个槽位，处理该槽位链表中的所有定时器。O(1)
• STOPTIMER：从链表中移除（持有节点指针）。O(1)

论文特别强调，在 PERTICKBOOKKEEPING 中，如果当前槽位为空，什么也不用做¹：

“If the element is 0 (no list of timers waiting to expire), no more work is done on that timer tick.”

为什么叫”时间轮”？

论文中的原话¹：

“We call this data structure a timing wheel. It can be viewed as a circular array of lists, where the position in the array corresponds to the time remaining before expiration.”

限制

基本时间轮要求数组大小 N 至少等于最大可能的定时器间隔。32 位计数器下，N 需要达到 4 亿以上——内存完全不可接受。

Scheme 4:  O(1) 的神器，但 N 必须 ≥ MaxInterval → 内存爆炸

方案 5-6：哈希时间轮

基本时间轮的核心限制是数组大小必须覆盖最大间隔。哈希的思路是：用一个较小的表，把间隔哈希到槽位。

Scheme 5：哈希 + 有序链表

每个槽位的链表按到期时间排序。

排序的好处是 PERTICKBOOKKEEPING 只需检查链表头部的定时器。但 STARTTIMER 需要通过二分或顺序查找找到插入位置，平均不是严格 O(1)。

Scheme 6：哈希 + 无序链表

每个槽位的链表不排序，新定时器直接插入头部。

这是论文为通用操作系统推荐的首选方案之一。 BSD UNIX 后来实际采用的就是 Scheme 6，只修改了约 500 行内核代码¹。

为什么无序链表更好？论文的推理是：STARTTIMER 的延迟通常比 PERTICKBOOKKEEPING 更敏感。前者发生在应用程序的关键路径上，后者发生在时钟中断上下文中，可以接受稍大的工作量。无条件 O(1) 的 STARTTIMER 比平均 O(1) 更有价值。

Scheme 5（有序）：      STARTTIMER 平均 O(1) —— 但有哈希冲突时的退化风险
Scheme 6（无序）：      STARTTIMER 严格 O(1) —— 确定性延迟，更适合实时场景

方案 7：分层时间轮

哈希时间轮用固定大小的表解决了”最大间隔”问题，但槽位数仍然是固定的。分层时间轮用另一个思路——用多组不同粒度的数组—来覆盖巨大的时间范围。

数据结构

   天轮（100 槽）          时轮（24 槽）          分轮（60 槽）          秒轮（60 槽）
   ┌──┬──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐
   │0 │1 │2 │...│99│       │0 │1 │2 │...│23│       │0 │1 │2 │...│59│       │0 │1 │2 │...│59│
   └──┴──┴──┴──┴──┘       └──┴──┴──┴──┴──┘       └──┴──┴──┴──┴──┘       └──┴──┴──┴──┴──┘

总共只需要 100 + 24 + 60 + 60 = 244 个槽位，就可以覆盖 100 天的时间范围。

Cascading：逐级降级

分层时间轮最核心的机制是 cascading——定时器从上层逐渐”下沉”到底层，只有到达最底层的秒轮时才真正触发回调。

插入一个 50 分 45 秒的定时器的完整路径：

STARTTIMER(50分45秒, callback)

  时轮（1小时后到期）
    → 时轮槽位 = 当前时 + 1
    → 存储: { minutes=15, seconds=15 }
      ↓ 1 小时后，时轮指针到达该槽位
  分轮（15分钟后到期）
    → 分轮槽位 = 当前分 + 15
    → 存储: { seconds=15 }
      ↓ 15 分钟后，分轮指针到达该槽位
  秒轮（15秒后到期）
    → 秒轮槽位 = 当前秒 + 15
    → 存储: { callback }
      ↓ 15 秒后，秒轮指针到达该槽位
  执行 callback()

sequenceDiagram
    participant App as STARTTIMER
    participant Hour as 时轮
    participant Minute as 分轮
    participant Second as 秒轮

    App->>Hour: 插入 50分45秒
    Note over Hour: 等待 1 小时
    Hour->>Hour: 指针到达当前槽位
    Hour->>Minute: cascading → 剩余 15 分钟
    Note over Minute: 等待 15 分钟
    Minute->>Minute: 指针到达当前槽位
    Minute->>Second: cascading → 剩余 15 秒
    Note over Second: 等待 15 秒
    Second->>App: 到期 → EXPIRYPROCESSING

论文中的原话描述这个机制¹：

“When the hour timer reaches 11, the list is examined. The expiry processing routine will insert the remainder of the seconds (15) in the minute array, 15 elements after the current minute pointer (0).”

复杂度

论文的评价¹：

“Scheme 7 uses essentially logarithmic time to insert an element; thus it is comparable in complexity to standard priority queue implementations like heaps. However, the constants appear to be better for Scheme 7.”

虽然插入是 O(m)，但 m 是常数（4 或 5），远小于 log n。而且内存占用完全固定。

七种方案全景对比

论文的最终推荐¹：

“For a general timer module… we recommend Scheme 6 or 7.”

graph TD
    Start["定时器实现需求"] --> Decision{"设计约束?"}

    Decision -->|"定时器数量少"| S1["Scheme 1<br/>直白法 O(n)/tick"]
    Decision -->|"启动频率低"| S2["Scheme 2<br/>有序链表 O(n) start"]
    Decision -->|"通用 OS"| S6["Scheme 6<br/>哈希+无序 O(1) start"]
    Decision -->|"内存受限"| S7["Scheme 7<br/>分层时间轮 极小内存"]
    Decision -->|"短间隔精确"| S4["Scheme 4<br/>基本时间轮 O(1) all"]

    style S6 fill:#90EE90
    style S7 fill:#87CEEB

论文的影响

BSD UNIX

Costello 将 Scheme 6 嵌入 BSD 内核。实测表明：新实现中 STARTTIMER 和 STOPTIMER 的时间恒定，不受定时器数量影响；而旧实现（Scheme 2，有序链表）的时间随定时器数量线性增长。

Linux 内核

Linux 内核对这篇论文的思想有正反两个方向的借鉴：

• 低精度定时器（timer wheel）：位于 kernel/time/timer.c，本质就是分层时间轮——8 到 9 层、每层 64 个 bucket（LVL_SIZE = 64，LVL_DEPTH = 8/9）²
• 高精度定时器（hrtimer）：使用红黑树，追求纳秒级精度

低精度定时器的层级设计几乎是 Scheme 7 的直接工程实现：

// kernel/time/timer.c  (HZ=1000 时)
// Level  粒度            覆盖范围
//   0     1 ms             0-63 ms
//   1     8 ms            64-511 ms
//   2    64 ms           512-4095 ms
//   3   512 ms          4096-32767 ms
//   4  4096 ms (~4s)   32768-262143 ms (~32s-~4m)
//   5 32768 ms (~32s) 262144-2097151 ms (~4m-~34m)
//   6 262144 ms (~4m) 2097152-16777215 ms (~34m-~4h)
//   7 2097152 ms (~34m) 16777216-134217727 ms (~4h-~1d)
//   8 16777216 ms (~4h) 134217728-1073741822 ms (~1d-~12d)

Tokio（Rust 异步运行时）

Tokio 的异步 timer 使用 6 层、每层 64 slot 的哈希时间轮，代码注释明确引用了 Varghese & Lauck 的论文³：

Level 0: 64 × 1 ms      = 64 ms
Level 1: 64 × 64 ms     = ~4 s
Level 2: 64 × ~4 s      = ~4 min
...                     ...
Level 5: 64 × ~12 day   = ~2 年

总结：这篇论文为什么经典

这篇论文的成就不是某个石破天惊的算法，而是系统性地定义了一个问题空间，然后完整地遍历了它。

三点贡献值得记住：

1. 通用的分析框架：四个例程（STARTTIMER、STOPTIMER、PERTICKBOOKKEEPING、EXPIRYPROCESSING）成为后来所有定时器实现的基准
2. 完整的设计空间：从 Scheme 1 到 Scheme 7，每一种方案都是不同约束下的最优解——没有银弹，只有权衡
3. 一个简单的思想：时间轮——利用时间单调递增的特性，把定时器按时间散列，每 tick 只处理一个槽位——这是空间换时间的一个教科书级范例

而全篇论文中我最喜欢的一段话，是下面这个不起眼的观察¹：

“In timer algorithms, however, the crucial observation is that some entity needs to do O(1) work per tick to update the current time; it costs only a few more instructions for the same entity to step through an empty bucket.”

系统本来就要在每 tick 做固定工作来更新时间。时间轮只是在这条不可避免的执行路径上，顺便检查一下当前槽位。当槽位为空时——这是最常见的情况——额外开销几乎为零。这就是时间轮能够同时实现 O(1) STARTTIMER、O(1) STOPTIMER、O(1) PERTICKBOOKKEEPING 的秘密。

References

• 上一篇 大模型工程化的自举迭代框架：从 Demo 到可持续生产系统的五层实践