起因
最近新项目在进行底层代码的重构和优化（代码源自老项目D1），分配给我的任务是对原来的玩家定时器进行优化。
原方案分析
轮询的方式：
- 一个每隔1000毫秒触发一次的定时器负责触发playerManager对象上的tick(),当playerManager的tick()方法被调用时，遍历所有玩家并调用玩家的tick()方法；
- 每个玩家对象身上都有一个tick()方法，每1000毫秒执行一次tick()方法——遍历玩家的功能系统，执行功能系统的tick()方法；
- 功能系统tick()进行计算和判断。
大致流程如下图所示：
按上述的方式，意味着每隔1000毫秒，就需要遍历所有玩家并调用其tick()方法；注意，一个玩家可能拥有多个功能系统，每个功能系统都可能拥有自己的tick()方法。其次很多功能系统的tick()会进行大量计算才能判断是否满足下一步逻辑执行的条件;如果用轮询的方式性能消耗是比较大的(因为绝大多数计算可能都是无效的)。
新方案探索
考虑将轮询检测改进为到点触发：到达指定时间点后才执行玩家的定时任务，这样可以减少大量不必要的计算和判断。
目前定时器实现的主要方式参考(定性分析):
| 实现方式 | get时间复杂度 | add时间复杂度 | delete时间复杂度 | 空间复杂度 | 使用例子 |
|---|---|---|---|---|---|
| 链表 | O(1) | O(1) | O(n) | O(n) | 比较低效,暂未发现有项目使用 |
| 最小堆 | O(log n) | O(log n) | O(log n) | O(n) | Java的ScheduledThreadPoolExecutor(使用DelayedQueue) |
| 时间轮 | O(1) | O(1) | O(1) | O(n) | netty等 |
| 多层级时间轮 | O(1) | O(1) | O(1) | O(n) | Linux内核，Kafka等 |
注意表格中的时间复杂度都是理论上的表述:
-
链表实现:最容易想到的质朴方法,但是效率不高;
-
最小堆:可以保证add和delete都在对数时间复杂度内;
如果用多线程操作堆:改变堆结构时需要对整个堆加锁;如果堆里的task元素太多,需要考虑加锁带来的性能消耗(Java的ScheduledThreadPoolExecutor就是对整个堆加锁);
-
时间轮:本质上是hash表的变种–>环状的哈希表,采用链接法解决hash冲突.使用时间轮可以保证add和delete操作的事件复杂度都在O(1)内完成.
-
多层级时间轮(自定义时间轮轮盘的单位时长):比如YearTimeWheel、MonthTimeWheel、DayTimeWheel、HourTimeWheel、MinuteTimeWhel等；当Task数量较多时,减少每层时间轮的Task数量，减少hash冲突,并且比较符合现实中的定时器需求(可以想想时钟和手表的指针)。
当然，不论采用何种方法实现定时器，定时器都只负责触发Task。Task的业务逻辑应当由相应业务线程去处理。
备注
1.因为保密的原因，上文中涉及的项目均为代号；
2.上文说的Task指定时任务。