时间轮算法 | newrain-zh博客

type

status

date

slug

summary

1.数据组织结构

时间轮常用数组+链表的形式(类似HashMap)，其中数组的每个槽(solt)或者说 bucket 表示时间精度，数组每个元素中存放的是双向循环链表，它里面存放的是要执行的任务。当currentTime 推进到某一时刻，就取出对应 solt 中的任务来执行。数组的整个长度决定了整个时间轮的时间范围，例如图 1 示例，数组的长度为 20，tickMs=1(毫秒)，则整个时间轮能够容纳的时间范围为 tickms * wheelSize = 20 毫秒，也就是 Interval。

初始情况下currentTime 指向时间solt 0，此时有一个定时为 2ms的任务添加进来，会存放 solt 2的 TimerTaskList 中。假设 currentTime指针指向了 10，此时有个 11 毫秒的任务添加进来，那么该任务会写入到之前已经到期的 solt 1 中，这也是为什么使用循环数组。

2. 溢出处理

2.1溢出列表

假设 tickMs = 1，当前数组的 size = 5，那么当前数组能表达的数组范围就是 [currentTime,5] 毫秒，超过这个周期范围，会放入溢出列表中。

假设 currentTime 为 00:03,此时若有大于00:03+5的任务，它将放入溢出列表中，这样currentTime 向前推移的过程中，可以遍历溢出列表，将符合条件的任务再次加入到时间轮的槽位中。在实际使用中会维护一个maxInterval，超过这个值的都不存放在时间轮中。

这个方案的缺点在于极端情况，若某个solt 因为同一时刻的任务过多时，链表很长。此时处理任务时，仍需遍历链表，导致响应延迟不稳定。

3.Kafka 多层时间轮

Kafka中存在大量的延时操作，比如延时生产、延时拉取、延迟删除等，Kafka 并没有采用 JDK 自带的 Timer或 DelayQueue 来实现延时的功能，而是基于时间轮的概念自定义了一个用于延时功能的定时器（SystemTimer）。为了解决溢出问题，它在时间轮的基础上扩展了多层时间轮。

3.1 数据组织的结构

图 1 描述了Kafka 的单层时间轮结构，数组+双向循环链表，这个双向循环列链表，多个了一个哨兵节点方便操作链表。

在处理溢出时，会新建多层时间轮，第一层的时间轮tickMs=1ms 、 wheelSize=20 、interval=20ms。第二层的时间轮的tickMs为第一层的 interval(20ms)，每一层的 wheelSize 是固定的都是二轮。所以第二层的总体时间跨度为 400ms(tickMs * wheelSize)，依次类推第三层的时间跨度为 8000ms。tickMs、wheelSize 都是可以根据配置来自行设定。只不过 kafka 追求的延时是毫秒级别的，所以采用该参数。

3.2 时间选择与对齐

TimingWhell 在创建的时候以当前系统时间为第一层时间轮的起始时间（startMs），但是这里的当前系统时间并没有选择简单的调用 System.currentTimeMillis 方法。而是调用了 Time.SYSTEM.hiResClockms,因为System.currentTimeMillis依赖于操作系统的具体实现，而且可能存在时间修改、回拨等问题。Kafka 的方案是获取当前的纳秒数然后转换成毫秒数，它是单调递增的，是 JVM 启动以来的时间。Kafka 的延时任务都是毫秒级的，它不像业务开发中常用的定时任务都具体到几点几分，精细度要求没那么高。业务开发中常用时分秒这种的多层时间轮，这种时间轮放置时间的计算比毫秒级别要好的多。

在创建时间轮时，通过 startMs 来构建第一层的时间轮currentTimeMs， 在这里要做时间对齐，确保 currentTimeMs 推进时是按tickMs整数倍推进和能够精确的将任务划分到 slot（配合添加任务时计算任务落到哪个 bucket 中）。

3.3 如何添加任务

添加任务时，首先会给任务设置一个过期时间，过期时间的计算在于用户设定的过期时间+hiResClockMs()。

这里有意思的是多层时间轮的结构,它以 TimerTaskList 为形式保存在了两个地方，一个就是以 bucket 为命名的数组，还有在延迟队列DelayQueue 保存了一份。

3.4 如何推进时间指针

推进时间指针的主要核心逻辑是更改当前时间轮的 currentTimeMs ,然后比较 bucket 的过期时间，如果过期，则取出 bucket 的双向循环链表执行任务，进行执行对应的任务（TaskEntry）。通常都常用线程或定时器去驱动整个时间轮的推进。通常 200ms 推进一次，获取到过期的 bucket,然后比较bucket 的过期时间是否大于等于 currentTimeMs+tickMs ，满足这个条件说明 bucket 的任务已经过期了，取出bucket中的所有任务，然后顺序执行并从链表删除（只删除 root 节点也就是哨兵节点以外的节点）。这整个过程也叫 ticket。虽然整体思路是这样的，但是 Kafka 在这个设计上做了更改。

前面提到过时间轮中的任务会在一个延时队列中保存一份，所以它在这里的推进方案是每 200ms 推进一次，先去延时队列中获取 bucket，bucket 的过期时间由于任务不断添加到同一个 bucket，所以bucket 的过期时间会变成最大过期，就意味着如果这个 bucket 的过期了，那代表它链表中的任务肯定都过期了，不需要再遍历链表中的每个节点的过期时间去判断，那么时间复杂度会成O(1)。虽然延时任务就可以获取过期的任务，但还是需要更改时间轮的时间指针（currentTimeMs）来保证整个时间轮向前推进，因为添加任务等 api 需要根据时间指针判断新添加的任务存放在哪个 bucket的。

在多层时间轮中，通常推进到第一层的末尾，需要将第二层的bucket 中的任务取出，并添加到一层的bucket中，依次类推到第 N 层，与时分秒的时间轮同理。

3.5 优化设计

3.4 已经说了部分的优化，时间轮运用的一种空间换时间的设计，在此基础上使用延时队列解决“空转”问题。

Kafka 的多层时间轮是按需创建的，也就是有溢出才会去创建，如果假设 tickMs为 1ms,wheelSize= 20,第一层时间的范围为最多只能表达 20毫秒内，如果此时添加的任务都是超过 20 毫秒，甚至几百毫秒，说明任务都在第二层，甚至是第四、第 5 层的 bucket 内，那么时间轮推进的时候，想要执行到最后一层的任务，必续一直做无效推进，因为前面的层级的 bucket 并没有任务。这样的无效代码执行，占用了 CPU，使用延时队列，如果堆顶元素没有过期，那么 poll 就阻塞，避免 CPU 执行无效指令来解决“空转”。