摘要.
# 缘起
数组和链表结合起来的数据结构被大量应用在操作系统、计算机网络，甚至是在 Apache 开源项目中。时间轮算法就是这种算法. 今天我们来了解一下这种算法.
# 分析
如何重新设计定时器算法
说到定时器（Timer），你应该不会特别陌生。像我们写程序时使用到的 Java Timer 类，或者是在 Linux 中制定定时任务时所使用的 cron 命令，亦或是在 BSD TCP 网络协议中检测网络数据包是否需要重新发送的算法里，其实都使用了定时器这个概念。那在课程的开头，我想先问问你，如果让你来重新设计定时器算法的话，会如何设计呢？
本质上，定时器的实现是依靠着计算机里的时钟来完成的。举个例子，假设时钟是每秒跳一次，那我们可以根据时钟的精度构建出 10 秒或者 1 分钟的定时器，但是如果想要构建 0.5 秒的定时器是无法做到的，因为计算机时钟最快也只能每一秒跳一次，所以即便当我们设置了 0.5 秒的定时器之后，本质上这个定时器也是只有 1 秒。当然了，在现实中，计算机里时钟的精度都是毫微秒（Nanosecond）级别的，也就是十亿分之一秒（1e-9）。
那回到设计定时器这个算法中，一般我们可以把定时器的概念抽象成 4 个部分（你可以理解为定时器的四个组件），它们分别是：
组件 1: 初始化定时器，规定定时器经过了多少单位时间之后超时，并且在超时之后执行特定的程序（生命的开始）；
组件 2: 删除定时器，终止一个特定的定时器（生命的结束）；
组件 3: 定时器超时进程，定时器在超时之后所执行的特定程序（即回调）；
组件 4: 定时器检测进程，假设定时器里的时间最小颗粒度为 T 时间（例如上面举例中的 1 秒），则每经过 T 时间之后都会执行这个进程来查看是否定时器超时，并将其移除。该组件 4 一旦检测到超时的定时器就会将其移除并执行组件 3 的回调.
你可能会问，如果我们只学习了数组和链表这两种数据结构，难道就可以设计一个被如此广泛应用的定时器算法了吗？完全没问题的，那我们就由浅入深，一起来看看各种实现方法优缺点吧。下面的所有算法我们都假设定时器超时时间的最小颗粒度为 T
维护无序定时器列表
最简单粗暴的方法，当然就是直接用数组或者链表来维护所有的定时器了。从前面的学习中我们可以知道，在数组中插入一个新的元素所需要的时间复杂度是 O(N)，而在链表的结尾插入一个新的节点所需要的时间复杂度是 O(1)，所以在这里可以选择用链表来维护定时器列表。假设我们要维护的定时器列表如下图所示：
它表示现在系统维护了 3 个定时器，分别会在 3T、T 和 2T 时间之后超时。如果现在用户又插入了一个新定时器，将会在 T 时间后超时，我们会将新的定时器数据结构插入到链表结尾，如下图所示：
每次经过 T 时间之后，定时器检测进程都会从头到尾扫描一遍这个链表，每扫描到一个节点的时候都会将里面的时间减去 T，然后判断这个节点的值是否等于 0 了，如果等于 0 了，则表示这个定时器超时，执行定时器超时进程并删除定时器，如果不等于，则继续扫描下一个节点。
这种方法的好处是定时器的插入和删除操作都只需要 O(1) 的时间。但是每次执行定时器检测进程的时间复杂度为 O(N)。如果定时器的数量还很小时还好，如果当定时器有成百上千个的时候，定时器检测进程就会成为一个瓶颈了。
维护有序定时器列表
这种方法是上述方法的改良版本。我们可以还是继续维护一个定时器列表，与第一种方法不一样的是，每次插入一个新的定时器时，并不是将它插入到链表的结尾，而是从头遍历一遍链表，将定时器的超时时间按从小到大的顺序插入到定时器列表中。还有一点不同的是，每次插入新定时器时，并不是保存超时时间，而是根据当前系统时间和超时时间算出一个绝对时间（即时间戳）出来。例如，当前的系统时间为 NowTime，超时时间为 2T，那这个绝对时间就为 NowTime + 2T。
假设原来的有序定时器列表如下图所示：
当我们要插入一个新的定时器，超时的绝对时间算出为 25 Dec 2019 9:23:34，这时候我们会按照超时时间从小到大的顺序，将定时器插入到定时器列表的开头，如下图所示：
维护一个有序的定时器列表的好处是
每次执行定时器检测进程的时间复杂度为 O(1)！！！
因为每次定时器检测进程只需要判断当前系统时间是否是在链表第一个节点时间之后了，如果是则执行定时器超时进程并删除定时器，如果不是则结束定时器检测进程。
这种方法的好处是执行定时器检测进程和删除定时器的时间复杂度为 O(1)，但因为要按照时间从小到大排列定时器，每次插入的时候都需要遍历一次定时器列表，所以插入定时器的时间复杂度为 O(N)。
其实这个比较 tricky 的思路在【1】中已经写过了——思想都是相通的~ 只有傻瓜才执着于技术本身.
插入操作不频繁的情况下，这种设计是可取的. 但是如果插入操作比较频繁的话，怎么改进一下插入的效率呢? 时间轮横空出世了~
维护定时器 “时间轮”
“时间轮”（Timing-wheel ）在概念上是一个用数组并且数组元素为链表的数据结构来维护的定时器列表，常常伴随着溢出列表（Overflow List）来维护那些无法在数组范围内表达的定时器。 “时间轮”有非常多的变种，今天我来解释一下最基本的 “时间轮” 实现方式。注意，时间轮中存储的时间都是绝对时间，这一点和上面的维护有序链表定时器是一样的.
首先基本的 “时间轮” 会将定时器的超时时间划分到不同的**周期（Cycle）**中去，数组的大小决定了一个周期的大小。例如，一个 “时间轮” 数组的大小为 8，那这个 “时间轮” 周期的大小就为 8T。更严格的说，我们维护一个最基本的 “时间轮” 需要维护以下几个变量：
- “时间轮” 的周期数，用 S 来表示；
- “时间轮” 的周期大小，用 N 来表示；（例如上面的举例为 8T，也就是数组的大小）
- “时间轮” 数组现在所指向的索引，用 i 来表示。
现在的时间我们可以用 S×N + i 来表示，每次我们执行完一次定时器检测进程之后，都会将 i 加 1。当 i 等于 N 的时候，我们将 S 加 1，并且将 i 归零。因为 “时间轮” 里面的数组索引会一直在 0 到 N－1 中循环，所以我们可以将数组想象成是一个环，例如一个 “时间轮” 的周期大小为 8 的数组，可以想象成如下图所示的环：
那么我们假设现在的时间是 S×N + 2，表示这个 “时间轮” 的当前周期为 S，数组索引为 2，同时假设这个 “时间轮” 已经维护了一部分定时器链表，如下图所示（ 有 2 个 S×N + 6 定时器）：
如果我们想新插入一个超时时间为 T 的新定时器进这个时间轮，因为 T 小于这个 “时间轮” 周期的大小 8T，所以表示这个定时器可以被插入到当前的 “时间轮” 中，插入的位置为当前索引为 1 + 2 % 8 = 3 ，插入新定时器后的 “时间轮” 如下图所示：
如果我们现在又想新插入一个超时时间为 9T 的新定时器进这个 “时间轮”，因为 9T 大于或等于这个“时间轮” 周期的大小 8T，所以表示这个定时器暂时无法被插入到当前的周期中，我们必须将这个新的定时器放进溢出列表里。溢出列表存放着新定时器还需要等待多少周期才能进入到当前 “时间轮” 中，我们按照下面公式来计算还需等待的周期和插入的位置：
还需等待的周期：9T / 8T = 1
新定时器插入时的索引位置：(9T + 2T) % 8T = 3
我们算出了等待周期和新插入数组的索引位置之后，就可以更新溢出列表，如下图所示：
在 “时间轮” 的算法中，定时器检测进程（定时器组件 4）只需要判断 “时间轮” 数组现在所指向的索引里的链表为不为空（即里面有没有超时的定时器），如果为空则不执行任何操作，如果不为空则对于这个数组元素链表里的所有定时器执行定时器超时进程（定时器的组件 3）。而每当 “时间轮” 的周期数加 1 的时候，系统都会遍历一遍溢出列表里的定时器是否满足当前周期数，如果满足的话，则将这个位置的溢出列表全部移到 “时间轮” 相对应的索引位置中。注意为了溢出链表的判断复杂度比较低，溢出链表的维护也是有序的.
在这种基本 “时间轮” 的算法里，定时器检测进程（定时器组件 4）的时间复杂度为 O(1)，而插入新定时器的时间复杂度取决于超时时间（即上面举例中的 T 还是 9T），因为插入的新定时器有可能会被放入溢出列表中从而需要遍历一遍溢出列表以便将新定时器放入到相对应周期的位置。如果没有超时的话，则直接插入数组（即图中的大圆环）处挂的链表即可（因为数组同一位置表示超时时间一样，那谁前谁后没关系）, 即插入是 O(1) 的. 但是如果跑到溢出链表中去了的话，就是 O(n) 的了.
你看，超时时间在当前时间周期内的时候，插入是 O(1) 的，这一定程度上就优化了单纯有序链表维护定时器的缺点. 代价就是你要再单独维护一个溢出链表罢了.
但是，在上述基本的时间轮的溢出链表中插入依旧没办法做到 O(1) 的. 所以我们有了变种时间轮的优化
你看，一个精妙的算法从来都不是一蹴而就的~ 而是随着需求的不断升级而演进的~
“时间轮” 变种算法
基本的 “时间轮” 插入操作因为维护了一个溢出列表导致定时器的插入操作无法做到 O(1) 的时间复杂度，所以为了 O(1) 时间复杂度的插入操作，一种变种的 “时间轮” 算法就被提出了。
在这个变种的 “时间轮” 算法里，我们加了一个 MaxInterval 的限制，这个 MaxInterval 其实也就是我们定义出的 “时间轮” 数组 N 的大小。假设 “时间轮” 数组的大小为 N，对于任何需要新加入的定时器，如果超时（绝对）时间小于 N 的话，则被允许加入到 “时间轮” 中，否则将不被允许加入。
注意，什么叫超时绝对时间? 还是以上面的例子为例，当前时间是 2T, 然后超时 T 的定时器想加进来，则绝对超时时间就是 3T，这个 3T 是相对于当前时间轮周期的起点而言的，这个 3T 就是超时绝对时间. 兹麻里，只有 3T <N, 该定时器才能被加入时间轮，否则拒绝其加入.
这种 “时间轮” 变种算法，执行定时器检测进程还有插入和删除定时器的操作时间复杂度都只有 O(1)。
但是，这样也太霸道了吧? 意思就是告诉客户端，您这定时器关注的时间太久远了，您等等再提吧~ 咱们这时间轮只关注一个周期 N 内的事情.
那么怎么实现这个变种时间轮算法呢? 就是下面马上要讲的分层时间轮
分层 “时间轮”
上面所描述到的 “时间轮” 变种算法，当我们要表达的 MaxInterval 很大而且超时时间颗粒度比较小的时候，会占用比较大的空间。例如，如果时间颗粒度是 1 秒，而 MaxInterval 是 1 天的话，就表示我们需要维护一个大小为 24 × 60 × 60 = 86400 的数组（话说，86400 的数组很大吗？手动笑哭~）。
那有没有方法可以将空间利用率提高，而同时保持着执行定时器检测进程还有插入和删除定时器的操作时间复杂度都只有 O(1) 呢？答案是使用分层 “时间轮”（Hierarchical Timing Wheel）。下面还是以时间颗粒度是 1 秒，而 MaxInterval 是 1 天的例子来说明分层 “时间轮” 算法。
我们可以使用三个 “时间轮” 来表示不同颗粒度的时间，分别是小时 “时间轮”、分钟“时间轮” 和秒 “时间轮”，可以称小时“时间轮” 为分钟 “时间轮” 的上一层 “时间轮”，秒“时间轮” 为分钟 “时间轮” 的下一层 “时间轮”。分层“时间轮” 会维护一个“现在时间”，
四不四让你想起了机械手表?
每层 “时间轮” 都需要各自维护一个当前索引来表示 “现在时间”。例如，分层“时间轮” 的“现在时间”是 22h:20min:30s，它的结构图如下图所示：
当每次有新的定时器需要插入进分层 “时间轮” 的时候，将根据分层 “时间轮” 的“现在时间”算出一个超时的绝对时间。例如，分层 “时间轮” 的“现在时间”是 21h:20min:30s，而当我们要插入的新定时器超时时间为 50 分钟 10 秒时，这个超时的绝对时间则为 22h:10min:40s。
我们需要先判断最高层的时间是否一致，如果不一致的话则算出时间差，然后插入定时器到对应层的 “时间轮” 中，如果一致，则到下一层中的时间中计算，如此类推。在上面的例子中，最高层的时间小时相差了 22(22h:10min:40s 的小时数)－21（21h:20min:30s 的小时数） = 1 小时，所以需要将定时器插入到小时 “时间轮” 中的 (1 + 21) % 24 = 22 这个索引中，定时器列表里还需要保存下层 “时间轮” 所剩余的时间 10min:40s，如下图所示, 这就完成了该定时器的插入：
每经过一秒钟，秒 “时间轮” 的索引都会加 1，并且执行定时器检测进程。定时器检测进程需要判断当前元素里的定时器列表是否为空，如果为空则不执行任何操作，如果不为空则对于这个数组元素列表里的所有定时器执行定时器超时进程。需要注意的是，定时器检测进程只会针对最下层的 “时间轮” 执行（原因你看完下面的举例就明白了）。
如果秒 “时间轮” 的索引到达 60 之后会将其归零，并将上一层的 “时间轮” 索引加 1，同时判断上一层的 “时间轮” 索引里的列表是否为空，如果不为空，则按照之前描述的算法将定时器加入到下一层 “时间轮” 中去，如此类推。
举个例子吧~ 在经过一段时间之后，上面的分层 “时间轮” 会到达以下的一个状态（即当前时间变成 22:00:00）：
这时候上层 “时间轮” 索引里的列表不为空（挂着一个 10min:40s），将这个定时器加入的索引为 10 的分钟 “时间轮” 中，并且保存下层 “时间轮” 所剩余的时间 40s，如下图所示：
如此类推，在经过 10 分钟之后 (即当前时间来到 22:10:00)，分层“时间轮” 会到达以下的一个状态：
同样的，我们将这个定时器插入到秒 “时间轮” 中，如下图所示：
这个时候，再经过 40 秒，秒 “时间轮” 的索引将会指向一个元素，里面有着非空的定时器列表，然后执行定时器超时进程并将定时器列表里所有的定时器删除。这就是为什么前面说定时器检测进程只会针对最下层的 “时间轮” 执行
我们可以看到，采用了分层 “时间轮” 算法之后，我们只需要维护一个大小为 24（小时） + 60（分钟） + 60（秒） = 144 的数组，分层时间轮就比前面节约了太多的空间（节约了 600 倍空间，算法的力量！）. 而同时保持着执行定时器检测进程还有插入和删除定时器的操作时间复杂度都只有 O(1)——当然，前提依旧是保持前面说过的 霸道
现在想想看，为什么能节约这么多内存? 因为其实 86400 个位置不是每个位置都要检测是否有定时器超时的. 通过时针和分针的分类，极大的降低了需要检测的粒度.
Apache Kafka 的 Purgatory 组件
Apache Kafka 是一个开源的消息系统项目，主要用于提供一个实时处理消息事件的服务。与计算机网络里面的 TCP 协议需要用到大量定时器来判断是否需要重新发送丢失的网络包一样，在 Kafka 里面，因为它所提供的服务需要判断所发送出去的消息事件是否被订阅消息的用户接收到，Kafka 也需要用到大量的定时器来判断发出的消息是否超时然后重发消息。
而这个任务就落在了 Purgatory 组件上。在旧版本的 Purgatory 组件里，维护定时器的任务采用的是 Java 的 DelayQueue 类来实现的。DelayQueue 本质上是一个堆（Heap）数据结构，这个概念将会在第 09 讲中详细介绍。现在我们可以把这种实现方式看作是维护有序定时器列表的一种变种。这种操作的一个缺点是当有大量频繁的插入操作时，系统的性能将会降低（我个人不同意这种看法，因为有序链表是绝对的有序，而堆只是局部的有序，我仅仅维护局部的有序怎么可能比维护全局有序更耗时间呢? 我估计老师想表达的意思应该是堆的 pop 操作比有序链表的 pop 操作，即过期操作更加耗时吧~ 毕竟堆的 pop 操作是挂 log 的，而链表的 pop 操作是 O(1) 的）。
因为 Kafka 中所有的最大消息超时时间都已经被写在了配置文件里，也就是说我们可以提前知道一个定时器的 MaxInterval，所以新版本的 Purgatory 组件则采用的了我们上面所提到的变种 “时间轮” 算法，将插入定时器的操作性能大大提升。根据 Kafka 所提供的检测结果，采用 DelayQueue 时所能处理的最大吞吐率为 25000 RPS，采用了变种 “时间轮” 算法之后，最大吞吐率则达到了 105000 RPS。
OK，这节课就讲到这里啦，下一课时我将分享 “哈希函数的本质及生成方式”，记得按时来听课哈。
下面是转载另一篇大佬的文章【2】
# 从定时任务说起
自然界中定时任务无处不在，太阳每天东升西落，候鸟的迁徙，树木的年轮，人们每天按时上班，每个月按时发工资、交房租，四季轮换，潮涨潮落，等等，从某种意义上说，都可以认为是定时任务。 大概很少有人想过，这些 “定时” 是怎样做到的。当然，计算机领域的同学们可能对此比较熟悉，毕竟工作中的定时任务也是无处不在的：每天凌晨更新一波数据库，每天 9 点发一波邮件，每隔 10 秒钟抢一次火车票。。。 至于怎么实现的？很简单啊，操作系统的 crontab，spring 框架的 quartz, 实在不行 Java 自带的 ScheduledThreadPool 都可以很方便的做到定时任务的管理调度。 当你熟练的敲下“* * 9 * * ?” 等着神奇的事情发生时，你是否想过背后的 “玄机”？
# 初识时间轮
大概去年的时候，业务需要实现一个时间调度的工具，定时生成报表，同组的哥们儿想了一个取巧的办法：
- 启动时从 DB 读取 cron 表达式解析，算出该任务下次执行的时间。
- 下次执行的时间 - 当前时间 = 时间差。
- 向 ScheduleThreadPool 线程池中提交一个延迟上面算出来的时间差的执行的任务。
- 任务执行时，算一下这个任务下次执行的时间，算时间差，提交到线程池。
- 当任务需要取消时，直接调用线程池返回的 Future 对象的 cancel() 方法就行了。 当时稍微想了一 ScheduleThreadPool 是怎么做到定时执行提交过来的任务的，大概有个模糊的概念，后来就把这事忘了。再后来，一次在地铁上看到一篇文章，讲了一种叫做时间轮的定时任务调度思想，感觉想法很不错，当年那个模糊的概念似乎清晰了很多，再后来，一个偶然的机会，网上搜了一下，竟然有一篇专门讲解时间轮算法的论文，顿时兴奋无比，赶紧打印下来，在上班的地铁上读了半个月，总算读完了。 戳这里下载：《Hashed and Hierarchical Timing Wheels》 论文中的思路很简单但也十分巧妙，对算法不断的改进对比，各种操作系统，框架中的基于时间的调度算法都是基于时间轮的思想实现的。下面我们来看看，这个神奇的时间轮到底是怎样实现定时任务的调度的。
# 绝对时间和相对时间
定时任务一般有两种：
- 约定一段时间后执行。
- 约定某个时间点执行。 聪明的你会很快发现，这两者之间可以相互转换，比如给你个任务，要求 12 点执行，你看了一眼时间，发现现在是 9 点钟，那么你可以认为这个任务三个小时候执行。 同样的，给你个任务让你 3 个小时后执行，你看了一眼现在是 9 点钟，那么你当然可以认为这个任务 12 点钟执行。 我们先来考虑一个简单的情况，你接到三个任务 A、B、C（都转换成绝对时间），分别需要再 3 点钟，4 点钟和 9 点钟执行，正当百思不得其解时，不经意间你瞅了一眼墙上的钟表，瞬间来了灵感，如醍醐灌顶，茅塞顿开：
如上图中所示，我只需要把任务放到它需要被执行的时刻，然后等着时针转到这个时刻时，取出该时刻放置的任务，执行就可以了。 这就是时间轮算法最核心的思想了。 什么？时针怎么转？ while-true-sleep 下面让我们一点一点增加复杂度。
# 需要重复执行多次的任务
多数定时任务是需要重复执行，比如每天上午 9 点执行生成报表的任务。对于重复执行的任务，其实我们需要关心的只是下次执行时间，并不关心这个任务需要循环多少次，还是那每天上午 9 点的这个任务来说。
- 比如现在是下午 4 点钟，我把这个任务加入到时间轮，并设定当时针转到明天上午九点 (该任务下次执行的时间) 时执行。
- 时间来到了第二天上午九点，时间轮也转到了 9 点钟的位置，发现该位置有一个生成报表的任务，拿出来执行。
- 同时时间轮发现这是一个循环执行的任务，于是把该任务重新放回到 9 点钟的位置。即 setInterval 怎么实现? setTimeout 的回调里面放 setTimeout 啊~
- 重复步骤 2 和步骤 3。 如果哪一天这个任务不需要再执行了，那么直接通知时间轮，找到这个任务的位置删除掉就可以了。 由上面的过程我们可以看到，时间轮至少需要提供 4 个功能：
- 加入任务（上面的组件 1）
- 执行任务（上面的组件 3）
- 删除任务（上面的组件 2）
- 沿着时间刻度前进（上面的组件 4）
# 同一时刻存在多个任务
上面说的是同一个时刻只有一个任务需要执行的情况，更通用的情况显然是同一时刻可能需要执行多个任务，比如每天上午九点除了生成报表之外，还需要执行发送邮件的任务，需要执行创建文件的任务，还需执行数据分析的任务等等，于是你刚才可能就比较好奇的时间轮的数据结构到现在可能更加好奇了，那我们先来说说时间轮的数据结构吧。
# 时间轮的数据结构
首先，时钟可以用数组或者循环链表表示，这个每个时钟的刻度就是一个槽，槽用来存放该刻度需要执行的任务，如果有多个任务需要执行呢？每个槽里面放一个链表就可以了，就像下面图中这样：
同一时刻存在多个任务时，只要把该刻度对应的链表全部遍历一遍，执行（扔到线程池中异步执行）其中的任务即可。
# 时间刻度不够用怎么办？
如果任务不只限定在一天之内呢？比如我有个任务，需要每周一上午九点执行，我还有另一个任务，需要每周三的上午九点执行。一种很容易想到的解决办法是：
# 增大时间轮的刻度
一天 24 个小时，一周 168 个小时，为了解决上面的问题，我可以把时间轮的刻度（槽）从 12 个增加到 168 个，比如现在是星期二上午 10 点钟，那么下周一上午九点就是时间轮的第 9 个刻度，这周三上午九点就是时间轮的第 57 个刻度，示意图如下：
仔细思考一下，会发现这中方式存在几个缺陷：
- 时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就 2 个任务，我得移动 720 次，其中 718 次是无用功，这其实就是上面说的
会占用比较大的空间 - 时间刻度太多会导致存储空间变大，利用率变低，比如一个月就 2 个任务，我得需要大小是 720 的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了。 于是乎，聪明的你脑袋一转，想到另一个办法：
# 列表中的任务中添加 round 属性 (其实类似于上面溢出列表的方法)
这次我不增加时间轮的刻度了，刻度还是 24 个，现在有三个任务需要执行，
- 任务一每周二上午九点。
- 任务二每周四上午九点。
- 任务三每个月 12 号上午九点。 比如现在是 9 月 11 号星期二上午 10 点，时间轮转一圈是 24 小时，到任务一下次执行（下周二上午九点）, 需要时间轮转过 6 圈后，到第 7 圈的第 9 个刻度开始执行。 任务二下次执行第 3 圈的第 9 个刻度，任务三是第 2 圈的第 9 个刻度。 示意图如下：
时间轮每移动到一个刻度时，遍历任务列表，把 round 值 - 1，然后取出所有 round=0 的任务执行。 这样做能解决时间轮刻度范围过大造成的空间浪费，但是却带来了另一个问题：时间轮每次都需要遍历任务列表，耗时增加，当时间轮刻度粒度很小 (秒级甚至毫秒级)，任务列表又特别长时，这种遍历的办法是不可接受的。 当然，对于大多数场景，这种方法还是适用的。 有没有既节省空间，又节省时间的办法呢？答案是有的，正如《Hashed and Hierarchical Timing Wheels》标题中提到的，有一种分层时间轮，可以解决做到既节省空间，又节省时间：
# 分层时间轮
分层时间轮是这样一种思想：
- 针对时间复杂度的问题：不做遍历计算 round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。
- 针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。 第一点很好理解，第二点有必要举个例子来说明： 比如我有三个任务：
- 任务一每周二上午九点。
- 任务二每周四上午九点。
- 任务三每个月 12 号上午九点。 三个任务涉及到四个时间单位：小时、天、星期、月份。 拿任务三来说，任务三得到执行的前提是，时间刻度先得来到 12 号这一天，然后才需要关注其更细一级的时间单位：上午 9 点。 基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。 月轮的时间刻度是天。 周轮的时间刻度是天。 天轮的时间刻度是小时。 初始添加任务时，任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。 三个时间轮以各自的时间刻度不停流转。 当周轮移动到刻度 2(星期二) 时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到 9 点执行。 同理，当月轮移动到刻度 12(12 号) 时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到 9 点执行。 这样就可以做到既不浪费空间，有不浪费时间。 整体的示意图如下所示：
时间轮的应用 时间轮的思想应用范围非常广泛，各种操作系统的定时任务调度，Crontab, 还有基于 java 的通信框架 Netty 中也有时间轮的实现，几乎所有的时间任务调度系统采用的都是时间轮的思想。 至于采用 round 型的时间轮还是采用分层时间轮，看实际需要吧，时间复杂度和实现复杂度的取舍。
# 参考
【2】http://blog.lanjingdejia.com/articles/2018/08/13/1534132662997.html https://yfscfs.gitee.io/post/%E4%BB%A4%E4%BA%BA%E6%83%8A%E8%89%B3%E7%9A%84%E6%97%B6%E9%97%B4%E8%BD%AE%E7%AE%97%E6%B3%95timingwheel/ https://yfscfs.gitee.io/post/%E4%BB%A4%E4%BA%BA%E6%83%8A%E8%89%B3%E7%9A%84%E6%97%B6%E9%97%B4%E8%BD%AE%E7%AE%97%E6%B3%95timingwheel/