写点什么

后端开发【一大波干货知识】定时器方案红黑树,时间轮,最小堆

  • 2022 年 4 月 08 日
  • 本文字数:3126 字

    阅读完需:约 10 分钟

目录:

  • 一、如何组织定时任务?

  • 定时器收网络 IO 处理造成误差特别大,该怎么处理?

  • 用何种数据机构存储定时器?

  • 红黑树如何解决相同时间的 key 值的?

  • 最小堆

  • 时间轮

  • 一个帮助理解单层级时间轮的例子

  • 如何解决空推进的问题?

  • 为什么多线程使用时间轮

  • 设计哪些接口,如何设计?

  • 满足哪些条件才能作为定时器的数据结构?

  • 二、定时的方法有哪些?

  • 究竟什么是定时?

  • 三、总结

一、如何组织定时任务?

首先,定时器组件通常和网络组件一起工作。举个最简单的例子来说:

int event=epoll_wait(epfd,ev,nev,timeout);
复制代码

timeout 作为参数值,<0 为一直阻塞,=0 相当于非阻塞检测双端队列就绪情况 0 代表立刻返回,>0 数值表示最长阻塞的时间。在时间上需要应对的问题填入 epoll_wait 函数,就可以兼顾网络事件的处理和定时任务的处理。

定时器收网络 IO 处理造成误差特别大,该怎么处理?

  • nginx,redis 中通过定时信号去处理+epoll_wait 解决,nginx_timer_revolusion()函数定时发送时间信号会打断 epoll_wait()的处理,让它尽快的处理定时事件,从而解决了误差较大的问题。很明显,如果网络 IO 处理事件时,会造成一定的误差。定时任务事件处理=epoll_wait 处理时间+网络事件处理时间。

//第一种:通过发送定时信号去打断epoll_wait函数while(!quit){  int now=get_now_time();//单位:ms  int timeout=get_nearest_time()-now;  if(timeout<0)      timeout=0;  int nevent=epoll_wait(epfd,ev,nev,timeout);  for(int i=0;i<nevent;i++)  {      //网络事件处理  }  update_timer();、//时间事件处理}
复制代码

单独开启一个线程,去处理定时任务。

//第二种:再其他线程添加定时任务void* thread_timer(void * thread_param){  init_timer();  while(!quit)  {      update_timer();      sleep(t);  }  clear_timer();  return nullptr;}
复制代码

用何种数据机构存储定时器?

考虑这个问题要清楚,越近要触发的事件优先级越高。定时器存在的意义是处理延时任务,具体来说比如:定期检测客户连接状态,心跳检测,技能冷却 CD,倒计时,定时广播,界面实时刷新等等。

红黑树如何解决相同时间的 key 值的?

大家知道,stl::map 和 stl::set 是内部都是采用红黑树实现的,并没有要求 key 值一定要不同、

int find_nares_expire_timer(){        ngx_rbtree_node_t *node;        if(timer.root==&sentinel){            return -1;    }    node=ngx_rbtree_min(timer.root,timer.sentinel);    int diff=(int)node->key-(int)current_time();    return diff>0 ? diff :0;}
复制代码

最小堆

最小堆是堆排序中一个子的流程,最小堆是一个完全二叉树(其他叶子节点都是满的,而最深的节点叶子都是靠在最左侧),用数组组织其中的元素。与用链表表示堆相比,数组表示堆不仅节省空间,而且更容易实现堆的插入、删除等操作。


  • 某个节点:x

  • 左子树索引:2x+1

  • 右子树索引:2x+2

  • 父节点索引:floor((x-1)/2)

需要注意的是:最小堆只关注父子的大小,不关注兄弟的大小。增加节点只有上升操作,删除节点有上升和下降,个人理解不管是删除还是增加,都是要先对树进行操作,而后维护树的正常秩序。红黑树和最小堆的增删都是 O(logn),在查找最小的就节点方面红黑树是 O(logh),最小堆是 O(log1),很明显最小堆比红黑树更加我稳定一些。

C++后台开发系统学习地址:C/C++Linux服务器开发高级架构师/C++后台开发架构师​

以下学习资料,C++后台开发面试题,教学视频,C++后台开发学习路线图,免费分享有需要的可以自行添加:学习资料群720209036 进去自取

时间轮

crontab 是 linux 的定时服务,它就是用时间轮实现的。与红黑树和最小堆不同的是,时间轮是多线程环境下使用的。tcp 的滑动窗口就是时间窗口的概念,这就是是单层级时间轮的实现。


  • 限流:动态的,5 秒内有 100 次操作,换句话说一秒一秒的移动,限制在 100 次的操作。单层级时间轮就是实现的限流这个操作。更精确,但是

  • 熔断:静态的,5 秒测一次,5 秒测一次的感觉。

一个帮助理解单层级时间轮的例子

在客户端给服务器发送心跳的这个过程中,老师举例客户端可能五秒发一次服务器十秒检测一次,如果没有收到心跳就会踢除连接。检测是否有过期连接的方法有两种:一种是每一个连接启动一个定时器,另一种是将所有的连接存放在 map<int,connect *>中,用一个定时器去检测上万个连接,因为有很多是新上来的连接,每秒去检测肯定是有很多次浪费的检测。要设计单层级时间轮要从两个方面考虑:一个是检测间隔时间的大小,另一个是时间轮的精度。

​公式:(5+10)/8=7

  • 5 表示当前时间。

  • 10 表示检测周期。

  • 8 表示连接数。

计算机内部取余操作 m%n=m-n*floor(m/n),x%16=x &(16-1)。时间轮根本就不怕任务多,任务越多越好。

如何解决空推进的问题?

  • kafka 利用的是最小堆+单层级时间轮

  • 多层级时间轮

为什么多线程使用时间轮

多线程要加锁,条件反射第一反应是锁的粒度。增加删除节点的时间复杂度都是 O(log1),所以锁的粒度是最小的。上面也说到,红黑树和最小堆的时间复杂度都是 O(logn),所以都使用时间轮。设计哪些接口,如何设计?笔者认为,分析定时器该如何设计,当有新设计需求时完全可以借用此模式,所以是有必要用心学的。

//初始化定时器void init)timer();//添加定时器Node * add_timer(int expire,callback cb);//删除定时器bool del_timer(Node* node);//找到最近发生的定时任务Node* find_nearest_timer();//清除定时器void clear_timer();
复制代码

满足哪些条件才能作为定时器的数据结构?

  • 能够快速找到这个节点,增加和删除。

  • 能够快速找到最小节点。

二、定时的方法有哪些?

究竟什么是定时?

定时是指在一段时间后欻某段代码的机制,我们可以利用这段代码有条不紊的处理所有到期的定时器。定时机制是定时器得以比处理的原动力。Linux 有三种定时方法:

  • socket 选项 SO_RCVTIMEO 和 SO_SNDTIMEO。

  • SIGALARM 信号。

  • I/O 复用系统调用的超时参数。(上文提到的 epoll_wait())。

socket 选项的 SO_RCVTIMEO 和 SO_SNDTIMEO 是用来设置 socket 几首数据和发送数据超时时间的。send,sendmsg,rcv,recvmsg,accept 和 connect 等系统调用都可以设置这个选项,根据这些系统调用的返回值以及 errno 来判断超时时间是否一道,然后去处理超时任务。

SIGALARM 信号是当 alarm()和 settimer()函数设置实时闹钟时被触发,然后我们利用这个信号的信号处理函数来处理定时任务。定时周期 T 反应了定时的精度,如果某个定时任务的超时时间不是 T 的整数倍,那么它实际被执行的时间和恶预期的时间将略有偏差。

Linux 下的三组 I/O 复用系统调用都带有超时参数,因此不仅能统一处理信号和 I/事件,也能同意处理定时事件。值得注意的是:I/O 复用系统调用可能在超时时间到期内就返回(I/O 事件发生)。如果我们要利用它们来定时,就需要不断的更新定时参数以反映剩余的时间。

更多的细节内容还要细致的研读游双先生的《Linux 高性能服务器编程》。

三、总结

通过零声学院 Mark 老师精彩的讲述定时器,让小生在定时器这个方面有了新的认识和突破,给鄙人领入了新的世界,开启了新的大门。

想想曾经,小可只沉溺于 Qt 中的 QTimer 类,就像一个烂醉如泥的懒汉,终日沉迷于花天酒地,只知开(颠)开(鸾)心(倒)心(凤)的酣畅,却不知阳春白雪正在向自己告别。虽然能够完成简单的任务,但是却从来没有发现其中藏着如此多的秘密。

现在的我,更像是一个满身泥泞,刚刚从大海中登陆抢滩的战士。

在 Mark 老师吹响嘹亮的冲锋号声中,尽管前进的道路上充满荆棘坎坷,但是为了胜利和尊严,不惜一切代价,奋勇争先。

生命不息,战斗不止

参考资料

推荐一个零声教育 C/C++后台开发的免费公开课程,个人觉得老师讲得不错,分享给大家:C/C++后台开发高级架构师,内容包括Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

用户头像

Linux服务器开发qun720209036,欢迎来交流 2020.11.26 加入

专注C/C++ Linux后台服务器开发。

评论

发布
暂无评论
后端开发【一大波干货知识】定时器方案红黑树,时间轮,最小堆_定时器_Linux服务器开发_InfoQ写作平台