时间轮

为什么使用时间轮

基于链表排序的定时器使用唯一的一条链表来管理所有定时器，插入操作的效率随着定时器数目的增多而降低。

时间轮使用哈希表的思想，将定时器散列到不同的链表上，这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。

时间轮的原理

时间轮可以理解为一种环形结构，像钟表一样被分为多个 slot 槽位。每个 slot 代表一个时间段，每个 slot 中可以存放多个任务，使用链表结构保存该时间段到期的所有任务。时间指针随着时间增加逐个slot 转动，并执行 slot 中的所有到期任务。

任务如何加入

根据任务的到期时间进行取模，将任务分布到不同的 slot 中。如图所示，时间轮被划分为 8 个 slot，每个 slot 代表 1s，当前时针指向 2。

假如现在需要调度一个 3s 后执行的任务，应该加入 2+3=5 的 slot 中；如果需要调度一个 12s 以后的任务，需要等待时针完整走完一圈 round 后再走 4 个 slot，需要放入第 (2+12)%8=6 个 slot。

当时针走到第 6 个 slot 时，怎么区分每个任务是立即执行，还是需要等待下一圈，甚至更久时间之后执行呢？因此需要把 round 信息保存在任务中。

例如图中第 6 个 slot 的链表中包含 3 个任务，第一个任务 round=0，需要立即执行；第二个任务 round=1，需要等待 1*8=8s 后执行；第三个任务 round=2，需要等待 2*8=8s 后执行。所以当时针转动到对应 slot 时，只执行 round=0 的任务，slot 中其余任务的 round 应当减 1，等待下一个圈之后执行。

定时器类

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class tw_timer 
{
public:
    tw_timer(int rot, int ts)
        : rotation(rot), time_slot(ts), next(nullptr), prev(nullptr) {}
private:
    int rotation;   /* 记录定时器在时间轮转多少 round 后生效 */
    int time_slot;  /* 记录定时器属于时间轮上哪个 slot*/
    void* user_data = nullptr;  /* 客户数据 */
    void (*cb_func)(void* );    /* 定时器回调函数 */

    tw_timer* next; /* 指向下一个定时器 */
    tw_timer* prev; /* 指向前一个定时器 */
};

多级时间轮