dubbo解析时间轮算法的实现HashedWheelTimer原理

本文基于dubbo 2.7.5版本代码

本文介绍一下dubbo使用的时间轮算法HashedWheelTimer。
dubbo里面涉及到定时任务调度的都是使用HashedWheelTimer。比如&＃xff1a;客户端等待服务端返回&＃xff0c;如果超时了&＃xff0c;HashedWheelTimer调度定时任务触发超时异常。
为什么要是用时间轮算法&＃xff1f;下面这些引用自文章&＃xff1a;https://zhuanlan.zhihu.com/p/32906730。

大量的调度任务如果每一个都使用自己的调度器来管理任务的生命周期的话&＃xff0c;浪费cpu的资源并且很低效。
时间轮是一种高效来利用线程资源来进行批量化调度的一种调度模型。把大批量的调度任务全部都绑定到同一个的调度器上面&＃xff0c;使用这一个调度器来进行所有任务的管理&＃xff08;manager&＃xff09;&＃xff0c;触发&＃xff08;trigger&＃xff09;以及运行&＃xff08;runnable&＃xff09;。能够高效的管理各种延时任务&＃xff0c;周期任务&＃xff0c;通知任务等等。
缺点&＃xff0c;时间轮调度器的时间精度可能不是很高&＃xff0c;对于精度要求特别高的调度任务可能不太适合。因为时间轮算法的精度取决于&＃xff0c;时间段“指针”单元的最小粒度大小&＃xff0c;比如时间轮的格子是一秒跳一次&＃xff0c;那么调度精度小于一秒的任务就无法被时间轮所调度。而且时间轮算法没有做宕机备份&＃xff0c;因此无法再宕机之后恢复任务重新调度。

dubbo的HashedWheelTimer实现和netty的是一致的。
一般调用时间轮增加定时任务的代码如下&＃xff1a;

HashedWheelTimer failTimer &＃61; new HashedWheelTimer(new NamedThreadFactory("failback-cluster-timer", true), 1,TimeUnit.SECONDS, 32, failbackTasks);RetryTimerTask retryTimerTask &＃61; new RetryTimerTask(loadbalance, invocation, invokers, lastInvoker, retries, RETRY_FAILED_PERIOD);failTimer.newTimeout(retryTimerTask, RETRY_FAILED_PERIOD, TimeUnit.SECONDS);


首先创建一个时间轮对象&＃xff0c;然后创建一个TimerTask对象&＃xff0c;调用时间轮对象的newTimeout方法将TimerTask加入到调度器中。
时间轮算法的原理是&＃xff1a;

上图的的圆环表示的就是时间轮&＃xff0c;时间轮被分割成了一个个扇形块&＃xff0c;每个扇形块代表一段时间间隔&＃xff0c;时间轮上的指针最初指向0扇形块&＃xff0c;时间轮上还有一个指针&＃xff0c;指针指到哪个扇形块&＃xff0c;就意味着该扇形块对应的任务到时间了&＃xff0c;需要执行了。任务由绿色的方块表示。假如扇形块代表的时间间隔为200ms&＃xff0c;那么每过200ms&＃xff0c;指针指向下一个扇形块。如果指针不指向某一扇形块&＃xff0c;就算该扇形块的任务已经到期了&＃xff0c;也不会执行。由此可以看出&＃xff0c;时间间隔设置的越短&＃xff0c;任务的到期执行时间就越精确。
有的任务到期时间比较长&＃xff0c;时间轮需要转几圈后才到期&＃xff0c;因此对每个任务增加一个字段&＃xff0c;用于表示圈数&＃xff0c;指针每转一圈&＃xff0c;圈数减1&＃xff0c;上图绿色方块前面的数字便是圈数。因此满足执行条件的任务是&＃xff1a;指针指向当前扇形块且圈数为0。
因为同时到期的任务不止一个&＃xff0c;因此位于同一个扇形块的任务用链表连接。
下面介绍一下dubbo针对时间轮的实现。
首先介绍HashedWheelTimer的构造方法的各个入参&＃xff1a;

ThreadFactory threadFactory,//创建线程的线程工厂对象&＃xff0c;每个时间轮对象持有一个线程
long tickDuration, //扇形块的时间间隔
TimeUnit unit, //tickDuration的单位
int ticksPerWheel,//圆环上一共有多少个时间间隔&＃xff0c;HashedWheelTimer对其正则化&＃xff0c;将其换算为大于等于该值的2^n
long maxPendingTimeouts//最多允许多少个任务等待执行


HashedWheelTimer有多个私有类&＃xff1a;

• Worker&＃xff1a;实现了Runnable接口&＃xff0c;时间轮里面的线程执行的是它的run方法。
• HashedWheelTimeout&＃xff1a;代表一个任务&＃xff0c;也就是上图的绿色方块。HashedWheelTimer.newTimeout方法内部创建该对象&＃xff0c;并将它加入到队列中。
• HashedWheelBucket&＃xff1a;代表上图的扇形块。时间轮上的扇形块组成一个数组&＃xff0c;HashedWheelTimer循环遍历该数组。HashedWheelBucket持有一个HashedWheelTimeout链表&＃xff0c;表示该扇形块对应的任务。

在创建HashedWheelTimer对象后&＃xff0c;线程并没有执行&＃xff0c;只有当调用了newTimeout方法时&＃xff0c;才会启动线程&＃xff0c;这属于懒启动的策略。当然也可以直接调用start()方法启动线程。
还有一点需要注意&＃xff0c;调用newTimeout方法后&＃xff0c;并没有将任务加入到时间轮中&＃xff0c;而是将任务放到了一个队列里面&＃xff0c;等待时间轮的指针指向下一个扇形块的时候&＃xff0c;才会将任务从队列里放入到时间轮上。每次最多处理100000个任务。
时间轮对象也不能创建太多&＃xff0c;INSTANCE_COUNTER属性记录了HashedWheelTimer对象个数&＃xff0c;最多不能超过64个。
当首次调用newTimeout或者start方法后&＃xff0c;便会调用属性workerThread的start方法启动线程&＃xff0c;workerThread是Thread对象。线程启动后&＃xff0c;开始执行Worker类的run方法。
下面介绍run方法流程&＃xff1a;

参考&＃xff1a;

https://zhuanlan.zhihu.com/p/32906730