「linux」定时器方案:红黑树、最小堆和时间轮的原理
一、网络事件和时间事件
对于服务端来说，驱动服务端逻辑的事件主要有两个，?个是?络事件，另?个是时间事件；
在不同框架中，这两种事件有不同的实现?式；
第?种，?络事件和时间事件在?个线程当中配合使?；例如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通过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中定时器就是这样实现的）
四、最小堆
最小堆也可以用一个数组来表示，数组的第一个数永远是最小的。
它的效率要比红黑树高，最小堆不一定要保证是一个有序的结构，只需要父节点小于子节点就好了。
红黑树的增加和删除的节点的 时间复杂度为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 秒内没收到心跳数据，则清除连接；
实际在开发过程中，若收到除了心跳包的其他数据，心跳检测也算通过，在这是为了简化流程，只判断心跳包；作为对?：我们假设使? map
上图的时间轮大小为8，时间精度为秒
定时事件什么时候要触发？
时间轮数组每个索引对应一串链表，每个节点就是要触发的定时时间，当时间轮指针指到该索引时，该链表下的时间都要触发。
将定时事件插入到时间轮中哪个位置呢？
假设时间轮的长度为8(也就是数组的长度)
在时间轮指针为5的时候加入了一个新的连接，那么它下次的检测的时间为 (5+10)%8=7，在时间轮数组索引为7的时候，进行检测。
这样就不需要每秒遍历所有的连接了，可以减少运算量。但是这样子仍然存在问题，因为10s检测一次，索引为5的时候加入的，可是过了2秒又要检测，因此依旧会检测到未超时的任务，浪费计算量。因此要求时间的长度要大于 检测时间间隔(在这里，也就是10秒)
时间轮大小应该取 2 的n次方 > 检测时间间隔
时间轮（数组）长度为什么要 2 的n次方 呢？
这就涉及取余操作原理的实现了，有除法还有下取整，如果是 2 的n次方,可以直接替换成位运算，来提高运算速度
?也就是说，16大小的时间轮 对于5来说，5%16=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，该定时事件触发
?(绿色箭头指的是，该索引处 用链表存放的定时器，时间范围)
由于将最近要处理的事件放入第一级时间轮中，由于事件密集，可以避免空推进的现象。
在实际的代码中，不需要记录，分针的指针和时针的指针，只有一个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)%12)
?多线程环境为什么使用时间轮？
涉及锁的力度，红黑树和最小堆都是O(logN),要对整个结构进行加锁，锁的力度比较大，会锁太久。
因为增加定时器和检测定时器都是O(1)，不管定时任务有多少。