本文共 3385 字，大约阅读时间需要 11 分钟。

目录

---

1、定时器概述

对于服务端来说，驱动服务端逻辑的事件主要有两个，⼀个是⽹络事件，另⼀个是时间事件；

在不同框架中，这两种事件有不同的实现⽅式；

• 第⼀种，⽹络事件和时间事件在⼀个线程当中配合使⽤；例如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);  //利用epoll_wait来实现定时器 for (int i=0; i

// 第⼆种 在其他线程添加定时任务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);

2、定时器设计

2.1、接⼝设计

// 初始化定时器void init_timer();// 添加定时器，经过expire时间之后执行回掉函数cbNode* add_timer(int expire, callback cb);// 删除定时器bool del_timer(Node* node);// 找到最近要发⽣的定时任务Node* find_nearest_timer();// 更新检测定时器void update_timer();

2.2、数据结构选择

2.2.1、红⿊树

对于增删查，时间复杂度为 ；对于红⿊树最⼩节点为最左侧节点，时间复杂度为 ；

2.2.2、最⼩堆

对于增查，时间复杂度为 ；对于删时间复杂度为 ，但是可以通过辅助数据结构（map或者hashtable来快速索引节点）来加快删除操作；对于最⼩节点为根节点，时间复杂度为O(1)；

2.2.3、跳表

对于增删查，时间复杂度为 ；对于跳表最⼩节点为最左侧节点，时间复杂度为O(1) ；但是空间复杂度⽐较⾼，为 O(n)；

2.2.4、时间轮

对于增删查，时间复杂度为O(1)；查找最小节点也为O(1)；

要点

1. 有序的结构，且增加删除操作不影响该结构有序；
2. 能快速查找最⼩节点；
3. 时间轮增加操作只从单个定时任务触发，忽略定时任务之间的⼤⼩关系；⽽红⿊树、最小堆、跳表的有序性依赖定时任务之间的大小关系；

2.3、红黑树实现定时器

void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel){ ngx_rbtree_node_t **p; for ( ;; ) { // 这⾥是重点 p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) ? &temp->left : &temp->right; if (*p == sentinel) { break; } temp = *p; } *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; ngx_rbt_red(node);}

STL中 map 结构采⽤的是红⿊树来实现，但是定时器不要使⽤ map 结构来实现，因为可能多个定 时任务需要同时被触发， map 中的key是惟⼀的； 红⿊树的节点同时包含 key 和 val ，红⿊树节点的有序由 key 来决定的；插⼊节点的时候，通 过⽐较key来决定节点存储位置；红⿊树的实现并没有要求 key 唯⼀；如上代码示例， for 循环中 (node->key - temp->key) < 0)? &temp->left : &temp->right; 当key相同的时候取值 为 temp->right ；定时器可以采用改造后的红黑树来实现。

2.4、最小堆实现定时器

满二叉树：所有的层节点数都是该层所能容纳节点的最大数量（满足；n>=0）;

完全二叉树：若二叉树的深度为h，则除了h层外，其余层的节点数都是该层所能容纳节点的最大数量（满足；n>=0）,且h层都集中在最左侧。

最小堆：

1. 是一颗完全二叉树
2. 某一个节点的值总是小于等于它的子节点的值
3. 堆中每个节点的子树都是最小堆

增加操作

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

删除操作

例如：假设删除1号节点，则需要下沉操作；假设删除9号节点，则需要上升操作；

2.5、时间轮实现定时器

从时钟表盘出发，如何⽤数据结构来描述秒表的运转；

int seconds[60]; // 数组来描述表盘刻度；++tick % 60; //每秒钟 ++tick 来描述秒针移动；对tick%60让秒针永远在[0,59]间移动； 对于时钟来说，它的时间精度（最⼩运⾏单元）是1秒；

2.5.1、单层级时间轮

背景

⼼跳检测：

客户端每 5 秒钟发送⼼跳包；服务端若 10 秒内没收到⼼跳数据，则清除连接；

实际在开发过程中，若收到除了⼼跳包的其他数据，⼼跳检测也算通过，在这⾥为了简化流程，只判断⼼跳包；

作为对⽐：我们假设使⽤ map<int, conn*> 来存储所有连接数；每秒检测 map 结构，那么每秒需要遍历所有的连接，如果这个map结构包含⼏万条连接，那么我们做了很多⽆效检测（当心跳包发送了之后10秒后采取检测心跳包收没收到，过早检测也没啥用）；考虑极端情况，刚添加进来的连接，下⼀秒就需要去检测，实际上只需要10秒后检测就⾏了；那么我们考虑使⽤时间轮来检测；

注意：这个例⼦只是⽤来帮助理解时间轮，不代表实际解决⽅案；

设计

1. 准备⼀个数组存储连接数据；那么数组⻓度设置为多少？
2. 考虑一秒内添加多条连接，那么可以参考hash处理冲突的方式，用链表链接起来；
3. 回到1中的问题，如果想2中链表稀疏，将数组长度设置大一些；如果想紧凑些，则将数组长度设置小一点（但是必须大于10，因为我们的规则是10秒内没收到数据则清除连接）
4. 假设我们设置数组长度为11,，那么检测指针的移动可以描述为++point % 11；m%n = m - n * floor(m/n)   //floor函数是向下取整   ；我们可以优化为：m%n = m & (n-1)
5. 考虑到正常情况下5秒种发送一次心跳包，10秒才检测一次，如下图到索引为10的时候并不能踢掉连接；所以需要每收到一次心跳包则used++，没检测一次used--；当检测到used==0，则踢掉连接。

2.5.2、多层级时间轮

参照时钟表盘的运转规律，可以将定时任务根据触发的紧急程度，分布到不同层级的时间轮中；

假设时间精度为10ms；在第1层级每10ms移动一格；每移动一格执行该格子当前所有的定时任务；

当第1层指针从255格开始移动，此时层级2移动一格；层级2移动一格的行为定义为将该格中的定时任务重新映射到层级1中；同理，层级2中从63开始移动，层级3格子中的定时任务重新映射到层级2；以此类推。

如何重新映射？定时任务的过期时间对上一层级的长度取余分布在上一层级的不同格子当中；

当层级1移动到255时，然后再走一下就是回到0，而对应的第二层级前进一下，以此类推即可。

转载地址：http://xjngz.baihongyu.com/