一.前言

​ hello,everyone，好久不见。最近一段时间我做的业务里面有一种需求，对于审批超时的任务需要通过websocket通知给前端，前端实时展示审批单的执行情况。一开始想着使用定时任务每隔一段时间去进行数据表数据进行扫描出过期数据进行通知。但是这种操作如何扫描时间间隔短，那么对于数据库的空扫描的就很多，扫描间隔时间长，那么比如我11：00就过期的任务，我11：05才执行定时任务扫描，显然数据的准确性无法得到保障。

​ 为了解决上述的业务场景问题，我使用了很多中间件，框架使用的时间轮来解决。本文将会介绍多种实现方式与使用场景，如有不对之处，欢迎指出，共同进步~

二.时间轮介绍

​ 如果一个系统中存在着大量的调度任务，而大量的调度任务如果每一个都使用自己的调度器来管理任务的生命周期的话，浪费cpu的资源并且很低效。

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

​ 不过，时间轮调度器的时间精度可能不是很高，对于精度要求特别高的调度任务可能不太适合。因为时间轮算法的精度取决于，时间段“指针”单元的最小粒度大小，比如时间轮的格子是一秒跳一次，那么调度精度小于一秒的任务就无法被时间轮所调度。

2.1.单层时间轮

​ 如上图，把上述的环形队列看成时钟，当前环形队列执行0节点，每个节点之间间隔为1分钟，每个时钟节点上指向了一个任务队列。例如我现在要执行一个任务在5分钟之后执行，则将任务放置在5节点，当时间轮转动到5节点是，则将5节点上的任务进行执行，执行完成后，清空5节点的任务。

2.2.带圈数的时间轮

​ 第一种最基础的时间轮中其实缺陷还是挺明显的。例如我设置一个间隔为1分钟，环形队列节点数为60个节点的时间轮。那么如果我的任务执行在70分钟之后（70%60=10），它将于10分钟之后过期的任务重合了。那么当时间轮转动到10节点时，节点上的10分钟过期任务与70分钟过期任务将会过期。

​ 因此在初级时间轮的基础上需要加上round圈数的参数，例如上述的70分钟的任务，任务加入到节点中时记下圈数为1，10分钟的任务记下圈数为0，指针转到10节点时，仅执行圈数为0的数据并移除，其他任务圈数-1。

2.3.多层时间轮

​ 再回头看一下2.2。如果任务的跨度时间很长，那么时间轮将会空转，只有round为0才会进行任务的执行，这个无疑是很消耗cpu的。因此这里引入多层时间轮的概念

​ 第一层的跨度为1ms，第二层的跨度为20ms，第三层的跨度为400ms。那么例如我们放入的任务为501ms，则将会放入第三层的第一个节点（501%400=101），冗余了101ms，当第三层的指针转到第一个节点时，则将101ms的任务转移到第二层，再将任务放入到第二层的第5个节点（101%20=1）。当第二层的指针转移到低5个节点的时候发现冗余时间，则将任务转移到第一层的第一个节点，第一层转移一次就执行了。这么做的好处是避免了单轮空转的情况。

三.应用

​ 时间轮的使用在各大框架与中间件中有使用，xxl-job，netty，kafka都对时间轮都自己的实现。思路基本上与删除的时间轮策略一致。

​ 日常业务中如果任务的延时比较固定，不会出现大跨度的时间，则可以调用netty包中HashedWheelTimer类，如果较为复杂则可以是用kafka中的延时队列的实现。思路与上述一致。

四.参考

时间轮在 Kafka 的实践