一、定时器的应用
定时器就像闹钟，可以设定一个时间，然后进入倒计时，到点了提醒我们。同样，应用开发也需要一个定时器，通过设定时间，到点了唤醒程序去执行某项任务。
常见的应用场景有：
1）心跳检测
2）游戏技能冷却
3）倒计时
4） 其他需要延时处理的功能
定时器由两部分组成：容器 + 检测触发机制
1）容器：负责组织大量定时任务
2）检测触发机制：负责检测最近要触发的定时任务
二、定时器的触发方式
对服务端来说，驱动服务端业务逻辑的事件，包括：网络事件、定时事件、以及信号事件。
通常，网络事件和定时事件会进行协同处理。
定时器触发形式通常有两种：
1）利用I/O多路复用系统调用的最后一个参数（超时时间），来触发检测定时器。
2）利用timefd，将定时检测作为I/O多路复用当中的事件进行处理。
2.1 网络事件和定时事件在一个线程中处理
网络事件和定时事件可以进行协同处理，即网络事件和定时事件在一个线程中处理。以epoll多路复用器为例子，通过epoll_wait()的第四个参数timeout作为延时触发定时器，业务逻辑的执行也在同一个线程中。
// 网络事件和定时事件在一个线程中处理，协同处理 while (!quit) { // 最近定时任务的触发时间 = 最近要被触任务的触发时间 - 当前时间 int timeout = get_nearest_timer() - now(); if (timeout < 0) timeout = -1; // 定时任务都过期 // 最近定时任务的触发时间作为 timeout 参数，timetout 定时任务触发 // 1、若没有网络事件，先去处理定时任务 // 2、若收到网络事件，先处理网络事件，再处理定时任务 int nevent = epoll_wait(epfd, ev, nev, timeout); for (int i = 0; i < nevent; i++) { // ... 处理网络事件 } // 轮询处理定时事件 update_timer(); }
1）为什么网络事件和定时事件可以协同处理？
因为reactor是基于事件的网络IO模型，IO的处理是同步的，事件的处理是异步的，而定时任务的处理也是异步的，所以事件的处理和定时任务的处理可以在一个线程中一起处理。
2）如何进行协同处理？
以 io 多路复用作为定时器驱动，“阻塞”地收集就绪事件，timeout 参数用于设置定时。
3）使用场景
- redis（单reactor）
- memcached、nginx（多reactor）
4）容器的数据结构
数据结构通常选择红黑树、跳表、最小堆等来实现定时器。
2.2
定时任务在通过一个单独的线程检测，以 sleep(time)作为定时器驱动，time 参数用于设置定时。
定时器事件的处理由其他线程或运行队列执行。
这种触发方式通常用于处理大量定时任务。
// 网络事件和定时事件在不同线程中处理 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);
该代码创建了一个单独的线程来处理定时事件。在循环中，定时器状态会被更新，并根据需要触发相应的事件。通过调用 sleep 函数，线程可以暂停一段时间，等待下一个定时事件的到来。最后，在线程结束时，定时器资源将被清理和释放。
1）数据结构
使用时间轮数据结构，在一个线程中利用sleep(time)负责检测（time要小于最小时间精度）。时间到达时，通过信号或插入运行队列让其他线程运行业务逻辑。
时间轮只负责检测。这种方式加锁粒度小。
二、定时器的设计
2.1 接口设计
基础接口有
1）初始化定时器
2）添加定时器 —— 添加定时任务
3）删除定时器 —— 删除定时任务
4）更新定时器 —— 到期任务的处理
另外，在协同处理的方案中，即网络事件和定时事件在一个线程中处理的触发方式。此时还需要额外添加接口，来查找最近定时任务的触发时间。
5）查找最近定时任务的触发时间
// 初始化定时器 void init_timer(); // 定时器的添加 Node* add_timer(int expire, callback cb); // 定时器的删除 bool del_timer(Node* node); // 定时器的更新 void update_timer(); // 返回最近定时任务的触发时间，用于协同处理 Node* find_nearest_timer();
2.2 数据结构设计
对定时任务的组织本质是要对定时任务优先级的处理。所谓优先级，就是先触发的定时任务放在最前面。由此产生两类数据结构；
1）按触发时间进行顺序组织，要求数据结构有序，或者相对有序。并且，能快速查找最近触发的定时任务，以及需要考虑怎么处理相同时间触发的定时任务。
- 红黑树（绝对有序）: nginx
- 跳表（绝对有序）：redis（将来引入）
- 最小堆（相对有序）: libevent, libev, go
2）按照执行顺序组织：时间轮
2.2.1 红黑树
红黑树的中序遍历是绝对有序的
2.2.3 最小堆
了解最小堆之前，需要先介绍满二叉树和完全二叉树
1）满二叉树：所有的层节点数都是该层所能容纳节点的最大数量，即满足
2）完全二叉树：若二叉树的深度为h，去掉了h层的节点，就是一个满二叉树；并且h层都集中在最左侧排序。
3）最小堆：
是一颗完全二叉树；
某一个节点的值总是小于等于它的子节点的值；
堆中任意一个节点的子树都是最小堆；
4）最小堆添加节点
为了满足完全二叉树的定义，往二叉树最高层沿着最左侧添加一个节点；然后考虑是否能上升操作；
如果此时添加值为 4 的节点，4 节点是 5 节点的左子树；4 比 5 小，4 和 5 需要交换值；
5）最小堆删除节点
删除操作需要先查找是否包含这个节点；确定存在后，交换最后一个节点，先考虑能否执行下降操作，否则执行上升操作；最后删除最后一个节点；
例如：删除 1 号节点，则需要下沉操作；
删除 9 号节点，则需要上升操作；
2.2.4 时间轮
时间轮是根据时钟运行规律而来的。时间精度为1s，时间范围为12h。定义三个数组分别存 秒、分、时；一个指针一秒钟移动一次，只需关注最近一分钟内要触发的定时任务。
1）添加任务
根据定时任务的间隔时间time，判断将其放在哪一层。
比如当前时间tick是65s，即秒针指向5，分针指向1。
现在要添加间隔时间112s的定时任务。那么根据((65+112)/60)%60 = 2，得到该任务添加在分针层级2的任务队列里。
2）重新映射
我们给出的时间轮的时间精度是秒，也就是只执行秒层的任务。所以秒针每转一圈，需要把下一分钟的任务重新映射到秒层。比如原来分针指向1，秒针转了一圈，下一轮需要把分针2里的任务，重新映射到秒层。
比如，原来添加的任务，过了55s后，当前时间120s。(65+112-120)%60 = 57，也就是刚才添加的任务映射在秒层57的位置。
3）删除节点
时间轮删除节点不方便，一般节点不能删除，因为tick一直在移动，会出现重新映射，节点位置可能改变。
那么可以添加一个标记字段cancel，当任务触发时检查这个字段，如果cancel=true则不执行具体任务。
三、利用红黑树实现定时器
3.1 数据结构
在C++中，set、map、multiset、multimap容器使用的是红黑树管理数据。这里选择 set来存储定时器任务。
使用set设计定时器，需要考虑一个关键问题：相同触发事件的定时任务如何处理？
举个例子，任务A到来时的时间 tick = 10，间隔 10s 后触发执行，其触发时间 expire = 20s ；任务B到来时的时间 tick = 15s，间隔 5s 后触发执行，其触发时间也是 expire = 20s。那到点了，应该先执行哪个任务呢？
我们根据插入顺序来决定执行顺序，先插入的先执行，放在红黑树的zuoce。后插入的后执行，放在红黑树的youce。通过 id 属性描述任务到来的先后顺序。
因此定时器结点的结构为
// 定义定时结点的基类，存储唯一标识的元素 struct TimerNodeBase { time_t expire; // 任务触发时间 int64_t id; // 用来描述插入先后顺序 }; // 定时结点，包含定时任务等 struct TimerNode : public TimerNodeBase { // 定时器任务回调函数 // C++ 11特性，使用函数对象。降低拷贝消耗，提高效率 // 使用 using 关键字定义了一个 Callback 类型的别名， // 别名指向一个接受 const TimerNode &node 参数、返回值为 void 的函数对象。 using Callback = std::function<void(const TimerNode &node)>; Callback func; // 构造函数，容器内部只构造一次 TimerNode(int64_t id, time_t expire, Callback func) : func(func) { this->expire = expire; this->id = id; } };
在代码中，我们把函数对象剥离出来。这是因为红黑树在改变的时候，为了保持平衡，需要频繁的对比。而对比就涉及到复制、移动等操作。注意到，对比我们只需要对比触发时间和id，不需要函数对象。
函数对象作为类，占用大量的空间，复制和移动代价高，因此，我们拆分成基类和派生类，基类存储标识，用于复制和移动；子类存储函数对象等，在容器内构造后，不再复制和移动。
因此，实现比较函数，采用基类引用比较。
// 按触发时间的先后顺序对结点进行排序 bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) { // 先比较触发时间 if (lhd.expire < rhd.expire) return true; else if (lhd.expire > rhd.expire) return false; // 触发时间相同，比较插入的先后顺序 // 比较id大小，先插入的结点id小，先执行 return lhd.id < rhd.id; }
3.2 接口实现
3.2.1 初始化定时器
获取当前时间
static time_t GetTick() { auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now()); auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch()); return temp.count(); }
1）chrono::steady_clock::now()：获取系统启动到当前的稳定时间。
2）chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now())：将当前的稳定时钟时间点转换为毫秒精度的时间点（time_point）。
3）sc.time_since_epoch()：计算时间间隔（duration）。
4）chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch())：将计算得到的时间间隔转换为毫秒精度（milliseconds）。
5）temp.count()：获取转换后的时间间隔的值，即毫秒数。
3.2.2 添加定时器
// 参数： msec 任务触发时间间隔，func 任务执行的回调函数 TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) { time_t expire = GetTick() + msec; // 相对于insert，emplace 避免了额外的拷贝或移动操作 auto ele = timermap.emplace(GenID(), expire, func); return static_cast<TimerNodeBase>(*ele.first); }
上面代码每次插入，需要根据红黑树的插入，重新调整set容器。其实红黑树是有序的，如果是插入一个大于红黑树最右边结点的元素，直接在这个结点，也就是容器末尾插入即可，时间复杂度O(1)。
TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) { time_t expire = GetTick() + msec; // 如果timermap为空，或者触发时间<=timermap的最后一个（最大的）结点的时间，正常插入 if (timermap.empty() || expire <= timermap.crbegin()->expire){ auto pairs = timermap.emplace(GenID(), expire, std::move(func)); return static_cast<TimerNodeBase>(*pairs.first); } // 否则直接插入最后，emplace_hint插入时间复杂度是O(1) auto ele = timermap.emplace_hint(timermap.crbegin().base(), GenID(), expire, std::move(func)); return static_cast<TimerNodeBase>(*ele); }
3.2.3 删除定时器
bool DelTimer(TimerNodeBase &node) { // 代替子类结点，避免函数对象复制控制和移动 auto iter = timermap.find(node); // 若存在，则删除该结点 if (iter != timermap.end()) { timermap.erase(iter); return true; } return false; }
3.2.4 更新定时器
bool CheckTimer() { auto iter = timermap.begin(); if (iter != timermap.end() && iter->expire <= GetTick()) { // 定时任务被触发，则执行对应的定时任务 iter->func(*iter); // 删除执行完毕的定时任务 timermap.erase(iter); return true; } return false; }
3.2.5 返回最近定时任务的触发时间
time_t TimeToSleep() { auto iter = timermap.begin(); if (iter == timermap.end()) { return -1; } // 最近任务的触发时间 = 最近任务初始设置的触发时间 - 当前时间 time_t diss = iter->expire - GetTick(); // 最近要触发的任务时间 > 0，继续等待；= 0，立即处理任务 (对应epoll_wait 的 timeout) return diss > 0 ? diss : 0; }
3.3 定时器的驱动
定时器驱动的方式，这里选择 epoll 来实现，通过参数 timeout 设置定时。
while (true) { // 最近任务的触发时间接口：TimeToSlee，作为 timeout 参数 int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep()); for (int i = 0; i < n; i++) { /* 处理网络事件 */ } // 处理定时事件 while(timer->CheckTimer()); }
3.4 代码实现
// g++ timer.cc -o timer -std=c++14 #include <sys/epoll.h> #include <functional> #include <chrono> #include <set> #include <memory> #include <iostream> using namespace std; // 定时结点的基类，存储唯一标识的元素，轻量级，用于比较 struct TimerNodeBase { time_t expire; // 任务触发时间 int64_t id; // 用来描述插入先后顺序，int64_t，能记录5000多年 }; // 定时结点，包含定时任务等 struct TimerNode : public TimerNodeBase { // 定时器任务回调函数 // 函数对象拷贝代价高，在容器内拷贝构造后不会再去移动 using Callback = std::function<void(const TimerNode &node)>; Callback func; // 构造函数，容器内部就地拷贝构造调用一次，此后不会再去调用 TimerNode(int64_t id, time_t expire, Callback func) : func(func) { this->expire = expire; this->id = id; } }; // 根据触发时间对结点进行排序 // 基类引用，多态特性，基类代替timerNode结点，避免拷贝构造子类 bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) { // 先比较触发时间 if (lhd.expire < rhd.expire) return true; else if (lhd.expire > rhd.expire) return false; // 触发时间相同，比较插入的先后顺序 // 比较id大小，先插入的结点id小，先执行 return lhd.id < rhd.id; } // 定时器类的实现 class Timer { public: // 获取当前时间 static time_t GetTick() { // 获取系统时间戳，系统启动到当前的时间 auto sc = chrono::time_point_cast<chrono::milliseconds>(chrono::steady_clock::now()); // 获取到时间戳的时间段 auto temp = chrono::duration_cast<chrono::milliseconds>(sc.time_since_epoch()); return temp.count(); } // 2、添加定时任务 // 参数： msec 任务触发时间间隔，func 任务执行的回调函数 TimerNodeBase AddTimer(time_t msec, TimerNode::Callback func) { time_t expire = GetTick() + msec; // 如果timermap为空，或者触发时间<=timermap的最后一个（最大的）结点的时间，正常插入 if (timermap.empty() || expire <= timermap.crbegin()->expire){ auto pairs = timermap.emplace(GenID(), expire, std::move(func)); return static_cast<TimerNodeBase>(*pairs.first); } // 否则直接插入最后，emplace_hint插入时间复杂度是O(1) auto ele = timermap.emplace_hint(timermap.crbegin().base(), GenID(), expire, std::move(func)); return static_cast<TimerNodeBase>(*ele); } // 3、删除/取消定时任务 bool DelTimer(TimerNodeBase &node) { // C++14的新特性：只需传递等价 key 比较，无需创建 key 对象比较， // 代替子类结点，避免函数对象复制控制和移动 auto iter = timermap.find(node); // 若存在，则删除该结点 if (iter != timermap.end()) { timermap.erase(iter); return true; } return false; } // 4、检测定时任务是否被触发，触发则执行定时任务 bool CheckTimer() { auto iter = timermap.begin(); if (iter != timermap.end() && iter->expire <= GetTick()) { // 定时任务被触发，则执行对应的定时任务 iter->func(*iter); // 删除执行完毕的定时任务 timermap.erase(iter); return true; } return false; } // 5、返回最近定时任务触发时间，作为timeout的参数 time_t TimeToSleep() { auto iter = timermap.begin(); if (iter == timermap.end()) { return -1; } // 最近任务的触发时间 = 最近任务初始设置的触发时间 - 当前时间 time_t diss = iter->expire - GetTick(); // 最近要触发的任务时间 > 0，继续等待；= 0，立即处理任务 return diss > 0 ? diss : 0; } private: // 产生 id 的方法 static int64_t GenID() { return gid++; } static int64_t gid; // 利用 set 排序快速查找要到期的任务 set<TimerNode, std::less<>> timermap; }; int64_t Timer::gid = 0; int main() { // 定时器驱动 int epfd = epoll_create(1); // 创建定时器 unique_ptr<Timer> timer = make_unique<Timer>(); int i = 0; timer->AddTimer(1000, [&](const TimerNode &node) { cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl; }); timer->AddTimer(1000, [&](const TimerNode &node) { cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl; }); timer->AddTimer(3000, [&](const TimerNode &node) { cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl; }); auto node = timer->AddTimer(2100, [&](const TimerNode &node) { cout << Timer::GetTick() << "node id:" << node.id << " revoked times:" << ++i << endl; }); timer->DelTimer(node); cout << "now time:" << Timer::GetTick() << endl; epoll_event ev[64] = {0}; while (true) { // 最近任务的触发时间接口：TimeToSlee，作为 timeout 参数 int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep()); for (int i = 0; i < n; i++) { /*... 处理网络事件 ...*/ } // 处理定时事件 while(timer->CheckTimer()); } return 0; }
