手撕定时器：从零开始

1. 定时器概述

1.1 容器

1.2 检测触发机制

2. 定时任务的执行

2.1 异步执行

2.2 触发时间

2.3 回调函数

3. 定时任务的容器结构

3.1 按触发时间排序的结构

3.1.1 红黑树（如 map、set、multimap、multiset）

3.1.2 最小堆

3.2 按执行序排列的结构：时间轮（Timing Wheel）

4. 检测和触发机制

4.1 基于IO多路复用的检测

4.1.1 阻塞时间

4.1.2 应用实例

4.2 timerfd

4.2.1 将定时任务转化为IO

4.2.2 Workflow

4.3 解决的核心问题

4.3.1 阻塞与调度

4.3.2 内核级检测

5. 定时器的实现

5.1 封装

5.2 实现

5.2.1 容器

5.2.2 检测触发机制

5.3 测试

5.4 优化

5.4.1 针对大量间隔时间相同的任务的优化

5.4.2 拆分思想

5.5 代码实践

5.5.1 epoll_wait第4个参数驱动

1. 定义基本定时器节点

2. 定义定时器节点

3. 定义比较运算符

4. 定义定时器类

5. 添加定时器

6. 删除定时器

7. 处理定时器

8. 计算休眠时间

9. ID 生成器

10. 主函数

11. 添加定时任务

12. 删除定时任务

13. 进入事件循环

总结

1. 定时器概述

定时器是用于管理和调度大量定时任务的模块。其核心组件包括容器和检测触发机制。

1.1 容器

容器负责组织和存储所有的定时任务。高效的容器结构能够支持快速插入、删除和查找任务，确保系统在处理大量定时任务时依然高效。

1.2 检测触发机制

检测触发机制的主要职责是监控定时任务，及时触发即将到期的任务。它需要具备高效的查找和调度能力，以确保最近要触发的任务能够被优先处理。

2. 定时任务的执行

2.1 异步执行

定时任务通常是异步执行的，这意味着它们不会阻塞主线程或过度占用线程资源。通过异步机制，可以在任务触发时高效地执行回调函数，而不影响系统的整体性能。

2.2 触发时间

每个定时任务都有一个触发时间，通常由当前时间加上一个间隔时间计算得出。这确保了任务在预定的时间点被准确地执行。

2.3 回调函数

当定时任务被触发时，会执行预先定义的回调函数。这些回调函数可以执行各种操作，如处理数据、发送通知或执行其他业务逻辑。

3. 定时任务的容器结构

选择合适的数据结构来存储和管理定时任务对于定时器的性能至关重要。以下是常见的几种容器结构：

3.1 按触发时间排序的结构

3.1.1 红黑树（如 `map`、`set`、`multimap`、`multiset`）

红黑树是一种自平衡的二叉查找树，能够在对数时间内进行插入、删除和查找操作。它适用于需要频繁动态调整任务的场景。

优点：

动态性强，适合频繁添加和删除任务。
可以快速查找最早要触发的任务。

缺点：

相比其他数据结构，内存占用可能更高。

3.1.2 最小堆

最小堆是一种优先队列，能够在常数时间内找到最小元素（即最早触发的任务），并在对数时间内进行插入和删除操作。

优点：

插入和删除操作效率高。
适合需要快速访问最早任务的场景。

缺点：

不支持高效的中间元素查找和删除。

3.2 按执行序排列的结构：时间轮（Timing Wheel）

时间轮是一种基于环形数据结构的定时器实现，适用于处理大量定时任务，尤其是那些具有相似触发时间间隔的任务。

优点：

内存和计算效率高，适合处理高并发定时任务。
能够以恒定时间复杂度处理任务。

缺点：

实现相对复杂。
对于长时间间隔的任务，可能需要多级时间轮。

4. 检测和触发机制

4.1 基于IO多路复用的检测

IO多路复用（如 select、poll、epoll）允许在单线程中同时处理多个IO事件。定时任务的检测可以集成到IO多路复用的机制中，通过设置一个超时参数来实现。

4.1.1 阻塞时间

当没有网络事件时，IO多路复用函数会阻塞等待一定时间。这段阻塞时间可以设置为当前时间到最近要触发任务的时间间隔，确保在任务到期前能够被及时唤醒。

4.1.2 应用实例

Redis 和 Nginx 等高性能服务器广泛使用这种机制来高效地处理网络和定时任务。

4.2 `timerfd`

timerfd 是 Linux 提供的一种机制，将定时器事件转化为文件描述符，可以与IO多路复用机制无缝集成。

4.2.1 将定时任务转化为IO

通过 timerfd_create 创建一个定时器文件描述符，并将定时任务的触发时间设置到该文件描述符上。这样，IO多路复用就可以监控定时任务的触发，统一处理网络和定时事件。

4.2.2 Workflow

创建 timerfd 并设置触发时间。
将 timerfd 添加到 IO 多路复用的监控列表中。
当定时器到期时，IO 多路复用会检测到 timerfd 的可读事件，触发相应的回调函数。

4.3 解决的核心问题

主要解决从当前时间到最近要过期任务的时间节点之间，当前线程如何高效处理的问题。

4.3.1 阻塞与调度

通过阻塞当前线程，释放执行权，让操作系统调度其他任务。这可以避免线程在等待过程中浪费资源。

4.3.2 内核级检测

将定时任务的检测需求交给内核，当前线程可以继续执行其他操作。当内核检测到定时任务到期时，通知当前线程进行处理。这种方式能够提高系统的整体效率和响应速度。

5. 定时器的实现

5.1 封装

定时器的封装通常涉及将定时器的功能模块化，以便在不同的上下文中重用。封装的目标是提供一个简洁的接口，使用户能够方便地创建和管理定时任务。

封装的要点：

接口设计：定义清晰的API，包括任务的添加、删除、启动和停止等功能。
内部实现：将容器和检测机制的具体实现细节隐藏在封装内部，用户只需关注如何使用接口。
错误处理：确保在任务添加或执行过程中能够处理异常情况，提供必要的错误反馈。

5.2 实现

5.2.1 容器

在实现中选择合适的容器结构是关键。可以结合前面提到的红黑树、最小堆和时间轮等结构。具体选择可以基于任务特性和性能需求。

示例结构：

红黑树：适用于需要频繁动态插入和删除的任务。
最小堆：适合任务量较大时快速访问最近要触发的任务。
时间轮：适合处理大量具有相似触发时间间隔的任务。

5.2.2 检测触发机制

实现检测触发机制时，可以采用 IO 多路复用和 timerfd 等技术来高效监控定时任务的触发。确保机制能够及时响应即将到期的任务。

实现思路：

使用 IO 多路复用来等待定时器和其他IO事件。
当定时器到期时，通过回调函数处理任务。

5.3 测试

测试是验证定时器实现是否符合预期的重要环节。可以进行以下类型的测试：

单元测试：针对各个模块（如容器、检测机制）进行单元测试，确保其功能正确。
集成测试：测试定时器的整体功能，包括任务的添加、执行和删除。
性能测试：在高并发和高任务量的情况下测试定时器的性能，验证其响应时间和资源使用情况。

5.4 优化

随着系统负载的增加，定时器的性能可能会受到影响，因此需要考虑优化策略。

5.4.1 针对大量间隔时间相同的任务的优化

在大量定时任务的情况下，可以考虑使用 insert_hint 技术，从 O(log n) 优化到 O(1)。

具体实现：

在任务添加时，可以通过维护一个指向合适插入位置的指针，减少不必要的比较和移动操作。
在插入相同触发时间的任务时，可以直接将任务插入到指针指向的位置，从而降低复杂度。

5.4.2 拆分思想

拆分思想可以有效提升定时器的性能，特别是在高并发场景中。

实现方式：

单线程多容器：在单个线程中使用多个容器来处理不同类型或优先级的定时任务。可以避免一个容器中任务的增加导致性能瓶颈。
多线程多容器：在多线程环境中，每个线程维护自己的容器和检测机制，这样可以并行处理任务，提高整体处理能力。

综合效果：

减少单个容器和线程的负载，提高系统的响应速度。
通过合理的任务分配和资源调度，优化资源利用率，提升系统整体性能。

5.5 代码实践

5.5.1 epoll_wait第4个参数驱动

#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;
};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;}
};bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) {if (lhd.expire < rhd.expire)return true;else if (lhd.expire > rhd.expire) return false;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();}TimerNodeBase AddTimer(time_t 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);}bool DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if (iter != timeouts.end()) {timeouts.erase(iter);return true;}return false;}void HandleTimer(time_t now) {auto iter = timeouts.begin();while (iter != timeouts.end() && iter->expire <= now) {iter->func(*iter);iter = timeouts.erase(iter);}}time_t TimeToSleep() {auto iter = timeouts.begin();if (iter == timeouts.end()) {return -1;}time_t diss = iter->expire - GetTick();return diss > 0 ? diss : 0;}
private:static int64_t GenID() {return gid++;}static int64_t gid;set<TimerNode, std::less<>> timeouts;
};
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) {int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());time_t now = Timer::GetTick();for (int i = 0; i < n; i++) {/**/}/* 处理定时事件*/timer->HandleTimer(now);}return 0;
}

1. 定义基本定时器节点

struct TimerNodeBase {time_t expire;int64_t id;
};

TimerNodeBase 结构体存储了定时任务的过期时间和唯一标识符（ID）。

2. 定义定时器节点

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 结构体继承自 TimerNodeBase，并且包含一个回调函数类型 Callback，用于在定时器到期时执行。构造函数初始化过期时间和 ID。

3. 定义比较运算符

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

这个运算符重载用于将 TimerNodeBase 对象进行排序，首先比较过期时间，若相同则比较 ID。这对于在容器中管理定时任务的顺序至关重要。

4. 定义定时器类

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();}

Timer 类的 GetTick 方法返回当前时间的毫秒数。使用 chrono 库可以精确获取系统的当前时间。

5. 添加定时器

TimerNodeBase AddTimer(time_t 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);
}

该方法用于添加定时任务，接收任务的延迟时间（毫秒）和回调函数。
计算出过期时间 expire，如果时间容器 timeouts 为空或者新的过期时间早于容器中最后一个任务的过期时间，则直接添加到容器。
否则，使用 emplace_hint 在适当的位置插入新任务，以提高性能。
返回添加的定时任务的基本信息。

6. 删除定时器

bool DelTimer(TimerNodeBase &node) {auto iter = timeouts.find(node);if (iter != timeouts.end()) {timeouts.erase(iter);return true;}return false;
}

此方法用于删除已存在的定时任务。使用 find 方法查找并删除，如果成功，返回 true。

7. 处理定时器

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

遍历定时任务容器，执行所有已到期的定时任务的回调函数，并将其从容器中移除。

8. 计算休眠时间

time_t TimeToSleep() {auto iter = timeouts.begin();if (iter == timeouts.end()) {return -1;}time_t diss = iter->expire - GetTick();return diss > 0 ? diss : 0;
}

计算下一个定时任务的到期时间，与当前时间的差值，如果没有定时任务，返回 -1，表示可以一直阻塞。

9. ID 生成器

private:static int64_t GenID() {return gid++;}static int64_t gid;set<TimerNode, std::less<>> timeouts;
};int64_t Timer::gid = 0;

生成唯一的 ID，使用静态变量 gid 进行自增。定时任务存储在 set 中，以确保按过期时间自动排序。

10. 主函数

int main() {int epfd = epoll_create(1);unique_ptr<Timer> timer = make_unique<Timer>();

创建一个 epoll 实例，用于事件通知和处理。
使用 unique_ptr 动态分配 Timer 对象。

11. 添加定时任务

    int i = 0;timer->AddTimer(1000, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});

添加多个定时任务，每个任务在 1000 毫秒后触发，打印信息并增加计数。

12. 删除定时任务

    auto node = timer->AddTimer(2100, [&](const TimerNode &node) {cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->DelTimer(node);

添加一个定时任务并立即删除它，确保不会执行。

13. 进入事件循环

    cout << "now time:" << Timer::GetTick() << endl;epoll_event ev[64] = {0};while (true) {int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());time_t now = Timer::GetTick();for (int i = 0; i < n; i++) {/**/}/* 处理定时事件*/timer->HandleTimer(now);}