定时器详解
引出
定时器是一个比较常见的数据结构，或者说框架，以一个最简单的例子引出，在游戏中，冷却时间使用的就是定时器；
所以说定时器是等待时间过期执行对应时间事件处理( 回调函数 )的一个框架；
补充：下文中可能会出现定时任务，它和时间事件基本上是一个东西
那么现在有一个就有一个问题，该如何实现定时器这一功能？
- 首先进行两种分类：随着网络事件处理定时事件；不随着网络事件处理时间事件；
定时器概述
对于一个服务器来说，需要许多客户端进行通信，必然会有网络IO相关的事件( 网络IO事件 )；
除此之外，服务器内部对于一个或N个客户端传输过来的数据进行延时相关的处理，针对不同送达时间，必然会有排序和时间事件；
对于不同的框架，针对网络事件和时间会有不同的实现：
- 第一种，网络事件和定时事件在同一个线程中使用；
- 第二种：网络事件和定时事件在不同的线程中使用；
第一种形式-网络事件和定时事件在同一个线程中使用
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
struct timeva l *timeout);
timeout > 0：表示等待指定的时间，单位为毫秒;
timeout == 0：表示立即返回，不管是否有事件发生;
timeout == -1：表示一直等待，直到有事件发生。
- 这一模式中，利用的是IO多路复用中的timeout参数；使用其大于0与等于0的情况，以一下代码举例。
// ... 其他代码
while(!quit){
int timeout=get_nearest_timer()-now_time();// get_nearest_timer为得到最近的时间事件
if(timeout<0)
timeout=-1;
int event_count=epoll_wait(epfd,ev,ev_num,timeout);
for(int i=0;i<event_count;i++){
// ... 处理网络事件
}
update_timer();// 处理时间事件
// ... 其他代码
}
// ... 其他代码
说明：get_nearest_timer()、update_timer()，为定时器提供
- 从上述中可知其流程：
- 最近定时任务需要的时间->epoll_wait阻塞一会儿->处理网络事件->处理时间事件;
- update_timer()函数可以只是用作确定时间事件的回调函数，可以把事件处理抛给线程池，而update_timer()会直接进行返回，不会阻塞主流程，这是一种事件的异步形式。
总结
针对于上述流程，最关键的一步就是使用epoll_wait进行阻塞，使得可以同步地进行网络IO处理和定时任务处理，让其处于一个流程中
当然这种必然也是有缺点的，比如定时任务或者网络IO数量太多，导致处理时间太长，不过这可以使用 reactor模型( 或者使用协程)+时间事件异步处理 的形式解决。多数情况下还是针对少量定时任务使用第一种。
再有就是多线程环境下，如果网络IO的事件处理和时间任务处理需要有一种同步的关系，大概还得进行加锁的复杂处理
扩展
- 其实reactor模型也是异步事件处理，从而让IO处理时同步的
第二种：网络事件和定时事件在不同的线程中使用
概况：时间事件使用一个单独的线程进行检测，一旦检测到进行回调、或者再抛给任务队列，由线程池进行处理；
void* thread_timer(void * thread_param) {
init_timer();// 初始化定时器
while (!quit) {
update_timer(); // 检测定时器中的定时任务
sleep(t); // 这?的 t 要?于 时间精度
}
clear_timer();
return NULL;
}
pthread_create(&pid, NULL, thread_timer, &thread_param);
说明：
定时器内部会维护大量的定时任务，update_timer()是用于检测定时器中所有需要被处理的定时任务，检测到后进行处理并删除该定时任务，处理时可以直接调用回调，也可以做成异步的事件处理。
使用sleep()/usleep()函数，减少进入update_timer()函数的次数，不过一定要让t小于时间精度（最小运行单元），否则t大于时间精度会让定时器不会及时的被检测到，会出现延时的状况。
总结
在不同线程处理网络事件和时间事件时，可以进行大量的定时任务的维护和处理，让网络IO处理和定时任务解耦。
定时器设计
既然要使用定时器，必然离不开定时器的设计，那么如何设计定时器，成为接下来需要解决的问题。
接口设计
首先是接口的设计
基本接口：
- 初始化定时器：
void init_timer();- 添加定时任务：
Node *add_timer(int expire,callback cb);- 删除定时任务：
bool delete_timer(Node* node);一般在检测定时器的时候使用，可以不对外提供该接口；- 找到最近的需要被触发的定时任务：
Node* find_nearest_timer();这种接口一般应用于网络事件和定时事件在一个线程中处理的触发方式。- 检测更新所有定时任务：
void update_timer();- 清除所有定时任务 :
void clear_timer();
内部数据结构选择
对外提供的接口解决了，那么接下来该思考定时器内部该用什么样的数据结构维护定时任务会让效率达到最佳；
该数据结构需要满足一些条件，比如查询最小节点的时间复杂度比如得小，比如增加删除节点不会影响原有的数据结构。
因此选择出来了，红黑树、最小堆都是最佳的选择。
红黑树
红黑树的中序遍历，让数据可以有序排序，而且是绝对排序（从小到大排序）。具体数据结构，可以去查找网上其他资料。
- 增删查的时间复杂度均为O(logN);
- 最小的节点为红黑树最左侧的节点，时间复杂度O(logN);
- 如果几乎同时来个两个时间相等的任务，但是key值比较时会出现相等的情况，你可以把后来的任务放到其右节点位置。
最小堆
最小堆是一个完全二叉树，且父节点一定比子节点小，这样得到的结果就是根节点一定是这棵树的最小值；具体数据结构，可以去查找网上其他资料。
增查的时间复杂度O(logN);
删除操作需要查找是否包含这个节点，删除的时间复杂度O(n);
最小节点的时间复杂度为O(1);
时间轮
以上两种实现方法需要时时刻刻都要进行检测，对于定时任务密集类型的自然可以，如果是定时任务之间的间隔时间过长怎么办？时时刻刻检测会增加很多无效检测，降低cpu的使用效率。
使用时间轮是一种解决上述问题的方法；
时间轮需要保证自己的时间精度足够小，否则会出现不能插入定时任务的情况
单层级时间轮
首先先谈一谈单层级时间轮，单层级时间轮就是使用数组模拟一个环形队列，数组