Tokio 源码深度解析

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

作者杨艺韬 · 15,452 字 · 发布于 2026-04-19 · 更新于 2026-09-24

本章要点

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 指令秒找
时间流逝 = 时间走到某个高层非空 slot 的起点时，把里面的定时器按剩余时间"降级"到更低层——级联展开
为什么不用 BinaryHeap：堆插入 / 取下一个都是 O(log N)——在百万定时器场景下明显慢于时间轮的 O(1)

11.1 从一个朴素问题开始

"实现一个定时器有什么难？"——这是很多没做过运行时的人的第一反应。但真正动手做一个"支持几十万 timer 并发 + 插入/取消/到期都是 O(log N) 或更快"的 timer、你会发现它几乎和设计一个数据库索引一样复杂。本节从一个朴素的 sleep(100ms) 需求出发、一步步推导"为什么朴素实现撑不住"——让你在心里对"分层时间轮为什么这么设计"建立动机感。

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

方案 A：一个线程 + 循环 sleep 每次 tokio::time::sleep(1秒) 就 spawn 一个线程调 std::thread::sleep(1秒)。能跑但疯狂浪费——一个连接一个线程，几千连接就几千线程，内存和调度开销迅速失控。

方案 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 的每一跳都是复杂度量级的改善（线程数 → O(N) 扫描 → O(log N) → O(1)）。Tokio 选 D 并不是玩花样——而是在"大量连接 + 每连接一个 timer"的工业场景下的自然选择。

有一个常常被忽略的思考：为什么 Linux 内核、Netty、Kafka、Tokio 这些顶级项目都用同一类数据结构（时间轮；Netty 是单层，其余是分层）？答案是——在"高频创建/销毁 + 大量并发 + 按时间排序 + 毫秒精度就够"这四个约束下、分层时间轮能把插入、取消、找下一个到期都做成与定时器总数无关的常数成本。其他数据结构各有优势，但在这四个约束的组合下，这个性质让分层时间轮成了主流选择。这是"问题的特定约束塑造最优数据结构"的典型案例——它提醒我们：数据结构选择不能脱离具体约束、"最优"是和"为什么最优"共同定义的。

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

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

"定时器"听起来是个简单需求——"5 秒后叫我"——但在异步运行时里面、这个简单需求有两个让人难以预料的规模挑战：（1）高频创建销毁——每个 HTTP 请求都有 timeout、每个 session 都有 heartbeat、一个 busy 服务每秒可能创建几千个 timer；（2）海量并发——一个 long-lived 连接服务（聊天、游戏）可能同时有几十万个活 timer。这两个挑战让"朴素最小堆"之类的数据结构撑不住——需要专门设计的数据结构。

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

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

数据结构是什么？几个候选——每个都有不同的 trade-off，读下面的对比你会看到数据结构选择对定时器性能的决定性影响。这种"同一个需求对应多个候选数据结构"的对比是工程素养的重要训练——你不应该只知道一种实现、而应该能比较多种实现的优劣。

几个候选：

无序 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、Linux 内核、Kafka 等的选择

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

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

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

Linux kernel 的 timer 子系统（Linux 内核官方仓库里 timer 子系统的源码）也用多层时间轮——每层 64 slot，HZ > 100 时 9 层、否则 8 层，Level 0 精度 1 jiffy（通常 1 ms 或 4 ms）。但它的范围反而比 Tokio 短：HZ=1000 时最后一层只到约 12 天（HZ=100 时约 15 天），更远的 timer 被强制按最后一层的最大超时到期；而且它不再做级联——源码注释写的是 "We don't have cascading anymore"，越高层粒度越粗，靠粒度本身做隐式批处理。

为什么两者取舍不同：内核里的 timer 绝大多数是会被取消的超时，允许远期 timer 精度变粗，换掉了级联的开销；Tokio 则让每个 timer 最终级联到 Level 0、按毫秒触发，6 层覆盖到约 2 年，再加层只是白白多占常驻内存（每层是 64 个侵入式链表头，Level 结构本身就是 KB 量级）。两者设计都是场景驱动的。

Netty（Java 异步网络框架）的 HashedWheelTimer 是一个单层时间轮——精度固定（默认 tick 100 ms、一圈 512 格）。没用分层：超过一圈的 timer 记下剩余圈数，不需要多层也能表示任意远的到期时间。

Netty 的决策背后：

默认 100 ms 精度对 HTTP / gRPC 超时足够
单层简化实现（没有 cascade 逻辑）
超过一圈的 timer 用 remainingRounds 记剩余圈数，每转到它所在的格子减一——远期 timer 会被反复检查，效率略低但接受
Java 的 GC 让"大数组常驻内存"成本比 Rust 高——分层会加剧 GC 压力

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

libuv（Node.js）用最小堆——uv_timer_t 基于 binary heap。每次插入 / pop 都是 O(log N)。这在 Node 场景下问题不大——Node 的 JS 层还会把相同时长的 setTimeout 归进同一条链表、所有 JS timer 共用一个底层 libuv 定时器，真正压到堆上的元素并不多。

Tokio 场景和 Node 不同：

Rust 后端服务常要扛海量并发连接
每个连接至少一个 timer（读超时）
这些 timer 直接进运行时的定时器结构、没有 JS 层那种按时长归并。最小堆胜在实现简单，但在百万 timer 下明显弱于时间轮；Node 的做法在它自己的场景里，简单实现的代价可以接受。

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

时间轮的原创论文

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

论文发表在 1987 年的 SOSP 上（作者当时都在 DEC），针对的正是"操作系统里要同时维护海量定时器"这一类问题——而几十年后 Tokio / Linux kernel / Netty 仍在用他们的算法。好算法的生命力。

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

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

分层时间轮是一个非常漂亮的数据结构——它的灵感来自"模拟手表"：秒针、分针、时针、日历。秒针每秒走一格、满 60 格推动分针走一格、满 60 分推动时针走一格……Tokio 的 wheel 用同样的思路：最内层的 slot 每毫秒移动、满 64 毫秒推动第二层、满 64 × 64 毫秒推动第三层……。这种"级联"设计让"查找下一个到期 timer"变成常数级的位操作（最多扫 6 层、每层一条 trailing_zeros）、而不是 O(N) 的线性扫描。

为什么层数选 6 / 每层 slot 数选 64？——这两个魔法数不是随意的。6 层 × 64 slot/层 = 64^6 = 2^36 毫秒 ≈ 800 天——这是 Tokio 能表示的最长 timer 时间。800 天足够任何真实应用（service 的 session timeout 通常最长几小时、几天已经极端）。64 slot 正好是一个 64 位 bitmap 一个字长——让 trailing_zeros CPU 指令能直接操作。两个选择的组合给了 Tokio "轻量级覆盖 + CPU 原生优化"的双重好处。

打开 tokio/src/runtime/time/wheel/mod.rs（省略注释）：

// 来源：tokio-rs/tokio · tokio/src/runtime/time/wheel/mod.rs:24（常量在 tokio/src/runtime/time/wheel/mod.rs:47 与 tokio/src/runtime/time/wheel/mod.rs:50）
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（tokio/src/runtime/time/wheel/mod.rs:26）：已经流逝的时间（单位毫秒），从 runtime 启动算起
levels: Box<[Level; 6]>（tokio/src/runtime/time/wheel/mod.rs:38）：6 层时间轮
pending: EntryList（tokio/src/runtime/time/wheel/mod.rs:41）：已经到期但还没 fire 的 timer 缓存（EntryList 是侵入式链表）

NUM_LEVELS = 6：6 层。**MAX_DURATION = 2^(6*6) - 1 = 2^36 - 1 ≈ 68.7 billion ms ≈ 2.18 年**。注意**超出这个范围的 timer 并不会被拒绝**——InsertError只有Elapsed 一个变体（tokio/src/time/error.rs:50），insert只在「已经过期」时报错；更长的 deadline 先被instant_to_tick钳到MAX_SAFE_MILLIS_DURATION（tokio/src/runtime/time/source.rs:29），再由 level_for里那个if masked >= MAX_DURATION 分支塞进最高层（tokio/src/runtime/time/wheel/mod.rs:283`），最高层的 slot 当环形缓冲反复转。总之 2 年对任何合理服务来说都够了。

Level 结构

打开 level.rs：

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

const LEVEL_MULT: usize = 64;

三字段：

level: usize：这是第几层（0-5）
occupied: u64（tokio/src/runtime/time/wheel/level.rs:16）：一个 64 位 bitmap，每个 bit 代表对应 slot 是否有 entry
slot: [EntryList; 64]（tokio/src/runtime/time/wheel/level.rs:19）：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_secs(7 * 24 * 3600)) → 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 ≈ 687 亿 ms。如果每层增加 slot 数（比如 128），每层覆盖范围翻倍，但总层数无大变化。

为什么不考虑非 64 进制？ 比如 16 进制（每层 16 slot）需要更多层、32 进制需要的层数也多。64 进制在 "每层精度 vs 整层范围 vs 层数 vs bitmap 大小"四个维度之间取得了平衡：它恰好是一个 u64 bitmap 的位数，6 层就能覆盖约 2 年。

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

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

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

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

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

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

"按到期距离决定放在哪一层"这个规则看似简单、但其实用到了一个非常漂亮的位运算技巧：level = (63 - leading_zeros(elapsed ^ when)) / 6——一条 CPU 指令 + 一个除法就能算出正确的 level、不需要 if/else 链判断。这种"把业务逻辑压缩到位运算"的风格在 Tokio hot path 上无处不在——每 CPU 指令都精打细算。初看觉得代码难读、读熟后会被这种精炼的美学打动。

往 wheel 里插入一个 timer 的逻辑是：计算到期时间距离现在多少毫秒 → 根据这个距离决定放到哪一层的哪个 slot。距离越近放越内层（精度高）、距离越远放越外层（精度低、但容量大）。这种"按到期距离分层"的策略让每一层只需要处理对应精度级别的 timer——内层 slot 数量少但高频翻转、外层 slot 数量大但低频翻转。整个 wheel 的信息密度因此达到了最优。

代码如下（省略注释与 debug_assert!）：

// 来源：tokio/src/runtime/time/wheel/mod.rs:89
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 是一个自由函数（tokio/src/runtime/time/wheel/mod.rs:276；Wheel 上那个同名方法在 tokio/src/runtime/time/wheel/mod.rs:271 转调它），原样：

// 来源：tokio/src/runtime/time/wheel/mod.rs:276
fn level_for(elapsed: u64, when: u64) -> usize {
    const SLOT_MASK: u64 = (1 << 6) - 1;

    // Mask in the trailing bits ignored by the level calculation in order to cap
    // the possible leading zeros
    let mut masked = elapsed ^ when | SLOT_MASK;

    if masked >= MAX_DURATION {
        // Fudge the timer into the top level
        masked = MAX_DURATION - 1;
    }

    let leading_zeros = masked.leading_zeros() as usize;
    let significant = 63 - leading_zeros;

    significant / NUM_LEVELS
}

注意这里是 elapsed ^ when 而不是 when - elapsed——很多人第一眼会以为是"算距离"，其实它算的是"elapsed 和 when 从第几个 6-bit 段开始分岔"。这正是分层时间轮想要的语义：同一层里 when 和 elapsed 的高位段必须相同，一旦某段不同就得往上一层放。| SLOT_MASK 把低 6 位垫满，保证 level 至少是 0；超过 MAX_DURATION 的则被"塞"进最高层。

用 leading_zeros 一条指令算出最高有效位：

分岔位落在第 0-5 位：level 0（64 ms 以内）
落在第 6-11 位：level 1（64 × 64 ms 以内）
落在第 12-17 位：level 2
……以此类推，significant / 6 就是层号

一次异或 + leading_zeros + 除法决定层号，没有任何分支链。

`add_entry`：把 timer 塞进 slot

原样：

// 来源：tokio/src/runtime/time/wheel/level.rs:122
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)（occupied_bit 在 tokio/src/runtime/time/wheel/level.rs:158）：在 bitmap 里把对应 bit 置 1

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

`slot_for`：位运算定位 slot

slot_for(duration, level) 的原样：

// 来源：tokio/src/runtime/time/wheel/level.rs:171
/// Converts a duration (milliseconds) and a level to a slot position.
fn slot_for(duration: u64, level: usize) -> usize {
    ((duration >> (level * 6)) % LEVEL_MULT as u64) as usize
}

LEVEL_MULT = 64 是 2 的幂，所以 % 64 编译后就是 & 0x3F——when 右移 level * 6 位后取低 6 位 = slot index。源码注释里专门写了一句 "Being a power of 2 is very important"（tokio/src/runtime/time/wheel/level.rs:37），说的就是这件事。

具体例子（假设 elapsed = 0）：

when = 50 → level_for 给出 level 0，(50 >> 0) % 64 = 50 → Level 0 slot 50
when = 800 → level 1（800 的最高有效位在第 9 位，9 / 6 = 1），(800 >> 6) % 64 = 12 → Level 1 slot 12
when = 300000 → level 3（最高有效位在第 18 位，18 / 6 = 3），(300000 >> 18) % 64 = 1 → Level 3 slot 1

这就是为什么 NUM_LEVELS = 6 配 LEVEL_MULT = 64——6 = log2(64)，移位量和层号严格对齐，位运算才优雅。

定位一个 slot 只是几条位运算指令——对比二叉堆插入要做 O(log N) 次比较和交换，差别在于是否随定时器总数增长。

cached_when：timer 的关键优化

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

因为定时器的"真实到期时间"（true_when）存在 StateCell 的原子字段里，reset 往后推 deadline 时可以不拿 driver 锁、直接 CAS 改掉它（extend_expiration，tokio/src/runtime/time/entry.rs:552）；而 wheel 是用 when 算出 slot 位置的——如果 wheel 里存的 entry 位置和它此刻的 true_when 对不上，删除时就找不到它所在的 slot。所以 TimerShared 额外存了一个 cached_when：

// 来源：tokio/src/runtime/time/entry.rs:395（`cached_when` 字段在 tokio/src/runtime/time/entry.rs:343，`true_when` 在 tokio/src/runtime/time/entry.rs:412）
/// Gets the true time-of-expiration value, and copies it into the cached
/// time-of-expiration value.
///
/// SAFETY: Must be called with the driver lock held, and when this entry is
/// not in any timer wheel lists.
pub(super) unsafe fn sync_when(&self) -> u64 {
    let true_when = self.true_when();
    self.cached_when.store(true_when, Ordering::Relaxed);
    true_when
}

sync_when 在即将把 entry 放进 wheel 时调用——把当时的 true_when 快照进 cached_when；此外 cached_when 只会在 entry 不在任何链表里时被改写（例如级联时 mark_pending 把新的到期 tick 写回，tokio/src/runtime/time/entry.rs:630）。所以 add_entry / remove_entry 用 cached_when 算 slot，两者必然算出同一个槽位。注释里也写明了这两个方法都必须在持有 driver 锁时调用，所以内部只用 Relaxed 序。

这是一个比"缓存加速"更重要的正确性约束：放进容器时用的 key，必须和取出时用的 key 严格一致。任何"按值定位"的侵入式容器都得处理这个问题。

插入后的 `elapsed` 保持不变

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

Wheel 的状态只在 Time Driver 的主循环被推进
插入 / 删除 / cancel 是纯修改操作——不推进时间
poll 由 Time Driver 在每次 park 醒来后调用——它通过运行时的 Clock 读当前时刻、算出新的 elapsed、处理所有到期 timer

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

相比之下，如果每次插入都要 "顺便检查过期"，代码会变成互相纠缠的分支——bug 几率飙升。这种清晰分工让 Wheel 本身的逻辑容易推理；本章末尾会看到，time: 相关的修复多半出在溢出、边界和分片并发上。

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

这里展示的技巧值得做一个可迁移的工程笔记："找最小元素"这个问题、如果集合可以编码成位图、那么用硬件 tzcnt 指令是最快的方式。现代 CPU 有专门的指令做 64 位 bitmap 的最低位查找，而用循环或 if 链做同样的事要执行数十条指令——差别在于是一条指令还是一段循环。这个技巧在内存分配器（buddy system）、CPU 任务调度器、数据库查询优化里反复出现——能把问题映射到位操作的场景、永远要考虑硬件指令优化。

这是整章最硬核的实现细节——用一个 64 位 bitmap 表示"当前层哪些 slot 非空"、用 trailing_zeros（x86 上是一条 bsf 或 tzcnt，AArch64 上是 rbit+clz 两条）找出最低位的 1。一两条 CPU 指令就能完成"找下一个到期 slot"的工作——比任何循环扫描都快得多。这种"把数据结构搜索映射到 CPU 原生位操作"是硬核系统性能优化的典型手法。

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

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

Wheel::next_expiration 的原样（tokio/src/runtime/time/wheel/mod.rs:169，去掉 debug_assert）：

// 来源：tokio/src/runtime/time/wheel/mod.rs:169
fn next_expiration(&self) -> Option<Expiration> {
    if !self.pending.is_empty() {
        // Expire immediately as we have things pending firing
        return Some(Expiration {
            level: 0,
            slot: 0,
            deadline: self.elapsed,
        });
    }

    // Check all levels
    for (level_num, level) in self.levels.iter().enumerate() {
        if let Some(expiration) = level.next_expiration(self.elapsed) {
            return Some(expiration);
        }
    }

    None
}

先看 pending：那是上一轮已经摘出来、还没 fire 完的 entry，它们的 deadline 就是当前的 elapsed，必须优先返回。之后才自下而上逐层问 Level::next_expiration（tokio/src/runtime/time/wheel/level.rs:51）。

真正用到 bitmap 的是 Level::next_occupied_slot（tokio/src/runtime/time/wheel/level.rs:108），原样：

// 来源：tokio/src/runtime/time/wheel/level.rs:108（`slot_range` 在 tokio/src/runtime/time/wheel/level.rs:162）
fn next_occupied_slot(&self, now: u64) -> Option<usize> {
    if self.occupied == 0 {
        return None;
    }

    // Get the slot for now using Maths
    let now_slot = (now / slot_range(self.level)) as usize;
    let occupied = self.occupied.rotate_right(now_slot as u32);
    let zeros = occupied.trailing_zeros() as usize;
    let slot = (zeros + now_slot) % LEVEL_MULT;

    Some(slot)
}

这里有个容易读漏的细节：不是直接 occupied.trailing_zeros()，而是先按当前所处的槽位 rotate_right 再取 trailing_zeros（tokio/src/runtime/time/wheel/level.rs:115-tokio/src/runtime/time/wheel/level.rs:116）。原因是每一层都是一个环——"最早到期"意味着"从 now_slot 开始沿环往前数遇到的第一个非空槽"，而不是"编号最小的非空槽"。rotate_right 把 now_slot 转到第 0 位，trailing_zeros 就正好数出这个环上的距离，最后再 + now_slot 转回真实槽号。

trailing_zeros() 在主流架构上只要一两条指令（x86 的 tzcnt / bsf 一条，AArch64 的 rbit + clz 两条），rotate_right 是单条 ror。最坏情况扫 6 层——层数是编译期常量、与定时器总数无关，这才是"O(1)"的真正含义。

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

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

单个 u64 的好处：

trailing_zeros() 一条 CPU 指令搞定（x86 的 bsf / tzcnt）
|= / &= 等位操作都是单条指令（occupied 只在持有分片锁时修改，本身不需要原子类型）
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)
单次操作成本随 N 增长	不增长	随 log N 增长

在 timer 数量大的场景，时间轮的优势来自"单次操作成本与总数无关"——不是常数更小，而是根本不随规模变化。对 Tokio 这种要支撑大量并发连接、每连接至少一个超时 timer 的 runtime，这个性质比任何具体数字都重要。（本机没有可复现的基准环境，这里不给绝对耗时数字。）

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 指针（TimerShared 的 pointers 字段，tokio/src/runtime/time/entry.rs:338）——插入 / 删除都是 O(1)，不管链表多长。和第 6 章的 OwnedTasks、第 8 章的 RegistrationSet 是同一家族——三个章节、同一个技术。

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

11.6 时间流逝：级联降级

级联这个操作是 Tokio 分层时间轮最容易写错的地方——也是大部分自己实现时间轮的人翻车的点。原因是它有多个边界条件：何时触发降级？降级到内层哪个 slot？降级时 slot 里的 timer 会不会多次处理？级联过程中新 insert 的 timer 落在哪？。每一个边界条件答错一点、整个数据结构就会出现 timer 丢失或多次触发的 bug。Tokio 的实现把这些边界条件都落在了 process_expiration 和 Level::next_expiration 的判断里（tokio/src/runtime/time/wheel/mod.rs:218、tokio/src/runtime/time/wheel/level.rs:51）。

级联降级是分层时间轮最精妙的机制——当外层的一个 slot 到期（比如"Level 1（每格 64 ms）的第 3 格"）、里面装着的 timer 并不是立刻触发、而是"降级"到内层的对应 slot 里（可能分散到内层的多个 slot）。这个降级保证了精度的一致性——一个 timer 无论被放到哪一层、最终都会在正确的毫秒被触发。这种"数据结构自己重组"的级联行为是整个分层时间轮算法最考验理解的部分——读源码时最容易卡在这里。

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

假设 Wheel.elapsed = 0 时你 sleep(3 秒)——3000 ms 超出 Level 0 的 64 ms 范围、又在 Level 1 的 4096 ms 以内，所以进 Level 1（3000 >> 6 = 46，slot 46）。Level 1 里的时间精度是 64 ms——具体到 ms 精度在 Level 1 里不能直接表达。

Tokio 的做法：当时间走到 Level 1 某个非空 slot 的起点（slot k 的起点是 elapsed = 64k）时——把这个 slot 里的所有 timer 取出来、按剩余时间重新插入到 Wheel 里（process_expiration，tokio/src/runtime/time/wheel/mod.rs:218）。

重新插入时（以 slot 1、elapsed = 64 为例）：

一个原本 80 ms 的 timer（80 >> 6 = 1，本来就在 Level 1 slot 1），现在剩余 80 - 64 = 16 ms——降级到 Level 0
那个 3 秒的 timer 在 slot 46，这一次不会被碰——要等 elapsed 走到 46 × 64 = 2944 才轮到它，那时剩余 56 ms，同样降到 Level 0

这种"上层 slot 到点，里面的 timer 重新插入" 叫 cascade（级联降级）。Level 1 的 slot 每格跨 64 ms、Level 2 每格跨 4096 ms，以此类推；空 slot 由 bitmap 直接跳过——Tokio 并不逐格推进，只处理非空的 slot。

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

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

答案：任何一个具体的 timer 最多被级联 NUM_LEVELS - 1 = 5 次（每次级联至少降一层，一路降到 Level 0；超过 MAX_DURATION 被塞进最高层绕圈的 timer 除外）。摊销到 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.7 一个完整级联例子：跟着 timer 走 5 分钟

这个具体例子是本章的"教学压舱石"——它把前面 5 节讨论的所有抽象机制（插入、级联、降级、bitmap 查找）用一个具体 timer 的生命周期展示出来。我强烈建议你读这个例子时拿一张纸画一下——画出 6 层 wheel 的示意图、标出这个 timer 在每一秒 / 每一分钟 / 每一级联过程中所在的 slot 位置。画完你会对"级联"这个抽象概念有真正的肌肉记忆。

抽象讨论完了级联、这一节用一个具体例子把整个过程可视化——"插入一个 5 分钟（300 秒）后到期的 timer、看它在 wheel 里的所有 slot 里流动"。你会看到这个 timer 怎么从最外层的一个 slot、随着时间流逝一步步降级到内层、最终落到最内层的某个毫秒精度 slot 里触发。这个例子比任何抽象描述都更能帮你理解级联的工作方式。

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

初始状态（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。先算层：300000 的最高有效位在第 18 位，18 / 6 = 3 → Level 3（不是 Level 2——Level 2 整层只覆盖 64 × 4096 = 262144 ms，300000 已经溢出）。再算槽：(300000 >> 18) % 64 = 1 → Level 3 slot 1

elapsed = 50 之后：Timer A 所在的 slot 被处理——A fire、Waker 调用、Task 重 schedule。

elapsed = 64 时：概念上 Level 0 走完了一轮（0-63），但 Tokio 在这里什么也不做：

Level 1 的 slot 1（覆盖 64-127 ms）是空的，occupied 里对应 bit 为 0
next_expiration 用 bitmap 直接找到下一个非空槽——Level 1 slot 12（覆盖 12×64=768 到 831 ms），中间的空 slot 全部跳过
elapsed 也不会归零——它是全局单调递增的毫秒数，各层的槽号靠 slot_for 对它移位取模得到

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

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

elapsed = 262144 ms（约 4.37 分钟）之后：Level 3 slot 1 到点——Timer C 剩余 37856 ms，降到 Level 2 slot 9（(300000 >> 12) % 64 = 9）。之后它只在自己所在的 slot 到点时再动：elapsed = 299008 时降到 Level 1 slot 15，elapsed = 299968 时降到 Level 0 slot 32，最终在 elapsed = 300000 fire——一共级联 3 次。

每个 timer 最多被级联 NUM_LEVELS - 1 = 5 次（从它初始层一路降到 Level 0），且这个上界与 wheel 里有多少 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 一步到位。

这个数字是"刚刚好"——好处来自它与 u64 字长、6 位移位的对齐。不过别把 Tokio 的每个常量都读成精调结果：event_interval 默认的 61，源码注释自己就说 "The number 61 is fairly arbitrary. I believe this value was copied from golang."（tokio/src/runtime/builder.rs:243）。

11.8 Time Driver 与 I/O Driver 的协作

这种"一个主循环统一处理 I/O 和 Time"的设计让 Tokio 的事件循环非常纯粹——所有阻塞点只在 epoll_wait 处、没有第二个阻塞源。（libuv 其实也是同一套思路：timer 堆决定 uv__io_poll 的 timeout，并不另开线程；真正另开线程的是 java.util.Timer / ScheduledThreadPoolExecutor 那类 Java API。）Tokio 里没有一条专门跑 timer 的线程——所有 timer 存在 Time Driver 的分片 wheel 里，epoll_wait 的超时参数就是"所有分片中最近的到期时间"。这种"一处阻塞、两类事件"的设计是 Tokio 低延迟的关键支撑之一。

Tokio 只有一个主事件循环——但 Driver 有两个（I/O Driver 和 Time Driver）。怎么让它们协作？答案是：Time Driver 作为 I/O Driver 的"超时参数"。每次 worker 要阻塞等事件时、Time Driver 算出"下一个 timer 到期还有多少时间"、把这个值作为 epoll_wait 的超时参数传给 I/O Driver。这样 I/O 事件或者 timer 到期、哪个先来都能正确唤醒 worker。这种"用一个循环同时处理 I/O 和 Time"是 Tokio 相对一些其他运行时（用单独线程跑 timer）更优雅的设计。

Time Driver 的 Driver struct 非常薄（tokio/src/runtime/time/mod.rs:108）：

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

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

park 的协作流程

// 来源：tokio/src/runtime/time/mod.rs:172 与 tokio/src/runtime/time/mod.rs:176
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（tokio/src/runtime/time/mod.rs:196）的逻辑：

拿 inner.wheels 的写锁，遍历所有分片问每个 Wheel 的 next_expiration_time()、取 min()，并把结果写进 inner.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` 的简洁

// 来源：tokio/src/runtime/time/mod.rs:314
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));
}

sharding 是 tokio 1.38.0（PR #6534）才引入的——把一个 Wheel 拆成多个 shard（每 shard 一把锁），减少插入 timer 时的锁竞争。process_at_time 依次处理每个 shard 的到期 timer、取所有 shard 里最早的那个作为下次 wake time。注意它的调用方 process（tokio/src/runtime/time/mod.rs:306）会先 thread_rng_n(shards) 随机挑一个起点（tokio/src/runtime/time/mod.rs:310）——源码注释写着 "For fairness, randomly select one to start."（tokio/src/runtime/time/mod.rs:308），避免每次都从 shard 0 开始导致靠后的 shard 被系统性延后。

tokio::time::sleep 的开销由什么组成

一次 tokio::time::sleep(Duration::from_millis(100)) 的 Tokio 侧开销可以拆成三块（本机没有可复现的基准环境，这里只谈构成，不给绝对数字）：

插入 timer：一次 level_for + slot_for 位运算、一次链表 push_front、一次 bitmap |=，外加一把 shard 锁——全是常数级操作，不随 timer 总数变化
到期 fire：从 slot 摘下 entry、状态机置为已触发、waker.wake() 把 Task 推回队列
级联：只在跨过某层边界时发生，一次要把一个 slot 里的 entry 全部重新 insert——这是唯一会随"那个 slot 里有多少 timer"变化的一步，但每个 timer 一生最多被级联 5 次

结构性结论：对绝大多数服务，单个 sleep 的调度开销远小于它守护的那次业务操作（一次 HTTP 调用、一次 DB 查询），因此可以忽略。真正需要留心的是量级——如果你每秒创建的 timer 数以百万计，这些常数会累加成可观的 CPU 占用，那时才轮到 sharding 和"复用同一个 Sleep + reset"这类手段发挥价值。

sleep 精度会随负载退化

有一件事必须写在前面：Tokio 的 sleep 只保证"不早于"，不保证"不晚于"。延迟的大小取决于运行时当时在忙什么，会随负载单调变差：

空闲时：worker park 在 epoll_wait 上、超时参数正是最近的到期时刻，醒来立刻处理，延迟主要来自内核定时器精度和线程被调度回来的时间
繁忙时：worker 正在 poll 别的 task，Tokio 不会抢占正在运行的 task 去 fire timer——这个 worker 只有等当前 poll 返回，才可能去推进 driver。一个长时间不让出的 task 会拖住同 worker 上排队的其他 task；在 current_thread 运行时下，所有 timer 都得等它返回
过载时（所有 worker 持续满负荷）：到期 timer 排在队列里等着被处理，延迟可以远超设定值

这对"基于 timer 的限流 / 心跳"有直接影响：tokio::time::interval 在高负载下的实际间隔会被拉长。不要假设 timer 频率精确；心跳间隔和对端 timeout 之间要留足余量，否则一次 CPU 尖峰就可能触发误判断链。想量化自己服务上的实际抖动，唯一可靠的办法是在你自己的负载上测——任何"标称数字"都不适用。

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

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

u64 ms 能表示 ~5 亿年——远超任何合理 runtime 运行时间
u64 ns 只能表示 ~585 年——也够，但 u128 更安全
Tokio 的 timer 精度本来就是 ms 级——Level 0 的 slot 是 1 ms。用更细单位没意义
单位越粗，同样 6 层 × 64 slot 覆盖的范围越长——2^36 个 tick 按毫秒算约 2 年，按纳秒算只有约 69 秒

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

timeout 的 "资源 pin" 问题

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

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

Timeout 每次被 poll 时先 poll 内部 future、再 poll 它持有的 Sleep，这次是 Sleep 先 Ready，返回 Err(Elapsed)
Timeout 随后被 drop，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 启动时时钟暂停（需要开启 test-util feature）。结合 tokio::time::advance(Duration) 手动推进时钟，你可以在测试里"瞬间"把时间跳到 100 小时后、不需要真等。

use std::time::Duration;

#[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 小时、测试瞬间完成、定时器逻辑被完整验证。

这个能力依赖运行时的"虚拟时钟"：advance 并不直接改 Wheel，而是把 Clock 的 base 往前拨（tokio/src/time/clock.rs:295），再 yield_now 让出；driver 下次 park 醒来用 Clock 读"当前时刻"，换算成 tick 后照常处理到期 timer。因为 Time Driver 读时间只经过 Clock、不直接调 std::time::Instant::now()，可以完美模拟时间流逝。

这和底层用时间轮还是堆无关——关键是所有时间读取都经过一层可替换的时钟抽象。架构决定可能性。

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 过期 = 自然唤醒
timer 到期本身不需要跨线程通知（只有别的线程插入了比 next_wake 更早的 timer 时，才要 unpark 一下 driver，tokio/src/runtime/time/mod.rs:442-tokio/src/runtime/time/mod.rs:449）

这种 "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

这意味着"推进时间"这件事本身不随核数扩展——不管多少 worker，同一时刻只有一个在真的 turn driver。注意 1.38 的 sharding 解决的是插入侧的锁竞争（每个 worker 往自己的分片插），而处理到期仍然由持有 driver 的那个 worker 统一做——process_at_time 会遍历所有分片。

所以 driver 持有者仍然是一个串行点。极端场景下（timer 创建和到期速率都极高）可能见到持有 driver 的 worker 明显比其他 worker 忙。这是 Tokio 当前架构的一个真实但通常无关紧要的限制。

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

对"精度"有正确认知是使用任何异步运行时的基础——很多线上事故源于开发者对精度假设过度乐观。比如"每秒心跳一次"这个需求、如果开发者假设 interval(1.sec) 能精确到毫秒、在极端负载下可能发生心跳间隔抖动到 5 秒、触发 peer 的 timeout 断链、引发级联故障。理解 Tokio 精度边界能让你在真实系统里做更稳健的设计——给 timeout 留足够 buffer、不依赖严格时间顺序、用单调时钟而不是墙钟。

答案：不能。Tokio 的 sleep 只保证"不早于"，且时间单位本身就是毫秒——它给不出比 1 ms 更细的承诺，也不给延迟上界。具体误差来源有：wheel 最内层 1 毫秒精度、epoll_wait 系统调用抖动、worker 被其他 task 占住没及时 poll sleep future。理解这些误差来源能让你在真实项目里做合理预期：不要用 Tokio sleep 做硬实时任务（电机控制、音频同步）——它的设计目标是"通用后端服务的几十毫秒级 timeout"、不是嵌入式实时系统的微秒精度。

Tokio sleep 的语义是 "至少睡这么久"——只会晚、不会早。误差来自四个叠加的来源：

Wheel Level 0 的 slot 是 1 ms——wheel 内部的时间单位就是毫秒，比 1 ms 更细的差别表达不出来
等待时长和 deadline 都以整毫秒计——park_internal 的源码注释原话是 "we effectively round up to 1ms here"（tokio/src/runtime/time/mod.rs:226），为的是避免微秒级的超短等待被操作系统当成零超时；deadline 换算成 tick 时也向上取整到整毫秒——deadline_to_tick 先加 999 999 ns 再截断成毫秒（tokio/src/runtime/time/source.rs:17-tokio/src/runtime/time/source.rs:19），保证不会因取整而提前触发
epoll_wait 的 timeout 参数本身也是毫秒粒度（第 9 章），加上内核定时器精度和线程被重新调度的延迟
协作式调度：worker 必须先从当前 task 的 poll 返回，才有机会处理到期 timer

综合下来，sleep(1ms) 实际睡的时间一定 ≥ 1 ms，且在负载下可能明显更久——足够满足绝大多数后端场景，但不适合亚毫秒级定时。

如果你需要更高精度：

别指望换个 tokio::time API 解决：interval、sleep_until 走的是同一个毫秒 tick 的时间轮，传 Duration::from_micros 也会被取整到毫秒
极致精度：在专用线程里直接用 std::thread::sleep（Linux 上底层是 clock_nanosleep）或 std::thread::park_timeout（绕过 Tokio）
更激进：硬实时调度（SCHED_FIFO）+ 自旋忙等

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

11.10 tokio 1.38 的时间轮 sharding 改造

tokio 1.38.0 之前 Time Driver 只有一个全局 wheel——所有线程的 timer 都插到这里。这在 timer 高频创建的场景下是锁争用热点。PR #6534 改造了这个设计——按 worker 线程分 shard、每个 shard 自己一份 wheel。这个改造是典型的"从全局锁到分片锁"优化模式——在数据库、文件系统、并发集合库里到处都能看到。

sharding 在 tokio 1.38.0（2024 年 5 月 30 日） 落地。分片数在 tokio/src/runtime/driver.rs:53 里就是 cfg.workers（字段定义在 tokio/src/runtime/driver.rs:43，传进 time::Driver::new 在 tokio/src/runtime/driver.rs:314）——等于运行时的 worker 线程数（多线程运行时默认取 CPU 核数）。

为什么要 shard：

1.38 之前全局只有一个 Wheel + 一把锁
高并发插入 timer（比如每个连接一个 30 秒超时）时，所有插入都抢这一把锁
大量 timer 场景下，锁竞争会成为主要 CPU 热点

sharding 后（tokio/src/runtime/time/entry.rs:661 的 generate_shard_id）：

worker 线程用自己的 worker index 当 shard id（tokio/src/runtime/time/entry.rs:665；current_thread 运行时固定为 0，tokio/src/runtime/time/entry.rs:663），非 worker 线程则 thread_rng_n 随机取一个（tokio/src/runtime/time/entry.rs:668）——所以 worker 上创建的 timer 天然落在各自的分片里，基本不撞锁
代价是：park_internal 要拿整组分片的写锁（wheels.write()）、遍历每个 wheel 取 min 才能算出下次唤醒时刻——每次 park 多一点固定开销
分片也带来过新 bug：1.38.1 就修了一个"没有在持有全部分片锁的情况下更新 wake_up，导致定时器不触发"的问题（#6683）

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

这次改造的工程价值：timer 插入侧的锁竞争被摊到各个 worker 上，量级越大收益越明显（比如海量长连接、每连接一个空闲超时）。中小规模服务基本感受不到差异——但 Tokio 宁愿做了也不留短板。

11.11 与其他专栏的关联

本章的分层时间轮和第 3 章 Waker、第 6 章 Task State 一样——都是"把业务逻辑压到位操作"的硬核性能优化案例。这些模式在 Tokio 里反复出现、也在 Rust 编译器、Linux 内核、数据库引擎里反复出现。读完本章你应该能识别这个"位操作优化"模式的通用特征、在自己的系统代码里看到类似机会时能想到用这套方法。

分层时间轮这个数据结构不是 Tokio 原创——它来自 Varghese 和 Lauck 在 1987 年 的论文《Hashed and Hierarchical Timing Wheels》。这篇论文已经快四十年了、至今仍是所有高性能定时器实现的理论基础。Linux 内核 timer 子系统、Java Netty 的 HashedWheelTimer、Kafka 的 purgatory 都用的是这个算法。这种"基础算法经过几十年打磨"的稳定性、是工业界大量采用的根本原因。

本章讲的侵入式链表（每个 timer 自带 prev / next，O(1) 从 slot 中间摘除），和 《vLLM 推理内核深度解析》第 5 章（KV Cache 管理：寸土寸金的显存） 里的 FreeKVCacheBlockQueue 直接复用 KVCacheBlock 自身的 prev_free_block / next_free_block 字段做双向链表是同一个思路——都是为了让"从中间摘掉一个节点"变成 O(1)、且不额外分配。

11.12 tokio::time 常用 API 一览

前面讲的都是底层数据结构、这一节回到用户层——讲 tokio::time 模块对外暴露的常用 API。sleep 只是最简单的一个——还有 interval（周期性触发）、timeout（给任何 Future 加超时）、Sleep::reset（高效重置一个已存在的 sleep）、Instant::now（获取当前时间）。这些 API 的每一个在真实服务里都有重要用途——heartbeat、grace timeout、idle detection、health check——理解它们的底层实现能让你在选 API 时做出更准确的判断。

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

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

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

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 返回的 Timeout 结构体里同时持有用户 future 和一个 Sleep（tokio/src/time/timeout.rs:161），每次 poll 先 poll 用户 future、再 poll Sleep，先 Ready 的那个决定结果。基于 Time Driver 的一个 sleep + I/O Driver 的等数据——两个 Driver 协作的典型案例。

Interval 的常见陷阱

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

注意：默认策略是 MissedTickBehavior::Burst（枚举在 tokio/src/time/interval.rs:183，Burst 在 tokio/src/time/interval.rs:242）——如果 do_work() 耗时超过一个周期，interval 会连着补齐错过的 tick（tick() 会立刻返回若干次），直到追上原本的时间表。想换行为有另外两个选项：

Delay（tokio/src/time/interval.rs:290）：源码原话是 "Tick at multiples of period from when [tick] was called, rather than"、"from start"（tokio/src/time/interval.rs:244-tokio/src/time/interval.rs:245）——以本次实际 tick 的时刻为新起点重新排，等于放弃追赶、保证两次 tick 之间至少隔一个周期
Skip（tokio/src/time/interval.rs:337）：源码原话是 "Skips missed ticks and tick on the next multiple of period from"、"start"（tokio/src/time/interval.rs:292-tokio/src/time/interval.rs:293）——丢掉错过的那些，直接跳到下一个对齐 start 的时刻，长期节奏不漂移

想要"绝不补偿、间隔恒定"用 Delay；想要"长期对齐、丢掉错过的"用 Skip。用 interval.set_missed_tick_behavior(...) 设置。

这类细节容易踩坑。

11.13 一个真实 timer bug：分片带来的"丢失的定时器"

分层时间轮加上分片之后，正确性的难点不只在数据结构本身，还在它和 park 的配合。这一节拆一个 tokio 自己踩过的、可查证的真实 bug——PR #6683，标题就叫 "time: fix race condition leading to lost timers"，在 tokio 1.38.1（2024 年 7 月 16 日） 发布，CHANGELOG 里对它的描述是"caused timers not to fire when they should"（定时器该响的时候没响）。它离引入分片的 1.38.0 只隔了一个半月——新引入的并发维度立刻带来了新的竞态。

bug 出在哪：1.38.0 的 park_internal 是这样算"下次该在什么时候醒"的——

// 1.38.0 的写法（有 bug）
let expiration_time = (0..rt_handle.time().inner.get_shard_size())
    .filter_map(|id| {
        let lock = rt_handle.time().inner.lock_sharded_wheel(id);
        lock.next_expiration_time()      // 拿到值就把这个分片的锁放掉了
    })
    .min();

rt_handle.time().inner.next_wake.store(next_wake_time(expiration_time));

注意那个闭包：lock 是闭包内的局部变量，next_expiration_time() 一返回，这个分片的锁就被释放了。于是出现一个窗口：

driver 线程读完 shard 0，放锁；继续读 shard 1、2……
就在这时，另一个 worker 往 shard 0 插入了一个很近的定时器，并按常规逻辑拿它和 next_wake 比较——读到的还是上一轮的旧值，新定时器不比它早，于是没有去 unpark driver
driver 线程算完 min（用的是过期的、不含新定时器的快照）后，把这个更晚的结果 store 进 next_wake
driver 于是按这个更晚的时刻去 park。那个新插入的定时器就"丢"了——要等到下一次有别的事件把 driver 唤醒才可能被处理

修复（PR #6683，新增 10 行、删去 5 行）：把所有分片的锁先收集起来一起持有，直到 next_wake 写完再统一释放：

let locks = (0..rt_handle.time().inner.get_shard_size())
    .map(|id| rt_handle.time().inner.lock_sharded_wheel(id))
    .collect::<Vec<_>>();

let expiration_time = locks.iter().filter_map(|lock| lock.next_expiration_time()).min();

rt_handle.time().inner.next_wake.store(next_wake_time(expiration_time));

// Safety: After updating the `next_wake`, we drop all the locks.
drop(locks);

到 1.40.0，这个不变式被固化进了类型：所有 wheel 分片放在一个 RwLock 后面，park_internal 直接 wheels.write() 拿到整体写锁再遍历（tokio/src/runtime/time/mod.rs:202-tokio/src/runtime/time/mod.rs:218）——"扫描所有分片"和"更新 next_wake"从此不可能被拆开。

这个故事的教训：

"扫描一组分片求最小值"和"把结果写回全局"必须在同一个临界区里——这是分片化时最容易漏的一条不变式，任何"分片 + 全局汇总量"的设计都会碰到
性能优化会引入新的正确性维度：1.38.0 拆锁是为了降低插入侧竞争，代价是"全局最小值"不再天然一致
修复的代码量往往极小，难的是定位——这次 fix 只动了十几行，但它对应的是"定时器偶尔不触发"这种最难复现的症状
看 CHANGELOG 是判断一个版本能不能上生产的实用手段：1.38.0 和 1.38.1 之间就隔着这个 bug

11.14 自我检验：从零实现一个时间轮

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

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

Step 1：定义结构

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：let significant = 63 - (elapsed ^ when | 63).leading_zeros() as usize; 然后 significant / 6（注意先算减法再除，别把优先级写错）
算 slot：(when >> (level * 6)) % 64
push 到该 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.15 本章小结

Time Driver 是 Tokio 里"被低估的精巧部件"——大多数用户只知道 sleep()、不知道它背后有这么一层工程。本章完整讲了它的设计动机、数据结构、实现细节、和它与 I/O Driver 的协作机制。关键 take-home：高性能定时器的核心技巧是"分层 + bitmap + 级联降级"——把 O(N) 的线性扫描转化为"层数固定、与定时器总数无关"的几条位运算。这套思路不只适用于定时器——任何"大量小任务按期触发"的场景（缓存过期、session 清理、分布式锁 lease）都可以借鉴。

带走三件事：

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
位运算定位：把 slot 数取成 2 的幂，>> / % 就会被编译成移位和掩码——分层结构因此免费获得常数级定位
bitmap + trailing_zeros：O(1) 找占用的最低 bit —— 很多调度问题都能用
摊销分析：某些操作看起来 O(N) 但生命周期平摊 O(1)——设计时考虑
multiplex 一个等待点：多种事件共享 epoll_wait 的 timeout 参数——减少阻塞点

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

一个收尾的小故事

把 tokio 的 CHANGELOG 按 time: 过滤着读一遍，是理解"这块代码有多难写对"最直接的方式：从 #4044（Instant 非单调时不要 panic）、#4495（超大 duration 的 sleep 不要 panic）、#5710（不要溢出到哨兵值）、#6487 与 #6612（Interval 的溢出检查），一直到本章讲的 #6683——几乎每一条都是溢出、边界或竞态。

一个看起来"只是数据结构"的东西，实际是 runtime 里最重的一块之一：

错误隐蔽（timer 不 fire 很难发现，往往表现为"服务偶尔卡住"）
性能关键（大量 timer 下每次 park 都要走一遍）
正确性复杂（级联 + 边界 + 并发 + 分片）

认真对待看似简单的东西——这是基础设施工程师和应用工程师最大的思维区别。

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

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

但"单调"不等于"和真实时间严格同速"：

时钟源的频率本身有 ppm 量级的偏差，长时间会累积成可观的绝对误差
clock_gettime 调用点受线程调度影响，本身带抖动
虚拟机里更糟：host 对 vCPU 的调度不均匀会让 guest 观察到的时间"跳变"

对 Tokio 的影响：短时间内 sleep 的相对时长基本可信；跨小时甚至跨天的长 sleep，它睡掉的"墙上时间"和你以为的可以对不上。

生产环境建议：

不要用 sleep 的累加来推算绝对时刻——需要绝对时刻就用（NTP 同步过的）系统时钟去判断，Instant 只用来测相对间隔
VM 内部跑 Tokio 注意宿主的时钟同步（chrony / ntpd）
长 sleep 醒来后重新读一次时钟校准——不要假设"我正好 sleep 了 N 毫秒"

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

一个对比：Tokio 和 Go runtime 的 timer

Go runtime 的 timer 实现也经历过几轮重构：早期是全局堆 + 专门的 timerproc goroutine（单点瓶颈），中间引入过多个 timer 桶来分摊锁竞争，到 Go 1.14 才把 timer 挪进每个 P、并交给 network poller 统一驱动——timerproc 就此消失。

Go 1.14 的做法和 Tokio 的"Time Driver 共享 epoll_wait"是同构的——两者都得出了 "把 timer 挂到 network poller 的 timeout 上" 比独立 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 实现（Linux 内核官方仓库里 timer 子系统的源码；当前实现是不做级联的多层时间轮）
《vLLM 推理内核深度解析》第 5 章：FreeKVCacheBlockQueue 的侵入式双向链表对比