AImager

定时器

#时间轮 #最小堆 
func main() {
	wg := sync.WaitGroup{}
    wg.Add(1)
    time.AfterFunc(time.Second, func(){wg.Done()})
	fmt.Println("test")
	wg.Wait()
}

上面的代码很简单，即go语言里面的定时器使用方法——1s后触发某个函数的执行，

定时器管理实现

链表

n个已存在定时器

链表的实现方式最为简单，即每次延迟信号来了之后，遍历链表，如果时间到期了，就从链表删除该元素，并唤醒对应触发方法。链表实现的主要问题在于寻找到期定时器的时间复杂度为O(n)，考虑下tcp都有超时逻辑，对于动辄几千上万连接的web服务，这样的复杂度显然是没法满足性能要求的。

层级时间轮

m层级时间轮（m固定，且一般很小），n个已存在定时器

时间轮

插入时间复杂度：O(1)（最多m次运算） 查找到期定时器复杂度：O(1)（最多m次运算）

层级时间轮的实现虽然复杂度都为O(1)，但在查找过程中需要做一些额外的工作，当低层级轮转回起始点的时候，高一级的层级轮相应的需要转动一格，而对应格里面存的所有定时器都需要插入到低层级轮里面去。因此，对于m层级时间轮上的定时器，其实际操作次数是m次（移动m-1次，查找一次）。

当定时时间超过了时间轮支持的最长时间，可以把定时器放在一个额外链表里面，最高级时间轮每转一圈，就需要遍历这个额外链表，把链表里时间小于时间轮最长时间的定时器加回到时间轮里面来，某种意义上就是链表合层级时间轮的混合实现，从这里也可以看出来，层级时间轮更适合短时间内的高并发定时。

最小堆

n个已存在定时器

插入时间复杂度：O(lgn) 查找到期定时器复杂度：O(1)

golang中的定时器实现

// 定时器结构体
type timer struct {
    // 定时器所在的最小堆，数组实现
    tb *timersBucket // the bucket the timer lives in
    // 定时器在数组中的索引，0即表示在最小堆的根，即最先被唤醒
	i  int           // heap index

	// Timer wakes up at when, and then at when+period, ... (period > 0 only)
	// each time calling f(arg, now) in the timer goroutine, so f must be
    // a well-behaved function and not block.
    // 定时器到期时间，ns
    when   int64
    // 创建计时器距到期时间的间隔时间
    period int64
    // 到期唤醒函数
    f      func(interface{}, uintptr)
    // 到期channel
    arg    interface{}
	seq    uintptr
}

参考链接