背景：大规模延时任务、周期性任务、定时任务的存储和处理
例子：支付订单在30分钟内如果没有完成就应该取消；Kafka中在acks=all的情况下处理生产者请求，在一定时间内如果没能达成所有的同步副本写入消息就返回异常；Dubbo中调用失败，延时重试等
需求：设计一个合理的数据结构存储这些等待中的请求，使得整个系统能够高效地插入、检查、清理和执行这些任务
算法
| 优先队列（最小堆） | 简单时间轮 | 哈希时间轮 | 哈希分层时间轮 | |
|---|---|---|---|---|
| 插入Timeout | O(log n) | O(1) | O(1) | O(m) |
| 删除Timeout | O(log n) | O(1) | O(1) | O(1) |
| 超时检查 | O(n) | O(1) | 平均 O(1), 最差 O(n) | O(1) |
| N的含义 | Timeout数量 | 统一时间槽内的Timeout数量 | m 为分层数量 |
简单时间轮
时间轮：本质是环形的数组
时间槽(bucket)：数组中的元素，本质是双向链表
双向链表中的节点：定时的任务Timeout
时间单位(每个时间槽的时间跨度) tickTime：1s (kafka里1ms，netty/dubbo里1ns)
整个时间轮的时间跨度：数组长度 * 时间单位 = 20s
插入定时任务：定时任务定于2s内完成，也就是说2s后如果这个定时任务还未返回成功将会被清楚。插入时，时间轮会根据定时任务的延时时间找到相对于当前时间的时间槽，比如：当前时间为第0s，定时任务延时为2s，那么它就会找到第2s的时间槽的链表进行插入
检查超时任务：当tick走到下一个时间槽时，就把这个时间槽下的双向链表里的所有定时任务进行超时处理
定时任务的最大延时：时间轮的时间跨度，20s
复用走过的时间槽，使得任何时间插入的Timeout定时任务的延时都可以在一个时间轮的时间跨度内任意定义。
复杂度分析：
- 插入O(1)：插入时只需 延时时间+当前时间 找到对应的时间槽插入即可
- 删除O(1)：在双向链表中删除Timeout节点即可
- 超时检查O(1)：当前时间槽下的双向链表里的所有Timeout都是超时任务，不用一一检查，直接清空
- 空间复杂度O(u)：时间槽个数，取决于最大时间跨度
优点：复杂度低，所有操作都是O(1)
缺点：时间轮的空间复杂度过高/定时任务时延受限。如果我要插入一个延时为1000s的定时任务，我必须创建一个至少有1000个时间槽的时间轮，即使我只是为了跑这一个任务却要浪费剩下999个时间槽；并且时间轮的指针要遍历这999个时间槽才执行到这个任务。
哈希时间轮
解决的问题：简单时间轮中的定时任务时延受限，空间复杂度过高
比如此时定义这个时间轮的时间跨度为8s，那么所有的定时任务都会被存储在这8个时间槽中
插入定时任务：定时任务定义延时为11s后完成，插入时根据当前时间计算出过期时间，将过期时间对时间轮的时间跨度取余（11 % 8 = 3），因此该任务便会被插入到第3s的时间槽中的队列后面
检查超时任务：当指针推进到下一个时间槽时，就遍历时间槽下的双向链表里的所有定时任务进行超时检查并删除
定时任务的最大延时：任意
复杂度分析：
- 插入O(1)：插入时只需 延时时间+当前时间 找到对应的时间槽的链表末尾插入即可
- 删除O(1)：在双向链表中删除Timeout节点即可
- 超时检查平均O(1)最坏O(n)：最坏的情况，所有的定时任务都放在一个时间槽上
- 空间复杂度O(u)：时间槽个数
优点：空间复杂度为常量；定时任务延时不受限制
缺点：如果有频繁的哈希冲突就会使得超时检查的复杂度上升，变得和使用队列的方式没有区别
哈希分层时间轮
从某种角度讲，哈希分层时间轮是多级哈希表的变种。对于哈希时间轮来说，如果时间轮的时间跨度较小，load factor过大，哈希冲突变多，增删改查的操作的复杂度就会上升，所以我们希望再牺牲一些空间复杂度来使得更多定时任务的增删改查能够在O(1)复杂度内完成。
比如我们此时增加一个时间轮，每个时间槽的时间跨度为20s，整个时间轮的时间跨度就有400s。第二层的时间轮的指针只有在第一层的指针绕完一圈之后才会走一格，就像水表一样。
**插入定时任务：**当前时间为第2s，插入一个延时22s的定时任务，根据第一个时间轮的指针位置计算出过期时间点为第24s，发现在第一个时间轮里无法装下；转换到第2个时间轮，根据第2个时间轮的指针位置计算出定时时间应该被放在[20,39]的时间槽里，于是将该定时任务插入到第二个时间轮的[20,39]时间槽的双向链表后。
检查超时任务：第一个时间轮的指针每走过一个周期，第二个时间轮走一个时间槽。第二个时间轮每走1个时间槽，会把这个时间槽下所有的定时任务去除重新放入第一个时间轮中。比如，我们有一个在第24s超时的任务，当前时间为第20s，第一个时间轮已经走完一个周期，第二个时间轮的指针来到了[20,39]的时间槽上把里面所有在[20,39]范围内的定时任务取出对第一个时间轮的时间跨度取余插入相应的槽中。第一个时间轮的指针再继续遍历，和前面的哈希时间轮一样去将遍历到的时间槽里的定时任务进行超时处理。
定时任务的最大延时：任意。在kafka中，通过动态地创建时间轮能够避免掉延时溢出地问题。比如现在我们有2层时间轮，我在第2s插入一个延时为500s的定时任务，我们发现这个延时超过了我们这个两层时间轮系统的时间跨度(400s)，就会以这个时间跨度(400s)作为时间单位创建下一层时间轮，这样就有了3层时间轮，整个系统的时间跨度也到了8000s。
复杂度分析：
- 插入O(m)：虽然插入定时任务是从最外层的时间轮开始的，但是最后都是要插入到时间跨度最小的时间轮，所以需要O(m)，m为时间轮层级
- 删除O(1)：在双向链表中删除Timeout节点即可
- 超时检查O(1)：对于时间跨度最效的时间轮，也就是第一层的时间轮，它走过的每个时间槽都标志着这个时间槽内的所有定时任务超时不用一一检查
- 空间复杂度：表示第层时间轮的时间槽个数
优点：更高的空间利用率；两层时间轮只用了40个数组元素，却可以承载[0-399s]的定时任务，而三层时间轮用60个数组元素，就可以承载[0-7999s]的定时任务，相比于简单时间轮更加高效
缺点：时间轮指针的空推进问题依然没有解决(稀疏时间轮)；比如说, 插入一个延时时间400s的任务, 指针就要执行399次"空推进", 这其实是对CPU资源的浪费
Kafka 关于"空推进"的优化
Kafka通过使用DelayQueue来解决空推进的问题。
DelayQueue被用来存储时间槽也就是bucket也就是双向链表。
Kafka首先解耦了检查超时任务和时间轮指针推进的操作。我每10s检查有没有超时任务，但是如果检查完后发现没有超时的任务，那么时间轮的指针也不会向前推进；如果有超时任务，时间轮的指针只会推进到超时任务所在的时间槽。
Kafka在Timer(可以看作时间轮类的管理类，入口，依赖TimingWheel)的设计中将指针推进(advanceClock)这个操作开放出来，也就是在这里业务方可以指定一次超时检查的最大耗时为多久，而这就是由DelayQueue实现的。DelayQueue通过poll(long timeout, TimeUnit unit)来获取过期的bucket，如果在timeout内没有取到就放弃获取；如果获取到的bucket不为空，就将bucket里的定时任务进行过期处理，并且在此时才会触发时间轮内的指针按照bucket的过期时间转动。
可能有人会问这样和直接用DelayQueue来实现Timer有什么区别呢？区别其实就在于如果直接基于DelayQueue实现，它存的其实是一个定时任务Timeout；而在Kafka这里存的是有定时任务的时间槽bucket。bucket的数量是小于等于Timeout的数量，并且依赖于多层时间轮，层级越高的时间轮的bucket的时间跨度越大就能存越多的Timeout，所以会有一定的优化。
实现
线程模型
- 用户线程：负责定时任务的注册
- 定时任务队列轮询线程：负责扫描任务队列上符合要求的任务，如果任务的时间戳达到规定的时刻，首先从队列中取走此任务，然后将其交给异步线程池来处理
- 异步线程池：负责定时任务的执行
java.util.Timer
数据结构：优先队列
单线程执行，未解耦超时检查和任务执行；未对任务的异常进行处理，单个任务异常会导致后面的任务无法执行
适用场景：不推荐使用
java.util.concurrent.ScheduledThreadPoolExecutor
数据结构：优先队列
多线程执行，不会单线程阻塞；线程池模型处理异常，单任务出错不影响后续任务
适用场景：大多数场景都适用
java.util.concurrent.DelayQueue
数据结构：优先队列
单纯的容器；无线程模型；线程安全；容器里的元素只有到时后才能被取出
适用场景：作为定时器服务的数据结构来被维护
io.netty.util.HashedWheelTimer
数据结构：哈希时间轮
多线程执行；通过位运算提高哈希效率；更低复杂度的插入和过期检查
适用场景：高吞吐的定时系统
kafka.utils.timer
数据结构：哈希分层时间轮
无线程模型；Timer入口线程安全，TimingWheel线程不安全；通过指针连接各层时间轮；DelayQueue解决空推进
使用场景：高吞吐的定时系统