垃圾回收/Garbage Collection

垃圾回收(Garbage Collection,简称GC)是一种自动内存管理的机制,自动释放不需要的对象,不需要手动释放
垃圾回收器的执行过程被划分为两个半独立的组件:

  • 赋值器(Mutator):这一名称本质上是在指代用户态的代码。因为对垃圾回收器而言,用户态的代码仅仅只是在修改对象之间的引用关系,也就是在对象图(对象之间引用关系的一个有向图)上进行操作。
  • 回收器(Collector):负责执行垃圾回收的代码。

根对象

根对象在垃圾回收的术语中又叫做根集合,它是垃圾回收器在标记过程时最先检查的对象,包括:

  1. 全局变量:程序在编译期就能确定的那些存在于程序整个生命周期的变量。
  2. 执行栈:每个 goroutine 都包含自己的执行栈,这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
  3. 寄存器:寄存器的值可能表示一个指针,参与计算的这些指针可能指向某些赋值器分配的堆内存区块。

    GC 实现方式

    所有的 GC 算法其存在形式可以归结为追踪(Tracing)和引用计数(Reference Counting)这两种形式的混合运用。

    追踪式 GC

    从根对象出发,根据对象之间的引用信息,一步步推进直到扫描完毕整个堆并确定需要保留的对象,从而回收所有可回收的对象。Go、 Java、V8 对 JavaScript 的实现等均为追踪式 GC。追踪式,分为多种不同类型,例如:
  • 标记清扫:从根对象出发,将确定存活的对象进行标记,并清扫可以回收的对象。
  • 标记整理:为了解决内存碎片问题而提出,在标记过程中,将对象尽可能整理到一块连续的内存上。
  • 增量式:将标记与清扫的过程分批执行,每次执行很小的部分,从而增量的推进垃圾回收,达到近似实时、几乎无停顿的目的。
  • 增量整理:在增量式的基础上,增加对对象的整理过程。
  • 分代式:将对象根据存活时间的长短进行分类,存活时间小于某个值的为年轻代,存活时间大于某个值的为老年代,永远不会参与回收的对象为永久代。并根据分代假设(如果一个对象存活时间不长则倾向于被回收,如果一个对象已经存活很长时间则倾向于存活更长时间)对对象进行回收。

    引用计数式 GC

    每个对象自身包含一个被引用的计数器,当计数器归零时自动得到回收。因为此方法缺陷较多,在追求高性能时通常不被应用。Python、Objective-C 等均为引用计数式 GC。

  • 引用计数:根据对象自身的引用计数来回收,当引用计数归零时立即回收。

Go垃圾回收类型
对于 Go 而言,Go 的 GC 目前使用的是无分代(对象没有代际之分)、不整理(回收过程中不对对象进行移动与整理)、并发(与用户代码并发执行)的三色标记清扫算法。原因在于:

  1. 对象整理的优势是解决内存碎片问题以及“允许”使用顺序内存分配器。但 Go 运行时的分配算法基于 tcmalloc,基本上没有碎片问题。 并且顺序内存分配器在多线程的场景下并不适用。Go 使用的是基于 tcmalloc 的现代内存分配算法,对对象进行整理不会带来实质性的性能提升。
  2. 分代 GC 依赖分代假设,即 GC 将主要的回收目标放在新创建的对象上(存活时间短,更倾向于被回收),而非频繁检查所有对象。但 Go 的编译器会通过逃逸分析将大部分新生对象存储在栈上(栈直接被回收),只有那些需要长期存在的对象才会被分配到需要进行垃圾回收的堆中。也就是说,分代 GC 回收的那些存活时间短的对象在 Go 中是直接被分配到栈上,当 goroutine 死亡后栈也会被直接回收,不需要 GC 的参与,进而分代假设并没有带来直接优势。并且 Go 的垃圾回收器与用户代码并发执行,使得 STW 的时间与对象的代际、对象的 size 没有关系。Go 团队更关注于如何更好地让 GC 与用户代码并发执行(使用适当的 CPU 来执行垃圾回收),而非减少停顿时间这一单一目标上。

三色标记法

回收器通过将对象图划分为三种状态来指示其扫描过程,三色抽象规定了三种不同类型的对象,并用不同的颜色表示:

  • 白色对象:在回收开始阶段,所有对象均为白色,当回收结束后,白色对象就是秋后处决名单表,清理掉白色对象。
  • 灰色对象:已经扫描到但未处理完成或者还需要再次处理的,就是一个中间过渡转态
  • 黑色对象:已被回收器访问到的对象,其中所有字段都已被扫描,黑色对象中任何一个指针都不可能直接指向白色对象。

三色标记流程

16d1f7bed619a951.gif
1 首先把所有的对象都放到白色的集合中
image.png

2从根节点开始遍历对象,遍历到的白色对象从白色集合中放到灰色集合中
image.png

3遍历灰色集合中的对象,把灰色对象引用的白色集合的对象放入到灰色集合中,同时把遍历过的灰色集合中的对象放到黑色的集合中
image.png

  • 循环步骤3,直到灰色集合中没有对象
  • 步骤4结束后,白色集合中的对象就是不可达对象,也就是垃圾,进行回收

image.png

image.png

黑色节点全部置 为白色,等待新一轮gc启动
image.png

STW

STW 通常意义上是指代”StoptheWorld” 。在STW阶段,CPU不执行用户代码,全部用于垃圾回收。STW 在垃圾回收过程中为了保证实现的正确性、防止无止境的内存增长等问题而不可避免的需要停止赋值器进一步操作对象图的一段过程。
在这个过程中整个用户代码被停止或者放缓执行, STW 越长,对用户代码造成的影响(例如延迟)就越大,早期 Go 对垃圾回收器的实现中 STW 长达几百毫秒,对时间敏感的实时通信等应用程序会造成巨大的影响。我们来看一个例子:

  1. package main
  2. import (
  3. "runtime"
  4. "time"
  5. )
  6. func main() {
  7. go func() {
  8. for {
  9. }
  10. }()
  11. time.Sleep(time.Millisecond)
  12. runtime.GC()
  13. println("OK")
  14. }

上面的这个程序在 Go 1.14 以前永远都不会输出 OK,其罪魁祸首是进入 STW 这一操作的执行无限制的被延长。

尽管 STW 如今已经优化到了半毫秒级别以下,但这个程序被卡死原因是由于需要进入 STW 导致的。原因在于,GC 在需要进入 STW 时,需要通知并让所有的用户态代码停止,但是 for {} 所在的 goroutine 永远都不会被中断,从而始终无法进入 STW 阶段。实际实践中也是如此,当程序的某个 goroutine 长时间得不到停止,强行拖慢进入 STW 的时机,这种情况下造成的影响(卡死)是非常可怕的。好在自 Go 1.14 之后,这类 goroutine 能够被异步地抢占,从而使得进入 STW 的时间不会超过抢占信号触发的周期,程序也不会因为仅仅等待一个 goroutine 的停止而停顿在进入 STW 之前的操作上。

并发标记清除法的难点

在没有用户态代码并发修改三色抽象的情况下,回收可以正常结束。但是并发回收的根本问题在于,用户态代码在回收过程中会并发地更新对象图,从而造成赋值器和回收器可能对对象图的结构产生不同的认知。这时以一个固定的三色波面作为回收过程前进的边界则不再合理。

我们不妨考虑赋值器写操作的例子:

时序 回收器 赋值器 说明
1 shade(A, gray) 回收器:根对象的子节点着色为灰色对象
2 shade(C, black) 回收器:当所有子节点着色为灰色后,将节点着为黑色
3 C.ref3 = C.ref2.ref1 赋值器:并发的修改了 C 的子节点
4 A.ref1 = nil 赋值器:并发的修改了 A 的子节点
5 shade(A.ref1, gray) 回收器:进一步灰色对象的子节点并着色为灰色对象,这时由于 A.ref1nil,什么事情也没有发生
6 shade(A, black) 回收器:由于所有子节点均已标记,回收器也不会重新扫描已经被标记为黑色的对象,此时 A 被着色为黑色,scan(A) 什么也不会发生,进而 B 在此次回收过程中永远不会被标记为黑色,进而错误地被回收。
  • 初始状态:假设某个黑色对象 C 指向某个灰色对象 A ,而 A 指向白色对象 B;
  • C.ref3 = C.ref2.ref1:赋值器并发地将黑色对象 C 指向(ref3)了白色对象 B;
  • A.ref1 = nil:移除灰色对象 A 对白色对象 B 的引用(ref2);
  • 最终状态:在继续扫描的过程中,白色对象 B 永远不会被标记为黑色对象了(回收器不会重新扫描黑色对象),进而对象 B 被错误地回收。

Go垃圾回收 - 图8

总而言之,并发标记清除中面临的一个根本问题就是如何保证标记与清除过程的正确性。

写屏障机制

写屏障是一个在并发垃圾回收器中才会出现的概念,垃圾回收器的正确性体现在:不应出现对象的丢失,也不应错误的回收还不需要回收的对象。

可以证明,当以下两个条件同时满足时会破坏垃圾回收器的正确性:

  • 条件 1: 赋值器修改对象图,导致某一黑色对象引用白色对象;
  • 条件 2: 从灰色对象出发,到达白色对象的、未经访问过的路径被赋值器破坏。

只要能够避免其中任何一个条件,则不会出现对象丢失的情况,因为:

  • 如果条件 1 被避免,则所有白色对象均被灰色对象引用,没有白色对象会被遗漏;
  • 如果条件 2 被避免,即便白色对象的指针被写入到黑色对象中,但从灰色对象出发,总存在一条没有访问过的路径,从而找到到达白色对象的路径,白色对象最终不会被遗漏。

我们不妨将三色不变性所定义的波面根据这两个条件进行削弱:

强弱三色不变式

强三色不变性

不存在黑色对象引用到白色对象的指针。

弱三色不变性

黑色对象可以引用白色对象,但是白色对象存在其他灰色对象对它的引用,或者可达它的链路上存在着灰色对象。

有两种非常经典的写屏障:Dijkstra 插入屏障和 Yuasa 删除屏障。

Dijkstra 插入屏障

灰色赋值器的 Dijkstra 插入屏障的基本思想是避免满足条件 1:

  1. // 灰色赋值器 Dijkstra 插入屏障
  2. func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
  3. shade(ptr)
  4. *slot = ptr
  5. }
  6. 添加下游对象(当前下游对象slot, 新下游对象ptr) {
  7. //1
  8. 标记灰色(新下游对象ptr)
  9. //2
  10. 当前下游对象slot = 新下游对象ptr
  11. }

场景:

  1. A.添加下游对象(nil, B) //A 之前没有下游, 新添加一个下游对象B, B被标记为灰色
  2. A.添加下游对象(C, B) //A 将下游对象C 更换为B, B被标记为灰色

黑色对象的内存槽有两种位置, . 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.
image.png

image.png

image.png
image.png
image.png
image.png
但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况(如上图的对象9). 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.

image.png
image.png
image.png
最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间在10~100ms间.
image.png

Yuasa 删除屏障

  1. // 黑色赋值器 Yuasa 屏障
  2. func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
  3. shade(*slot)
  4. *slot = ptr
  5. }
  6. 添加下游对象(当前下游对象slot 新下游对象ptr) {
  7. //1
  8. if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
  9. 标记灰色(当前下游对象slot) //slot为被删除对象, 标记为灰色
  10. }
  11. //2
  12. 当前下游对象slot = 新下游对象ptr
  13. }

场景:

  1. A.添加下游对象(B, nil) //A对象,删除B对象的引用。 B被A删除,被标记为灰(如果B之前为白)
  2. A.添加下游对象(B, C) //A对象,更换下游B变成C。 B被A删除,被标记为灰(如果B之前为白)

image.png

image.png
image.png
image.png
image.png
image.png
image.png

降低的回收精度低,一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮,在下一轮GC中被清理掉。

混合写屏障

插入写屏障缺点是:结束时需要STW来重新扫描栈,标记栈上引用的白色对象的存活;
删除写屏障缺点是:回收精度低,GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象。
具体操作:
1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描,无需STW),
2、GC期间,任何在栈上创建的新对象,均为黑色。
3、被删除的对象标记为灰色。
4、被添加的对象标记为灰色。
满足: 变形的弱三色不变式.

  1. // 混合写屏障
  2. func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
  3. shade(*slot)
  4. shade(ptr)
  5. *slot = ptr
  6. }
  7. 添加下游对象(当前下游对象slot, 新下游对象ptr) {
  8. //1
  9. 标记灰色(当前下游对象slot) //只要当前下游对象被移走,就标记灰色
  10. //2
  11. 标记灰色(新下游对象ptr)
  12. //3
  13. 当前下游对象slot = 新下游对象ptr
  14. }

混合写屏障是Gc的一种屏障机制,所以只是当程序执行GC的时候,才会触发这种机制。
image.png
image.png

image.png

image.png

对象被一个栈对象删除引用,成为另一个栈对象的下游
image.png

image.png
image.png
对象被一个堆对象删除引用,成为另一个堆对象的下游
image.png
image.png
image.png

对象从一个栈对象删除引用,成为另一个堆对象的下游
image.png
image.png

image.png

在这个实现中,如果无条件对引用双方进行着色,自然结合了 Dijkstra 和 Yuasa 写屏障的优势,但缺点也非常明显,因为着色成本是双倍的,而且编译器需要插入的代码也成倍增加,随之带来的结果就是编译后的二进制文件大小也进一步增加。为了针对写屏障的性能进行优化,Go 1.10 前后,Go 团队随后实现了批量写屏障机制。其基本想法是将需要着色的指针统一写入一个缓存,每当缓存满时统一对缓存中的所有 ptr 指针进行着色。

GC 的流程

当前版本的 Go 以 STW 为界限,可以将 GC 划分为五个阶段:

阶段 说明 赋值器状态
SweepTermination 清扫终止阶段,为下一个阶段的并发标记做准备工作,启动写屏障 STW
Mark 扫描标记阶段,与赋值器并发执行,写屏障开启 并发
MarkTermination 标记终止阶段,保证一个周期内标记任务完成,停止写屏障 STW
GCoff 内存清扫阶段,将需要回收的内存归还到堆中,写屏障关闭 并发
GCoff 内存归还阶段,将过多的内存归还给操作系统,写屏障关闭 并发

具体而言,各个阶段的触发函数分别为:

Go垃圾回收 - 图39

GC触发

Go 语言中对 GC 的触发时机存在两种形式:

主动触发

通过调用 runtime.GC 来触发 GC,此调用阻塞式地等待当前 GC 运行完毕。

被动触发

被动触发分为两种方式

系统监控

当超过两分钟没有产生任何 GC 时,强制触发 GC。
默认情况下,最长2分钟触发一次GC,这个间隔在src/runtime/proc.go:forcegcperiod变量中被声明:

  1. // forcegcperiod is the maximum time in nanoseconds between garbage
  2. // collections. If we go this long without a garbage collection, one
  3. // is forced to run.
  4. //
  5. // This is a variable for testing purposes. It normally doesn't change.
  6. var forcegcperiod int64 = 2 * 60 * 1e9


步调(Pacing)算法

其核心思想是控制内存增长的比例。

通过 GOGC 或者 debug.SetGCPercent 进行控制(他们控制的是同一个变量,即堆的增长率 $\rho$)。整个算法的设计考虑的是优化问题:如果设上一次 GC 完成时,内存的数量为 $H_m$(heap marked),估计需要触发 GC 时的堆大小 $H_T$(heap trigger),使得完成 GC 时候的目标堆大小 $H_g$(heap goal) 与实际完成时候的堆大小 $H_a$(heap actual)最为接近,即: $\min |H_g - H_a| = \min|(1+\rho)H_m - H_a|$。

Go垃圾回收 - 图40

除此之外,步调算法还需要考虑 CPU 利用率的问题,显然我们不应该让垃圾回收器占用过多的 CPU,即不应该让每个负责执行用户 goroutine 的线程都在执行标记过程。理想情况下,在用户代码满载的时候,GC 的 CPU 使用率不应该超过 25%,即另一个优化问题:如果设 $u_g$为目标 CPU 使用率(goal utilization),而 $u_a$为实际 CPU 使用率(actual utilization),则 $\min|u_g - u_a|$。

求解这两个优化问题的具体数学建模过程我们不在此做深入讨论,有兴趣的读者可以参考两个设计文档:Go 1.5 concurrent garbage collector pacing[5] 和 Separate soft and hard heap size goal[6]。

计算 $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 时候,估计的堆增长率为:


h_t^{(n+1)} = h_t^{(n)} + 0.5 \left[ \frac{H_g^{(n)} - H_a{(n)}} - h_t^{(n)} - \frac{u_a{(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,可以写如下程序进行验证:
  1. package main
  2. import (
  3. "os"
  4. "runtime"
  5. "runtime/trace"
  6. "sync/atomic"
  7. )
  8. var stop uint64
  9. // 通过对象 P 的释放状态,来确定 GC 是否已经完成
  10. func gcfinished() *int {
  11. p := 1
  12. runtime.SetFinalizer(&p, func(_ *int) {
  13. println("gc finished")
  14. atomic.StoreUint64(&stop, 1) // 通知停止分配
  15. })
  16. return &p
  17. }
  18. func allocate() {
  19. // 每次调用分配 0.25MB
  20. _ = make([]byte, int((1<<20)*0.25))
  21. }
  22. func main() {
  23. f, _ := os.Create("trace.out")
  24. defer f.Close()
  25. trace.Start(f)
  26. defer trace.Stop()
  27. gcfinished()
  28. // 当完成 GC 时停止分配
  29. for n := 1; atomic.LoadUint64(&stop) != 1; n++ {
  30. println("#allocate: ", n)
  31. allocate()
  32. }
  33. println("terminate")
  34. }

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

  1. $ go build -o main
  2. $ GODEBUG=gctrace=1 ./main
  3. #allocate: 1
  4. (...)
  5. #allocate: 20
  6. gc finished
  7. 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
  8. scvg: 8 KB released
  9. scvg: inuse: 1, idle: 62, sys: 63, released: 58, consumed: 5 (MB)
  10. terminate

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

  1. 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 次

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

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

  1. $ go build -o main
  2. $ GODEBUG=gctrace=1,gcpacertrace=1 ./main
  3. #allocate: 1
  4. (...)
  5. 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
  6. #allocate: 28
  7. 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
  8. (...)
  9. #allocate: 37
  10. 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
  11. #allocate: 38
  12. 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$

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


\begin{align}
h_t^{(2)} &= h_t^{(1)} + 0.5 \left[ \frac{H_g^{(1)} - H_a{(1)}} - h_t^{(1)} - \frac{u_a{(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 \
\end{align}

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

内存分配&标记清除

目前的 Go 实现中,当 GC 触发后,会首先进入并发标记的阶段。并发标记会设置一个标志,并在 mallocgc 调用时进行检查。当存在新的内存分配时,会暂停分配内存过快的那些 goroutine,并将其转去执行一些辅助标记(Mark Assist)的工作,从而达到放缓继续分配、辅助 GC 的标记工作的目的。

编译器会分析用户代码,并在需要分配内存的位置,将申请内存的操作翻译为 mallocgc 调用,而 mallocgc 的实现决定了标记辅助的实现,其伪代码思路如下:

  1. func mallocgc(t typ.Type, size uint64) {
  2. if enableMarkAssist {
  3. // 进行标记辅助,此时用户代码没有得到执行
  4. (...)
  5. }
  6. // 执行内存分配
  7. (...)
  8. }

GC API

在 Go 中存在数量极少的与 GC 相关的 API,它们是

  • runtime.GC:手动触发 GC
  • runtime.ReadMemStats:读取内存相关的统计信息,其中包含部分 GC 相关的统计信息
  • debug.FreeOSMemory:手动将内存归还给操作系统
  • debug.ReadGCStats:读取关于 GC 的相关统计信息
  • debug.SetGCPercent:设置 GOGC 调步变量
  • debug.SetMaxHeap(尚未发布[10]):设置 Go 程序堆的上限值

GC 的历史及演进

  • Go 1:串行三色标记清扫
  • Go 1.3:并行清扫,标记过程需要 STW,停顿时间在约几百毫秒
  • Go 1.5:并发标记清扫,停顿时间在一百毫秒以内
  • Go 1.6:使用 bitmap 来记录回收内存的位置,大幅优化垃圾回收器自身消耗的内存,停顿时间在十毫秒以内
  • Go 1.7:停顿时间控制在两毫秒以内
  • Go 1.8:混合写屏障,停顿时间在半个毫秒左右
  • Go 1.9:彻底移除了栈的重扫描过程
  • Go 1.12:整合了两个阶段的 Mark Termination,但引入了一个严重的 GC Bug 至今未修(见问题 20),尚无该 Bug 对 GC 性能影响的报告
  • Go 1.13:着手解决向操作系统归还内存的,提出了新的 Scavenger
  • Go 1.14:替代了仅存活了一个版本的 scavenger,全新的页分配器,优化分配内存过程的速率与现有的扩展性问题,并引入了异步抢占,解决了由于密集循环导致的 STW 时间过长的问题

可以用下图直观地说明 GC 的演进历史:

Go垃圾回收 - 图41

在 Go 1 刚发布时的版本中,甚至没有将 Mark-Sweep 的过程并行化,当需要进行垃圾回收时,所有的代码都必须进入 STW 的状态。而到了 Go 1.3 时,官方迅速地将清扫过程进行了并行化的处理,即仅在标记阶段进入 STW。

这一想法很自然,因为并行化导致算法结果不一致的情况仅仅发生在标记阶段,而当时的垃圾回收器没有针对并行结果的一致性进行任何优化,因此才需要在标记阶段进入 STW。对于 Scavenger 而言,早期的版本中会有一个单独的线程来定期将多余的内存归还给操作系统。

Go垃圾回收 - 图42

而到了 Go 1.5 后,Go 团队花费了相当大的力气,通过引入写屏障的机制来保证算法的一致性,才得以将整个 GC 控制在很小的 STW 内,而到了 1.8 时,由于新的混合屏障的出现,消除了对栈本身的重新扫描,STW 的时间进一步缩减。

从这个时候开始,Scavenger 已经从独立线程中移除,并合并至系统监控这个独立的线程中,并周期性地向操作系统归还内存,但仍然会有内存溢出这种比较极端的情况出现,因为程序可能在短时间内应对突发性的内存申请需求时,内存还没来得及归还操作系统,导致堆不断向操作系统申请内存,从而出现内存溢出。

Go垃圾回收 - 图43

到了 Go 1.13,定期归还操作系统的问题得以解决,Go 团队开始将周期性的 Scavenger 转化为可被调度的 goroutine,并将其与用户代码并发执行。而到了 Go 1.14,这一向操作系统归还内存的操作时间进一步得到缩减。

GC存在问题

尽管 Go 团队宣称 STW 停顿时间得以优化到 100 微秒级别,但这本质上是一种取舍。原本的 STW 某种意义上来说其实转移到了可能导致用户代码停顿的几个位置;除此之外,由于运行时调度器的实现方式,同样对 GC 存在一定程度的影响。

目前 Go 中的 GC 仍然存在以下问题:

1. Mark Assist 停顿时间过长

  1. package main
  2. import (
  3. "fmt"
  4. "os"
  5. "runtime"
  6. "runtime/trace"
  7. "time"
  8. )
  9. const (
  10. windowSize = 200000
  11. msgCount = 1000000
  12. )
  13. var (
  14. best time.Duration = time.Second
  15. bestAt time.Time
  16. worst time.Duration
  17. worstAt time.Time
  18. start = time.Now()
  19. )
  20. func main() {
  21. f, _ := os.Create("trace.out")
  22. defer f.Close()
  23. trace.Start(f)
  24. defer trace.Stop()
  25. for i := 0; i < 5; i++ {
  26. measure()
  27. worst = 0
  28. best = time.Second
  29. runtime.GC()
  30. }
  31. }
  32. func measure() {
  33. var c channel
  34. for i := 0; i < msgCount; i++ {
  35. c.sendMsg(i)
  36. }
  37. fmt.Printf("Best send delay %v at %v, worst send delay: %v at %v. Wall clock: %v \n", best, bestAt.Sub(start), worst, worstAt.Sub(start), time.Since(start))
  38. }
  39. type channel [windowSize][]byte
  40. func (c *channel) sendMsg(id int) {
  41. start := time.Now()
  42. // 模拟发送
  43. (*c)[id%windowSize] = newMsg(id)
  44. end := time.Now()
  45. elapsed := end.Sub(start)
  46. if elapsed > worst {
  47. worst = elapsed
  48. worstAt = end
  49. }
  50. if elapsed < best {
  51. best = elapsed
  52. bestAt = end
  53. }
  54. }
  55. func newMsg(n int) []byte {
  56. m := make([]byte, 1024)
  57. for i := range m {
  58. m[i] = byte(n)
  59. }
  60. return m
  61. }

运行此程序我们可以得到类似下面的结果:

  1. $ go run main.go
  2. Best send delay 330ns at 773.037956ms, worst send delay: 7.127915ms at 579.835487ms. Wall clock: 831.066632ms
  3. Best send delay 331ns at 873.672966ms, worst send delay: 6.731947ms at 1.023969626s. Wall clock: 1.515295559s
  4. Best send delay 330ns at 1.812141567s, worst send delay: 5.34028ms at 2.193858359s. Wall clock: 2.199921749s
  5. Best send delay 338ns at 2.722161771s, worst send delay: 7.479482ms at 2.665355216s. Wall clock: 2.920174197s
  6. Best send delay 337ns at 3.173649445s, worst send delay: 6.989577ms at 3.361716121s. Wall clock: 3.615079348s

Go垃圾回收 - 图44

在这个结果中,第一次的最坏延迟时间高达 7.12 毫秒,发生在程序运行 578 毫秒左右。通过 go tool trace 可以发现,这个时间段中,Mark Assist 执行了 7112312ns,约为 7.127915ms;可见,此时最坏情况下,标记辅助拖慢了用户代码的执行,是造成 7 毫秒延迟的原因。

2. Sweep 停顿时间过长

同样还是刚才的例子,如果我们仔细观察 Mark Assist 后发生的 Sweep 阶段,竟然对用户代码的影响长达约 30ms,根据调用栈信息可以看到,该 Sweep 过程发生在内存分配阶段:

Go垃圾回收 - 图45

3. 由于 GC 算法的不正确性导致 GC 周期被迫重新执行

此问题很难复现,但是一个已知的问题,根据 Go 团队的描述,能够在 1334 次构建中发生一次 [15],我们可以计算出其触发概率约为 0.0007496251874。虽然发生概率很低,但一旦发生,GC 需要被重新执行,非常不幸。

4. 创建大量 Goroutine 后导致 GC 消耗更多的 CPU

这个问题可以通过以下程序进行验证:

  1. func BenchmarkGCLargeGs(b *testing.B) {
  2. wg := sync.WaitGroup{}
  3. for ng := 100; ng <= 1000000; ng *= 10 {
  4. b.Run(fmt.Sprintf("#g-%d", ng), func(b *testing.B) {
  5. // 创建大量 goroutine,由于每次创建的 goroutine 会休眠
  6. // 从而运行时不会复用正在休眠的 goroutine,进而不断创建新的 g
  7. wg.Add(ng)
  8. for i := 0; i < ng; i++ {
  9. go func() {
  10. time.Sleep(100 * time.Millisecond)
  11. wg.Done()
  12. }()
  13. }
  14. wg.Wait()
  15. // 现运行一次 GC 来提供一致的内存环境
  16. runtime.GC()
  17. // 记录运行 b.N 次 GC 需要的时间
  18. b.ResetTimer()
  19. for i := 0; i < b.N; i++ {
  20. runtime.GC()
  21. }
  22. })
  23. }
  24. }

其结果可以通过如下指令来获得:

  1. $ go test -bench=BenchmarkGCLargeGs -run=^$ -count=5 -v . | tee 4.txt
  2. $ benchstat 4.txt
  3. name time/op
  4. GCLargeGs/#g-100-12 192µs ± 5%
  5. GCLargeGs/#g-1000-12 331µs ± 1%
  6. GCLargeGs/#g-10000-12 1.22ms ± 1%
  7. GCLargeGs/#g-100000-12 10.9ms ± 3%
  8. GCLargeGs/#g-1000000-12 32.5ms ± 4%

这种情况通常发生于峰值流量后,大量 goroutine 由于任务等待被休眠,从而运行时不断创建新的 goroutine,
旧的 goroutine 由于休眠未被销毁且得不到复用,导致 GC 需要扫描的执行栈越来越多,进而完成 GC 所需的时间越来越长。
一个解决办法是使用 goroutine 池来限制创建的 goroutine 数量。

参考

https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/
https://juejin.im/post/5c62d45ee51d457fa44f4404#heading-18
https://www.jianshu.com/p/bfc3c65c05d1
https://www.jianshu.com/p/4c5a303af470