golang源码阅读之定时器以及避坑指南

notokoy · · 566 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

欢迎访问我的个人网站获取更佳阅读排版体验: 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<<63 - 1
    }
    // 最小堆插入操作
    t.i = len(tb.t)
    tb.t = append(tb.t, t)
    if !siftupTimer(tb.t, t.i) {
        return false
    }
    // 下标为0,说明该timer的触发时间为当前桶中最早的
    if t.i == 0 {
        // 桶协程在sleep,唤醒它
        if tb.sleeping {
            tb.sleeping = false
            notewakeup(&tb.waitnote)
        }
        // 桶协程被挂起了,重新调度
        if tb.rescheduling {
            tb.rescheduling = false
            goready(tb.gp, 0)
        }
    }
    // 如果timer所属的桶还没有创建,创建并开启桶协程
    if !tb.created {
        tb.created = true
        go timerproc(tb)
    }
    return true
}

// 桶协程,注意,这里有两层for循环,最外面的for是永远不会退出的
func timerproc(tb *timersBucket) {
    tb.gp = getg()
    for {
        // 进互斥锁
        lock(&tb.lock)
        // 睡眠标志修改
        tb.sleeping = false
        // 获取当前时间
        now := nanotime()
        delta := int64(-1)
        for {
            // 如果桶内没有timer,直接退出内层for
            if len(tb.t) == 0 {
                delta = -1
                break
            }
            // 获取最早触发timer,并检查是否到达触发时间
            t := tb.t[0]
            delta = t.when - now
            // 还没到时间,直接退出内层for
            if delta > 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 || faketime > 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 < 0 || 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
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:notokoy

查看原文:golang源码阅读之定时器以及避坑指南

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

566 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传