一、网络风波和时间风波
对于服务端来说，驱动服务端逻辑的风波主要有两个，⼀个是⽹络风波，另⼀个是时间风波；
在不同框架中，这两种风波有不同的实现⽅式；
第⼀种，⽹络风波和时间风波在⼀个线程当中配合使⽤；诸如nginx、redis；
第⼆种，⽹络风波和时间风波在不同线程当中处理；诸如skynet；
第一种
// 第⼀种
while (!quit) {
int now = get_now_time();// 单位：ms
int timeout = get_nearest_timer() - now;
if (timeout < 0) timeout = 0;
int nevent = epoll_wait(epfd, ev, nev, timeout);
for (int i=0; i<nevent; i++) {
//... ⽹络事件处理
}
update_timer(); // 时间事件处理
}通过epoll_wait中的timeout进行定时操作。并且因为可能会遭到网路风波处理中网路影响，致使前面update_timer()时间风波处理出现比较大的偏差（没有这么准时）。
遭到网路影响，定时器的偏差较大，怎么解决？
通过定时讯号，发送讯号的方法提早打断epoll_wait，之后尽早执行我们的定时器风波update_timer()(nginx就是采用这些技巧)
第二种
// 第⼆种 在其他线程添加定时任务
void* thread_timer(void * thread_param) {
init_timer();
while (!quit) {
update_timer(); // 更新检测定时器，并把定时事件发送到消息队列中
sleep(t); // 这⾥的 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）、最小堆(libevent、go、libev等大部份)、时间轮（netty、kafka、skynet）
三、红黑树
在黑红树中，如何解决相同的时间的key？
例如插入时间为7，这么就可以插入左侧(也就是说，假如定时器的时间相等的话，定时风波后加入的就后触发)（nignx中定时器就是这样实现的）
四、最小堆
最小堆也可以用一个链表来表示，链表的第一个数永远是最小的。
它的效率要比黑红树高如何安装LINUX，最小堆不一定要保证是一个有序的结构，只须要父节点大于子节点就好了。
黑红树的降低和删掉的节点的时间复杂度为O(logN)，查找最小的节点时间为O(H),其中H为黑红树高度
最小堆的降低和删掉节点的时间复杂度也为O(logN)，查找最小的节点时间为O(1)
最小堆的是一种AVL树，左右子树高度差不超过1，因而降低和删掉节点的时间更具有稳定性，而黑红树没有最小堆如此稳定。而且最小堆的查找最小节点的时侯复杂度仅有O(1)。因而大部份定时器，都用最小堆来做。
最小堆和黑红树一般用在单线程，时间轮用在多线程(缘由在本文最后)
相关视频推荐
黑红树、最小堆、时间轮、跳表多种方法实现定时器
基于黑红树，现场手撕高效定时器模块，打算好linux开发环境
学习地址：C/C++Linux服务器开发/后台构架师【零声教育】-学习视频教程-腾讯课堂
须要C/C++Linux服务器构架师学习资料加qun812855908获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，解释器，DPDK，ffmpeg等），免费分享
五、时间轮
1、单层级时间轮
用于实现时间窗口（如tcp滑动窗口）的限流与熔断
假定检查5秒内是否有100次操作
限流：每秒都查看近来五秒是否有100次操作
熔断：每过五秒查看这五秒有没有100次操作
显而易见的，限流愈发确切，而且很花费时间，熔断没这么确切，并且相对来说没这么历时间
熔断的应用：
DDos功击：
顾客端不断发送大量数据给服务器的过程为DDos功击
解决办法：
在网路底层用DPDK判定
在应用层用熔断机制判定规定时间内顾客端发送的数据包是否小于最大上限
为何要使用时间轮？
案例：脉搏检查：
顾客端每5秒钟发送脉搏包；服务端若10秒内没收到脉搏数据，则去除联接；
实际在开发过程中linux端口映射，若收到不仅脉搏包的其他数据，脉搏检查也算通过，在这是为了简化流程，只判定脉搏包；作为对⽐：我们假定使⽤map来储存所有联接数；每秒检查map结构linux c++定时器，这么每秒须要遍历所有的联接，假如这个map结构包含⼏万条联接，这么我们做了好多⽆效检查；考虑极端情况，刚添加进来的联接，下⼀秒就须要去检查，实际上只须要10秒后检查就⾏了；这么我们考虑使⽤时间轮来测量
上图的时间轮大小为8，时间精度为秒
定时风波哪些时侯要触发？
时间轮链表每位索引对应一串数组，每位节点就是要触发的定时时间，当时间轮指针指到该索引时，该数组下的时间都要触发。
将定时风波插入到时间轮中那个位置呢？
假定时间轮的宽度为8(也就是链表的宽度)
在时间轮指针为5的时侯加入了一个新的联接，这么它上次的测量的时间为(5+10)%8=7，在时间轮字段索引为7的时侯，进行测量。
这样就不须要每秒遍历所有的联接了，可以降低运算量。并且这样子一直存在问题，由于10s检查一次，索引为5的时侯加入的，但是过了2秒又要检查，因而仍然会检查到未超时的任务，浪费估算量。因而要求时间的宽度要小于测量时间间隔(在这儿，也就是10秒)
时间轮大小应当取2的n次方>测量时间间隔
时间轮（字段）宽度为何要2的n次方呢？
这就涉及取余操作原理的实现了，有乘法还有下取整，倘若是2的n次方,可以直接替换成位运算，来提升运算速率
也就是说，16大小的时间轮对于5来说，5=5
可以写成5&(16-1)=5
16写成2补码为1111,五写为二补码为0101，也就是说小于等于16的数，就会被控制在0~15内，实现取余的疗效。
时间轮设置太大有哪些后果？
会出现踏空(空推动)的情况，在时间轮中，风波会显得很稀疏，好多对应索引下，没有定时器风波。精度由1s设置成1ms也会导致空推动现象。
怎么解决空推动问题？
(空推动是分布式定时器必需要解决的问题，可以通过最小堆+时间轮解决,通过最小堆让时间轮的表针直接跳到下一个要触发定时器风波的索引处，防止出现空推动的现象（或则使用多层级时间轮）
假如定时任务，时间跨径非常大，几微秒的，几个小时的，几天的定时任务，该如何处理呢？
单层级时间轮无法解决，会出现好多空推动的问题。因而要使用多层级时间轮,例如将近来几秒要触发的置于第一层，几分钟的置于第二层，几小时的置于第三层…
2、多层级时间轮
例如当前时针的表针在2处,钟面的表针在0处，下一个时间定时器在61秒后触发，因为61》=60，因而floor((2+61)/60)=1,
于是置于钟面的索引为1处的地方。（同时数组中的节点还记录着时间，2+61=63）
当时针表针经过58秒后，时针指向0，钟面往前联通一格，为1。这时侯，将时针指向的定时器风波，映射到第一级时间轮(秒)上面，还有3秒，因而放在时针索引为(63-60=3)处。当再经过3秒，分针表针指向3，该定时风波触发
(红色箭头指的是，该索引处用数组储存的定时器，时间范围)
因为将近来要处理的风波装入第一级时间轮中，因为风波密集，可以防止空加快的现象。
在实际的代码中linux c++定时器，不须要记录，钟面的表针和分针的表针，只有一个tick，范围是0~43200。
由于都可以通过tick进行算下来。
按前面的反例，可以晓得，不仅第一级时间轮，0号位置是有数据的，并且第二级，第五级一般是没有数据的，为何这些开源框架中，0号位置都有数据呢？
哪些情况下，最后一层的0号索引有数据呢？
tick的范围是(0~43199由于(60*60*12=43200)）
由于tick不能始终加到无穷大（假如能加到无穷大，在0号位置就不会有值）
例如刚开始时针指向2，其他表针都指向0。要经过43199秒，这么(2+43199)%43200=1
因而，此时数据放到，第三层的索引0号处。(秒针的位置为秒针当前的位置+floor(x/3600))
多线程环境为何使用时间轮？
涉及锁的力度，黑红树和最小堆都是O(logN),要对整个结构进行加锁，锁的力度比较大，会锁太久。
由于降低定时器和测量定时器都是O(1)，不管定时任务有多少。
