游戏后台定时器系统设计与实现
尽管如今游戏类型多种多样，各种玩法层出不穷，各种平台不断延伸，从游戏后台程序的角度来看，还是可以发现很多相通的地方。从数学模型上讲，任何程序都是一个状态机，准确的说是一个图灵机，总是在一边读写纸带一边机械地改变自身状态。
驱动游戏Server这台“机器”不断运转的因素，主要有两个方面，一个是消息，一个是时间。消息主要体现于客户端侧的玩家操作，同时也有Server之间的交互，以及对进程的信号控制等。时间方面，一种是固定间隔或时间点上的特定逻辑触发，另一种则是由事件动态诱发的时延逻辑，如玩家进入某种状态，持续几秒后消失。
时间触发逻辑的常用解决方案是定时器，大家应该也比较熟悉，无论系统层还是应用层都有很多优秀的实现。虽然本质上定时器并不是唯一解决方案，但引入定时器概念，可以将时间控制的实现界面统一起来，同时相比传统的轮询Check方式，具有更加灵活简洁的使用方式。
本文将主要结合游戏中实际概念与需求，介绍下在以往项目中，定时器系统的设计和实践。
一．概念抽取
1.Tick，游戏逻辑帧
从游戏后台的真实需求来讲，定时事件的触发一般不需要过高时间精度，为了既能满足精度要求，又能清晰刻画游戏时间概念，这里抽取出了Tick的概念，亦可称为游戏逻辑帧。按以往的经验，通常将1秒划分为20个Tick，即每个Tick占时50毫秒。相较于真实时间，以Tick描述时间还有一个好处，就是具有连续性和单调性，无论是对于定时器系统自身的实现，还是应用层的某些特定需求场景，连续时间系统都是极其良好的特性。
2.Timer结点
Timer结点即是对定时器本身的属性描述，包括作用间隔，作用次数，触发时的行为，以及支撑该行为的相关数据。与常规定时器的定义并无大异。
值得一提的是本文定时器系统是支持使用共享内存的，Timer结点使用了定长数据结构，为了合理有效地对内存进行利用，实际应用中，Timer结点通常只存放相关标识和索引数据。如Player定时存盘Timer，其结点内实际上只存放了Timer类型和玩家ID，待存盘的数据始终是位于Player身上。这里也体现出时间触发本身才是定时器的核心作用，而不是维护各种事件的具体数据状态。
关于结点触发的执行行为，常见的设计是设置一个回调函数指针，这也是纯C中的常用方式。当使用C++进行实现时，也可以稍微优雅一点，利用多态的特性，将行为制定成一个virtual函数，不同类型的Timer结点实现各自的具体行为。如下：
然而考虑到Timer结点位于SHM，函数指针和虚函数可能都不是完美的方式，需要在基于SHM重启进程时进行重设。目前项目索性直接使用了根据Type显式强制转换，并没有使用虚函数。示意如下：
3.TimerID
如所有ID的含义一样，TimerID作为对一个Timer结点的唯一标识。设置Timer成功后会返回一个TimerID，通过TimerID可以执行结点的删除，变更等逻辑。
4.Timer属主
这里提出了属主这样一个概念。在实际应用中，我们提倡每一个定时器都有其属主，也即其归属对象。比如玩家相关的Timer其属主为Player对象，怪物相关Timer的属主为Monster对象。属主对象身上，存有其所有Timer结点的ID。当属主对象释放时，其负责释放所占的Timer资源，以防止Timer泄露。另一方面Timer触发时，如果找不到属主，也会主动释放自己。本质上属主并非每个Timer的必要属性，比如一些全局唯一Timer，但实际应用中我们提倡这样的使用方式，在获得到了Timer的动态特性同时，避免产生资源泄露问题。
二．数据结构设计
1.算法实现选型
关于Timer队列的实现，有很多非常优秀的经典设计，比如基于时间轮、多级时间轮、基于最小堆的经典算法，在Linux内核以及很多开源项目中都能找到具体实现，网上也有大量的文章介绍，这里就不再详细讨论其实现细节，只对相关异同做简单比较。
多级时间轮主要解决了间隔跨度较大的问题，比如既有间隔一天的Timer，也有间隔几毫秒的，使用多级可以更加合理的利用内存，触发检查上也可以获得更高的效率。最小堆算法的主要好处是可以O(1)时间获取到最近Timer的发生时刻，进而更加有效地避免触发检查空跑，甚至可以通过sleep真正空出CPU资源。当然最小堆插入和删除是O(LogN)的。
从游戏业务的实际需求出发，Timer常用于实现频繁发生和变化的一些短时状态，通常为几秒至几十分钟，以小时来记的就非常少见了。而且很多长时间的状态，都是使用一个截止时间戳进行表示，并非真的使用一个超长的Timer，这样多级时间轮的作用并不显著。
同时如前所述，设计上我们抽取了Tick概念，将每秒进行了适当分片，并非毫秒甚至微秒级的时间粒度，检查触发的空跑已经受到了有效控制，最小堆的作用也并不明显。
基于以上实际需求的考虑，我们选择了简单时间轮的算法作为实现，技能很好地满足游戏后台的实际需要，实现上也简单明了，易于理解和维护。
2.数据结构示意
图2.1定时器队列数据结构
Tick Bucket为时间槽数组，与Tick时间形成对应，每个Bucket实际为链表头结构，在该Tick发生的Timer被串接在该时间槽上。Tick Bucket的最大长度可按实际需求指定，在现有项目中，我们设定为144000个，即可以表示两个小时的持续时间。超过2个小时的Timer将会取模后对应到时间槽上，这也是“时间轮”中轮字的含义。
Curr Tick指向了当前Tick所对应的Bucket，随着真实时间的流逝，驱动该指针连续单向移动，这也保证了逻辑时间Tick的单调递增特性。在指向到每一个Bucket后，会对其挂接队列上的Timer以此遍历，执行事件触发逻辑。
Free List是空闲Timer结点的链表，将空闲结点串接在一起，以便可以O(1)复杂度新增Timer。Timer结点实际上是来自于一个连续的数组空间，最大结点个数可根据实际需要进行指定。
3.关键操作说明
a)新增Timer
从FreeList首端取出一个可用结点，设置结点相关属性，将该结点挂接到对应的时间槽上，构造TimerID返回。
b)删除Timer
根据TimerID索引到对应结点，核对结点状态，将该结点从Bucket链表中退出，串接在FreeList尾部，以供再次利用。
c)时间Check
程序主循环中调用Timer队列的Check函数，驱动时间流逝，根据真实时间设置当前Tick数值，Tick值发生变化时遍历对应时间槽上的所有Timer，完成事件触发逻辑。
4.TimerID设计
TimerID是Timer结点的唯一标识。从执行效率考虑，最好还具有快速索引的能力，以较低的时间复杂度实现结点的定位。同时也需要一些容错方面的考虑，比如一个Timer实际已经运行完毕，但其他对象仍持有该TimerID并错误地再次使用，此时应避免索引到错误结点。从唯一性，高效率，容错性触发，TimerID的构成设计如下：
8位Type表示了Timer结点的类型。
32位Index为结点在数组内的位置下标，可以直接定位到该结点。
24为SeqNo为结点序列号，每次结点重新分配时序号增加。
基于以上的ID形式，在唯一性、高效率、容错性上得到较好的实现。同时可以看出，新增、删除节点的时间复杂度均为O(1)。
至此一个定时器队列系统的数据结构及运转方式已经比较清楚了。
三．应用场景
1.固定间隔触发
固定间隔Timer可能是游戏中最常见的，比如Player每5分钟存盘一次，警戒中的怪物每秒搜索一次附近目标，伤害类Buff每两秒产生一次扣血，等等。
2.技能施放流程
在之前的端游项目，技能系统是灵活利用定时器的一个典型例子。比如玩家施放一个弹道类远程技能，流程如下：
开始施放–>吟唱3秒->发出火球->火球飞行5秒->命中目标->技能结束
后台的代码的执行逻辑大致是：开始技能施放，产生吟唱动作，设置3秒Timer并进入等待，Timer触发时产生火球起飞动作，设置5秒Timer并进入等待，Timer触发时通知命中动作，技能结束。
具体实现时技能控制本身是一个状态机，结合Timer的使用，可以灵活控制各个技能的施放流程。特别是不同技能的动作组合和状态持续时间各不相同，使用Timer来做时间上的动态控制，就显得比较清晰和灵活了。
3.策划脚本Timer
在之前的端游项目，曾经做过这样一个机制，可以由策划同事在任务或AI的脚本中，自由使用Timer。这样很多时间相关的完整逻辑都可以由策划独立实现了。比如某活动在特定地图内展开，分成多个阶段，不同阶段定时刷出不同怪物，最后阶段刷出Boss，Boss存活一段时间后会变身超级Boss，以及每过一段时间会召唤出辅助小怪，等等。只要建立起了灵活的脚本Timer机制，类似如上的各种复杂的活动流程，都可以由脚本很方便地实现了。
然而这里也存有一定的风险，策划同事本身的程序思路并非都很完备，而Timer作为一种动态资源，是存在滥用和泄露风险的。这里主要的解决办法还是基于属主的概念，对Timer进行合理的限定。如策划可使用的Timer是有限的，是有其归属对象的。如每个地图至多提供10个脚本Timer，每个怪物至多提供5个Timer，在地图或怪物对象被释放时，由程序回收其相关Timer资源。项目实际运行中，脚本Timer机制还是非常可靠和有效的。
四．总结
本文结合游戏后台的实际需求情景，比较完整地介绍了定时器系统的设计、实现及应用。希望能对从事游戏后台开发的同事提供一些帮助和借鉴，限于时间和作者水平，难免会有描述不准确和个人理解偏差的地方，也欢迎私下里多和本人交流讨论。
