Golang中的GC

Posted on Edited on In Views:
很多语言内存管理需要手动实现，而不是全部交由操作系统实现。内存管理的核心就是释放那些不会被使用的内存，根据内存被引用，或者变量是否被引用。

内存回收实现方式

现代高级编程语言管理内的方式分为两种：自动和手动。

  • 手动：

    像C、C++等编程语言使用手动管理内存的方式，编写代码过程中需要主动申请或者释放内存；

  • 自动：

    像PHP、Java和Go等语言使用自动的内存管理系统，有内存分配器和垃圾回收器来代为分配和回收内存

image-20220918204112669

主流的GC形式：

  • 追踪式垃圾回收

    从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆，并确定需要保留的对象，从而回收所有可回收的对象。Golang、Java用的是这种。

  • 引用计数

    每个对象包含被引用的计数器，计数器归零时自动回收。Python用的是这种。

追踪式实现方式

  • 标记清扫：从根对象出发，递归获取引用，将确定存活的对象进行标记，并清扫可以回收的对象
  • 标记整理：解决内存碎片的问题，标记过程中，将对象尽可能整理到一块连续的内存上
  • 增量式：将标记与清扫过程分批执行，每次执行很小的部分，从而增量的推进垃圾回收，达到近似实时、几乎无停顿的目的
  • 增量整理：在增量的基础上，增加对对象的整理过程
  • 分代式：将对象根据时间长短进行分类，通过存活时间分为年轻代、老年代、永久代，根据分代式假设对对象进行回收

Golang使用的GC是无分代（golang的编译器会通过逃逸分析，将大部分新生对象存储在栈上，只有那些需要长期存在的对象才会被分配到需要进行垃圾回收的堆中。对于在堆上对象的分代没有优势，分代优势在频繁分配的对象上，而这些对象通常被栈管理）、不整理（golang内存分配基于tcmalloc的现代内存分配算法，没有碎片问题）、并发的三色标记清扫算法。通过独立的进程执行，会搜索不再使用的变量，将其释放，需要注意GC在运行时会占用机器资源。

GC是自动的，也可以手动显式执行。

Mark & Sweep

标记和清扫

image-20220918204450757

STW：

可以是stop the world的缩写，也可以是start the world的缩写，指从stop the world阶段到start the world阶段的时间间隔。STW在垃圾回收过程中为了保证实现的准确性、防止无止境的内存增长等问题而不可避免的需要停止赋值进一步操作对象的一段过程。

stop the world，GC的一些阶段需要停止所有的mutator（应用程序）以确定当前的引用关系。这边是很多人对GC担心的来源，这也是GC算法优化的重点。

Root：

根对象是mutator不需要通过其他对象就可以直接访问到的对象。比如全局对象，栈对象中的数据等。通过Root对象可以追踪到其他存活的对象。例如上图中Root set对象，通过跟对象寻找到应用对象，清除E和F对象。

Mark Sweep两个阶段：标记（Mark）和清除（Sweep）两个阶段，所以也叫Mark-Sweep垃圾回收算法。

这个算法就是严格按照追踪式算法的思路来实现：

image70

  1. Stop the World
  2. Mark：通过Root和Root直接间接访问到的对象，来寻找所有可达的对象，并进行标记
  3. Sweep：对堆对象迭代，已标记的对象置位标记。所有未标记的对象加入freelist，可用于再分配。
  4. Start the World

这个算法最大的问题是GC执行期间需要把整个程序完全暂停，朴素的Mark Sweep是整体STW，并且分配速度慢，内存碎片率高。

在Go 1.1版本，STW阶段（从stop the world 到start the world）可能需要秒级。

标记过程需要STW，因为对象引用关系如果在标记阶段做了修改，会影响标记结果的正确性。

在1.3版本，引入并发GC，相比1.1版本，将sweep的过程移动到STW之后，减少STW的时间。

  • 每个mark或sweep本身是多个线程（协程）执行的（concurrent并行的）
  • mutator 和collector同时运行（background应用程序和收集器同时运行，收集器在后台运行）

concurrent这一层是比较好实现的，GC时整体进行STW，那么对象引用关系不会再改变，对mark或者sweep任务进行分块，就能多个线程concurrent执行任务mark或sweep。

background这一层，也就是说mutator和mark，sweep同时运行，相对复杂一点

  • 1.3以前的版本使用标记-清扫的方式，整个过程都需要STW
  • 1.3版本分离了标记和清扫的操作，标记过程STW，清扫过程并发执行

background sweep是比较容易实现的，因为mark后，哪些对象是存活，哪些是要被sweep是已知的，sweep的是不再被引用的对象。

sweep结束前，这些对象不会再被分配到，所以sweep和mutator运行共存。无论全局还是栈不可能能访问到的这些对象，可以安全清理。

1.5版本再标记过程使用三色标记法，标记和清扫都是并发执行的，但标记阶段的前后需要STW一定时间来做GC的准备工作和栈的re-scan。

三色标记法

三色标记是对标记清除法的改进，标记清楚法在珍格格执行时要求长时间STW。Glang 在1.5版本改用三色标记法。三色标记法中有两个重要概念，对象的三色抽象和波面推进。

三色抽象是一种描述追踪式回收器的方法，从逻辑上严密推导标记清理这种垃圾回收方法的正确性。

初始将所有内存标记为白色，然后将roots加入带扫描队列（进入队列即被视为变成灰色），然后使用并发goroutine扫描队列中的指针，如果指针还引用了其他指针，那么被引用的也进入了队列，被扫描的对象视为黑色。

三色抽象规定了三种不同类型的对象，用颜色区分：

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

image72

回收过程是一个波面不断推荐的过程，回收开始，所有对象均为白色，标记过程开始，灰色对象开始出现，随着波面扩大，当一个对象的所有子节点均完成扫描，被着色成黑色。整个堆便利完成，只剩下黑色和白色对象。黑色对象为可达对象，白色为不可达，即垃圾对象。

Tri-color Marking

三色标记的过程

垃圾收集器从root开始，然后跟随指针递归整个内存空间。

分配于noscan的span的对象（也就是不包含指针的span），不会进行扫描。

这个过程不是由同一个goroutine完成的，每个指针都排队在工作池（待扫描的队列）中，然后，先看到的被标记为工作协程的后台协程从该池中出队，扫描对象，然后将在其中找到的指针排入队列。

Tri-color Coloring

三色染色的过程

  • 一开始所有对象被认为是白色
  • 跟节点（stacks，heap，global variables）被染色为灰色

一旦主流程走完，gc会：

  • 选一个灰色对象，标记为黑色
  • 便利这个对象的所有指针，标记所有其引用的对象为灰色

最终直到所有对象需要被染色。

标记结束后，黑色对象是内存中正在使用的对象，而白色对象是要收集的对象。比如，一个从匿名函数中创建的实例struct，无法从堆栈中访问，因此它保持为白色，可以清除。

image-20220918213655891

颜色在内部实现原理：

每个span中有一个名为gcmarkBits的位图属性，该属性跟踪扫描，并将相应的位设置为1。

Write Barrier

写屏障

1.5版本再标记过程中使用三色标记法。

回收过程主要有四个阶段，其中标记和清扫都并发执行。但标记阶段的前后需要STW一定时间来做GC的准备工作和栈的re-scan（清扫阶段和应用程序要同时执行，避免出现在标记过程中增量引用的部分被误识别）。

使用并发的垃圾回收，也就是多个mutator与mark并发执行，想要在并发或者增量的标记算法中保证正确性，需要达成以下两种三色不变性（Tri-color invariant）中的任意一种：

  • 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象
  • 弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径（也就是这个白色对象会被其他的灰色对象访问到）

一个白色对象被黑色对象引用，是注定无法通过这个黑色对象来保证自身存活的，于此同时，如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏，那么这个白色对象必然会被视为垃圾清除掉。

故当上述两个条件同时满足时，就会出现对象丢失的问题。

如果这个白色对象下游还引用了其他对象，并且这条路径是指向下游对象的唯一路径，那么他们也是必死无疑的。

image-20220918215343800

例如在程序运行过程，进行标记，标记B对象为灰色对象，B对象引用C对象，此时可能A是栈上一个对象指向C，B是一个堆上对象指向C，当B指向C的关系被破坏，此时C还是白色，被回收之后，A无法访问到C，出现对象丢失的错误。

为了方式这种现象，最简单的方式就是STW，直接禁止掉其他用户程序对对象应用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响。为了解决STW的问题，引入写屏障。

写屏障，也叫做插入屏障，1.5版本使用的Dijkstra 写屏障用的就是这个原理。插入屏障拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色状态（也就是当A引用C时，将C状态改为灰色），这样就不存在黑色对象引用白色对象的情况了，满足强三色不变式。在插入指针f时将c对象标记为灰色。

image-20220918220016592

如果对栈上的写做屏障，那么流程代码会非常复杂，并且性能下降会非常大。根据局部性的原理来说，其实程序跑起来，大部分其实都是操作在栈上，函数参数、函数调用导致的压栈、出栈、局部变量、协程栈，这些如果也弄起写屏障，复杂度和性能是无法解决的。

所以Go选择仅对堆上的指针插入增加写屏障（图中A插入指针指向C），这样就会出现在扫描结束后，栈上仍存在引用白色对象的情况，这时的C是灰色的，不满足三色不变式，所以需要对栈进行重新扫描使其变黑，完成剩余对象的标记，这个过程需要STW。（也就是前面说的栈的re-scan）

image-20220918220512045

初始化GC任务，包括开启写屏障，和开启辅助GC，统计root对象的任务数量等，这个过程需要STW。

扫描所有root对象，包括全局指针和goroutine（G）栈上的指针（扫描对应G栈时需要停止该G），将其加入扫描队列（灰色队列），并循环处理灰色队列的对象，直到灰色队列为空，该过程后台并行执行。

完成标记工作，重新扫描（re-scan）全局指针和栈。因为Mark和mutator是并行的，所以在mark过程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障记录下来，re-scan再检查一下，这个过程也是会STW的，按照标记结果回收所有的白色对象，该过程后台并发执行。

删屏障

删除屏障 Yuasa，也是拦截写操作的，但是是通过保护灰色对象到白色对象的路径不会断来实现的。

image-20240416180207261

如图，在删除指针e时，将对象C标记为灰色，这样下游的所有白色对象，即使会被黑色对象引用，最终也还是会被扫描标记的，满足了弱三色不变式。这种方式的回报精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮在下一轮GC中被清理掉。

混合屏障

插入屏障和删除屏障各有优缺点。

插入屏障在标记开始时无需STW，可直接开始，并发进行，但是结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活。

删除屏障则需要再GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW。

image-20220918221939296

Go中的混合写屏障满足的是变形的弱三色不变式，同样允许黑色对象引用白色对象，白色对象处于灰色保护状态，但是只由堆上的灰色对象保护。

混合屏障结合了删除屏障和写入屏障的有点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，标记结束后，因为栈在扫描后使用是黑色的，也无需再进行re-scan操作了，减少了STW的时间。

image-20220918222917762

为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，还需要将创建的所有堆上新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误的回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

Sweep

清扫阶段

sweep让GO知道哪些内存可以重新分配使用，然而，sweep过程并不会处理释放的对象内存置为0，而是在分配重新使用的时候，重新reset bit。

每个span内有一个bitmap allocBits，表示上一次GC之后每一个object的分配情况，

image-20220918223048189

1：表示已分配

0：表示未使用或者已释放

GC将会启动去释放不再被使用的内存。在标记期间，GC会用一个位图gcmarkBits来跟踪在使用中的内存。

正在被使用的内存被标记为黑色，然而当前执行并不能够到达的那些内存会保持为白色。

image-20220918223405879

现在，可以使用gcmarkBits精确查看可用于分配的内存。Go使用gcmarkBits赋值了allocBits，这个操作就是内存清理。（将gcmarkBits替换allocBits）

然而必须每个span都来一次类似的处理，需要耗费大量时间，Go的目标是在清理内存时不阻碍执行，并未次提供了两种策略。

  • 在后台启动一个worker等待清理内存一个一个mspan处理

    image-20220918223813575

    当开始运行程序时，Go将设置一个后台运行的Worker（唯一的任务就是去清理内存），它将进入睡眠状态并等待内存段扫描。

  • 当申请分配内存时lazy触发

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

    这种方式是即时执行。由于这些内存段已经被分发到每一个处理器P的本地缓存mcache中，因此很难追踪到首先清理哪些内存。这就是为什么Go首先将所有内存段移动到mcentral的原因。然后它将会让本地缓存mcache再次请求他们，去即时清理。

    image-20220918231110719 image-20220918231120977

    即时扫描确保所有内存段都会得到清理（节省资源），同时不会阻塞程序执行。

    由于后台只有一个worker在清理内存块，清理过程可能会花费一些时间。但是，如果另一个GC周期在一次清理过程中启动会发生什么。在这种情况下，这个运行GC的goroutine就会在开始标记阶段前去协助完成剩余的清理工作。

STW

在Stop the world阶段，当前运行的所有程序将被暂停，扫描内存的root节点和添加写屏障。

image-20220918231249565

这个阶段的第一步，时抢占所有正在运行的goroutine，被抢占之后，这些goroutine会被悬停在一个相对安全的状态。

在1.14版本之后，支持信号抢占，相对以前全局变量（preemptable）的方式时间更短。

处理器P（无论是正在运行代码的P还是在idle列表中的P），都会被标记成停止状态（stopped），不再运行任何代码，调度器把每个P的M从对应P分离出来，当道idle列表中。

image-20220918231555886

对于goroutine而言，他们会被放到一个全局队列中等待。

Pacing

  • 运行时，只有GC Percentage（GC百分比）的配置选项，默认情况下为100。

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

    例如：使用环境变量 GODEBUG 和 gctrace = 1选项生成GC trace， GODEBUG=gctrace=1 ./app

    image-20220918231905451 image-20220918231915686

  • 如果超过2分钟没有触发，sysmon会强制GC。

终止器

通过终止器验证Golang会GC。finalizer 终止器，GC时某个对象无法被访问，则finalizer就会调用这个对象。

1
runtime.SetFinalizer(obj any, finalizer any)

只有对象被GC时，终止器才会被执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type Road int

func findRoad(r *Road) {        // r does not escape
    log.Printf("road: %v", *r)	// *r escapes to heap
}

func entry() {
    var rd Road = Road(99)	// moved to heap: rd
    r := &rd
    runtime.SetFinalizer(r, findRoad)   // 在gc时候，判断gc是否能被访问到
}

func main() {
    entry()
    runtime.GC()		// 第一次GC，取消对象r的关联
    runtime.GC()		// 第二次GC，r被gc，findRoad被执行
    time.Sleep(time.Second)
}

执行结果

1
2022/07/25 17:25:48 road: 99

runtime的函数

1
2
3
4
5
6
fmt.Println(runtime.NumCPU()) // 返回当前CPU个数
fmt.Println(runtime.Version()) // 返回当前golang版本
runtime.GC()    // 手动GC
fmt.Println(runtime.NumGoroutine())    // 返回当前存在的goroutine个数	
runtime.Gosched()    // 强制切换goroutine
runtime.Goexit()    // 关闭当前调用这个函数的goroutine

分析GC过程

gc流程

以STW为界限，可以将GC划分为五个阶段：

  • sweep Termination：清扫终止阶段，为下一个阶段的并发标记做准备工作，启动写屏障
  • Mark：扫描标记阶段，与复制器并发执行，写屏障开启
  • Mark Termination：标记终止阶段，保证一个周期内标记任务完成，停止写屏障
  • GCoff：内存清扫阶段，将需要回收的内存归还到堆中，写屏障关闭
  • GCoff：内存归还阶段，将过多的内存归还给操作系统，写凭证关闭

触发GC

​ 触发GC有两种方式：一种是手动，一种是自动。

​ 手动触发：调用runtime.gc

​ 自动触发：自动触发机制有两种方式，一种是时间间隔，大约2分钟没有任何GC系统会强制触发，二种是步调算法，当内存增长达到一定比例时触发GC

gctrace

通过开启gctrace，可以看到gc的过程

1
GODEBUG=gctrace=1 go run main.go

截取部分

1
gc 1 @0.005s 2%: 0.009+0.63+0.037 ms clock, 0.090+0.39/0.69/0+0.37 ms cpu, 4->4->0 MB, 4 MB goal, 0 MB stacks, 0 MB globals, 10 P
  • gc 1 ：第几个gc周期，这是第一个
  • @0.005s： 程序开始运行到第一次GC事件为0.005s
  • 2%：此次GC过程CPU占用率
  • wall clock：0.009+0.63+0.037 ms clock
    • 0.009：STW，stop the world，开启写屏障时间
    • 0.63：标记阶段的时间
    • 0.037：STW，start the world，关闭写屏障时间
  • CPU time：0.090+0.39/0.69/0+0.37 ms cpu
    • 0.090：Stop the world，开启写屏障的CPU时间
    • 0.39：辅助标记时间
    • 0.69：并发标记时间
    • 0：GC空闲时间
    • 0.37：start the world，关闭写屏障时间的CPU事件
  • 4->4->0 MB, 4 MB goal, 0 MB stacks, 0 MB globals,
    • 4：标记开始时，堆大小的实际值
    • 4：标记结束时，堆大小的实际值
    • 0：标记结束时，标记为存活对象大小
    • 4：标记结束时，堆大小的预测值
    • 0：估计的可扫描堆栈大小
    • 0：可扫描全局大小
  • 10 P：使用的处理器数量

go tool trace

将统计的信息通过可视化的方式展现出来，在代码中调用trace的API

1
2
3
4
5
6
7
8
f, _ := os.Create("trace.out")
defer f.Close()
trace.Start(f)
defer trace.Stop()
entry()
runtime.GC()
runtime.GC()
time.Sleep(time.Second)
1
go tool trace ./trace.out

debug.ReadGCStats

通过debug的包

1
2
3
4
5
6
s := debug.GCStats{}
for i := 0; i < 100; i++ {
    member()
    debug.ReadGCStats(&s)
    fmt.Printf("gc %d last@%v, PauseTotal %v\n", s.NumGC, s.LastGC, s.PauseTotal)
}

输出

1
2
gc 93 last@2022-07-25 21:19:50.388347 +0800 CST, PauseTotal 4.190662ms
gc 94 last@2022-07-25 21:19:50.388729 +0800 CST, PauseTotal 4.259787ms

runtime.ReadMemStats

通过运行时的内存相关API

1
2
3
4
5
6
s := runtime.MemStats{}
for i := 0; i < 100; i++ {
    member()
    runtime.ReadMemStats(&s)
    fmt.Printf("gc %d last@%v, next_heap_size %vMB\n", s.NumGC, time.Unix(int64(time.Duration(s.LastGC).Seconds()), 0), s.NextGC/(1<<20))
}

输出

1
2
gc 98 last@2022-07-25 21:25:04 +0800 CST, next_heap_size 8MB
gc 99 last@2022-07-25 21:25:04 +0800 CST, next_heap_size 8MB

内存泄露

即使有GC，也会出现内存泄漏。从上面GC目标是堆上的内存来看，如果让变量附着在堆上，则会出现内存泄露。

变量附着在全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var m = make(map[int]interface{})

func env(i int) {
    s := make([]int, 1<<20)
    m[i] = s
}

func main() {
    f, _ := os.Create("trace1.out")
    defer f.Close()
    trace.Start(f)
    defer trace.Stop()
    for i := 0; i < 10000; i++ {
        env(i)
    }
}

image-20220726101606183

可见Heap一直在增长

泄露

除了附着在堆上出现内存泄露，还有可能出现channel泄露。当goroutine往一个没有接受者接收的channel发送信息，goroutine无法执行完成，goroutine及其执行栈得不到释放

1
2
3
4
5
6
7
8
9
10
11
f, _ := os.Create("trace2.out")
defer f.Close()
trace.Start(f)
defer trace.Stop()
ch := make(chan struct{})
for i := 0; i < 100000; i++ {
    go func() {
        ch <- struct{}{}
    }()
}
time.Sleep(5 * time.Second)

image-20220726102814647

引申：

  • go doc 1.19