【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（上）

承接上文

承接之前的【精华推荐 |【算法数据结构专题】「延时队列算法」史上非常详细分析和介绍如何通过时间轮（TimingWheel）实现延时队列的原理指南】，让我们基本上已经知道了「时间轮算法」原理和核心算法机制，接下来我们需要面向于实战开发以及落地角度进行分析如何实现时间轮的算法机制体系。

前言回顾

什么是时间轮

• 调度模型：时间轮是为解决高效调度任务而产生的调度模型/算法思想。

• 数据结构：通常由 hash 表和双向链表实现的数据结构。

为什么用时间轮？

对比传统队列的优势

相比传统的队列形式的调度器来说，时间轮能够批量高效的管理各种延时任务、周期任务、通知任务等等。例如延时队列/延时任务体系

延时任务/队列体系

**延时任务、周期性任务，应用场景主要在延迟大规模的延时任务、周期性的定时任务等。

案例-Kafka 的延时操作系列

比如，对于耗时的网络请求（比如 Produce 时等待 ISR 副本复制成功）会被封装成 DelayOperation 进行延迟处理操作，防止阻塞 Kafka 请求处理线程，从而影响效率和性能。

传统队列带来的性能问题

Kafka 没有使用传统的队列机制（JDK 自带的 Timer+DelayQueue 实现）。因为时间复杂度上这两者插入和删除操作都是 O(logn)，不能满足 Kafka 的高性能要求。

基于 JDK 自带的 Timer+DelayQueue 实现

JDK Timer 和 DelayQueue 底层都是个优先队列，即采用了 minHeap 的数据结构，最快需要执行的任务排在队列第一个，不一样的是 Timer 中有个线程去拉取任务执行，DelayQueue 其实就是个容器，需要配合其他线程工作。

ScheduledThreadPoolExecutor 是 JDK 的定时任务实现的一种方式，其实也就是 DelayQueue+池化线程的一个实现。

基于时间轮 TimeWheel 的实现

时间轮算法的插入删除操作都是 O(1)的时间复杂度，满足了 Kafka 对于性能的要求。除了 Kafka 以外，像 Netty 、ZooKeepr、Dubbo 等开源项目、甚至 Linux 内核中都有使用到时间轮的实现。

当流量小时，使用 DelayQueue 效率更高。当流量大事，使用时间轮将大大提高效率。

时间轮算法是怎么样的，算法思想是什么？

时间轮的数据结构

数据结构模型主要由：时间轮环形队列和时间轮任务列表组成。

• 时间轮（TimingWheel） 是一个存储定时任务的环形队列（cycle array），底层采用环形数组实现，数组中的每个元素可以对应一个时间轮任务任务列表（TimeWheelTaskList） 。

• 时间轮任务任务列表（TimeWheelTaskList） 是一个环形的双向链表，其中的每个元素都是延时/定时任务项（TaskEntry），其中封装了任务基本信息和元数据（Metadata）。

可以看到图中的几个参数：

• startMs: 开始时间

• tickMs: 时间轮执行的最小单位。时间轮由多个时间格组成，每个时间格代表当前时间轮的基本时间跨度就是 tickMs。

• wheelSize: 时间轮中环形队列的数量。时间轮的时间格数量是固定的，可用 wheelSize 来表示。

• interval：时间轮的整体时间跨度 = tickMs * wheelSize

根据上面这两个属性，我们就可以讲整个时间轮的总体时间跨度（interval）可以通过公式 tickMs × wheelSize 计算得出。例如果时间轮的 tickMs=1ms，wheelSize=20，那么可以计算得出 interval 为 20ms。

currentTime 游标指针

此外，时间轮还有一个游标指针，我们称之为（currentTime），它用来表示时间轮当前所处的时间，currentTime 是 tickMs 的整数倍。

整个时间轮的总体跨度是不变的，随着指针 currentTime 的不断流动，当前时间轮所能处理的时间段也在不断后移，整个时间轮的时间范围在 currentTime 和 currentTime+interval 之间。

currentTime 可以将整个时间轮划分为到期部分和未到期部分，currentTime 当前指向的时间格也属于到期部分，表示刚好到期，需要处理此时间格所对应的 TimeWheelTaskList 中的所有任务。

currentTime 游标指针的运作流程

1. 初始情况下表盘指针 currentTime 指向时间格 0，此时有一个定时为 2ms 的任务插入进来会存放到时间格为 2 的任务列表中。

2. 随着时间的不断推移，指针 currentTime 不断向前推进，过了 2ms 之后，当到达时间格 2 时，就需要将时间格 2 所对应的任务列表中的任务做相应的到期操作。

3. 此时若又有一个定时为 8ms 的任务插入进来，则会存放到时间格 10 中，currentTime 再过 8ms 后会指向时间格 10。

总之，整个时间轮的总体跨度是不变的，随着指针 currentTime 的不断推进，当前时间轮所能处理的时间段也在不断后移，总体时间范围在 currentTime 和 currentTime+interval 之间。

层次化时间轮机制

如果当提交了超过整体跨度（interval）的延时任务，如何解决呢？因此引入了层级时间轮的概念，当任务的到期时间超过了当前时间轮所表示的时间范围时，就会尝试添加到层次时间轮中。

层次化时间轮实现原理介绍

层次化时间轮任务升级跃迁

在任务插入时，如果第一层时间轮不满足条件，就尝试插入到高一层的时间轮，以此类推。

• 第一层的时间轮 tickMs=1ms, wheelSize=20, interval=20ms

• 第二层的时间轮的 tickMs 为第一层时间轮的 interval，即为 20ms

第一层和第二层时间轮的 wheelSize 是固定的，都是 20，那么第二层的时间轮的总体时间跨度 interval 为 400ms。正好是第一层时间轮的 20 倍。以此类推，这个 400ms 也是第三层的 tickMs 的大小，第三层的时间轮的总体时间跨度为 8000ms。

• 第 N 层时间轮走了一圈，等于 N+1 层时间轮走一格。即高一层时间轮的时间跨度等于当前时间轮的整体跨度。

层次化时间轮任务降级跃迁

随着时间推进，也会有一个时间轮降级的操作，原本延时较长的任务会从高一层时间轮重新提交到时间轮中，然后会被放在合适的低层次的时间轮当中等待处理；

案例介绍

层次化时间轮任务升级跃迁

例如：350ms 的定时任务，显然第一层时间轮不能满足条件，所以就升级到第二层时间轮中，最终被插入到第二层时间轮中时间格 17 所对应的 TimeWheelTaskList 中。如果此时又有一个定时为 450ms 的任务，那么显然第二层时间轮也无法满足条件，所以又升级到第三层时间轮中，最终被插入到第三层时间轮中时间格 1 的 TimeWheelTaskList 中。

层次化时间轮任务降级跃迁

在 [400ms,800ms) 区间的多个任务（比如 446ms、455ms 以及 473ms 的定时任务）都会被放入到第三层时间轮的时间格 1 中，时间格 1 对应的 TimerTaskList 的超时时间为 400ms

随着时间的流逝，当次 TimeWheelTaskList 到期之时，原本定时为 450ms 的任务还剩下 50ms 的时间，还不能执行这个任务的到期操作。

这里就有一个时间轮降级的操作，会将这个剩余时间为 50ms 的定时任务重新提交到层级时间轮中，此时第一层时间轮的总体时间跨度不够，而第二层足够，所以该任务被放到第二层时间轮到期时间为[40ms,60ms)的时间格中。

再经历了 40ms 之后，此时这个任务又被“察觉”到，不过还剩余 10ms，还是不能立即执行到期操作。所以还要再有一次时间轮的降级，此任务被添加到第一层时间轮到期时间为[10ms,11ms)的时间格中，之后再经历 10ms 后，此任务真正到期，最终执行相应的到期操作。

后续章节预告

接下来小编会出【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮（TimingWheel）实现延时队列的开发实战落地（下），进行实战编码进行开发对应的层次化的时间轮算法落地。