定时任务之时间轮算法

初识时间轮

我们先来考虑一个简单的情况，目前有三个任务A、B、C，分别需要在3点钟，4点钟和9点钟执行，可以把时间想象成一个钟表。

如上图中所示，我只需要把任务放到它需要被执行的时刻，然后等着时针转到这个时刻时，取出该时刻放置的任务，执行就可以了。 这就是时间轮算法最核心的思想了。 时针怎么转呢？ while-true-sleep ，也可以使用空的阻塞队列加上超时时间进行睡眠。

在大多数情况中同一时刻可能需要执行多个任务，比如每天上午九点除了生成报表之外，还需要执行发送邮件的任务，需要执行创建文件的任务等等。

时间轮的数据结构。首先，时间轮的刻度可以用数组或者链表表示，每个刻度就是一个槽，槽用来存放该刻度需要执行的任务，如果有多个任务需要执行呢？每个槽里面放一个链表就可以了，就像下面图中这样：

同一时刻存在多个任务时，只要把该刻度对应的链表全部遍历一遍，执行（扔到线程池中异步执行）其中的任务即可。

简单时间轮的实现

由一个 hash table和链表实现，HashTable 的 key 值为时间单位，value 为链表的 root 节点。

时间刻度不够用怎么办？

上述时间轮表示一天的时间，但如果任务不只限定在一天之内呢？比如我有个任务，需要每周一上午1点执行，我还有另一个任务，需要每月的第十二天的上午四点执行。一种很容易想到的解决办法是：

1.增大时间轮的刻度

一天24个小时，一周168个小时，一月720个小时，为了解决上面的问题，我可以把时间轮的刻度（槽）从12个增加到168个，所以每周一上午1点就是时间轮的第1个刻度，每周五上午4点就是时间轮的第100个刻度，示意图如下：

仔细思考一下，会发现这种方式存在几个缺陷：

1.时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，按照一个月30天算，需要移动720次，其中718次是无用的。

2.时间刻度太多会导致存储空间变大，利用率变低。

这种方式直接导致空间复杂度变大。

2.增加圈数

为每个任务增加一个圈数round标识，每次遍历到这个任务时，圈数减1，当圈数为0时，执行该任务，示意图如下：

但这种，每次时间轮转动，都需要对整个任务链表进行计算，增加了时间复杂度。最完美的实现就是转到对应刻度时，执行该刻度下所有的任务。

分层时间轮

分层时间轮是这样一种思想：每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。

比如有一个任务三每个月12号上午九点。

月轮的刻度为30天，周轮的刻度为7天，天轮为24小时。

这个任务需要月轮的时间刻度转动到12号这一天，然后才需要关注其更细一级的时间单位：上午9点。

初始添加任务时，任务一每周二上午九点，任务二每周四上午九点，任务三每个月12号上午九点。为任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。三个时间轮以各自的时间刻度不停流转。

当周轮移动到刻度2(星期四)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。

同理，当月轮移动到刻度12(12号)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。

这样就可以做到既不浪费空间，有不浪费时间。

整体的示意图如下所示：

定时器一览

1.无序定时器列表

2.有序定时器列表

3. 定时器树

4. 简单的计时轮

5. 带有有序定时器列表的哈希轮

6. 带有无序定时器列表的哈希轮

7.分层时间轮

时间轮的应用

时间轮的思想应用范围非常广泛，各种操作系统的定时任务调度，Redisson、Crontab、Netty、Kafka、Caffeine等组件的时间任务调度均采用时间轮的思想。

在不同的场景下，选择合适的定时器。

参考资料

hashed-and-hierarchical-timeing-wheels论文：Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility | the morning paper

时间轮简介：时间轮timewheel算法_天涯泪小武的博客-CSDN博客

netty时间轮分析：Netty时间轮 - 腾讯云开发者社区-腾讯云