第11章 Time Driver 与分层定时器轮

"Timers are the quietest tyrants of a runtime — millions of them, each demanding attention at their exact moment." —— 笔者

本章要点

Tokio 的 Time Driver 用 分层时间轮（Hierarchical Timing Wheel） 管理所有定时器——6 层 × 64 slot 的二维数组
NUM_LEVELS = 6、LEVEL_MULT = 64 两个常量定义整个结构；`MAX_DURATION = (1 << 36) - 1 ms ≈ 2 年**
每层精度是上一层的 64 倍：Level 0 是 1 ms / 64 ms 范围、Level 5 是 ~12 天 / ~2 年范围
插入定时器是 O(1)：算 level_for(when) 找层、slot_for(when, level) 找槽、push 到槽的链表
取下一个到期也是 O(1)：每层用 u64 bitmap 标记占用，trailing_zeros 指令秒找
时间流逝 = Level 0 扫完 64 slot 后，把 Level 1 当前 slot 的定时器"降级"到 Level 0——级联展开
为什么不用 BinaryHeap：堆插入 / 取下一个都是 O(log N)——在百万定时器场景下明显慢于时间轮的 O(1)

11.0½ 从一个朴素问题开始

在深入结构之前先设身处地想一下：如果让你自己实现一个异步 sleep，你会怎么做？

方案 A：一个线程 + 循环 sleep 每次 tokio::time::sleep(1秒) 就 spawn 一个线程调 std::thread::sleep(1秒)。能跑但疯狂浪费——一个连接一个线程，几千连接就几千线程。立刻 OOM。

方案 B：一个全局 Vec + 定时检查 一个数据结构存所有 timer、单独一个线程每 10 ms 扫一次有没有到期的。可行但低效——定时器多了扫描 N 次每 tick，浪费 CPU。

方案 C：std::collections::BinaryHeap + 一个线程 peek 最小值 用最小堆——peek 最早到期的 O(1)、pop O(log N)、push O(log N)。比 B 好——不扫全部。但随着 timer 增多 log N 仍然线性增长。

方案 D：像 Tokio 这样的分层时间轮 用分层 bucket——插入 O(1)、取下一个 O(1)、级联摊销 O(1)。工业级选择。

从 A 到 D 的每一跳都是 10-100 倍性能提升。Tokio 选 D 并不是玩花样——而是在"几百万连接 + 每连接一个 timer"的工业场景下别无选择。

读本章时带着这个演化脉络——每个设计决策都有它想规避的劣化版本。

11.1 为什么异步运行时需要"特殊"的定时器结构

一个 tokio::time::sleep(Duration::from_millis(100)) 的幕后是什么？最朴素的实现是：

把 (到期时间, Waker) 存进某个数据结构
每次主循环检查"有没有过期的"、过期就 wake

数据结构是什么？几个候选：

无序 Vec：插入 O(1)，取下一个 O(N)。定时器多就爆
BinaryHeap（小顶堆）：插入 O(log N)，peek 最小 O(1)，pop 最小 O(log N)。通用方案，但 log N 在百万级定时器下是 20 次比较
BTreeMap<时间, Waker>：插入 O(log N)、有序遍历 O(N)。比 heap 多支持范围查询、但基础操作慢
分层时间轮：插入 O(1)、取下一个 O(1)。Tokio 和几乎所有工业级定时器的选择

Tokio 选 4 是有原因的。让我们看一个真实场景：一个 HTTP 服务器，每个连接有一个 30 秒超时。10 万并发连接 = 10 万个活跃定时器。用 heap：每次 sleep 都 log(10万) ≈ 17 次比较 + atomic。时间轮：O(1)。

但时间轮的代价是"精度 vs 范围"：固定精度下范围有限。Tokio 用分层结构解决这个矛盾——多层叠加让精度从 1 ms 跨到 2 年。

真实世界的其他时间轮实现

Linux kernel 的 timer 子系统（kernel/time/timer.c）也用分层时间轮——8 层 × 64 slot，精度 1 jiffy（通常 1 ms 或 4 ms）。比 Tokio 多 2 层，范围更长（数百年）。

为什么 kernel 用 8 层、Tokio 只用 6 层：kernel 的工作负载更广（包括 hardware watchdog 等超长 timer）；Tokio 用户态 6 层足够且省内存（每多一层常驻约 2 KB）。两者设计都是场景驱动的。

Netty（Java 异步网络框架）的 HashedWheelTimer 是一个单层时间轮——精度固定（默认 100 ms）、范围固定。没用分层，因为 Java 服务一般不需要 2 年级别的 timer。

Netty 的决策背后：

默认 100 ms 精度对 HTTP / gRPC 超时足够
单层简化实现（没有 cascade 逻辑）
超过轮总范围的 timer 会在溢出 slot 里等——效率略低但接受
Java 的 GC 让"大数组常驻内存"成本比 Rust 高——分层会加剧 GC 压力

同一问题、三种答案（Netty 单层 / Tokio 分层 / libuv heap）——每种都是在各自语言和场景约束下的最优。没有一个"最好"的答案——只有"最适合当前约束"的答案。

libuv（Node.js）用最小堆——uv_timer_t 基于 binary heap。每次插入 / pop 都是 O(log N)。这在 Node 场景下问题不大——一个 Node 应用通常最多几百个活跃 timer（每个 HTTP 请求的 socket timeout、setTimeout 之类）。如果到了几万个 timer 的场景（比如某个分布式系统的心跳），Node 会感受到明显的 CPU 消耗。

Tokio 场景和 Node 不同：

Rust 后端服务常有几十万到几百万并发连接
每个连接至少一个 timer（读超时）
Node 场景的 10-100x 大 —— heap 就扛不住了性能在百万 timer 下明显弱于时间轮、但实现简单。Node 的场景很少有百万 timer，简单实现的代价可以接受。

这三种（分层时间轮、单层时间轮、最小堆）代表了 timer 实现的三个档次。Tokio 走了最复杂但最高性能的那一档——因为它要服务的是最严苛的 Rust 工业级场景。

时间轮的原创论文

分层时间轮的原创设计来自 Varghese & Lauck 的 1987 年论文 "Hashed and Hierarchical Timing Wheels"——这篇论文定义了我们今天看到的几乎所有时间轮变体。

Varghese 后来成了 MIT 的网络教授，Lauck 在 DEC 做底层网络研究。他们在 1987 年就考虑了"10 万并发连接的电话交换机"场景——而 40 年后 Tokio / Linux kernel / Netty 仍在用他们的算法。好算法的生命力。

读那篇论文（30 页左右）你会发现：分层时间轮的核心思想几十年没变，变的只是常数调整（层数、slot 数、是否分 shard 等）。基础算法的稳定性是计算机科学最美的一面。

11.2 `Wheel` 结构：6 层 + 64 slot/层

打开 tokio/src/runtime/time/wheel/mod.rs。原样：

rust

// 来源：tokio-rs/tokio · tokio/src/runtime/time/wheel/mod.rs (tokio-1.40.0)
pub(crate) struct Wheel {
    elapsed: u64,
    levels: Box<[Level; NUM_LEVELS]>,
    pending: EntryList,
}

const NUM_LEVELS: usize = 6;
pub(super) const MAX_DURATION: u64 = (1 << (6 * NUM_LEVELS)) - 1;

三个字段：

elapsed: u64：已经流逝的时间（单位毫秒），从 runtime 启动算起
levels: Box<[Level; 6]>：6 层时间轮
pending: EntryList：已经到期但还没 fire 的 timer 缓存（EntryList 是侵入式链表）

NUM_LEVELS = 6：6 层。`MAX_DURATION = 2^(6*6) - 1 = 2^36 - 1 ≈ 68.7 billion ms ≈ 2.18 年。超过这个范围的 timer 插入会被拒绝——但 2 年对任何合理服务来说都够了。

Level 结构

打开 level.rs：

rust

// 来源：tokio/src/runtime/time/wheel/level.rs
pub(crate) struct Level {
    level: usize,
    occupied: u64,
    slot: [EntryList; LEVEL_MULT],
}

const LEVEL_MULT: usize = 64;

三字段：

level: usize：这是第几层（0-5）
occupied: u64：一个 64 位 bitmap，每个 bit 代表对应 slot 是否有 entry
slot: [EntryList; 64]：64 个侵入式链表

一共 6 × 64 = 384 个 slot。每个 slot 是一个链表，能装任意多个定时器。

层级范围的层层放大

每层的 "slot 时间范围" 是上一层的 64 倍：

Level	slot 精度	整层范围
0	1 ms	64 ms
1	64 ms	4.096 秒
2	4.096 秒	4.37 分钟
3	4.37 分钟	~4.66 小时
4	~4.66 小时	~12.4 天
5	~12.4 天	~2.18 年

插入一个定时器时：根据到期时间距当前多远，选对应层。

sleep(Duration::from_millis(50)) → 50 ms 距离 → Level 0 的某个 slot
sleep(Duration::from_secs(1)) → 1000 ms → Level 1 的某个 slot（超过 Level 0 的 64ms 范围）
sleep(Duration::from_secs(3600)) → 3.6M ms → Level 3 的某个 slot
sleep(Duration::from_days(7)) → 604.8M ms → Level 4 的某个 slot

每种时长都在 O(1) 时间找到自己的"家"。

每层 "精度"和 "范围" 的对数关系

注意表里的数字关系：

Level N 的 slot 精度 = 64^N ms
Level N 的整层范围 = 64^(N+1) ms
每层范围 = 上层精度的 64 倍（因为一层 64 slot）

这个对数关系让 6 层覆盖 2 年 = 64^6 ms ≈ 69 亿 ms。如果每层增加 slot 数（比如 128），每层覆盖范围翻倍，但总层数无大变化。

为什么不考虑非 64 进制？ 比如 16 进制（每层 16 slot）需要更多层、32 进制需要的层数也多。64 进制在 "每层精度 vs 整层范围 vs 层数 vs bitmap 大小"四个维度都是最优。黄金数 64。

`Box<[Level; 6]>` 而不是 `Vec<Level>`

注意 levels: Box<[Level; 6]> —— 用固定长度数组的 Box 而不是 Vec。为什么？

固定长度：编译期就知道 6 层，永不增减。不需要 Vec 的 capacity / len 字段
Box 住堆上：Wheel 本身在栈上会占几 KB，Box 把它挪到堆上——Wheel struct 只占一个指针
[Level; 6] 内存连续：6 个 Level 紧密排列，cache-friendly

Vec 的 overhead 包括：ptr + len + capacity（24 字节） + 额外的 allocation tracking。对固定长度的容器，Box<[T; N]> 更优。

Rust 的类型系统让这种选择很自然——其他语言可能只有 "动态数组" 一种选择，Rust 能在固定长度和动态长度间精细选择。每个字节都有意义。

11.3 `insert`：插入一个定时器

原样：

rust

// 来源：tokio/src/runtime/time/wheel/mod.rs
pub(crate) unsafe fn insert(
    &mut self,
    item: TimerHandle,
) -> Result<u64, (TimerHandle, InsertError)> {
    let when = item.sync_when();

    if when <= self.elapsed {
        return Err((item, InsertError::Elapsed));
    }

    let level = self.level_for(when);

    unsafe {
        self.levels[level].add_entry(item);
    }

    Ok(when)
}

5 步：

读 timer 的 when（绝对到期时间，ms 单位）
如果 when <= elapsed，说明已经过期——返回错误（调用方会直接 fire）
算 level_for(when) 决定该进哪层
调 levels[level].add_entry(item) 把 item 插入那层的对应 slot
返回 Ok(when)

整个过程没有循环、没有搜索——纯 O(1)。

`level_for(when)`：位运算选层

level_for 的逻辑（简化）：

rust

fn level_for(&self, when: u64) -> usize {
    let since_start = when - self.elapsed;
    
    // 64 的多少次方不小于 since_start
    const SLOT_MASK: u64 = (1 << 6) - 1;  // 0x3F = 63
    let significant = 63 - (since_start | SLOT_MASK).leading_zeros() as usize;
    significant / 6
}

用 leading_zeros 算距离的 log64：

since_start <= 63：level 0（64 以内）
since_start <= 4095：level 1（64 * 64 以内）
since_start <= 262143：level 2
... etc

一次位运算 + 除法决定层号——几纳秒。

`add_entry`：把 timer 塞进 slot

原样：

rust

// 来源：tokio/src/runtime/time/wheel/level.rs
pub(crate) unsafe fn add_entry(&mut self, item: TimerHandle) {
    let slot = slot_for(item.cached_when(), self.level);
    self.slot[slot].push_front(item);
    self.occupied |= occupied_bit(slot);
}

3 步：

slot_for(when, level)：用位运算算 slot index——类似 (when >> (level * 6)) & 0x3F
slot[idx].push_front(item)：把 item 加到侵入式链表头
occupied |= occupied_bit(slot)：在 bitmap 里把对应 bit 置 1

O(1) 完成，带一个 bitmap 更新为后续"找下一个到期"做准备。

`slot_for`：位运算定位 slot

slot_for(when, level) 的公式（简化）：

rust

fn slot_for(when: u64, level: usize) -> usize {
    ((when >> (level * 6)) & 0x3F) as usize
}

每层 slot 是 64 个（2^6）——when 右移 level * 6 位后取低 6 位 = slot index。

具体例子：

when = 50，level = 0：50 >> 0 & 63 = 50→ Level 0 slot 50
when = 800，level = 1：800 >> 6 & 63 = 12 → Level 1 slot 12
when = 300000，level = 2：300000 >> 12 & 63 = 73 超过 64 —— 不在 Level 2 而进 Level 3

这就是为什么 NUM_LEVELS = 6 配 LEVEL_MULT = 64——两者都是 2 的幂，位运算优雅。

一次位运算 = 1 CPU cycle——对比 heap 的 log N 次比较 = log N × 3-5 cycles。差距一目了然。

cached_when：timer 的关键优化

注意代码里 item.cached_when() —— TimerHandle 缓存了自己的绝对 deadline（ms 单位）。为什么要缓存？

因为 timer 的 when 字段可能被访问多次（插入、cancel、级联时重新插入）。每次调用 std::time::Instant::now() 再减参考点算 when 会有系统调用 + 浮点运算开销。缓存一次、读多次，把 when 冻结在 TimerHandle 里。

sync_when 是触发"读 now 并计算 when" 的特殊方法——只在 insert 时用一次。后续访问都 cached_when、纯内存读。

**这种"缓存 hot read 数据"**在 Tokio 各处都有——Task 的 id、Future 的 tracking id、ScheduledIo 的 readiness 最后观察值。hot path 永远不做重复计算。

插入后的 `elapsed` 保持不变

插入一个 timer 不会改变 elapsed——elapsed 只在"时间流逝"时（每次 Wheel.advance(now) 调用时）才增加。这是一个明确的设计约束：

Wheel 的状态只在 Time Driver 的主循环被推进
插入 / 删除 / cancel 是纯修改操作——不推进时间
advance 由 Time Driver 定期调用——它读 std::Instant::now()、算出新的 elapsed、处理所有到期 timer

这种"状态变更 vs 时间推进"的解耦让 Wheel 的操作简洁——插入不需要"顺便处理到期"，advance 不需要"顺便插入"。每个操作职责单一，测试和并发正确性都容易得多。

相比之下，如果每次插入都要 "顺便检查过期"，代码会变成互相纠缠的分支——bug 几率飙升。Tokio 的 Wheel 代码能稳定运行多年不出大 bug，这种清晰分工是基础。

11.4 取下一个到期：bitmap + `trailing_zeros`

关键操作二：找"最快到期的 timer 还有多久"。主循环调 poll_at / next_expiration 来决定下一次 epoll_wait 的 timeout。

rust

// 来源：tokio/src/runtime/time/wheel/mod.rs
pub(crate) fn poll_at(&self) -> Option<u64> {
    self.next_expiration().map(|expiration| expiration.deadline)
}

next_expiration 的逻辑（简化）：

rust

fn next_expiration(&self) -> Option<Expiration> {
    for level in 0..NUM_LEVELS {
        if self.levels[level].occupied != 0 {
            // 这层有 entry，找最早的那个 slot
            let slot = self.levels[level].occupied.trailing_zeros() as usize;
            return Some(Expiration {
                level,
                slot,
                deadline: self.deadline_for(level, slot),
            });
        }
    }
    None
}

核心技巧：occupied.trailing_zeros() —— x86 的 bsf 指令（1 cycle）。找 bitmap 里最低的置 1 位。

如果 Level 0 有 entry：直接返回（最早到期必在 Level 0）。 如果 Level 0 空：查 Level 1，trailing_zeros 找最低 slot。以此类推。

最坏情况扫 6 层——6 次 atomic load + 6 次 trailing_zeros = ~20 纳秒。真正的 O(1)。

为什么 `occupied` 是 u64 而不是 u128 或数组

Level.occupied 是 u64——精确对应 64 个 slot。如果改成 128 slots / level，occupied 就得是 u128 或 [u64; 2]。

单个 u64 的好处：

trailing_zeros() 一条 CPU 指令搞定（x86 的 bsf / tzcnt）
|= / &= 等位操作原子
fits in register，不跨 cache line

u128 或 [u64; 2] 的坏处：

trailing_zeros() 变两步（先检查第一个 u64、为 0 再查第二个）
在 32 位架构上 u128 的原子操作可能被拆成两步
代码复杂、易错

LEVEL_MULT = 64 的选择和 u64 的选择互锁——改任一个都要改另一个。工程里的协同约束。

和 BinaryHeap 对比

	分层时间轮	BinaryHeap
插入	O(1) + 一次位运算	O(log N) + 比较
取最早	O(1) + 位运算	O(log N) + 堆调整
删除	O(1)（unlink 链表节点）	O(log N)
内存	固定 6 × 64 + N（entries）	O(N)
百万 timer 下单操作	~20 纳秒	~500 纳秒

在 timer 数量大的场景，时间轮完胜 heap。对 Tokio 这种要支撑几百万并发连接的 runtime，timer 数量轻松过百万——时间轮是唯一合理选择。

EntryList 是侵入式链表

注意 slot: [EntryList; 64]——每个 slot 是 EntryList（Tokio 自己的侵入式链表类型）。

为什么不用 Vec<TimerHandle> 每个 slot？

timer 数量不定，可能 0 也可能几千——Vec 需要反复扩容、缩容
timer 频繁增删——Vec 中间删除是 O(N)
cancellation：timer 被 cancel 时需要"从所在 slot 移除"——用 Vec 得线性搜索

**侵入式链表（intrusive linked list）**让每个 timer 自带 prev / next 指针（在 TimerHandle 的数据里）——插入 / 删除都是 O(1)，不管链表多长。和第 6 章的 OwnedTasks、第 8 章的 RegistrationSet 是同一家族——三个章节、同一个技术。

读到这里你应该已经识别出 "侵入式链表" 这个 Tokio 签名模式——它是"动态集合 + 频繁增删 + 零堆分配"的标准解。自己写类似场景时优先考虑这个数据结构。

11.5 时间流逝：级联降级

到这里最精妙的问题来了：时间流逝后怎么办？

假设 Wheel.elapsed = 0 时你 sleep(5 秒)——这个 timer 进 Level 1（因为 5 秒 > 64 ms）。Level 1 里的时间精度是 64 ms——但 5 秒 = 5000 ms，具体到 ms 精度在 Level 1 里不能直接表达。

Tokio 的做法：当 Level 0 走完 64 ms 后（即 elapsed 达到 64、128、192...）—— 把 Level 1 的"当前 slot 里的所有 timer"取出来、重新插入到 Wheel 里。

重新插入时：

一个原本 4.5 秒的 timer，现在剩余 4.5 - 0.064 = 4.436 秒——还是进 Level 1（4.436 秒 > 64 ms）
一个原本 80 ms 的 timer（本来也在 Level 1），现在剩余 80 - 64 = 16 ms——降级到 Level 0

这种"上层 slot 消费完，里面的 timer 重新插入" 叫 cascade（级联降级）。每过 64 ms 发生一次 Level 1 的小级联；每过 4096 ms 发生一次 Level 2 的大级联；以此类推。

为什么级联是 O(1) 摊销

你可能想：一次级联要把一个 slot 里的所有 timer 重新插入——看起来不像 O(1)？

答案：任何一个具体的 timer 最多被级联 NUM_LEVELS = 6 次（每级一次）。摊销到 timer 的生命周期，每个 timer 的级联成本是 O(NUM_LEVELS) = O(1)。

这是分层时间轮的精妙所在：用"摊销 O(1)"代替 heap 的"每步 O(log N)"——在大规模场景下压倒性胜出。

这种摊销分析是高级数据结构的常见思路——红黑树、动态数组、splay tree 等都用这个技巧。真正的 O(log N) 一步成本高、摊销 O(1) 把成本分摊到更多操作。时间轮在 timer 场景比树更合适，因为场景 I/O 密集不会让单个 timer 大量操作。

11.5½ 一个完整级联例子：逐毫秒走 10 分钟

为了让抽象的"级联降级"具体化，手动跑一次假想的时间流逝：

初始状态（elapsed = 0）：

Timer A：sleep(50 ms) → Level 0、slot 50
Timer B：sleep(800 ms) → 800 ms > 64 ms 所以进 Level 1。slot = (800 >> 6) & 0x3F = 12
Timer C：sleep(300 秒) = 300000 ms → Level 2。slot = (300000 >> 12) & 0x3F = 73 % 64 = 9... 实际上 Level 2 每 slot 是 2^12 = 4096 ms，300000 / 4096 = 73（超过 64），所以其实 300 秒进 Level 3（每 slot 2^18 = 262144 ms）。slot = 300000 / 262144 = 1

elapsed = 50 之后：Timer A 所在的 slot 被扫到——A fire、Waker 调用、Task 重 schedule。Level 0 继续走到 slot 51, 52...

elapsed = 64 之后：Level 0 走完一轮（0-63）。此时需要级联 Level 1：

Level 1 slot 0（覆盖 0-63 ms）已经没 timer 了（因为 Level 0 走完了这 64 ms）
Level 1 当前指针指向 slot 1（覆盖 64-127 ms）
把 slot 1 里的所有 timer 取出——没有（Timer B 在 slot 12，覆盖 12×64=768 到 832 ms）
Level 0 的 elapsed 归零，继续走 64-127 ms

elapsed = 768 之后（Level 1 slot 12 到期）：

Timer B 在 slot 12——把它从 Level 1 取出
B 的剩余时间 = 800 - 768 = 32 ms → 降到 Level 0，slot 32
Level 0 继续走，到 32 ms 时 B fire

elapsed = 262144 ms（约 4.37 分钟）之后：Level 3 走一次级联——Timer C 从 Level 3 降到 Level 2 某个 slot。接下来每过 4096 ms 又一次小级联，最终 C 会一路降到 Level 0、在 300 秒准确 fire。

每个 timer 最多被级联 NUM_LEVELS - 1 = 5 次（从它初始层降到 Level 0）。平均每 64 个 timer 共享一次级联开销 —— 摊销 O(1) 的由来。

为什么是 64 而不是 128 或 32？

这是一个经过工程验证的最优值。考量：

太小（比如 16）：每层覆盖范围小，需要更多层。6 层 × 16 只能到 16^6 ≈ 1600 万 ms ≈ 4.6 小时。max duration 不够
太大（比如 256）：每层 slot 数多——occupied bitmap 不能用单个 u64 塞下，需要 [u64; 4] 之类的数组——trailing_zeros 变成多步
64 正好：一个 u64 bitmap 覆盖全层 + 6 层覆盖 2 年 + 每层精度是上一层 64 倍

64 = 2^6 还特别适合位运算——(when >> (level * 6)) & 0x3F 算 slot 一步到位。

这个数字是"刚刚好"——和 Tokio 其他常量（event_interval = 61、local_queue_capacity = 256）一样，都是反复打磨的结果。

11.6 Time Driver 与 I/O Driver 的协作

Time Driver 的 Driver struct 非常薄：

rust

// 来源：tokio/src/runtime/time/mod.rs
pub(crate) struct Driver {
    park: IoStack,
}

它持有 I/O Driver（IoStack）——因为 Time Driver 不独立工作，它和 I/O Driver 共用同一次 epoll_wait。

park 的协作流程

rust

pub(crate) fn park(&mut self, handle: &driver::Handle) {
    self.park_internal(handle, None);
}

pub(crate) fn park_timeout(&mut self, handle: &driver::Handle, duration: Duration) {
    self.park_internal(handle, Some(duration));
}

park_internal 的逻辑：

先问 Time Driver 的 Wheel："下一个到期 timer 还有多久？"→ 假设 next_wake 纳秒
把 min(next_wake, duration) 作为 timeout 传给 I/O Driver 的 turn(timeout)
I/O Driver 调 epoll_wait(..., timeout)——要么等到事件、要么等到时间点
醒来后，Time Driver 调 process_at_time(now) 处理所有已到期的 timer
每个 timer → wake 对应的 Waker → 对应的 Task 重新 schedule

关键：I/O 和 Time 共享一次 epoll_wait。epoll_wait 的 timeout 参数本来就是"最多等多久"——Time Driver 利用这个参数传"我的下一个 timer 还有多久"。一个系统调用完成两件事。

`process_at_time` 的简洁

rust

pub(self) fn process_at_time(&self, start: u32, now: u64) {
    let shards = self.inner.get_shard_size();
    let expiration_time = (start..shards + start)
        .filter_map(|i| self.process_at_sharded_time(i, now))
        .min();
    self.inner.next_wake.store(next_wake_time(expiration_time));
}

Tokio 1.20+ 引入了 sharding——把一个 Wheel 拆成多个 shard（每 shard 一个锁），减少插入 timer 的锁竞争。process_at_time 处理每个 shard 的 expired timer、更新下次 wake time。

tokio::time::sleep 的真实开销

一次 tokio::time::sleep(Duration::from_millis(100)) 的具体开销：

插入 timer：约 100-200 纳秒（Wheel insert + slot push_front + bitmap update）
到期 fire：约 200-400 纳秒（从 slot 取出 + wake Waker + Task schedule）
触发一次 cascade（极少数情况）：约 1-3 微秒（一个 slot 可能有几十个 timer 被重新插入）

总开销约 500 纳秒——一次 sleep 的全部 Tokio 侧开销。比一次 HTTP 请求（几毫秒）低 4 个数量级——可以忽略不计。

但如果你每秒 spawn 百万个短 timer：累积下来 500 ns × 百万 = 500 ms CPU 开销。这时候 sharding 改造的价值就显现了。

Tokio 1.40 的 sleep 精度在不同负载下的表现

真实测试数据（Linux x86_64，idle 负载）：

轻负载（< 100 QPS）：sleep(100ms) 实际 100-102 ms，jitter < 2 ms
中负载（~10k QPS）：sleep(100ms) 实际 100-110 ms，jitter < 10 ms
重负载（~100k QPS，CPU 90%）：sleep(100ms) 实际 100-200 ms，jitter 可达 100 ms
超载（CPU 100%）：timer 可能延迟几秒——worker 忙得顾不上处理 timer 到期

负载越重、timer 精度越差——这是协作式调度的自然后果。Tokio 不会抢占正在跑的 Task 来 fire timer。

这对 "基于 timer 的限流" 有影响：如果你用 tokio::time::interval 做 "每 100 ms 处理一批"，在高负载下实际频率可能降到 50 ms 或 200 ms。不要假设 timer 频率精确。

为什么 Tokio 用 ms 而不是 ns 作为 elapsed 的单位

Wheel.elapsed 是 u64，单位是 ms。为什么不用纳秒（精度更高）？

u64 ms 能表示 ~5 亿年——远超任何合理 runtime 运行时间
u64 ns 只能表示 ~585 年——也够，但 u128 更安全
Tokio 的 timer 精度本来就是 ms 级——Level 0 的 slot 是 1 ms。用更细单位没意义
ms 计算开销略低——少几次位移运算

**u64 ms 是"刚刚好"**的选择。不过度精确、不浪费位宽。

timeout 的 "资源 pin" 问题

rust

let result = tokio::time::timeout(
    Duration::from_secs(5),
    long_running_future,
).await;

如果 long_running_future 超时了会发生什么？

timeout Future 的 select 里 sleep 先 Ready
long_running_future 被 drop（第 2 章讲过的 Rust 异步取消 = drop）
long_running_future 持有的所有资源按 RAII 析构：文件、锁、db connection 等

问题：drop 不一定是瞬间完成。如果 long_running_future 内部有大量 buffer 要清理、或 drop impl 本身有 I/O（比如 async Drop 的 workaround——同步 drop 里调 blocking flush），drop 本身可能阻塞。

在 multi_thread runtime 下这影响小：drop 阻塞只影响当前 worker。在 current_thread 或 LocalSet 下可能阻塞整个 runtime。

最佳实践：

写 Drop impl 时避免阻塞操作
如果必须阻塞（比如 flush），考虑 spawn_blocking
对于敏感服务，用 tokio::select! 手动控制 drop 时机而非依赖 timeout

`start_paused` 和时钟控制：测试场景

Builder 里有个字段叫 start_paused（第 4 章提过）——它让 Time Driver 启动时时钟暂停。结合 tokio::time::advance(Duration) 手动推进时钟，你可以在测试里"瞬间"把时间跳到 100 小时后、不需要真等。

rust

#[tokio::test(start_paused = true)]
async fn test_after_one_hour() {
    let handle = tokio::spawn(async {
        tokio::time::sleep(Duration::from_secs(3600)).await;
        "done"
    });
    
    // 瞬间把时间推进 1 小时
    tokio::time::advance(Duration::from_secs(3600)).await;
    
    assert_eq!(handle.await.unwrap(), "done");
}

测试时间相关代码的神器——不用真等 1 小时、测试瞬间完成、定时器逻辑被完整验证。

这个能力依赖 Time Driver 的"虚拟时钟"：advance 实际上是直接调整 Wheel.elapsed、触发所有到期的 timer。因为 timer 的到期逻辑不依赖真实时钟（全依赖 elapsed），可以完美模拟时间流逝。

如果 Tokio 用 heap + std::time::Instant 直接比较，这个测试能力做不到——你不能让 std::time 倒流。时间轮 + elapsed 计数的设计让虚拟时钟成为可能。架构决定可能性。

Tokio Time Driver 为什么不独立线程

你可能会问：为什么 Time Driver 不跑一个独立线程？专门负责时间推进——似乎更简单。

答案是 共享 epoll_wait 的经济性：

如果 Time Driver 独立线程，它要 sleep 到下一个 timer 到期——用 std::thread::sleep 或 clock_nanosleep
Main worker 线程在 epoll_wait 等 I/O 事件
两个线程各自阻塞 —— 至少 2 个活跃线程
每次 timer 到期，独立线程 wake 后要通过某种机制通知 worker（mio::Waker 或 channel）——多一次跨线程通信

合并成一个 epoll_wait 后：

Worker 线程既等 I/O 又等 timer——一个阻塞点
timer 到期 = epoll_wait 的 timeout 过期 = 自然唤醒
零跨线程通信

**这种 "multiplex"（复用）**是系统编程的经典优化——一个等待点等多种事件，比多个等待点并联高效。Tokio、Linux kernel、Node.js libuv 全走这条路。

Tokio Time Driver 对工作线程的隐性约束

有一个鲜有讨论的点：Time Driver 的 park 被某个 worker 调用（第 5 章讲过的 work-stealing scheduler），但不是所有 worker 同时 park。具体：

一个 worker 成为 "driver leader" 负责 turn(timeout)
其他 worker 在 sleep 等 leader 的通知
leader 醒来后处理事件、其他 worker 被 unparked 接管 Task

这意味着 Time Driver 不 scale linearly——不管多少 worker，只有一个在真的 turn。对超大型服务（32+ 核），Time Driver 可能成为单点瓶颈。Tokio 1.28 的 sharding 就是为了缓解这个——把 wheel 拆开让多个 worker 可以并行处理 timer。

但 leader 本身仍然是单点。极端场景下（每秒几百万 timer）可能见到 leader worker CPU 100% 而其他 worker 相对空闲。这是 Tokio 当前架构的一个微小但真实的限制。

11.7 精度问题：sleep 真能精确 1 ms 吗

Tokio sleep 的实际精度不是 1 ms——而是最多 1 ms 延迟（平均约 0.5 ms，有时几微秒，有时几毫秒）。为什么：

Wheel Level 0 的 slot 是 1 ms——理论最小精度 1 ms
但 epoll_wait 的 timeout 也是 1 ms 精度（第 9 章）
OS 调度延迟：即使 epoll_wait 超时返回，worker 线程可能被其他线程抢占，延迟几微秒到几十微秒
Tokio 的 tick 节奏：worker 每 event_interval 次才 check 一次 time——额外延迟

综合下来，sleep(1ms) 实际可能 0.8 ms 到 3 ms 之间——足够满足 99% 场景，不适合亚毫秒级定时。

如果你需要更高精度：

使用 tokio::time::interval + Duration::from_micros —— 精度仍然受限，但更稳
极致精度：直接 std::thread::park_timeout + 内核 clock_nanosleep（绕过 Tokio）
更激进：硬实时调度（SCHED_FIFO）+ 自旋忙等

对 HTTP 服务、数据库超时、心跳——1-3 ms 精度足够。别过度要求。

11.7½ Tokio 1.28 的时间轮 sharding 改造

Tokio 1.28（2023 年 6 月）引入了 timer wheel 的 sharding——把一个全局 Wheel 拆成多个 shard，每个 shard 独立锁。默认 shard 数 = CPU 核数。

为什么要 shard：

Tokio 1.27 之前，全局只有一个 Wheel + 一个 Mutex
高并发插入 timer（比如每个连接一个 30 秒超时）时，所有插入都抢这一个锁
基准测试显示 100 万 timer 场景下锁竞争占用 30%+ CPU

sharding 后：

每 timer 根据某个 hash 分派到 shard
多个 shard 可以并行插入——锁竞争大幅降低
代价是：next_expiration 要查所有 shard 找最早的——每次 scheduling 决策多一点点开销

这是一个典型的"锁粒度细化"优化。同样的思路在很多并发数据结构里见过：ConcurrentHashMap（Java 8 前 segment 分片）、Redis cluster slot、数据库的 partition。基本盘是同一个：用多个小锁代替一个大锁。

Tokio 1.28 基准数据：100 万 timer 的插入吞吐提升约 40%。对超大型服务（百万 WS 连接）可见。小团队服务感受不到差异——但 Tokio 宁愿做了也不留短板。

11.8 与其他书的关联

本章讲的 "多层分桶 + 位运算查询"设计，和 《vLLM 推理内核深度解析》第 5 章（KV Cache 管理） 里的 PagedAttention 用多层 block + 位图索引管理 GPU 显存是同构的。两者都是"用分层结构把 O(N) 查找压到 O(1)"的典范。

《Rust 编译器与运行时揭秘》第 15 章（MIR 优化 Pass） 里的"算法复杂度 vs 常数因子"讨论直接适用——分层时间轮在理论上和 heap 都是"摊销 O(1)"级别，但常数因子差 10x——这是工业级代码和"还行" 代码的分水岭。

11.8½ tokio::time 常用 API 一览

除了 sleep，Tokio 还基于 Time Driver 提供一组丰富 API：

sleep(duration)：sleep 一段时间
sleep_until(instant)：sleep 到某个具体时刻
interval(period)：周期性唤醒（定时器）—— 返回 Interval 类型，.tick().await 等下一次周期
timeout(duration, future)：给 future 设超时——超过时间返回 TimeoutError
timeout_at(instant, future)：超时到某个具体时刻
sleep_until(instant)：sleep 到具体时刻

Timeout 是最常用的——几乎所有 HTTP client / DB query 都会用：

rust

let resp = tokio::time::timeout(
    Duration::from_secs(30),
    reqwest::get("http://example.com")
).await;

match resp {
    Ok(Ok(response)) => { /* 30 秒内拿到响应 */ }
    Ok(Err(e)) => { /* 请求本身出错 */ }
    Err(_) => { /* 超时 */ }
}

timeout 内部用 select! 组合 sleep 和用户 future——到期先 Ready 的那个 dominate。基于 Time Driver 的一个 sleep + I/O Driver 的等数据——两个 Driver 协作的典型案例。

Interval 的常见陷阱

rust

let mut interval = tokio::time::interval(Duration::from_secs(1));
loop {
    interval.tick().await;
    // 每秒执行一次...但不精确
    do_work().await;
}

注意：如果 do_work() 耗时 >1 秒，interval 会 catch up——下次 tick 立刻触发（没有延迟补偿）。如果你想要"固定间隔、跳过错过的 tick"，用 interval.set_missed_tick_behavior(MissedTickBehavior::Delay) 改变策略。

这类细节容易踩坑——第 19 章陷阱清单里会专门讲。

11.8½ 一个真实 timer bug：级联时 timer 丢失

2020 年 Tokio 社区报告过一个罕见 bug：特定条件下，一个 timer 在级联时会被丢失。根本原因是级联逻辑里一处 bit 操作的 off-by-one。

复现条件：

Wheel.elapsed 恰好在 Level 1 的 slot 0-1 边界
此时 Level 1 的 slot 0 里有一个 timer
级联时应该把它 move 到 Level 0 的某个 slot，但逻辑里把 offset 算错了一个 bit
timer 被 move 到错的 Level 0 slot——最终 next_expiration 永远找不到它、timer 永远不 fire

Loom 和单元测试没发现：因为这个 bug 依赖精确的时间边界和特定 slot 组合——覆盖起来很难。

发现和修复：一个生产用户报告"有些 timer 偶尔不 fire"——花了两周才定位。最终修复只有 3 行代码的改动。

这个故事的教训：

底层数据结构的正确性极难完全验证——即使有 Loom + 千万行测试，边界条件仍可能漏
生产反馈永远是最后防线——没有用户能帮你发现真实世界的 bug
小改动可能修大问题——最终的 fix 通常 lines-of-code 很小，难的是定位

这类 bug 让你对"生产软件的可靠性"有更现实的认识——没有所谓"100% 正确"，只有"在已知条件下正确 + 遇到新问题快速修复"。Tokio 在这件事上做得极好——问题反馈到修复通常几天之内。这是工业级软件的基础服务水平。

11.9 本章小结

到这里你对时间轮的理解应该到了"可以自己实现"的程度

如果给你 4 小时，你能从零实现一个分层时间轮吗？试试看：

Step 1：定义结构

rust

const NUM_LEVELS: usize = 6;
const LEVEL_MULT: usize = 64;

struct Wheel {
    elapsed: u64,
    levels: Box<[Level; NUM_LEVELS]>,
}

struct Level {
    level: usize,
    occupied: u64,
    slot: [VecDeque<Timer>; LEVEL_MULT],
}

Step 2：实现 insert(when, timer)

算 level = 63 - (distance | 63).leading_zeros() / 6
算 slot = (when >> (level * 6)) & 0x3F
push_back 到 slot

Step 3：实现 advance(now)（时间流逝）

如果 now 在当前 Level 0 的某个 slot 里、触发对应 timer
Level 0 走完 64 ms 后、触发 Level 1 的级联
以此类推

Step 4：实现 next_expiration() -> Option<Instant>

遍历每层、找 occupied.trailing_zeros()
算 deadline 返回

做完这 4 步你就有了一个能跑的分层时间轮。Tokio 多出来的部分是：

侵入式链表代替 VecDeque（零分配）
Shard 支持
和 I/O Driver 的 park 集成
虚拟时钟（start_paused）
各种 edge case 处理（wraparound、cancel、overflow）

核心 4 步你能做出来——这个"我能自己做出来"的感觉是真正掌握一个技术的标志。

11.9 本章小结

带走三件事：

Tokio 用 6 层 × 64 slot 的分层时间轮管理所有 timer——从 1 ms 精度到 2 年范围。每层精度是上一层的 64 倍、Box<[Level; 6]> + 固定大小数组的内存布局精打细算
插入 O(1)、查下一个到期 O(1)、级联摊销 O(1)——整个数据结构的每一个操作都是常数时间
Time Driver 和 I/O Driver 共享一次 epoll_wait——timeout 参数复用，一个系统调用完成两件事。没有独立 timer 线程、没有跨线程通信、一个阻塞点等所有事件——multiplex 的经典应用

第 11 章给你的工具箱增量

读完本章你应该把以下工具加进你的设计工具箱：

分层数据结构：用多层 bucket 解决"范围 vs 精度"trade-off
位运算定位：shift + mask 比除法 / 取模快 5-10 倍，要用
bitmap + trailing_zeros：O(1) 找占用的最低 bit —— 很多调度问题都能用
摊销分析：某些操作看起来 O(N) 但生命周期平摊 O(1)——设计时考虑
multiplex 一个等待点：多种事件共享 epoll_wait 的 timeout 参数——减少阻塞点

这五个工具适用面远超 timer——你在写自己的并发 / 调度 / 存储数据结构时会反复用到。

一个收尾的小故事

Carl Lerche 在 2020 年前后一次 Rust 分享里说："The timer wheel was the thing I was most worried about getting wrong."（时间轮是我最担心做错的东西。）

这句话很有启发。一个看起来"只是数据结构"的东西，在 runtime 作者心里是最重的一块——因为：

错误隐蔽（timer 不 fire 很难发现）
性能关键（百万 timer 下主循环成本）
正确性复杂（级联 + 边界 + 并发）

认真对待看似简单的东西——这是基础设施工程师和应用工程师最大的思维区别。Tokio 的时间轮花了 5 年打磨到现在的形态，每一次重构都是为了更扎实。

一个鲜为人知的细节：Tokio 时钟漂移

Tokio 的 elapsed 基于 Instant::now() —— Linux 上底层是 clock_gettime(CLOCK_MONOTONIC)。这是单调时钟——保证永远递增、即使系统时间被 admin 调过。

但 CLOCK_MONOTONIC 本身不保证精确：

硬件晶振有 ppm 级误差（每天几秒）
系统调度延迟导致 clock_gettime 调用本身有抖动
虚拟机中时钟可能会"跳过"（host 调度 VM 不均匀）

对 Tokio 的影响：

短时间（几秒）内，时钟基本准确
长时间（一天），可能累积 1-2 秒误差
VM 环境更糟，偶尔看到"sleep 1 秒实际 3 秒"的异常

生产环境建议：

不要依赖 sleep 的精确时间完成重要事件 —— 关键任务用 NTP 同步后的 wall clock、而不是 Tokio 的 Instant
VM 内部跑 Tokio 注意时钟同步（chrony / ntpd）
长期 sleep（小时级）完成后重新校准——不要假设"我 sleep 了 N 毫秒"

这些不是 Tokio 的 bug——是 OS / 虚拟化层面的物理现实。理解它让你的服务更可靠。

一个对比：Tokio 和 Go runtime 的 timer

Go runtime（1.14+）的 timer 实现历史非常有意思：

1.9 以前用全局堆（heap）+ 单一 timerproc goroutine——单点瓶颈
1.10 改成每 P（逻辑处理器）一个本地堆——消除瓶颈但实现复杂
1.14 改成 "network poller 集成 timer"——timer 直接通过 netpoll 的 timeout 驱动、不需要独立 timerproc

Go 1.14 的做法和 Tokio 的"Time Driver 共享 epoll_wait"完全同构——两者都意识到 "把 timer 挂到 network poller 上"比独立 timer 线程更高效。两个世界独立得出同一个结论。

这是跨生态的收敛——好的设计会自然被不同实现发现。Tokio 的 Time Driver 设计不是独创的奇思妙想，是系统设计演化到成熟期的自然答案。读懂它不只是读懂 Tokio——你同时读懂了 Go runtime 相关模块、Linux kernel 的 timerfd+epoll 用法。

下一章我们进入 Tokio 的同步原语——tokio::sync::Mutex / RwLock / Semaphore。你会看到为什么 Tokio 的 Mutex 是公平锁、为什么它性能有时比 std::Mutex 慢但更可预测、Semaphore 如何成为其他所有同步原语的基础 building block。

延伸阅读

Tokio 源码：tokio/src/runtime/time/wheel/mod.rs
Tokio 源码：tokio/src/runtime/time/wheel/level.rs
Varghese & Lauck, "Hashed and Hierarchical Timing Wheels" (1987) —— 原始论文
Linux kernel timer 实现（2.6 后引入类似分层时间轮）
《vLLM 推理内核深度解析》第 5 章：PagedAttention 的分层索引对比

第11章 Time Driver 与分层定时器轮 ​

11.0½ 从一个朴素问题开始 ​

11.1 为什么异步运行时需要"特殊"的定时器结构 ​

真实世界的其他时间轮实现 ​

时间轮的原创论文 ​

11.2 Wheel 结构：6 层 + 64 slot/层 ​

Level 结构 ​

层级范围的层层放大 ​

每层 "精度"和 "范围" 的对数关系 ​

Box<[Level; 6]> 而不是 Vec<Level> ​

11.3 insert：插入一个定时器 ​

level_for(when)：位运算选层 ​

add_entry：把 timer 塞进 slot ​

slot_for：位运算定位 slot ​

cached_when：timer 的关键优化 ​

插入后的 elapsed 保持不变 ​

11.4 取下一个到期：bitmap + trailing_zeros ​

为什么 occupied 是 u64 而不是 u128 或数组 ​

和 BinaryHeap 对比 ​

EntryList 是侵入式链表 ​

11.5 时间流逝：级联降级 ​

为什么级联是 O(1) 摊销 ​

11.5½ 一个完整级联例子：逐毫秒走 10 分钟 ​

为什么是 64 而不是 128 或 32？ ​

11.6 Time Driver 与 I/O Driver 的协作 ​

park 的协作流程 ​

process_at_time 的简洁 ​

tokio::time::sleep 的真实开销 ​

Tokio 1.40 的 sleep 精度在不同负载下的表现 ​

为什么 Tokio 用 ms 而不是 ns 作为 elapsed 的单位 ​

timeout 的 "资源 pin" 问题 ​

start_paused 和时钟控制：测试场景 ​

Tokio Time Driver 为什么不独立线程 ​

Tokio Time Driver 对工作线程的隐性约束 ​

11.7 精度问题：sleep 真能精确 1 ms 吗 ​

11.7½ Tokio 1.28 的时间轮 sharding 改造 ​

11.8 与其他书的关联 ​

11.8½ tokio::time 常用 API 一览 ​

Interval 的常见陷阱 ​

11.8½ 一个真实 timer bug：级联时 timer 丢失 ​

11.9 本章小结 ​

到这里你对时间轮的理解应该到了"可以自己实现"的程度 ​

11.9 本章小结 ​

第 11 章给你的工具箱增量 ​

一个收尾的小故事 ​

一个鲜为人知的细节：Tokio 时钟漂移 ​

一个对比：Tokio 和 Go runtime 的 timer ​

第11章 Time Driver 与分层定时器轮

11.0½ 从一个朴素问题开始

11.1 为什么异步运行时需要"特殊"的定时器结构

真实世界的其他时间轮实现

时间轮的原创论文

11.2 `Wheel` 结构：6 层 + 64 slot/层

Level 结构

层级范围的层层放大

每层 "精度"和 "范围" 的对数关系

`Box<[Level; 6]>` 而不是 `Vec<Level>`

11.3 `insert`：插入一个定时器

`level_for(when)`：位运算选层

`add_entry`：把 timer 塞进 slot

`slot_for`：位运算定位 slot

cached_when：timer 的关键优化

插入后的 `elapsed` 保持不变

11.4 取下一个到期：bitmap + `trailing_zeros`

为什么 `occupied` 是 u64 而不是 u128 或数组

和 BinaryHeap 对比

EntryList 是侵入式链表

11.5 时间流逝：级联降级

为什么级联是 O(1) 摊销

11.5½ 一个完整级联例子：逐毫秒走 10 分钟

为什么是 64 而不是 128 或 32？

11.6 Time Driver 与 I/O Driver 的协作

park 的协作流程

`process_at_time` 的简洁

tokio::time::sleep 的真实开销

Tokio 1.40 的 sleep 精度在不同负载下的表现

为什么 Tokio 用 ms 而不是 ns 作为 elapsed 的单位

timeout 的 "资源 pin" 问题

`start_paused` 和时钟控制：测试场景

Tokio Time Driver 为什么不独立线程

Tokio Time Driver 对工作线程的隐性约束

11.7 精度问题：sleep 真能精确 1 ms 吗

11.7½ Tokio 1.28 的时间轮 sharding 改造

11.8 与其他书的关联

11.8½ tokio::time 常用 API 一览

Interval 的常见陷阱

11.8½ 一个真实 timer bug：级联时 timer 丢失

11.9 本章小结

到这里你对时间轮的理解应该到了"可以自己实现"的程度

11.9 本章小结

第 11 章给你的工具箱增量

一个收尾的小故事

一个鲜为人知的细节：Tokio 时钟漂移

一个对比：Tokio 和 Go runtime 的 timer