首页 > 代码库 > 高性能定时器时间轮的探究
高性能定时器时间轮的探究
时间轮的概念
关于定时器有很多种,有基于升序的定时器时间链表,但是这种链表存在效率的不足,就是当插入定时器的时候时间复杂度是O(n).今天,我们来认识一下高性能定时器时间轮。
如上图所示,就是一个时间轮的基本轮廓。一个轮子上有很多槽slot,每一个槽指向一个定时器链表,这个链表是无序的。时间轮每转动一步就会指向下一个槽,其实也可以理解为一个滴答时间成为时间轮的槽间隔si (slot interval)。它实际上就是心跳时间。如果该时间轮有n个槽,因此它运转一周的时间是n*si.
如果现在指针指向槽cs,我们此时要添加一个定时器时间为ti的定时器,则该定时器将被插入槽ts对应的链表
ts = (cs+ti/si)%N
基于排序链表的定时器使用唯一的链表来管理所有定时器,所以插入定时器的数目越多,效率就会越低,而时间轮则是利用哈希表的思想,将定时器散列到不同的链表中,这样每条链表上的数据就会显著少于原来排序链表的数目。插入操作的效率基本不受定时器数目的影响(不需要排序,直接散列到一个链表上)。
显然要提高时间轮的精度,就要使si(slot interval)足够小,要提高其执行效率则要N要足够大。
时间轮
时间轮的代码示例
下面我们来通过实例代码进行系统讲解时间轮
本示例代码已经正确在机器上运行,结果得到验证!
验证运行环境:
Distributor ID: Ubuntu
Description: Ubuntu 13.04
Release: 13.04
Codename: raring
下面是time_wheel_timer.h的源代码
#ifndef TIME_WHEEL_TIMER #define TIME_WHEEL_TIMER #include<time.h> #include<netinet/in.h> #include<stdio.h> #define BUFFER_SIZE 64 class tw_timer; struct client_data { sockaddr_in address; int sockfd; char buf[BUFFER_SIZE]; tw_timer* timer; } ; class tw_timer { public: tw_timer(int rot,int ts):rotation(rot),time_slot(ts),next(NULL),prev(NULL){} public: int oldrotation; int rotation;/*记录定时器在时间轮上转多少圈后生效*/ int time_slot;/*记录定时器属于时间轮上的哪个槽*/ void (*cb_func)(client_data*);/*定时器回调函数*/ client_data* user_data;/*用户数据*/ tw_timer* next;/*指向下一个定时器*/ tw_timer* prev;/*指向前一个定时器*/ time_t expire;//定时时间 time_t start_time;//设定定时器的时间 }; class time_wheel { public: time_wheel():cur_slot(0) { for(int i=0;i<N;i++) { slots[i]=NULL;/*初始化每个槽的头结点*/ } } ~time_wheel() { for(int i=0;i<N;i++) { tw_timer* tmp = slots[i]; while(tmp) { slots[i]=tmp->next; delete tmp; tmp = slots[i]; } } } /*根据定时器的定时值timeout创建一个定时器,并把它插入合适的槽中*/ tw_timer* add_timer(int put_timeout) { if(put_timeout<0) { return NULL; } int ticks =0; int timeout = put_timeout-time(NULL); if(timeout<SI) ticks = 1; else ticks = timeout/SI; /*计算待插入的定时器在时间轮上转动多少圈后触发*/ int rotation = ticks/N; /*计算定时器应该被插入哪个槽中*/ int ts = (cur_slot+ticks%N)%N; /*创建定时器,它在时间轮转动rotation圈之后被触发,且位于第ts个槽中*/ tw_timer* timer = new tw_timer(rotation,ts); timer->expire = put_timeout; timer->oldrotation = rotation; if(!slots[ts]) slots[ts]=timer; else { 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; if(timer == slots[ts]) { slots[ts] = slots[ts]->next; if(slots[ts]) slots[ts]->prev = NULL; delete timer; } else { timer ->prev->next = timer ->next; if(timer->next) timer ->next ->prev = timer ->prev; delete timer; } } void tick() { tw_timer* tmp = slots[cur_slot]; while(tmp) { //如果定时器要转的圈数仍大于零 if(tmp->rotation>0) { tmp ->rotation --; tmp= tmp->next; } else { time_t cur_time = time(NULL); if(cur_time<tmp->expire) tmp=tmp->next; else { tmp->cb_func(tmp->user_data); if(tmp ==slots[cur_slot]) { slots[cur_slot] = tmp->next; delete 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; delete tmp; tmp = tmp2;//tmp 指向下一个定时器 } } } } cur_slot=++cur_slot%N; } private: static const int N = 60;/*转动一周需要12秒*/ static const int SI = 1;/*每隔1秒中,转动一次*/ tw_timer* slots[N];/*时间轮的槽,其中每个月元素指向一个定时器链表,链表无序*/ int cur_slot;/*时间轮当前槽*/ }; #endif
下面是time_wheel.main.cpp
<pre name="code" class="cpp">#include<iostream> #include<unistd.h> #include<pthread.h> #include<stdlib.h> #include"time_wheel_timer.h" using namespace std; static time_wheel client_timer; void myfunc(client_data*arg) { cout<<"timeout-->"<<"oldrotation:"<<arg->timer->oldrotation<<" now need rotation:"<<arg->timer->rotation<<" sockfd:"<< arg->sockfd<<" timer_slot:"<<arg->timer->time_slot<<" start_time:"<<arg->timer->start_time<< " expire:"<<arg->timer->expire<<" now:"<<time(NULL)<<" duration_time:"<<arg->timer->expire-arg->timer->start_time<<endl; arg =NULL; } void* checktick(void*arg) { while(1)
{ client_timer.tick(); usleep(1000);//后续可以采用信号的方式进行改进 } } int main() { client_data*users = new client_data[20]; srand(time(NULL)); for(int i =0;i<10;i++) { users[i].sockfd = i; time_t cur_time = time(NULL); tw_timer* timer = client_timer.add_timer(cur_time+rand()%100+1); if(timer) { timer->user_data = http://www.mamicode.com/&users[i];>编译执行
g++ time_wheel.main.cpp -lpthread -owheel
执行结果
ky@ky-S910-X31E:~/libz/72$ ./wheel timeout-->oldrotation:0 now need rotation:0 sockfd:9 timer_slot:24 start_time:1404385502 expire:1404385526 now:1404385526 duration_time:24 timeout-->oldrotation:0 now need rotation:0 sockfd:8 timer_slot:25 start_time:1404385502 expire:1404385527 now:1404385527 duration_time:25 timeout-->oldrotation:0 now need rotation:0 sockfd:0 timer_slot:25 start_time:1404385502 expire:1404385527 now:1404385527 duration_time:25 timeout-->oldrotation:0 now need rotation:0 sockfd:4 timer_slot:52 start_time:1404385502 expire:1404385554 now:1404385554 duration_time:52 timeout-->oldrotation:1 now need rotation:0 sockfd:1 timer_slot:2 start_time:1404385502 expire:1404385564 now:1404385564 duration_time:62 timeout-->oldrotation:1 now need rotation:0 sockfd:7 timer_slot:15 start_time:1404385502 expire:1404385577 now:1404385577 duration_time:75 timeout-->oldrotation:1 now need rotation:0 sockfd:3 timer_slot:16 start_time:1404385502 expire:1404385578 now:1404385578 duration_time:76 timeout-->oldrotation:1 now need rotation:0 sockfd:6 timer_slot:30 start_time:1404385502 expire:1404385592 now:1404385592 duration_time:90 timeout-->oldrotation:1 now need rotation:0 sockfd:2 timer_slot:32 start_time:1404385502 expire:1404385594 now:1404385594 duration_time:92 timeout-->oldrotation:1 now need rotation:0 sockfd:5 timer_slot:35 start_time:1404385502 expire:1404385597 now:1404385597 duration_time:95其中oldrotation:1表示旋转圈数,need rotation:0 表示目前剩下的旋转圈数,sockfd:2表示是第几个定时器, timer_slot:32 表示定时器位于第几个槽中,start_time:1404385502 表示定时器开始定时的时间,expire:1404385597表示定时器超时时间。
时间轮分析
对应时间轮分析,添加一个定时器的时间按复杂度为O(1),删除一个定时的时间复杂度也是O(1),执行一个定时器的时间复杂度为O(n),如果定时器的时间轮上的槽数越高则效率就会更好的提升
更多内容请前往个人文库
http://wenku.baidu.com/p/helpylee