定时器——最小堆、红黑树、时间轮

本文主要是介绍定时器——最小堆、红黑树、时间轮，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 定时器触发方式

有两种触发方式

IO多路复用的最后一个参数（Redis、Nginx）
timerfd：将定时任务转化为IO，让IO多路复用进行检测

2 定时器设计

2.1 红黑树

参见3

2.2 最小堆

在这里插入图片描述

堆顶最先过期

2.3 时间轮

在这里插入图片描述

假如上述分别表示秒、分、时，三个指针都指向0所在的位置，则3秒后的任务挂在第一行的3处，1分06秒的任务挂在第二行的1处，依此类推。

当到达3秒时，取出任务执行，当遍历完第一行后（过了60秒），第二行中1的任务将重新排列到第1行中，原先1分06秒的任务将挂在第一行的6下（第6秒），第二行的指针将指向1处。

多个层级的好处：
上述时间轮所能表示的最大范围为12 * 60 * 60 = 43200秒，若用线性数组，则需要43200大小的空间，而上述时间轮的空间只有60 + 60 + 12 = 132，大大节省了空间。

在时间轮的设计中，需关注：

时间指针：按照最小精度进行移动
最小精度：最小精度表示能接受的误差，第一行定义了最小精度，上述时间轮最小精度是1秒
最大范围：上述时间轮最大能表示43200秒的范围

3 基于set+timerfd的定时器实现

源码：
通过网盘分享的文件：timers
链接: https://pan.baidu.com/s/1OfBjuXimXbYaC1j7550oTw?pwd=8xib 提取码: 8xib

3.1 时间对象

struct TimerNodeBase {time_t expire; //过期时间uint64_t id; //自增id，由于同一时间可能有多个任务，因此不能用expire作为标识//id越大，插入越晚
};struct TimerNode : public TimerNodeBase {using Callback = std::function<void(const TimerNode &node)>; //函数对象Callback func;TimerNode(int64_t id, time_t expire, Callback func) : func(std::move(func)) {this->expire = expire;this->id = id;}
};

这里为什么要封装两个类，使用继承，而不是就一个类呢？

由于我们使用了set，set<TimerNode, std::less<>> timeouts;，set中的元素是对象，而set又是基于红黑树，插入和删除会左旋、右旋，使用两个类，避免Callback参与比较，避免Callback的拷贝

3.2 定时器

class Timer {
public:static inline time_t GetTick() {return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();} //获取当前时间
private:static inline uint64_t GenID() {return gid++;}static uint64_t gid;set<TimerNode, std::less<>> timeouts;
};uint64_t Timer::gid = 0;

gid为自增的id，唯一标识TimerNode

3.2.1 重载比较

bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {if(lhd.expire < rhd.expire) {return true;} else if(lhd.expire > rhd.expire) {return false;} else return lhd.id < rhd.id;
}

set中是TimerNode对象，set无法进行比较，需自行定义比较函数

3.2.2 AddTimer

TimerNodeBase AddTimer(int msec, TimerNode::Callback func)
{time_t expire = GetTick() + msec; //获取过期时间if(timeouts.empty() || expire <= timeouts.crbegin()->expire) {auto pairs = timeouts.emplace(GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*pairs.first);}auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));return static_cast<TimerNodeBase>(*ele);
}

使用emplace：使用insert会创建一个对象，再拷贝到红黑树中，emplace避免拷贝
区分if：if内是常规插入，而使用emplace_hint插入到最后面，因为很多时候定时器是按时间序插入的，直接插入到红黑树的最右侧即可。

3.2.3 DelTimer

void DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if(iter != timeouts.end()) {timeouts.erase(iter);}
}

3.3.4 HandleTimer

void HandleTimer(time_t now) {auto iter = timeouts.begin();while(iter != timeouts.end() && iter->expire <= now) {iter->func(*iter);iter = timeouts.erase(iter);}
}

由于using Callback = std::function<void(const TimerNode &node)>;

故函数的参数是TimerNode对象，所以func(*iter)

3.3 timerfd

int epfd = epoll_create(1);
int timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
struct epoll_event ev = {.events=EPOLLIN | EPOLLET};
epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &ev);unique_ptr<Timer> timer = make_unique<Timer>();timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
});struct epoll_event evs[64] = {0};while (true) {int n = epoll_wait(epfd, evs, 64, -1);time_t now = Timer::GetTick();...timer->HandleTimer(now);
}epoll_ctl(epfd, EPOLL_CTL_DEL, timerfd, &ev);
close(timerfd);
close(epfd);