一、背景
因为前公司有个项目(一个给运营同学使用的可以通过配置化 实现 圈取人群并发送 红包，优惠券，短信，push, 站内信等等 推送能力的 营销推送系统,其中大部分的任务都是延迟定时发送方式,所以当时实现的时候大量使用了公司基础中间件团队开发的延迟消息中间件,可以实现指定时间推送任务的能力), 在阅读这个中间件源码的时候, 发现其中借鉴了时间轮算法的思想,所以就研究了下。
首先说一下，时间轮算法真心有点绕，但它的思想是在现实生活中有相关的模型的，那就是时钟，研究了相关实现算法之后，对 时钟 这个生活中看似 普普通通的习以为常的东西 佩服的很啊，发明这些东西的人真的厉害啊，当然 实现了时间轮算法的大牛们 也一样厉害，别人写出来的算法，活生生研究了两天才算是完全搞明白，在此记录下
二、算法以及源码实现
本文也是我在阅读一些网友的分析文章之后，因为觉得他们对于算法实现的的一些"连接点"没有很清晰的说明,当时看完之后，自己又琢磨了很久，想明白了之后，主要是在那些文章的基础上完善这些 介绍相薄弱的"连接点"的内容。所以再阅读这篇文章之前，建议阅读以下关于时间轮的基本知识。我阅读的相关文章有
https://my.oschina.net/anur/blog/2252539 这篇文章里还有一些引用也可以一并看下。下面是一些关于我的理解：
时间轮：我自己觉得也可以叫做 "时间线"，因为时间是一直往前的，如果用时间戳表示的话就是一个不断增大的long类型的数字，但是为什么它又叫做"轮"呢，轮就有循环,后来者居上的意思 . 解释这个之前我们先看看层次时间轮一般的模型吧
如上面3张图，图1 是现实生活中的钟表，其分别有有秒针,分针，时针，而一个表盘被分成了60个刻度(也可以看成60个格子，这里采用刻度这一说法吧其实两者表示含义是一样的但因为秒针每走一次之后会落在下一个刻度线上，这样好理解一些)。因为有60个刻度，所以也可以看成一个60进制的计数系统, 秒针走一圈，分针走一个刻度，而时针不变(因为时针走一个刻度其实是一个小时,此时还没到)。所以这个钟表就使用了3个计树器来表示了12小时的秒数也就是 12*60*60=43200 秒。当然对于大于这个树的时间也延生出了 周，月，年，等等，本质上也是一种进制的思想。 对于基本的表盘而言这个计时器的时间精度也就是到秒了，无法衡量比秒更精确地时间了。虽然表盘上的刻度一直是在不断循环的，但因为现实中的时间一直是在流逝的，表示时间的这个时间戳是在不断增大的，所以其实，个人觉得时间轮可以用下面的图表示：
解释下上面的图：首先说明一下，上图展示了3个表盘，他们拥有相同的刻度数量10个。第一个每个刻度代表前进20ms的计数器盘。第二个是每个刻度代表前进200ms(也就是第一个走完一周的)的计数器盘，第三个是每个刻度代表前进2000ms(也就是第二个走完一周的)的计数器盘。我们能表示的时间范围是固定的——当然这个范围固定是指这里限定了只有三个轮子，可以想象成一个分别只有秒针，分针，时针的表盘，对于同一个表盘而言，他们都有10个刻度(时钟是60个刻度)，每个刻度代表时间向前移动20个单位(单位可以是 毫秒，秒，分，时等等。时钟每个刻度是 1个单位也就是1s)。但后一个表盘的一个刻度是前一个表盘从开头到结尾时间的总和，这个很重要，因为为了能表示超过第一个或者第二个表盘时间范围的时间，只能不断调大表盘刻度所代表的的时间范围。最后虽然三个表盘加起来能表示的时间范围是有限的，但因为有一个currentTime(表示当前时间的指针) 一直在向前进也就是不断在变大，所以，这个currentTime指针加上一个刻度就能`不断`表示 未来一段时间范围内时间戳。(不断增减表盘就能增加表示的未来的时间范围)
对于跟时间挂钩的任务来说，我们把任务挂在相应的时间点下面等时间一到就执行任务就ok了。对于延时任务而言，无非就是挂载的时间点是将来的某个时间点而已。所以分析下来,无非就是把任务挂在某个时间点，然后驱动currentTime 指针向前走，遇到某个时间点下面挂载的有任务，就执行。还是比较抽象，我们举几个例子：
假设前提：currentTime指针 指向现在 假如是 晚上 20:00:00:000 精确到毫秒 ，假如这个时间点对应的时间戳long timeStamp 是 0 (假设，方便下面计算)
举例0：我在现在也就是20:00:00:000 (时间戳是0) 想让时间在5ms之后也就是20:00:00:005 时 放一首歌(一个任务)，那很显然我只需要把这个任务挂在 图4 的 currentTime指针位置就行了。为什么？因为表盘最小颗粒度一个刻度就代表了20ms，5ms包含在内无法区分，直接就执行了。
举例1 ：我在现在也就是20:00:00:000 (时间戳是0) 想让时间在20ms之后也就是20:00:00:023 时 放一首歌(一个任务)，那很显然我只需要把这个任务挂在 图4 的 20和40 交接的那个刻度上就ok了。然后currrentTime 继续以一个刻度20ms前进, 发现20和40交界线处有个任务，然后就取出任务，此时任务的真实执行时间是20:00:00:023 , 而currentTime 是20:00:00:020，他们只差3ms，小于一个刻度的时间了，所以也就立即执行了
举例2：其他条件跟举例1一样，我只是想在当前时间 加230 毫秒 也就是 20：00：00：230 时执行一个闹钟，此时这个任务就应该挂在200和400相交的那条线上,因为此时第二个轮子，每个刻度表示200ms,就相当于此时表盘的精度是 200ms，无法再区分比这更精确地范围了，所以在200ms~400之间的任务都会在 20：00：00：200 的时候被拿出来，但此时我们需要对拿出的任务做下检查，此任务是否应该执行，因为其实我们最小的表盘最小刻度是20ms，也就是精度，也就说我们能精确到当前时间+20ms内的时间，但此时我们拿出的任务的它的执行时间是 20：00：00：230(当前时间是20：00：00：200), 它需要在30ms之后执行的，也就是说这个30ms大于了我们的最小表盘的的刻度时间，我们还不能执行，需要等真实时间消耗20ms (最小刻度盘刻度走完一个也就是20ms之后) , 此时当前时间是20：00：00：220， 任务执行时间只比当前时间多10ms , 小于最小盘的精度20ms 就能 执行了。那应该怎么做呢————解决办法：因为这个任务是在20：00：00：200 的时候拿出来的，也就是说currentTime当前时间是这个.任务执行时间只大于这个时间点 30ms，所以这个任务此时应该再次进行挂载，放在 20和40交界线上（从第二个时间轮跑到第一个时间轮了，一切都因为 currentTime变了这个很重要，不变的话，是挂不到第一个时间轮上面的）
补充一下：最小刻度也叫精度 也可以理解成 原子性操作无法拆分的，都是一个刻度一个刻度地执行，没有执行到中间的
嗯，通过上面三个例子 相关的任务执行机制 已经说清了。下面来分析下源码：
首先是时间轮（TimeWheel） 的相关介绍：
一个时间轮的定义就如图所以：
tickMs 就是一个刻度代表的时间范围
wheelSize 就是刻度数量
interval 就代表一个表盘能表示的时间范围 interval=tickMs*wheelSize
buckets 主要是用来盛放挂载在时间轮上某个时间刻度的任务的，数组下表其实就是一个个刻度记号，我们通过把任务的执行时间与当前时间的差值 然后除以一个刻度代表的范围也就是tickMs 再 对wheelSize 取余就得到了刻度下表也就是buckets 数组下表，然后就挂载任务就ok了。
currentTimestamp 这个是每个时间轮自己的当前时间，currentTimestamp 是 精度的整数倍，取整处理了
overflowWheel 对上面时间轮的引用
delayQueue 其实这个 阻塞队列一个是用来存储这些bucket的，还有一个是用来驱动时间使用的，具体会在下面解释
下面说一下 任务，因为不同的任务可能执行时间是一样的，所以 执行时间一样的任务，都被挂载在了同一个bucket 下了。
OK，系统需要的两个基本元素我们已经有了。下面就看看具体是什么算法让他们运行的吧
1： 一个Timer 管理器
众所周知，按照设计模式来说，异步任务执行，肯定是要有个时间任务管理器的——Timer, 这个管理器，一是提供给客户端一个 能随时添加 延迟任务 的接口。二是要能在任务指定的时间执行任务。我们一个个来分析。让我们从正常的业务场景出发，我们先添加一些延时任务
如下：
如上所示逻辑很清晰：具体的添加工作有 时间轮来完成，Timer 本来也只是做做管理，具体工作还是要下派啊，一个很重要的逻辑，68行 如果添加不进去而且没取消就 交给工作线程池执行了。这是一个很重要的点，可我们明明是添加逻辑啊，为什么跑到执行了呢，这是因为 如果一个任务 将要执行的时间 小于最小精度了也就是 20ms 了，那还添加啥啊，直接就执行了。就像 举例0 的案例一样 。接着看 TimeWheel.addTask(timedTask) 的逻辑：
如上所示主要逻辑：
1： 任务执行时间-当前时间 < 当前时间轮最小精度 返回false 也就是直接执行不需要挂载了
2： 任务执行时间-当前时间 大于等于 当前时间轮最小精度 小于 当前时间轮整个时间范围时 说明还是可以挂载在某个刻度下的 ，那就 根据 时间偏移 % 刻度数量，就得到了 bucket的下表位置，然后把 timedTask 假如到相应的bucket下，注意此时bucket 是挂载在某个刻度下的。时间是刻度的整数倍。如果这个刻度下也就是这个bucket下的第一个任务，那么就把这个bucket假如延迟队列里(为什么要加延迟队列？bucket能加说明bucket实现了Delayed接口，为什么？下面说)
3： 如果这个时间轮所能代表的时间范围不够，那就去上面一个时间轮去执行同样的逻辑进行挂载
看下 上一个时间轮的如何构造的：
如上所示：对于取父时间轮，其刻度所代表的时间范围是 本时间轮 一圈时间范围综合，刻度数量不变，delayQueue 一直是同一个，3个时间轮都是往一个延迟队列里塞。
以上就是 添加一个任务的逻辑总结一下：
1： 根据任务的时间和当前时间对比，如果小于当前时间轮的刻度时间范围，直接执行
2：大于等于一个刻度 小于整个 当前时间轮所能表示的时间，就 添加到相应的 bucket 下，bucket 加入延迟队列
3：如果大于当前时间轮所能表示的时间，那么就找到父亲时间轮(如果为null就创建)从1继续相同逻辑
到目前为止只有添加逻辑，时间轮的currentTime到目前为止还是刚创建时的时间戳，根本没有往前走，currentTime不往前走，他和 挂载在 时间线 下的任务的距离就一直 没有缩小，任务又怎么能触发执行呢？
所以当务之急就是 怎么把currentTime 往前走？答案就是 要借助 DelayQueue<Bucket> 了
还记得前面添加逻辑里 最终bucket是放进了 DelayQueue 里的，bucket 放进去后，就会按bucket时间大小 排列，从小往大 依次出队，当然要其时间在当前时间之后，就像 图4 那样 bucket 按照时间线 前进方向一个个挂载时间下，时间不到 ，不会出队，bucket里又放着这个刻度下 (这个时间点 所有需要执行的任务)。所以 Timer (时间管理器 )其实是通过 DelayQueue<Bucket>.poll(timeout, TimeUnit.MILLISECONDS) 的不断尝试阻塞地把任务出队的方式 模拟时间前进的效果：源码如下：
如上所以：
1：delayQueue 不断阻塞timeout的时间，timeout 一般为一个 最小盘的刻度时间，本文中20ms，用来模拟最小盘时间在向前进一个刻度的时间内，能获取到的这个刻度下 挂载的bucket，能取出来，说明这个bucket已经过了真实世界的当前时间了，已经过期了，但要注意
bucket 的时间 是刻度时间，也就是一个刻度时间范围的整数倍其实也是刻度开始时间，bucket里盛放的 任务的具体时间可以有差别，这个可以参考 举例2
2：如果经过一个刻度 ，这个刻度下挂载的有任务bucket，首先 先更新当前时间轮的 currentTime ，这个很重要，因为 延迟队列或者说真实的时间确实在前进，如果一旦发现有任务 ，时间轮的currentTime 就应该更新，而且这个更新 是需要递归地尝试更新 父时间轮。源码如下：
1: timestamp 代表取出的bucket时的时间,对于最小时间轮来说,因为时间往前走了一个刻度,所以timestamp至少等于currentTimestamp + tickMs,如果delayqueue.poll跳过几个没有挂载数据的刻度的话，那么timestamp 大于currentTimestamp + tickMs 但不管怎样，只要poll 出bucket后，currentTimestamp 就会和当前时间保持相对一致的，也算是一直懒处理吧
2: 尝试更新父时间轮,这个操作会只要overflowWheel不为null就会触发，但父currentTimestamp 不一定会改变，因为子时间轮一次20m前进，要走10次，才能到达父时间轮tickMs
最后一步：
其实就是对取出的bucket里的任务 做处理了，因为这个bucket有可能是从 第二个 或者 第三个时间轮刻度下取出的 bucket，所以 对于这些bucket 里的 TimedTask 的 执行时间有可能是大于 最小盘的一个刻度所能表示的时间的，因为第二个，三个时间轮 一个刻度 所代表的时间范围太大，比如第二时间轮的第一个刻度 表示 当前时间 +200ms , 在这个时间范围内的任务都放在一个bucket里了，所以我们需要对bucket里的task，从新执行 addTask(TimedTask) ,因为当前时间已经变了，所以需要重新计算他们的时间轮是第几个，以及任务所属的bucket 是哪一个，具体代码如下：
Consumer<TimedTask> flush 就是 addTask(TimedTask timedTask) 【上面已经分析过这份方法】，所以逻辑就是遍历bucket里的任务，然后重新添加一遍
总结：
1： 任务都属于某一个bucket，bucket 都挂载在某个刻度下，有一个时间范围
2：同时bucket 是一个延迟队里的元素
3：利用延迟队列阻塞出队的方式模拟时间线的前行，然后执行挂载在 时间刻度下 bucket 的取出
4： 取出bucket后，更新各个时间轮的当前时间，以减小和更未来任务执行时间的差距
5： 遍历取出bucket里的任务，如果任务执行时间和当前时间的差值小于最小时间轮一个刻度表示时间范围时，就可以执行了
以上就是整个执行流程了
回答几个问题：
1： 为什么用延迟队列
如果不用延迟队列模拟时间前进，还可以通过while循环，但是这样会一直在轮训，cpu也扛不住，如果while里sleep ，那就无法保证最小精度的执行了
2：为什么用bucket
首先bucket实现了 delayed , 属于阻塞队列的元素，那可不可以不要bucket，全部任务，直接挂到 具体的时间点下，这样的话 队列元素太多，而且入队时间复杂度是 O(logn), 而如果用bucket的话，就会减少元素入队的次数，而且 任务定位bucket是一个O(1)的复杂度
参考：
https://my.oschina.net/anur/blog/2252539
https://juejin.im/post/6844903648397525006
//www.greatytc.com/p/87240220097b
