时间轮算法

原创
2019/08/30 14:30
阅读数 2.8K

前言

现实开发中有许多的延迟操作,比如定时清理过期数据等,在JDK中自带的Timer或者DelayQueue来实现延迟的功能,但很多开源的中间件中并没有使用Timer或者DelayQueue来实现而是使用基于时间轮算法来实现执行延迟任务功能,例如2.7.0以上的Dubbo基于时间轮实现了,失败定时重发,心跳检测等延迟操作。JDK的Timer和DelayQueue插入和删除操作的平均时间复杂度为O(nlog(n))并不能满足的高性能插入删除的要求,而而基于时间轮可以将插入和删除操作的时间复杂度都降为O(1) 。

实现

时间轮是参考钟表盘来实现,钟表盘上的表针会在固定时间后向前走一格,走完12格后又回到原来位置重复上面流程,时间轮也类似定义了几个格,在固定时间在这几个格上走动。盗图看下结构

如上图,时间轮有多个时间格组成,每个时间格里放置了任务队列,当走到某个时间格时会执行当前时间格里的任务。时间轮的每个时间格用slot表示,时间轮的时间格长度是固定的用wheelLength表示,每个时间格走动的间隔时间也是固定的用tickDuration表示,假设当前指向时间格的第一个位置,要执行一个延迟时间为deadline的任务,那么需要先找到对应的slot将任务加入才能顺利执行,其对应的计算公式:slot = (deadline / tickDuration)%wheelLength;走完一圈时间轮所需的时间为:loopDuration = tickDuration*wheelLength,如果任务的deadline > loopDuration,那么第一轮走到对应的slot是不能执行此任务,需要计算执行此任务需要经过轮数,计算格式为:remainingRounds = deadline / tickDuration / wheelLength;也就是说次任务需要再经过remainingRounds+1轮并走到对应的slot才能执行。

举个例子:

定义时间格长度wheelLength=12,每个时间格间隔时间tickDuration=1s,假设当前指向时间格的第一个位置,如果执行一个需要20s后执行的延迟任务,根据公式slot=8,remainingRound=1,也就是说时间轮走2圈,并且走到时间格位置为8的地方才能执行任务。

展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部