小编点评

Netty是一个高性能的网络库，它使用了大量的机制来提升性能，包括延迟队列的时间轮调度算法。 1. **延迟任务实现**： 在Netty中，延迟任务是通过`HashedWheelTimer`类实现的。这个类内部维护了一个时间轮，时间轮是由一系列的`HashedWheelBucket`组成的，每个桶代表一个时间槽，可以存放多个任务。 2. **时间轮调度算法原理**： 时间轮调度算法的核心思想是将时间划分为一系列的长度固定的时间槽（slot），每个时间槽对应一个周期性触发事件的时间点。一个循环运行的时钟（时针）会经过这些时间槽，并在每个槽位上触发对应的任务执行。由于时钟是可以自由移动的（只要不超过一个轮次的时间），因此它可以用来异步处理一些定时或延时任务。 3. **任务添加与移除**： 在Netty中，任务是通过`TimerTask`对象来表示的。这些任务会被添加到`HashedWheelTimer`的时间轮中，`HashedWheelTimer`会根据任务的到期时间将其放置在相应的时间槽中。当任务被添加到时间轮中时，它的`run`方法会在指定的时间后被触发执行。 4. **任务执行**： 当定时触发的时候，时间轮中的任务会根据它们的`round`属性（记录任务添加到时间轮的时间点距离当前时间的轮数差）来决定如何执行。如果`round`为0，则任务需要立即执行；否则，任务将在下一轮触发时执行。需要注意的是，如果有同一个任务在多个时间槽中被添加，Netty会采用拉链法（chain method）来处理这种冲突。 5. **优缺点**： - **优点**：延时任务的添加和移除都可以在O(1)的时间复杂度内完成，非常高效；只需要一个线程就可以驱动整个系统的工作。 - **缺点**：如果时间轮中的槽数量过多，那么时间轮转动的速度可能会降低，对高优先级的任务响应速度可能受到影响。此外，时间轮算法需要额外的内存来存储状态信息（如时间槽和任务对象的引用）。 总体来说，Netty中的时间轮调度算法为处理定时和延时任务提供了一种高效且灵活的方式。

正文

Netty 框架是以性能著称的框架，因此在它的框架中使用了大量提升性能的机制，例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1)，那么什么是时间轮调度算法呢？接下来我们一起来看。

1.延迟任务实现

在 Netty 中，我们需要使用 HashedWheelTimer 类来实现延迟任务，例如以下代码：

public class DelayTaskExample {
    public static void main(String[] args) {
        System.out.println("程序启动时间：" + LocalDateTime.now());
        NettyTask();
    }

    private static void NettyTask() {
        // 创建延迟任务实例
        HashedWheelTimer timer = new HashedWheelTimer(3, // 间隔时间
                TimeUnit.SECONDS, // 间隔时间单位
                100); // 时间轮中的槽数
        // 创建任务
        TimerTask task = new TimerTask() {
            @Override
            public void run(Timeout timeout) throws Exception {
                System.out.println("执行任务时间：" + LocalDateTime.now());
            }
        };
        // 将任务添加到延迟队列中
        timer.newTimeout(task, 0, TimeUnit.SECONDS);
    }
}

以上程序的执行结果如下：

程序启动时间：2024-06-04T10:16:23.033
执行任务时间：2024-06-04T10:16:26.118

从上述执行结果可以看出，我们使用 HashedWheelTimer 实现了延迟任务的执行。

2.时间轮调度算法

那么问题来了，HashedWheelTimer 是如何实现延迟任务的？什么是时间轮调度算法？

查看 HashedWheelTimer 类的源码会发现，其实它是底层是通过时间轮调度算法来实现的，以下是 HashedWheelTimer 核心实现源码（HashedWheelTimer 的创建源码）如下：

private static HashedWheelBucket[] createWheel(int ticksPerWheel) {
    // 省略其他代码
    ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);
    HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];
    for (int i = 0; i < wheel.length; i ++) {
        wheel[i] = new HashedWheelBucket();
    }
    return wheel;
}
private static int normalizeTicksPerWheel(int ticksPerWheel) {
    int normalizedTicksPerWheel = 1;
    while (normalizedTicksPerWheel < ticksPerWheel) {
        normalizedTicksPerWheel <<= 1;
    }
    return normalizedTicksPerWheel;
}
private static final class HashedWheelBucket {
    private HashedWheelTimeout head;
    private HashedWheelTimeout tail;
    // 省略其他代码
}

在 HashedWheelTimer  中，使用了 HashedWheelBucket 数组实现时间轮的概念，每个 HashedWheelBucket 表示时间轮中一个 slot（时间槽），HashedWheelBucket 内部是一个双向链表结构，双向链表的每个节点持有一个 HashedWheelTimeout 对象，HashedWheelTimeout 代表一个定时任务，每个 HashedWheelBucket 都包含双向链表 head 和 tail 两个 HashedWheelTimeout 节点，这样就可以实现不同方向进行链表遍历，如下图所示：

时间轮算法的设计思想就来源于钟表，如上图所示，时间轮可以理解为一种环形结构，像钟表一样被分为多个 slot 槽位。每个 slot 代表一个时间段，每个 slot 中可以存放多个任务，使用的是链表结构保存该时间段到期的所有任务。时间轮通过一个时针随着时间一个个 slot 转动，并执行 slot 中的所有到期任务。

任务的添加是根据任务的到期时间进行取模，然后将任务分布到不同的 slot 中。如上图所示，时间轮被划分为 8 个 slot，每个 slot 代表 1s，当前时针指向 2 时，假如现在需要调度一个 3s 后执行的任务，应该加入 2+3=5 的 slot 中；如果需要调度一个 12s 以后的任务，需要等待时针完整走完一圈 round 零 4 个 slot，需要放入第 (2+12)%8=6 个 slot。

那么当时针走到第 6 个 slot 时，怎么区分每个任务是否需要立即执行，还是需要等待下一圈 round，甚至更久时间之后执行呢？所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务，第一个任务 round=0，需要立即执行；第二个任务 round=1，需要等待 18=8s 后执行；第三个任务 round=2，需要等待 28=8s 后执行。所以当时针转动到对应 slot 时，只执行 round=0 的任务，slot 中其余任务的 round 应当减 1，等待下一个 round 之后执行。

可以看出时间轮有点类似 HashMap，如果多个任务如果对应同一个 slot，处理冲突的方法采用的是拉链法。在任务数量比较多的场景下，适当增加时间轮的 slot 数量，可以减少时针转动时遍历的任务个数。

时间轮定时器最大的优势就是，任务的新增和取消都是 O(1) 时间复杂度，而且只需要一个线程就可以驱动时间轮进行工作。

课后思考

Netty 中的时间轮调度算法有什么缺点？

参考 & 鸣谢

《Netty核心原理剖析与RPC实践》

本文已收录到我的面试小站 www.javacn.site，其中包含的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。