定时器的实现原理
文章目录
- 1.定时器的作用?
- 2.数据结构要求
- 3.时间轮
- 4.分级时间轮
- 5.业界实现方案
- 参考文献
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
总结
