完整代码实现： netpoll/net/inner/timing_wheel.h netpoll/net/inner/timing_wheel.cc实现契机 在网络框架的设计中,有一个环节是踢出空闲的连接,但是我觉得这个过程并不是一个很紧急的过程,有没有一种可以损失定时任务精度,但追求更小的时间消耗的方式呢? 我想到在原本的定时器上层封装一个时间轮,这样可以让那些不怎么重要的任务迅速添加,且即便在并发量很大的时候也能够防止过多的系统调用,因为你只需要和中间层打交道,并且时间轮本身的插入复杂度就是 O1 级别的. 这样每个线程维护一个每秒一转的时间轮来处理不重要的定时任务,可以减少整个系统在繁忙时不必要的开销. 如下图: img框架设计 我们这里的时间轮由于是直接调用已经实现好的定时器来进行轮转，所以不需要考虑定时轮转的问题。只需要关注实现时间轮采取的数据结构。 可以先考虑一种最简单的时间轮实现：使用一个数组结构，然后保存一个下标用于存储每次轮询到的位置，每次触发轮询都只需要把下标+1即可，然后通过模运算得到数组下标获取对应需要执行的任务。 但这样实现有一个很明显的问题：如果需要支持较长的定时任务，需要大量的内存。 为了优化这个内存的问题,我们采取多个不同精度的时间轮同时推进,如下图: img 我们假设从左往右的任务队列依次是 Q4/Q3/Q2/Q1 . 假设全局时间轮一共轮转了 112 次,我们可以把上述队列的各个位置看成是10进制数的各个位置,那么四个队列从左到右分别代表 0 1 1 2 这四个值,每个队列都是自己单独的每隔对应的 10^n 推进一次,而这个数字就记录了它们目前已经推进过多少次了(进位后不算),这个数值可以度量挨着的高位队列距离下次推进需要多久. 当我们需要往对应的队列中插入任务时,需要加上这个值(当前队列的前一个)作为初值. 对于上述描述,我们举一个例子比如当前时间轮计数器已经是 123 ,当前我需要添加一个 100s 后的任务,根据 123%10=3 可知还需要 7 次 Q1 的推进,Q2 才推进,以此类推 Q2 还需要推进 10-12%10=8 次,Q3 才推进一格......而我们目前需要添加一个延时 100s 的任务,首先计算需要在第一个队列添加到什么位置,如果任务需要的时间少于 10s ,那么只需要放入 Q1 中对应的位置即可,但是本例中需要添加 100s 后的任务,则优先往 Q2 添加任务,Q1 就只需要记录 Q2 无法表示的精度即可,计算在 Q2 中的位置首先需要 100+3=103 得到初值, 然后得到 103%10=3 是 Q2 不能表示的精度,也就是需要使用 Q1 来表示 3s 的精度,103/10=10 得到在 Q2 需要的精度,该数值正好小于等于 10 ,那么直接在 Q2 的相应位置插入任务即可. 最后我们可以验算一下,计数器是 123 的时候,添加100s 后的任务,我们在 Q1 添加了 3s 的任务,在 Q2 添加了 10*10-7=93s 的任务,请注意,我们对于这个 3s 的任务并不是立马就添加,而是在 Q2 中的任务执行结束后再添加,所以最终成功完成了延时 100s 后执行任务. 我们再次计算上述逻辑实现的时间轮最多可以添加多长的延时任务呢? $$ 10^310+10^210+10^110+10^010=11111s $$ 以上都是以 10 进制为基底的情况,实际的实现中,我默认是以 100 进制为基底,如果按照上述图中有 4 个队列,我算了算大概是可以表示 100000101s 大概是 3.17 年. 假设每个任务需要 32byte 内存,那么时间轮队列的内存消耗也只有 32*100*4=12800=12.5KB ,如果采用的是朴素的实现方式,最终需要的内存可能是 2.98GB ,这波优化确实是好很多.源码实现任务队列实现 对于时间轮中队列的设计使用 std::deque ,队列中每个元素是一个 std::unordered_set ,这个集合中包含多个任务,每个任务是一个 void* 指针,使用shared_ptr 进行内存管理,具体每个任务的调用是通过将队列头部的智能指针给 pop 出去,然后尾部继续插入空的指针,如果被 pop 的智能指针对应的引用计数减少为0,那么就调用对应的析构,而析构函数才是真正需要调用的任务. 这种设计逻辑是为了简化对同一个任务的延时逻辑,如果之前已经添加的延时任务马上就要被调用了,但是我还是想重置这个延时,那么只要这个引用计数不为零,真正的任务都不会被调用.这样设计特别适合踢出空闲的 TCP 连接.using EntryPtr = std::shared_ptr<void>; using EntryBucket = std::unorder…