前言


时间轮（timer wheel）是一种用来管理大量定时任务的数据结构。最朴素的做法是把所有定时器放进一个按到期时间排序的链表或最小堆，每次取最早到期的那个。最小堆的插入与删除是 O(log n)，对几万个定时器已经够用；但当定时器数量达到百万级、且大量定时器集中在相近的到期时间时，堆的常数开销与缓存不友好会成为瓶颈。时间轮把「时间」本身离散成槽位，插入与删除接近 O(1)，因此被网络库、操作系统内核广泛采用。


「多级」是时间轮的关键。单级时间轮如果要有很长的覆盖范围，槽位数量必须很大；例如每秒一个槽、要覆盖一天，就需要 86400 个槽。多级时间轮用「时、分、秒」式的分层，低级轮转一圈就推动高级轮走一格，用很少的槽位覆盖很长的时间范围。


需要说明：本文给出的是一个教学用的简化实现，借鉴了 Linux 内核时间轮的分层思想，但槽位数、层数、级联细节都做了简化，不声称与任何内核版本一致。代码用 C11 编写，不依赖平台 API。定时器的触发依赖外部周期调用 wheel_tick，本文不涉及真实时钟源。


一、单级时间轮的局限


单级时间轮是一个环形数组，每个槽挂一条定时器链表。维护一个当前槽指针，每过一个时间单位，指针前进一格，处理该槽里的定时器。


设槽数为 N，时间粒度为 1 秒，则单级时间轮能表达的最大延迟是 N 秒。要支持 1 小时的延迟，N 至少为 3600；要支持 1 天，N 为 86400。槽位越多，内存占用越大，而且大部分槽在任意时刻都是空的，空间利用率低。


多级时间轮用「进位」解决这个问题。以 3 位一级、共 4 级为例，每级 8 个槽：




级别覆盖范围槽位含义



08 个 tick每个 tick 一格

164 个 tick每 8 个 tick 一格

2512 个 tick每 64 个 tick 一格

34096 个 tick每 512 个 tick 一格



总共 32 个槽，就能表达 4096 个 tick 的延迟。定时器按「延迟落在哪一级的范围」放到对应层，等到低级轮转一圈、把时间推进到那一格时，再把高级的定时器「降级」重新挂到低级轮上，这个过程叫级联（cascade）。


二、放置规则


设当前时间为 now，定时器到期时间为 expires，延迟 delta = expires - now。



  • 若 delta < 8，放在第 0 层，槽号为 expires & 7；

  • 若 delta < 64，放在第 1 层，槽号为 (expires >> 3) & 7；

  • 若 delta < 512，放在第 2 层，槽号为 (expires >> 6) & 7；

  • 否则放在第 3 层，槽号为 (expires >> 9) & 7。


槽号用「到期时间的低位」而不是「延迟的低位」，是因为这样同一槽内的定时器在时间轴上是连续的，级联时只要把整槽取出重新分配即可。用位运算而不是除法，是因为级数与位宽都是 2 的幂，移位比除法便宜。


第 3 层覆盖 4096 个 tick，超过这个范围的定时器要么被拒绝，要么被截断到最大范围（会延迟触发）。工程实现里通常还会在最外层加一个「溢出链表」，本文从简，选择拒绝。


三、完整实现


// 适用于 C11

#include <stddef.h>

#include <stdio.h>



#define WHEEL_BITS   3

#define WHEEL_SIZE   (1 << WHEEL_BITS)     /* 每级 8 个槽 */

#define WHEEL_LEVELS 4

#define WHEEL_RANGE  (1UL << (WHEEL_BITS * WHEEL_LEVELS))  /* 4096 */



typedef struct timer {

    unsigned long expires;             /* 绝对到期 tick */

    void (*fn)(void *arg);

    void *arg;

    struct timer *next;                /* 同一槽内的链表指针 */

} timer_t;



typedef struct {

    timer_t *slots[WHEEL_LEVELS][WHEEL_SIZE];

    unsigned long current;

} wheel_t;



static void wheel_insert(wheel_t *w, timer_t *t, unsigned long now);



static void wheel_init(wheel_t *w) {

    int level;

    int slot;

    for (level = 0; level < WHEEL_LEVELS; ++level) {

        for (slot = 0; slot < WHEEL_SIZE; ++slot) {

            w->slots[level][slot] = NULL;

        }

    }

    w->current = 0;

}



/* 把定时器挂到合适的层与槽 */

static void wheel_insert(wheel_t *w, timer_t *t, unsigned long now) {

    unsigned long delta = t->expires - now;

    int level = 0;

    int shift;

    int slot;



    while (level < WHEEL_LEVELS - 1 &&

           delta >= (1UL << (WHEEL_BITS * (level + 1)))) {

        ++level;

    }



    shift = WHEEL_BITS * level;

    slot = (int)((t->expires >> shift) & (WHEEL_SIZE - 1));



    t->next = w->slots[level][slot];

    w->slots[level][slot] = t;

}



int wheel_add(wheel_t *w, timer_t *t, unsigned long delay) {

    if (delay >= WHEEL_RANGE) {

        return -1;                     /* 超出可表达范围 */

    }

    if (delay == 0) {

        delay = 1;                     /* 最早在下一个 tick 触发 */

    }

    t->expires = w->current + delay;

    wheel_insert(w, t, w->current);

    return 0;

}



/* 把某一层的某一槽整体取出，重新分配到合适的层 */

static void wheel_cascade(wheel_t *w, int level, int slot, unsigned long now) {

    timer_t *t = w->slots[level][slot];

    w->slots[level][slot] = NULL;



    while (t != NULL) {

        timer_t *next = t->next;

        wheel_insert(w, t, now);

        t = next;

    }

}



/* 处理第 0 层的当前槽：到期的执行，未到期的重新挂 */

static void wheel_fire(wheel_t *w, int slot, unsigned long now) {

    timer_t *t = w->slots[0][slot];

    w->slots[0][slot] = NULL;



    while (t != NULL) {

        timer_t *next = t->next;

        if (t->expires <= now) {

            t->fn(t->arg);

        } else {

            wheel_insert(w, t, now);

        }

        t = next;

    }

}



void wheel_tick(wheel_t *w) {

    unsigned long now = ++w->current;

    int idx0 = (int)(now & (WHEEL_SIZE - 1));



    /* 低级轮走完一圈，先级联高级轮，再从高到低降级 */

    if (idx0 == 0) {

        int idx1 = (int)((now >> WHEEL_BITS) & (WHEEL_SIZE - 1));

        if (idx1 == 0) {

            int idx2 = (int)((now >> (2 * WHEEL_BITS)) & (WHEEL_SIZE - 1));

            if (idx2 == 0) {

                int idx3 = (int)((now >> (3 * WHEEL_BITS)) & (WHEEL_SIZE - 1));

                wheel_cascade(w, 3, idx3, now);

            }

            wheel_cascade(w, 2, idx2, now);

        }

        wheel_cascade(w, 1, idx1, now);

    }



    wheel_fire(w, idx0, now);

}

逐段说明。timer_t 是调用方分配的结构体，时间轮只保存指针，不负责 malloc/free。这样插入与删除都不会触发堆分配，适合在中断上下文或实时系统中使用。


wheel_insert 从第 0 层开始，根据 delta 逐级判断是否超过当前层的覆盖范围。条件 delta >= (1UL << (WHEEL_BITS * (level + 1))) 表示「延迟已经装不进这一层」，需要升到下一层。循环上限是 WHEEL_LEVELS - 1，保证不会越界。


槽号取 (expires >> shift) & (WHEEL_SIZE - 1)。以第 1 层为例，shift = 3，槽号是 expires 的第 3 到第 5 位；第 2 层取第 6 到第 8 位。这与「每 8 个 tick 推进一格」的语义一致。


wheel_add 接收的是相对延迟，内部转换成绝对时间 expires。使用绝对时间的好处是级联时不需要修改定时器的字段，重新插入时只需用 expires - now 重新计算层级。


wheel_cascade 先摘下整条链，再逐个重新插入。重新插入时 now 是当前时间，expires - now 变小了，定时器会落到更低的层。


wheel_tick 的顺序很关键：先级联，再处理第 0 层。原因在下一节展开。


四、为什么必须先级联后触发


假设当前 now = 8，一个定时器的 expires = 8。它在插入时（假设 now = 0，delta = 8）被放到了第 1 层，槽号 (8 >> 3) & 7 = 1。到了 now = 8，第 0 层走完一圈，idx0 = 0，第 1 层的 idx1 = 1，wheel_cascade(w, 1, 1, 8) 把它取出。此时 delta = 0，重新插入会落到第 0 层槽 8 & 7 = 0。


如果先执行 wheel_fire(w, 0, 8) 再级联，这个定时器会在级联后才被放进第 0 层的槽 0，而槽 0 刚刚处理过，它要等到 8 个 tick 之后（now = 16）才会被再次处理，整整晚了一个轮转周期。


同理，级联必须从最高层开始，逐级向下。考虑 now = 64，第 1 层 idx1 = 0、第 2 层 idx2 = 1。如果先级联第 1 层，再级联第 2 层，那么第 2 层里 expires = 64 的定时器会被降到第 1 层的槽 0，而槽 0 刚刚级联过，它要等到 now = 128 才被处理，晚了 64 个 tick。正确顺序是「第 3 层、第 2 层、第 1 层」，代码里通过嵌套的 if 保证了这一点。


wheel_fire 里还有一个 t->expires <= now 的判断。理论上第 0 层当前槽里的定时器都应该到期，但级联与重新插入可能带来边界情况，加一层防御更稳妥。如果 expires > now，就重新插入，让它在正确的槽位等待。


五、复杂度与工程注意


插入的复杂度取决于层级判断，最多 WHEEL_LEVELS 次比较，可以视为 O(1)。触发一个槽时，槽内链表长度决定了处理成本，平均下来每个定时器只被处理常数次，因此总成本是 O(1) 摊还。相比最小堆的 O(log n)，时间轮在大规模定时器场景下更有优势。


但时间轮也有代价。第一，精度固定为一个 tick，无法表达比 tick 更细的延迟。第二，删除定时器不如堆方便：时间轮通常不提供「按句柄删除」，而是给定时器加一个 cancelled 标志，触发时检查并跳过，这叫惰性删除。第三，回调函数执行期间如果有新定时器插入，可能修改正在遍历的链表，需要把「待触发的定时器」先摘成独立链表再逐个执行，本文的 wheel_fire 已经先摘下整槽，避免了这个问题的常见形态。


如果要支持取消，可以在 timer_t 里加 int cancelled;，在 wheel_fire 中判断；或者额外维护一个哈希表，从定时器地址映射到所在层与槽，但删除时仍要遍历链表找前驱，复杂度 O(槽内长度)。


常见坑点


坑点一：先触发后级联，导致定时器晚一个周期。


// ❌ 错误：先处理第 0 层，再级联，刚降级的定时器错过本轮

wheel_fire(w, idx0, now);

if (idx0 == 0) { wheel_cascade(w, 1, idx1, now); }

// ✅ 正确：先级联，再触发

if (idx0 == 0) { wheel_cascade(w, 1, idx1, now); }

wheel_fire(w, idx0, now);

坑点二：级联顺序从低到高。


// ❌ 错误：先级联第 1 层，第 2 层降下来的定时器错过本轮

wheel_cascade(w, 1, idx1, now);

wheel_cascade(w, 2, idx2, now);

// ✅ 正确：从最高层开始，逐级向下

wheel_cascade(w, 2, idx2, now);

wheel_cascade(w, 1, idx1, now);

坑点三：槽号用延迟而不是绝对时间计算。


// ❌ 错误：级联后延迟改变，槽号与原有位置不一致

int slot = (int)(delta & (WHEEL_SIZE - 1));

// ✅ 正确：用绝对到期时间的低位

int slot = (int)((t->expires >> shift) & (WHEEL_SIZE - 1));

坑点四：层级判断没有上限，数组越界。


// ❌ 错误：delay 超过最大范围时 level 继续增加

while (delta >= (1UL << (WHEEL_BITS * (level + 1)))) ++level;

// ✅ 正确：限制在最大层，并在入口拒绝超范围延迟

while (level < WHEEL_LEVELS - 1 && delta >= (1UL << (WHEEL_BITS * (level + 1)))) ++level;

坑点五：在遍历槽内链表时直接插入新定时器。


// ❌ 错误：回调里添加定时器可能修改当前链表，遍历指针失效

while (t != NULL) { t->fn(t->arg); t = t->next; }

// ✅ 正确：先摘下整槽，再逐个处理

timer_t *list = w->slots[0][slot];

w->slots[0][slot] = NULL;

while (list != NULL) { timer_t *next = list->next; /* ... */ list = next; }

坑点六：时间轮负责释放定时器内存。


// ❌ 错误：定时器可能是栈上对象或由调用方复用，不能由时间轮 free

free(t);

// ✅ 正确：时间轮只保存指针，生命周期由调用方管理

坑点七：用有符号数存 tick，溢出后变成负数。


// ❌ 错误：有符号溢出是 UB

int current = 0;

++current;

// ✅ 正确：用无符号类型，回绕行为有定义

unsigned long current = 0;

坑点八：忘记处理 delay == 0。


// ❌ 错误：delay 为 0 时 expires 等于 current，该槽本轮已处理过，要等下一圈

t->expires = w->current + delay;

// ✅ 正确：把 0 延迟提升为 1，保证下一个 tick 触发

if (delay == 0) delay = 1;

t->expires = w->current + delay;

总结




要点说明



结构每级 N 个槽，槽内链表，低级轮转推动高级轮

放置按延迟选层级，按绝对到期时间的低位选槽号

级联低级走完一圈，从最高层向最低层逐级降级

顺序必须先级联后触发，否则晚一个轮转周期

复杂度插入 O(1)，触发摊还 O(1)

边界延迟上限、零延迟、回调中的并发修改



多级时间轮的精髓不在代码量，而在「用空间换时间」的分层思想：把长延迟拆成「高位」与「低位」，低位用密集的槽快速推进，高位只在进位时处理。写实现时盯住三点——按绝对时间选槽、从高到低级联、先级联后触发——定时器就不会出现「晚一拍」或「永不触发」的问题。




# c++ # 开发语言
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

《敲下回车之后：一次 DNS 解析的接力赛》

avatar openEuler 社区

Java方法学习总结：方法区内存结构总结

本文总结了方法区是JVM规范定义的逻辑区域，用于存储类元数据、常量池等信息，而非固定物理分区。不同JVM实现可采用不同方式：HotSpot JDK 7及以前用永久代，JDK 8后改用元空间，但均满足规范要求。方法区逻辑上属于堆，但物理上可独立于堆内存，其具体实现由JVM自行决定，以适应不同的内存管理策略与操作系统特性。理解方法区的关键在于区分逻辑概念与物理实现。

avatar openEuler 社区
cover

免配置Codex 一键整合包，双端 Agent 落地教程

avatar openEuler 社区