定时器原理

如何理解定时器

定时器在日常通常被描述为组织大量延时任务的模块，其实从字面意思去理解的话，他就是去处理延时任务的，那么什么是延时任务呢？我们来看一张图：

在现代开发当中，同时是要处理多个任务的，我们将任务添加进某个数据结构到任务触发之间是存在一段时间间隔的，那么就会引发一个问题，这段时间当前 CPU 核心是在去等么？

这儿肯定是不会让 CPU 核心去等的，因为我们要保证一个原则，不过去占用一个线程，高效的处理定时任务，这也意味着再添加任务到触发任务之间的这一段时刻，我们不可能让线程在这儿进行等待，这样就违背了我们高效的原则了。

所以也就有了定时器的出现，在添加任务到触发任务之间肯定是会存在大量任务的，我们就需要将当前的大量任务组织起来，然后触发最近将要超时的任务，这样，就保证了当前线程并不是一味地在这儿阻塞进行等待，对于将要超时的任务他就会去进行处理。

那么定时器就可以被描述为组织大量延时任务的数据结构和触发最近将要超时任务的机制。

定时器数据结构选取

既然定时器需要组织大量的延时任务，就需要选取一种数据结构，最为合适的几种数据结构分别为：红黑树、最小堆和时间轮。

红黑树

根据上面的描述我们就可以这么去理解定时器，“时间”和“任务”，两者之间就成了对应的关系，某个时间点就对应了相应的任务，其实我们就可以看出来这天然的就对应这一种 [key，value] 的关系了，这种关系很容易就让人想到了红黑树这中数据结构。

同时，对于添加的任务来说，肯定是存在时间顺序的，因为定时器总是优先去处理最近将要么超时的任务：

红黑树是一种自平衡的二叉查找树，同时，他也是一种有序的数据结构，对于插入以及删除的时间复杂度都是O（LogN）级别的，如果要实现一个定时，红黑树肯定是一个可以选择的数据结构，在 C++ 的 STL 库中存在四种红黑树的数据结构：map/set/multimap/multiset，我们后续定时器的实现选取的就是multimap这个结构。

选取multimap这个结构主要是基于两点：

• 肯定会存在同一时间触发多个任务的场景存在，map的实现是基于一对一的关系的，而multimap是基于一对多的关系的，所以肯定是选multimap的；
• 我们通常是获取最近将要超时的任务，添加也是添加基于顺序进行添加的，那么基于红黑树这种数据结构，我们会发现第一种操作的的时间复杂度是O（1）。
  
  Ngnix，workflow里面的定时器都是基于红黑树进行实现的。

最小堆

最小堆是一种特殊的完全二叉树数据结构，其中每个父节点的值都小于或等于其子节点的值。这个性质使得最小堆的根节点始终是整个堆中的最小元素。

他的特点就在于：最小堆是一棵完全二叉树，意味着除了最后一层外，其他层都是完全填充的，且最后一层的节点尽可能向左靠拢。而且任意一个子节点页满足最小堆的要求。

对于最小堆来说他的查找，插入和删除的效率也是很高的，我们如果需要插入一个元素，基于最小堆的性质，肯定是往二叉树最高层沿着最左侧添加一个节点，然后考虑是否需要上升进行调整；删除一个元素也是，先找到这个元素，然后将其与最后一个节点进行交换，然后调整堆结构，这个可以参考之前的一篇文章：堆数据结构详解。

堆的这种理念其实跟定时器也是比较契合的，最小堆堆顶总是最小的那个数据，也就是我们最近需要处理的任务，同时，他的插入和删除的也是比较高的。libev，libevent 里面的定时器是基于最小堆实现的。

时间轮

红黑树，最小堆是按触发时间进行顺序组织，而接下来需要介绍的时间轮是按执行顺序进行组织的。

对于时间轮来说，它是基于钟表的原理来进行实现的：


对于Linux内核，Kafka 都是基于时间轮进行实现的。

定时器触发方式

对于服务端来说，驱动服务端业务逻辑的事件包括网络事件、定时事件、以及信号事件；通常网络事件和定时事件会进行协同处理；定时器触发形式通常有两种：

利用 IO 多路复用系统调用最后一个参数（超时），来触发检测定时器

理解定时器以后我们就很容易想到 IO 多路复用的最后一个参数timeout，他的取值会存在以下三种情况：

• NULL/nullptr：select调用后进行阻塞等待，直到被监视的某个文件描述符上的某个事件就绪。
• 0：selec调用后t进行非阻塞等待，无论被监视的文件描述符上的事件是否就绪，select检测后都会立即返回。
• 特定的时间值：select调用后在指定的时间内进行阻塞等待，如果被监视的文件描述符上一直没有事件就绪，则在该时间后select进行超时返回。

我们首先的理解 recator 的本质，他是将 IO 转化为对事件的管理，因为我们对于用户端来说，并不知道 IO 什么时候就绪，客户端何时发送数据，什么时候建立连接…，存在很多个不知道的情况，所以就会导致我们不知道什么时候去调用 accept/read/write，而 IO 多路复用解决的就是这个问题，当监听事件就绪就调用 accept 建立连接通路，真正的事件就绪就调用read/write对数据进行读写，他本质上解决的就是一个调用时机的问题。

对于我们的定时器来说，是处理定时任务的，他其实本质上也是一个事件，如果时间到了，就去执行，其实跟 IO 多路复用的这种思想是很相似的，我们都是需要去异步处理它，所以在这儿我们会使用 IO 多路复用的最后一个参数。

利用 timerfd，将定时检测作为 IO 多路复用当中的事件进行处理

timerfd 其实也是基于网络 IO 的思想进行实现的，他主要是依靠以下两个接口来进行实现的：

#include <sys/timerfd.h>int timerfd_create(int clockid, int flags);

timerfd_create 用于创建一个定时器文件描述符（timer file descriptor），它允许应用程序通过文件描述符来监控定时器事件，解析如下：

• clockid：指定定时器使用的时钟源，常见选项包括：
  CLOCK_REALTIME：系统实时时间（可受系统时间调整影响）；
  CLOCK_MONOTONIC：单调时钟（不受系统时间调整影响，适合测量时间间隔）；
  CLOCK_BOOTTIME（Linux 2.6.39 后支持）：类似 CLOCK_MONOTONIC，但包含系统休眠时间。
• flags：控制文件描述符的行为，可选值：
  TFD_NONBLOCK：设置文件描述符为非阻塞模式。
  TFD_CLOEXEC：设置文件描述符为 close-on-exec（执行 exec 时自动关闭）。

返回值：

• 成功时返回一个文件描述符（fd），可用于后续的 timerfd_settime 和 read 操作。
• 失败时返回 -1，并设置 errno（如 EINVAL 表示无效参数）。

int timerfd_settime(int fd, int flags, const struct itimerspec *new_value, struct itimerspec *old_value);

timerfd_settime 用于设置或修改 timerfd 计时器的到期时间和间隔周期。它是 timerfd 系列系统调用的一部分，需要配合 timerfd_create 创建的定时器文件描述符使用，参数解析：

• fd：由 timerfd_create 创建的定时器文件描述符；
• flags：控制标志位，可以是以下值之一：
  0：使用相对时间（以当前时间为基准）
  TFD_TIMER_ABSTIME：使用绝对时间（以 Epoch 时间为基准）
• new_value：指向 itimerspec 结构的指针，指定新的定时器设置；

struct itimerspec {struct timespec it_interval;  /* 定时器间隔周期 */struct timespec it_value;     /* 首次到期时间 */
};struct timespec {time_t tv_sec;                /* 秒 */long tv_nsec;                 /* 纳秒 */
};

• old_value：指向 itimerspec 结构的指针，用于存储之前的定时器设置（可为 NULL）。

返回值：

• 成功时返回 0
• 失败时返回 -1 并设置 errno

定时器的实现

接下来我们通过红黑树的方式来实现一个定时器：

#ifndef __TIMER__
#define __TIMER__#include <map>
#include <functional>
#include <chrono>// TimerNode 结点，延时任务
class TimerNode
{
public:friend class Timer;TimerNode(uint64_t timeout, std::function<void()> cb): timeout_(timeout), callback_(std::move(cb)){}private:uint64_t timeout_;std::function<void()> callback_;
};class Timer
{
public:// 添加延时任务TimerNode* AddTimeout();// 删除延时任务void DelTimeout();// 获取延时时间int WaitTime();// 处理延时任务void HandleTimeout();private:std::multimap<uint64_t, TimerNode *> timer_map_; // 前面代表超时时间，后面代表超时任务
};#endif

添加延时任务、

static uint64_t GetCurrentTime()
{using namespace std::chrono;return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
}
// 添加延时任务
TimerNode *AddTimeout(uint64_t diff, std::function<void()> cb)
{// 根据 diff 创建延时任务auto node = new TimerNode(GetCurrentTime() + diff, std::move(cb));if (timer_map_.empty() || node->timeout_ < timer_map_.rbegin()->first){auto it = timer_map_.insert(std::make_pair(node->timeout_, std::move(node)));return it->second;}else{auto it = timer_map_.emplace_hint(timer_map_.crbegin().base(), std::make_pair(node->timeout_, std::move(node)));return it->second;}
}

• 我们的延时任务通过 timer_map_ 进行管理，添加延时任务其实就是将延时任务放进 timer_map_ 中进行管理，我们的每一个延时任务都需要被处理，被添加以后我们如何去进行处理就需要使用到回调函数，将回调函数作为 TimerNode 的第二个结点的原因也在这儿，我们可以更为直接的对延时任务进行处理；
• 对于延时任务，我们以当前时间+延时时间，表示延时的时间，在这儿进行添加的时候我们就需要注意，我们添加的延时任务不一定是按顺序排布的，但是红黑树这个结构肯定是按顺序进行排布的，所以添加的延时任务时我们就可以进行优化，如果对应的添加的延时任务的延时时间是小于红黑树最后一个节点的，我们调用 insert 函数插入，因为要重新进行排序，如果对应的添加的延时任务的延时时间是大于红黑树最后一个节点的，我们直接找到尾结点，调用 emplace_hint 函数直接构造一个节点即可，这样是可以提高效率的。
• 最终返回值肯定当前的这个延时任务。

删除延时任务

// 删除延时任务
void DelTimeout(TimerNode *node)
{auto it = timer_map_.equal_range(node->timeout_);for (auto iter = it.first; iter != it.second; iter++){if (iter->second == node){timer_map_.erase(iter);break;}}
}

删除延时任务应该注意的地方就在同一时间我们可能会插入多个延时任务，那么再删除的时候就应该将这个时间点对应的已经处理的延时任务删除，就使用到了 equal_range 这个接口，他用于在有序范围内查找等于给定值的所有元素的范围。它返回一个 std::pair，其中 first 指向第一个不小于给定值的元素，second 指向第一个大于给定值的元素。刚好适用于当前场景。

获取延时时间

// 获取延时时间
int WaitTime()
{auto iter = timer_map_.begin();if (iter == timer_map_.end()){return -1;}uint64_t diff = iter->first - GetCurrentTime();return diff > 0 ? diff : 0;
}

获取延时时间其实就是获取到当前延时任务的一个时间，这个就不多做解释了。

处理延时任务

// 处理延时事件
void HandleTimeout()
{auto iter = timer_map_.begin();while (iter != timer_map_.end() && iter->first <= GetCurrentTime()){iter->second->callback_();iter = timer_map_.erase(iter);}
}

处理我们对应的延时任务，就是调用对应的回调函数，处理完成以后将这个延时任务删除就可以了。

整体代码如下：

#ifndef __TIMER__
#define __TIMER__#include <map>
#include <functional>
#include <chrono>// TimerNode 结点，延时任务
class TimerNode
{
public:friend class Timer;TimerNode(uint64_t timeout, std::function<void()> cb): timeout_(timeout), callback_(std::move(cb)){}private:// int id_;uint64_t timeout_;               // 什么时候触发std::function<void()> callback_; // 异步任务，回调函数
};class Timer
{
public:static uint64_t GetCurrentTime(){using namespace std::chrono;return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();}// 添加延时任务TimerNode *AddTimeout(uint64_t diff, std::function<void()> cb){// 根据 diff 创建延时任务auto node = new TimerNode(GetCurrentTime() + diff, std::move(cb));if (timer_map_.empty() || node->timeout_ < timer_map_.rbegin()->first){auto it = timer_map_.insert(std::make_pair(node->timeout_, std::move(node)));return it->second;}else{auto it = timer_map_.emplace_hint(timer_map_.crbegin().base(), std::make_pair(node->timeout_, std::move(node)));return it->second;}}// 删除延时任务void DelTimeout(TimerNode *node){auto it = timer_map_.equal_range(node->timeout_);for (auto iter = it.first; iter != it.second; iter++){if (iter->second == node){timer_map_.erase(iter);break;}}}// 获取延时时间int WaitTime(){auto iter = timer_map_.begin();if (iter == timer_map_.end()){return -1;}uint64_t diff = iter->first - GetCurrentTime();return diff > 0 ? diff : 0;}// 处理延时事件void HandleTimeout(){auto iter = timer_map_.begin();while (iter != timer_map_.end() && iter->first <= GetCurrentTime()){iter->second->callback_();iter = timer_map_.erase(iter);}}private:std::multimap<uint64_t, TimerNode *> timer_map_; // 前面代表超时时间，后面代表超时任务// std::unordered_map<int, TimerNode *> map_; // id与延时任务对应的关系Timer() = default;Timer(const Timer &) = delete;Timer &operator=(const Timer &) = delete;Timer(Timer &&) = delete;Timer &operator=(Timer &&) = delete;~Timer(){for (auto &pair : timer_map_){delete pair.second;}}
};#endif

当前定时器存在一个可以优化的点，就在于我们需要让他能够全局被进行使用，不希望每次不同对象去使用都去进行创建，在这里可以将他设置成为单例的，提供给全局进行使用，优化后代码如下：

#ifndef __TIMER__
#define __TIMER__#include <map>
#include <functional>
#include <chrono>// TimerNode 结点，延时任务
class TimerNode
{
public:friend class Timer;TimerNode(uint64_t timeout, std::function<void()> cb): timeout_(timeout), callback_(std::move(cb)){}private:// int id_;uint64_t timeout_;               // 什么时候触发std::function<void()> callback_; // 异步任务，回调函数
};class Timer
{
public:// 单例模式static Timer* GetInstance(){static Timer instance;return &instance;}static uint64_t GetCurrentTime(){using namespace std::chrono;return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();}// 添加延时任务TimerNode *AddTimeout(uint64_t diff, std::function<void()> cb){// 根据 diff 创建延时任务auto node = new TimerNode(GetCurrentTime() + diff, std::move(cb));if (timer_map_.empty() || node->timeout_ < timer_map_.rbegin()->first){auto it = timer_map_.insert(std::make_pair(node->timeout_, std::move(node)));return it->second;}else{auto it = timer_map_.emplace_hint(timer_map_.crbegin().base(), std::make_pair(node->timeout_, std::move(node)));return it->second;}}// 删除延时任务void DelTimeout(TimerNode *node){auto it = timer_map_.equal_range(node->timeout_);for (auto iter = it.first; iter != it.second; iter++){if (iter->second == node){timer_map_.erase(iter);break;}}}// 获取延时时间int WaitTime(){auto iter = timer_map_.begin();if (iter == timer_map_.end()){return -1;}uint64_t diff = iter->first - GetCurrentTime();return diff > 0 ? diff : 0;}// 处理延时事件void HandleTimeout(){auto iter = timer_map_.begin();while (iter != timer_map_.end() && iter->first <= GetCurrentTime()){iter->second->callback_();iter = timer_map_.erase(iter);}}private:std::multimap<uint64_t, TimerNode *> timer_map_; // 前面代表超时时间，后面代表超时任务// std::unordered_map<int, TimerNode *> map_; // id与延时任务对应的关系Timer() = default;Timer(const Timer &) = delete;Timer &operator=(const Timer &) = delete;Timer(Timer &&) = delete;Timer &operator=(Timer &&) = delete;~Timer(){for (auto &pair : timer_map_){delete pair.second;}}
};#endif

这就是当前整个定时器的设计，他主要就是用来去处理延时任务的，当我们需要处理大量延时任务的时候，使用定时器就会比较合适。