层级时间轮实现高性能定时器
此篇介绍时间轮，它的时间复杂度是最优的，插入、查找（最小）、删除都是O（1），很恐怖的性能
这里示例一个三层时间轮，模拟时钟表盘的运作方式，便于理解且性能不低
设计思路：
1.根据定时任务的超时时间，按超时时间范围存入不同的链表中，处于同一个链表的任务的超时时间范围相同但无序
2.每一个槽中放入一个链表，可以通过槽访问链表的头尾节点
3.定时任务是否超时的判断依据是，定时任务从创建到即将执行这一过程中，定时器的内部时间time的增长是否大于任务的超时时间，也就是说，在定时器里有内部时间概念，这个时间是由函数调用手动递增的，而不是系统时间
这是定时器以及定时任务的结构
struct timer_node { struct timer_node *next; uint32_t expire; handler_pt callback; uint8_t cancel; }; typedef struct link_list { timer_node_t head; timer_node_t *tail; } link_list_t; typedef struct timer { link_list_t second[SECONDS]; // 秒槽 link_list_t minute[MINUTES]; // 分钟槽 link_list_t hour[HOURS]; // 小时槽 spinklock_t lock; uint32_t time; time_t current_point; } timer_st;
对于一个定时任务 timer_node
1.首先它是一个链表，所以需要next指针
2.expire是自定义的超时时间，这个时间概念是由定时器维护的
3.callback，该定时任务所执行的函数
对于一个定时器 timer
1.second[SECONDS];这是一个结构体数组，数组的每一位存储着一个link_list链表,这个链表存储着一些定时任务节点，根据命名可以看出，SECONDS = 60，
示例：超时时间为1秒的任务存放在second[1]链表中，超时时间为59秒的任务存放在second[59]链表中，此时如果有两个超时时间为2秒的任务，那么它们都将存放在second[2]链表中
2.minute[MINUTES];分钟槽，这里存放着超时时间范围在（1，60]分钟的定时任务
示例：超时时间为65秒和90秒的定时任务都将存放在minute[1]链表中，因为它们都属于60-120s这个时间范围
3.time，这就是定时器维护的内部时间了，一般初始化为0，代表第0秒，在时间轮运行时，会有函数将它递增，因此它区别于系统时间每秒+1，它的秒数增长频率是不固定的
4.time_t current_point;这是一个time_t类型的变量，用于保存一个系统时间，在时间轮中用于time增长的参考
接下来介绍几个核心的函数：
1.添加定时任务：
static void add_node(timer_st *T, timer_node_t *node) { uint32_t time = node->expire; // 定时任务的绝对超时时间 uint32_t current_time = T->time; // 定时器内部当前时间 uint32_t mesc = time - current_time; // 定时任务的相对超时时间 if (mesc < ONE_MINUTE) { link_to(&T->second[time % SECONDS], node); } else if (mesc < ONE_HOUR) { link_to(&T->minute[(uint32_t)(time/ONE_MINUTE) % MINUTES], node); } else { link_to(&T->hour[(uint32_t)(time/ONE_HOUR) % HOURS], node); } } timer_node_t *add_timer(int time, handler_pt func) { timer_node_t *node = (timer_node_t *)malloc(sizeof(*node)); spinlock_lock(&TI->lock); node->expire = time + TI->time; ptinrf("add timer at %u, expire at %u, now_time at %lu\n", TI->time, node->expire, now_time()); node->callback = func; node->cancel = 0; if (time <= 0) { spinlock_unlock(&TI-> lock); node->callback(node); free(node); return NULL; } add_node(TI, node); spinlock_unlock(&TI->lock); return node; }
逻辑：
1.先根据任务指定的expire确定超时时间点，为expire(超时时间) + TI->time(定时器当前时间)
- 设置任务的回调函数（非重点）
- 根据超时时间点，将该定时任务添加到正确的时间轮槽中：
static void add_node(timer_st *T, timer_node_t *node) { uint32_t time = node->expire; // 绝对超时时间 uint32_t current_time = T->time; // 当前的定时器事件 uint32_t mesc = time - current_time; // 多少秒后超时（绝对超时时间） if (mesc < ONE_MINUTE) { // 相对超时时间小于一分钟 link_to(&T->second[time % SECONDS], node); // 添加到秒槽中 } else if (mesc < ONE_HOUR) { // 大于一分钟，小于60分钟 link_to(&T->minute[(uint32_t)(time/ONE_MINUTE) % MINUTES], node);// 添加到分钟槽中 } else { // 添加到小时槽中 link_to(&T->hour[(uint32_t)(time/ONE_HOUR) % HOURS], node); } }
重点中的重点
相信你注意到了add_node函数中的**mesc = time - current_time;**，由于定时器的时间推进，一个定时任务的相对超时时间会随之减少，会导致在某一（定时器）时刻，一些定时任务的位置变得不正确，例如一个65秒的定时任务，在10秒后仍未得到处理，那么它此时的相对超时时间是55秒，这时，它应该由原来所在的minute分钟槽移动到second秒槽中
由于这种情况会普遍发生，我们需要利用额外的函数处理这些需要重新换槽的任务——remap函数
remap（）// 重新映射
remap要做的很简单：将一个槽中的全部或部分节点搬到另一个或几个槽中，简洁的操作是：先将原槽清空，再为这些节点重新匹配合适的槽，这就叫做重新映射
static void remap(timer_st *T, link_list_t *level, int idx) { timer_node_t *current = link_clear(&level[idx]); // 清空当前槽 while (current) { // 将槽中的节点全部重新映射到新槽 timer_node_t *temp = current->next; add_node(T, current); // 核心操作，重新匹配并添加到槽中 current = temp; } }
时间轮的推进—定时器内部时间增长
static void timer_shift(timer_st *T) { uint32_t ct = ++T->time % HALF_DAY; // 定时器内部时间 + 1秒 if (ct % SECONDS == 0) { // 当前时间为整分钟 // 每分钟重新分配一次 uint32_t minute_idx = (ct / ONE_MINUTE) % MINUTES; if (minute_idx != 0) { // 当前时间是整分钟 remap(T, T->minute, minute_idx); } // 每小时重新分配一次 if (ct % ONE_HOUR == 0) { uint32_t hour_idx = (ct / ONE_HOUR) % HOURS; remap(T, T->hour, hour_idx); } } }
每推进一秒定时器时间，判断一次是否需要重新分配分钟槽或小时槽
1.每一分钟remap一次分钟槽到秒槽，因为每过一分钟，大于一分钟小于两分钟的任务的相对超时时间会变为一分钟内
2.每小时remap一次小时槽到分钟槽中，因为每过一小时，大一小时小于两小时的任务的相对时间会变为一小时内
执行定时任务：
static void timer_execute(timer_st *T) { uint32_t idx = T->time % SECONDS; // 每一次执行最小时间单位槽-->秒 中的定时器任务 while (T->second[idx].head.next) { timer_node_t *current = link_clear(&T->second[idx]); spinklock_unlock(&T->lock); dispatch_list(current); spinlock_lock(&T->lock); } } static void dispath_list(timer_node_t *current) { do { timer_node_t * temp = current; current = current->next; if (temp->cancel == 0) temp->callback(temp); free(temp); } while (current); }
每次执行一个槽中链表的所有任务，任务执行后会被移除
值得注意的是
每次只执行秒槽中的任务，因为这是定时器的最小执行精度，并且分钟槽和小时槽中的任务最终也会随定时器的时间推进而重新映射到秒槽中
运行定时器
static void timer_update(timer_st *T) { spinlock_lock(&T->lock); timer_execute(T); // 执行一个秒槽中的任务 timer_shift(T); // 推进定时器内部时间 timer_execute(T); spinlock_unlock(&T->lock); } void check_timer(int *stop) { // 同步系统时间和定时器的当前时间 while (*stop == 0) { time_t cp = now_time(); // 获取系统当前时间 if (cp != TI->current_point) { // 当前系统时间于上一次获取的系统时间的对比 uint32_t diff = (uint32_t)(cp - TI->current_point); // 当前系统时间于上一次获取的系统时间的时间差 TI->current_point = cp; // 更新定时器内暂存的系统时间 int i; for (i = 0; i < diff; i++) { // 推进定时器，补偿时间差 timer_update(TI); // 推动定时器时间增长、处理任务 } } usleep(200000); // 循环运行间隔 } }
