![[算法数据结构专题]「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(上)](/static/background/40.jpg "[算法数据结构专题]「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(上)")
承接上文
前言回顾
什么是时间轮
-
调度模型：时间轮是为解决高效调度任务而产生的调度模型/算法思想。
- 数据结构：通常由hash表和双向链表实现的数据结构。
为什么用时间轮？
对比传统队列的优势
相比传统的队列形式的调度器来说，时间轮能够批量高效的管理各种延时任务、周期任务、通知任务等等。例如延时队列/延时任务体系
延时任务/队列体系
案例-Kafka的延时操作系列
比如，对于耗时的网络请求（比如Produce时等待ISR副本复制成功）会被封装成DelayOperation进行延迟处理操作，防止阻塞Kafka请求处理线程，从而影响效率和性能。
传统队列带来的性能问题
时间复杂度上这两者插入和删除操作都是 O(logn，不能满足Kafka的高性能要求。
基于JDK自带的Timer+DelayQueue实现
ScheduledThreadPoolExecutor是JDK的定时任务实现的一种方式，其实也就是DelayQueue+池化线程的一个实现。
基于时间轮TimeWheel的实现
当流量小时，使用DelayQueue效率更高。当流量大事，使用时间轮将大大提高效率。
时间轮算法是怎么样的，算法思想是什么？
时间轮的数据结构
-
时间轮任务任务列表（TimeWheelTaskList） 是一个环形的双向链表，其中的每个元素都是延时/定时任务项（TaskEntry），其中封装了任务基本信息和元数据（Metadata）。
时间轮（TimingWheel） 是一个存储定时任务的环形队列（cycle array），底层采用环形数组实现，数组中的每个元素可以对应一个时间轮任务任务列表（TimeWheelTaskList） 。
-
时间轮执行的最小单位。时间轮由多个时间格组成，每个时间格代表当前时间轮的基本时间跨度就是tickMs。
-
时间轮中环形队列的数量。时间轮的时间格数量是固定的，可用wheelSize来表示。
-
时间轮的整体时间跨度 = tickMs * wheelSize
startMs: 开始时间
tickMs=1ms，wheelSize=20，那么可以计算得出interval为20ms。
currentTime游标指针
整个时间轮的总体跨度是不变的，随着指针currentTime的不断流动，当前时间轮所能处理的时间段也在不断后移，整个时间轮的时间范围在currentTime和currentTime+interval之间。
currentTime游标指针的运作流程
-
此时若又有一个定时为8ms的任务插入进来，则会存放到时间格10中，currentTime再过8ms后会指向时间格10。
初始情况下表盘指针currentTime指向时间格0，此时有一个定时为2ms的任务插入进来会存放到时间格为2的任务列表中。
总之，整个时间轮的总体跨度是不变的，随着指针currentTime的不断推进，当前时间轮所能处理的时间段也在不断后移，总体时间范围在currentTime和currentTime+interval之间。
层次化时间轮机制
层次化时间轮实现原理介绍
层次化时间轮任务升级跃迁
第一层的时间轮tickMs=1ms, wheelSize=20, interval=20ms
第一层和第二层时间轮的wheelSize是固定的，都是20，那么第二层的时间轮的总体时间跨度interval为400ms。正好是第一层时间轮的20倍。以此类推，这个400ms也是第三层的tickMs的大小，第三层的时间轮的总体时间跨度为8000ms。
- 第N层时间轮走了一圈，等于N+1层时间轮走一格。即高一层时间轮的时间跨度等于当前时间轮的整体跨度。
层次化时间轮任务降级跃迁
案例介绍
层次化时间轮任务升级跃迁
例如：350ms的定时任务，显然第一层时间轮不能满足条件，所以就升级到第二层时间轮中，最终被插入到第二层时间轮中时间格17所对应的TimeWheelTaskList中。如果此时又有一个定时为450ms的任务，那么显然第二层时间轮也无法满足条件，所以又升级到第三层时间轮中，最终被插入到第三层时间轮中时间格1的TimeWheelTaskList中。
层次化时间轮任务降级跃迁
随着时间的流逝，当次TimeWheelTaskList到期之时，原本定时为450ms的任务还剩下50ms的时间，还不能执行这个任务的到期操作。
再经历了40ms之后，此时这个任务又被“察觉”到，不过还剩余10ms，还是不能立即执行到期操作。所以还要再有一次时间轮的降级，此任务被添加到第一层时间轮到期时间为[10ms,11ms的时间格中，之后再经历10ms后，此任务真正到期，最终执行相应的到期操作。
后续章节预告
接下来小编会出【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下），进行实战编码进行开发对应的层次化的时间轮算法落地。
编程笔记 » [算法数据结构专题]「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(上)