理解定时器

很多场景会用到定时器，例如

  • 使用 TCP 长连接时，客户端需要定时向服务端发送心跳请求。
  • 财务系统每个月的月末定时生成对账单。
  • 双 11 的 0 点，定时开启秒杀开关。

定时器像水和空气一般，普遍存在于各个场景中，一般定时任务的形式表现为：经过固定时间后触发、按照固定频率周期性触发、在某个时刻触发。定时器是什么？可以理解为这样一个数据结构：

  • 存储一系列的任务集合，并且 Deadline 越接近的任务，拥有越高的执行优先级
  • 在用户视角支持以下几种操作：
    • NewTask：将新任务加入任务集合
    • Cancel：取消某个任务
  • 在任务调度的视角还要支持： Run：执行一个到期的定时任务

判断一个任务是否到期，基本会采用轮询的方式， 每隔一个时间片 去检查 最近的任务 是否到期，并且，在 NewTask 和 Cancel 的行为发生之后，任务调度策略也会出现调整。

说到底，定时器还是靠线程轮询实现的。

数据结构

我们主要衡量 NewTask（新增任务），Cancel（取消任务），Run（执行到期的定时任务）这三个指标，分析他们使用不同数据结构的时间 / 空间复杂度。

双向有序链表

LinkedList 是一个天然的双向链表

  • NewTask：O(N)
  • Cancel：O(1)
  • Run：O(1)

分析:

  • NewTask O(N) 很容易理解，按照 expireTime 查找合适的位置即可；Cancel O(1)
  • 任务在 Cancel 时，会持有自己节点的引用，所以不需要查找其在链表中所在的位置，即可实现当前节点的删除，这也是为什么我们使用双向链表而不是普通链表的原因；
  • Run O(1)，由于整个双向链表是基于 expireTime 有序的，所以调度器只需要轮询第一个任务即可。

最小堆

最小堆定时器的实现方式，是最常见的一种实现定时器的方式。堆顶时钟保存最先到期的定时器，基于事件触发的定时器系统可以根据堆顶定时器到期时间，进行睡眠。基于周期性睡眠的定时器系统，每次只需遍历堆顶的定时器是否到期，即可。堆顶定时器超时后，继续调整堆，使其保持为最小堆并同时对堆顶定时器进行超时判断。

PriorityQueue 是一个天然的堆，可以利用传入的 Comparator 来决定其中元素的优先级。expireTime 是 Comparator 的对比参数。

  • NewTask：O(logN)
  • Cancel：O(logN)
  • Run：O(1)

NewTask O(logN) 和 Cancel O(logN) 分别对应堆插入和删除元素的时间复杂度 ；

Run O(1)，由 expireTime 形成的最小堆，我们总能在堆顶找到最快的即将过期的任务。定时器超时处理时调整堆的复杂度在所有定时器都超时情况下为：O(nlgn)。

堆与双向有序链表相比，NewTask 和 Cancel 形成了 trade off，但考虑到现实中，定时任务取消的场景并不是很多，所以堆实现的定时器要比双向有序链表优秀。

时间轮

定时器的实现方式有两种：一级时间轮和层级时间轮。

一级时间轮

时间轮 是一个环形结构，可以用时钟来类比，钟面上有很多 bucket ，每一个 bucket 上可以存放多个任务，使用一个 List 保存该时刻到期的所有任务，同时一个指针随着时间流逝一格一格转动，并执行对应 bucket 上所有到期的任务。任务通过 取模 决定应该放入哪个 bucket 。和 HashMap 的原理类似，newTask 对应 put，使用 List 来解决 Hash 冲突。

以上图为例，假设一个 bucket 是 1 秒，则指针转动一轮表示的时间段为 8s，假设当前指针指向 0，此时需要调度一个 3s 后执行的任务，显然应该加入到 (0+3=3) 的方格中，指针再走 3 次就可以执行了；如果任务要在 10s 后执行，应该等指针走完一轮零 2 格再执行，因此应放入 2，同时将 round（1）保存到任务中。检查到期任务时只执行 round 为 0 的， bucket 上其他任务的 round 减 1。

再看图中的 bucket5，我们可以知道在 $8+5=13s$ 后，有两个任务需要执行，在 $16+5=21s$ 后有一个任务需要执行。

  • NewTask：O(1)
  • Cancel：O(1)
  • Run：O(M)
  • Tick：O(1)

M： bucket ，M ~ N/C ，其中 C 为单轮 bucket 数

时间轮算法的复杂度可能表达有误，比较难算，仅供参考。另外，其复杂度还受到多个任务分配到同一个 bucket 的影响。并且多了一个转动指针的开销。Run最坏情况O(M)，平均O(1),显然格子越多每个格子对应的List就越短，越接近O(1)；最坏情况下所有的任务都在一个格子中，O(M)。

传统定时器是面向任务的，时间轮定时器是面向 bucket 的。

时间轮 有两个重要的参数：tickDuration 和 ticksPerWheel。

  • tickDuration：即一个 bucket 代表的时间.
  • ticksPerWheel：一轮含有多少个 bucket ，如果任务较多可以增大这个参数，降低任务分配到同一个 bucket 的概率。

ticksPerWheel 控制了时间轮中 bucket 的数量，决定了冲突发生的概率，tickDuration 决定了指针拨动的频率，一方面会影响定时的精度，一方面决定 CPU 的消耗量。当任务数量非常大时，考虑增大 ticksPerWheel；当时间精度要求不高时，可以适当加大 tickDuration，不过大多数情况下，不需要 care 这个参数。

层级时间轮

如果定时器轮的精度是1ms，那么spoke个数为2^10时，仅仅能够表示1s，2^20表示17.476min.如果精度为1s，那么spoke个数为2^10时，能够表示17min，2^20表示12day.所有这种一级时间轮的实现方式所带来的空间复杂度还是不小的。特别是在需要跨度比较长的定时器时。基于此，就出现了层级时间轮.

如果任务的时间跨度很大，数量也多，传统的 时间轮 会造成任务的 round 很大，单个 bucket 的任务 List 很长，并会维持很长一段时间。这时可将轮盘按时间粒度分级：

层级时间轮的实现方式被比作经典的”水表实现方式”，一级时间轮只有一个进制，层级时间轮采用了不同的进制，最低级的时间轮每个spoke表示基本的时间精度，次级时间轮每个spoke表示的时间精度为最低级时间轮所能表示时间长度，依次类推。例如内核的时间轮采用5级时间轮，每一级时间轮spoke个数从低级到高级分别为：8,6,6,6,6，所能表达的时间长度为：2^6 2^6 2^6 2^6 2^8 = 2^32 ticks，在系统tick精度为10ms时，内核时间轮所能表示的时间跨度为42949672.96s，约为497天。

现在，每个任务除了要维护在当前轮盘的 round，还要计算在所有下级轮盘的 round。当本层的 round 为 0 时，任务按下级 round 值被下放到下级轮子，最终在最底层的轮盘得到执行。

  • NewTask：O(H)
  • Cancel：O(H)
  • Run：O(M)
  • Tick：O(1)

H：层级数量

设想一下一个定时了 3 天，10 小时，50 分，30 秒的定时任务，在 tickDuration = 1s 的单层时间轮中，需要经过：$3246060+106060+5060+30$ 次指针的拨动才能被执行。但在 wheel1 tickDuration = 1 天，wheel2 tickDuration = 1 小时，wheel3 tickDuration = 1 分，wheel4 tickDuration = 1 秒 的四层时间轮中，只需要经过 $3+10+50+30$ 次指针的拨动！

当时间跨度很大时，提升单层时间轮的 tickDuration 可以减少空转次数，但会导致时间精度变低，层级时间轮既可以避免精度降低，又避免了指针空转的次数。如果有时间跨度较长的定时任务，则可以交给层级时间轮去调度。

最佳实践

如何在时间堆和时间轮之间如何做选择，需要区分场景，做一个简单的对比：

  1. 时间堆是高精度版本定时器,是面向任务的，当任务数非常大时，使用堆 (PriorityQueue) 维护任务的新增、删除会导致性能下降，

  2. 时间轮是低精度版本定时器,面向 bucket，设置合理的 ticksPerWheel，tickDuration ，可以不受任务量的限制。所以在任务非常多时，时间轮可以表现出它的优势。相反，如果任务量少，时间轮内部的 Worker 线程依旧会不停的拨动指针，虽然不是特别消耗性能，但至少不能说：时间轮一定比时间堆优秀。时间轮 由于开辟了一个 bucket 数组，占用的内存会稍大。

上述的对比，让我们得到了一个最佳实践：在任务非常多且对时间精准度要求低时，使用时间轮可以获得性能的提升。例如服务治理框架中的心跳定时任务，服务实例非常多时，每一个客户端都需要定时发送心跳，每一个服务端都需要定时检测连接状态，这是一个非常适合使用时间轮的场景。如果对时间精准度要求非常高,最小堆是非常合适的方案.

参考:
https://www.cnkirito.moe/timer/
https://blog.csdn.net/anonymalias/article/details/52022787