Go语言进阶(十一)GC原理

GC 原理

Mark & Sweep (标记和清扫)

Garbage Collection (垃圾回收)

现代高级编程语言管理内存的方式分为两种:自动和手动,像 C、C++ 等编程语言使用手动管理内存的方式,工程师编写代码过程中需要主动申请或者释放内存;而 PHP、Java 和 Go 等语言使用自动的内存管理系统,有内存分配器和垃圾收集器来代为分配和回收内存,其中垃圾收集器就是我们常说的 GC。主流的垃圾回收算法:

  • 引用记数
  • 追踪式垃圾回收

Go 现在用的三色标记法就属于追踪式垃圾回收算法的一种。

image-20211216134412709

Mark & Sweep

Stop the world (STW)

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

Root

根对象是 mutator 不需要通过其他对象就可以直接访问到的对象。比如全局对象,栈对象中的数据等。通过Root 对象,可以追踪到其他存活的对象。

image-20211216134600143

Mark Sweep 两个阶段:标记(Mark)和 清除(Sweep)两个阶段,所以也叫 Mark-Sweep 垃圾回收算法。

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

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

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停,朴素的 Mark Sweep 是整体 STW,并且分配速度慢,内存碎片率高。以上是Go1.1时代, STW 可能秒级。

Go1.3时代开始,标记过程需的要 STW,因为对象引用关系如果在标记阶段做了修改,会影响标记结果的正确性。

并发 GC 分为两层含义:

  • 每个 mark 或 sweep 本身是多个线程(协程)执行的(concurrent)
  • mutator 和 collector 同时运行(background)

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

而对于 backgroud 这一层, 也就是说 mutator 和 mark,sweep 同时运行,则相对复杂。

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

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

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

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

Tri-color Mark & Sweep (三色标记法)

三色标记是对标记清除法的改进,标记清除法在整个执行时要求长时间 STW,Go 从1.5版本开始改为三色标记法,初始将所有内存标记为白色,然后将 roots 加入待扫描队列(进入队列即被视为变成灰色),然后使用并发 goroutine 扫描队列中的指针,如果指针还引用了其他指针,那么被引用的也进入队列,被扫描的对象视为黑色

  • 白色对象:潜在的垃圾,其内存可能会被垃圾收集器回收。
  • 黑色对象:活跃的对象,包括不存在任何引用外部指针的对象以及从根对象可达的对象,垃圾回收器不会扫描这些对象的子对象。
  • 灰色对象:活跃的对象,因为存在指向白色对象的外部指针,垃圾收集器会扫描这些对象的子对象。

垃圾收集器从 root 开始然后跟随指针递归整个内存空间。分配于 noscan 的 span 的对象, 不会进行扫描。然而,此过程不是由同一个 goroutine 完成的,每个指针都排队在工作池中 然后,先看到的被标记为工作协程的后台协程从该池中出队,扫描对象,然后将在其中找到的指针排入队列。

  • noscan 的 span 的对象,表示不是指针对象,不需要被扫描。

image-20211216142303295

image-20211216142312070

染色流程:

1) 一开始所有对象被认为是白色

image-20211216143354333

2) 根节点(stacks,heap,global variables)被染色为灰色

image-20211216143419895

3) 选一个灰色对象,标记为黑色

image-20211216143436094

4) 遍历这个对象的所有指针,标记所有其引用的对象为灰色

image-20211216143453393

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

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

image-20211216143505667

颜色在内部实现原理:
每个 span 中有一个名为 gcmarkBits 的位图属性,该属性跟踪扫描,并将相应的位设置为1。

Write Barrier (写屏障)

1.5版本在标记过程中使用三色标记法。回收过程主要有四个阶段,其中,标记清扫都并发执行的,但标记阶段的前后需要 STW 一定时间来做GC 的准备工作栈的 re-scan

使用并发的垃圾回收,也就是多个 Mutator 与 Mark 并发执行,想要在并发或者增量的标记算法中保证正确性,我们需要达成以下两种三色不变性(Tri-color invariant)中的任意一种:

  • 强三色不变性:黑色对象不会指向白色对象,只会指向灰色对象或者黑色对象。
  • 弱三色不变性 :黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。

可以看出,一个白色对象被黑色对象引用,是注定无法通过这个黑色对象来保证自身存活的,与此同时,如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏,那么这个白色对象必然会被视为垃圾清除掉。 故当上述两个条件同时满足时,就会出现对象丢失的问题。如果这个白色对象下游还引用了其他对象,并且这条路径是指向下游对象的唯一路径,那么他们也是必死无疑的。

image-20211216145148442

为了防止这种现象的发生,最简单的方式就是 STW,直接禁止掉其他用户程序对对象引用关系的干扰,但是 STW 的过程有明显的资源浪费,对所有的用户程序都有很大影响,如何能在保证对象不丢失的情况下合理的尽可能的提高 GC 效率,减少 STW 时间呢?

Dijkstra 插入屏障

插入屏障拦截将白色指针插入黑色对象的操作,标记其对应对象为灰色状态,这样就不存在黑色对象引用白色对象的情况了,满足强三色不变式,在插入指针 f 时将 C 对象标记为灰色。

image-20211216145658775

如果对栈上的写做拦截,那么流程代码会非常复杂,并且性能下降会非常大,得不偿失。根据局部性的原理来说,其实我们程序跑起来,大部分的其实都是操作在栈上,函数参数啊、函数调用导致的压栈出栈、局部变量啊,协程栈,这些如果也弄起写屏障,那么可想而知了,根本就不现实,复杂度和性能就是越不过去的坎

引入re-scan重扫描。

Yuasa 删除屏障

删除屏障也是拦截写操作的,但是是通过保护灰色对象到白色对象的路径不会断来实现的。如上图例中,在删除指针 e 时将对象 C 标记为灰色,这样 C 下游的所有白色对象,即使会被黑色对象引用,最终也还是会被扫描标记的,满足了弱三色不变式。这种方式的回收精度低,一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮,在下一轮 GC 中被清理掉。

image-20211216151310554

混合屏障

插入屏障和删除屏障各有优缺点,Dijkstra 的插入写屏障在标记开始时无需 STW,可直接开始,并发进行,但结束时需要 STW 来重新扫描栈,标记栈上引用的白色对象的存活;Yuasa 的删除写屏障则需要在 GC 开始时 STW 扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象,但结束时无需 STW。

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

image-20211216152413019

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

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

Sweep 清扫阶段

Sweep 让 Go 知道哪些内存可以重新分配使用,然而,Sweep 过程并不会处理释放的对象内存置为0(zeroing the memory)。而是在分配重新使用的时候,重新 reset bit。

image-20211216152838207

每个 span 内有一个 bitmap allocBits,他表示上一次 GC 之后每一个 object 的分配情况,1:表示已分配,0:表示未使用或释放。

image-20211216152852933

内部还使用了 uint64 allocCache(deBruijn),加速寻找 freeobject。

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

image-20211216153030794

正在被使用的内存被标记为黑色,然而当前执行并不能够到达的那些内存会保持为白色。
现在,我们可以使用 gcmarkBits 精确查看可用于分配的内存。Go 使用 gcmarkBits 赋值了 allocBits,这个操作就是内存清理。
然而必须每个 span 都来一次类似的处理,需要耗费大量时间。Go 的目标是在清理内存时不阻碍执行,并为此提供了两种策略。

Go 提供两种方式来清理内存:

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

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

2) 当申请分配内存时候 lazy 触发

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

image-20211216153142782

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

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

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

image-20211216153435093

image-20211216153441828

Stop The Wrold

在垃圾回收机制 (GC) 中,”Stop the World” (STW) 是一个重要阶段。顾名思义, 在 “Stop the World” 阶段, 当前运行的所有程序将被暂停, 扫描内存的 root 节点和添加写屏障 (write barrier) 。

image-20211216153528272

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

处理器 P (无论是正在运行代码的处理器还是已在 idle 列表中的处理器), 都会被被标记成停止状态 (stopped), 不再运行任何代码。 调度器把每个处理器的 M 从各自对应的处理器 P 分离出来, 放到 idle 列表中去。

对于 Goroutine 本身, 他们会被放到一个全局队列中等待。

image-20211216153709754

Pacing (起搏器)

1) 运行时中有 GC Percentage 的配置选项,默认情况下为100。

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

2)如果超过2分钟没有触发,会强制触发 GC