苍穹平台的定时任务处理分析

苍穹平台内部使用了时间轮算法 timing wheel

介绍

时间轮是一种高效利用线程资源进行批量化调度的一种调度模型。把大批量的调度任务全部绑定到同一个调度器上，使用这一个调度器来进行所有任务的管理、触发、以及运行。所以时间轮的模型能够高效管理各种延时任务、周期任务、通知任务。

如果在业务逻辑中存在数量较大的定时任务，且每个定时任务都创建一个只属于自己的的调度管理器负责自身的生命周期及周期任务执行， 这会极大的浪费cpu的资源，降低自身性能。

时间轮算法的核心是，轮询线程不再是负责遍历所有任务，而只在负责处于其当前时间上的任务。就像钟表一样，时间轮有一个指针会一直旋转，每转到一个新的时间，就去执行挂在这一时刻下的所有任务，当然，这些任务通常是交给其他线程去做，指针要做的只是继续往下转，不会关心任务的执行进度。

时间轮算法的应用非常广泛，在 Dubbo、Netty、Kafka、ZooKeeper、Quartz 的组件中都有时间轮思想的应用，甚至在 Linux 内核中都有用到。

时间轮机制及演进

时间轮本质上是一个环形队列，底层采用了数组进行实现，数组的索引代表其参考的任务执行的时间，数组中的每个元素可以存放一个定时任务列表。定时任务列表同样是一个环状的双向链表，其中每一项代表一个可执行的定时任务项。因此，时间轮的结构可以看作是将同一时刻执行的定时任务聚合在一个任务队列中，并挂在相应时间的数组索引上。

在时钟轮机制中，有时间槽和时钟轮的概念，时间槽就相当于时钟的刻度，而时钟轮就相当于秒针与分针等跳动的一个周期，我们会将每个任务放到对应的时间槽位上。

时钟轮的运行机制和生活中的时钟也是一样的，每隔固定的单位时间，就会从一个时间槽位跳到下一个时间槽位，这就相当于我们的秒针跳动了一次。

时间轮的一些概念：

● tickMs：基本时间跨度。时间轮由多个时间格组成，每个时间格代表当前时间轮的基本时间跨度。

● wheelSize：每一层时间轮的时间格个数。一个时间轮完成定义后，其时间格的个数是固定的。

● interval：时间跨度。一个时间轮的总体时间跨度 interval = tickMs * wheelSize。

● currentTime：当前时间。相当于时间轮的表盘指针，表示当前所处的时间，其取值通常是 tickMs 的整数倍。已经被指向的时间格属于到期部分，其对应的任务队列都需要被取出执行。

● 随着时间的不断推移，指针 currentTime 的位置不断向前推进。当有一个新的定时任务进来时，则在当前 currentTime 位置的基础上，加上对应的相对时间，则为新任务应该插入的队列位置。

简单时间轮算法

任务队列在加入时间轮时已经按照其执行时间完成了有序的归位，因此当轮询线程遍历到某一个时间格时，当前时间格对应的任务队列中的所有任务就可以开始直接执行，不需要再检查任务执行的时间戳是否已达到。

在实际应用中，定时任务的调度常常精确到分钟或者秒钟的粒度。如果一个定时任务需要指定在每天的某一个时刻执行，精确到秒，那么时间轮则需要支持一天 24 * 60 * 60 = 86400 个刻度。其占用的内存空间很大，但实际任务占用的可能只有几个甚至几十个，严重浪费系统资源。

round 的时间轮算法

为了处理上面提到的问题，我们可以在每个定时任务中增设一个 round 字段，用以标识当前任务还需要在时间轮中遍历几轮，才进入执行的时间判断轮。其执行逻辑为：每次遍历到一个时间格后，其任务队列上的所有任务 round 字段减 1，如果 round 字段变为 0，则将任务移出队列，提交给异步线程池来执行其内容。如果这是一个重复任务，那么提交后再将它重新添加到任务队列中。

假设现在将时间轮的精度设置为秒，时间轮共有 60 个时间格，那么一个 130 秒后执行的任务，可以将其 round 字段设为 2，并将任务加入到时间刻度为 10 的任务队列中。

即对于间隔时间为 x 的定时任务：

● round = x / 60 （整除）

● 刻度位置 pos = x % 60

这种方式虽然减少了时间轮的刻度个数，但并没有减少轮询线程的轮询次数，其效率还是相对比较低。时间轮每遍历一个时间刻度，就要完成一次判断和执行的操作，其运行效率与一般的任务队列差别不大，并没有太大的效率提升。完成了一次遍历，但是并没有提交可执行的任务，这种现象可以称之为“空轮询”。

分层时间轮算法

另一种对简单时间轮算法改良的方案，可以参照钟表中时、分、秒的设计，设置三个级别的时间轮，分别代表时、分、秒，且每个轮分别带有 24、60、60 个刻度。这样子三个时间轮结合使用，就能表达一天内所有的时间刻度。

将时钟轮分为多层，下一层时钟轮中每个槽位的单位时间是当前时间轮整个周期的时间，这就相当于 1 分钟等于 60 秒钟；当时钟轮将一个周期的所有槽位都跳动完之后，就会从下一层时钟轮中取出一个槽位的任务，重新分布到当前的时钟轮中，当前时钟轮则从第 0 槽位从新开始跳动，这就相当于下一分钟的第 1 秒。

当 hour 时间轮的轮询线程轮询到执行的时间格时，其对应的任务队列已达到其执行的 hour 时间。此时这些任务需转移到下一层 minute 时间轮中，根据其执行时间的 minute 位，插入到对应的任务队列中。后续的步骤都类似，直至到最后一层 second 的时间轮中，被轮询到的队列即可提交其所有的任务到异步执行线程池中。

采用分层时间轮的方式，不需要引入 round 字段，只要在最后一级遍历到的任务队列，必然是可提交执行的，进而避免了空轮询的问题，提高了轮询的效率。每个时间轮的遍历由不同的轮询线程实现，虽然引入的线程并发，但是线程数仅仅跟时间轮的级数有关，并不会随着任务数量的增加的增加。