定時器
Go的定時器是在經(jīng)過一段時間后做一些事情，位于標(biāo)準(zhǔn)庫的time包。主要是time.Timer, time.Ticker和看起來不太明顯的定時器time.Sleep托享。由于從官方文檔中不能清楚地知道這些定時器是怎么實現(xiàn)的俊卤，所以一些人就會認為每個定時器都會有一個自己的goroutine直到時間到了才退出。這是用最簡單的方式來實現(xiàn)的血筑。我們可以用一個小程序來驗證一下绘沉。
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")
}
如果沒有參數(shù)這個程序會在定時器之前打印出所有g(shù)oroutine；如果有參數(shù)那么會打印出執(zhí)行了定時器之后的所有g(shù)oroutine。我們需要用到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
所有的定時器都基于相同的數(shù)據(jù)結(jié)構(gòu)——runtime.timer。增加一個新的定時器，你需要實例化runtime.timer并把它傳遞給函數(shù)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
}
所以，在這里我們把持續(xù)時間(duration)轉(zhuǎn)換成具體的時間戳when绑榴，定時器應(yīng)該要調(diào)用以c作為參數(shù)的函數(shù)f哪轿。在time包中，函數(shù)f有三種類型：
- sendTime：發(fā)送當(dāng)前時間到channel或者在發(fā)送被阻塞的情況下丟棄翔怎。被time.Timer和time.Ticker使用窃诉。
- goFunc：在goroutine中執(zhí)行一些函數(shù)杨耙。被time.AfterFunc使用。
- goroutineReady：喚醒特定的goroutine飘痛。被runtime.timeSleep使用珊膜。
現(xiàn)在我們已經(jīng)理解了在運行時中定時器是怎樣的了和它們應(yīng)該怎么做的了。接下來讓我們看看運行時是怎么存儲定時器和在時間到了的時候怎么去調(diào)用函數(shù)的宣脉。
runtime.timers
runtime.timers只是一個數(shù)據(jù)結(jié)構(gòu)车柠，堆。當(dāng)你想在一些元素中重復(fù)地去查找極限值（最大或最兴懿）的時候堆就很有用了竹祷。在我們的例子中，極限值就是最接近當(dāng)前時間的when羊苟。是不是很方便塑陵？那么，讓我們看看在最壞的情況下操作定時器的算法復(fù)雜度：
- 增加新的定時器——O(log(n))
- 刪除定時器——O(log(n))
- 生成定時器函數(shù)——O(log(n))
所以蜡励，如果你有一百萬個定時器猿妈，那么操作數(shù)量一般來說會少于1000（log(1kk) ~= 20，但是生成操作會多出來幾個最小值刪除巍虫，因為多個定時器可能在相同的時間達到它們的截止時間） 彭则。這是非常快的占遥，并且所有的工作都發(fā)生在同一個獨立的goroutine中俯抖，所以它不會阻塞。siftupTimer和siftdownTimer函數(shù)是用來維護堆的性質(zhì)的瓦胎。但是數(shù)據(jù)結(jié)構(gòu)不會只為自己工作芬萍，一些東西也需要用到它們。在我們的例子中它只是一個timeproc函數(shù)的goroutine搔啊。它在第一個定時器開始的時候生成柬祠。
runtime.timerproc
如果沒有源碼的話有點難以描述到底發(fā)生了什么，所以這一節(jié)將開始對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
// 維持堆的性質(zhì)不變
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 運行時間驅(qū)動的事件
// 它會一直睡眠直到下一個事件進入了定時器的堆中
// 如果 addtimer 插入了一個更早的事件旧蛾， addtimerLocked 將會更早地喚醒timeproc
func timerproc() {
// set timer goroutine
// 設(shè)置定時器goroutine
timers.gp = getg()
// forever loop
// 死循環(huán)
for {
lock(&timers.lock)
// mark goroutine not sleeping
// 標(biāo)記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
// 已經(jīng)沒有其他的定時器了莽龟，退出迭代循環(huán)
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 并移到堆的下方锨天，經(jīng)過t.period再執(zhí)行
if t.period > 0 {
// leave in heap but adjust next time to fire
// 留在堆里但是調(diào)整下次執(zhí)行的時間
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.
// 從堆中移除
// 這是從堆中移除的操作：
// - 交換第一個和最后一個
// - 設(shè)置最后一個為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 設(shè)成 -1毯盈，所以并發(fā)的 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
// 不用鎖調(diào)用定時器函數(shù)
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 - 定時器為空，設(shè)成 “rescheduling” 并暫停定時器goroutine病袄。它將會一直睡眠直到在 addtimerLocked 中調(diào)用 "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.
// 至少還有一個定時器未結(jié)束搂赋，睡眠直到結(jié)束
// 如果在堆中還有一些定時器赘阀，那么會一直睡眠直到最快的時間到了
timers.sleeping = true
noteclear(&timers.waitnote)
unlock(&timers.lock)
notetsleepg(&timers.waitnote, delta)
}
}
這里有兩個變量我覺得應(yīng)該要解釋一下的：
rescheduling和sleeping。它們都是表明goroutine已經(jīng)進入睡眠脑奠，但是卻用到了不同的同步機制基公。
當(dāng)所有當(dāng)前的定時器已經(jīng)被處理，但是在未來一段時間還有需要處理的時候捺信，將會設(shè)置成sleeping。它使用了基于OS的同步欠痴，所以它會調(diào)用一些OS的系統(tǒng)調(diào)用來進入睡眠并喚醒goroutine迄靠，并且系統(tǒng)調(diào)用也意味著它是用OS線程來做這件事的。它使用了 note 結(jié)構(gòu)和下面的函數(shù)來達到同步：
- noteclear -重置 note 狀態(tài)
- notetsleepg -使goroutine進入睡眠直到 notewakeup 被調(diào)用或者經(jīng)過一段時間之后（假設(shè)是定時器到下一個定時器之間的時間）喇辽。這個函數(shù)將 timers.waitnote 賦值給“指向定時器goroutine的指針”
- notewakeup -喚醒調(diào)用notetsleepg的goroutine
如果新的定時器比之前最早的定時器還要早的話掌挚，notewakeup 可能會在 addtimerLocked 中被調(diào)用。
當(dāng)堆中已經(jīng)沒有任何定時器菩咨，也就是沒有事情干的時候吠式，將會設(shè)置成rescheduling。它會利用go 調(diào)度器使用goparkunlock函數(shù)來使goroutine進入睡眠抽米。不像 notetsleepg特占，這樣不會消耗任何的操作系統(tǒng)資源，但同樣的也就不支持“喚醒超時”云茸，因此它不能在 sleeping分支的時候代替 notetsleepg是目。 而當(dāng)一個新的定時器通過 addTimerLocked被加進來的時候，就會調(diào)用 goready函數(shù)來喚醒goroutine标捺。
結(jié)論
我們已經(jīng)了解了Go定時器的底層實現(xiàn)了——運行時既不會每個定時器都一個goroutine懊纳，也不會“免費”使用定時器。理解事情是怎么工作的從而避免過早優(yōu)化是很重要的亡容。而且嗤疯，我們也會學(xué)習(xí)到，閱讀運行時的代碼是相當(dāng)簡單的闺兢，所以你不應(yīng)該害怕茂缚。我希望你能享受這次的閱讀并分享給你的朋友。
備注
這篇文章是翻譯自： How Do They Do It: Timers in Go屋谭，本人翻譯地比較爛阱佛，后面會持續(xù)修改的，歡迎大家提供一些意見戴而。
