定时器的实现原理

1.定时器的作用?

定时器的主要用途是执行定时任务。

定时任务在很多场景都需要用到，比如游戏的 Buff 实现，Redis 中的过期任务，Linux 中的定时任务，电商未支付订单的关闭等等。

2.数据结构要求

定时器需要支持如下几个操作：

• 创建定时器
• 添加定时任务
• 取消定时任务
• 执行到期任务（查找）

以下为常见实现定时器数据结构的时间复杂度：

• 有序链表：插入O(n)，删除 O(1)，过期 expire 执行 O(1)
• 最小堆：插入O(logn)，删除 O(logn)，过期 expire 执行 O(1)
• 红黑树：插入O(logn)，删除 O(logn)，过期 expire 执行 O(logn)
• 哈希表+链表（时间轮）：插入 O(1)，删除 O(1)，过期 expire 平均执行 O(1)（最坏为O(n)）

不同开源框架定时器实现方式不一，如 libuv 采用最小堆，nginx 采用红黑树，linux 内核和 skynet 采用时间轮算法等等。

3.时间轮

一个时间轮是一个环形结构，可以想象成时钟，分为很多格子，一个格子代表一段时间（越短 Timer 精度越高），并用一个 List 保存在该格子上到期要执行的所有任务。同时一个指针随着时间流逝一格一格移动，并执行对应 List 中所有到期的任务。任务通过取模决定应该放入哪个格子。

以上图为例，假设一个格子是1秒，则整个 wheel 能表示的时间段为 8s。

假如当前指针指向 0。

此时需要调度一个 3s 后执行的任务，显然应该加入到(0+3=3)的方格中，指针再走3次就可以执行了。

如果任务要在10s后执行，应该等指针走完一个 round 零 2 格再执行，因此应放入2并将 round 标记为 2 表示第二轮时执行。

4.分级时间轮

如果任务的时间跨度很大，数量也多，传统的时间轮会造成任务的 round 很大，单个格子的任务 List 很长，并会维持很长一段时间。

这时可将 Wheel 按时间粒度分级：

这种方式的优点在于能够保证任务链表的长度一直在比较短的状态，但缺点是需要更多的空间。

5.业界实现方案

业界对于定时器/延迟队列的工程实践，则通常使用以下几种方案。

• 基于 Redis ZSet 实现。
• 采用某些自带延迟选项的队列实现，如 RabbitMQ、Beanstalkd、腾讯 TDMQ 等。
• 基于 Timing-Wheel 时间轮算法实现。

参考文献

如何快速实现一个定时器？- InfoQ