触发频率及其调步算法

8.3.1 GC 的调控方式

// src/runtime/debug
func SetGCPercent(percent int) int
func SetMaxStack(bytes int) int

GOGC

8.3.2 调步算法及其数学模型

目前触发 GC 的条件使用的是从 Go 1.5 时提出的调步（Pacing）算法，
调步算法是优化并发执行时 GC 的步调，换句话说就是解决什么时候应该触发下一次 GC
的这个问题。

调步算法包含四个部分：

  1. GC 周期所需的扫描估计器
  2. 为用户代码根据堆分配到目标堆大小的时间估计扫描工作量的机制
  3. 用户代码为未充分利用 CPU 预算时进行后台扫描的调度程序
  4. GC 触发比率的控制器

现在我们从两个不同的视角来对这个问题进行建模。

模型的建立

从用户的角度而言，我们希望给定一个给定的增长率，使堆在给定增长率的情况下触发下一次 GC。
这时设 $h_g$ 为目标增长率（即 GOGC / 100），则完成 n 个 GC 周期后标记对象的总大小为：

Hg(n)=(1+hg)Hm(n−1)H_g^{(n)} = (1+h_g) H_m^{(n-1)}

图1：调步算法的模型

这时的 $H_g(n)$ 是作为用户的我们所希望的堆的增长结果，GC 必须将堆的大小限制在此结果以内。

从 GC 的角度而言，我们需要在观察到给定数量的新的内存分配后，开始执行 GC，设触发时刻的堆大小为 $H_T$，
在执行 GC 的期间由于用户代码并发执行，同样会产生一定数量的内存分配，不妨设该次 GC 完成时堆的大小为 $H_a$。
在不同的情况下，一个 GC 周期后得到的实际堆大小既可以大于也可以小于堆大小。但我们的优化还需要考虑这这个因素：

  • 因素1: 我们应该尽可能的使得第 n 次 GC 周期的目标堆大小 $H_a^{(n)} < H_g^{(n)}$ 从而避免不断增加的内存消耗。
  • 因素2: 我们应该尽可能的避免第 n 次 GC 周期的目标堆大小 $H_a^{(n)} - H_g^{(n)}$ 的指过大，从而产生过量的 CPU 消耗，进而导致应用的执行速度减慢。

显然，如果我们没有并行 GC，即需要对用户代码执行 STW，则 GC 期间不会产生新的分配，
问题将变得异常简单：当堆增长到 $H_g^{(n)}$ 时开始执行下一阶段的 GC。
但当需要 GC 并行的与用户代码执行时，我们则需要提前在堆大小为 $H_T$ 时候触发 GC，
以得到最优的 GC 触发条件，则我们可以将合适触发 GC 这个问题转化为以下优化问题：

优化问题1：寻找 $H_T^{(n)}$，使得 $\min |H_g^{(n)} - H_a^{(n)}| = \min |(1+h_g) H_m^{(n-1)} - H_a^{(n)}|$。

而对于第二个因素而言，为了控制 GC 对 CPU 的使用率，并发阶段的 GC 应该尽可能接近 GOMAXPROCS 的 25%。这包括后台收集器中的时间和来自用户代码的富足，但不是写屏障的时间（仅因为计数会增加写屏障的开销）。如果设 $u_g$为目标 CPU 使用率（goal utilization），而 $u_a$为实际 CPU 使用率（actual utilization），于是我们有第二个优化问题：

优化问题2：寻找 $H_T^{(n)}$，同时使得 $\min|u_g^{(n)} - u_a^{(n)}|$。

模型的解

TODO: 求解的具体数学建模过程

综上所述，计算 $H_T$ 的最终结论（从 Go 1.10 时开始 $h_t$ 增加了上界 $0.95 \rho$，从 Go 1.14 开始时 $h_t$ 增加了下界 0.6）是：

  • 设第 n 次触发 GC 时 (n > 1)，估计得到的堆增长率为 $h_t^{(n)}$、运行过程中的实际堆增长率为 $h_a^{(n)}$，用户设置的增长率为 $\rho = \text{GOGC}/100$（ $\rho > 0$）则第 $n+1$ 次出触发 GC 时候，估计的堆增长率为：

ht(n+1)=ht(n)+0.5[Hg(n)−Ha(n)Ha(n)−ht(n)−ua(n)ug(n)(ha(n)−ht(n))]h_t^{(n+1)} = h_t^{(n)} + 0.5 \left[ \frac{H_g^{(n)} - H_a^{(n)}}{H_a^{(n)}} - h_t^{(n)} - \frac{u_a^{(n)}}{u_g^{(n)}} \left( h_a^{(n)} - h_t^{(n)} \right) \right]

  • 特别的，$h_t^{(1)} = 7 / 8$，$u_a^{(1)} = 0.25$，$u_g^{(1)} = 0.3$。第一次触发 GC 时，如果当前的堆小于 $4\rho$ MB，则强制调整到 $4\rho$ MB 时触发 GC

  • 特别的，当 $h_t^{(n)}<0.6$时，将其调整为 $0.6$，当 $h_t^{(n)} > 0.95 \rho$ 时，将其设置为 $0.95 \rho$

  • 默认情况下，$\rho = 1$（即 GOGC = 100），第一次触发 GC 时强制设置触发第一次 GC 为 4MB，

结论的验证

我们可以编写如下程序对我们的求解过程进行验证：

package main

import (
    "os"
    "runtime"
    "runtime/trace"
    "sync/atomic"
)

var stop uint64

// 通过对象 P 的释放状态，来确定 GC 是否已经完成
func gcfinished() *int {
    p := 1
    runtime.SetFinalizer(&p, func(_ *int) {
        println("gc finished")
        atomic.StoreUint64(&stop, 1) // 通知停止分配
    })
    return &p
}

func allocate() {
    // 每次调用分配 0.25MB
    _ = make([]byte, int((1<<20)*0.25))
}

func main() {
    f, _ := os.Create("trace.out")
    defer f.Close()
    trace.Start(f)
    defer trace.Stop()

    gcfinished()

    // 当完成 GC 时停止分配
    for n := 1; atomic.LoadUint64(&stop) != 1; n++ {
        println("#allocate: ", n)
        allocate()
    }
    println("terminate")
}

我们先来验证最简单的一种情况，即第一次触发 GC 时的堆大小：

$ go build -o main
$ GODEBUG=gctrace=1 ./main
#allocate:  1
...
#allocate:  20
gc finished
gc 1 @0.001s 3%: 0.016+0.23+0.019 ms clock, 0.20+0.11/0.060/0.13+0.22 ms cpu, 4->5->1 MB, 5 MB goal, 12 P
scvg: 8 KB released
scvg: inuse: 1, idle: 62, sys: 63, released: 58, consumed: 5 (MB)
terminate

通过这一行数据我们可以看到：

gc 1 @0.001s 3%: 0.016+0.23+0.019 ms clock, 0.20+0.11/0.060/0.13+0.22 ms cpu, 4->5->1 MB, 5 MB goal, 12 P
  1. 程序在完成第一次 GC 后便终止了程序，符合我们的设想
  2. 第一次 GC 开始时的堆大小为 4MB，符合我们的设想
  3. 当标记终止时，堆大小为 5MB，此后开始执行清扫，这时分配执行到第 20 次，即 20*0.25 = 5MB，符合我们的设想

我们将分配次数调整到 50 次

for n := 1; n < 50; n++ {
    println("#allocate: ", n)
    allocate()
}

来验证第二次 GC 触发时是否满足公式所计算得到的值（为 GODEBUG 进一步设置 gcpacertrace=1）：

$ go build -o main
$ GODEBUG=gctrace=1,gcpacertrace=1 ./main
#allocate:  1
...

pacer: H_m_prev=2236962 h_t=+8.750000e-001 H_T=4194304 h_a=+2.387451e+000 H_a=7577600 h_g=+1.442627e+000 H_g=5464064 u_a=+2.652227e-001 u_g=+3.000000e-001 W_a=152832 goalΔ=+5.676271e-001 actualΔ=+1.512451e+000 u_a/u_g=+8.840755e-001
#allocate:  28
gc 1 @0.001s 5%: 0.032+0.32+0.055 ms clock, 0.38+0.068/0.053/0.11+0.67 ms cpu, 4->7->3 MB, 5 MB goal, 12 P

...
#allocate:  37
pacer: H_m_prev=3307736 h_t=+6.000000e-001 H_T=5292377 h_a=+7.949171e-001 H_a=5937112 h_g=+1.000000e+000 H_g=6615472 u_a=+2.658428e-001 u_g=+3.000000e-001 W_a=154240 goalΔ=+4.000000e-001 actualΔ=+1.949171e-001 u_a/u_g=+8.861428e-001
#allocate:  38
gc 2 @0.002s 9%: 0.017+0.26+0.16 ms clock, 0.20+0.079/0.058/0.12+1.9 ms cpu, 5->5->0 MB, 6 MB goal, 12 P

我们可以得到数据：

  • 第一次估计得到的堆增长率为 $h_t^{(1)} = 0.875$
  • 第一次的运行过程中的实际堆增长率为 $h_a^{(1)} = 0.2387451$
  • 第一次实际的堆大小为 $H_a^{(1)}=7577600$
  • 第一次目标的堆大小为 $H_g^{(1)}=5464064$
  • 第一次的 CPU 实际使用率为 $u_a^{(1)} = 0.2652227$
  • 第一次的 CPU 目标使用率为 $u_g^{(1)} = 0.3$

我们据此计算第二次估计的堆增长率：

ht(2)=ht(1)+0.5[Hg(1)−Ha(1)Ha(1)−ht(1)−ua(1)ug(1)(ha(1)−ht(1))]=0.875+0.5[5464064−75776005464064−0.875−0.26522270.3(0.2387451−0.875)]≈0.52534543909h_t^{(2)} = h_t^{(1)} + 0.5 \left[ \frac{H_g^{(1)} - H_a^{(1)}}{H_a^{(1)}} - h_t^{(1)} - \frac{u_a^{(1)}}{u_g^{(1)}} \left( h_a^{(1)} - h_t^{(1)} \right) \right]= 0.875 + 0.5 \left[ \frac{5464064 - 7577600}{5464064} - 0.875 - \frac{0.2652227}{0.3} \left( 0.2387451 - 0.875 \right) \right]\approx 0.52534543909

因为 $0.52534543909 < 0.6\rho = 0.6$，因此下一次的触发率为 $h_t^{2} = 0.6$，与我们实际观察到的第二次 GC 的触发率 0.6 吻合。

8.3.3 实现细节

扫描工作估计器

扫描协助

赋值器协助

触发比率控制器

// gcTrigger 是一个 GC 周期开始的谓词。具体而言，它是一个 _GCoff 阶段的退出条件
type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: 当前时间
    n    uint32 // gcTriggerCycle: 开始的周期数
}

type gcTriggerKind int

const (
    // gcTriggerHeap 表示当堆大小达到控制器计算的触发堆大小时开始一个周期
    gcTriggerHeap gcTriggerKind = iota

    // gcTriggerTime 表示自上一个 GC 周期后当循环超过
    // forcegcperiod 纳秒时应开始一个周期。
    gcTriggerTime

    // gcTriggerCycle 表示如果我们还没有启动第 gcTrigger.n 个周期
    // （相对于 work.cycles）时应开始一个周期。
    gcTriggerCycle
)

// test 报告当前出发条件是否满足，换句话说 _GCoff 阶段的退出条件已满足。
// 退出条件应该在分配阶段已完成测试。
func (t gcTrigger) test() bool {
    // 如果已禁用 GC
    if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
        return false
    }
    // 根据类别做不同判断
    switch t.kind {
    case gcTriggerHeap:
        // 上个周期结束时剩余的加上到目前为止分配的内存 超过 触发标记阶段标准的内存
        // 考虑性能问题，对非原子操作访问 heap_live 。如果我们需要触发该条件，
        // 则所在线程一定会原子的写入 heap_live，从而我们会观察到我们的写入。
        return memstats.heap_live >= memstats.gc_trigger
    case gcTriggerTime:
        if gcpercent < 0 { // 因为允许在运行时动态调整 gcpercent，因此需要额外再检查一遍
            return false
        }
        // 计算上次 gc 开始时间是否大于强制执行 GC 周期的时间
        lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
        return lastgc != 0 && t.now-lastgc > forcegcperiod // 两分钟
    case gcTriggerCycle:
        // 进行测试的周期 t.n 大于实际触发的，需要进行 GC 则通过测试
        return int32(t.n-work.cycles) > 0
    }
    return true
}

TODO:

type mstats struct {
    ...
    last_gc_nanotime uint64 // 上次 gc (monotonic 时间)
    ...

    // triggerRatio is the heap growth ratio that triggers marking.
    //
    // E.g., if this is 0.6, then GC should start when the live
    // heap has reached 1.6 times the heap size marked by the
    // previous cycle. This should be ≤ GOGC/100 so the trigger
    // heap size is less than the goal heap size. This is set
    // during mark termination for the next cycle's trigger.
    triggerRatio float64

    // gc_trigger 指触发标记阶段的堆大小
    //
    // 当 heap_live ≥ gc_trigger 时，标记阶段将开始执行
    // 它同样用来表示必须完成的成比例清扫时的堆大小。
    //
    // 该字段在 triggerRatio 在标记终止阶段为下一个周期的触发器进行计算。
    gc_trigger uint64

    // heap_live 是 GC 认为的实际字节数。即：最近一次 GC 保留的加上从那之后分配的字节数。
    // heap_live <= heap_alloc ，因为 heap_alloc 包括尚未扫描的未标记对象
    // （因此在我们扫描时分配和向下），而 heap_live 不包含这些对象（因此只在 GC 之间上升）。
    //
    // 该字段是在没有锁的情况下原子更新的。
    // 为了减少竞争，只有在从 mcentral 获取 span 时才会更新，
    // 并且此时它会计算该 span 中的所有未分配的插槽（将在该 mcache 从该 mcentral 获取另一个 span 之前分配）。
    // 因此，它对 “真正的” 实时堆大小的估计略微偏高了。之所以高估而非低估的原因是
    // 1) 在必要时提前触发 GC 2) 这会导致保守的 GC 率而而非过低的 GC 率。
    //
    // 读取同样应该是原子的（或在 STW 期间）。
    //
    // 每当更新该字段时，请调用 traceHeapAlloc() 和 gcController.revise()
    heap_live uint64

    (>..)

    // heap_marked 表示前一个 GC 中标记的字节数。标记终止阶段结束后，heap_live == heap_marked,
    // 与 heap_live 不同的是，heap_marked 在下一个 mark_termination 之前都不会发生变化
    heap_marked uint64
}

//go:linkname setGCPercent runtime/debug.setGCPercent
func setGCPercent(in int32) (out int32) {
    lock(&mheap_.lock)
    out = gcpercent
    if in < 0 {
        in = -1
    }
    gcpercent = in
    heapminimum = defaultHeapMinimum * uint64(gcpercent) / 100
    gcSetTriggerRatio(memstats.triggerRatio) // 更新步调来响应 gcpercent 变化
    unlock(&mheap_.lock)
    ...
    return out
}
func gcSetTriggerRatio(triggerRatio float64) {
    // Compute the next GC goal, which is when the allocated heap
    // has grown by GOGC/100 over the heap marked by the last
    // cycle.
    goal := ^uint64(0)
    if gcpercent >= 0 {
        goal = memstats.heap_marked + memstats.heap_marked*uint64(gcpercent)/100
    }

    // Set the trigger ratio, capped to reasonable bounds.
    if triggerRatio < 0 {
        // This can happen if the mutator is allocating very
        // quickly or the GC is scanning very slowly.
        triggerRatio = 0
    } else if gcpercent >= 0 {
        // Ensure there's always a little margin so that the
        // mutator assist ratio isn't infinity.
        maxTriggerRatio := 0.95 * float64(gcpercent) / 100
        if triggerRatio > maxTriggerRatio {
            triggerRatio = maxTriggerRatio
        }
    }
    memstats.triggerRatio = triggerRatio

    // 根据触发器比率来计算绝对的 GC 触发器
    //
    // 当分配的堆的大小超过标记的堆大小时，我们触发下一个 GC 循环。
    trigger := ^uint64(0)
    if gcpercent >= 0 {
        trigger = uint64(float64(memstats.heap_marked) * (1 + triggerRatio))
        // 小于最小堆大小时不触发
        minTrigger := heapminimum
        if !isSweepDone() { // 即 mheap_.sweepdone != 0
            // Concurrent sweep happens in the heap growth
            // from heap_live to gc_trigger, so ensure
            // that concurrent sweep has some heap growth
            // in which to perform sweeping before we
            // start the next GC cycle.
            sweepMin := atomic.Load64(&memstats.heap_live) + sweepMinHeapDistance
            if sweepMin > minTrigger {
                minTrigger = sweepMin
            }
        }
        if trigger < minTrigger {
            trigger = minTrigger
        }
        ...
        if trigger > goal {
            // The trigger ratio is always less than GOGC/100, but
            // other bounds on the trigger may have raised it.
            // Push up the goal, too.
            goal = trigger
        }
    }

    // Commit to the trigger and goal.
    memstats.gc_trigger = trigger
    memstats.next_gc = goal
    ...

    // Update mark pacing.
    if gcphase != _GCoff {
        gcController.revise()
    }

    // Update sweep pacing.
    if isSweepDone() {
        mheap_.sweepPagesPerByte = 0
    } else {
        // Concurrent sweep needs to sweep all of the in-use
        // pages by the time the allocated heap reaches the GC
        // trigger. Compute the ratio of in-use pages to sweep
        // per byte allocated, accounting for the fact that
        // some might already be swept.
        heapLiveBasis := atomic.Load64(&memstats.heap_live)
        heapDistance := int64(trigger) - int64(heapLiveBasis)
        // Add a little margin so rounding errors and
        // concurrent sweep are less likely to leave pages
        // unswept when GC starts.
        heapDistance -= 1024 * 1024
        if heapDistance < _PageSize {
            // Avoid setting the sweep ratio extremely high
            heapDistance = _PageSize
        }
        pagesSwept := atomic.Load64(&mheap_.pagesSwept)
        sweepDistancePages := int64(mheap_.pagesInUse) - int64(pagesSwept)
        if sweepDistancePages <= 0 {
            mheap_.sweepPagesPerByte = 0
        } else {
            mheap_.sweepPagesPerByte = float64(sweepDistancePages) / float64(heapDistance)
            mheap_.sweepHeapLiveBasis = heapLiveBasis
            // Write pagesSweptBasis last, since this
            // signals concurrent sweeps to recompute
            // their debt.
            atomic.Store64(&mheap_.pagesSweptBasis, pagesSwept)
        }
    }

    gcPaceScavenger()
}
最后编辑: kuteng  文档更新时间: 2021-10-19 14:31   作者：kuteng