Go-07-垃圾回收

Go Comments

垃圾回收

GC，全称 Garbage Collection，即垃圾回收，是一种自动内存管理的机制

通常，垃圾回收器的执行过程被划分为两个半独立的组件：

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

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

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

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

  • 追踪式 GC:从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆并确定需要保留的对象，从而回收所有可回收的对象。Go、 Java、V8 对 JavaScript 的实现等均为追踪式 GC。
  • 引用计数式 GC:每个对象自身包含一个被引用的计数器，当计数器归零时自动得到回收。因为此方法缺陷较多，在追求高性能时通常不被应用。Python、Objective-C 等均为引用计数式 GC。

目前比较常见的 GC 实现方式包括：

  • 追踪式，分为多种不同类型，例如：
    • 标记清扫：从根对象出发，将确定存活的对象进行标记，并清扫可以回收的对象。
    • 标记整理：为了解决内存碎片问题而提出，在标记过程中，将对象尽可能整理到一块连续的内存上。
    • 增量式：将标记与清扫的过程分批执行，每次执行很小的部分，从而增量的推进垃圾回收，达到近似实时、几乎无停顿的目的。
    • 增量整理：在增量式的基础上，增加对对象的整理过程。
    • 分代式：将对象根据存活时间的长短进行分类，存活时间小于某个值的为年轻代，存活时间大于某个值的为老年代，永远不会参与回收的对象为永久代。并根据分代假设（如果一个对象存活时间不长则倾向于被回收，如果一个对象已经存活很长时间则倾向于存活更长时间）对对象进行回收。
  • 引用计数：根据对象自身的引用计数来回收，当引用计数归零时立即回收。

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

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

三色标记法

理解三色标记法的关键是理解对象的三色抽象以及波面（wavefront）推进这两个概念。三色抽象只是一种描述追踪式回收器的方法，在实践中并没有实际含义，它的重要作用在于从逻辑上严密推导标记清理这种垃圾回收方法的正确性。也就是说，当我们谈及三色标记法时，通常指标记清扫的垃圾回收。

从垃圾回收器的视角来看，三色抽象规定了三种不同类型的对象，并用不同的颜色相称：

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

这样三种不变性所定义的回收过程其实是一个波面不断前进的过程，这个波面同时也是黑色对象和白色对象的边界，灰色对象就是这个波面。

当垃圾回收开始时，只有白色对象。随着标记过程开始进行时，灰色对象开始出现（着色），这时候波面便开始扩大。当一个对象的所有子节点均完成扫描时，会被着色为黑色。当整个堆遍历完成时，只剩下黑色和白色对象，这时的黑色对象为可达对象，即存活；而白色对象为不可达对象，即死亡。这个过程可以视为以灰色对象为波面，将黑色对象和白色对象分离，使波面不断向前推进，直到所有可达的灰色对象都变为黑色对象为止的过程

三色标记法全貌

三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些.

第一步: 就是只要是新创建的对象,默认的颜色都是标记为“白色”.

image-20210829204317283

这里面需要注意的是, 所谓“程序”, 则是一些对象的根节点集合。

第二步: 每次GC回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合，类似层序遍历

image-20210829204538529

第三步: 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，灰色被遍历之后就放入黑色集合

image-20210829204707809

第四步: 重复第三步, 直到灰色中无任何对象

image-20210829204909941

第五步: 回收所有的白色标记表的对象. 也就是回收垃圾

image-20210829204944981

以上就是三色并发标记法，Go是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题？

没有STW的三色标记法

一定要依赖STW的。因为如果不暂停程序，程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。例如

image-20210829205244387

已经标记为灰色的对象2有指针指向白色的对象3

image-20210829205411544

在还没有扫描到对象2，已经标记为黑色的对象4创建指针q，指向对象3

image-20210829205556490

于此同时对象2将指针p移除，对象3就被挂载了已经扫描完成的黑色的对象4下面

image-20210829205745077

正常执行逻辑，对象2和对象7 被标记为黑色，而对象3因为对象4不在被扫描，而等待被回收

image-20210829210010244

对象3被无辜的清除掉了

当下列两个条件同时满足时, 就会出现对象丢失现象!

  • 条件1: 一个白色对象被黑色对象引用**(白色被挂在黑色下)**，它的下游对象也会一并被清理掉
  • 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)**

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

答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了

屏蔽机制

让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.

  1. 强-弱三色不变式

    强三色不变式: 不存在黑色对象引用到白色对象的指针

    image-20210829210423104

    弱三色不变式: 所有被黑色对象引用的白色对象都处于灰色保护状态

    image-20210829210542280

为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式“插入屏障”, “删除屏障”。

插入屏障

具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)

满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)

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

第一步：程序起初创建，全部标记为白色，将所有对象放入白色集合中

image-20210831231111455

第二步：遍历Root Set(非递归形式，只遍历一次，得到灰色节点)

image-20210831231418953

第三步：遍历Grey 灰色标记表。将可达的对象从白色标记为灰色遍历之后的灰色，标记为黑色

image-20210831231655992

第四步：如果此刻外界向对象4添加对象8，对象1添加对象9。对象4在堆区触发插入屏蔽机制，对象1不触发

image-20210831231856596

第五步：由于插入写屏障(黑色对象添加白色，将白色改为灰色)，对象8变为灰色，对象9依然时i白色

image-20210831232029636

第六步：继续循环上述流程进行三色标记，直到没有灰色节点

image-20210831232147178

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

第七步：在准备回收白色前，重新遍历扫描一次栈空间。此时加STW暂停保护栈，防止外界干扰

image-20210831232410377

第八步：在STW中，将栈中的对象一次三色标记，直到没有灰色标记

image-20210831232542554

第八步：停止STW

image-20210831232628158

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

image-20210831232803798
删除屏障

具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。

满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)

第一步：程序起初创建，全部标记为白色，将所有对象放入白色集合

image-20210831234649845

第二步：遍历Root Set(非递归形式，只遍历一次)，得到灰色节点

image-20210831234748877

第三步：灰色对象1删除对象5，如果不触发删除写屏障，5-2-3路径与主链路断开，最后均会被清除

image-20210831234838602

第四步：触发删除写屏障，被删除对象5，被标记为黑色

image-20210831234903103

第五步：遍历Grey 灰色标记表，将可达的对象，从白色标记为灰色。遍历之后的灰色，标记为黑色

image-20210831234930140

第六步：继续循环上述流程进行三色标记，直到没有灰色节点

image-20210831235001271

第七步：这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉

image-20210831235138751

第八步：清除白色

image-20210831234618990

混合写屏障(hybrid write barrier)机制

插入写屏障和删除写屏障的短板：

  • 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
  • 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点

具体操作:

1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，

2、GC期间，任何在栈上创建的新对象，均为黑色。

3、被删除的对象标记为灰色。

4、被添加的对象标记为灰色。

image-20210831235449381

第一步：GC刚刚开始，都标记为白色

第二步：优先扫描栈对象，将可达对象全部标记为黑色

场景一

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

第一步：将对象7添加到对象1的下游，因为栈不启动写屏障，所以直接挂载下面

image-20210831235813222

第二步：对象4删除对象7的引用关系，因为对象4是堆区，所以触发写屏障，标记被删除的对象7为灰色(删除即赋新值为nil)

image-20210831235848390

参考文献

  1. https://golang.design/go-questions/memgc/principal/
  2. https://www.bookstack.cn/read/aceld-golang/5、Golang三色标记+混合写屏障GC模式全分析.md