Timer 定时器技术分享

Timer 定时器技术分享

说点废话

不管是客户端Client还是服务器Server,不论你是从事游戏行业还是互联网行业,在技术上总会涉及到定时器。虽然有的框架系统已经帮你实现,并且提供完美API供你使用,但你真的了解定时器吗?我们不仅要知道如何使用正确的Timer,还得明白定时器的实现原理,要知其所以然。

理解定时器

使用者角度分类:

  1. 周期性定时器

    1. 使用 TCP 长连接时,客户端需要定时向服务端发送心跳请求
    2. 游戏内系统每日重置功能
    3. 体力回复
  2. 非周期性定时器

    1. 玩法活动定时开启、关闭

当然,大部分非周期性定时器都可以使用周期性定时器实现,即执行一次后立即调用Remove接口即可

定时器像水和空气一般,普遍存在于各个场景中,一般定时任务的形式表现为:经过固定时间后触发、按照固定频率周期性触发、在某个时刻触发。定时器是什么?可以理解为这样一个数据结构:存储一系列的任务集合,并且 Deadline 越接近的任务,拥有越高的执行优先级

支持以下几种操作:

  1. Add New TimerTask 添加新的定时器
  2. Kill Or Remove TimerTask 取消或者移除既有定时器任务
  3. Run 执行

判断一个TimerTask是否到期,基本会采用轮询的方式,每隔一个时间片tickDuration去检查最近的任务是否到期。

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

现在知道Timer是靠轮询来实现的,那么中间应该采用那种数据结构呢?采用不同的数据结构实现,其性能也大不一样!
现在主要有如下几种:List链表、Heap最小堆、时间轮、分级时间轮,其中时间轮的实质为Hash表。

数据结构

双向有序链表

AddTimer O(N)很容易理解,按照 expireTime 查找合适的位置即可;KillTimer O(1) ,任务在 Kill 时,会持有自己节点的引用,所以不需要查找其在链表中所在的位置,即可实现当前节点的删除;RunTimer O(1),由于整个双向链表是基于 expireTime 有序的,所以调度器只需要轮询第一个任务即可。

最小堆

最小堆指的是满足除了根节点以外的每个节点都不小于其父节点的堆。这样,堆中的最小值就存放在根节点中,并且在以某个结点为根的子树中,各节点的值都不小于该子树根节点的值。一个最小堆的例子如下图:
最小堆

明显的,最小堆添加新元素或者删除节点效率为O(lgn), root节点expireTime最小,执行优先级最高,因此复杂度为O(1)

如果程序中的定时器数量比较少,基于最小堆的定时器一般可以满足需求,且实现简单。

时间轮

时间轮的实质为哈希环HashTable,每个定时器任务根据对其expireTime哈希,得到对应的位置index,复杂度为O(1)
时间轮

性能比较:

实现方式AddTimerKillTimerRunTimer
基于链表O(1)O(n)O(n)
基于排序链表O(n)O(1)O(1)
基于最小堆O(lgn)O(lgn)O(1)
基于时间轮O(1)O(1)O(1)

现在看起来我们选择时间轮来实现就行了,是否这样就完事了?

着重分析时间轮

如果需要支持的定时器范围非常的大,上面的实现方式则不能满足这样的需求。因为这样将消耗非常可观的内存,假设需要表示的定时器范围为:0 – 2^3-1ticks,则简单时间轮需要 2^32 个元素空间,这对于内存空间的使用将非常的庞大。也许可以降低定时器的精度,使得每个 Tick 表示的时间更长一些,但这样的代价是定时器的精度将大打折扣。

现在的问题是,度量定时器的粒度,只能使用唯一粒度吗?想想日常生活中常遇到的水表,如下图:
水表

钟表:
水表

分级时间轮同样如此,每级时间轮所代表的粒度精度都不一样,这样结合起来,既能够保证定时器的精度,也能以较小内存代价表示范围更大更多的定时器。

简单时间轮: 一个齿轮,每个齿轮保存一个超时的node链表。一个齿轮表示一个时间刻度,比如钟表里面一小格代表一秒,钟表的秒针每次跳一格。假设一个刻度代表10ms,则2^32 个格子可表示1.36年,2^16个格子可表示10.9分钟。当要表示的时间范围较大时,空间复杂度会大幅增加。

分级时间轮: 类似于水表,当小轮子里的指针转动满一圈后,上一级轮子的指针进一格。 采用五个轮子每个轮子为一个简单时间轮,大小分别为 2^8, 2^6, 2^6, 2^6, 26,所需空间:28 + 2^6 + 2^6 + 2^6 + 2^6 = 512, 可表示的范围为 0 – 2^8 * 2^6 * 2^6* 2^6* 2^6 = 2^32 。

分级时间轮简洁图
分级时间轮

熟知的Linux系统内核,定时器实现方式就是分级时间轮
Linux内核

具体实现

wheel_timer_mgr.h

wheel_timer_mgr.cpp

发表评论

电子邮件地址不会被公开。 必填项已用*标注

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax