一、设计思想

在单线程事件循环中管理延时任务（定时回调），和 epoll_wait 的超时参数配合，实现添加/删除/触发定时器的功能。

1.1 封装操作

• TimerNode：封装一个定时任务（到期时间 + 回调）。实现用裸指针 TimerNode* 管理内存。

• Timer（单例样式）：负责定时器容器和三类核心操作：

  1. AddTimeout(diff, cb)：添加一个在 now+diff 到期的任务，返回 TimerNode* 句柄。
  2. DelTimeout(node)：通过传入的 TimerNode* 删除任务。
  3. WaitTime()：返回距离下一个定时器到期还有多少毫秒（用于 epoll_wait 的 timeout 参数）。
  4. HandleTimeout()：触发并删除所有已到期的任务（执行回调）。

1.2 实现要点

(1）容器

• 使用 std::multimap<uint64_t, TimerNode*> timer_map_：
  • key = 到期时间（毫秒绝对时间）；value = 指向任务的指针。
• 优点：
  • 有序，最早到期元素位于 begin()，获取下一个触发 O(1)。
  • 支持相同到期时间的多个任务（multimap）。
  • 给定迭代器删除（erase(it)) 是 O(1)（但查找迭代器是 O(log n)），整体删除复杂度 O(log n)。

（2）检测/触发机制

• 利用 epoll_wait 的 超时参数：把 WaitTime() 的结果传给 epoll_wait，当超时发生或有 I/O 事件发生时，返回主循环，调用 HandleTimeout() 执行到期任务。

• 优点：实现简单，事件循环只需一个 epoll_wait。

• 注意点：当另一个线程插入了更早的定时器时，如果当前线程在 epoll_wait 阻塞，需要一个唤醒机制（例如 eventfd、pipe 或 timerfd），否则会错过早期触发或等待过久。

• 更稳健的方式是使用 timerfd 把“下一个触发时间”交给内核，timerfd 可直接加入 epoll，且在更新下次到期时可调用 timerfd_settime 来唤醒 epoll。

二、代码实现

2.1 TimerNode 类

class TimerNode {
public:
    friend class Timer;
    TimerNode(uint64_t timeout, std::function<void()> callback)
        : timeout_(timeout), callback_(std::move(callback)) {}
private:
    // int id;
    uint64_t timeout_;
    std::function<void()> callback_;
};

• 作用：保存到期时间和回调。

2.2 GetCurrentTime()

• 使用 steady_clock 的毫秒计数： 使用单调时钟（monotonic）避免系统时间变更影响定时器。

2.3 AddTimeout

TimerNode* AddTimeout(uint64_t diff, std::function<void()> cb) {
    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;
    }
};

• 创建一个新的 TimerNode 并插入到 multimap。为了在大量“尾部插入”的场景下加速，使用 emplace_hint 给出 end() 的 hint（crbegin().base() 通常等价于 end()），可以把插入从 O(log n) 降到接近 O(1)。

• 复杂度：

  • 常规 insert ：O(log n)。
  • 使用 emplace_hint 且 hint 准确（插到末尾）：常见实现可接近 O(1)。

2.4 DelTimeout

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 找到所有与 node->timeout_ 相同键的元素，然后线性遍历这些元素直到找到指针一致的那个并删除。

• 复杂度：O(log n + k)，其中 k 是与该时间戳相等的元素数目（equal_range 的查找是 O(log n)，然后 k 次比较）。

2.5 WaitTime

int WaitTime() {
    auto iter = timer_map_.begin();
    if (iter == timer_map_.end()) {
        return -1;
    }
    
    if (iter->first <= GetCurrentTime()) {
	    return 0;
    }
    
    uint64_t diff = iter->first - GetCurrentTime();
    return diff > 0 ? diff : 0;
}

• 返回距离下一个到期的毫秒数（-1 表示无定时器 -> epoll_wait 无限等待）。

• 注意处理无符号下溢：

  • iter->first 与 GetCurrentTime() 都是 uint64_t。如果 iter->first < now（即已经过期），iter->first - now 会发生无符号下溢，结果是一个很大的正数。随后 diff > 0 成立，函数返回一个巨大的毫秒数（而不是 0），导致 epoll_wait 被误导去睡很久，从而延迟触发。

2.6 HandleTimeout

void HandleTimeout() {
    auto iter = timer_map_.begin();
    while (iter != timer_map_.end() && iter->first <= GetCurrentTime()) {
        iter->second->callback_();
        iter = timer_map_.erase(iter); // 删除已处理的定时器
    }
}

• 从最早到期开始，依次触发回调并从容器中删除。

• 复杂度：设有 m 个已经到期任务，删除每个元素在 RB-tree 中通常为 O(log n)，所以整体 O(m log n)；获取 begin 和比较是 O(1)。

2.7 完整代码

#pragma once

#include <sys/epoll.h>
#include <unistd.h>
#include <map>
#include <functional>
#include <chrono>

class TimerNode {
public:
    friend class Timer;
    TimerNode(uint64_t timeout, std::function<void()> callback)
        : timeout_(timeout), callback_(std::move(callback)) {}
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) {
        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;
	    }
	    
	    if (iter->first <= GetCurrentTime()) {
		    return 0;
	    }
	    
	    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_;

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

int main() {
    int epfd = epoll_create1(0);
    if (epfd == -1) {
        std::cerr << "epoll_create error: " << errno << std::endl;
        return -1;
    }

    Timer timer;

    int i = 0;
    timer.AddTimeout(1000, [&]() {
        std::cout << "Timeout 1 second:" << i++ << std::endl;
    });

    timer.AddTimeout(2000, [&]() {
        std::cout << "Timeout 2 seconds:" << i++ << std::endl;
    });

    auto node = timer.AddTimeout(3000, [&]() {
        std::cout << "Timeout 3 seconds:" << i++ << std::endl;
    });

    timer.DelTimeout(node);

    epoll_event evs[512];

    while (true) {
        int n = epoll_wait(epfd, evs, 512, timer.WaitTime());
        if (n == -1) {
            if (errno == EINTR) {
                continue; // Interrupted by a signal, retry
            }
            std::cerr << "epoll_wait error: " << errno << std::endl;
            break;
        }
        // 处理延时任务
        timer.HandleTimeout();
    }

    return 0;
}

三、定时器的优化策略

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

• emplace_hint：

  • 大量任务按时间单调递增地加入（例如周期任务按时间序列到来），在末尾插入使用 emplace_hint(end(), ...) 可以将插入从 O(log n) 降低到接近 O(1)。

• 同间隔分桶：

  • 把“同一周期/间隔”的任务放在同一链表或桶里。主结构只维护每个桶的下一次到期时间（桶的数量远小于任务数），主结构尺寸下降，插入/删除开销显著降低。

• 时间轮：

  • 对短周期、大并发、重复的定时任务非常高效（平均 O(1)），但牺牲精度（槽宽）并且实现复杂（分层时间轮支持长超时）。

• 保留尾部 hint（last_hint）：

  • 如果你的任务大多数被加入到时间序列末端，可以把上次插入的位置作为 hint，直接调用 emplace_hint(last_hint, ..)。

3.2 基于拆分思想

• 单线程拆分多容器：

  • 把不同功能/不同对象的定时器放到不同的 Timer 容器（例如每个 worker 一个），降低单容器规模，减少竞争。

• 多线程 + 多检测机制：

  • 方案 A：每个 I/O 线程维护自己的定时器队列（无锁或轻锁），这样 epoll_wait + timer 在同一线程内，避免跨线程唤醒开销。

  • 方案 B：一个专门的定时器线程负责触发，将触发事件派发给工作线程（适合集中化策略）。

  • 方案 C：混合：短期/高频任务放时间轮或每线程容器，长超时任务放红黑树或堆。

• 唤醒机制：

  • 在多线程情形下，新增一个比当前最早到期还早的定时器时，必须唤醒 epoll_wait —— 常用方法是 eventfd（写一个事件）或使用 timerfd 并把其加入 epoll，timerfd_settime 可以更新 kernel 的超时并保证唤醒及时。