【高性能定时器】 时间轮

时间轮

简述

顾名思义，时间轮就像一个轮子，在转动的时候外界会指向轮子不同的区域，该区域就可以被使用。因此只要将不同时间的定时器按照一定的方法散列到时间轮的不同槽（即时间轮划分的区域）之中，就可以实现在运转到某个槽时，进行判断该定时器是否已经到达运行时间（需要判断是由于有的定时器并非在这一圈就需要运行，可能需要后面几圈才会运行。

从图中也可以看出，每个槽中的定时器是以（双向）链表形式存储的，每次添加的时候直接插入到链表的开始（头插法）。值得注意的是，由于使用头插法，因此在运行到某个槽时，需要遍历一遍链表，已检查是否有到达时间的计时器，有的话就运行，并删除结点。

至于在每转到一个槽时都要检查是否到达运行时间，可以这样理解：时间轮进行散列的方法就是取余运算，假设每个槽的间隔为1s，共有n个槽，当前转到了第cur个槽，那么一个定时在 t s以后运行的定时器就要放在第（ cur + t % n ） % n个槽，并在运行t / n圈后到达该槽时才会运行。因此一个槽中的定时器运行的时间是相差i（i >= 0）个周期的。

所以时间轮简单来说就是散列 + 链表，这样与使用升序链表相比，散列可以直接定位要插入的槽所在位置，可以提高添加定时器的效率，由O(N)到了O(1)。

对实现时间轮来说，最主要的还是链表的操作是否熟练，当然也主要是双向链表的添加与删除。

代码分析

• 记录定时器的时间信息，从而获取在时间轮中槽的位置，以及在多少圈之后被触发。在定时时间不足槽之间切换的时间时，要将t/n记为1，否则记录t/n的整除结果。

    // timeout为定时时间，SI为槽之间切换的时间
    int ticks;
    if( timeout < SI ) {
        ticks = 1;
    } else {
        ticks = timeout / SI;
    }

    int rotation = ticks / N;  // 被触发的圈数
    int ts = ( cur_slot + ticks % N ) % N;  // 被插入的槽

• 为提高定时器的添加效率，使用头插法，将定时器添加在槽的开始位置。
• 使用双向链表，需要注意将后面的结点的pre指向前一个结点。
• 删除链表时要注意结点是否是第一个结点

代码实现（含注释）

#ifndef _TIMEWHEEL_H_
#define _TIMEWHEEL_H_

#include <time.h>
#include <netinet/in.h>

const int BUFFER_SIZE = 64;

class TwTimer;

// 用户数据，绑定socket和定时器
struct client_data {
    sockaddr_in address;
    int sock_fd;
    char buf[BUFFER_SIZE];
    TwTimer* timer;
};

// 定时器类，时间轮采用双向链表
class TwTimer {
public:
    int rotation;  // 定时器转多少圈后生效
    int time_slot;  // 记录定时器属于时间轮的哪个时间槽
    client_data* user_data;  // 客户数据
    TwTimer* next;  // 指向下一个定时器
    TwTimer* pre;  // 指向上一个定时器
public:
    TwTimer( int rot, int ts ) : rotation(rot), time_slot(ts), next(NULL), pre(NULL) {}
    void (*cb_func)( client_data * );  // 回调函数
};

class TimeWheel {
private: 
    static const int N = 60;  // 槽的数目
    static const int SI = 1;  // 定时器槽之间时间间隔
    TwTimer* slot[ N ];  // 时间轮的槽，指向一个定时器链表，链表无序
    int cur_slot;  // 当前槽
public:
    TimeWheel() : cur_slot(0) {
        for( int i = 0; i < N; i++ ) {
            slot[i] = NULL;
        }
    }

    ~TimeWheel() {
        for( int i = 0; i < N; i++ ) {
            TwTimer* tmp;
            while( tmp = slot[i], tmp ) {
                slot[i] = tmp->next;
                delete tmp;
            }
        }
    }

    TwTimer* add_timer( int timeout );  // 根据定时值创建定时器，并插入槽中
    void del_timer( TwTimer* timer );
    void tick();
};

TwTimer* TimeWheel::add_timer( int timeout ) {
    if( timeout < 0 ) {
        return NULL;
    }

    // 记录多少个tick后被触发，不足最小单位SI的记为1，其余为timeout/SI
    int ticks = 0;
    if( timeout < SI ) {
        ticks = 1;
    } else {
        ticks = timeout / SI;
    }

    int rotation = ticks / N;  // 被触发的圈数
    int ts = ( cur_slot + ticks % N ) % N;  // 被插入的槽
    TwTimer* timer = new TwTimer( rotation, ts );

    // 如果链表为空，则放到头，否则插入到第一个位置
    if( !slot[ts] ) {
        slot[ts] = timer;
    } else {
        timer->next = slot[ts];
        slot[ts]->pre = timer;
        slot[ts] = timer;
    }

    return timer;
}


// 删除定时器
void TimeWheel::del_timer( TwTimer* timer ) {
    if( !timer ) {
        return;
    }

    // 注意链表为双向的
    int ts = timer->time_slot;
    if( timer == slot[ts] ) {
        slot[ts] = slot[ts]->next;
        if( slot[ts] ) {
            slot[ts]->pre = NULL;
        }
    } else {
        timer->pre->next = timer->next;
        if( timer->next ) {
            timer->next->pre = timer->pre;
        }
    }
    delete timer;
}

// SI时间到后，条用该函数，时间轮向前滚动一个槽的间隔
void TimeWheel::tick() {
    TwTimer* tmp = slot[cur_slot];
    while( tmp ) {
        if( tmp->rotation > 0 ) {  // 定时时间未到
            tmp->rotation--;
            tmp = tmp->next;
        } else {  // 定时时间已到
            tmp->cb_func( tmp->user_data );
            if( tmp == slot[cur_slot] ) {  // tmp位于链表首
                slot[cur_slot] = tmp->next;
                if( slot[cur_slot] ) {
                    slot[cur_slot]->pre = NULL;
                }
                delete tmp;
                tmp = slot[cur_slot];
            } else {  // tmp位于链表中
                tmp->pre->next = tmp->next;
                if( tmp->next ) {
                    tmp->next->pre = tmp->pre;
                }
                TwTimer* tmp2 = tmp->next;
                delete tmp;
                tmp = tmp2;
            }
        }
    }
    cur_slot = ( cur_slot + 1 ) % N;
}

#endif