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

### 1.目录：

- 一、如何组织定时任务？
- 定时器收网络IO处理造成误差特别大，该怎么处理？
- 用何种数据机构存储定时器？
- 红黑树如何解决相同时间的key值的？
- 最小堆
- 时间轮
- 一个帮助理解单层级时间轮的例子
- 如何解决空推进的问题？
- 为什么多线程使用时间轮
- 设计哪些接口，如何设计？
- 满足哪些条件才能作为定时器的数据结构？
- 二、定时的方法有哪些？
- 究竟什么是定时？
- 三、总结

### 2.如何组织定时任务？

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

```
int event=epoll_wait(epfd,ev,nev,timeout);
```

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

### 3.定时器收网络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;
}
```

### 4.用何种数据机构存储定时器？

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

![img](https://linuxcpp.0voice.com/zb_users/upload/2022/12/15/20221215165314_38616.jpg)

### 5.红黑树如何解决相同时间的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;
}
```

### 6.最小堆

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

![img](https://linuxcpp.0voice.com/zb_users/upload/2022/12/15/20221215165315_76657.jpg)

- 某个节点:x
- 左子树索引:2x+1
- 右子树索引:2x+2
- 父节点索引:floor((x-1)/2)

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

### 7.时间轮

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

![img](https://linuxcpp.0voice.com/zb_users/upload/2022/12/15/20221215165316_76587.jpg)

- 限流:动态的，5秒内有100次操作，换句话说一秒一秒的移动，限制在100次的操作。单层级时间轮就是实现的限流这个操作。更精确，但是
- 熔断:静态的，5秒测一次，5秒测一次的感觉。

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

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

![img](https://linuxcpp.0voice.com/zb_users/upload/2022/12/15/20221215165316_49767.jpg)

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

- 5表示当前时间。
- 10表示检测周期。
- 8表示连接数。

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

### 9.如何解决空推进的问题？

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

### 10.为什么多线程使用时间轮

多线程要加锁，条件反射第一反应是锁的粒度。增加删除节点的时间复杂度都是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();
```

### 11.满足哪些条件才能作为定时器的数据结构？

- 能够快速找到这个节点，增加和删除。
- 能够快速找到最小节点。

### 12.定时的方法有哪些？

#### 12.1究竟什么是定时？

定时是指在一段时间后欻某段代码的机制，我们可以利用这段代码有条不紊的处理所有到期的定时器。定时机制是定时器得以比处理的原动力。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高性能服务器编程》。

### 13.总结

通过零声学院Mark老师精彩的讲述定时器，让小生在定时器这个方面有了新的认识和突破，给鄙人领入了新的世界，开启了新的大门。
想想曾经，小可只沉溺于Qt中的QTimer类，就像一个烂醉如泥的懒汉，终日沉迷于花天酒地，只知开(颠)开(鸾)心(倒)心(凤)的酣畅，却不知阳春白雪正在向自己告别。虽然能够完成简单的任务，但是却从来没有发现其中藏着如此多的秘密。
现在的我，更像是一个满身泥泞，刚刚从大海中登陆抢滩的战士。
在Mark老师吹响嘹亮的冲锋号声中，尽管前进的道路上充满荆棘坎坷，但是为了胜利和尊严，不惜一切代价，奋勇争先。
**生命不息，战斗不止**

原文链接：https://zhuanlan.zhihu.com/p/495173977

作者：[Hu先生的Linux](https://www.zhihu.com/people/huhu520-10)