基于侵入式链表的时间轮定时器实现

游戏服务器一般都会需要这样一种功能 – 在某个确定的时间点干某件特定的事情,例如:某个排行需要在每月第一天进行结算,某个比赛需要在下周六中午12:00准时通知服务器所有玩家比赛开始……当然,这种功能不局限于游戏服务器,其他类型服务器或多或少也有包含。我们称之这个功能为定时器功能或者定时器组件

这里实现了一种用C++模板机制实现的秒级(比较容易改写成毫秒级)定时器,核心算法使用的是时间轮(Timing-Wheel),辅助数据结构使用的是侵入式链表(Intrusive-List)。首先简单介绍一些基本概念。

代码戳这里

侵入式链表(Intrusive-List)

最典型的Intrusive-List例子应该就是linux内核中使用的链表了,它的优点是用户知道自己在表中的位置,删除比较方便,且用户自己管理数据块,这个数据块可以被多个链表同时共享(注意这是一个很重要的特性,相比非侵入式链表节约了不少空间),这种数据结构在redisnginx代码中广泛使用。

相对应的,非侵入式链表(Non-intrusive-list)的例子就是std::list了,被使用在各大软件与应用中,易用,稳定,用户群里大基本任何关于它的问题都可以google到,当然这里说的Non-intrusive-list不单单只是指std::list,只是std::list占去了Non-intrusive-list至少90%的“市场份额”。

一些比较好的关于链表资料:

针对星际争霸1实现的链表,作者参与过暴雪半数以上知名游戏开发
http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists

IBM工程师写关于linux内核链表分析
https://www.ibm.com/developerworks/cn/linux/kernel/l-chain/

时间轮(Timing-Wheel)

对于Timing-Wheel的基本理解就像老式钟表,一个圆盘,上面很多刻度,外加刻度针。每次Tick,轮盘转动(根据物理相对运动,也可以理解成刻度针摆动),这时指针指向新的刻度标签,这个刻度标签上有任何过期定时器那么则进行处理,定期进行下一次Tick,处理下一个刻度标签上的事件……

本文的实现

游戏服务器一般来说不需要很精确的计时(端游上需要毫秒级,一些技能的吟唱是需要毫秒级支持的),特别手游服务器一般精确到秒级即可,所以对于Timing-Wheel的N取值为60即可(1分钟60秒,每秒对应一个轮)。我们采用每个轮子上挂接顺序链表的方式进行定时器存储,这样的话在轮询时只用判断表头是否过期即可。

timewheel

对于插入行为,我们根据定时器过期时间(expireTm)对N值进行求余hash,从而找到对应的轮,将其插入顺序链表。

timewheel1

对于轮的转动,原则上以秒为单位进行指针移动。

问题与解决

问题1:若定时器过期处理函数(func)耗时过长,导致精度下降,如何处理?

建议是在func中不要放过重的逻辑,如果无法避免重逻辑,可以使用线程解决。但是使用线程会使开发同步性的成本就会增加,也会增加维护的复杂度,所以这是一个取舍过程,本文中的实现无法完全避免这个问题。

问题2:一个过期处理函数(func)耗时几秒,已经导致了精确严重下降,如何处理?

本文实现一个简单的追赶机制,我们在处理定时器过期线程(滴答线程)将每次滴答(Tick)时间默认设置为200ms,并且记录当前的时间指针位置(secStep),当发生了一个很耗时的func,我们会发现当前时间(curTm)大于secStep,那么我将secStep++,直到curTm==secStep我们就不做任何移动当前secStep的操作,让其自动随时间移动,这样在1秒的时间内可以大约追赶4秒误差。

问题3:定时器是否线程安全?

是,粗暴的使用线程锁。

问题4:定时器内存管理是怎么样的?

内存会对定时器事件(timerEvent),进行new/delete(可以优化为高效的内存池模式),无需用户进行额外的内存操作。

代码戳这里


转载文章请注明出处:漫漫路 - lanindex.com

Leave a Comment

Your email address will not be published.

鄂公网安备42018502003990号