定义

时间轮（Time Wheel）是一种数据结构，通常用于处理定时任务和时间相关的操作。它类似于定时器或调度器，可以在未来的某个时间点执行特定的任务或操作。时间轮的主要思想是将一系列任务按照时间分配到不同的槽中，然后以固定的时间间隔轮转，执行到期的任务。

时间轮通常由以下主要组件构成：

1. 时间槽（Time Slot）：时间轮被分割成一系列固定大小的时间槽，每个槽代表一个时间段。任务被放置在适当的时间槽中，以便在特定时间触发执行。
2. 指针（Pointer）：时间轮中有一个指针，指向当前时间槽，表示当前的时间。
3. 槽队列（Slot Queue）：每个时间槽可以包含一个任务队列，其中存储了将在该槽到期时执行的任务。
4. 时间间隔（Tick Interval）：时间轮按固定时间间隔（例如1秒）前进一格，将指针移动到下一个时间槽。任务的到期时间与当前时间加上多个时间间隔相关联。

具体如下图所示：

时间轮是一个高性能，低消耗的数据结构。

使用场景

• 定时任务调度，特别是海量任务场景下基本都能见到时间轮的身影

执行过程

在时间轮内，指针指向轮子上的一个槽。 它以恒定的速率顺时针转动。每转动一步就指向下一个槽，每次转动称之为一个tick。 一个滴答的时间称为时间轮的槽间隔si（slot interval），它实际上就是心搏时间。 时间轮共有N个槽，因此它运转一周的时间是Nsi。 每个槽指向一个定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差Nsi的整数 倍。 时间轮正式利用这个关系将定时器散列到不同的链表中。 假如：现在指针指向槽cs，我们要添加一个定时时间为ti的定时器，则该定时器将被插入槽ts（timer slot）对应的链表中：

ts = (cs + (ti / si)) % N

比如有一个时间轮，60个槽，每次转移需要1秒，起始位置指向0，有一个定时任务每5秒运行一次，执行图实例如下所示：

如果某个任务需要80秒执行一次，那么上述案例中的时间轮刻度将不够用，有几种解决方案：

• 增大时间轮刻度
• 列表中的任务增加round属性
• 分层时间轮

增大时间轮刻度

解决方案：

• 将60个刻度变成160个刻度

缺点：

• 时间刻度太多会导致时间轮走到的多数刻度没有任务执行
• 存储空间变大，利用率遍地

添加round属性

计算逻辑：

• round = 80/60 = 1，任务将放到刻度为20的任务链表中

执行过程：

• 每转动一次，遍历任务链表，执行round=0的任务，将任务的round-1。

缺点：

• 每次转动都需要去遍历任务，当任务列表很长的时候性能较低

分层时间轮

添加分钟轮：每一个刻度代表一分钟。

以第一次执行为例，当分钟轮到达1时，将任务丢给秒轮当前刻度+20刻度处，20秒后执行任务。

分层时间轮解决了上面两种方案的问题，并在各种开源框架Netty、kafka中广泛应用。