社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
注:本文基于 go-1.13 源码进行分析,而在 go 的 1.14 版本中,关于定时器的实现略有一些改变,以后会再专门写一篇文章进行分析。
我们在日常开发中会经常用到 time.NewTicker 或者 time.NewTimer 进行定时或者延时的处理逻辑。
Timer 和 Ticker 在底层的实现基本一致,本文将主要基于 Timer 进行探讨研究。Timer 的使用方法如下:
import (
"fmt"
"time"
)
func main() {
timer := time.NewTimer(2 * time.Seconds)
<-timer.C
fmt.Println("Timer fired")
}
在上面的例子中,我们首先利用 time.NewTimer 构造了一个 2 秒的定时器,同时使用 <-timer.C 阻塞等待定时器的触发。
对于 time.NewTimer 函数,我们可以轻易地在 go 源码中找到它的实现,其代码位置在 time/sleep.go#L82。如下:
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
}
NewTimer 主要包含两步:
在 Timer 结构体中的属性 C 不难理解,从最开始的例子就可以看到,它是一个用来接收 Timer 触发消息的 channel。注意,这个 channel 是一个有缓冲 channel,缓冲区大小为 1。
我们主要看的是 runtimeTimer 这个结构体:
timer 对象构造好后,接下来就调用了 startTimer 函数,从名字来看,就是启动 timer。具体里面做了哪些事情呢?
startTimer 具体的函数定义在 runtime/time.go 中,里面实际上直接调用了另外一个函数 addTimer。我们可以看下 addTimer 的代码 /runtime/time.go#L131:
func addtimer(t *timer) {
// 得到要被插入的 bucket
tb := t.assignBucket()
// 加锁,将 timer 插入到 bucket 中
lock(&tb.lock)
ok := tb.addtimerLocked(t)
unlock(&tb.lock)
if !ok {
badTimer()
}
}
可以看到 addTimer 至少做了两件事:
那么问题来了,bucket 是什么?timer 插入到 bucket 中后,会以何种方式触发?
在 go 1.13 的 runtime 中,共有 64 个全局的 timer bucket。每个 bucket 负责管理一些 timer。timer 的整个生命周期包括创建、销毁、唤醒和睡眠等都由 timer bucket 管理和调度。
每个 timersBucket 实际上内部是使用最小四叉堆来管理和存储各个 timer。最小堆是非常常见的用来管理 timer 的数据结构。在最小堆中,作为排序依据的 key 是 timer 的 when 属性,也就是何时触发。即最近一次触发的 timer 将会处于堆顶。如下图:
每个 timerbucket 负责管理一堆这样有序的 timer,同时每个 timerbucket 都有一个对应的名为 timerproc 的 goroutine 来负责不断调度这些 timer。代码在 /runtime/time.go#L247
对于每个 timerbucket 对应的 timeproc,该 goroutine 也不是时时刻刻都在监听。timerproc 的主要流程概括起来如下:
当 timer 触发时,timerproc 会调用对应的 callback。对于 timer 和 ticker 来说,其 callback 都是 sendTime 函数,如下:
func sendTime(c interface{}, seq uintptr) {
select {
case c.(chan Time) <- Now():
default:
}
}
这里的 c interface{},也就是我们上文中提到的,在定义 timer 或 ticker 时,timer 对象中的 C 属性, 在 timer 和 ticker 中,它都被初始化为长度为 1 的有缓冲 channel。
调用 sendTime 时,会向 channel 中传递一个值。由于是缓冲为 1 的 buffer,因此当缓冲为空时,sendTime 可以无阻塞地把数据放到 channel 中。
如果定时时间过短,也不用担心用户调用 <-timer.C 接收不到触发事件,因为事件已经放到了 channel 中。
而对于 ticker 来说,sendTime 会被调用多次,而 channel 的缓冲长度只有 1。如果 ticker 没有来得及消费 channel,会不会导致 timerproc 调用 callback 阻塞呢?答案是不会的。因为我们可以看到,在这个 select 语句中,有一个 default 选项,如果 channel 不可写,会触发 default。对于 ticker 来说,如果之前的触发事件没有来得及消费,那新的触发事件到来,就会被立即丢弃。
因此对于 timerproc 来说,调用 sendTime 的时候,永远不会阻塞。这样整个 timerproc 的过程也不会因为用户侧的行为,导致某个 timer 没有来得及消费而造成阻塞。
64 个 timerbucket 的定义代码如下,在 /runtime/time.go#L39 可以看到。
const timersLen = 64
var timers [timersLen]struct {
timersBucket
// The padding should eliminate false sharing
// between timersBucket values.
pad [cpu.CacheLinePadSize - unsafe.Sizeof(timersBucket{})%cpu.CacheLinePadSize]byte
}
不过 64 个 timerbucket,而不是一个,或者说为什么不至于与 GOMAXPROCS 保持一致呢?
首先,在 go 1.10 之前,go runtime 中的确只有一个 timers 对象,负责管理 timer。这个时候也就没有分桶了,整个定时器调度模型非常简单。但问题也非常明显,
因此,在 go 1.10 中,引入了全局 64 个 timer 分桶的策略。将 timer 打散到分桶内,每个桶负责自己分配到的 timer 即可。好处也非常明显,可以有效降低了锁粒度和 timer 调度的负担。
那为什么是 64 个 timerbucket,而不是 32 个或者更多,或者不干脆与 GOMAXPROCS 保持一致?这点在源码注释中也有详细的说明:
Ideally, this would be set to GOMAXPROCS, but that would require dynamic reallocation.
The current value is a compromise between memory usage and performance that should cover the majority of GOMAXPROCS values used in the wild.
理想情况下,分桶的个数和保持 GOMAXPROCS 一致是最优解。但是这就会涉及到 go 启动时的动态内存分配。作为运行时应该尽量减少程序负担。而 64 个 bucket 则是内存占用和性能之间的权衡了。
每个 bucket 具体负责管理的 timer 和 go 调度模型 GMP 中 P 有关,代码如下:
func (t *timer) assignBucket() *timersBucket {
id := uint8(getg().m.p.ptr().id) % timersLen
t.tb = &timers[id].timersBucket
return t.tb
}
可以看到,timer 获取其对应的 bucket 时,是根据 golang 的 GMP 调度模型中的 P 的 id 进行取模。而当 GOMAXPROCS > 64, 一个 bucket 将会同时负责管理多个 P 上的 timer。
TimersBucket 里面使用最小堆管理 Timer,但是与我们常见的,使用二叉树来实现最小堆不同,Golang 这里采用了四叉堆 (4-heap) 来实现。这里 Golang 并没有直接给出解释。这里直接贴一段 知乎网友对二叉堆和 N 叉堆的分析。
- 上推节点的操作更快。假如最下层某个节点的值被修改为最小,同样上推到堆顶的操作,N 叉堆需要的比较次数只有二叉堆的 logn 2倍。
- 对缓存更友好。二叉堆对数组的访问范围更大,更加随机,而 N 叉堆则更集中于数组的前部,这就对缓存更加友好,有利于提高性能。
C 语言知名开源网络库 libev,内部既采用了二叉树也采用了四叉堆来实现。它在注释里提到 benchmark,四叉树相比来说缓存更加友好,在 50000 + 个 timer 的场景下,四叉树会有 5% 的性能提升。具体可见 libev/ev.c#L2227
我们通常使用 time.Sleep(1 * time.Second) 来将 goroutine 暂时休眠一段时间。sleep作在底层实现也是基于 timer 实现的。代码在runtime/time.go#L84。有一些比较有意思的地方,单独拿出来讲下。
我们固然也可以这么做来实现 goroutine 的休眠:
timer := time.NewTimer(2 * time.Seconds)
<-timer.C
这么做当然可以。但 golang 底层显然不是这么做的,因为这样有两个明显的额外性能损耗。
既然都可以放在 runtime 里面做。golang 里面做的更加干净:
这个做法和libco的poll实现几乎一样:sleep时切走协程,时间到了就唤醒协程。
分析 timer 的实现,可以明显的看到整个设计的演进,从最开始的全局 timers 对象,到分桶 bucket,以及到 go1.14 最新的 timer 调度。整个过程也可以学习到整个决策的走向和取舍。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!