golang源码阅读之定时器以及避坑指南
欢迎访问我的个人网站获取更佳阅读排版体验： golang源码阅读之定时器以及避坑指南 | yoko blog
( https://pengrl.com/p/62835/
)
本文分为三部分：
第一部分为阅读源码后的总结。
第二部分为高性能场景使用定时器需要注意的地方。
第三部分为系统库源码以及我写的注释。
本文基于go version 1.11.4
先放总结
所有业务层的timer对象都被底层的全局容器变量所持有及管理。这里说的全局容器是一个桶（bucket）数组，数组大小固定为64，数组的每个元素为一个桶对象，每个桶内包含一个最小堆和一个loop循环协程（以下简称 桶协程
）。
timer对象归哪个桶管理取决于申请该timer对象时G所在的P（通过P的id取余64作为桶数组下标）。
（关于golang线程调度模型中G P M的概念超出了本文的讨论范围。这里只简单理解G为当前goroutine，P为当前goroutine所属的任务队列。）
由于hash算法和P的id相关，所以一个程序最多有min(64, GOMAXPROCS)个桶在使用。
另外，和桶一对一关联的桶协程是懒开启的，只在桶被初次使用时（即有timer对象hash到了这个桶）才开启，开启后桶协程内部的循环永远不会退出。
不将桶数量直接设置为GOMAXPROCS是因为那样的话数组需要动态申请。
桶数量设置为64是权衡在不同环境下（GOMAXPROCS不同）内存使用以及性能间的一种经验值。
每个桶都有一个最小堆，根据桶内所有timer的超时触发绝对时间点做调整。
关于数据结构最小堆的详细介绍读者可以自行查找资料，这里你只需要知道堆的底层使用数组实现，插入和删除的时间复杂度都是O(logn)，并且插入和删除后，最小堆始终保持最小的元素在堆顶位置，所以获取最小元素是O(1)的。
事实上，golang定时器中的最小堆使用的是四叉树实现，相较于常见的二叉树实现，在节点数量比较多时，四叉树对底层数组的访问路径的局部性更好，CPU cache更友好些。
当桶内没timer时，桶协程被挂起。即rescheduling状态。
当桶内还有timer时，桶内协程睡眠直到最小超时触发时间点后再唤醒。即sleeping状态。
当往桶内加入新timer而该timer的超时触发时间点正好是当前桶内最小的，则唤醒桶协程。让桶协程重新判断，设置新的最小超时触发时间点后进入sleeping状态。
由于桶数量是固定的，所以hash桶的操作是无锁的。
但是桶内有互斥锁，因为 桶协程
和 业务层调用Timer的接口
可能并行操作桶内的最小堆和各种标志等变量。
使用timer时，以下几点开销要做到心里有数， 桶内互斥锁的开销，最小堆容器管理的开销，协程调度的开销，创建timer对象时、超时触发返回当前时间时、桶协程内部都会有获取当前时间调用的开销。
高性能场景如何使用
阅读源码的目的，是学习别人写的好的地方，以及保证正确的使用姿势。
你能看出下面这段伪代码存在的问题吗？
func consume() {
t := new time.NewTimer(5 * time.Second)
select {
case <- ch:
// 做相关的业务
case <- t:
// 超时了，做超时处理
}
}
这是timer常见的一种用法，为某个 消费者
设置消费超时时间。
如果在超时时间内消费 ch
成功了，则timer对象在业务层没有被触发。
那么问题来了，底层从最小堆中删除timer只有两种情况，要么在业务层显式调用Stop方法停止定时器，要么底层判断timer已经到达超时触发时间。刚才这种情况，底层只能等到超时触发时间（伪代码中为5秒后）才能从容器中移除该timer。 即资源被延时释放了。
作为写业务层代码的人，很可能会误认为业务层已经不再使用且不再持有该timer了，资源就被释放了。
如果我们的生产消费非常的频繁，底层容器将堆积大量的timer，从而浪费大量内存和CPU资源。
另外，假设你在其它场景使用了time.Ticker（不同于Timer只在超时后触发一次，Ticker将周期性触发超时）而没有调用Stop（即使业务层已不再持有Ticker对象了），情况将更糟糕，底层容器将一直持有Ticker对象，并周期性触发超时，然后修改下次超时时间点。 资源将永远得不到释放，内存和CPU将永久性的泄漏。
正确的做法应该是：
Ticker对象不再使用后，显式调用Stop方法。
Timer对象不再使用后，在高性能场景下，也应该显式调用Stop方法，及时释放资源。
那么这又分为两种情况，Timer是否已经在业务层触发超时了。
通过阅读系统库源码我们可以得知，对已超时的Timer调用Stop方法内部有变量保护，是安全的。但是这种保护需要拿一次桶内的互斥锁，高性能场景下也需要考虑这个消耗。
所以正确释放Timer对象的做法是，简单点就在上面伪代码的 select
结束后统一调用Stop，精细点就在 ch
得到消费时调用Stop。
我之后会再写一篇文章，关于在某些特定场景下如何自己实现一个简易timer，牺牲部分我们不需要的精确度来大幅提高超时业务逻辑的性能。
部分源码的说明
涉及到文件为：
- src/time/sleep.go
- src/time/tick.go
- src/runtime/time.go
- 其它一些runtime中的代码
首先看 time/sleep.go
，里面有time.Timer的实现，time.Timer比较简单，只是对runtime包中timer的一层wrap。这层自身实现的最核心功能是将底层的超时回调转换为发送channel消息。
// 这里可以看到是对runtimeTimer的wrap
type Timer struct {
C <-chan Time
r runtimeTimer
}
func NewTimer(d Duration) *Timer {
// 注意，这里的channel是带缓冲的，保证了业务层如果不接收这个channel，底层的
// 桶协程不会因为发送channel而被阻塞
c := make(chan Time, 1)
t := &Timer{
C: c,
r: runtimeTimer{
when: when(d),
// 向底层timer传入sendTime回调函数
f: sendTime,
arg: c,
},
}
startTimer(&t.r)
return t
}
// 将底层的超时回调转化为channel发送，并写入了当前时间
func sendTime(c interface{}, seq uintptr) {
// Non-blocking send of time on c.
// Used in NewTimer, it cannot block anyway (buffer).
// Used in NewTicker, dropping sends on the floor is
// the desired behavior when the reader gets behind,
// because the sends are periodic.
select {
case c.(chan Time) <- Now():
default:
}
}
// After就是匿名Timer
func After(d Duration) <-chan Time {
return NewTimer(d).C
}
接下来我们看 runtime/time.go
// timer结构体
type timer struct {
tb *timersBucket // timer所属的桶
i int // 最小堆中的下标，为-1时则不可用了
// 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.
when int64 // 超时时间点
period int64 // 如果是Ticker，会有这个值，周期性触发
f func(interface{}, uintptr) // 回调
arg interface{} // time.Timer会传入channel变量，一会回调时把channel带回去
seq uintptr // 这个变量目前没有用
}
// 桶数量固定为64
const timersLen = 64
// 全局桶数组，还对cache伪共享做了优化
var timers [timersLen]struct {
timersBucket
// The padding should eliminate false sharing
// between timersBucket values.
pad [sys.CacheLineSize - unsafe.Sizeof(timersBucket{})%sys.CacheLineSize]byte
}
// addTimer时，首先P id取余64获取timer所属的bucket
func (t *timer) assignBucket() *timersBucket {
id := uint8(getg().m.p.ptr().id) % timersLen
t.tb = &timers[id].timersBucket
return t.tb
}
func (tb *timersBucket) addtimerLocked(t *timer) bool {
// 负数参数保护性代码
if t.when < 0 {
t.when = 1< 0 {
break
}
ok := true
// 如果是period有值，说明需要周期性触发，我们将该timer修改触发时间后，重新
// 插入最小堆中
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)
if !siftdownTimer(tb.t, 0) {
ok = false
}
} else {
// 从最小堆中删除
last := len(tb.t) - 1
if last > 0 {
tb.t[0] = tb.t[last]
tb.t[0].i = 0
}
tb.t[last] = nil
tb.t = tb.t[:last]
if last > 0 {
if !siftdownTimer(tb.t, 0) {
ok = false
}
}
// 下标设置为-1，deltimer时发现下标为-1则不用删除了
t.i = -1 // mark as removed
}
// 把t中变量拷贝出来，就可以出锁了
f := t.f
arg := t.arg
seq := t.seq
unlock(&tb.lock)
// 堆调整时如果下标设置越界了，则丢到这里来处理，badTimer会直接panic
if !ok {
badTimer()
}
// 如果开了race检查的话
if raceenabled {
raceacquire(unsafe.Pointer(t))
}
f(arg, seq)
lock(&tb.lock)
}
// 如果桶内没有timer了，把协程挂起
if delta 0 {
// No timers left - put goroutine to sleep.
tb.rescheduling = true
goparkunlock(&tb.lock, waitReasonTimerGoroutineIdle, traceEvGoBlock, 1)
continue
}
// At least one timer pending. Sleep until then.
// 如果还有协程，睡眠直到桶内最早触发时间点到达后唤醒
tb.sleeping = true
tb.sleepUntil = now + delta
noteclear(&tb.waitnote)
unlock(&tb.lock)
notetsleepg(&tb.waitnote, delta)
}
}
// Delete timer t from the heap.
// Do not need to update the timerproc: if it wakes up early, no big deal.
func deltimer(t *timer) bool {
if t.tb == nil {
// t.tb can be nil if the user created a timer
// directly, without invoking startTimer e.g
// time.Ticker{C: c}
// In this case, return early without any deletion.
// See Issue 21874.
return false
}
tb := t.tb
lock(&tb.lock)
// t may not be registered anymore and may have
// a bogus i (typically 0, if generated by Go).
// Verify it before proceeding.
i := t.i
last := len(tb.t) - 1
// 如果已经触发过或已经被删除了，则返回false告知调用方
if i last || tb.t[i] != t {
unlock(&tb.lock)
return false
}
if i != last {
tb.t[i] = tb.t[last]
tb.t[i].i = i
}
tb.t[last] = nil
tb.t = tb.t[:last]
ok := true
if i != last {
if !siftupTimer(tb.t, i) {
ok = false
}
if !siftdownTimer(tb.t, i) {
ok = false
}
}
unlock(&tb.lock)
if !ok {
badTimer()
}
return true
}
About The Author
