MMO中的时间轮概念

时间轮这个东西，这个东西并不是为MMO所设计的。它的由来也就是为了优化传统的定时器效率低下的问题。
在开发高性能服务器中，定时器总是不可或缺的
传统的定时器实现思想。 分两种
1.最LOW的一种， 只有一个定时器。 需要遍历所有的定时任务。时间复杂度O(n).
2.比较科学的一种，使用一个最小堆的数据结构（优先队列），来构建整个定时任务的结构。开启一个定时任务复杂度为O(logn);

时间轮先上个图：

时间轮算法可以通过上图来描述。假设时间轮大小为 8，1s 转一格，每格指向一个链表，保存着待执行的任务。
假设，当前位于 2，现在要添加一个 3s 后指向的任务，则 2+3=5，在第 5 格的链表中添加一个节点指向任务即可，标识 round=0。
假设，当前位于 2，现在要添加一个 10s 后指向的任务，则（2+10）% 8 = 4，则在第 4 格添加一个节点指向任务，并标识 round=1，则当时间轮第二次经过第 4 格时，即会执行任务。
时间轮只会执行 round=0 的任务，并会把该格子上的其他任务的 round 减 1。
时间轮可以做新加入一个定时任务，删除一个定时任务，执行一个到期任务复杂度都为O(1).

时间轮有分为两种， 一种为简单时间轮， 一种为分极时间轮。
简单时间轮， 就是上面所述的那种。
分级时间轮： 类似于水表，当小轮子里的指针转动满一圈后，上一级轮子的指针进一格。 采用五个轮子每个轮子为一个简单时间轮，大小分别为 2^8， 2^6， 2^6， 2^6， 2^{6，所需空间：2}8 + 2^6 + 2^6 + 2^6 + 2^6 = 512， 可表示的范围为 0 – 2^8 * 2^6 * 2^6* 2^6* 2^6 = 2^32。
上图：分级时间轮

分层时间轮是这样一种思想：
针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。
针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。
第一点很好理解，第二点有必要举个例子来说明，比如我有三个任务：
任务一每周二上午九点。
任务二每周四上午九点。
任务三每个月12号上午九点。
三个任务涉及到四个时间单位：小时、天、星期、月份。
拿任务三来说，任务三得到执行的前提是，时间刻度先得来到12号这一天，然后才需要关注其更细一级的时间单位：上午9点。
基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。
月轮的时间刻度是天。
周轮的时间刻度是天。
天轮的时间刻度是小时。
初始添加任务时，任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。
三个时间轮以各自的时间刻度不停流转。
当周轮移动到刻度2(星期二)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
同理，当月轮移动到刻度12(12号)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
这样就可以做到既不浪费空间，有不浪费时间。

至于采用round型（简单时间轮）的时间轮还是采用分层时间轮，看实际需要吧，时间复杂度和实现复杂度的取舍

几种常用定时器算法时间复杂度对比：

END