首页 > 代码库 > 高性能定时器时间轮的探究

高性能定时器时间轮的探究

时间轮的概念 

   关于定时器有很多种,有基于升序的定时器时间链表,但是这种链表存在效率的不足,就是当插入定时器的时候时间复杂度是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