对于单层级时间轮需要数组的大小足够大，否则插入的定时任务超出数组可关注时间（比如时间精度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)，对于添加任务、删除任务使用自旋锁即可。

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

说明

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

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