简介

定时器是一种在理论的利用中十分常见和无效的一种工具，其原理就是把要执行的工作依照执行工夫的程序进行排序，而后在特定的工夫进行执行。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/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」,懂技术，更懂你！