网络编程中定时器的实现

发表于

在网络编程中，往往涉及到定时器的使用。很多程序员甚至把定时器实现的机制作为评判一个网络库或者服务器的一个重要考察点。

这篇博文就分析两个项目的定时器实现，第一个是zaver，第二个是muduo。

zaver的实现

zaver是一个很小的项目，笔者阅读代码觉得不错。实现计时器的原理为，使用一个优先队列，按照过期时间排序，把计时任务都加入到队列中，每次epoll去poll的时候，先查看队列中最早过期的任务剩余时间为多少，再把这个时间作为poll的超时时间。

在主线程中的while循环如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* epoll_wait loop */
while (1) {
    // (bt)找到最早过期的计时器，返回剩余的时间，如果没有则返回0
    time = zv_find_timer();
    debug("wait time = %d", time);
    // (bt) time参数为 0相当于非阻塞, -1为阻塞
    n = zv_epoll_wait(epfd, events, MAXEVENTS, time);
    // (bt) 和nginx一样，先处理超时，后处理events
    zv_handle_expire_timers();
    
    for (i = 0; i < n; i++) {
        //handle events
    }
}

优先队列其实就是堆，分为最大堆，最小堆，两者都可以理解为二叉树。最大堆根节点为最大元素，最小堆根节点为最小元素。

最小优先队列实现几个接口insert，delmin，min，这三个接口是最关键的。其中堆的删除和插入会涉及到上滤和下滤。比如delmin即把根节点干掉，之后需要把最小二叉树重新调整平衡；insert操作是把元素插入到堆的最后一个位置上，之后需要重新调整最小树的平衡。

muduo的实现

muduo的实现有人吐槽，也有人夸奖。它把定时器交给内核管理，利用linux内核提供的timerfd_create接口创建定时器。

muduo中定义了TimerQueue类作为定时器的封装。初始化时候，通过linux的API创建timerfd。定义一个timers来存储timer，这个timers的存储结构是std::Set，元素是std::pair<Timestamp, Timer *>，添加定时器则往timers添加。

如何获取超时任务呢？比如在now这个Timerstamp点上，获取超时的定时器。getExpired函数的实现如下：

1
2
3
4
5
6
std::vector<Entry> expired;
Entry sentry(now, reinterpret_cast<Timer*>(UINTPTR_MAX));
TimerList::iterator end = timers_.lower_bound(sentry);
assert(end == timers_.end() || now < end->first);
std::copy(timers_.begin(), end, back_inserter(expired));
timers_.erase(timers_.begin(), end);

其中lower_bound函数用来获取比now大的迭代器。函数最后返回expired这个vector。muduo使用linux的API创建定时触发可读的timerfd，fd触发时调用handleRead函数，该函数调用getExpired获取超时定时器，并且逐一执行。在muduo的注释中也有一句wake up loop by timerfd_settime()。

总结

muduo使用的是set存储定时器，set是默认排序的，最早超时的会在最前面，即set.begin()为最早超时的定时器。

zaver使用的是最小优先队列即最小堆来存储定时器，zaver自己实现了优先队列，min接口会返回最早超时的定时器。

从效率上来说，红黑树删除插入的时间复杂度都是O(logN)，最小优先队列的时间复杂度也为O(logN)，所以两者没有太多区别。

可以看到用c去实现一些东西会存在自己造轮子的问题，优先队列在c++的STL已经有priority_queue这个类实现。