时间轮原理

什么是时间轮？

时间轮（Timing Wheel）是一种高效管理定时任务的数据结构，类似于生活中的时钟。

第一次听到这个说法时我以为只是比喻，看完源码才发现它字面意义上就是一个轮子：秒针每走一格，就扫过刻度盘上对应的那一格，扫到哪一格，就把该执行的任务执行掉。延时队列需要的正是这件事：把”未来某一段时间”切成若干个格子，任务按到期时间放进对应的格子，指针转过来时统一触发。

时间轮能流行，靠的是三个参数之间的取舍：

• tick_duration（精度）：指针每次前进一格代表多长时间。精度越高触发越准，但转得越快，空转的开销也越大。
• ticks_per_wheel（轮长）：轮子一共有多少个格子。轮子越大，能覆盖的时间跨度越大，但内存占用跟着线性上升。
• resolution（分辨率）：实际能取到的最小时间单位，通常就等于一个 tick。

一句话概括它的取舍：用内存换时间，用精度换吞吐。相比每次都去有序集合里查最小值、或者用最小堆做 O(log n) 的调整，时间轮的插入和推进几乎都是常数时间。

什么时候值得上时间轮？判断标准并不复杂：

这也是我们把时间轮放在《Redis ZSet 方案》之后讲的原因：ZSet 负责可靠地存和查，时间轮负责在内存里高效地触发，两者常常是配合关系，而不是替代关系。

---

基本原理

单层时间轮

时间轮结构：

    ┌───┬───┬───┬───┬───┬───┐
    │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │  ← 槽位（slots）
    ├───┼───┼───┼───┼───┼───┤
    │   │   │A  │   │B  │   │  ← 任务（A 在槽位 2，B 在槽位 4）
    └───┴───┴───┴───┴───┴───┘
      ↑
    当前指针（current_slot）

时间轮转动：
- 每秒转动一格
- 指针指向的槽位，其中的任务到期执行

这张图里有三个概念必须先钉死，后面所有推导都建立在它们之上。

槽位（slot）是什么？ 槽位是轮子上的一个刻度格，本质上是一个任务链表的头指针。槽位自己并不存任务，它只负责回答两个问题：“现在指针停在哪个格子”和”这一格该到期了，里面挂着谁”。链表节点通常直接内嵌在定时器对象里（intrusive list），这样插入任务不需要额外分配内存，GC 压力也小。

指针怎么前进？ 由一个后台线程按固定节奏把指针往后挪一格。每挪一格，就把这一格挂着的任务取出来处理。指针是”当前时间”的代理：指针所在位置加上已经转过的圈数，共同构成此刻。

任务的槽位怎么算？ 假设当前指针停在第 cur 格，tick 间隔为 tickDuration，一个任务要在 delay 毫秒后执行，它需要的 tick 数是：

ticks = ceil(delay / tickDuration)

如果 ticks 没有超过一圈，任务落在：

slot = (cur + ticks) % ticksPerWheel

如果 ticks 超过了一圈，说明它要等好几圈之后才到期。这时有两种处理方式：

• 记录剩余圈数（rounds）：任务挂在 slot = (cur + ticks) % ticksPerWheel 上，同时记住还要再转 rounds = ticks / ticksPerWheel 圈。指针每次扫到这个槽位，就把 rounds 减一；减到 0 才真正触发。Kafka 的 HashedWheelTimer 用的就是这一种。
• 降级到更高一层：把超出的部分交给上一级时间轮，也就是《层级时间轮》里秒针、分针、时针的关系。

用一张表把几种情况放在一起最直观。假设 ticksPerWheel = 6，当前指针在槽位 0，tick 间隔 1 秒：

延时 2 秒 → ticks = 2  → slot = (0 + 2) % 6 = 2              （一圈以内）
延时 4 秒 → ticks = 4  → slot = (0 + 4) % 6 = 4              （一圈以内）
延时 8 秒 → ticks = 8  → slot = (0 + 8) % 6 = 2, rounds = 1  （超出一圈）

指针推进过程（每秒一格）：

  时刻   指针   扫描槽位   发生什么
  t=1s     1       1        无
  t=2s     2       2        任务 A 到期执行
  t=4s     4       4        任务 B 到期执行
  t=8s     2       2        rounds 从 1 减到 0，任务 C 真正到期

注意最后一行：任务 C 在 t=2s 时就被扫到过一次，但它只是把圈数减了 1，并没有执行。这正是单层时间轮处理长延时的机制，也是它复杂的地方所在。

方案落地

下面是一个可运行的最小实现，把上面讨论的三件事都写了出来：桶链表、指针推进、圈数递减。

public class TimingWheel {

    /** 一个槽位就是一条任务链表的头 */
    static class Bucket {
        TimerTask head;

        void add(TimerTask task) {
            // 头插法：O(1)，且刚扫到的任务最先被取走
            task.next = head;
            head = task;
        }
    }

    static class TimerTask {
        final long deadlineMs;
        long rounds;          // 还需要转多少圈才到期
        TimerTask next;

        TimerTask(long deadlineMs, long rounds) {
            this.deadlineMs = deadlineMs;
            this.rounds = rounds;
        }
    }

    private final long tickDurationMs;
    private final int ticksPerWheel;
    private final Bucket[] wheel;
    private int cursor = 0;

    public TimingWheel(long tickDurationMs, int ticksPerWheel) {
        this.tickDurationMs = tickDurationMs;
        this.ticksPerWheel = ticksPerWheel;
        this.wheel = new Bucket[ticksPerWheel];
        for (int i = 0; i < ticksPerWheel; i++) {
            wheel[i] = new Bucket();
        }
    }

    /** 加入任务：算出圈数和槽位，插到链表头部 */
    public void add(long deadlineMs) {
        long remain = deadlineMs - System.currentTimeMillis();
        long ticks = Math.max(0, (remain + tickDurationMs - 1) / tickDurationMs);
        long rounds = ticks / ticksPerWheel;
        long offset = ticks % ticksPerWheel;
        int slot = (int) ((cursor + offset) % ticksPerWheel);

        wheel[slot].add(new TimerTask(deadlineMs, rounds));
    }

    /** 推进一格：扫描当前槽位，圈数递减到 0 的任务到期 */
    public List<TimerTask> tick() {
        cursor = (cursor + 1) % ticksPerWheel;
        List<TimerTask> expired = new ArrayList<>();
        Bucket bucket = wheel[cursor];

        TimerTask cur = bucket.head;
        bucket.head = null;
        while (cur != null) {
            TimerTask next = cur.next;
            cur.next = null;
            if (cur.rounds > 0) {
                cur.rounds--;
                // 圈数没减完，放回同一个槽位，等下一轮再扫
                bucket.add(cur);
            } else {
                expired.add(cur);
            }
            cur = next;
        }
        return expired;
    }
}

调度线程只要按固定节奏调用 tick() 即可：

ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
scheduler.scheduleAtFixedRate(this::tick, tickDurationMs, tickDurationMs, TimeUnit.MILLISECONDS);

这段代码里有三处值得注意：

1. 头插还是尾插，决定了桶内是否有序。 上面用的是头插，扫桶时从链表头依次取出，所以同一个槽位里的任务是”后进先出”。如果业务要求同一时刻到期的任务严格按入队顺序执行，就要改成尾插并维护一个尾指针。
2. 圈数递减会把任务放回原桶。 这是 rounds 方案的代价：每转一圈，同一批长延时任务都会被重新扫一遍。任务数乘以平均圈数，就是一轮的总扫描量。
3. 内部统一记录绝对截止时间，而不是相对延时。 进程重启后只要把任务重新灌进来就能继续算，不需要记录”还剩多久”这种易错的状态。

最后一点决定了时间轮在生产中的位置：它是一个内存态调度器，不是一个可靠存储。我们在《Redis ZSet 方案》里讲的 ZSet 才是任务的事实来源，时间轮只是被灌进去的那一批”接下来马上要到期”的任务。重启时的恢复流程是：从 ZSet 或数据库里捞出未来一个轮长范围内的任务，重新灌进时间轮，圈数直接由 deadline 减掉当前时间算出来。

---

时间复杂度

这张表要拆开看才准确，因为三个 O(1) 说的不是同一件事。

添加任务才是真正的 O(1)。 算圈数、算槽位是常数次整数运算，链表插入是头插，也是 O(1)。这是时间轮相对最小堆最大的优势：最小堆插入是 O(log n)，而且调整过程中会随机访问数组、频繁缓存失效。

获取到期任务严格来说是 O(1 + k)，不是 O(1)。 每转一格固定扫描一个槽位，扫描本身是 O(1)；但把这一格里到期的任务取出来是 O(k)，k 是该格到期的任务数。之所以写”O(1) 平均”，是因为在任务均匀分布的前提下，每个槽位里的任务数约等于总任务数除以槽位数，摊销下来就是常数。

空间复杂度要说得更准确。 轮子本身占 O(slots)，但每个任务还要占一条链表节点的内存，所以总空间是 O(slots + n)，n 是任务数。轮子大不代表省内存，它只是把”时间分辨率”和”槽位数量”这两件事解耦了。

扫描次数的摊销分析。 一个任务要等 k 圈才到期，它就会被扫到 k 次。所以轮子转一圈的总扫描量是 O(n × 平均圈数)。这正是单层时间轮的软肋：延时越长，被重复扫描的次数越多。

---

优缺点

优点

• ✅ 性能极高（O(1)）
• ✅ 精度可控
• ✅ 内存占用固定

这里”内存占用固定”严格来说是”轮子本身的内存占用固定”，也就是 O(slots)，与任务数无关；任务本身仍然占 O(n)。把这句话说准很重要，否则会误以为时间轮能装下无限任务。

缺点

• ❌ 只支持固定间隔的延时
• ❌ 长延时任务需要大容量时间轮

第二点要展开说，因为它是单层时间轮的真正边界。

单层时间轮在哪里会崩？

1. 延时跨度超过一轮。 任务要么需要记录圈数（引入额外状态和重复扫描），要么需要更大的轮子。延时 7 天、tick 1 秒，就要 604800 个槽位，每秒扫一次，纯粹空转。

2. 精度和跨度互相挤压。 想覆盖 7 天又要秒级精度，单层轮就得有 60 万个槽位；想省内存把轮子缩到 4096 格，精度就退化成约 148 秒——订单超时取消 30 分钟，直接失去意义。

3. 延时分布稀疏。 实际业务里延时分布通常是长尾的：绝大多数任务在几分钟内到期，少数任务要等几天。用单层轮覆盖最大跨度，大部分槽位永远是空的，内存花在了没人用的格子上。

4. 进程重启即全部丢失。 时间轮是纯内存结构，没有任何持久化。重启、发布、OOM 都是一次全量清空。

5. GC 与调度抖动。 大量定时器对象持续创建和销毁，在高 QPS 下会给 JVM 带来可观的 young GC 压力；同时如果调度线程被长任务阻塞，轮子就会”落后”，恢复时出现任务集中爆发的惊群。

单层时间轮的适用边界

结论先说：单层时间轮适合”延时范围集中且不跨圈”的场景，比如网络超时、心跳检测、连接管理、秒级到分钟级的调度。

一旦需求里出现”最长要等 7 天”，单层轮就该让位了。两个方向：

• 层级时间轮：用秒针、分针、时针这样的多层结构承载不同跨度，任务在层级之间降级。详见《层级时间轮》。
• 哈希时间轮：用固定数量的桶加圈数计数器，把”任意延时”压进有界内存。详见《哈希时间轮》。

而如果任务本身需要可靠地存下来、随时查、随时取消，那就该回到《Redis ZSet 方案》或《消息队列延时方案》，让可靠存储负责事实，让时间轮只负责触发。

上一章节

时间轮

下一章节

哈希时间轮