一、定时器应用

心跳检测/周期任务
倒计时/超时机制

对于服务端而言，驱动服务端的事件主要有两种：网络事件、定时事件。

不同的框架中，这两种事件有不同的实现方式：

第一种：网络事件和时间事件在一个线程中配合使用。如：Nginx、Redis；

第二种：网络事件和时间事件在不同线程中处理。如skynet。

// 第一种：
while (!quit) {
    time_t now = time(NULL);
    int timeout = get_nearest_timer() - 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 *p) {
    init_timer();
    while (!quit) {
        update_timer();  // 更新定时器，并处理时间事件或把时间事件发送到MQ
        sleep(t);        // t要小于时间精度
    }
    clear_timer();
    return NULL;
}

二、定时器设计

1. 接口设计

// 初始化timer
void init_timer();

// 添加timer
Node *add_timer(int expire, callback cb);

// 删除timer
bool del_timer(Node *node);

// 找到最近的定时任务
Node *find_nearest_timer();

// 更新timer
void update_timer();

// 清除timer
void clear_timer();

2. 实现方式

红黑树
最小堆
跳表
时间轮

待确认

实现方式	增删查	查找最小节点	应用场景
RBTree	O(log2^N)	O(log2N)	Nginx Redis
MinHeap	增查：O(log2N) 删：O(N) ，可通过辅助数据结构（hash table）快速定位节点，加快删除操作	O(1)	常用？
SkipList	O(log2N) 空间复杂度O(1.5N)	O(1)
时间轮	O(1)	O(1)	Linux内核

2.1 红黑树

这里需要和STL的map区分，因为这里可能存在相同的key，而map的key是唯一的。可以考虑使用multimap，也可以自己实现。

nginx中的实现如下：

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 ( ;; ) {
        // 注意：key相同时，p选择right
        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);
}

2.2 最小堆

完全?叉树：若?叉树的深度为 h ，除了 h 层外，其他层的节点数都是该层所能容纳节点的最?
数量（满?2^n），且 h 层都集中在最左侧；

最小堆特性：
? 1. 是?颗完全?叉树；
? 2. 某?个节点的值总是?于等于它的?节点的值；
? 3. 堆中每个节点的?树都是最?堆；

增加节点步骤：

? ? ? ? 为了满足完全二叉树特性，把新增的节点放到最后的位置，然后考虑是否需要上升。如添加“4”，4为5的左子树，4<5 需要上升。

删除节点步骤：

? ? ? ?删除前需要查询节点是否存在，最小堆的查询效率是O(n)，查询到节点后，把该节点和最后一个节点交换位置，先考虑下降操作，如果操作失败则考虑上升操作，最后删除最后一个节点。

如删除“1”，首先1和3交换，3和2交换，再删除末尾节点；

如删除“9“，首先9和3交换，3不能下沉了，考虑上升操作，3和7交换。

2.3 时间轮

单层时间轮

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

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

作为对?：我们假设使? map<int, conn*> 来存储所有连接数；每秒检测 map 结构，那么每秒需
要遍历所有的连接，如果这个map结构包含?万条连接，那么我们做了很多?效检测；考虑极端
情况，刚添加进来的连接，下?秒就需要去检测，实际上只需要10秒后检测就?了；那么我们考
虑使?时间轮来检测；

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

TODO