高性能定时器策略之时间轮定时器算法

时间轮定时器是有多个时间槽(slot)组成，每个时间槽代表时间的基本跨度。类似于一个时钟，时钟指针以恒定的速度每往下走一步，代表一个时间跨度。

时间槽的个数是固定的，用SN(Slot Num)表示，每转动一次可称为一个滴答(tick),所以转动一周也就需要个SN滴答。每一个滴答需要的槽间间隔为SI（Slot Interval），则转一周也就共需要（SN * SI）时间单位。

时间轮的每个槽都指向一个定时器链表，每个链表的定时器都有一个相同的特性：相差（SN * SI）的整数倍，也即是一周的整数倍。正是由于时间轮有这样的特性，所以可以根据定时器的触发时间和时间轮的槽数，把定时器hash到对应的链表上。

一个简单的时间轮如下图：

比如我们要插入一个超时时间为TI的定时器，那么计算器应该插入到槽对应的链表的方式如下：

TS = ( CS + （TI / SI) ) % SN

CS 代表当前的槽位，因为时间轮定时器不停的在走。

时间轮采用的是hash的思想，把各个定时器分散到不同槽的链表中，这个避免了单个链表的过长，提高了效率。

从上面的公式可以看出，对时间轮而言，当SI 越小的时候，定时器的精度就越高；当SN槽数越多时，效率越高，因为定时器被分配到不同的链表中，链表的长度也就相对短了，提高了遍历效率。

下面实现一个简单的时间轮，代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 


#define BUFFER_SIZE  64 //缓冲区长度
#define SLOTS_NUM    60 //时间轮上槽的数目


//结构体声明
typedef struct tw_timer tw_timer;
typedef struct client_date client_date;


/* EPOLL回调函数*/
typedef void (*epoll_ callback_ t)(int, int); 


struct tw_timer{
    int rotation; //记录定时器在时间轮上转多少圈后触发
    int time_slot; //记录定时器属于时间轮上的槽位（对应的链表）
    void (*cb_func)(client_date *); //定时器回调函数
    client_date *user_date; //client数据
    tw_timer *prev;  //指向前一个定时器
    tw_timer *next ;  //指向下一个定时器
};
//用户数据 
struct client_date{
    int sockfd; 
    char buf[BUFFER_SIZE];
    tw_timer *time; 
};


//每1秒时间轮转动一次，也即是槽间隔为1秒
static const int SI = 1;
//时间轮的槽， 其中每个元素指向一个定时器链表,链表无序
tw_timer *slots[SLOTS_NUM]; 


//事件的当前槽
int cur_slot = 0;


tw_timer * malloc_tw_timer(int rotation, int time_slot)
{
    tw_timer *timer = (tw timer *)malloc(sizeof(tw_timer)); 
    memset(timer, 0, sizeof(tw_timer));
    timer->rotation = rotation;
    timer->time_slot = time_slot;
    timer->prev = NULL ;
    timer->next = NULL ;
    timer->cb_func = NULL ;
    timer->user_date = NULL;
    return timer;  
}


void* free_tw_timer(tw_timer *timer)
{
    if(NULL == timer)
        return NULL;
    
    if(NULL != timer->user_date)
        free(timer->user_date);
    
    free(timer);
} 


void time_wheel()
{
    int i = 0;
    for(i = 0; i < SLOTS_NUM; i++)
      slots[i] = NULL;
}


//遍历每个槽，销毁定时器
void del_time_wheel()
{
    int i = 0;
    for(i = 0; i < SLOTS_NUM; i++)
    {
    tw_timer *tmp = slots[i];
    while(tmp)
    {
      slots[i] = tmp->next;
      free_tw_timer(tmp);
      tmp = slots[i];
    }    
    }
}
 
 /*根据定时器timeout创建一 个定时器，并把它插入到一个合适的槽中*/ 
tw_timer * add_timer(int timeout)
{
    if(timeout < 0)
        return NULL;


    int ticks = 0;
    /*待插入的超时时间小于时间轮的槽间隔SI，则将ticks向 上调整为1,
      否则将ticks向下调整为 timeout/SI 
    */
    if(timeout < SI) 
    {
    ticks = 1;
    }
    else
    {
        ticks = timeout / SI;
    }


    //计算待插入的定时器在时间轮转动多少圈后被触发
    int rotation = ticks / SLOTS_NUM;
    //计算待插入的定时器应该被插入到哪个槽中
    int ts = (cur_slot + (ticks % SLOTS_NUM)) % SLOTS_NUM;
    //创建新的定时器，它在时间轮转动rotation圈后被触发
    tw_timer *timer = malloc_tw_timer(rotation, ts);
    /*若第ts个槽为空，则插入定时器，并将该定时器置为该槽的头结点*/
    if(!slots[ts])
    {
        printf("add timer, rotation is %d, ts is %d, cur_ slot is %d
", 
                rotation, ts, cur_slot); 
        slots[ts] = timer;
    }
    else //否则，将定时器插入其中
    {
        printf("slots[%d] is not null
", ts); 
    timer->next = slots[ts];
        slots[ts]->prev = timer;
        slots[ts] = timer;
    } 


    return timer;
}
 
void del_timer(tw_timer *timer)
{
    if(!timer)
      return ;
    
    int ts = timer->time_slot;
 
    /*slots[ts]是目标定时器所在槽头结点，若目标定时器为头结点，则需要重置第ts个槽的头结点*/ 
   if(timer == slots[ts])
   {
    slots[ts] = slots[ts]->next;
        if(slots[ts])
        {
      slots[ts]->prev = NULL;
      }
     }
    else
    {
    timer->prev->next = timer->next;
    if(timer->next)
    {
        timer->next->prev = timer->prev;
    } 
       
  }
     free_tw_timer(timer);    
}


//SI 时间到后，调用该函数， 时间轮向前滚动一个槽的间隔
void tick()
{
  tw_timer *tmp = slots[cur_slot];
  //遍历该槽对应链表的所有定时器，查看是否触发
  while(tmp)
  {
    if(tmp->rotation > 0)
    {
      tmp->rotation--;
      tmp = tmp->next;
    }
    else //到期,执行任务
    {
      tmp->cb_func(tmp->user_date);
      if(tmp == slots[cur_slot])
      {
        printf("delete head in cur_slot, cur_slot %d
", cur_slot);
        slots[cur_slot] = tmp->next;
        free_tw_timer(tmp);
        
        if(slots[cur_slot])
          slots[cur_slot]->prev = NULL;
          
        tmp = slots[cur_slot];
      }
      else
      {
        tmp->prev->next = tmp->next;
        if(tmp->next)
        {
          tmp->next->prev = tmp->prev;
        }
      
        tw_timer *tmp2 = tmp->next;
        free_tw_timer(tmp);        
        tmp = tmp2;
      }
    
    }
  }


  //更新时间轮的当前槽，以反映时间轮的转数
  cur_slot = ++cur_slot % SLOTS_NUM;
}

测试如下

int total = 0; //记录1s定时器触发次数


void test (client_date *cd)
{ 
  printf("total = %d
", total);
}


void test_add_timer(int timeout, void (*cb_func)(client_date *))
{
    tw_timer * timer;
    timer = add_timer(timeout); 
    timer->cb_func = cb_func;  
}




void test_crete_timer()
{
    //创建一一个2秒5秒10秒70秒， 85秒的定时器 
    test_add_timer(2, test);
    test_add_timer(5, test);
    test_add_timer(10, test);
    test_add_timer(70, test);
    test_add_timer(85, test);
  
    time_t now ;
    struct tm *tm_now ;
    time(&now) ;
    tm_now = localtime(&now) ;
    printf("test_crete_timer datetime: %d-%d-%d %d:%d:%d
", tm_now->tm_year+1900,
         tm_now->tm_mon+1, tm_now->tm_mday, tm_now->tm_hour, tm_now->tm_min, tm_now->tm_sec);
  
}


//保存触发定时器相应的fd和回调，在该回调中进行遍历时间轮
typedef struct epoll_callback_info
{
    int iFd;
    epoll_callback_t pfEpollCallBack; 
}epoll_callback_info;


//创建一个触发定时器
int createTimer(long lMSec, int epfd, epoll_callback_t pfEpollCallback)
{
  struct itimerspece stTimer;
  struct epoll_event event;
  int timerfd;
  int iSec = (int)(lMSec/1000);
  int ret = -1;


  memset(&event, 0, sizeof(event));
  event.events = EPOLLIN | EPOLLHUP | EPOLLERR;
  
  memset(&stTimer, 0, sizeof(stTimer));
  stTimer.it_value.tv_sec = iSec;
  stTimer.it_value.tv_nsec = (lMSec%1000)*1000000;
  stTimer.it_interval.tv_sec = iSec;
  stTimer.it_interval.tv_nsec = (lMSec%1000)*1000000;
  
  timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
  if(-1 != timerfd)
  {
    if(0 == timerfd_settime(timerfd, 0, &stTimer, NULL))
    {
      epoll_callback_info *p = malloc(sizeof(epoll_callback_info));
      p->iFd = timerfd;
      p->pfEpollCallback = pfEpollCallback;
      
      event.data.ptr = p;
      ret = epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &event);
    }
    else
    {
      printf("timerfd_settime Failed");
    }
    
    /*定时器时间设定或添加epoll错误时，释放资源*/
    if(0 != ret)
    {
      printf("add to epoll failed or set time failed");
      close(timerfd);
      timerfd = -1;
    }
  }
  else
  {
    printf("create timerfd failed");
  }


  return timerfd;
}


void timer_read_timerFd(int timerfd)
{
  uint64_t exp;
  (void)read(timerfd, &exp, sizeof(uint64_t));
  
  total++;
  return;
}


//epoll上定时器回调，每触发一次则调用一次tick()
void commomTimerCB(int uiEvent, int iTimeFd)
{
  timer_read_timerFd(iTimeFd);
  tick();
}




int main()
{
  struct epoll_event wait_event[100];
  int epfd;
  int timerfd;
  epoll_callback_t pfEpllCallback;
  int i = 0;
  struct itimerspece stTimer;
  long lMSec = 1000; //1s定时器时间
  int count;
  
  epfd = epoll_create(1);
  if(-1 == epfd)
  {
    printf("epoll create error
");
    return -1;
  }
  
  printf("create epoll fd: %d
", epfd);
  time_wheel();
  test_create_timer();
  
  timerfd = createTimer(lMSec, epfd, (epoll_callback_t)commomTimerCB);
  if(-1 == timerfd)
  {
    printf("failed to create timer");
    return -1;
  }
  
  for(;;)
  {
    waitfds = epoll_wait(epfd, wait_event, 100, -1);
    printf("count %d
", count++);
    
    for(i = 0; i < waitfds; i++)
    {
      epoll_callback_info *t = (epoll_callback_info*)wait_event[i].data.ptr;
      pfEpllCallback = (epoll_callback_t)(unsigned long)t->pfEpllCallback；
      pfEpllCallback(wait_event[i].events, t->iFd);
    }
  }
  
  return 0;
}