时间轮

前言

时间轮是一个非常高效且低成本的计时算法，论文地址《Hashed and Hierarchical Timing Wheels》，Linux 内核中使用广泛，你所用到的crontab就是如此，相对于DelayQueue的O(logN)，HashedWheelTimer 的时间复杂度是 O(1)。有广泛的使用，比如在netty,kafka,Dubbo,Redisson等著名框架中。

使用场景

1，定时任务
2，超时处理
3，心跳检测
4，锁超时释放
等等...

原理

[图片上传中...(2.png-9377fa-1654501129086-0)] 2.png

1，HashedWheelTimer 的时间精度并不高，误差在 100ms 左右，任务队列等待任务数量过多的情况下可能会积累出相应的误差。
2，HashedWheelTimer 能够处理非常大量的定时任务，且每次定位到要处理任务的候选集合链表只需要指针指向下一个桶即可，时间复杂度为O(1) ，而 Timer 等则需要调整堆，是 O(logN) 的时间复杂度。
3，HashedWheelTimer 实际上是将一个大的任务拆成多个小的任务，放到时间盘上。这样可以减少大量的CPU，线程，内存资源消耗。
5，HashedWheelTimer 单时间盘，无法满足的情况下，可以使用多时间盘，每个时间盘代表不同的时间单位

主要实现

实现的话主要理解Netty的HashedWheelTimer算法。主要有4个类。Timer，TimerTask，Timeout，HashedWheelTimer。

三个接口
Timer：管理 TimerTask，HashedWheelTimer 也是实现了 Timer 接口
TimerTask：通过上述的 Timer.newTimeout(TimerTask, long, TimeUnit) 加入，在指定时间后执行的 Task
Timeout：持有上层的 Timer 实例，和下层的 TimerTask 实例，然后取消任务的操作也在这里面
三者的关系

3.png

一个实现

HashedWheelTimer：时间轮算法具体实现。

java代码使用：

HashedWheelTimer wheelTimer = new HashedWheelTimer();
wheelTimer.newTimeout(timeout -> System.out.println("1s delay"), 1, TimeUnit.SECONDS);
wheelTimer.newTimeout(timeout -> System.out.println("10s delay"), 10, TimeUnit.SECONDS);
wheelTimer.newTimeout(timeout -> System.out.println("11s delay"), 11, TimeUnit.SECONDS);
TimeUnit.SECONDS.sleep(20);

注意：netty使用时间轮算法的情况下，能够处理上百万的连接。不过一般都是处理一些短快的任务比如心跳。而且netty的实现只支持单轮。