netty 系列之:HashedWheelTimer 一种定时器的高效实现

2022 年 5 月 16 日
本文字数：3055 字
阅读完需：约 10 分钟

简介

定时器是一种在实际的应用中非常常见和有效的一种工具，其原理就是把要执行的任务按照执行时间的顺序进行排序，然后在特定的时间进行执行。JAVA 提供了 java.util.Timer 和 java.util.concurrent.ScheduledThreadPoolExecutor 等多种 Timer 工具，但是这些工具在执行效率上面还是有些缺陷，于是 netty 提供了 HashedWheelTimer,一个优化的 Timer 类。

一起来看看 netty 的 Timer 有何不同吧。

java.util.Timer

Timer 是 JAVA 在 1.3 中引入的。所有的任务都存储在它里面的 TaskQueue 中：

private final TaskQueue queue = new TaskQueue();

复制代码

TaskQueue 的底层是一个 TimerTask 的数组，用于存储要执行的任务。

private TimerTask[] queue = new TimerTask[128];

复制代码

看起来 TimerTask 只是一个数组，但是 Timer 将这个 queue 做成了一个平衡二叉堆。

当添加一个 TimerTask 的时候，会插入到 Queue 的最后面，然后调用 fixup 方法进行再平衡：

    void add(TimerTask task) {        // Grow backing store if necessary        if (size + 1 == queue.length)            queue = Arrays.copyOf(queue, 2*queue.length);
        queue[++size] = task;        fixUp(size);    }

复制代码

当从 heap 中移出运行的任务时候，会调用 fixDown 方法进行再平衡：

    void removeMin() {        queue[1] = queue[size];        queue[size--] = null;  // Drop extra reference to prevent memory leak        fixDown(1);    }

复制代码

fixup 的原理就是将当前的节点和它的父节点进行比较，如果小于父节点就和父节点进行交互，然后遍历进行这个过程：

    private void fixUp(int k) {        while (k > 1) {            int j = k >> 1;            if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)                break;            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;            k = j;        }    }

复制代码

fixDown 的原理是比较当前节点和它的子节点，如果当前节点大于子节点，则将其降级：

    private void fixDown(int k) {        int j;        while ((j = k << 1) <= size && j > 0) {            if (j < size &&                queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)                j++; // j indexes smallest kid            if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)                break;            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;            k = j;        }    }

复制代码

二叉平衡堆的算法这里不做详细的介绍。大家可以自行查找相关的文章。

java.util.concurrent.ScheduledThreadPoolExecutor

虽然 Timer 已经很好用了，并且是线程安全的，但是对于 Timer 来说，想要提交任务的话需要创建一个 TimerTask 类，用来封装具体的任务，不是很通用。

所以 JDK 在 5.0 中引入了一个更加通用的 ScheduledThreadPoolExecutor，这是一个线程池使用多线程来执行具体的任务。当线程池中的线程个数等于 1 的时候，ScheduledThreadPoolExecutor 就等同于 Timer。

ScheduledThreadPoolExecutor 中进行任务保存的是一个 DelayedWorkQueue。

DelayedWorkQueue 和 DelayQueue,PriorityQueue 一样都是一个基于堆的数据结构。

因为堆需要不断的进行 siftUp 和 siftDown 再平衡操作，所以它的时间复杂度是 O(log n)。

下面是 DelayedWorkQueue 的 shiftUp 和 siftDown 的实现代码：

       private void siftUp(int k, RunnableScheduledFuture<?> key) {            while (k > 0) {                int parent = (k - 1) >>> 1;                RunnableScheduledFuture<?> e = queue[parent];                if (key.compareTo(e) >= 0)                    break;                queue[k] = e;                setIndex(e, k);                k = parent;            }            queue[k] = key;            setIndex(key, k);        }
        private void siftDown(int k, RunnableScheduledFuture<?> key) {            int half = size >>> 1;            while (k < half) {                int child = (k << 1) + 1;                RunnableScheduledFuture<?> c = queue[child];                int right = child + 1;                if (right < size && c.compareTo(queue[right]) > 0)                    c = queue[child = right];                if (key.compareTo(c) <= 0)                    break;                queue[k] = c;                setIndex(c, k);                k = child;            }            queue[k] = key;            setIndex(key, k);        }

复制代码

HashedWheelTimer

因为 Timer 和 ScheduledThreadPoolExecutor 底层都是基于堆结构的。虽然 ScheduledThreadPoolExecutor 对 Timer 进行了改进，但是他们两个的效率是差不多的。

那么有没有更加高效的方法呢？比如 O(1)是不是可以达到呢？

我们知道 Hash 可以实现高效的 O(1)查找，想象一下假如我们有一个无限刻度的钟表，然后把要执行的任务按照间隔时间长短的顺序分配到这些刻度中，每当钟表移动一个刻度，即可以执行这个刻度中对应的任务，如下图所示：

这种算法叫做 Simple Timing Wheel 算法。

但是这种算法是理论上的算法，因为不可能为所有的间隔长度都分配对应的刻度。这样会耗费大量的无效内存空间。

所以我们可以做个折中方案，将间隔时间的长度先用 hash 进行处理。这样就可以缩短间隔时间的基数，如下图所示：

这个例子中，我们选择 8 作为基数，间隔时间除以 8，余数作为 hash 的位置，商作为节点的值。

每次遍历轮询的时候，将节点的值减一。当节点的值为 0 的时候，就表示该节点可以取出执行了。

这种算法就叫做 HashedWheelTimer。

netty 提供了这种算法的实现：

public class HashedWheelTimer implements Timer

复制代码

HashedWheelTimer 使用 HashedWheelBucket 数组来存储具体的 TimerTask:

private final HashedWheelBucket[] wheel;

复制代码

首先来看下创建 wheel 的方法：

    private static HashedWheelBucket[] createWheel(int ticksPerWheel) {        //ticksPerWheel may not be greater than 2^30        checkInRange(ticksPerWheel, 1, 1073741824, "ticksPerWheel");
        ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);        HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];        for (int i = 0; i < wheel.length; i ++) {            wheel[i] = new HashedWheelBucket();        }        return wheel;    }

复制代码

我们可以自定义 wheel 中 ticks 的大小，但是 ticksPerWheel 不能超过 2^30。

然后将 ticksPerWheel 的数值进行调整，到 2 的整数倍。

然后创建 ticksPerWheel 个元素的 HashedWheelBucket 数组。

这里要注意，虽然整体的 wheel 是一个 hash 结构，但是 wheel 中的每个元素，也就是 HashedWheelBucket 是一个链式结构。

HashedWheelBucket 中的每个元素都是一个 HashedWheelTimeout. HashedWheelTimeout 中有一个 remainingRounds 属性用来记录这个 Timeout 元素还会在 Bucket 中保存多久。

long remainingRounds;

复制代码

总结

netty 中的 HashedWheelTimer 可以实现更高效的 Timer 功能，大家用起来吧。

更多内容请参考 http://www.flydean.com/50-netty-hashed-wheel-timer/
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

发布于: 23 小时前阅读数: 19

原文链接:【http://xie.infoq.cn/article/a0cdbcef280f28f58ad136266】。文章转载请联系作者。

程序那些事

关注

关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！

发布

暂无评论

创作场景

netty 系列之:HashedWheelTimer 一种定时器的高效实现

简介

java.util.Timer

java.util.concurrent.ScheduledThreadPoolExecutor

HashedWheelTimer

总结

程序那些事

评论