Linux 内核定时器子系统：Timer Wheel 与 hrtimer 的设计艺术

时间，是操作系统中最晦暗的维度之一。进程调度依赖它，网络超时依赖它，磁盘刷写依赖它——百万个定时器同时在跑，内核如何在微秒级精度和 O(1) 复杂度之间找到平衡？

一、问题的本质：时间轮为何而生

在 Linux 内核 2.6 时代，定时器实现的是一棵红黑树（rbtree），按过期时间排序。查找"下一个最快过期定时器"是 O(log N)，插入删除也是 O(log N)。这在服务器场景下可以接受，但当定时器数量飙升到十万级时——DPVS 负载均衡器的连接超时、消息队列的延迟任务、容器健康检查——log N 的常数便不可忽视。

2001 年，Varghese 和 Lauck 在 SIGCOMM 上提出了 Hierarchical Timing Wheel（分层时间轮）概念。其核心洞察是：时间的本质是周期性的。秒针走完一圈引发分针走动一格，分针走完一圈引发时针走动一格——不同精度的时间刻度天然形成层级关系。

Linux 内核在 4.x 时代正式引入了 Timer Wheel 机制，将"查找下一个待触发定时器"的复杂度从 O(log N) 降到了均摊 O(1)。这不是红黑树退化了，而是数据结构的选择改变了问题的规模。

二、Timer Wheel 的数据结构

内核的定时器轮由五个桶（wheel level）组成，每个桶覆盖不同精度的时间范围：

/* include/linux/timerwheel.h */
#define WHEEL_SIZE 64       /* 每个轮层的桶数 */
#define WHEEL_BIT  6        /* log2(64) */
#define WHEEL_NUM  5        /* 轮层数量 */

/* 每个轮层覆盖时间跨度 */
/* TVR = 2^6   = 64 jiffies   (256ms @ HZ=250)    */
/* TVN = 2^12  = 4096 jiffies  (16s)                */
/* TVN = 2^18  = 262144 jiffies (17min)             */
/* TVN = 2^24  = 16M jiffies   (6.8days)            */
/* TVN = 2^30  = 1B jiffies    (34.8years)          */

五轮层级级递进：

每个定时器根据其到期时间（expires）与当前时间（jiffies）的差值，被放置到对应层级的对应桶中。当某个桶被"遍历"时，该桶内的所有定时器到期执行。

核心机制：每一 tick，Level 0 的当前桶被扫描。当 Level 0 完成一圈后，从 Level 1 取出一个桶，"级联"展开到 Level 0；Level 1 完成一圈后从 Level 2 取，以此类推。这就像一个机械钟表的齿轮传动系统。

三、源码漫步：add_timer 的实现逻辑

/* kernel/time/timer.c */
static inline unsigned int timer_get_idx(struct timer_list *timer)
{
    return (timer->expires - base->clk) & WHEEL_MASK;
}

static void Internal __mod_timer(struct timer_list *timer, unsigned long expires, ...)
{
    unsigned int idx;
    struct list_head *vec;
    int i;

    idx = calc_wheel_index(expires, &base->clk, &base->tqhead);
    ...
    list_add_tail(&timer->entry, &base->vectors[tqhead + idx]);
}

calc_wheel_index 函数根据到期时间与当前 jiffies 的差值，计算出应该位于哪一层的哪一个桶。当差值大于 Level 0 总跨度（64 ticks）但小于 Level 1 总跨度时，定时器直接放入 Level 1，避免在 Level 0 空转浪费内存。

懒惰插入：内核不会在 add_timer 时立即级联检查。只有当 tick 到来时，才进行一次级联操作。这意味着在密集 add_timer 场景下，一段区间内的定时器会安安静静躺在同一个桶里，无需任何树调整操作。

四、hrtimer：纳秒级精度的另一条路

Timer Wheel 解决的是"大量短周期定时器的高效管理"，它的最小粒度受限于 HZ（通常 250Hz 或 1000Hz）。但实时系统、音视频处理、网络 QoS 调度需要微秒甚至纳秒级精度——此时 Timer Wheel 力不从心。

hrtimer（High-resolution Timer）应运而生。它基于红黑树 + clockevent device 实现：

/* include/linux/hrtimer.h */
struct hrtimer {
    struct timerqueue_node      tnode;
    ktime_t                     _softexpires;
    enum hrtimer_restart        (*function)(struct hrtimer *);
    struct hrtimer_clock_base   *base;
    u8                          state;
};

struct hrtimer_cpu_base {
    struct hrtimer_clock_base   clock_base[MAX_CLOCK_BASES];
    unsigned int                active_bases;
    ktime_t                     (*get_time)(void);
};

hrtimer 的触发机制与 Timer Wheel 截然不同：

/* kernel/time/hrtimer.c */
static void __hrtimer_run_queues(struct hrtimer_cpu_base *cpu_base, int cpu)
{
    struct timerqueue_node *node;
    ktime_t now;

    node = timerqueue_getnext(&cpu_base->active);
    while (node) {
        struct hrtimer *timer;
        timer = container_of(node, struct hrtimer, tnode);
        now = hrtimer_update_base(cpu_base);

        if (now < node->expires)
            break;

        /* 执行回调 */
        restart = timer->function(timer);
        ...
        node = timerqueue_getnext(&cpu_base->active);
    }

    /* 编程下一次 clockevent */
    hrtimer_update_next_timer(cpu_base, cpu);
}

关键设计点：hrtimer 不依赖全局 tick，它直接驱动硬件。在无定时器请求时将 CPU 切到更深 C-state，这是电源管理的基石。

五、tick broadcast 与 NOHZ 模式下的双赢

当 CPU 进入 NOHZ_FULL（full dynticks）模式后，周期性 tick 会停止，但全局仍需要一些定时器运行（如 TCP 重传、cgroup 统计）。Linux 引入了 tick broadcast 机制：

/* kernel/time/tick-broadcast.c */
struct tick_device {
    struct clock_event_device *evtdev;
    enum tick_device_mode mode;
    ...
};

static void tick_handle_periodic_broadcast(struct clock_event_device *dev)
{
    /* 从 "bc_cpu" 发送 IPI 给处于 dyntick 状态的 CPU */
    apic->send_IPI_mask(cpu_online_mask & tick_broadcast_mask,
                        LOC_VECTOR);
}

"bc_cpu"（broadcast cpu）：一台机器上设计一个 CPU 始终维持 tick，该 CPU 在每个 tick 到来时通过 IPI 中断其他已进入 deep idle 的 CPU，确保它们的 Timer Wheel 仍然被"拨动"。这是 Idle 状态下定时器仍然能工作的秘诀。

代价：一个 CPU 无法进入最深的 C6 状态。这是功耗和精度的 trade-off。

六、性能实测：红黑树 vs Timer Wheel vs hrtimer

在 64 核 AMD EPYC 7763 + 4 块 Intel E810 网卡的场景下，我们测了三组数据：

场景 A：10万并发网络连接，延迟 Timer（超时=30s）

Timer Wheel 的优势随定时器数量增长更加明显。10万级以上的定时器，红黑树每次插入都需要锁竞争和树旋转，而 Timer Wheel 只需要一次位运算确定桶位置。

场景 B：hrtimer 精度测试（期望精度，比较 APIC timer vs HPET）

TSC-Deadline 模式是现代服务器最优选择：CPU 无需中断即可唤醒，自行对比 TSC 值与 deadline。在 io_uring 中已经大规模使用这一特性。

七、内核精准计时的新宠：TSC-Deadline

/* arch/x86/include/asm/msr.h */
static inline void tsc_deadline_program(unsigned long long deadline_tsc)
{
    /* 写入 MSR_IA32_TSC_DEADLINE_FULL */
    wrmsr(MSR_IA32_TSC_DEADLINE_FULL, deadline_tsc, 0);
}

TSC-Deadline 模式下，CPU 自行在 TSC 超过目标值时触发中断。无需发送 IPI，无需编程 PIT/APIC 比较器。

好处：

代价：虚拟化场景下，TSC 可能不稳定（需要 TSC scaling 或 VMware 的 TSC 补偿机制）。KVM 提供了 kvmclock + paravirtualized TSC-Deadline 桥接方案，但云厂商仍然谨慎。

八、工程实践：如何选定时器

最佳实践：

# 快速检查是否有定时器泄漏
watch -n1 'grep "^TIMERS" /proc/timer_list | awk "{sum+=\$2} END {print sum}"' 

九、从定时器看 Linux 设计哲学

Timer Wheel 的设计体现了一个工程哲学：当你无法消除复杂度，就改变复杂度的分布。

红黑树将 O(log N) 分散到每次操作中；Timer Wheel 将 O(log N) 压缩为每次 tick 的 O(1) 均摊级联。对于网络服务器这种"大量定时器均匀分布、tick 持续运行"的场景，Timer Wheel 本质上是在用"周期性轮询的简单性"替代"有序结构的排序代价"。

hrtimer 则体现了另一条哲学：绝对精度有绝对代价，按需精度才是最优解。不是所有定时器都需要微秒精度，短周期用硬件直驱，长周期用 Timer Wheel，两个子系统共存于内核、各司其职——这是 Linux 能服务好从嵌入式到超算全场景的原因之一。

十、结语

Linux 内核定时器是一个被严重低估的子系统。我们调用的每一个 setitimer()、alarm()、select() timeout，最终在某个 CPU 的某个桶中默默计数了若干 tick；而音频播放器精确到微秒的每一帧回调，又悄无声息地驱动着红黑树和 clockevent device。

下一次当你写 if (time_after(jiffies, timeout)) 时，可以想想背后那个五层齿轮咬合的时间轮——那是 Varghese 在 1996 年论文中画的草图，经历了近三十年仍然是内核子系统中最优雅的数据结构设计之一。