文章目录

• 定时任务的处理方式
• 实现方案
• • 1）红黑树
  • 2）最小堆
  • 3）时间轮
  • 方案选择
• 时间轮的实现
• • 单层级时间轮
  • 多层级时间轮
  • • Skynet的时间轮
• 五层级时间轮实现代码

定时任务的处理方式

服务端的驱动逻辑主要涉及两类事件的处理：网络I/O事件和定时事件，不同的框架采用不同的方式来整合这两种事件的处理流程：

• 在同一个线程中先处理I/O事件，再处理定时事件，如nginx、redis。利用 epoll_wait 监测I/O的同时依靠 timeout 参数来实现所谓定时，缺点是I/O的处理导致延时比较严重。
• 网络事件和I/O事件在不同线程中处理，如skynet。由单独的线程更新检测定时器，并把定时事件发送到消息队列中。

实现方案

首先需要为定时器选择合适的数据结构，其应该满足两点基本要求：

• 节点元素有序（越近要触发的任务越靠前）
• 可快速查找到key最小的节点

比较合适的数据结构包括红黑树、最小堆以及时间轮。

1）红黑树

增删改的时间复杂度都为O(logn)，获取最小节点的复杂度也为O(h)，h是树的高度。
Nginx的定时器就是采用红黑树实现，并且通过信号打断epoll_wait的方式来解决定时误差大的问题。

2）最小堆

增、删和改的时间复杂度为O(logn)；获取最小节点的复杂度为O(1)。因为堆不是完全有序的，所以效率相对于红黑树还是会高一点的，复杂度也比较稳定。
libevent 的定时器便是采用最小堆来实现。

3）时间轮

时间轮实质上采用循环数组实现，描述了钟表的运行方式，在某个时间节点执行注册到该节点下的任务。因此增删改的时间复杂度都为O(1)，获取最小节点的复杂度也为O(1)。
skynet、kafka等采用时间轮来实现定时器。

方案选择

红黑树和最小堆更适合用于单线程环境，而时间轮则适合于多线程环境，主要是关系到锁的粒度，因为时间轮操作的时间复杂度是O(1)，而红黑树和最小堆操作的时间复杂度较高，较大的锁粒度影响多线程的运行效率。但时间轮缺点是占用更多的内存，实质是以空间换时间。

时间轮的实现

单层级时间轮

单层级时间轮类似于Hashtable，使用数组存储数据，每个数组的元素便是一个时间点下需要执行的任务，指示时间的指针在数组上循环移动，数组索引的跨度代表的就是时间间隔。如当前时间点位于下标1，每个索引间隔（精度）为1s，则添加一个5s后执行的任务时，该任务将被挂到下标为1+5=6的元素下面，当时间指针走到下标6时，将执行将元素中的所有任务。

不难理解，当我们添加一个任务时，其所在数组下标的计算方式为：++tick % N，N是数组的长度。

显然多个任务会在某个时间点同时执行，因此参考Hash冲突的解决方式，使用链表将任务链接起来。

设计单层级时间轮时需要考虑这两个参数：

• 数组长度的设置：如果数组长度设置得太小，则类似于Hashtable一样很容易出现冲突，总是会检测到还没有超时的任务，因此数组大小N至少应该是可能会用到的最大时间间隔，比如最大可设置时间间隔是10s，则应设置数组长度N≥11。
  出于优化的目的，我们设置N总是为2ⁿ，这样一来我们可以将tick % N优化为tick & (2^n - 1)。比如上面的例子我们应设置N=16。

• 时间精度的确定：根据需求来确定，如10s发一次心跳检测，那么时间精度就可以用秒。

单层级时间轮的踏空问题（空推进）：如果我们需要设置很大的时间间隔，且时间精度又比较高（如10ms），则单层级时间轮的数组会很大，那么很可能就会出现大量的空格，大量的时间被浪费在空格的检测上，空间利用率也非常低，这就是空推进问题。Kafka等组件都使用了单层级时间轮+最小堆的方案来解决空推进问题，减少踏空。

多层级时间轮

多层级时间轮在一定程度上模拟了钟表的运作方式，非常适用于时间跨度很大而时间精度又要求比较高的应用中作为定时器。其基本思路是构建多个时间轮数组，第一层的时间精度最高，越往后的层级时间精度越低，把最近要触发的任务放在第一层，时间跨度较大的任务放到之后的几层，当第一层的时间都走完之后，再把下一层的一个时间点下的所有任务都分配到第一层，然后时间点继续在第一层移动。举个栗子更好理解：

假设我们设计一个3层级时间轮，时间精度分别秒、分、时，时间指针分别为tick_s、tick_m、tick_h。当tick_s在第1层走到tick_s=1时，需要添加一个1s后执行的任务A和一个60秒后执行的任务C，则这两个任务将分别被添加到图中所示的两个位置。

显然任务A在tick_s走到2时就会被执行。当tick_s走到60并取余而变回0时，会将第2层中tick_m前进一格，并使tick_m下的所有任务重新映射到第1层，然后第1层继续执行；以此类推，当tick_m走到60并取余而变回0时，会将第3层中tick_h前进一格，并使tick_h下的所有任务重新映射到第1层。

添加任务时下标的计算方法为：

1. expire = timeout + current，timeout, current∈[0, 43199]。（其中43200=60×60×12）
2. 如果timeout∈[0, 59]，则该任务直接插入到第1级中相应的位置；如果timeout∈[60, 3599]，则该任务插入到第2级下标为expire / 60的位置；如果timeout∈[3600, 43199]，则该任务插入到第3级下标为((expire % 43200) / 3600) % 12的位置。因此能够设置的最大超时时间 timeout 其实就是12个小时，超出这个范围时间轮就可能出错。同时，当expire超出43200时，第3级之后没有下一级了，所以作(expire % 43200)以使第3级的指针tick_h回到起点重新开始。

每次更新current后，重新映射到高层级任务到第1层的计算方法为：idx = (expire - current) % 60。

不难发现，按照上面的公式计算，tick_m=0的位置是永远不会有数据的，而tick_h=0的位置在expire ≥ 43200时，计算得到第3级下标为0，因此是可能会有数据的。

Skynet的时间轮

Skynet中用5层级时间轮设计了一个32位的定时器，时间精度10ms，时间轮数组如下所示：

第1级时间轮数组长度为2⁸，之后四级数组长度均为2⁶，因此可设置的超时时间长达 2⁸×2⁶×2⁶×2⁶×2⁶=2³²。可以想象，如果用单层级时间轮来设计这个定时器，为了避免检测到还没有超时的任务，那么数组长度就是2³²，显然不现实。

这个五层级时间轮的计算方式就与前面举的12小时的例子是一脉相承了。由于这里面的时间参数都是无符号整型，因此不需要人为地对expire, timeout, now等参数作范围判断或范围限定，每个层级的数组长度都是2ⁿ，取余时也可以做优化了。

五层级时间轮实现代码

之后上传到github。