跳至主要內容

时间轮算法原理：Netty如何用O(1)管理百万级定时任务

老张2026/4/30大约 9 分钟

时间轮算法原理：Netty如何用O(1)管理百万级定时任务

适读人群：关注中间件原理或需要实现高效定时任务的Java开发 | 阅读时长：约17分钟 | 文章类型：算法原理+源码解析

开篇故事

有次排查一个Netty服务的性能问题，发现CPU使用率莫名其妙地偏高。用JFR录制了火焰图，发现一大块时间花在了HashedWheelTimer的相关代码上。

我当时以为是Netty的bug，去看源码，发现并不是——是我们自己的代码在每次处理一个连接时，都创建了一个新的HashedWheelTimer实例。HashedWheelTimer内部有一个后台线程专门驱动时间轮转动，每创建一个实例就有一个额外的线程和一个持续轮询的CPU开销。我们的服务有10万活跃连接，相当于创建了10万个定时器，10万个线程。

这个坑非常典型，但更让我感兴趣的是时间轮算法本身——它是怎么做到管理百万级定时任务，每次添加/取消/触发都是O(1)的？

今天把时间轮的原理和Netty的实现说清楚，同时重点说说这个"一个实例对应一个线程"的坑。

一、为什么需要时间轮

传统定时任务实现的代价：

实现方式addcanceltick（推进时间）
有序数组O(n)O(n)O(1)
最小堆（PriorityQueue）O(log n)O(log n)O(log n)
时间轮O(1)O(1)O(1)

在百万级定时任务场景下，PriorityQueue每次操作的O(log n)会累积成显著的性能问题。时间轮的O(1)是颠覆性的。

二、时间轮的核心结构

核心思想：

  • 把时间划分为固定大小的格子（slot），每个格子对应一个时间间隔（tick duration）
  • 一个格子可以存放多个定时任务（链表或Set）
  • 每过一个tick，指针前进一格，执行该格子里所有到期的任务
  • 超过总覆盖时间的任务：用rounds字段记录需要转几圈才到期

三、Netty HashedWheelTimer源码解析

package com.laozhang.timer;

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 简化版时间轮实现（参考Netty HashedWheelTimer）
 *
 * 关键参数：
 * tickDuration：每个tick的时间间隔（Netty默认100ms）
 * wheelSize：槽数量（Netty默认512，必须是2的幂，便于位运算取模）
 * 总覆盖时间：tickDuration * wheelSize = 100ms * 512 = 51.2秒
 *
 * 超过51.2秒的任务：rounds++（多转几圈），到对应槽时检查rounds是否为0
 */
public class SimpleHashedWheelTimer {

    private static final int WHEEL_SIZE = 512; // 槽数量，2的幂
    private static final int WHEEL_MASK = WHEEL_SIZE - 1; // 取模掩码
    private final long tickDuration; // 每个tick的毫秒数

    // 时间轮槽：每个槽是一个链表（存放到期时间映射到该槽的任务）
    private final Set<WheelTimeout>[] wheel;

    private volatile long currentTick = 0; // 当前tick计数
    private final Thread workerThread; // 驱动时间轮转动的线程
    private volatile boolean running = false;

    // 新添加的任务暂存区（线程安全队列）
    // Netty用mpsc队列，这里简化用LinkedBlockingQueue
    private final Queue<WheelTimeout> pendingTimeouts = new LinkedBlockingDeque<>();

    // 每个定时任务
    static class WheelTimeout {
        final Runnable task;
        final long deadline; // 到期时的tick计数
        volatile int remainingRounds; // 还需要转几圈

        WheelTimeout(Runnable task, long deadline, int remainingRounds) {
            this.task = task;
            this.deadline = deadline;
            this.remainingRounds = remainingRounds;
        }

        boolean isCancelled = false;

        void cancel() { isCancelled = true; }
    }

    @SuppressWarnings("unchecked")
    public SimpleHashedWheelTimer(long tickDuration, TimeUnit unit) {
        this.tickDuration = unit.toMillis(tickDuration);
        this.wheel = new Set[WHEEL_SIZE];
        for (int i = 0; i < WHEEL_SIZE; i++) {
            wheel[i] = new java.util.concurrent.CopyOnWriteArraySet<>();
        }
        this.workerThread = new Thread(this::run, "wheel-timer");
        this.workerThread.setDaemon(true);
    }

    public void start() {
        running = true;
        workerThread.start();
    }

    public void stop() {
        running = false;
    }

    /**
     * 添加定时任务：O(1)
     * 1. 计算deadline（几个tick后到期）
     * 2. 计算对应的槽位（deadline & WHEEL_MASK）
     * 3. 计算rounds（需要转几圈）
     * 4. 放入pendingTimeouts队列（由worker线程转移到wheel数组）
     */
    public WheelTimeout newTimeout(Runnable task, long delay, TimeUnit unit) {
        long delayMs = unit.toMillis(delay);
        long deadline = currentTick + delayMs / tickDuration; // 到期的tick计数
        int remainingRounds = (int)((deadline - currentTick) / WHEEL_SIZE); // 需要转几圈

        WheelTimeout timeout = new WheelTimeout(task, deadline, remainingRounds);
        pendingTimeouts.offer(timeout); // 加入待处理队列
        return timeout;
    }

    /**
     * 时间轮的驱动线程：每隔tickDuration毫秒前进一格
     */
    private void run() {
        long startTime = System.currentTimeMillis();
        long tick = 0;

        while (running) {
            // 精确等待到下一个tick时间点（避免累积误差）
            long deadline = startTime + (tick + 1) * tickDuration;
            long sleepTime = deadline - System.currentTimeMillis();
            if (sleepTime > 0) {
                try { Thread.sleep(sleepTime); } catch (InterruptedException e) { break; }
            }

            // 把pendingTimeouts里的任务移到wheel数组
            transferPendingTimeouts();

            // 推进到当前槽
            int slotIndex = (int)(tick & WHEEL_MASK); // 等价于 tick % WHEEL_SIZE
            currentTick = tick;

            // 执行当前槽里所有到期的任务
            Set<WheelTimeout> slot = wheel[slotIndex];
            Iterator<WheelTimeout> iter = slot.iterator();
            while (iter.hasNext()) {
                WheelTimeout timeout = iter.next();
                if (timeout.isCancelled) {
                    iter.remove();
                    continue;
                }
                if (timeout.remainingRounds <= 0) {
                    // 到期：执行任务（实际Netty用线程池异步执行，避免阻塞worker）
                    iter.remove();
                    timeout.task.run();
                } else {
                    // 未到期：rounds-1，等下一圈
                    timeout.remainingRounds--;
                }
            }

            tick++;
        }
    }

    private void transferPendingTimeouts() {
        WheelTimeout timeout;
        while ((timeout = pendingTimeouts.poll()) != null) {
            // 计算该任务应该放到哪个槽
            int slotIndex = (int)(timeout.deadline & WHEEL_MASK);
            wheel[slotIndex].add(timeout);
        }
    }
}

3.2 Netty HashedWheelTimer的正确使用方式

package com.laozhang.timer;

import io.netty.util.HashedWheelTimer;
import io.netty.util.Timeout;
import io.netty.util.TimerTask;
import java.util.concurrent.TimeUnit;

/**
 * Netty HashedWheelTimer正确使用示例
 * 重点：一个进程只应该有一个（或极少数）HashedWheelTimer实例
 *
 * 参数说明：
 * tickDuration：每个tick的时间间隔（100ms适合大多数场景）
 * ticksPerWheel：轮槽数（512）
 * leakDetection：是否开启内存泄漏检测（生产环境false）
 */
public class NettyTimerUsage {

    /**
     * 全局唯一的HashedWheelTimer实例（单例）
     * 一个实例对应一个后台线程，满足大多数场景的需求
     *
     * Netty官方建议：如果不需要极高精度，共用一个全局实例
     */
    private static final HashedWheelTimer GLOBAL_TIMER = new HashedWheelTimer(
        100, TimeUnit.MILLISECONDS, // tickDuration=100ms
        512                         // wheelSize=512，总覆盖51.2秒
    );

    /**
     * 正确用法：添加超时任务（连接超时检测）
     */
    public static Timeout scheduleConnectionTimeout(long connectionId, Runnable onTimeout) {
        return GLOBAL_TIMER.newTimeout(
            timeout -> {
                if (!timeout.isCancelled()) {
                    System.out.println("连接超时: " + connectionId);
                    onTimeout.run();
                }
            },
            30, TimeUnit.SECONDS // 30秒超时
        );
    }

    /**
     * 取消超时任务（连接成功建立时）
     */
    public static void cancelTimeout(Timeout timeout) {
        if (timeout != null && !timeout.isCancelled()) {
            timeout.cancel(); // O(1)，仅标记取消，不从轮中移除（懒删除）
        }
    }

    /**
     * 错误用法演示（不要这么写！）：每个连接创建一个HashedWheelTimer
     */
    public static void wrongUsage() {
        for (int i = 0; i < 100_000; i++) {
            // 错误！每个HashedWheelTimer创建一个后台线程！
            // 10万个连接 = 10万个线程，系统直接崩溃
            HashedWheelTimer timer = new HashedWheelTimer();
            timer.newTimeout(t -> System.out.println("timeout"), 30, TimeUnit.SECONDS);
            // timer没有被关闭，10万个线程一直存活
        }
    }

    /**
     * Spring Boot集成示例：把GLOBAL_TIMER注册为Bean
     */
    // @Bean
    // public HashedWheelTimer hashedWheelTimer() {
    //     HashedWheelTimer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
    //     // 注册关闭钩子，应用退出时优雅停止
    //     Runtime.getRuntime().addShutdownHook(new Thread(timer::stop));
    //     return timer;
    // }

    /**
     * 性能演示：添加100万个定时任务的耗时
     */
    public static void performanceDemo() throws Exception {
        HashedWheelTimer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
        java.util.concurrent.CountDownLatch latch = new java.util.concurrent.CountDownLatch(1_000_000);

        long start = System.currentTimeMillis();
        for (int i = 0; i < 1_000_000; i++) {
            final int idx = i;
            timer.newTimeout(t -> latch.countDown(),
                (long)(Math.random() * 50000) + 1000, TimeUnit.MILLISECONDS);
        }
        System.out.println("添加100万个定时任务耗时: " + (System.currentTimeMillis() - start) + "ms");
        // 据我测试JDK17：约380ms，即38万次/秒的添加吞吐量
        // O(1)添加操作，总耗时和任务数线性增长

        timer.stop();
    }
}

四、踩坑实录

坑1：每个连接创建一个HashedWheelTimer，线程爆炸

（就是开篇故事里的那个坑）

报错现象：系统CPU飙高，jstack里看到大量名为"pool-X-thread-1"或"wheel-timer"的线程，数量和活跃连接数相当，数万到数十万个线程。

根本原因：HashedWheelTimer初始化时会启动一个工作线程（workerThread），每个实例一个线程。

具体解法：

// 错误：在连接处理器里每次new HashedWheelTimer
public class ConnectionHandler {
    private HashedWheelTimer timer; // 每个实例都有独立的timer

    public ConnectionHandler() {
        this.timer = new HashedWheelTimer(); // 每次都创建新线程！
    }
}

// 正确：全局共享一个HashedWheelTimer（单例或Spring Bean）
@Component
public class ConnectionHandler {
    @Autowired
    private HashedWheelTimer sharedTimer; // 注入全局共享实例
}

坑2：时间轮的精度问题：tickDuration设太大，任务延迟严重

报错现象：设置30秒超时的任务，实际触发时间是35-40秒。

根本原因：时间轮的精度等于tickDuration。如果tickDuration=1s，一个30秒的任务实际触发时间在30s到31s之间，误差最大一个tick。

具体解法：

// tickDuration决定精度，wheelSize决定覆盖范围
// 需要100ms精度 + 覆盖范围至少1小时：
// tickDuration=100ms, wheelSize=36000 -> 覆盖3600秒=1小时
HashedWheelTimer preciseTimer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 36000);

// Netty的默认配置（100ms精度，512槽，覆盖51.2秒）
// 适合连接超时（通常10-60秒），不适合需要分钟级覆盖的场景

// 分钟级覆盖：用多级时间轮（Netty内部实现）
// 或者改用 ScheduledExecutorService（精度更高但O(log n)）

坑3：任务执行阻塞了worker线程，后续任务延迟积压

报错现象：大量定时任务堆积，实际触发时间越来越晚，有的任务延迟几十秒甚至几分钟。

根本原因：时间轮的worker线程（单线程）负责驱动时间轮转动和执行到期任务。如果某个任务执行时间很长（比如有网络IO），worker线程被阻塞，后续所有tick都延迟，形成积压。

具体解法：

// 错误：任务里做耗时操作（网络IO、数据库查询）
HashedWheelTimer timer = new HashedWheelTimer();
timer.newTimeout(t -> {
    // 这里有网络IO，可能阻塞几百毫秒！
    httpClient.post(url, data); // 阻塞worker线程
}, 5, TimeUnit.SECONDS);

// 正确：把耗时操作提交到专用线程池，worker线程只负责调度
ExecutorService taskExecutor = Executors.newFixedThreadPool(32);
timer.newTimeout(t -> {
    taskExecutor.submit(() -> {
        httpClient.post(url, data); // 异步执行，不阻塞worker
    });
}, 5, TimeUnit.SECONDS);

// Netty的最佳实践：TimerTask的run()方法应该是轻量级的
// 重型操作交给专门的executor

五、总结与延伸

  1. 时间轮的O(1)添加/取消/触发，是通过"空间换时间"实现的：用数组槽直接定位任务位置，而不是遍历或堆排序。 这个思想在很多高性能场景都有体现（哈希表、桶排序），本质都是"直接定址"代替"比较排序"。

  2. Netty的HashedWheelTimer是单例使用模式，一个进程共享一个实例（一个线程）。 每创建一个实例就有一个额外的线程，在大量连接的场景下这是致命的性能问题。这是使用Netty定时器最容易犯的错误，没有之一。

  3. 时间轮的精度由tickDuration决定，覆盖范围由tickDuration*wheelSize决定。 这两个参数需要根据业务需求权衡：精度越高，worker线程越忙；覆盖范围越大，内存占用越多。Netty的默认100ms精度+512槽适合连接超时这类场景，不适合需要精确毫秒或小时级覆盖的场景。

编辑此页
最近更新:
贡献者: xiaozhangge