很多场景都会用到定时器，比如心跳检测、倒计时、技能冷却等。
一般定时任务的形式表现为：
那定时器到底是什么呢？可以理解为这样一个数据结构：
那应该如何判断一个任务是否到期呢？
对于服务端的来说，驱动服务端逻辑的事件主要有两个：一个是网络事件，一个是时间事件。
在不同的框架中，这两种事件有不同的实现方式：
// 第一种：
while(!quit){
int now = get_now_time(); //单位：ms
int timeout = get_nearset_timer() - now;
if(timeout < 0){
timeout = 0;
}
int nevent = epoll_wait(epfd, ev, nev, timeout);
for(int i = 0; i < nevent; i++){
//.... 网络事件处理
}
update_timer(); //时间事件处理
}
// 第二种 在其他线程添加定时任务
void *thread_timer(void *thread_param){
init_timer();
while(!quit){
update_timer();
sleep(t);
}
clear_timer();
return NULL;
}
pthread_create(&pid, NULL, thread_timer, &thread_param);
需要注意两点：
绝对禁止的操作
其线程模型应该如下如下：
也就是说要把任务注册、任务到期检查、任务执行这三个分开
必须满足：
为此，有如下选择
（1） 有序链表
（2）红黑树
（3） 最小堆
（4） 跳表
（5）时间轮
怎么选择：
// 初始化定时器
void init_timer();
// 添加定时器
Node* add_timer(int expire, callback cb);
// 删除定时器
bool del_timer(Node* node);
// 找到最近要发⽣的定时任务
Node* find_nearest_timer();
// 更新检测定时器
void update_timer();
// 清除定时器
// void clear_timer();
#pragma once
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
#include "rbtree.h"
ngx_rbtree_t timer;
static ngx_rbtree_node_t sentinel;
typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);
struct timer_entry_s {
ngx_rbtree_node_t rbnode;
timer_handler_pt handler;
};
static uint32_t current_time() {
uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
struct timespec ti;
clock_gettime(CLOCK_MONOTONIC, &ti);
t = (uint32_t)ti.tv_sec * 1000;
t += ti.tv_nsec / 1000000;
#else
struct timeval tv;
gettimeofday(&tv, NULL);
t = (uint32_t)tv.tv_sec * 1000;
t += tv.tv_usec / 1000;
#endif
return t;
}
ngx_rbtree_t * init_timer() {
ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value);
return &timer;
}
void add_timer(uint32_t msec, timer_handler_pt func) {
timer_entry_t *te = (timer_entry_t *)malloc(sizeof(timer_entry_t));
memset(te, 0, sizeof(timer_entry_t));
te->handler = func;
msec += current_time();
printf("add_timer expire at msec = %u\n", msec);
te->rbnode.key = msec;
ngx_rbtree_insert(&timer, &te->rbnode);
}
void del_timer(timer_entry_t *te) {
ngx_rbtree_delete(&timer, &te->rbnode);
free(te);
}
int find_nearest_expire_timer() {
ngx_rbtree_node_t *node;
if (timer.root == &sentinel) {
return -1;
}
node = ngx_rbtree_min(timer.root, timer.sentinel);
int diff = (int)node->key - (int)current_time();
return diff > 0 ? diff : 0;
}
void expire_timer() {
timer_entry_t *te;
ngx_rbtree_node_t *sentinel, *root, *node;
sentinel = timer.sentinel;
uint32_t now = current_time();
for (;;) {
root = timer.root;
if (root == sentinel) break;
node = ngx_rbtree_min(root, sentinel);
if (node->key > now) break;
printf("touch timer expire time=%u, now = %u\n", node->key, now);
te = (timer_entry_t *) ((char *) node - offsetof(timer_entry_t, rbnode));
te->handler(te);
ngx_rbtree_delete(&timer, &te->rbnode);
free(te);
}
}
#include <stdio.h>
#include <string.h>
#include <sys/epoll.h>
#include "rbt-timer.h"
void hello_world(timer_entry_t *te) {
printf("hello world time = %u\n", te->rbnode.key);
}
int main()
{
init_timer();
add_timer(3000, hello_world);
int epfd = epoll_create(1);
struct epoll_event events[512];
for (;;) {
int nearest = find_nearest_expire_timer();
int n = epoll_wait(epfd, events, 512, nearest);
for (int i=0; i < n; i++) {
//
}
expire_timer();
}
return 0;
}
#ifndef MARK_MINHEAP_TIMER_H
#define MARK_MINHEAP_TIMER_H
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include "minheap.h"
static min_heap_t min_heap;
static uint32_t
current_time() {
uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
struct timespec ti;
clock_gettime(CLOCK_MONOTONIC, &ti);
t = (uint32_t)ti.tv_sec * 1000;
t += ti.tv_nsec / 1000000;
#else
struct timeval tv;
gettimeofday(&tv, NULL);
t = (uint32_t)tv.tv_sec * 1000;
t += tv.tv_usec / 1000;
#endif
return t;
}
void init_timer() {
min_heap_ctor_(&min_heap);
}
timer_entry_t * add_timer(uint32_t msec, timer_handler_pt callback) {
timer_entry_t *te = (timer_entry_t *)malloc(sizeof(*te));
if (!te) {
return NULL;
}
memset(te, 0, sizeof(timer_entry_t));
te->handler = callback;
te->time = current_time() + msec;
if (0 != min_heap_push_(&min_heap, te)) {
free(te);
return NULL;
}
printf("add timer time = %u now = %u\n", te->time, current_time());
return te;
}
bool del_timer(timer_entry_t *e) {
return 0 == min_heap_erase_(&min_heap, e);
}
int find_nearest_expire_timer() {
timer_entry_t *te = min_heap_top_(&min_heap);
if (!te) return -1;
int diff = (int) te->time - (int)current_time();
return diff > 0 ? diff : 0;
}
void expire_timer() {
uint32_t cur = current_time();
for (;;) {
timer_entry_t *te = min_heap_top_(&min_heap);
if (!te) break;
if (te->time > cur) break;
te->handler(te);
min_heap_pop_(&min_heap);
free(te);
}
}
#endif // MARK_MINHEAP_TIMER_H
#include <stdio.h>
#include <sys/epoll.h>
#include "mh-timer.h"
void hello_world(timer_entry_t *te) {
printf("hello world time = %u\n", te->time);
}
int main() {
init_timer();
add_timer(3000, hello_world);
int epfd = epoll_create(1);
struct epoll_event events[512];
for (;;) {
int nearest = find_nearest_expire_timer();
int n = epoll_wait(epfd, events, 512, nearest);
for (int i=0; i < n; i++) {
//
}
expire_timer();
}
return 0;
}
// gcc mh-timer.c minheap.c -o mh -I./
可以将所有的定时器都放到一个[最小堆]中，并且在内部启动一个线程，持续检查堆顶的定时器是否已经到期，如果到期则触发对应的回调函数
将所有的定时器放到一个最小堆中，有几个明显的缺点：
怎么优化呢？
还可以进一步优化：
为何要引入时间轮：
时间轮算法是通过一个时间轮去维护定时任务。一个时间轮就是一个环形结构，可以想象成时钟：
如上图：
时间轮的数据结构：
比如说当我们需要在3小时、4小时、5小时之后执行某个任务，那么，如下图，我们做出一个时间轮，刻度是1h。
可以看到插入任务从计算槽位到插入链表，时间复杂度都是O(1)。
如果任务超出了刻度怎么办？比如说我有个任务，需要每周一上午9点指向，还有另一个任务，需要每周三的上午9点执行，怎么处理呢？
有如下方式：
ps：时间轮除了定时任务之外，还能实现延迟消息的功能。比如让一个任务几分钟之后发送一条消息出去。在比如可以实现订单过期功能，用户下单10分钟没付款，就取消订单，可以通过时钟轮实现。
HashedWheelTimer是一个环形结构，可以用时钟来类比，钟面上有很多bucket，每一个bucket上可以存放多个任务，使用一个list保存该时刻到期的所有任务，同时一个指针随着时间流逝一格一格的转动，并执行对应bucket上所有到期的任务。任务通过取模决定应该放入哪个bucket。
从时钟表盘出发，如何⽤数据结构来描述秒表的运转
时间轮小结：
怎么实现呢？
一个时间轮就是一个定时器容器，该容器可以高效的管理定时器。思路如下：
在层级时间轮中，将插槽分为多个层次，每一层的时间轮的插槽范围都会扩大。比如：
举个例子：
在这个例子中，时钟轮的扫描周期仍是 100 毫秒，但是其中的任务并没有被过多的重复扫描，它完美地解决了 CPU 浪费的问题