1.2.C++项目：仿mudou库实现并发服务器之时间轮的设计

一、为什么要设计时间轮？

（一）简单的秒级定时任务实现：

在当前的高并发服务器中，我们不得不考虑⼀个问题，那就是连接的超时关闭问题。我们需要避免⼀个连接长时间不通信，但是也不关闭，空耗资源的情况。
这时候我们就需要⼀个定时任务，定时的将超时过期的连接进行释放。

（二）Linux提供给我们的定时器：

1.原型

#include 
int timerfd_create(int clockid, int flags);
	clockid: CLOCK_REALTIME-系统实时时间，如果修改了系统时间就会出问题； 
	CLOCK_MONOTONIC-从开机到现在的时间是⼀种相对时间；
	flags: 0-默认阻塞属性
	
	int timerfd_settime(int fd, int flags, struct itimerspec *new, struct itimerspec *old);
	fd: timerfd_create返回的⽂件描述符
	flags: 0-相对时间， 1-绝对时间；默认设置为0即可.
	new： ⽤于设置定时器的新超时时间
	old： ⽤于接收原来的超时时间
	struct timespec {
	time_t tv_sec; /* Seconds */
	long tv_nsec; /* Nanoseconds */
};
	struct itimerspec {
	struct timespec it_interval; /* 第⼀次之后的超时间隔时间 */
	struct timespec it_value; /* 第⼀次超时时间 */
};
定时器会在每次超时时，⾃动给fd中写⼊8字节的数据，表⽰在上⼀次读取数据到当前读取数据期间超时了多少次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.例子

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
int main()
{
/*创建⼀个定时器 */
int timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
	struct itimerspec itm;
    itm.it_value.tv_sec = 3;//设置第⼀次超时的时间
	itm.it_value.tv_nsec = 0;
	itm.it_interval.tv_sec = 3;//第⼀次超时后，每隔多⻓时间超时
	itm.it_interval.tv_nsec = 0;
	timerfd_settime(timerfd, 0, &itm, NULL);//启动定时器
	/*这个定时器描述符将每隔三秒都会触发⼀次可读事件*/
	time_t start = time(NULL);
	while(1) {
	    uint64_t tmp;
	 /*需要注意的是定时器超时后,则描述符触发可读事件，必须读取8字节的数据，保存的是⾃上*/
	     int ret = read(timerfd, &tmp, sizeof(tmp));
	    if (ret < 0) {
	     return -1;
		}
	  std::cout << tmp << " " << time(NULL) - start << std::endl;
	 }
	  close(timerfd);
	
	 return 0;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

二、时间轮

（一）思想

上述的例子，存在⼀个很大的问题，每次超时都要将所有的连接遍历一遍，如果有上万个连接，效率无疑是较为低下的。
这时候大家就会想到，我们可以针对所有的连接，根据每个连接最近⼀次通信的系统时间建立⼀个小根堆，这样只需要每次针对堆顶部分的连接逐个释放，直到没有超时的连接为止，这样也可以大大提高处理的效率。
上述方法可以实现定时任务，但是这里给大家介绍另⼀种方案：时间轮
时间轮的思想来源于钟表，如果我们定了⼀个3点钟的闹铃，则当时针走到3的时候，就代表时间到了。

同样的道理，如果我们定义了一个数组，并且有一个指针，指向数组起始位置，这个指针每秒钟向后走动一步，走到哪里，则代表哪里的任务该被执行了，那么如果我们想要定一个3s后的任务，则只需要将任务添加到tick+3位置，则每秒中走一步，三秒钟后tick走到对应位置，这时候执行对应位置的任务即可。
但是，同一时间可能会有大批量的定时任务，因此我们可以给数组对应位置下拉一个数组，这样就可以在同一个时刻上添加多个定时任务了。

（一）代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 /*定时任务类*/
using TaskFunc = std::function<void()>;
// 它是一个使用 std::function 模板类实现的函数指针。
//这里的函数指针是指可以指向任意函数的指针类型，其参数类型为 void()，表示该函数不接受任何参数，返回类型为 void。
using ReleaseFunc = std::function<void()>; 
 
class TimeTask {
    private:
        uint64_t _id;  // 定时器任务对象
        uint64_t _timeout; // 定时任务的超时时间
        bool _canceled;     // false-表示没有被取消， true-表示被取消
        TaskFunc _task_cb;  // 定时器对象要执行的定时任务
        ReleaseFunc _release; //用于删除TimerWheel中保存的定时器对象信息
    public:
        // 1.构造函数
        TimeTask(uint64_t id,uint32_t delay,const TaskFunc &cb) : _id(id),_timeout(delay),_task_cb(cb) {}
        // 2.析构函数
         ~TimerTask() { 
            if (_canceled == false) _task_cb(); 
            _release(); 
        }
        void Cancel() { _canceled = true; }
        void SetRelease(const ReleaseFunc &cb) { _release = cb; }
        uint32_t DelayTime() { return _timeout; }
};

class TimeWheel {
    private:
        using WeakTask = std::weak_ptr<TimeTask>; 
    // std::weak_ptr 是 C++11 标准库中引入的一种智能指针，
    // 它提供了对指针所指向对象的弱引用。当弱引用超出作用域或者对象被销毁时，
    // 智能指针会自动设置为 nullptr，从而避免了悬空指针（dangling pointer）的问题。
        using PtrTask = std::share_ptr<TimeTask>;
        std::vector<std::vector<PtrTask>> _wheel;
        int _tick; // 当前的秒针
        int _capacity; // 表盘最大数量 ——其实就是最大延迟时间
        std::unordered_map<uint64_t,WeakTask> _timers;
    private:
        void RomoveTimer(uint64_t id) {
            auto it = _timers.find(id);
            if (it != _timers.find(id)) {
                _timers.arase(it);
            }
        }
    public:
        Wheel() _capacity(60),_tick(0),_wheel(_capacity) {}
        
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using TaskFunc = std::function<void()>;
using ReleaseFunc = std::function<void()>;
class TimerTask{
    private:
        uint64_t _id;       // 定时器任务对象ID
        uint32_t _timeout;  //定时任务的超时时间
        bool _canceled;     // false-表示没有被取消， true-表示被取消
        TaskFunc _task_cb;  //定时器对象要执行的定时任务
        ReleaseFunc _release; //用于删除TimerWheel中保存的定时器对象信息
    public:
        TimerTask(uint64_t id, uint32_t delay, const TaskFunc &cb): 
            _id(id), _timeout(delay), _task_cb(cb), _canceled(false) {}
        ~TimerTask() { 
            if (_canceled == false) _task_cb(); 
            _release(); 
        }
        void Cancel() { _canceled = true; }
        void SetRelease(const ReleaseFunc &cb) { _release = cb; }
        uint32_t DelayTime() { return _timeout; }
};

class TimerWheel {
    private:
        using WeakTask = std::weak_ptr<TimerTask>;
        using PtrTask = std::shared_ptr<TimerTask>;
        int _tick;      //当前的秒针，走到哪里释放哪里，释放哪里，就相当于执行哪里的任务
        int _capacity;  //表盘最大数量---其实就是最大延迟时间
        std::vector<std::vector<PtrTask>> _wheel;
        std::unordered_map<uint64_t, WeakTask> _timers;
    private:
        void RemoveTimer(uint64_t id) {
            auto it = _timers.find(id);
            if (it != _timers.end()) {
                _timers.erase(it);
            }
        }
    public:
        TimerWheel():_capacity(60), _tick(0), _wheel(_capacity) {}
        void TimerAdd(uint64_t id, uint32_t delay, const TaskFunc &cb) {
            PtrTask pt(new TimerTask(id, delay, cb));
            pt->SetRelease(std::bind(&TimerWheel::RemoveTimer, this, id));
            int pos = (_tick + delay) % _capacity;
            _wheel[pos].push_back(pt);
            _timers[id] = WeakTask(pt);
        }
        //刷新/延迟定时任务
        void TimerRefresh(uint64_t id) {
            //通过保存的定时器对象的weak_ptr构造一个shared_ptr出来，添加到轮子中
            auto it = _timers.find(id);
            if (it == _timers.end()) {
                return;//没找着定时任务，没法刷新，没法延迟
            }
            PtrTask pt = it->second.lock();//lock获取weak_ptr管理的对象对应的shared_ptr
            int delay = pt->DelayTime();
            int pos = (_tick + delay) % _capacity;
            _wheel[pos].push_back(pt);
        }
        void TimerCancel(uint64_t id) {
            auto it = _timers.find(id);
            if (it == _timers.end()) {
                return;//没找着定时任务，没法刷新，没法延迟
            }
            PtrTask pt = it->second.lock();
            if (pt) pt->Cancel();
        }
        //这个函数应该每秒钟被执行一次，相当于秒针向后走了一步
        void RunTimerTask() {
            _tick = (_tick + 1) % _capacity;
            _wheel[_tick].clear();//清空指定位置的数组，就会把数组中保存的所有管理定时器对象的shared_ptr释放掉
        }
};

class Test {
    public:
        Test() {std::cout << "构造" << std::endl;}
        ~Test() {std::cout << "析构" << std::endl;}
};

void DelTest(Test *t) {
    delete t;
}

int main()
{
    TimerWheel tw;

    Test *t = new Test();

    tw.TimerAdd(888, 5, std::bind(DelTest, t));

    for(int i = 0; i < 5; i++) {
        sleep(1);
        tw.TimerRefresh(888);//刷新定时任务
        tw.RunTimerTask();//向后移动秒针
        std::cout << "刷新了一下定时任务，重新需要5s中后才会销毁\n";
    }
    tw.TimerCancel(888);
    while(1) {
        sleep(1);
        std::cout << "-------------------\n";
        tw.RunTimerTask();//向后移动秒针
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

一个时间轮写的我都要痛苦死了。。。
呜呜呜呜谁能救救我。。。。。。。。