CC BY 4.0 （除特别声明或转载文章外）
定时器实现一般常见的有两种方式：
- 时间轮（time_wheel）
- 最小堆
就我自己的了解，使用时间轮的开源项目有：云风的skynet、陈硕的muduo；而经典的libevent库则使用的是最小堆。
分别解释下最小堆和时间轮的简单概念：
- 最小堆：最小堆是一个经过排序的完全二叉树,除开根节点，其他任意节点的值都要小于它两个左右孩子的值。
另外关于二叉树的分类，我会另外单独写个笔记整理一下。
关于完全二叉树，一个n层的二叉树，除了第n-1层是满的（没有空位），第n层右边可以满可以不满，但是从左到右不能出现空位。可使用广度遍历来判断是否是完全二叉树。
- 时间轮：可以直接拿我们生活中的手边做例子，手表一共有三个分级，时钟、分针和秒针，我们把秒针的一个刻度称为一个tick，秒针每走一圈，分针就移动一个刻度， 时间轮的原理就跟手表的模型是一样的。
时间轮算法
时间轮 (Timing-Wheel) 算法类似于一以恒定速度旋转的左轮手枪，枪的撞针则撞击枪膛，如果枪膛中有子弹，则会被击发。下面我将由简入深介绍基于时间轮实现的定时器。
时间轮算法的复杂程度跟你的分级层数有关，最简单的就是只有一轮，复杂一点的就是分层的时间轮，比如Hierarchy 时间轮（也就是linux系统下的时间轮实现方式）。
不分层的时间轮
不分层的时间轮是最简单，也是很容易理解的时间轮模型了：
假设有个N个槽（tick) 的轮子，随着时间推进，每走一个tick的时间，指针指向到槽也往前推进一格，直到一个轮所有的槽都执行完毕。
下图描述了一个不分层的时间时间轮模型：
我们可以根据上面的模型，实现一个简单实用的时间轮定时器，一般的场景一层的时间轮已经够用了，比如游戏服务器，很少用到时间跨度非常大的定时器。 根据我自己的项目经验，目前我们的游戏服务器内部采用的就是简单的不分层时间轮，模型如下：
|-- user_t[0]
|-slot_t[0] --- |-- ……
|-slot_t[1] |-- user_t[n]
tw.slots = |-……
|-……
|-slot_t[6400-1]
tw.lslot = 留一个槽，存放那些超时时间大于一轮的超时事件
上面模型中，slots表示时间轮的槽位，每个槽位里面可能有多个定时器任务，用一个链表来存放这些定时器任务。
该时间轮一共有6400个刻度，一个tick为10毫秒，那么每次走完一个转盘需要的时间等于 6400 * 10ms,即64s，差不多一分钟的时间走一轮。
用lua表述下这个模型，大概如下：
tick = 10 ms -- tick
slotlen = 6000 -- 刻度数量
--下面用lua的table表示这个时间轮的数据结构：
time_wheel = {
slots = {
[1] = {timeobj1,timeobj2,…} -- 刻度1上的定时对象
[2] = {timeobj1,timeobj2,…} -- 刻度2上的定时对象
},
lslot = {t1,t2,…} -- 这里存放的是tick超过一圈的定时对象
curTick = 0, -- 当前走了多少个tick
}
timeObj = {
tick=10, -- 表示这个定时对象需要10个tick，
tickout = 1230, -- 表示超时的tick，即当定时器tick了1230次后，就触发超时事件
}
ps：
关于curTick,这里必须使用无符号，因为curTick是定时器每tick一次就会自增1，而无符号没有溢出的问题，这样可以满足定时器tick到无符号整数能容纳的最大数之后也能继续正确运行。 举个例子：如果我们有用无符号的32位int表示curTick，那么当curTick一直自增到 0xFFFFFFFF(4294967295)，那么当下一次tick是，curTick又会复位到0，新的tick又会继续运行。
处理下一轮
当一个时间轮跑完一整轮后，要把超过一轮的定时器任务取出来重新分配格子。
例如：有一个循环为 5个 Tick 时间轮，当在tick为3的时候插入一个5tick后的定时器任务A，因为3+5=8tick已经超过时间轮的大小，所以，A必定在一轮循环完后，再取出来分配新的格子。 当tick=5时，一轮结束，然后取出任务A，此时分配的格子索引为：8%5=3。
分层的时间轮
当我们在一些定时跨度比较大的场景时，上面的单层时间轮可能不再满足你的需求（当然是可以继续工作，但是有更好的办法）。 此时我们需要考虑分层，就好比现实生活中的手表，它分层了时、分、秒三个不同粒度的层级，这样可以节省内存空间。
这里分层的时间轮，并不是按照手表的粒度来分，而是用了另一种方式：
用一个32bit的无符号整型表示一个时间轮的范围，也就是说它能够支持2^32个tick（也就是0xFFFFFFFF），把它分层为5组，每组的粒度分别为：
256,64,64,64,64，也就是
256*64*64*64*64=2^32，时间轮就只需要256+64*4=512个桶，比上面未分层的时间轮数组更小。
这是我自己用go实现的 time_wheel，比较简单，还有很多需要优化的细节，但是基础都实现了。
当然，上面的这种实现是比较简单的，但是对于游戏服务器来说，这个简单的时间轮已经够用了，如果说想实现更高端的，可以参考云风skynet里面的时间轮实现。