网络编程中的定时事件

在网络编程中, 定时事件是很关键的一部分, 比如我们作心跳, 检测连接等等任务需求,都是需要定时事件的支持.一般的时间相关任务有:

1. 获取当前时间
2. 时区转换与日期计算
3. 定时操作

一般而言我们经常讲定时器, 实际上定时器是两部分组成的:

1. 定时器
2. 定时器的组织形式

定时器

我们先来了解Linux中支持的时间函数:

计时函数:

• time: C时间函数, time_t格式, 精确到秒 1s
• ftime: struct timeb格式, 精确到毫秒 10^-3s, 1ms
• gettimeofday: struct timeval格式, 精确到微秒, 10^-6s, 1μs
• clock_gettime: struct timespec格式, 精确到纳秒, 10^-9s, 1ns

定时函数:

• sleep(3): 多线程环境, sleep就是个笑话
• alarm(2): 使用信号计时, 参考前一章, 不建议
• usleep(3): 同sleep
• nanosleep(2): 挂起线程有毒
• clock_nanosleep(2): 同上
• getitimer(2)/setitimer(2): 多线程中使用信号麻烦
• timer_create(2)/timer_settime(2)/timer_gettime(2)/timer_delete(2) 可以指定接受方的线程/进程, 但是仍然是信号触发, 信号函数能做的事有限
• timerfd_create(2)/timerfd_gettime(2)/timerfd_settime(2) 建议使用, 统一事件源, 可以将超时事件融入Reactor

我们经过上面的分析, 最后的结论是:

1. 计时操作使用gettimeofday,精度足够, 同时不会陷入内核, clock_gettime因为切换开销大
2. 定时操作使用timerfd*系列函数, 不会直接处理信号, 和读写事件一样方便的处理方式

所以, 我们对于定时器的创建, 便使用下面的三个接口

#include <sys/timerfd.h>
int timerfd_create(int clockid, int flags);
int timerfd_settime(int fd, int flags,
                    const struct itimerspec *new_value,
                    struct itimerspec *old_value);
int timerfd_gettime(int fd, struct itimerspec *curr_value);

timerfd_create

用来创建定时器实例, 参数含义:

• clockid: CLOCK_REALTIME,实际时间. CLOCK_MONOTONIC, 晶振时间/绝对时间, CLOCK_BOOTTIME, 即使系统挂起, 仍然计时, 算是晶振时间的强化版, 超时后还会唤醒
• flags: TFD_NONBLOCK, TFD_CLOEXEC和其他标志基本一致

timerfd_settime

用来进行时间的设置.其中,注意的是new_value和old_value两个参数 用来进行新定时的设置, 和上一个定时的获取

当超时后, timerfd会变的可读就绪

• read(2): 会在fd上读出uint64_t的数据
• poll, selectg, epoll: 和读事件类似,
• ioctl: 同其他fd相同
• close: 在不使用定时器的时候, 可以close文件描述符

timerfd_gettime

用于进行时间的获取, 是个值-结果参数

定时器的组织形式

我们一般在网络编程中提到定时器的时候, 更多的是指这个概念. 那么, 常见的定时器组织形式有这么几种: 无序链表, 排序链表, 最小堆, 时间轮, 平衡树(算是不完整的最小堆, 实现方式上区别)

他们的时间复杂度是这样的:

对于定时器的组织形式, 我们提出的要求是:

• StartTimer: 创建插入定时器
• StopTimer: 停止定时并删除
• TickTimer: 超时执行定时函数

链表

无论是排序链表还是无序链表, 本质都是一样的.

• 将定时器作为节点管理
• 插入/删除/查找时进行遍历判断

模型很容易理解, 对吧? 关键的区别在于时间复杂度上: 1.无序链表: 插入时直接头插O(1), 删除和超时时需要遍历判断定时器情况O(n); 2.有序链表: 采用降序链表, 插入时需要找到合适的位置, 时间复杂度是O(n), 删除和超时, 距今时间最近的定时器节点一定是在起始处, 所以事件复杂度是O(1)

在实现上,推荐有以下两种方式:

1. 使用std::list或者std::forward_list
2. 或者使用<list.h>

避免重复再造轮子, 基本就是链表操作, 配合timerfd*很容易实现, 这里不再赘述. 同时要注意的是: 我们进行定时器操作时, 一般单线程内, 一个timerfd足够, 不断修改时间可

实现方式不再赘述

接下来介绍两种比较不错的定时器管理方式: 最小堆和时间轮

时间堆(最小堆)

最小堆是堆的一种, (堆是一种二叉树), 指的是堆中任何一个父节点都大于子节点, 子节点顺序不作要求 而二插排序树(BST)指的是: 左子树节点小于父节点, 右子树节点大于父节点, 对所有节点适用

那么, 我们选择最小堆形式在于:

1. 最小堆保证最小的节点在顶部, 所以删除, 超时的时间复杂是O(1)
2. 因为最小堆的性质要求, 即使是插入, 平均时间复杂度也是O(lgn)

那么, 最小堆的实现是这样, (本质上最小堆就是优先队列):

• 可以使用数组模拟, 为了扩展性, 可以使用std::vector

重点是两种操作: 上滤和下滤

• 插入: 上滤操作, 首先将节点放在最后, 然后向上移动到合适位置
• 删除: 下滤操作, 删除节点, 将最后节点放在堆顶, 然后向下移动找到合适位置

时间轮

顾名思义, 时间轮就是个轮子, 像钟表一样, 随着指针的移动而指向某一个格子(或 槽).

它如何进行定时器的管理呢?

时间轮提前确定好, 时间的间隔, 在每一个格子就是一个链表(无所谓顺序), 这个链表中的时间都是一致的. 当指针指向当前格子时, 便将所有超时时间直接处理, 并且移除. 就是这么简单

一般的实现方式: 因为都是格子, 而且我们要保证操作的时间复杂度, 一般用数组或者std::vector实现

时间复杂度分析:

• 插入: 数组或者向量, 都支持RandomAccess Iterator, 时间复杂度是O(1)
• 删除: 同上O(1)
• 超时: 同上O(1)

深入分析三种定时器

链表

我们这里不严格区分链表的有无序, 着重分析存在的问题. 优点:

• 操作, 实现简单
• 定时事件较少时, 可获得不错的性能 O(n), O(1), O(1)(以排序链表为例)

缺点:

• 当有大量定时事件时, 就会造成链表过长, 时空开销陡然增长(O(n)不是盖得)

那么, 有没有改进的措施, 勉强算有吧

1. 不同的时间级使用多条链表
2. 可以尝试”静态链表”, 不过另一方面移动开销增加, 失去链表灵活的特点

而且上面的思路发展下去, 不就是时间轮么

最小堆

优点:

• 简单操作, 时间复杂度良好
• 可以同时管理大量的定时事件

缺点: 没有什么特别明显地, 可能是插入的效率比时间轮差吧

时间轮

优点:

• 几种定时器管理方式中, 时间复杂度最低, 性能最好的
• 可以同时管理大量的定时事件

缺点:

• 需要进行严格的设计

时间轮可能存在的问题在于: 精度 控制时间轮的精度是十分重要的问题, 我们在精度控制方面有这样的限制

1. 精度太大, 1s, 2s, 基本别玩了
2. 精度太小, 要不然就是支持的定时区间太短, 要不然就会消耗太多资源

那么我们的修改措施也是存在的:

1. 一定程度程度上可以考虑使用bitmap,虽然可能是平时不常用的数据结构, 不过在空间开销上很小 bitmap也是Bloom Filter的要点之一
2. 使用多级时间轮, (是不是像分页设计的解法一样), 使用多级时间轮也能比较好的解决这个问题

最后,简单说一下muduo, 也是platinum中的定时器, 使用二叉平衡树管理.

事实上二叉平衡树的效率并没有时间堆, 时间轮好

优点在于:

• STL中现成的设施, std::map, std::set,相比与自造数据结构, 健壮性得到保证
• 在并非海量定时事件时, 效率还不错, 并不会成为性能瓶颈

最主要的是: 该项目中本身定时事件一般, 而且是从原来链表的设计修改, 性能完全足够

用chenshuo的话说就是: 可以优化, 但没必要

定时器推荐

最后, 就是我们甄选定时器类型的时候了, 建议如下:

1. 如果定时任务并不多时, 使用链表完全足够, Redis中使用的就是无序链表
2. 如果能够明确组织好时间区间, 即: 时间比较密集, 一定选择时间轮, 最高效的定时器
3. 除上面两种情况以外, 都建议使用时间堆, 其通用性更强, 对定时时间是否密集, 定时任务数量无 明显要求