时间轮算法解析(Netty HashedWheelTimer源码解读)

1、背景

时间轮算法可以用于高效的执行大量的定时任务。
在Netty中的一个典型应用场景是判断某个连接是否idle,如果idle(如客户端由于网络原因导致到服务器的心跳无法送达),则服务器会主动断开连接,释放资源。得益于Netty NIO的优异性能,基于Netty开发的服务器可以维持大量的长连接,单台8核16G的云主机可以同时维持几十万长连接,及时掐掉不活跃的连接就显得尤其重要。
2、算法简介
                                            
网上盗个图,时间轮算法可以通过上图来描述。假设时间轮大小为8,1s转一格,每格指向一个链表,保存着待执行的任务。
假设,当前位于2,现在要添加一个3s后指向的任务,则2+3=5,在第5格的链表中添加一个节点指向任务即可,标识round=0。
假设,当前位于2,现在要添加一个10s后指向的任务,则(2+10)% 8 = 4,则在第4格添加一个节点指向任务,并标识round=1,则当时间轮第二次经过第4格时,即会执行任务。
时间轮只会执行round=0的任务,并会把该格子上的其他任务的round减1。
算法的原理非常浅显易懂,但是阅读源码实现还是有益的。
3、源码解析
1、构造方法
参数:
1)threadFactory
用于生成工作线程
2)tickDuration和unit
每格的时间间隔,默认100ms
3)ticksPerWheel
一圈下来有几格,默认512,特别的,如果传入的不是2的N次方,则会调整为大于等于该参数的第一个2的N次方,好处是可以优化hash值的计算
4)leakDetection
如果false,那么只有工作线程不是后台线程时才会追踪资源泄露,这个参数可以忽略
5)maxPendingTimeouts
最大的pending数量,默认-1,表示不限制
注:可以看到构造方法执行结束时,工作线程并没有启动,那么应该是在第一次添加任务的时候启动的,我们继续看添加任务的newTimeout方法
2、newTimeout
首先,通过一个原子变量来计数当前的任务数,如果设置最大pending且超过了,则会直接throw Exception
其次,便是调用start方法来正式启用worker线程,为了防止重复调用,使用了一个原子操作,并且调用完毕之后会CountDownLatch.await阻塞住,直到线程完全起来才返回


可以看到,方法是public的,也即用户可以显示的调用,而无需等待第一次添加任务时再启动
最后,便是包装一个HashedWheelTimeout对象(计算出了deadline),丢给队列,等待工作线程处理,那么接下来的重点就是看worker线程的实现了

3、Worker线程
工作线程启动的第一步是初始化startTime,并调用countDown来通知start方法,初始化结束了
其次便是一个循环,循环内的行为就是每隔一段跳一格的操作了,我们看具体的操作:
1)首先调用waitForNextTick()


首先计算一下当前tick下的deadline,减去startTime,得到sleepTimeMs,随后sleep一下。这里面有几个小细节:
计算sleepTimeMs先加999999,应该是不足1ms的,补足1ms
因为每次执行定时任务消耗的时候是不受控制的,因此算出来的sleepTimeMs可能为负,这个时候就可以直接返回了执行下一个格子里的任务了
如果currentTime==Long.MIN_VALUE,会直接返回一个负数,这个应该是为了处理时间轮执行了很长时间导致的long值溢出,具体了解的可以评论里告诉,不胜感激
下面还有一个,如果是windows平台,先除以10再乘以10,是因为windows平台下最小调度单位是10ms,如果不处理成10ms的倍数,可能导致sleep更不准了
最后,如果线程被打断了,并且是shutdown状态,会直接返回负数,并在随后的while判断中挑出循环
2)随后调用processCanceldTasks()
该方法是为了处理那些被取消的任务,任务存放在一个queue中

3)transferTimeoutsToBuckets()
该方法是从timeouts(就是前面newTimeout是放进去的那个queue)的queue中取出任务,放到格子里(HashedWheelBucket是一个链表),为了防止这个操作销毁太多时间,导致更多的任务时间不准,因此一次最多操作10w个。几个注意点:
计算stopIndes时,含义是取模,因为mask是2的N次方减1,因此%和&可以等价操作,即x % (mask + 1) == x & mask,这个技巧在jdk的集合类中也被使用到
为了防止出现任务延迟太久,因此在计算模之前,还先取max in (calculated, tick),从而让那些本应该在 过去执行的任务,在这期先快速执行掉

4)expireTimeouts(deadline)
这是HashedWheelBucket的一个方法,就是来执行该格子里那些已经过期的任务
这步的操作比较简单,就是一次遍历链表,如果remainingRounds(剩下的圈数)小于等于0,那么就把他移除并执行expire方法(即TimerTask的run方法);如果任务被取消了,则直接移除;否则remainingRounds减一,等待下一圈

5)如果中间时间轮的状态不再是started,那么就会跳出循环,并依次取出各个bucket上的未执行且没有被取消的任务,stop方法会返回这个列表

4、总结
  时间轮算法理解起来很简单,实现也似乎不难,但是通过阅读源码,可以看到,其中还是有很多很多的小细节需要注意,这个就不容易了
  而且通过阅读源码,可以看到,整个时间轮的调度都是在一个线程里完成的,因此对于那些耗时较大的定时任务,如果直接扔进去处理显然会影响其他任务的正常执行,例子如下:
                                              

                                                                        



本文来自网易实践者社区,经作者曹佳俊授权发布。