用时间轮实现定时器

前言

        我们在网络编程中会遇到这样一个场景：我们需要维护大量的TCP连接以进行网络通信，但这些连接中有大量的空闲。我们如何高效地管理这些连接？答案是定时器，我们给每个连接设置定时器来自动管理，规定时间内未进行通信则自动关闭连接。

        但是你应该能很快发现问题，连接数量一多，这些与连接挂钩的定时器也多了，系统的整体性能就会急剧下降，这时候就要请出今天的主角时间轮了。

原理

       时间轮（Timing Wheel）是一种高效的定时器数据结构，广泛用于网络编程、事件驱动编程和操作系统中，用于管理和调度在特定时间点需要执行的任务。它的核心思想是使用一个循环数组（或称为轮子）来存储定时事件，并通过一个指针（或称为“时钟指针”）来跟踪当前时间。

        我们先从时钟入手，我们知道时钟由时针、分针、秒针三部分组成，秒针一圈分针一格，分针一圈时针一格。现在我们将这三个针分开，每个针转一圈都会回到原点。

        我们将其抽象简化成三个数组，把任务按照执行序依次以链表的方式挂在各个槽位，比如有一个36秒的任务，我们就可以计算出它会挂在秒针的第36个槽位上，当秒针指向这个槽位时就会执行这个槽位的任务。这时候你可能疑惑，如果是挂在分针上的任务，那执行逻辑又该如何？这时候就要小心了，当分针走到指定槽位，就需要将槽位上挂载的所有任务重新映射到秒针上，时针也是如此，这样一来，真正的执行者只有秒针数组。

实现思路

       接下来我们一个使用时间轮的定时器。首先来看任务节点，由于我们需要对分针，时针的槽位上的任务重新分配，自然过期时间是必不可少的，回调函数、参数也必不可少，此外，重新分配的机制使节点位置一直在改变致使我们无法删除节点，所以我们添加一个执行字段，等到这个任务启动时通过这个字段判断是否执行此任务。

// 定义定时器节点
class TimerNode {
public:
    std::function<void(TimerNode*)> callback; // 定时器回调函数
    uint32_t expire;                           // 定时器过期时间
    bool cancel;                               // 是否取消定时器
    int id;                                    // 携带参数
};

        节点问题讨论完了，重头戏来了，我们怎么设计时间轮类。前文我们分析了时间轮的由来，既然执行任务都在秒针那一层，分针与时针都需要到点重新分配，我们何不干脆使用两个轮？一个用来执行，一个用于存储。也就是说，我们可以设计一个近程定时器和一个远程定时器。我们将远程定时器分层级来模拟分针和时针，不局限于2个。此外，我们还需要几个成员变量存放当前时间、当前节点，以及一个互斥锁供多线程访问。

        我们还需要几个成员函数：添加任务节点、删除节点（设置执行字段为false）、处理到期的定时任务以及循环推进函数等等。总体设计及解释如下：

#include <stdint.h>
#include<functional>
#include<list>
#include<mutex>

#define TIME_NEAR_SHIFT 8
#define TIME_NEAR (1 << TIME_NEAR_SHIFT)//近程任务
#define TIME_LEVEL_SHIFT 6
#define TIME_LEVEL (1 << TIME_LEVEL_SHIFT)//远程任务
#define TIME_NEAR_MASK (TIME_NEAR-1)
#define TIME_LEVEL_MASK (TIME_LEVEL-1)

struct TimerNode{
    TimerNode*next;
    uint32_t expire;//过期时间
    std::function<void()> callback;//回调函数
    uint8_t cancel;//取消标志
    int id; 
};

struct List{
    TimerNode head;
    TimerNode*tail;
};

class TimerWheel{
public:
    TimerWheel(){

    }
    ~TimerWheel(){

    }

public:
    TimerNode *link_clear(List *list) {
        TimerNode *ret = list->head.next;
        list->head.next = 0;
        list->tail = &(list->head);
        return ret;
    }

    void link(List *list, TimerNode *node) {
        list->tail->next = node;
        list->tail = node;
        node->next = 0;
    }

    void add_node(TimerWheel*T, TimerNode *node) {//添加节点
        uint32_t time = node->expire;
        uint32_t current_time = T->time_;
        uint32_t msec = time - current_time;
        if (msec < TIME_NEAR) {//分层添加任务
            link(&T->near[time & TIME_NEAR_MASK], node);
        } else if (msec < (1 << (TIME_NEAR_SHIFT + TIME_LEVEL_SHIFT))) {
            link(&T->t[0][(time >> TIME_NEAR_SHIFT) & TIME_LEVEL_MASK], node);
        } else if (msec < (1 << (TIME_NEAR_SHIFT + 2 * TIME_LEVEL_SHIFT))) {
            link(&T->t[1][(time >> (TIME_NEAR_SHIFT + TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK], node);
        } else if (msec < (1 << (TIME_NEAR_SHIFT + 3 * TIME_LEVEL_SHIFT))) {
            link(&T->t[2][(time >> (TIME_NEAR_SHIFT + 2 * TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK], node);
        } else {
            link(&T->t[3][(time >> (TIME_NEAR_SHIFT + 3 * TIME_LEVEL_SHIFT)) & TIME_LEVEL_MASK], node);
        }
    }

    void move_list(TimerWheel *T, int level, int idx) {//清除链表并将所有定时器节点重新添加到时间轮中，以便重新分配。
        TimerNode *current = link_clear(&T->t[level][idx]);
        while (current) {
            TimerNode *temp = current->next;
            add_node(T, current);
            current = temp;
        }
    }

    void timer_shift(TimerWheel *T) {//更新时间轮的时间，并在必要时移动远程定时器链表中的定时器。
        int mask = TIME_NEAR;
        uint32_t ct = ++T->time_;
        if (ct == 0) {
            move_list(T, 3, 0);
        } else {
            uint32_t time = ct >> TIME_NEAR_SHIFT;
            int i = 0;
            while ((ct & (mask - 1)) == 0) {
                int idx = time & TIME_LEVEL_MASK;
                if (idx != 0) {//重新分配
                    move_list(T, i, idx);
                    break;
                }
                mask <<= TIME_LEVEL_SHIFT;
                time >>= TIME_LEVEL_SHIFT;
                ++i;
            }
        }
    }
    
    void dispatch_list(TimerNode *current) {//执行链表中的所有定时器节点，并释放它们。
        do {
            TimerNode *temp = current;
            current = current->next;
            if (temp->cancel == 0)
                temp->callback();
            free(temp);
        } while (current);
    }

    void timer_execute(TimerWheel *T) {//执行当前时间点的所有近程定时器。
        int idx = T->time_ & TIME_NEAR_MASK;
        while (T->near[idx].head.next) {
            TimerNode *current = link_clear(&T->near[idx]);
            std::lock_guard<std::mutex> lock(mutex_);
            dispatch_list(current);
        }
    }

    void *timer_update(TimerWheel *T) {//执行所有到期的定时器，并更新时间轮。
        std::lock_guard<std::mutex> lock(mutex_);
        timer_execute(T);
        timer_shift(T);
        timer_execute(T);
    }

    void del_timer(TimerNode *node) {
        node->cancel = 1;
    }

    uint64_t gettime() {//获取当前时间
	    uint64_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
	    struct timespec ti;
	    clock_gettime(CLOCK_MONOTONIC, &ti);
	    t = (uint64_t)ti.tv_sec * 1000;
	    t += ti.tv_nsec / 1000000;
#else
	    struct timeval tv;
	    gettimeofday(&tv, NULL);
	    t = (uint64_t)tv.tv_sec * 100;
	    t += tv.tv_usec / 10000;
#endif
	    return t;
    }

    void expire_timer(void) {//检查是否有定时器已经过期。
        uint64_t cp = gettime();
        //首先获取当前时间，然后与时间轮中记录的最后检查时间 current_point 进行比较。
        //如果当前时间与最后检查时间不同，说明已经过去了一段时间，需要调用 timer_update 函数多次来处理这段时间内的所有过期定时器。
        if (cp != this->current_point_) {
            uint32_t diff = (uint32_t)(cp - this->current_point_);
            this->current_point_ = cp;
            int i;
            for (i=0; i<diff; i++) {
                timer_update(this);
            }
        }
    }

   void clear_timer() {
	    int i,j;
	    for (i=0;i<TIME_NEAR;i++) {
		    List * list = &this->near[i];
		    TimerNode* current = list->head.next;
		    while(current) {
			    TimerNode * temp = current;
			    current = current->next;
			    free(temp);
		    }
		    link_clear(&this->near[i]);
	    }
	    for (i=0;i<4;i++) {
		    for (j=0;j<TIME_LEVEL;j++) {
			    List * list = &this->t[i][j];
			    TimerNode* current = list->head.next;
			    while (current) {
				    TimerNode * temp = current;
				    current = current->next;
				    free(temp);
			    }
			    link_clear(&this->t[i][j]);
		    }
	    }
    }

private:
    List near[TIME_NEAR];//近程任务链表
    List t[4][TIME_LEVEL];//远程任务分四层链表
    std::mutex mutex_;
    uint32_t time_;//当前时间
    uint64_t current_;
    uint64_t current_point_;
};