时间轮算法

最近工作中使用了Xxl-Job框架来做分布式调度，内部采用了时间轮做整体调度，顺便学习并总结一下。

绝对时间和相对时间

定时任务一般有两种：

1. 约定一段时间后执行。
2. 约定某个时间点执行。

其实这两者是可以互相转换的，比如现在有一个定时任务是12点执行，当前时间是9点，那就可以认为这个任务是3小时后执行。同样，现在又有一个任务，是3小时后执行，那也可以认为这个任务12点执行。

假设我们现在有3个定时任务A、B、C，分别需要在3点、4点和9点执行，我们把它们都转换成绝对时间。
在这里插入图片描述
只需要把任务放到它需要被执行的时刻，然后等到时针转到相应的位置时，取出该时刻放置的任务，执行就可以了。这就是时间轮算法的核心思想。

重复执行

多数定时任务是需要重复执行，比如每天上午9点执行生成报表的任务。对于重复执行的任务，其实我们需要关心的只是下次执行时间，并不关心这个任务需要循环多少次，还是那每天上午9点的这个任务来说。

比如现在是下午4点钟，我把这个任务加入到时间轮，并设定当时针转到明天上午九点(该任务下次执行的时间)时执行。
时间来到了第二天上午九点，时间轮也转到了9点钟的位置，发现该位置有一个生成报表的任务，拿出来执行。
同时时间轮发现这是一个循环执行的任务，于是把该任务重新放回到9点钟的位置。
重复步骤2和步骤3。

如果哪一天这个任务不需要再执行了，那么直接通知时间轮，找到这个任务的位置删除掉就可以了。由上面的过程我们可以看到，时间轮至少需要提供4个功能：

加入任务
执行任务
删除任务
沿着时间刻度前进

时间轮的数据结构

时钟可以使用数组来表示，那么时钟的每一个刻度就是一个槽，槽用来存在该刻度需要被执行的定时任务。正常业务中，同一时刻中是会存在多个定时任务的，所以每个槽中放一个链表或者队列就可以了，执行的时候遍历一遍即可。
在这里插入图片描述

时间刻度不够用

增加时间轮的刻度

现在有我有2个定时任务，一个任务每周一上午9点执行，另一个任务每周三上午9点执行。最简单的办法就是增大时间轮的长度，可以从12个加到168 (一天24小时，一周就是168小时)，那么下周一上午九点就是时间轮的第9个刻度，这周三上午九点就是时间轮的第57个刻度。
在这里插入图片描述

这样做的缺点:

时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，我得移动720次，其中718次是无用功。

2. 时间刻度太多会导致存储空间变大，利用率变低，比如一个月就2个任务，我得需要大小是720的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了。

任务增加round属性

现在时间轮的刻度还沿用24，但是槽中的每个任务增加一个round属性，代表时钟转过第几圈之后再次转到这个槽的时候执行。

在这里插入图片描述

上图代表任务三在指针下一圈移动时执行，整体流程就是时间轮没移动一个刻度的时候都要遍历槽中所有任务，对每个任务的round属性减1，并取出round为0的任务调度，这样可以解决增加时间轮带来的空间浪费。但是这样带来的问题时，每次移动刻度的耗时会增加，当时间刻度很小(秒级甚至毫秒级)，任务列表有很长，这种方案是不能接受的。

分层时间轮

分层时间轮是这样一种思想：
　　1. 针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。
　　2. 针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。

假设现在有3个定时任务：

1. 任务一每天上午9点执行
2. 任务二每周2上午9点执行
3. 任务三每月12号上午9点执行。

根据这三个任务的调度粒度，可以划分为3个时间轮，月轮、周轮和天轮，初始添加任务时，任务一被添加到天轮上，任务二被添加到周轮，任务三被添加到月轮上。三个时间轮按各自的刻度运转，当周轮移动到刻度2时，取出任务二丢到天轮上，当天轮移动到刻度9时执行。同样任务三在移动到刻度12时，取出任务三丢给月轮。以此类推。
在这里插入图片描述