登录注册
最新博客
最新资源下载
时间轮算法解析（Netty HashedWheelTimer源码解读）
把生命浪费在美好事物上2018-07-17 11:131、背景
时间轮算法可以用于高效的执行大量的定时任务。
在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、总结
时间轮算法理解起来很简单，实现也似乎不难，但是通过阅读源码，可以看到，其中还是有很多很多的小细节需要注意，这个就不容易了
而且通过阅读源码，可以看到，整个时间轮的调度都是在一个线程里完成的，因此对于那些耗时较大的定时任务，如果直接扔进去处理显然会影响其他任务的正常执行，例子如下：
本文来自网易实践者社区，经作者曹佳俊授权发布。
分享至：
