定时器

Go的定时器是在经过一段时间后做一些事情，位于标准库的time包。主要是time.Timer, time.Ticker和看起来不太明显的定时器time.Sleep。由于从官方文档中不能清楚地知道这些定时器是怎么实现的，所以一些人就会认为每个定时器都会有一个自己的goroutine直到时间到了才退出。这是用最简单的方式来实现的。我们可以用一个小程序来验证一下。

package main

import (
    "fmt"
    "os"
    "runtime/debug"
    "time"
)

func main() {
    debug.SetTraceback("system")
    if len(os.Args) == 1 {
        panic("before timers")
    }
    for i := 0; i < 10000; i++ {
        time.AfterFunc(time.Duration(5*time.Second), func() {
            fmt.Println("Hello!")
        })
    }
    panic("after timers")
}

如果没有参数这个程序会在定时器之前打印出所有goroutine；如果有参数那么会打印出执行了定时器之后的所有goroutine。我们需要用到panic不然的话没有什么简单的方法来查看运行时的goroutine——它们被runtime.NumGoroutines和runtime.Stack排除了，所以仅剩的方法就是让程序crash掉。让我们看看在生成定时器之前生成了多少个goroutine：

go run afterfunc.go 2>&1 | grep "^goroutine" | wc -l
4

在生成了10K个定时器之后：

go run afterfunc.go 2>&1 | grep "^goroutine" | wc -l
5

哇！只多出了一个goroutine！
让我们接下来看看为什么只单单多出来一个goroutine。

runtime.timer

所有的定时器都基于相同的数据结构——runtime.timer。增加一个新的定时器，你需要实例化runtime.timer并把它传递给函数runtime.startTimer。这里有个time包的例子：

func NewTimer(d Duration) *Timer {
    c := make(chan Time, 1)
    t := &Timer{
        C: c,
        r: runtimeTimer{
            when: when(d),
            f:    sendTime,
            arg:  c,
        },
    }
    startTimer(&t.r)
    return t
}

所以，在这里我们把持续时间(duration)转换成具体的时间戳when，定时器应该要调用以c作为参数的函数f。在time包中，函数f有三种类型：

• sendTime：发送当前时间到channel或者在发送被阻塞的情况下丢弃。被time.Timer和time.Ticker使用。
• goFunc：在goroutine中执行一些函数。被time.AfterFunc使用。
• goroutineReady：唤醒特定的goroutine。被runtime.timeSleep使用。

现在我们已经理解了在运行时中定时器是怎样的了和它们应该怎么做的了。接下来让我们看看运行时是怎么存储定时器和在时间到了的时候怎么去调用函数的。

runtime.timers

runtime.timers只是一个数据结构，堆。当你想在一些元素中重复地去查找极限值（最大或最小）的时候堆就很有用了。在我们的例子中，极限值就是最接近当前时间的when。是不是很方便？那么，让我们看看在最坏的情况下操作定时器的算法复杂度：

• 增加新的定时器——O(log(n))
• 删除定时器——O(log(n))
• 生成定时器函数——O(log(n))

所以，如果你有一百万个定时器，那么操作数量一般来说会少于1000（log(1kk) ~= 20，但是生成操作会多出来几个最小值删除，因为多个定时器可能在相同的时间达到它们的截止时间） 。这是非常快的，并且所有的工作都发生在同一个独立的goroutine中，所以它不会阻塞。siftupTimer和siftdownTimer函数是用来维护堆的性质的。但是数据结构不会只为自己工作，一些东西也需要用到它们。在我们的例子中它只是一个timeproc函数的goroutine。它在第一个定时器开始的时候生成。

runtime.timerproc

如果没有源码的话有点难以描述到底发生了什么，所以这一节将开始对Go的代码做一些注释。代码是直接从src/runtime/time.go文件直接拷贝过来的并添加了一些注释。

// Add a timer to the heap and start or kick the timerproc if the new timer is
// earlier than any of the others.
// 增加一个定时器到堆中并开始或者删掉timeproc如果新的定时器早于任何定时器的话
func addtimerLocked(t *timer) {
    // when 必须不能是负值，否则的话 timeproc将会溢出
    // when must never be negative; otherwise timerproc will overflow
    // during its delta calculation and never expire other runtime·timers.
    if t.when < 0 {
        t.when = 1<<63 - 1
    }
    t.i = len(timers.t)
    timers.t = append(timers.t, t)
    // maintain heap invariant
    // 维持堆的性质不变
    siftupTimer(t.i)
    // new time is on top
    // 新的时间在堆的顶部了
    if t.i == 0 {
        // siftup moved to top: new earliest deadline.
        // siftup 移到了顶部：新的最早的截止时间
        if timers.sleeping {
            // wake up sleeping goroutine, put to sleep with notetsleepg in timerproc()
            // 唤醒睡眠中的goroutine
            timers.sleeping = false
            notewakeup(&timers.waitnote)
        }
        if timers.rescheduling {
            // run parked goroutine, put to sleep with goparkunlock in timerproc()
            // 运行暂停的goro
            timers.rescheduling = false
            goready(timers.gp, 0)
        }
    }
    if !timers.created {
        // run timerproc() goroutine only once
        // 只运行一次timeproc()
        timers.created = true
        go timerproc()
    }
}

// Timerproc runs the time-driven events.
// It sleeps until the next event in the timers heap.
// If addtimer inserts a new earlier event, addtimerLocked wakes timerproc early.
// Timeproc 运行时间驱动的事件
// 它会一直睡眠直到下一个事件进入了定时器的堆中
// 如果 addtimer 插入了一个更早的事件， addtimerLocked 将会更早地唤醒timeproc
func timerproc() {
    // set timer goroutine
    // 设置定时器goroutine
    timers.gp = getg()
    // forever loop
    // 死循环
    for {
        lock(&timers.lock)
        // mark goroutine not sleeping
        // 标记goroutine不是在睡眠
        timers.sleeping = false
        now := nanotime()
        delta := int64(-1)
        // iterate over timers in heap starting from [0]
        // 从堆的[0]开始迭代定时器
        for {
            // there are no more timers, exit iterating loop
            // 已经没有其他的定时器了，退出迭代循环
            if len(timers.t) == 0 {
                delta = -1
                break
            }
            t := timers.t[0]
            delta = t.when - now
            if delta > 0 {
                break
            }
            // t.period means that it's ticker, so change when and move down
            // in heap to execute it again after t.period.
            // t.period 意味着它是一个ticker，所以改变 when 并移到堆的下方，经过t.period再执行
            if t.period > 0 {
                // leave in heap but adjust next time to fire
                // 留在堆里但是调整下次执行的时间
                t.when += t.period * (1 + -delta/t.period)
                siftdownTimer(0)
            } else {
                // remove from heap
                // this is just removing from heap operation:
                // - swap first(extremum) with last
                // - set last to nil
                // - maintain heap: move first to its true place with siftdownTimer.
                // 从堆中移除
                // 这是从堆中移除的操作：
                // - 交换第一个和最后一个
                // - 设置最后一个为nil
                // - 维护堆：用 siftdownTimer把第一个移到正确的位置
                last := len(timers.t) - 1
                if last > 0 {
                    timers.t[0] = timers.t[last]
                    timers.t[0].i = 0
                }
                timers.t[last] = nil
                timers.t = timers.t[:last]
                if last > 0 {
                    siftdownTimer(0)
                }
                // set i to -1, so concurrent deltimer won't do anything to
                // heap.
                // 把 i 设成 -1，所以并发的 deltimer不会对堆做任何事情
                t.i = -1 // mark as removed
            }
            f := t.f
            arg := t.arg
            seq := t.seq
            unlock(&timers.lock)
            if raceenabled {
                raceacquire(unsafe.Pointer(t))
            }
            // call timer function without lock
            // 不用锁调用定时器函数
            f(arg, seq)
            lock(&timers.lock)
        }
        // if delta < 0 - timers is empty, set "rescheduling" and park timers
        // goroutine. It will sleep here until "goready" call in addtimerLocked.
        // 如果 delta < 0 - 定时器为空，设成 “rescheduling” 并暂停定时器goroutine。它将会一直睡眠直到在 addtimerLocked 中调用 "goready"
        if delta < 0 || faketime > 0 {
            // No timers left - put goroutine to sleep.
            timers.rescheduling = true
            goparkunlock(&timers.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
            continue
        }
        // At least one timer pending. Sleep until then.
        // If we have some timers in heap, we're sleeping until it's time to
        // spawn soonest of them. notetsleepg will sleep for `delta` period or
        // until notewakeup in addtimerLocked.
        // notetsleepg fills timers.waitnote structure and put goroutine to sleep for some time.
        // timers.waitnote can be used to wakeup this goroutine with notewakeup.
        // 至少还有一个定时器未结束，睡眠直到结束
        // 如果在堆中还有一些定时器，那么会一直睡眠直到最快的时间到了
        timers.sleeping = true
        noteclear(&timers.waitnote)
        unlock(&timers.lock)
        notetsleepg(&timers.waitnote, delta)
    }
}

这里有两个变量我觉得应该要解释一下的：
rescheduling和sleeping。它们都是表明goroutine已经进入睡眠，但是却用到了不同的同步机制。

当所有当前的定时器已经被处理，但是在未来一段时间还有需要处理的时候，将会设置成sleeping。它使用了基于OS的同步，所以它会调用一些OS的系统调用来进入睡眠并唤醒goroutine，并且系统调用也意味着它是用OS线程来做这件事的。它使用了 note 结构和下面的函数来达到同步：

• noteclear -重置 note 状态
• notetsleepg -使goroutine进入睡眠直到 notewakeup 被调用或者经过一段时间之后（假设是定时器到下一个定时器之间的时间）。这个函数将 timers.waitnote 赋值给“指向定时器goroutine的指针”
• notewakeup -唤醒调用notetsleepg的goroutine

如果新的定时器比之前最早的定时器还要早的话，notewakeup 可能会在 addtimerLocked 中被调用。

当堆中已经没有任何定时器，也就是没有事情干的时候，将会设置成rescheduling。它会利用go 调度器使用goparkunlock函数来使goroutine进入睡眠。不像 notetsleepg，这样不会消耗任何的操作系统资源，但同样的也就不支持“唤醒超时”，因此它不能在 sleeping分支的时候代替 notetsleepg。 而当一个新的定时器通过 addTimerLocked被加进来的时候，就会调用 goready函数来唤醒goroutine。

结论

我们已经了解了Go定时器的底层实现了——运行时既不会每个定时器都一个goroutine，也不会“免费”使用定时器。理解事情是怎么工作的从而避免过早优化是很重要的。而且，我们也会学习到，阅读运行时的代码是相当简单的，所以你不应该害怕。我希望你能享受这次的阅读并分享给你的朋友。

备注

这篇文章是翻译自： How Do They Do It: Timers in Go，本人翻译地比较烂，后面会持续修改的，欢迎大家提供一些意见。