时间轮定时器 Domi●Cat

定时器实现一般常见的有两种方式:

  • 时间轮(time_wheel)
  • 最小堆

就我自己的了解,使用时间轮的开源项目有:云风的skynet、陈硕的muduo;而经典的libevent库则使用的是最小堆。

分别解释下最小堆和时间轮的简单概念:

  • 最小堆:最小堆是一个经过排序的完全二叉树,除开根节点,其他任意节点的值都要小于它两个左右孩子的值。

另外关于二叉树的分类,我会另外单独写个笔记整理一下。

关于完全二叉树,一个n层的二叉树,除了第n-1层是满的(没有空位),第n层右边可以满可以不满,但是从左到右不能出现空位。可使用广度遍历来判断是否是完全二叉树。

  • 时间轮:可以直接拿我们生活中的手边做例子,手表一共有三个分级,时钟、分针和秒针,我们把秒针的一个刻度称为一个tick,秒针每走一圈,分针就移动一个刻度, 时间轮的原理就跟手表的模型是一样的。

时间轮算法

时间轮 (Timing-Wheel) 算法类似于一以恒定速度旋转的左轮手枪,枪的撞针则撞击枪膛,如果枪膛中有子弹,则会被击发。下面我将由简入深介绍基于时间轮实现的定时器。

时间轮算法的复杂程度跟你的分级层数有关,最简单的就是只有一轮,复杂一点的就是分层的时间轮,比如Hierarchy 时间轮(也就是linux系统下的时间轮实现方式)。

不分层的时间轮

不分层的时间轮是最简单,也是很容易理解的时间轮模型了:

假设有个N个槽(tick) 的轮子,随着时间推进,每走一个tick的时间,指针指向到槽也往前推进一格,直到一个轮所有的槽都执行完毕。

下图描述了一个不分层的时间时间轮模型:

简单时间轮

我们可以根据上面的模型,实现一个简单实用的时间轮定时器,一般的场景一层的时间轮已经够用了,比如游戏服务器,很少用到时间跨度非常大的定时器。 根据我自己的项目经验,目前我们的游戏服务器内部采用的就是简单的不分层时间轮,模型如下:

							|-- user_t[0]
			|-slot_t[0]	---	|-- ……
			|-slot_t[1]		|-- user_t[n]
tw.slots  = |-……
			|-……
			|-slot_t[6400-1]

tw.lslot  = 留一个槽,存放那些超时时间大于一轮的超时事件

上面模型中,slots表示时间轮的槽位,每个槽位里面可能有多个定时器任务,用一个链表来存放这些定时器任务。

该时间轮一共有6400个刻度,一个tick为10毫秒,那么每次走完一个转盘需要的时间等于 6400 * 10ms,即64s,差不多一分钟的时间走一轮。

用lua表述下这个模型,大概如下:

tick = 10 ms    -- tick
slotlen = 6000  -- 刻度数量

--下面用lua的table表示这个时间轮的数据结构:
time_wheel = {
	slots = {
		[1] = {timeobj1,timeobj2,…} -- 刻度1上的定时对象
		[2] = {timeobj1,timeobj2,…} -- 刻度2上的定时对象
	},
	lslot = {t1,t2,…}   -- 这里存放的是tick超过一圈的定时对象
	curTick = 0,        -- 当前走了多少个tick  
}

timeObj = {
	tick=10,        -- 表示这个定时对象需要10个tick,
	tickout = 1230, -- 表示超时的tick,即当定时器tick了1230次后,就触发超时事件
}

ps:

关于curTick,这里必须使用无符号,因为curTick是定时器每tick一次就会自增1,而无符号没有溢出的问题,这样可以满足定时器tick到无符号整数能容纳的最大数之后也能继续正确运行。 举个例子:如果我们有用无符号的32位int表示curTick,那么当curTick一直自增到 0xFFFFFFFF(4294967295),那么当下一次tick是,curTick又会复位到0,新的tick又会继续运行。

处理下一轮

当一个时间轮跑完一整轮后,要把超过一轮的定时器任务取出来重新分配格子。

例如:有一个循环为 5个 Tick 时间轮,当在tick为3的时候插入一个5tick后的定时器任务A,因为3+5=8tick已经超过时间轮的大小,所以,A必定在一轮循环完后,再取出来分配新的格子。 当tick=5时,一轮结束,然后取出任务A,此时分配的格子索引为:8%5=3

分层的时间轮

当我们在一些定时跨度比较大的场景时,上面的单层时间轮可能不再满足你的需求(当然是可以继续工作,但是有更好的办法)。 此时我们需要考虑分层,就好比现实生活中的手表,它分层了时、分、秒三个不同粒度的层级,这样可以节省内存空间。

这里分层的时间轮,并不是按照手表的粒度来分,而是用了另一种方式:

用一个32bit的无符号整型表示一个时间轮的范围,也就是说它能够支持2^32个tick(也就是0xFFFFFFFF),把它分层为5组,每组的粒度分别为:

256,64,64,64,64,也就是 256*64*64*64*64=2^32,时间轮就只需要 256+64*4=512个桶,比上面未分层的时间轮数组更小。

这是我自己用go实现的 time_wheel,比较简单,还有很多需要优化的细节,但是基础都实现了。

当然,上面的这种实现是比较简单的,但是对于游戏服务器来说,这个简单的时间轮已经够用了,如果说想实现更高端的,可以参考云风skynet里面的时间轮实现