定时器方案，红黑树，时间轮

定时器应用

心跳检测 、技能冷却、 倒计时 、其他需要延时处理的功能

定时器触发方式

对于服务端来说，驱动服务端业务逻辑的事件包括网络事件、 定时事件、以及信号事件；通常网络事件和定时事件会进行协同处理；定时器触发形式通常有两种：

1 网络事件和定时事件在一个线程中处理；例如：nginx、 redis、memcached；

     定时任务比较少的时候。

     对于多线程情况，引起时间处理不均衡。

     任务多了，会影响网络事件处理。

2 网络事件和定时事件在不同线程中处理；例如： skynet，...；

     usleep(time)  time要小于最小时间精度

    通常采用的数据结构是  时间轮

    加锁粒度比较小

    时间轮只负责检测，通过信号或者插入执行队列让其他线程处理。

// 网络事件和定时事件在一个线程中处理
while (!quit) {
    int timeout = get_nearest_timer() - now();
    if (timeout < 0) timeout = -1;
    int nevent = epoll_wait(epfd, ev, nev,
timeout);
    for (int i=0; i
        // ... 处理网络事件
   }
    // 处理定时事件
    update_timer();
}
// 网络事件和定时事件在不同线程中处理
void * thread_timer(void *thread_param) {
    init_timer();
    while (!quit) {
        update_timer();
        sleep(t);
   }
    clear_timer();
    return NULL;
}
pthread_create(&pid, NULL, thread_timer,
&thread_param);

定时器设计

接口设计

// 初始化定时器 void init_timer();

// 添加定时器 Node* add_timer(int expire, callback cb);

// 删除定时器 bool del_timer(Node* node);

// 找到最近要触发的定时任务 Node* find_nearest_timer();   // 只有第一种情况才需要

// 更新检测定时器 void update_timer();

// 清除定时器   void clear_timer();

数据结构设计

对定时任务的组织本质是要处理对定时任务优先级的处理；由此产生两类数据结构；

按触发时间进行顺序组织

要求数据结构有序（红黑树、跳表），或者相对有序 （最小堆）；

能快速查找最近触发的定时任务；

需要考虑怎么处理相同时间触发的定时任务；

按执行顺序进行组织

时间轮

红黑树

绝对有序 ， nginx

跳表  

绝对有序，redis未来会引用跳表

最小堆

满二叉树：所有的层节点数都是该层所能容纳节点的最大数量 （满足 )

完全二叉树：若二叉树的深度为 h，去除了 h 层的节点，就是 一个满二叉树；且 h 层都集中在最左侧排列；

最小堆：

是一颗完全二叉树；

某一个节点的值总是小于等于它的子节点的值；

堆中任意一个节点的子树都是最小堆；

libevent,libev

为了满足完全二叉树的定义，往二叉树最高层沿着最左侧添加 一个节点；然后考虑是否能上升操作；如果此时添加值为 4 的 节点，4 节点是 5 节点的左子树；4 比 5 小，4 和 5 需要交换 值；

最小堆删除节点

删除操作需要先查找是否包含这个节点；确定存在后，交换最后一个节点，先考虑能否执行下降操作，否则执行上升操作； 最后删除最后一个节点； 例如：删除 1 号节点，则需要下沉操作；删除 9 号节点，则需要上升操作；

时间轮

为什么要分成多个层级： 

1 减少空间占用   

2 只需要关注最近要触发的定时任务      最近一分钟

3 按照任务触发的轻重缓急进行组织

4 减少任务的检测

tick

取值范围为时间范围，只需要记录一个指针，当秒针移动一圈，说明下一分钟的任务要进行了。

任务节点

expire , callback , next （解决相同触发时间的任务）

添加节点

根据time判断放在哪一层， expire = tick0 + time

重新映射

当分针的任务移动到秒针层级时

为什么需要重新映射?        时间精度为秒，只执行秒针层级的任务。

怎么重新映射：

1 确定重新映射的位置(算出分针的指针位置）   tick    |      (tick/60)%60

2 取出该指针指向槽位的所有任务

3 time = tick0 + time - tick

4 再添加节点的逻辑。

删除节点

1 节点位置可能发生变化

2 添加一个字段，cancel = true ，任务触发时遇到这个标记不执行具体任务

时间轮场景

内核 ，skynet , kafka , netty

 运行图

 原理图

#include 
#include 
#include 
#include 
#include 
#include 
 
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; // 如果时间相同，根据id的先后顺序执行
	};
};
bool operator < (const TimerNodeBase& lhd , const TimerNodeBase& rhd){// std::less<> 需要
	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::steady_clock::now());
		auto temp = chrono::duration_cast(sc.time_since_epoch());
		return temp.count();
	}
	TimerNodeBase AddTimer(time_t msec , TimerNode::Callback func){
		time_t expire = GetTick() + msec;
		auto ele = timermap.emplace(GenID() , expire , func);
		return static_cast(*ele.first);
	}
	bool DelTimer(TimerNodeBase& node){
		auto iter = timermap.find(node); // c++14新特性， 传一个相似值  ， 基类引用
		if(iter != timermap.end()){
			timermap.erase(iter);
			return true;
		}
		return false;
	}
	bool CheckTimer(){      // 检查是否有定时事件
		auto iter = timermap.begin();
		if(iter != timermap.end() && iter->expire <= GetTick()){ // 时间到了
			iter->func(*iter);  // 执行任务
			timermap.erase(iter);
			return true;
		}
		return false;
	}
	time_t TimeToSleep(){
		auto iter = timermap.begin();
		if(iter == timermap.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> timermap;
};
int64_t Timer::gid = 0;
 
int main(){
	int epfd = epoll_create(1);
 
	unique_ptr timer = make_unique();
	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;
	struct epoll_event ev[64] = {0};
	while(true){
		/*
            -1 永久阻塞
            0 没有事件立刻返回，有事件就拷贝到 ev 数组当中
            t > 0  阻塞等待 t ms， 
            timeout  最近触发的定时任务离当前的时间
        */
        int n = epoll_wait(epfd, ev, 64, timer->TimeToSleep());
		for (int i = 0; i < n; i++) {
		/*网络事件处理*/
		}
		/* 处理定时事件*/
		while(timer->CheckTimer());  
	}
	return 0;
}