定时器详解

引出

定时器是一个比较常见的数据结构，或者说框架，以一个最简单的例子引出，在游戏中，冷却时间使用的就是定时器；

所以说定时器是等待时间过期执行对应时间事件处理( 回调函数 )的一个框架；

补充：下文中可能会出现定时任务，它和时间事件基本上是一个东西

那么现在有一个就有一个问题，该如何实现定时器这一功能？

• 首先进行两种分类：随着网络事件处理定时事件；不随着网络事件处理时间事件；

定时器概述

对于一个服务器来说，需要许多客户端进行通信，必然会有网络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 timeval *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处理和定时任务解耦。

定时器设计

既然要使用定时器，必然离不开定时器的设计，那么如何设计定时器，成为接下来需要解决的问题。

接口设计

首先是接口的设计

基本接口：

1. 初始化定时器：void init_timer();
2. 添加定时任务：Node *add_timer(int expire,callback cb);
3. 删除定时任务：bool delete_timer(Node* node);一般在检测定时器的时候使用，可以不对外提供该接口；
4. 找到最近的需要被触发的定时任务：Node* find_nearest_timer();这种接口一般应用于网络事件和定时事件在一个线程中处理的触发方式。
5. 检测更新所有定时任务：void update_timer();
6. 清除所有定时任务 :void clear_timer();

内部数据结构选择

对外提供的接口解决了，那么接下来该思考定时器内部该用什么样的数据结构维护定时任务会让效率达到最佳；

该数据结构需要满足一些条件，比如查询最小节点的时间复杂度比如得小，比如增加删除节点不会影响原有的数据结构。

因此选择出来了，红黑树、最小堆都是最佳的选择。

红黑树

红黑树的中序遍历，让数据可以有序排序，而且是绝对排序（从小到大排序）。具体数据结构，可以去查找网上其他资料。

• 增删查的时间复杂度均为O(logN);
• 最小的节点为红黑树最左侧的节点，时间复杂度O(logN);
• 如果几乎同时来个两个时间相等的任务，但是key值比较时会出现相等的情况，你可以把后来的任务放到其右节点位置。

最小堆

最小堆是一个完全二叉树，且父节点一定比子节点小，这样得到的结果就是根节点一定是这棵树的最小值；具体数据结构，可以去查找网上其他资料。

• 增查的时间复杂度O(logN);

• 删除操作需要查找是否包含这个节点，删除的时间复杂度O(n);

• 最小节点的时间复杂度为O(1);

时间轮

以上两种实现方法需要时时刻刻都要进行检测，对于定时任务密集类型的自然可以，如果是定时任务之间的间隔时间过长怎么办？时时刻刻检测会增加很多无效检测，降低cpu的使用效率。

使用时间轮是一种解决上述问题的方法；

时间轮需要保证自己的时间精度足够小，否则会出现不能插入定时任务的情况

单层级时间轮

首先先谈一谈单层级时间轮，单层级时间轮就是使用数组模拟一个环形队列，数组的每一个元素是一个定时任务链表。通过一个指针不断遍历这个数组，遇到某个元素的任务链表不为空就执行相应的任务。

对于单层级时间轮需要数组的大小足够大，否则插入的定时任务超出数组可关注时间（比如时间精度1ms，数组大小为20，可关注的时间就是20ms）的N多倍，会导致定时任务执行顺序出错。（不确定在定时任务的结构体增加一个圈数可不可以）;

多层级时间轮

那么多层级时间轮就是解决上述问题一个好的解决办法。类似于进制进位一样，一旦超过该层级的可关注时间，就会进入下一层级，直到有位置可以插入；如果某个定时任务即将执行，也会不断返回上一层级，直至挂载到第一层级（也是被执行层级）。

如果使用时间轮也是直接使用多层级时间轮的，它有以下这些优点：

• 相比于单层级时间轮，它的空间占用大大减少；因为多层级针对任务的时间储存是乘的关系，而单层级是加的关系
• 对于多层级，除去第一层的任务需要时时刻刻关注，其他层的元素每增加一次重新映射一次即可。

数据结构

struct timer_event {
	uint32_t handle;
	int session;
};
// 定时任务
struct timer_node {
	struct timer_node *next;
	uint32_t expire;
};
// 任务链表
struct link_list {
	struct timer_node head;
	struct timer_node *tail;
};
struct timer {
	struct link_list near[TIME_NEAR];
	struct link_list t[4][TIME_LEVEL];
	struct spinlock lock;	// 自旋锁，多线程操作需要，时间复杂度O(1)
	uint32_t time;			//时间指针，范围是2^32*10ms
	uint32_t starttime;
	uint64_t current;
	uint64_t current_point;
};

因此针对时间轮设计，需要确定几点：

1. 确定时间范围。每一层级允许的添加任务的时间范围
2. 确定时间精度。每一次tick(指针增加一次)的时间
3. 确定时间层级。第一层组织最近关注的延时任务，是实际执行的层级；其他层级只负责向上一层级重新映射。
4. 实现添加任务接口。
5. 实现删除任务的接口。对于删除任务，一般不采取直接从链表删除的方式，因为时间指针一直再增加，定时任务可能会被重新映射，节点位置发生改变。因此，可以通过添加一个标记字段cancel，当cancel=true时不执行具体任务。
6. 实现重新映射，每一次时间指针移动都需要判断是否可重新映射。

时间轮总结

时间轮顾名思义，是仿照时钟规律而发明出来的。使用时间轮就是使用多层级时间轮。

时间轮通过多个层级存放定时任务，第一层组织最近关注的延时任务，是实际执行的层级；其他层级只负责向上一层级重新映射。

对于相同时间触发的定时任务，时间轮采用一个链表将它们存放在同一个时间槽，时间到达时一起执行。

多线程下，定时器只管检测，检测到了定时任务，将其抛给线程池执行，定时器本身线程不执行定时任务的业务逻辑。

时间轮删除节点很不方便，一般不采用删除方式，因为时间指针一直在移动，定时任务可能会被重新映射，节点位置发生改变；因此，可以通过添加一个标记字段cancel，当cancel=true时不执行具体任务。

内部数据结构选择总结

多线程环境下，使用最小堆和红黑树的定时器，在进行添加任务、删除任务的时候需要把整个树进行加锁，使用互斥锁；如果是时间轮，由于其时间复杂度为O(1)，对于添加任务、删除任务使用自旋锁即可。

如果定时任务比较少，可以选择红黑树或者最小堆；如果定时任务比较多，选择时间轮。

说明

写这篇文章的目的，是捋清定时器会有哪些问题，从宏观的一个角度去看待定时器，如果内容有哪些地方不够细节，可以利用谷歌、必应进行搜索，深度了解其原理、或者实现代码。比如红黑树的数据结构是什么样的、最小堆的数据结构是什么样的等这些问题我相信有很多大牛会比我讲的更好，或者说有着更深刻的理解。

此外，本人目前只是一名大学生，对于编程自认为没有达到很高的水平，而且很多地方也有一些借鉴的成分，如果文章中有任何不对的地方，欢迎指正，本人会虚心接受的。