时间轮算法 — 转
nurvnurv 2020-05-01
出处： 那些惊艳的算法们（三）—— 时间轮
从定时任务说起
自然界中定时任务无处不在，太阳每天东升西落，候鸟的迁徙，树木的年轮，人们每天按时上班，每个月按时发工资、交房租，四季轮换，潮涨潮落，等等，从某种意义上说，都可以认为是定时任务。
大概很少有人想过，这些“定时”是怎样做到的。当然，计算机领域的同学们可能对此比较熟悉，毕竟工作中的定时任务也是无处不在的：每天凌晨更新一波数据库，每天9点发一波邮件，每隔10秒钟抢一次火车票。。。
至于怎么实现的？很简单啊，操作系统的crontab，spring框架的quartz,实在不行Java自带的ScheduledThreadPool都可以很方便的做到定时任务的管理调度。
当你熟练的敲下“* * 9 * * ?”等着神奇的事情发生时，你是否想过背后的“玄机”？
初识时间轮
大概去年的时候，业务需要实现一个时间调度的工具，定时生成报表，同组的哥们儿想了一个取巧的办法：
1. 启动时从DB读取cron表达式解析，算出该任务下次执行的时间。
2. 下次执行的时间 - 当前时间 = 时间差。
3. 向ScheduleThreadPool线程池中提交一个延迟上面算出来的时间差的执行的任务。
4. 任务执行时，算一下这个任务下次执行的时间，算时间差，提交到线程池。
5. 当任务需要取消时，直接调用线程池返回的Future对象的cancel()方法就行了。
当时稍微想了一ScheduleThreadPool是怎么做到定时执行提交过来的任务的，大概有个模糊的概念，后来就把这事忘了。再后来，一次在地铁上看到一篇文章，讲了一种叫做时间轮的定时任务调度思想，感觉想法很不错，当年那个模糊的概念似乎清晰了很多，再后来，一个偶然的机会，网上搜了一下，竟然有一篇专门讲解时间轮算法的论文，顿时兴奋无比，赶紧打印下来，在上班的地铁上读了半个月，总算读完了。
戳这里下载：《Hashed and Hierarchical Timing Wheels》
论文中的思路很简单但也十分巧妙，对算法不断的改进对比，各种操作系统，框架中的基于时间的调度算法都是基于时间轮的思想实现的。下面我们来看看，这个神奇的时间轮到底是怎样实现定时任务的调度的。
绝对时间和相对时间
定时任务一般有两种：
1. 约定一段时间后执行。
2. 约定某个时间点执行。
聪明的你会很快发现，这两者之间可以相互转换，比如给你个任务，要求12点执行，你看了一眼时间，发现现在是9点钟，那么你可以认为这个任务三个小时候执行。
同样的，给你个任务让你3个小时后执行，你看了一眼现在是9点钟，那么你当然可以认为这个任务12点钟执行。
我们先来考虑一个简单的情况，你接到三个任务A、B、C（都转换成绝对时间），分别需要再3点钟，4点钟和9点钟执行，正当百思不得其解时，不经意间你瞅了一眼墙上的钟表，瞬间来了灵感，如醍醐灌顶，茅塞顿开：
如上图中所示，**我只需要把任务放到它需要被执行的时刻，然后等着时针转到这个时刻时，取出该时刻放置的任务，执行就可以了**。 这就是时间轮算法最核心的思想了。 什么？时针怎么转？ while-true-sleep 下面让我们一点一点增加复杂度。
需要重复执行多次的任务
多数定时任务是需要重复执行，比如每天上午9点执行生成报表的任务。对于重复执行的任务，其实我们需要关心的只是下次执行时间，并不关心这个任务需要循环多少次，还是那每天上午9点的这个任务来说。
1. 比如现在是下午4点钟，我把这个任务加入到时间轮，并设定当时针转到明天上午九点(该任务下次执行的时间)时执行。
2. 时间来到了第二天上午九点，时间轮也转到了9点钟的位置，发现该位置有一个生成报表的任务，拿出来执行。
3. 同时时间轮发现这是一个循环执行的任务，于是把该任务重新放回到9点钟的位置。
4. 重复步骤2和步骤3。
如果哪一天这个任务不需要再执行了，那么直接通知时间轮，找到这个任务的位置删除掉就可以了。
由上面的过程我们可以看到，时间轮至少需要提供4个功能：
1. 加入任务
2. 执行任务
3. 删除任务
4. 沿着时间刻度前进
同一时刻存在多个任务
上面说的是同一个时刻只有一个任务需要执行的情况，更通用的情况显然是同一时刻可能需要执行多个任务，比如每天上午九点除了生成报表之外，还需要执行发送邮件的任务，需要执行创建文件的任务，还需执行数据分析的任务等等，于是你刚才可能就比较好奇的时间轮的数据结构到现在可能更加好奇了，那我们先来说说时间轮的数据结构吧。
时间轮的数据结构
首先，时钟可以用数组或者循环链表表示，这个每个时钟的刻度就是一个槽，槽用来存放该刻度需要执行的任务，如果有多个任务需要执行呢？每个槽里面放一个链表就可以了，就像下面图中这样：
同一时刻存在多个任务时，只要把该刻度对应的链表全部遍历一遍，执行（扔到线程池中异步执行）其中的任务即可。
时间刻度不够用怎么办？
如果任务不只限定在一天之内呢？比如我有个任务，需要每周一上午九点执行，我还有另一个任务，需要每周三的上午九点执行。一种很容易想到的解决办法是：
增大时间轮的刻度
一天24个小时，一周168个小时，为了解决上面的问题，我可以把时间轮的刻度（槽）从12个增加到168个，比如现在是星期二上午10点钟，那么下周一上午九点就是时间轮的第9个刻度，这周三上午九点就是时间轮的第57个刻度，示意图如下：
仔细思考一下，会发现这中方式存在几个缺陷：
1. 时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，我得移动720次，其中718次是无用功。
2. 时间刻度太多会导致存储空间变大，利用率变低，比如一个月就2个任务，我得需要大小是720的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了。
于是乎，聪明的你脑袋一转，想到另一个办法：
列表中的任务中添加round属性
这次我不增加时间轮的刻度了，刻度还是24个，现在有三个任务需要执行，
1. 任务一每周二上午九点。
2. 任务二每周四上午九点。
3. 任务三每个月12号上午九点。
比如现在是9月11号星期二上午10点，时间轮转一圈是24小时，到任务一下次执行（下周二上午九点）,需要时间轮转过6圈后，到第7圈的第9个刻度开始执行。
任务二下次执行第3圈的第9个刻度，任务三是第2圈的第9个刻度。
示意图如下：
时间轮每移动到一个刻度时，遍历任务列表，把round值-1，然后取出所有round=0的任务执行。 这样做能解决时间轮刻度范围过大造成的空间浪费，但是却带来了另一个问题：时间轮每次都需要遍历任务列表，耗时增加，当时间轮刻度粒度很小(秒级甚至毫秒级)，任务列表又特别长时，这种遍历的办法是不可接受的。 当然，对于大多数场景，这种方法还是适用的。 有没有既节省空间，又节省时间的办法呢？答案是有的，正如《Hashed and Hierarchical Timing Wheels》标题中提到的，有一种分层时间轮，可以解决做到既节省空间，又节省时间：
分层时间轮
分层时间轮是这样一种思想：
1. 针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。
2. 针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。
第一点很好理解，第二点有必要举个例子来说明：
比如我有三个任务：
1. 任务一每周二上午九点。
2. 任务二每周四上午九点。
3. 任务三每个月12号上午九点。
三个任务涉及到四个时间单位：小时、天、星期、月份。
拿任务三来说，任务三得到执行的前提是，时间刻度先得来到12号这一天，然后才需要关注其更细一级的时间单位：上午9点。
基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。
月轮的时间刻度是天。
周轮的时间刻度是天。
天轮的时间刻度是小时。
初始添加任务时，任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。
三个时间轮以各自的时间刻度不停流转。
当周轮移动到刻度2(星期二)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
同理，当月轮移动到刻度12(12号)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
这样就可以做到既不浪费空间，有不浪费时间。
整体的示意图如下所示：
时间轮的应用
时间轮的思想应用范围非常广泛，各种操作系统的定时任务调度，Crontab,还有基于java的通信框架Netty中也有时间轮的实现，几乎所有的时间任务调度系统采用的都是时间轮的思想。
至于采用round型的时间轮还是采用分层时间轮，看实际需要吧，时间复杂度和实现复杂度的取舍。
