时间轮-理论篇

1. 引言

定时任务再开发过程中无处不在，定时发送消息，定时更新数据库表的状态，Linux系统定时执行脚本等等。这些操作都离不开定时任务，那么这些定时任务是怎么实现的是否又去想过。如果让开发者自己去实现一个定时任务又该怎么实现？

最简单的方案：定义一个链表，将要执行的任务添加到链表中。然后用线程去遍历链表，找出需要执行的任务进行执行。通过反复遍历任务链表就能实现定时任务的执行功能。

但是上述方案有一个很重要的缺陷：如果我的任务有上百万个甚至更多的情况下，可能光遍历整个链表找出需要执行的任务就要花费一定量的时间。如果此时刚好有一个任务添加到链表的Tail,但是任务扫描的指针此时刚好在第一个Head任务节点。此时添加的任务执行时间就在添加后的20ms后，这个时候线程扫描到最后一个需要执行的任务的耗时可能超过了20ms,那么这种情况下就会出现任务的延迟执行。

Tips: 任务的延迟执行需要有一个合理的容忍范围。

在论文《Hashed and Hierarchical Timing Wheels》 提出了时间轮的概念来解决传统定时任务中的弊端

2. 时间轮简介

在生活中大家肯定见过指针手表(非电子手表)这个就可以看做时间轮，山地自行车的前后齿轮、水表的齿轮、以及减速齿轮都可以看做是时间轮。以手表的刻度为例子，机械手表上最长的指针每条以下表示1秒，也就是将一分钟分成了60个1秒。 时间轮的核心思想：将单位时间分成若干个时间间隔，每个时间间隔包含了时间单位除以若干时间间隔的时间量，时间轮转动到对应的时间间隔就执行当前时间间隔对应的可执行的任务。

下面用例子来说明：

1秒我们可以分成8个时间间隔，那么每个时间间隔就是125ms,如下图所示：

2.1 简单的时间轮

在论文《Hashed and Hierarchical Timing Wheels》 中每一个时间间隔叫做 bucket 。 bucket的作用用于存放当前时间间隔内存在的需要执行的任务。例如现在有四个任务A、B、C、D分别要在一秒的三个不同的时间段执行，A、B在两个不同的时间段执行，C、D在同一个时间段执行。那么在时间轮上的示意图如下：

当时间轮的指针从1Bucket的开始时间到结束时间段的过程中，会去遍历Bucket的链表中的任务，将需要执行的任务从链表中拿出来执行。已上图的例子每一秒时间轮的指针走一圈。

Tips: bucket中存放的任务是时间轮一个时间间隔中的任务，也就是说这些任务是一个时间段里面的任务。例如：100ms和80ms需要执行的任务都说存在bucket1。

进一步思考，如果你一分钟执行一次，那么时间轮的刻度就需要分成480个时间段，随着单位时间刻度的增加会让时间论的刻度越来越多。这样对于计算机来说就是消耗更多的内存。这种如何解决，在论文中提出另一个概念就是：分层时间轮

2.2 分层时间轮

在生活中分层时间轮也是比比皆是，例如在手表长最长的指针代表秒针，中间的代表分针，最短的代表时针。例如我有三个任务 A、B、C分别在以下时间执行：

• A六十秒的时候执行一次
• B十五分钟的时候执行一次
• C六点位置的时候执行一次

如下图所示：

秒时间轮完成一圈触发分时间轮刻度往下一个，分时间轮完成一周触发时时间轮往下一个刻度。分层时间轮之间的刻度关系可以自己定义。不需要和时间刻度表上一样的。具体取决于业务的需要。例如：Linux的Corntab只支持分钟，而Java的Quartz可以支持到秒。

3.总结

时间轮是一种高效来利用线程资源来进行批量化调度的一种调度模型。提高利用率，但是时间轮调度器的时间精度可能不是很高，对于精度要求特别高的调度任务可能不太适合。因为时间轮算法的精度取决于，也就是时间间隔，时间间隔越小精度越高。时间轮的使用在各大框架与中间件中有使用，netty，kafka,jraft（这个是fork netty的）。

我是蚂蚁背大象，文章对你有帮助点赞关注我，文章有不正确的地方请您斧正留言评论~谢谢！