时间轮实现
时间轮是一种环形的数据结构,分成多个格。
每个格代表一段时间,时间越短,精度越高。
每个格上用一个链表保存在该格的过期任务。
指针随着时间一格一格转动,并执行相应格子中的到期任务。
名词解释:
时间格:环形结构中用于存放延迟任务的区块
指针:指向当前操作的时间格,代表当前时间
格数:时间轮中时间格的个数
间隔:每个时间格之间的间隔,代表时间轮能达到的精度
总间隔:当前时间轮总间隔,等于格数*间隔,代表时间轮能表达的时间范围
单表时间轮
以上图为例,假设一个格子是1秒,则整个时间轮能表示的时间段为8s, 如果当前指针指向2,此时需要调度一个3s后执行的任务,需要放到第5个格子(2+3)中,指针再转3次就可以执行了。
单表时间轮存在的问题是:
格子的数量有限,所能代表的时间有限,当要存放一个10s后到期的任务怎么办?这会引起时间轮溢出。
有个办法是把轮次信息也保存到时间格链表的任务上。
如果任务要在10s后执行,算出轮次10/8 round等1,格子10%8等于2,所以放入第二格。
检查过期任务时应当只执行round为0的任务,链表中其他任务的round减1。
带轮次单表时间轮存在的问题是:
如果任务的时间跨度很大,数量很大,单层时间轮会造成任务的round很大,单个格子的链表很长,每次检查的量很大,会做很多无效的检查。怎么办?
分层时间轮
过期任务一定是在底层轮中被执行的,其他时间轮中的任务在接近过期时会不断的降级进入低一层的时间轮中。
分层时间轮中每个轮都有自己的格数和间隔设置,当最低层的时间轮转一轮时,高一层的时间轮就转一个格子。
分层时间轮大大增加了可表示的时间范围,同时减少了空间占用。
举个例子:
上图的分层时间轮可表达8 8 8=512s的时间范围,如果用单表时间轮可能需要512个格子, 而分层时间轮只要8+8+8=24个格子,如果要设计一个时间范围是1天的分层时间轮,三个轮的格子分别用24、60、60即可。
工作原理:
时间轮指针转动有两种方式:
根据自己的间隔转动(秒钟轮1秒转1格;分钟轮1分钟转1格;时钟轮1小时转1格)
通过下层时间轮推动(秒钟轮转1圈,分钟轮转1格;分钟轮转1圈,时钟轮转1格)
指针转到特定格子时有两种处理方式:
如果是底层轮,指针指向格子中链表上的元素均表示过期
如果是其他轮,将格子上的任务移动到精度细一级的时间轮上,比如时钟轮的任务移动到分钟轮上
举个例子:
添加1个5s后执行的任务
算出任务应该放在秒钟轮的第5个格子
在秒钟轮指针进行5次转动后任务会被执行
添加一个50s后执行的任务
算出该任务的延迟时间已经溢出秒钟轮
50/8=6,所以该任务会被保存在分钟轮的第6个格子
在秒钟轮走了6圈(6*8s=48s)之后,分钟轮的指针指向第6个格子
此时该格子中的任务会被降级到秒钟轮,并根据50%8=2,任务会被移动到秒钟轮的第2个格子
在秒钟轮指针又进行2次转动后(50s)任务会被执行
添加一个250s后执行的任务
算出该任务的延迟时间已经溢出分钟轮
250/8/8=3,所以该任务会被保存在时钟轮的第3个格子
在分钟轮走了3圈(3*64s=192s)之后,时钟轮的指针指向第3个格子
此时该格子中的任务会被降级到分钟轮,并根据(250-192)/8=7,任务会被移动到分钟轮的第7个格子
在秒钟轮走了7圈(7*8s=56s)之后,分钟轮的指针指向第7个格子
此时该格子中的任务会被降级到秒钟轮,并根据(250-192-56)=2,任务会被移动到秒钟轮的第2个格子
在秒钟轮指针又进行2次转动后任务会被执行
优点:
高性能(插入任务、删除任务的时间复杂度均为O(1),DelayQueue由于涉及到排序,插入和移除的复杂度是O(logn))
缺点:
数据是保存在内存,需要自己实现持久化
不具备分布式能力,需要自己实现高可用
延迟任务过期时间受时间轮总间隔限制