阿男聊技术

从 tokio::time::sleep 看异步 Timer 的实现：一次从 Future::poll 到哈希时间轮的源码之旅

tokio::time::sleep 看起来和 thread::sleep 只差一个 .await，但背后连接的是一整套哈希时间轮、原子状态机和操作系统的定时唤醒机制。这篇文章从源码出发，把这条链路拆开来看。

引言：两个 sleep 的对比

在 Rust 里让程序”等一下”有两种常见方式：

// 方式一：标准库的阻塞 sleep
std::thread::sleep(Duration::from_secs(5));

// 方式二：Tokio 的异步 sleep
tokio::time::sleep(Duration::from_secs(5)).await;

从表面看，两者似乎差不多——都是在某个地方停了 5 秒。但它们在运行时的行为有本质区别。用一个简单的对比实验就能看出来。

如果把下面三个场景跑一遍：

先看场景一——在 async 任务里混入同步阻塞的版本：

// tokio_block_bad.rs
use tokio::time;
use std::time::Duration;

#[tokio::main(flavor = "current_thread")]
async fn main() {
    let start = std::time::Instant::now();

    let task1 = tokio::spawn(async move {
        println!("[任务1] 开始阻塞, 时间: {:?}", start.elapsed());
        std::thread::sleep(Duration::from_secs(5));
        println!("[任务1] 结束阻塞, 时间: {:?}", start.elapsed());
    });

    let task2 = tokio::spawn(async move {
        println!("[任务2] 开始异步等待, 时间: {:?}", start.elapsed());
        time::sleep(Duration::from_secs(2)).await;
        println!("[任务2] 结束异步等待, 时间: {:?}", start.elapsed());
    });

    let _ = tokio::join!(task1, task2);
}

运行结果：

[任务1] 开始阻塞, 时间: 32.1µs
... 卡住 5 秒，task2 根本没机会开始 ...
[任务1] 结束阻塞, 时间: 5.001s
[任务2] 开始异步等待, 时间: 5.001s
[任务2] 结束异步等待, 时间: 7.002s

task2 被 task1 的同步阻塞卡了整整 5 秒，总耗时 7 秒。

再看场景二——两个任务都用异步 sleep：

// tokio_async_good.rs
use tokio::time;
use std::time::Duration;

#[tokio::main(flavor = "current_thread")]
async fn main() {
    let start = std::time::Instant::now();

    let task1 = tokio::spawn(async move {
        println!("[任务1] 开始异步等待5秒, 时间: {:?}", start.elapsed());
        time::sleep(Duration::from_secs(5)).await;
        println!("[任务1] 结束异步等待, 时间: {:?}", start.elapsed());
    });

    let task2 = tokio::spawn(async move {
        println!("[任务2] 开始异步等待2秒, 时间: {:?}", start.elapsed());
        time::sleep(Duration::from_secs(2)).await;
        println!("[任务2] 结束异步等待, 时间: {:?}", start.elapsed());
    });

    let _ = tokio::join!(task1, task2);
}

运行结果：

[任务1] 开始异步等待5秒, 时间: 41.5µs
[任务2] 开始异步等待2秒, 时间: 43.2µs
[任务2] 结束异步等待, 时间: 2.001s
[任务1] 结束异步等待, 时间: 5.002s

总耗时 5 秒，两个任务在单线程上并发执行，互不阻塞。

场景一的 7 秒暴露了问题：当 task1 在 Tokio 的单线程 runtime 里直接调用 thread::sleep，整个工作线程都被阻塞，task2 根本得不到执行机会。而场景二的两个异步 sleep 却在单线程上实现了并发——task2 在 2 秒后准时完成。

关键不在于”等待”本身，而在于用什么方式等待。thread::sleep 把线程卡住；tokio::time::sleep 只让任务挂起，线程依然可以服务其他任务。

这篇文章的目的就是拆开 tokio::time::sleep 的内部实现，看看它到底是怎么做到的。

在进入细节之前，可以先回顾一下异步系统的基础契约。在之前的文章《Rust async/await 的底层契约：从 Future::poll 到 Tokio 运行时》¹中，我们梳理了 Future::poll、Context、Waker 组成的核心协议：任务被 poll，如果未就绪就返回 Poll::Pending 并保存 Waker，事件就绪后通过 wake() 通知运行时重新调度。sleep 正是这套协议的一个具体应用——它用”时间到达”作为就绪条件。

概念先行：从伪代码理解核心思路

在深入源码之前，先建立一个直觉。tokio::time::sleep 的秘密可以用一句话概括：它不会让线程去空等，而是注册一个”闹钟”后立刻把线程还给调度器，到时间了再由闹钟叫醒它。

具体来说，下面这行代码实际触发了 6 个步骤：

tokio::time::sleep(Duration::from_secs(5)).await;

sequenceDiagram
    participant Task as 你的任务
    participant Exec as Tokio 调度器
    participant Timer as Tokio 定时器(全局)

    Task->>Timer: 1. 注册："5秒后唤醒我"
    Task->>Exec: 2. 返回 Poll::Pending
    Exec->>Exec: 3. 切换去执行其他任务
    Note over Timer: 时钟滴答滴答...
    Timer->>Task: 4. 5秒到了，调用 Waker.wake()
    Task->>Exec: 5. 重新排队等待执行
    Exec->>Task: 6. 再次 poll，返回 Poll::Ready

如果把这个过程写成极简的伪代码，大致是这样的：

// 简化的 Sleep Future（概念示意）
struct Sleep {
    deadline: Instant,
    registered: bool,
}

impl Future for Sleep {
    type Output = ();

    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        if Instant::now() >= self.deadline {
            // 时间到了，完成
            return Poll::Ready(());
        }

        if !self.registered {
            // 时间没到：把 waker 注册到全局定时器
            // 定时器会在 deadline 时调用 waker.wake()
            let waker = cx.waker().clone();
            TOKIO_TIMER.insert(self.deadline, waker);
            self.registered = true;
        }

        // 关键：返回 Pending，交出执行权
        Poll::Pending
    }
}

核心行为只有三个：

1. 首次 poll：发现时间没到 → 把 Waker（闹钟）注册到全局定时器 → 返回 Pending，线程继续服务其他任务
2. 等待期间：零轮询、零浪费——不需要每秒检查 1000 次”时间到了吗”，定时器在精确时间点触发唤醒
3. 定时器触发：Waker::wake() 通知调度器把任务放回就绪队列，下次 poll 时返回 Ready

这和张嘴就来的 thread::sleep 有着本质区别：

有了这个心理模型，接下来就可以拆开源代码，看 Tokio 怎么把伪代码里的 TOKIO_TIMER 变成真正的数据结构。

一、Sleep 的结构：一个 Future 的解剖

tokio::time::sleep(duration) 的签名返回一个 Sleep 结构体：

pub fn sleep(duration: Duration) -> Sleep {
    // 计算 deadline = now + duration
    // 然后调用 Sleep::new_timeout(deadline, location)
}

它实现了 Future trait，所以可以 .await。但 Sleep 里面到底放了什么？核心字段如下²：

// tokio/src/time/sleep.rs: 220-232
pin_project! {
    pub struct Sleep {
        // 内部字段（tracing 相关，非关键路径）
        inner: Inner,

        // 连接 Sleep 实例和驱动它的 Timer 的关键纽带
        #[pin]
        entry: Timer,
    }
}

entry 字段的类型是 Timer，它在 tokio::runtime 内部被定义为一个 enum³：

// tokio/src/runtime/mod.rs: 437-442
pub(crate) enum Timer {
    Traditional(time::TimerEntry),
    Alternative(time_alt::Timer),  // 仅 tokio_unstable + rt-multi-thread
}

本文聚焦在 Traditional 分支——也就是默认的 Timer 实现。TimerEntry 的结构如下⁴：

// tokio/src/runtime/time/entry.rs: 287-310
pub(crate) struct TimerEntry {
    // Arc 引用到 runtime 的调度器句柄
    driver: scheduler::Handle,

    // 共享的内部结构，参与侵入式链表
    #[pin]
    inner: Option<TimerShared>,

    // deadline：首次 poll 时才注册到时间轮
    deadline: Instant,

    // 是否已经注册
    registered: bool,
}

而 TimerShared 是前端（TimerEntry）和驱动端（Driver）之间共享的状态⁵：

// tokio/src/runtime/time/entry.rs: 336-360
pub(crate) struct TimerShared {
    // 侵入式双向链表的指针
    pointers: linked_list::Pointers<TimerShared>,

    // 注册到 Wheel 时的时间（原子变量）
    registered_when: AtomicU64,

    // 当前状态：到期时间、已触发、或已注销
    state: StateCell,

    _p: PhantomPinned,
}

这几个结构的层次关系可以总结为下图：

graph TD
    A["tokio::time::sleep(duration)"] --> B["Sleep<br/>(Future)"]
    B --> C["Timer<br/>(enum)"]
    C --> D["TimerEntry<br/>(Traditional 分支)"]
    D --> E["TimerShared<br/>(共享状态)"]
    E --> F["StateCell<br/>(原子状态 + Waker)"]
    E --> G["registered_when<br/>(AtomicU64)"]
    E --> H["pointers<br/>(侵入式链表节点)"]

简单来说：用户持有的 Sleep 是一个 Future，它的内部通过 TimerEntry 管理一个 deadline，而 TimerShared 以侵入式链表节点的形式嵌入到底层的哈希时间轮（Hashed Timing Wheel）中。

二、首次 poll：注册到时间轮

当 Sleep 第一次被 poll 时，TimerEntry 还没有注册到时间轮。这时它会调用 reset，将自己插入到底层的 Wheel 数据结构中⁶：

// tokio/src/runtime/time/entry.rs: 598-617
pub(crate) fn poll_elapsed(
    mut self: Pin<&mut Self>,
    cx: &mut Context<'_>,
) -> Poll<Result<(), super::Error>> {
    if !self.registered {
        let deadline = self.deadline;
        // 首次 poll：将 deadline 注册到时间轮
        self.as_mut().reset(deadline, true);
    }

    let inner = self.inner()
        .expect("inner should already be initialized by `self.reset()`");
    // 通过 StateCell 检查是否已经到期
    inner.state.poll(cx.waker())
}

reset 的核心逻辑是：

1. 把 Instant 格式的 deadline 通过 TimeSource 转换成 u64 类型的 tick（毫秒级）
2. 先尝试原子操作 extend_expiration——如果新 deadline 比旧的晚，可以无锁更新
3. 如果 extend_expiration 失败（比如 deadline 提前了，或者 timer 已经在触发队列中），则走 reregister 路径重新插入 Wheel

这里有一个关键细节：首次注册不是在 sleep() 调用时发生的，而是在第一次 poll 时发生的。这也是为什么如果在 runtime 外部直接调用 sleep() 会 panic——它需要拿到当前的调度器句柄，而句柄只存在于 runtime 上下文中。如果把它包在一个 async block 里，调用就是惰性的，等到真正 poll 时已经在 runtime 内部了，就不会 panic⁷。

三、哈希时间轮（Hashed Timing Wheel）

Timer 的核心数据结构是一个多层哈希时间轮。Tokio 的注释明确引用了 Varghese 和 Lauck 的经典论文⁸，该论文也因 Linux 内核的高精度定时器实现而广为人知。

时间轮的核心思想很简单：把到期的定时器散列到不同的 slot 里，时钟走动时只检查当前 slot，避免每次都扫描全部定时器。

它本质上是用空间换时间：用 6 层 × 64 slot 的数组，换取每次 tick 只扫一个 slot 的能力。对比一下就能明白——如果用一个普通 Vec 或链表存储所有定时器，每次 tick 都得全量扫描一遍，O(n)；而时间轮把定时器按到期时间散列，每次 tick 只检查当前 slot，O(1)。存储只是手段，快速检索到期定时器才是时间轮存在的目的。

Tokio 使用了 6 层时间轮，每层 64 个 slot：

Level 0: 64 × 1 ms      = 64 ms 覆盖范围
Level 1: 64 × 64 ms     = ~4 秒覆盖范围
Level 2: 64 × ~4 s      = ~4 分钟覆盖范围
Level 3: 64 × ~4 min    = ~4 小时覆盖范围
Level 4: 64 × ~4 hr     = ~12 天覆盖范围
Level 5: 64 × ~12 day   = ~2 年覆盖范围

下图展示了一个简化的 3 层时间轮的工作方式：

graph LR
    subgraph "Level 2 (~4 min)"
        L2["slot 0-63<br/>每 slot ~4s"]
    end
    subgraph "Level 1 (~4 sec)"
        L1["slot 0-63<br/>每 slot 64ms"]
    end
    subgraph "Level 0 (64 ms)"
        L0["slot 0-63<br/>每 slot 1ms"]
    end

    L2 -->|"降级：slot 到期<br/>重新分配"| L1
    L1 -->|"降级"| L0
    L0 -->|"到期触发"| F["fire → wake"]

定时器首先被插入到与它的到期时间匹配的层级。比如一个 10 秒后到期的定时器，会落在 Level 2 的某个 slot 里。当该 slot 到期时，里面的所有定时器会被重新分配到 Level 1；然后再降到 Level 0；最终在 Level 0 的 slot 到期时真正触发。

这种层级设计的优势在于：

• 插入 O(1)：只需要根据到期时间算出 slot 位置
• 每 tick 的检查量很小：只处理当前 slot 内的定时器
• 覆盖范围大：6 层 64 slot 的结构可以覆盖约 2 年的时间范围，精度 1 毫秒

Wheel 结构体的关键字段⁹：

// tokio/src/runtime/time/wheel/mod.rs: 22-39
pub(crate) struct Wheel {
    // 时间轮启动以来经过的毫秒数
    elapsed: u64,

    // 6 层，每层 64 个 slot
    levels: Box<[Level; NUM_LEVELS]>,

    // 等待触发的定时器队列
    pending: EntryList,
}

四、StateCell：原子状态机

TimerShared 中最关键的部分是 StateCell——一个用原子变量实现的状态机，负责协调用户端（TimerEntry）和驱动端（Driver）之间的并发访问¹⁰：

// tokio/src/runtime/time/entry.rs: 91-102
pub(super) struct StateCell {
    // 保存到期时间，或特殊标志值 u64::MAX（已注销）
    state: AtomicU64,

    // 定时器触发后的结果
    result: UnsafeCell<TimerResult>,

    // 已注册的 Waker
    waker: AtomicWaker,
}

state 字段承载了定时器的完整生命周期：

stateDiagram-v2
    [*] --> Scheduled: set_expiration(tick)
    Scheduled --> PendingFire: mark_pending() 成功
    PendingFire --> Fired: fire(Ok(()))
    Scheduled --> Fired: 直接 fire
    Fired --> [*]: STATE_DEREGISTERED
    Scheduled --> Cancelled: cancel / deregister
    Cancelled --> [*]

几个关键操作的实现：

poll——用户端检查是否到期¹⁰：

// tokio/src/runtime/time/entry.rs: 142-162
fn poll(&self, waker: &Waker) -> Poll<TimerResult> {
    // 先注册 waker，确保 fire 和 poll 之间的竞争不会丢失唤醒
    self.waker.register_by_ref(waker);
    // 读取状态
    self.read_state()
}

fn read_state(&self) -> Poll<TimerResult> {
    let cur_state = self.state.load(Ordering::Acquire);
    if cur_state == STATE_DEREGISTERED {
        // 已经触发，读取 result
        Poll::Ready(unsafe { self.result.with(|p| *p) })
    } else {
        Poll::Pending
    }
}

注意 poll 里先注册 waker 再读状态的顺序——如果反过来，可能会发生在读状态之后、注册 waker 之前这个窗口期内定时器恰好触发并调用 fire，从而导致任务永久丢失唤醒信号。

mark_pending——驱动端将定时器移入待触发队列¹⁰：

// tokio/src/runtime/time/entry.rs: 171-199
unsafe fn mark_pending(&self, not_after: u64) -> Result<(), u64> {
    let mut cur_state = self.state.load(Ordering::Relaxed);
    loop {
        if cur_state > not_after {
            // 实际到期时间比当前 tick 晚——不应该触发
            break Err(cur_state);
        }
        match self.state.compare_exchange_weak(
            cur_state,
            STATE_PENDING_FIRE,
            Ordering::AcqRel,
            Ordering::Acquire,
        ) {
            Ok(_) => break Ok(()),
            Err(actual_state) => cur_state = actual_state,
        }
    }
}

这里使用 CAS（Compare-And-Swap）来原子地将定时器从”已调度”状态转换到”待触发”状态。CAS 失败意味着有人并发修改了状态（比如用户端重置了定时器），需要重试。

fire——完成定时器¹⁰：

// tokio/src/runtime/time/entry.rs: 211-231
unsafe fn fire(&self, result: TimerResult) -> Option<Waker> {
    let cur_state = self.state.load(Ordering::Relaxed);
    if cur_state == STATE_DEREGISTERED {
        return None;  // 已经触发过了
    }

    // 写入结果
    unsafe { self.result.with_mut(|p| *p = result) };
    // 标记为已注销
    self.state.store(STATE_DEREGISTERED, Ordering::Release);

    // 取出之前注册的 waker 以便唤醒
    self.waker.take_waker()
}

fire 返回一个 Option<Waker>，驱动端在释放锁之后调用它来唤醒等待中的任务。

五、运行时如何驱动定时器

前面讲的是 Sleep 的结构和状态管理，但这些定时器到底是怎么被驱动的？答案在运行时的主循环里。

Tokio 的 Driver::park_internal 是定时器驱动的核心入口¹¹：

// tokio/src/runtime/time/mod.rs: 213-256
fn park_internal(&mut self, rt_handle: &driver::Handle, limit: Option<Duration>) {
    let handle = rt_handle.time();
    let mut lock = handle.inner.lock();

    // 获取时间轮中最近的到期时间
    let next_wake = lock.wheel.next_expiration_time();
    lock.next_wake = next_wake.map(|t|
        NonZeroU64::new(t).unwrap_or_else(|| NonZeroU64::new(1).unwrap())
    );
    drop(lock);

    match next_wake {
        Some(when) => {
            let now = handle.time_source.now(rt_handle.clock());
            let mut duration = handle.time_source
                .tick_to_duration(when.saturating_sub(now));

            if duration > Duration::from_millis(0) {
                // 有定时器在将来才到期：带超时地 park 线程
                self.park_thread_timeout(rt_handle, duration);
            } else {
                // 有定时器已经到期或即将到期：立即返回
                self.park.park_timeout(rt_handle, Duration::from_secs(0));
            }
        }
        None => {
            // 没有定时器且有 limit：带超时 park
            // 没有定时器且没有 limit：无限期 park
        }
    }

    // 醒来后处理到期的定时器
    handle.process(rt_handle.clock());
}

流程很清晰：

sequenceDiagram
    participant RT as Runtime Worker
    participant Driver as Time Driver
    participant Wheel as Hashed Wheel
    participant OS as OS Timer

    RT->>Driver: park_internal()
    Driver->>Wheel: next_expiration_time()
    Wheel-->>Driver: Some(5000) = 5 秒后
    Driver->>OS: park_timeout(5s)
    Note over OS: 线程休眠，CPU 可服务其他任务
    OS-->>Driver: 5 秒后唤醒（或更早被 unpark）
    Driver->>Wheel: process(now)
    Wheel-->>Driver: 到期的 TimerEntry 列表
    Driver->>Driver: fire → 取出 Waker
    Driver->>RT: wake_all()
    RT->>RT: 重新 poll 对应的 Sleep Future

关键点在于：线程的休眠时间是由时间轮中最早的到期时间决定的。如果有多个 sleep 在等待，线程会以最早的 deadline 作为 park timeout；当时间到达（或被其他事件提前 unpark）后，驱动处理所有到期的定时器，批量唤醒对应的任务。

具体的处理逻辑在 Handle::process_at_time¹¹：

// tokio/src/runtime/time/mod.rs: 296-337
pub(self) fn process_at_time(&self, mut now: u64) {
    let mut waker_list = WakeList::new();
    let mut lock = self.inner.lock();

    // 从时间轮中收集所有到期（≤ now）的定时器
    while let Some(entry) = lock.wheel.poll(now) {
        if let Some(waker) = unsafe { entry.fire(Ok(())) } {
            waker_list.push(waker);
            if !waker_list.can_push() {
                // 批次满了，释放锁后批量唤醒
                drop(lock);
                waker_list.wake_all();
                lock = self.inner.lock();
            }
        }
    }

    // 更新下一次唤醒时间
    lock.next_wake = lock.wheel.poll_at()
        .map(|t| NonZeroU64::new(t).unwrap_or_else(|| NonZeroU64::new(1).unwrap()));
    drop(lock);

    // 唤醒剩余 waker
    waker_list.wake_all();
}

这里使用 WakeList 来批量收集 waker，在释放驱动锁之后再统一调用 wake()，避免持有锁时调用外部代码带来死锁风险。

六、最底层：从 park_timeout 到时钟中断

前面说 park_timeout 让线程休眠到最近的 deadline，但它到底是怎么”准时醒来”的？答案在最底层的硬件时钟中断。

Tokio 的 park_timeout 在 Linux 上最终会调用 mio::Poll::poll(events, timeout)，后者通过 epoll_wait(timeout_ms) 进入内核。内核内部使用高精度定时器（hrtimer）来实现这个超时：

sequenceDiagram
    participant Tokio as Tokio Worker
    participant mio as mio / epoll
    participant Kernel as Linux Kernel
    participant hrtimer as hrtimer 子系统
    participant Clock as 时钟事件设备 (APIC/HPET)

    Tokio->>mio: park_timeout(5000ms)
    mio->>Kernel: epoll_wait(timeout=5000ms)
    Kernel->>hrtimer: schedule_hrtimeout_range()
    hrtimer->>hrtimer: enqueue_hrtimer() 插入红黑树
    hrtimer->>Clock: 编程设备为 one-shot，5 秒后触发中断
    Note over Tokio: 线程休眠，CPU 可服务其他任务
    Note over Clock: ... 5 秒 ...
    Clock-->>Kernel: 硬件时钟中断
    Kernel->>hrtimer: hrtimer_interrupt()
    hrtimer->>hrtimer: __hrtimer_run_queues() 遍历红黑树
    hrtimer->>Kernel: hrtimer_wakeup() → wake_up_process()
    Kernel-->>Tokio: epoll_wait 返回
    Tokio->>Tokio: process_at_time() 处理到期定时器

6.1 红黑树 vs 哈希时间轮

有趣的是，内核的 hrtimer 和 Tokio 用了不同的数据结构。Tokio 的 time driver 使用哈希时间轮（本文第三节），而 Linux 的 hrtimer 使用红黑树（rbtree）来组织定时器¹²：

// include/linux/hrtimer_defs.h: 27-35
struct hrtimer_clock_base {
    struct hrtimer_cpu_base    *cpu_base;
    clockid_t                  clockid;
    unsigned int               seq;
    // 按到期时间排序的红黑树根节点
    struct timerqueue_linked_head active;
    ktime_t                    (*get_time)(void);
    ktime_t                    offset;
};

enqueue_hrtimer() 将定时器插入红黑树，时间复杂度 O(log n)¹³：

// kernel/time/hrtimer.c: 1096-1104
/*
 * enqueue_hrtimer - internal function to (re)start a timer
 *
 * The timer is inserted in expiry order. Insertion into the
 * red black tree is O(log(n)).
 */
static bool enqueue_hrtimer(struct hrtimer *timer,
                            struct hrtimer_clock_base *base,
                            enum hrtimer_mode mode, bool was_armed)

这并不是说哪种数据结构更优——它们只是面向不同的约束。内核的 hrtimer 需要纳秒级精度和动态的到期时间分布，红黑树的 O(log n) 插入更为稳妥。Tokio 的哈希时间轮只需要毫秒级精度，但需要管理海量定时器（成千上万个 Sleep 并发），O(1) 插入和批量降级更适合这种场景。

有意思的是，Linux 内核也有一套低精度定时器（timer wheel），代码路径在 kernel/time/timer.c，它用的正是和 Tokio 类似的层级哈希轮结构——8 到 9 层，每层 64 个 bucket（LVL_SIZE = 64，LVL_DEPTH = 8/9），粒度和覆盖范围的表¹⁴：

// kernel/time/timer.c: 104-115 (HZ=1000 时)
//
// HZ 1000 steps
// Level Offset  Granularity            Range
//  0      0         1 ms                0 ms -         63 ms
//  1     64         8 ms               64 ms -        511 ms
//  2    128        64 ms              512 ms -       4095 ms
//  3    192       512 ms             4096 ms -      32767 ms
//  4    256      4096 ms (~4s)      32768 ms -     262143 ms
//  5    320     32768 ms (~32s)    262144 ms -    2097151 ms
//  6    384    262144 ms (~4m)    2097152 ms -   16777215 ms
//  7    448   2097152 ms (~34m)  16777216 ms -  134217727 ms
//  8    512  16777216 ms (~4h)  134217728 ms - 1073741822 ms

对比 Tokio 的 6 层 64 slot 设计，两者的核心思想同源——都源自哈希时间轮的经典设计。

6.2 从时钟中断到进程唤醒

当硬件时钟事件设备（Local APIC Timer 或 HPET）在 deadline 到达时产生中断，内核进入 hrtimer_interrupt()。这个函数做了几件关键的事¹³：

1. 更新时间基准：hrtimer_update_base() 读取硬件计数器和系统时间
2. 处理到期定时器：__hrtimer_run_queues() 遍历红黑树中所有到期时间 ≤ now 的定时器
3. 调用定时器回调：对于 sleep 类定时器，回调是 hrtimer_wakeup()

hrtimer_wakeup 的实现非常直接——找到等待中的进程，把它叫醒¹³：

// kernel/time/hrtimer.c: 2184-2193
static enum hrtimer_restart hrtimer_wakeup(struct hrtimer *timer)
{
    struct hrtimer_sleeper *t =
        container_of(timer, struct hrtimer_sleeper, timer);
    struct task_struct *task = t->task;

    t->task = NULL;
    if (task)
        wake_up_process(task);

    return HRTIMER_NORESTART;
}

wake_up_process() 将进程状态设为 TASK_RUNNING 并放入就绪队列。随后内核的调度器在合适的时机把它调度回 CPU。Tokio 的 worker 线程从 epoll_wait 返回，继续执行 process_at_time()，完成定时器的处理。

6.3 关键细节：这不是周期性的 tick

需要注意，现代 Linux 在 NOHZ（dynticks）模式下并不是靠周期性的时钟中断来驱动定时器的，而是把时钟事件设备编程为一次性（one-shot）触发。hrtimer_interrupt() 在处理完当前到期的定时器后，会重新编程时钟设备，让它在下一次最早到期的 deadline 时再产生中断¹³。

这意味着如果系统上没有定时器在等待（或者最近的定时器在 5 秒后），CPU 可以进入深度休眠状态，期间不产生任何时钟中断。这也是为什么 Tokio 的 park_timeout 在”没有定时器且没有 limit”时可以直接无限期 park——内核不会为它浪费任何 CPU 周期。

这条从 tokio::time::sleep 到硬件时钟中断的链路也就清楚了：

tokio::time::sleep(5s).await
    → Sleep::poll() 返回 Pending，注册到哈希时间轮
    → Driver::park_timeout(5s)
    → mio → epoll_wait(timeout=5000ms)
    → 内核 schedule_hrtimeout_range() → 插入红黑树
    → 编程时钟设备 one-shot 5 秒后触发
    → [CPU 休眠或服务其他任务]
    → 5 秒后时钟中断 → hrtimer_interrupt()
    → __hrtimer_run_queues() → hrtimer_wakeup() → wake_up_process()
    → epoll_wait 返回 → 线程醒来
    → process_at_time() → fire → wake_all()
    → Sleep::poll() 返回 Ready

七、TimeSource：时间与 tick 的桥梁

TimerEntry 使用 Instant 作为对外的时间抽象，而 Wheel 内部使用 u64 毫秒级 tick。TimeSource 负责两者之间的转换¹⁵：

// tokio/src/runtime/time/source.rs: 6-38
pub(crate) struct TimeSource {
    start_time: Instant,
}

impl TimeSource {
    pub(crate) fn deadline_to_tick(&self, t: Instant) -> u64 {
        // 向上取整到最近的毫秒
        self.instant_to_tick(t + Duration::from_nanos(999_999))
    }

    pub(crate) fn instant_to_tick(&self, t: Instant) -> u64 {
        let dur: Duration = t.saturating_duration_since(self.start_time);
        let ms = dur.as_millis().try_into()
            .unwrap_or(MAX_SAFE_MILLIS_DURATION);
        ms.min(MAX_SAFE_MILLIS_DURATION)
    }

    pub(crate) fn now(&self, clock: &Clock) -> u64 {
        self.instant_to_tick(clock.now())
    }
}

deadline_to_tick 在做向上取整——1 毫秒精度意味着任何不到 1 毫秒的等待都会被当成 1 毫秒处理。MAX_SAFE_MILLIS_DURATION 是 u64::MAX - 1，约为 5.84 亿年，远超实际需要。

八、把整条链路串起来

现在可以把 tokio::time::sleep 的完整执行路径画出来：

tokio::time::sleep(Duration::from_secs(5))
    │
    ├─ 创建 Sleep { entry: TimerEntry { deadline: now + 5s, registered: false } }
    │
    ├─ 首次 poll:
    │   ├─ TimerEntry::reset(deadline, true)
    │   │   ├─ 初始化 TimerShared（如果还没有）
    │   │   ├─ 将 deadline 转为 tick → 插入 Wheel（哈希时间轮）
    │   │   └─ 设置 registered = true
    │   ├─ StateCell::poll(cx.waker())
    │   │   ├─ 注册 waker 到 AtomicWaker
    │   │   └─ 加载 state → 还不是 STATE_DEREGISTERED
    │   └─ 返回 Poll::Pending
    │
    ├─ Runtime::park_internal:
    │   ├─ Wheel::next_expiration_time() → Some(5000)
    │   ├─ 计算 duration = 5000ms
    │   └─ OS::park_timeout(5000ms)  ← 线程休眠 5 秒
    │
    ├─ 5 秒后 OS 唤醒线程:
    │   ├─ Wheel::poll(now) → 找到到期的 entry
    │   ├─ entry.fire(Ok(()))
    │   │   ├─ result ← Ok(())
    │   │   ├─ state ← STATE_DEREGISTERED
    │   │   └─ 取出 waker
    │   └─ waker_list.wake_all()  ← 把任务放回调度队列
    │
    └─ 任务被再次 poll:
        ├─ StateCell::read_state()
        │   └─ cur_state == STATE_DEREGISTERED → 读取 result = Ok(())
        └─ 返回 Poll::Ready(())

sequenceDiagram
    participant User as User Task
    participant Sleep as Sleep Future
    participant Entry as TimerEntry
    participant Cell as StateCell
    participant Wheel as Hashed Wheel
    participant Driver as Time Driver
    participant OS as OS

    User->>Sleep: .await → poll(cx)
    Sleep->>Entry: poll_elapsed(cx)
    Entry->>Wheel: reset(deadline) → insert to Wheel
    Entry->>Cell: poll(waker) → register waker
    Cell-->>Entry: Poll::Pending
    Entry-->>Sleep: Poll::Pending
    Sleep-->>User: Poll::Pending

    Note over User: Worker 线程继续服务其他任务

    Driver->>Wheel: next_expiration_time() → 5000ms
    Driver->>OS: park_timeout(5000ms)
    Note over OS: ... 5 秒 ...
    OS-->>Driver: 唤醒

    Driver->>Wheel: poll(now) → 到期 entry
    Driver->>Cell: fire(Ok(()))
    Cell-->>Driver: Some(waker)
    Driver->>Driver: waker.wake()

    Note over User: 任务被重新调度
    User->>Sleep: poll(cx)
    Sleep->>Cell: read_state()
    Cell-->>Sleep: Poll::Ready(Ok(()))
    Sleep-->>User: Poll::Ready(())

九、取消、重置与交互细节

Sleep 的设计还支持两个重要的交互场景：

取消：直接 drop 掉 Sleep 实例即可。TimerEntry 的 PinnedDrop 实现会调用 cancel()，将定时器从时间轮中移除⁴。没有额外的清理工作。

重置：可以通过 Pin<&mut Sleep>::reset(new_deadline) 来改变 Sleep 的到期时间，而无需创建新的 Future²。内部实现会先尝试原子地延后到期时间（extend_expiration），如果 CAS 成功则无需操作时间轮；如果提前了到期时间，则会重新走 reregister 路径。

这种”乐观延后”的优化利用了定时器一个常见的使用模式——超时通常在操作开始时设置，然后在操作结束前被取消。延后触发时，旧的 slot 位置依然是”安全的”（不会过早触发），所以可以用 CAS 无锁更新。

总结

tokio::time::sleep 的实现体现了异步系统设计的核心分层：

1. 接口层（sleep() / Sleep）：对用户暴露一个 .await 即可等待的 Future
2. 运行时层（TimerEntry / TimerShared / StateCell）：用一个原子状态机管理定时器的生命周期，协调用户端和驱动端的并发访问
3. 数据结构层（Wheel）：用 6 层哈希时间轮实现 O(1) 插入和高效的到期检测
4. 驱动层（Driver::park_internal）：通过操作系统的定时唤醒（park_timeout）驱动整个机制运转

最终的效果是：一个单线程可以同时管理成千上万个定时器，线程只会在最近的 deadline 时休眠，期间 CPU 可以服务其他任务或进入省电状态。tokio::time::sleep 的高效并发能力不是来自魔法，而是来自一条从 Future 到 OS 的精心设计的链路。

References

• 上一篇 Rust async/await 的底层契约：从 Future::poll 到 Tokio 运行时