基于时间轮实现毫秒级定时器一、为什么需要时间轮在服务器开发中定时器经常用于处理连接超时、心跳检测、资源清理、缓存刷新等任务如果使用排序链表管理定时器每次添加新定时器都要按照过期时间找到插入位置定时器数量多时插入效率会下降时间轮的核心思想是把定时器按照过期时间分散到不同槽中用空间换时间降低插入成本可以把时间轮理解成一个环形数组数组中的每个位置叫做一个槽也就是slot每个槽后面挂一条定时器链表时间轮指针每隔一段时间向后移动一格这一次移动叫做一次tick二、时间轮中的几个核心概念时间轮主要有两个参数N时间轮中槽的数量SI相邻两个槽之间的时间间隔也叫槽间隔如果时间轮有N个槽每个槽间隔是SI那么时间轮转一圈的时间就是N * SI例如N 60SI 1s那么时间轮转一圈就是60s添加一个定时器时假设当前槽是cur_slot定时器超时时间是timeout需要先计算它经过多少个 tick 到期ticks timeout / SI然后计算它应该放到哪个槽中ts (cur_slot ticks) % N如果定时器超时时间超过一圈还需要记录它要等待几圈rotation ticks / N所以一个定时器节点中通常要保存两个关键字段time_slot_表示定时器在哪个槽中rotation_表示还需要转多少圈才真正到期三、时间轮实现1 定时器节点设计我的定时器节点是tw_timer核心代码如下classtw_timer{public:tw_timer(introtation,inttime_slot):rotation_(rotation),time_slot_(time_slot),next_(nullptr),prev_(nullptr){}public:introtation_;inttime_slot_;std::functionvoid()cb_func;tw_timer*next_;tw_timer*prev_;};这个节点中主要保存了rotation_还需要转多少圈time_slot_当前定时器所在的槽cb_func定时器到期后的回调函数next_和prev_用于组成双向链表这里使用std::functionvoid()保存回调比普通函数指针更灵活可以直接绑定 lambda、普通函数或者std::bind2 时间轮结构设计我的时间轮类中核心成员如下static const int N 100static const int SI 1vectortw_timer * slots_int cur_slot_其中slots_是一个数组每个元素都是一个定时器链表的头指针cur_slot_表示当前时间轮指针指向哪个槽在我的实现中N 100SI 1表示时间轮有 100 个槽每个槽的时间间隔是 1 个时间单位3 添加和触发定时器添加定时器的核心逻辑是tw_timer*add_timer(inttimeout){if(timeout0){returnnullptr;}intticks;if(timeoutSI){ticks1;}else{tickstimeout/SI;}introtationticks/N;intts(tickscur_slot_)%N;tw_timer*new_timernewtw_timer(rotation,ts);if(!slots_[ts]){slots_[ts]new_timer;}else{new_timer-next_slots_[ts];slots_[ts]-prev_new_timer;slots_[ts]new_timer;}returnnew_timer;}这段代码的逻辑很清晰先根据timeout和SI计算ticks再通过rotation ticks / N计算需要等待几圈通过ts (ticks cur_slot_) % N计算应该插入哪个槽最后把定时器头插到对应槽的链表中头插法的好处是插入效率高添加一个定时器的复杂度接近O(1)时间轮推进时会调用tick()voidtick(){tw_timer*timerslots_[cur_slot_];while(timer){if(timer-rotation_0){timer-rotation_--;timertimer-next_;continue;}timer-cb_func();timerdel_timer(timer);}cur_slot_(cur_slot_1)%N;}每次tick()只处理当前槽上的链表如果rotation_ 0说明这个定时器虽然在当前槽但还没有真正到期只需要执行rotation_--如果rotation_ 0说明定时器到期执行cb_func()然后从链表中删除这个节点四、timerfd epoll 如何驱动时间轮时间轮本身只是一个数据结构它不会自己转动需要外部周期性触发tick()我的测试代码中使用timerfd作为时间源并把timerfd加入epoll核心流程是使用timerfd_create创建定时器 fd使用timerfd_settime设置周期触发时间把timerfd加入epoll当timerfd可读时读取触发次数根据触发次数调用对应次数的wheel-tick()// 创建 timerfd每 100ms 触发一次inttimerfdcreate_timerfd(100);if(timerfd-1){close(epollfd);return-1;}// 加入 epollepoll_addfd(epollfd,timerfd);epoll_event events[1024];while(true){intnumepoll_wait(epollfd,events,1024,-1);if(num0){if(errnoEINTR){continue;}perror(epoll_wait);break;}for(inti0;inum;i){intsockfdevents[i].data.fd;if(sockfdtimerfd(events[i].eventsEPOLLIN)){uint64_texpirations0;// expirations表示从上次读取到现在timerfd一共触发了多少次ssize_t retread(timerfd,expirations,sizeof(expirations));if(ret!sizeof(expirations)){continue;}for(uint64_tj0;jexpirations;j){wheel-tick();}}}}五、一个需要注意的问题SI 和 timerfd 间隔要统一我的时间轮中写的是SI 1但测试代码里创建timerfd时使用的是create_timerfd(100)也就是每100ms触发一次这时要注意单位问题如果我把SI 1理解成 1 秒那么timerfd应该每1000ms触发一次如果timerfd每100ms调用一次tick()那么add_timer(10)实际上不是 10 秒后触发而是 10 个 tick 后触发也就是大约 1 秒后触发所以实际写项目时最好统一单位比如规定SI 100表示一个槽间隔是 100ms所有timeout都用毫秒表示timerfd也按照 100ms 周期触发这样时间含义更清楚不容易混乱六、关于时间轮中 N 的意义我对N的理解是N 类似哈希表中桶的数量时间轮中的每个槽就像哈希表中的一个桶定时器会根据过期时间被映射到不同的槽中如果N太小槽的数量少定时器就容易集中到同一个槽上导致某些槽后面的链表很长这样虽然添加定时器还是接近O(1)但当时间轮指针转到这个槽时需要遍历很长的链表执行效率会下降