游戏服务端定时器的实现

最近在看过一些定时器相关的资料，也读了一些代码，比如云风的skynet的定时器实现，小有启发，因此将所得整理记录下来。　　

通常，一个定时器模块会提供以下三个接口：

reg_tick(timeout, callback);
unreg_tick(tick_id);
update_timer();

reg_tick注册一个tick，unreg_tick取消一个tick，update_timer更新计时器的时间，触发其中过期的tick。前两个接口好理解，问题是第三个接口update_timer，到底什么时候调用这个呢？看下面的说明。

一个游戏服务端需要处理客户端的请求，也要处理定时的任务，其主循环或许如下：

1 while 1:
2     #处理网络IO任务
3     result = select(10)
4     for fd, event in result:
5         handle(fd, event)
6     #处理定时任务
7     update_timer()

update_time这个函数的工作就是找出服务器所有过期的定时任务，并执行其对应的回调函数。最简单的实现是，假设服务器有一个集合保存着所有注册了的tick（一个tick就是一个定时任务，下文将不再解释），每次更新计时器的时候，遍历集合中的所有tick，挨个去判断这个tick是否过期，如果是则执行其callback，可能的话还要删掉这个已经触发了的tick。

1 def update_timer():
2     current = get_cur_time()
3     for timer in reg_timer_list:
4         if timer.expeires > current:
5             timer.callback()

接下来分析这个实现的时间复杂度。如果使用vector来存储tick的话，reg_tick的时间是O(1)，unreg_tick的时间是O(n)，update_timer的时间也是O(n)。

当然有几种简单的改进方法，比如改为用hash_map来存储tick，可以将插入和删除的时间降到O(1)，但需要注意的是对于一般的hash_map如果没有记录前一个和后一个元素的位置，遍历起来是会相对耗时的。因此update_timer的时间可能会需要更多，具体依赖hash_map的实现。当然也可以使用红黑树来存储tick。

另一种改进方法是，依然使用占内存相对较小的vector存储tick，不过需要维持这个vector，使其中所有tick都是按触发时间从早到晚的依次排序。这样一来插入和删除的时间变为O(n)，但是相对的，update_timer却变快了，因为可以把要触发的tick都集中到一起，摊还下来从而每一个tick的触发时间变少了。这样做通常是有好处的，如上文所述，相对于reg_tick和unreg_tick服务器一般会较为频繁的调用update_timer这个函数。

其实基于维持一个有序数组的思想还可以进一步的优化，比如用触发时间为key使用最小堆来存储tick。这种情况插入删除和有序数组时间复杂度一致，但是update_timer一般来说效率更高。

其实还可以进一步再优化，这次依然选择hash_map作为存储tick的数据结构，只不过存储在hash_map中的key是一个时间戳，value是这个时间戳对应的所有tick列表。这样一来每次调用update_timer这个函数不再需要遍历整个hash_map，而是根据时间戳索引到对应的tick列表，因此update_timer的时间复杂度降至O(1)。由此而来，reg_timer、unreg_timer、update_timer三个接口的时间复杂度都降至O(1)。

1 def update_timer():
2     last = get_last_update()
3     current = get_cur_time()
4     while last <= current:
5         for timer in reg_timer_dict[last]:
6             timer.callback()
7             last += 1

到这为止了吗？

通用性的解决方案是为了满足大多数的情况而被使用的，在特定问题下，如果我们根据问题的独特性进行相应的优化，通常能做的更好，这也是造轮子的意义所在。回到计时器这个问题，我们是否能优化一下hash_map空间复杂度呢？

接下来要引入的就是特定情况下的解决方案。我们可以基于一个假设进行优化，假设我们不需要注册一个很久以后的tick。由此而引出的是分层时间轮计时器，这个也是Linux内核使用的定时器算法（skynet的定时器也是，可以读一下skynet的代码，只有两百多行）。

一般使用的都是分层时间轮，朴素时间轮算法就不作说明了。之前在看资料的时候，找到了一篇文章对分层时间轮描述的很详细，地址是见文章结尾的参考资料。

我在这里就简单说明一下。假设这个有三个时钟，分别是时分秒。以秒级时钟说明，这个时钟有60个槽，代表了一分钟的60秒，每一个槽对应存放的是tick列表。我们有一个变量记录下当前的秒针的位置，每当秒针走一步，则触发对应槽的tick列表中的所有tick。假设我要注册一个10秒钟之后触发的tick，则把这个tick插入到（当前秒针+10）mod 60的位置上即可。这样60秒内的tick没什么问题，但是大于60秒则如何处理？这时就要使用到分钟级的时钟了。比如说我需要注册一个70秒后触发的tick，通过计算可以发现这个tick是下一分钟触发的，因此把这个tick存放在（当前分针+1）mod 60的位置上。当秒针转完一轮后，分针需要走一步，这个时候就把当前分针所指向的槽的所有tick都插入到秒级时钟去。比如说刚刚的70秒后的tick，因为秒针走了一轮，这时候触发时间变成10秒之后，因此把它插入到（当前秒针+10）mod 60的位置。时针的处理与这个类似。通过这种方法，表示一天需要的空间复杂度是60+60+24=144个槽。

Linux内核和Skynet的定时器都是使用这个方法，但是它们不是按时分秒这样分层，而是将32bit按8/6/6/6/6/分成5个部分，也就是有5个时钟（这里每一个时钟被称为Time Vector简称TV），原来的秒级时钟变为2^8=256个槽。这种分层方法的空间复杂度变为256+64+64+64+64=512个槽，支持注册最长时间的tick是256*64*64*64*64=2^32秒。

参考资料：

浅析 Linux 中的时间编程和实现原理，第 3 部分: Linux 内核的工作。地址：http://www.ibm.com/developerworks/cn/linux/1308_liuming_linuxtime3/
游戏服务器定时任务大家是通过什么方式实现的韦易笑的回答。地址：https://www.zhihu.com/question/32251997