简单时间轮(simple_timing_wheel)

  • 一个 简单时间轮 就是一个循环列表,列表中的每一格包含一个定时任务列表(双向链表)。一个时间单位为 u、大小为 n 的简单时间轮,可以包含的定时任务的最大到期间隔为 n*u。 以 u 为 1ms、n 为 3 的简单时间轮为例,可以包含的定时任务的最大到期间隔为 3ms。
  • 初始时,假设当前时间指向第 1 格(此时:到期间隔为 [0ms, 1ms) 的定时任务放第 1 格,[1ms, 2ms) 的放第 2 格,[2ms, 3ms) 的放第 3 格)。
  • 此时我们创建一个到期间隔为 1ms 的定时任务 task1,按规则该任务会被插入到第 2 格。 随着时间的流逝,过了 1ms 后当前时间指向第 2 格,这一格包含的定时任务 task1 会被删除并执行。 当前时间指向第 2 格(此时:到期间隔为 [0ms, 1ms) 的定时任务放第 2 格,[1ms, 2ms) 的放第 3 格,[2ms, 3ms) 的放第 1 格),我们继续创建一个到期间隔为 2ms 的定时任务 task2,按规则该任务被插入到第 1 格。

简单时间轮的优点是实现简单,缺点是:

  • 选定 n 后,就不能包含到期间隔超过 n*u 的定时任务。 如果定时任务的到期时间跨度较大,就会选择较大的 n,在定时任务较少时会造成很大的空间浪费。
  • 变体实现,它们通过在定时任务中增加记录 round 轮次信息,可以有效弥补上述两个缺点。同样以上面 u 为 1ms、n 为 3 的简单时间轮为例,初始时间指向第 1 格;此时如果要创建到期时间为 4ms 的定时任务,可以在该任务中设置 round 为 1(4/3 取整),剩余到期时间用 4ms 减去 round*3ms 等于 1ms,因此放到第 2 格;等到当前时间指向第 2 格时,判断任务中的 round 大于 0,所以不会删除并执行该任务,而是对其 round 减一(于是 round 变为 0);等到再过 3ms 后,当前时间再次指向第 2 格,判断任务中的 round 为 0,进而删除并执行该任务。

    func (s *SimpleTimingWheel) getPositionAndCircle(d time.Duration) (pos int, circle int) {
    	delaySeconds := int(d.Seconds())
    	intervalSeconds := int(s.interval.Seconds())
    	circle = int(delaySeconds / intervalSeconds / s.nodeNum) //添加轮数
    	//计算要放的节点
    	//剩下的时候在一轮就可以搞定
    	pos = int(delaySeconds - (intervalSeconds * s.nodeNum * circle) + s.currentNode)
    	return
    }
    
  • 这些变体实现因为只使用了一个时间轮,所以仍然存在一个缺点:如果定时任务数量很大,分摊到每一格的定时任务列表就会很长

使用方法

tw := NewSimpleTimingWheel(SetNodeNum(6))
tw.Start()
fmt.Println("开始", time.Now().Format("2006-01-02 15:04:05"))
tw.AddTask(8*time.Second, func() {
	fmt.Println("8秒后执行", time.Now().Format("2006-01-02 15:04:05"))
	//tw.Stop()
})

完整演示代码 点击这里

联系 QQ: 3355168235