Golang 是如何GC的？

作者: 齐舞647 | 来源:发表于2022-04-05 16:18 被阅读0次

一、什么是 GC ?

GC：垃圾回收（Garbage Collection）是一种自动管理内存的机制。传统的编程语言（C/C++）中，释放无用变量内存空间是程序员手动释放，存在内存泄漏或者释放不该释放内存等问题；为了解决这个问题，后续的语言（oc/swift/java/python/php/golang 等）都引入了语言层面的自动内存管理，语言使用者无需对内存进行手动释放，内存释放由虚拟机（virtual machine）或者运行时（runtime）来对不再使用的内存资源进行自动回收。

Golang GC 的发展史

go1.1，串行三色清扫。
go1.3，提高了垃圾回收的精确度。
go1.4，之前版本的runtime大部分是使用C写的，这个版本大量使用Go进行了重写，让GC有了扫描stack的能力，进一步提高了垃圾回收的精确度。
go1.5，目标是降低GC延迟，采用了并发标记和并发清除，三色标记，write barrier，以及实现了更好的回收器调度，设计文档1，文档2，以及2015 版的Go talk。
go1.6，小优化，当程序使用大量内存时，GC暂停时间有所降低。
go1.7，小优化，当程序有大量空闲goroutine，stack大小波动比较大时，GC暂停时间有显著降低。
go1.8，write barrier切换到hybrid write barrier，以消除STW中的re-scan，把STW的最差情况降低到50us，设计文档。
go1.9，提升指标比较多，（1）过去 runtime.GC, debug.SetGCPercent, 和 debug.FreeOSMemory都不能触发并发GC，他们触发的GC都是阻塞的，go1.9可以了，变成了在垃圾回收之前只阻塞调用GC的goroutine。（2）debug.SetGCPercent只在有必要的情况下才会触发GC。
go.1.10，小优化，加速了GC，程序应当运行更快一点点。
go1.12，显著提高了堆内存存在大碎片情况下的sweeping性能，能够降低GC后立即分配内存的延迟。
go1.13，着手解决向操作系统归还内存的，提出了新的 Scavenger
go1.14，替代了仅存活了一个版本的 Scavenger，全新的页分配器，优化分配内存过程的速率与现有的扩展性问题，并引入了异步抢占，解决了由于密集循环导致的 STW 时间过长的问题
go1.15，删除了一些GC元数据和一些无用的类型元数据，Go 1.15编译出的二进制文件size会减少5%左右。
......

主要版本变化：

go-gc.png

1.5 版本以及以后版本的GC 主要分为四个阶段，其中标记和清理都是并发执行的，但是标记阶段的前后需要使用STW来做GC的准备工作和栈的rescan（这也是1.8的优化点）。

1.8 版本引入混合屏障，最小化第一次STW，写入屏障和删除屏障各有优缺点，Dijkstra写入写屏障在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；Yuasa的删除写屏障则需要在GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW。Go1.8版本引入的混合写屏障结合了Yuasa的删除写屏障和Dijkstra的写入写屏障，结合了两者的优点。

二、常见的 GC 算法

1. 引用计数法

根据对象自身的引用计数来回收，当引用计数归零时进行回收，但是计数频繁更新会带来更多开销，且无法解决循环引用的问题。
代表：Objective-C、Swift

优点：简单直接，回收速度快
缺点：需要额外的空间存放计数，无法处理循环引用的情况；

2. 标记清除法

标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。

标记清除法.png

优点：简单直接，速度快，适合可回收对象不多的场景
缺点：会造成不连续的内存空间（内存碎片），导致有大的对象创建的时候，明明内存中总内存是够的，但是空间不是连续的造成对象无法分配；

3. 复制法

复制法将内存分为大小相同的两块，每次使用其中的一块，当这一块的内存使用完后，将还存活的对象复制到另一块去，然后再把使用的空间一次清理掉。

复制法.png

优点：解决了内存碎片的问题，每次清除针对的都是整块内存，但是因为移动对象需要耗费时间，效率低于标记清除法；
缺点：有部分内存总是利用不到，资源浪费，移动存活对象比较耗时，并且如果存活对象较多的时候，需要担保机制确保复制区有足够的空间可完成复制；

4. 标记整理

标记过程同标记清除法，结束后将存活对象压缩至一端，然后清除边界外的内容。

标记整理.png

优点：解决了内存碎片的问题，也不像标记复制法那样需要担保机制，存活对象较多的场景也使适用；
缺点：性能低，因为在移动对象的时候不仅需要移动对象还要维护对象的引用地址，可能需要对内存经过几次扫描才能完成；

5. 分代式

将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。

三、Golang 选择的 GC 算法

Golang GC 算法使用的是无无分代（对象没有代际之分）、不整理（回收过程中不对对象进行移动与整理）、并发（与用户代码并发执行）的三色标记清扫算法。
原因在于：

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

1. 三色标记法的原理

三色标记法将对象分为三类，并用不同的颜色相称：

白色对象（可能死亡）：未被回收器访问到的对象。在回收开始阶段，所有对象均为白色，当回收结束后，白色对象均不可达。
灰色对象（波面）：已被回收器访问到的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们可能还指向白色对象。
黑色对象（确定存活）：已被回收器访问到的对象，其中所有字段都已被扫描，黑色对象中任何一个指针都不可能直接指向白色对象。

标记过程如下：

第一步：起初所有的对象都是白色的；
第二步：从根对象出发扫描所有可达对象，标记为灰色，放入待处理队列；
第三步：从待处理队列中取出灰色对象，将其引用的对象标记为灰色并放入待处理队列中，自身标记为黑色；
重复第三步，直到待处理队列为空，此时白色对象即为不可达的“垃圾”，回收白色对象；

go-gc.gif

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

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

2. 屏障机制

2.1 STW

STW 是Start/Stop The World的缩写。通常意义上指的是从 Stop The World 到 Start The World 这一段时间间隔。垃圾回收过程中为了保证准确性、防止无止境的内存增长等问题而不可避免的需要停止赋值器进一步操作对象图以完成垃圾回收。STW时间越长，对用户代码造成的影响越大。

2.2 No STW 存在的问题

假设下面的场景，已经被标记为灰色的对象2，未被标记的对象3被对象2用指针p引用；此时已经被标记为黑色的对象4创建指针q 指向未被标记的对象3，同时对象2将指针p移除；对象4已经被标记为黑色，对象3未被引用，对象2删除与对象3的引用，导致最后对象3被误清除；

三色标记法，不启动STW - 图1

三色标记法，不启动STW - 图2

三色标记法，不启动STW - 图3

三色标记法，不启动STW - 图4

三色标记法，不启动STW - 图5

垃圾回收的原则是不应出现对象的丢失，也不应错误的回收还不需要回收的对象。如果同时满足下面两个条件会破坏回收器的正确性：
- 条件 1: 赋值器修改对象图，导致某一黑色对象引用白色对象；（通俗的说就是A突然持有了B的指针，而B在并发标记的过程中已经被判定为白色对象要被清理掉的）
- 条件 2: 从灰色对象出发，到达白色对象且未经访问过的路径被赋值器破坏；（通俗的说就是A持有B的指针，这个持有关系被释放）
只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：
- 如果“条件 1”被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
- 如果“条件 2”被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

可能的解决方法：整个过程STW，浪费资源，且对用户程序影响较大，由此引入了屏障机制；

2.3 屏障机制

把回收器视为对象，把赋值器视为影响回收器这一对象的实际行为（即影响 GC 周期的长短），从而引入赋值器的颜色：

黑色赋值器：已经由回收器扫描过，不会再次对其进行扫描。
灰色赋值器：尚未被回收器扫描过或尽管已经扫描过，但仍需要重新扫描。

2.3.1 插入屏障（Dijkstra）- 灰色赋值器

写入前，对指针所要指向的对象进行着色

// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) //先将新下游对象 ptr 标记为灰色
    *slot = ptr
}

//说明：
添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //step 1
  标记灰色(新下游对象ptr)   
  
  //step 2
  当前下游对象slot = 新下游对象ptr                    
}

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

避免条件1（赋值器修改对象图，导致某一黑色对象引用白色对象；）因为在对象A 引用对象B 的时候，B 对象被标记为灰色

Dijkstra 插入屏障的好处在于可以立刻开始并发标记。但存在两个缺点：

由于 Dijkstra 插入屏障的“保守”，在一次回收过程中可能会残留一部分对象没有回收成功，只有在下一个回收过程中才会被回收；
在标记阶段中，每次进行指针赋值操作时，都需要引入写屏障，这无疑会增加大量性能开销；为了避免造成性能问题，Go 团队在最终实现时，没有为所有栈上的指针写操作，启用写屏障，而是当发生栈上的写操作时，将栈标记为灰色，但此举产生了灰色赋值器，将会需要标记终止阶段 STW 时对这些栈进行重新扫描。

三色标记并发，插入屏障 - 图1

三色标记并发，插入屏障 - 图2

三色标记并发，插入屏障 - 图3

三色标记并发，插入屏障 - 图4

三色标记并发，插入屏障 - 图5

三色标记并发，插入屏障 - 图6

三色标记并发，插入屏障 - 图7

三色标记并发，插入屏障 - 图8

三色标记并发，插入屏障 - 图9

三色标记并发，插入屏障 - 图10

特点：在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈

2.3.2 删除屏障（Yuasa）- 黑色赋值器

写入前，对指针所在对象进行着色

// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) 先将*slot标记为灰色
    *slot = ptr
}

//说明：
添加下游对象(当前下游对象slot， 新下游对象ptr) {
  //step 1
  if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
          标记灰色(当前下游对象slot)     //slot为被删除对象， 标记为灰色
  }  
  //step 2
  当前下游对象slot = 新下游对象ptr
}

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

避免条件2（从灰色对象出发，到达白色对象的、未经访问过的路径被赋值器破坏），因为被删除对象，如果自身是灰色或者白色，则被标记为灰色。

GC三色标记并发：删除屏障 - 图1

GC三色标记并发：删除屏障 - 图2

GC三色标记并发：删除屏障 - 图3

GC三色标记并发：删除屏障 - 图4

GC三色标记并发：删除屏障 - 图5

GC三色标记并发：删除屏障 - 图6

GC三色标记并发：删除屏障 - 图7

特点：标记结束不需要STW，但是回收精度低，GC 开始时STW 扫描堆栈记录初始快照，保护开始时刻的所有存活对象；且容易产生“冗余”扫描；

2.3.3 混合屏障

大大缩短了 STW 时间

GC 开始将栈上的对象全部扫描并标记为黑色；
GC 期间，任何在栈上创建的新对象，均为黑色；
被删除的堆对象标记为灰色；
被添加的堆对象标记为灰色；

// 混合写屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)
    shade(ptr)
    *slot = ptr
}

混合屏障 - 图1

混合屏障 - 图2

场景一：对象被一个堆对象删除引用，成为栈对象的下游

由于屏障的作用，对象7不会被误删除；

混合屏障 - 场景1 - 图1

混合屏障 - 场景1 - 图2

场景二：对象被一个栈对象删除引用，成为栈对象的下游

混合屏障 - 场景2 - 图1

混合屏障 - 场景2 - 图2

混合屏障 - 场景2 - 图3

场景三：对象被一个堆对象删除引用，成为堆对象的下游

混合屏障 - 场景3 - 图1

混合屏障 - 场景3 - 图2

混合屏障 - 场景3 - 图3

场景四：对象被一个栈对象删除引用，成为另一个堆对象的下游

混合屏障 - 场景4 - 图1

混合屏障 - 场景4 - 图2

混合屏障 - 场景4 - 图3

Golang 中的混合屏障结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各goroutine的栈，使其变黑并一直保持，标记结束后，因为栈空间在扫描后始终是黑色的，无需进行re-scan，减少了STW 的时间。

3. Go GC 流程

3.1 标记清理

Marking setup

为了打开写屏障，必须停止每个goroutine，让垃圾收集器观察并等待每个goroutine进行函数调用，等待函数调用是为了保证goroutine停止时处于安全点。

set up

// 如果goroutine4 处于如下循环中，运行时间取决于slice numbers的大小
func add(numbers []int) int {
    var v int
    for _, n := range numbers {
             v += n
     }
     return v
}

下面的代码中，由于for{} 循环所在的goroutine 永远不会中断，导致始终无法进入STW阶段，资源浪费；Go 1.14 之后，此类goroutine 能被异步抢占，使得进入STW的时间不会超过抢占信号触发的周期，程序也不会因为仅仅等待一个goroutine的停止而停顿在进入STW之前的操作上。

func main() {
    go func() {
        for {
        }
    }()
    time.Sleep(time.Milliecond)
    runtime.GC()
    println("done")
}

golang 不同版本GC STW时间关系

Marking

一旦写屏障打开，垃圾收集器就开始标记阶段，垃圾收集器所做的第一件事是占用25%CPU。

标记阶段需要标记在堆内存中仍然在使用中的值。首先检查所有现goroutine的堆栈，以找到堆内存的根指针。然后收集器必须从那些根指针遍历堆内存图，标记可以回收的内存。

当存在新的内存分配时，会暂停分配内存过快的那些 goroutine，并将其转去执行一些辅助标记（Mark Assist）的工作，从而达到放缓继续分配、辅助 GC 的标记工作的目的。

marking-1

marking-2

Mark 终止

关闭写屏障，执行各种清理任务（STW - optional）

Mark 终止-1

Mark 终止-2

Sweep（清理）

清理阶段用于回收标记阶段中标记出来的可回收内存。当应用程序goroutine尝试在堆内存中分配新内存时，会触发该操作，清理导致的延迟和吞吐量降低被分散到每次内存分配时。

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

问：清除阶段出现新对象：

清除阶段是扫描整个堆内存，可以知道当前清除到什么位置，创建的新对象判定下，如果新对象的指针位置已经被扫描过了，那么就不用作任何操作，不会被误清除，如果在当前扫描的位置的后面，把该对象的颜色标记为黑色，这样就不会被误清除了

问：什么时候进行清理？

主动触发（runtime.GC()）被动触发（GC百分比、定时）

3.2 GC 百分比

运行时中有GC 百分比的配置选项，默认情况下为100。此值表示在下一次垃圾收集必须启动之前可以分配多少新内存的比率。将GC百分比设置为100意味着：基于在垃圾收集完成后标记为活动的堆内存量，下次垃圾收集前，堆内存使用可以增加100%。

3.3 GC 过程演示

演示一个GC过程，并输出相关信息，使用GODEBUG变量生成GC trace

func gcfinished() *int {
   p := 1
   runtime.SetFinalizer(&p, func(_ *int) {
      println("gc finished")
      atomic.StoreUint64(&stop, 1) // 通知停止分配
   })
   return &p
}
func allocate() {
   _ = 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; n < 50; n++ {
      println("#allocate: ", n)
      allocate()
   }
   println("terminate")
}

gc演示

gc 1      : 第一个GC周期
@0.001s   : 从程序开始运行到第一次GC时间为0.001 秒
6%        : 此次GC过程中CPU 占用率

wall clock
 0.037+0.18+0.045 ms clock
0.037 ms  : STW，Marking Start, 开启写屏障
0.18 ms   : Marking阶段
0.945 ms  : STW，Marking终止，关闭写屏障

CPU time
0.60+0.077/0.056/0.12+0.72 ms cpu
0.60 ms   : STW，Marking Start
0.077 ms  : 辅助标记时间
0.056 ms  : 并发标记时间
0.12 ms   : GC 空闲时间
0.72 ms   : Mark 终止时间

4->4->0 MB， 5 MB goal
4 MB      ：标记开始时，堆大小实际值
4 MB      ：标记结束时，堆大小实际值
0 MB      ：标记结束时，标记为存活对象大小
5 MB      ：标记结束时，堆大小预测值

16 P
16P       ：本次GC过程中使用的goroutine 数量

第一次堆增长率 ：h_t=+8.750000e-001
第一次的运行过程中的实际堆增长率为：h_a=+1.321777e+000
第一次实际的堆大小为：5193728
第一次目标的堆大小：5439488
第一次的 CPU 实际使用率为：u_a=+2.702135e-001
第一次的 CPU 目标使用率为：u_g=+3.000000e-001

四、关注指标与调优示例

4.1 关注指标

Go 的 GC 被设计为成比例触发、大部分工作与赋值器并发、不分代、无内存移动且会主动向操作系统归还申请的内存。因此最主要关注的、能够影响赋值器的性能指标有：

CPU 利用率：回收算法会在多大程度上拖慢程序？有时候，这个是通过回收占用的 CPU 时间与其它 CPU 时间的百分比来描述的。
GC 停顿时间：回收器会造成多长时间的停顿？目前的 GC 中需要考虑 STW 和 Mark Assist 两个部分可能造成的停顿。
GC 停顿频率：回收器造成的停顿频率是怎样的？目前的 GC 中需要考虑 STW 和 Mark Assist 两个部分可能造成的停顿。
GC 可扩展性：当堆内存变大时，垃圾回收器的性能如何？但大部分的程序可能并不一定关心这个问题。

4.2 调优示例

4.2.1 合理化内存分配的速度、提高赋值器的 CPU 利用率

goroutine 的执行时间占其生命周期总时间非常短的一部分，但大部分时间都花费在调度器的等待上了，说明同时创建大量 goroutine 对调度器产生的压力确实不小，我们不妨将这一产生速率减慢，一批一批地创建 goroutine。

func concat() {
   for n := 0; n < 100; n++ {
      for i := 0; i < 8; i++ {
         go func() {
            s := "Go GC"
            s += " " + "Hello"
            s += " " + "World"
            _ = s
         }()
      }
   }
}

//改进
func concat() {
   wg := sync.WaitGroup{}
   for n := 0; n < 100; n++ {
      wg.Add(8)
      for i := 0; i < 8; i++ {
         go func() {
            s := "Go GC"
            s += " " + "Hello"
            s += " " + "World"
            _ = s
            wg.Done()
         }()
      }
      wg.Wait()
   }
}

4.2.2 降低并复用已经申请的内存

newBuf()产生的申请的内存过多, sync.Pool 是内存复用的一个最为显著的例子

func newBuf() []byte {
   return make([]byte, 10<<20)
}
b := newBuf()

//改进
var bufPool = sync.Pool{
    New: func() interface{} {
        return make([]byte, 10<<20)
    },
}
b := bufPool.Get().([]byte)

4.2.3 调整 GOGC

降低收集器的启动频率（提高GC百分比）无法帮助垃圾收集器更快完成收集工作。降低频率会导致垃圾收集器在收集期间完成更多的工作。可以通过减少新分配对象数量来帮助垃圾收集器更快完成收集工作。

4.3 小结

控制内存分配的速度，限制 goroutine 的数量，从而提高赋值器对 CPU 的利用率。
减少并复用内存，例如使用 sync.Pool 来复用需要频繁创建临时对象，例如提前分配足够的内存来降低多余的拷贝。
需要时，增大 GOGC 的值，降低 GC 的运行频率。

4.4 CPU 内存占用过高问题排查

导出智能问答的数据：导出数据时，为每个app id开了一个协程（由各自的协程获取数据，数据获取完成后，协程将这些数据生成sheet，然后flush进Excel文件），等待每个协程都运行完成后，生成最终的导出文件，上传到tos。在此过程中，每个协程都申请了较大的堆资源用于数据存储数据和生成sheet，从而导致内存升高。

参考：

【1】Golang三色标记、混合写屏障GC模式图文全分析
【2】Golang 三色标记
【3】The Journey of Go's Garbage Collector
【4】Garbage Collection In Go
【5】Go垃圾回收
【6】Go内存分配和管理
【7】GC的认识
【8】如何做Go性能分析
【9】Golang GC 字节分享