Golang中的GC

GC不是一个陌生的词，它是垃圾回收英文单词（garbage collection）的缩写。GC对于高级编程语言是必须的，尤其是对业务性比较强的语言,比如C#、Java、Python、Go，程序员可以把重点放到业务实现上，而尽量避免关注语言本身内存分配与回收。但并不是说编程语言有了GC之后程序员们就不需要了解GC了，了解了内存管理与垃圾回收之后对编程语言会有更深刻的理解，对程序的优化也有很大的助力。

Go语言GC的演进

  • V1.3 普通的标记清除法，过程需要STW
  • V1.5 三色标记法，堆空间启用写屏障，栈空间不启用，全部扫描后，需要STW并重新扫描栈空间
  • V1.8 三色标记法，混合写屏障机制，栈空间不启用写屏障，堆空间需要启用写屏障，过程基本不需要STW。

标记清扫法

Go V1.3之前的GC采用标记清扫方法（mark and sweep），在GC的时候暂停所有的线程，标记出活动的对象，清除不活动的对象，待回收完成后再恢复到之前的工作环境，这就是STW（Stop The World）。

STW的大致流程是这样的：

graph LR
1.启动SWT --> 2.Mark标记 --> 3.Sweep清除 --> 4.停止STW --> 5.程序继续执行

标记清扫方法的缺点：

  • STW的时候使程序暂停，程序会出现暂停、卡顿，影响业务
  • 标记需要扫描整个堆栈信息
  • 清除数据会产生内存碎片

最重要的问题还是STW会影响业务，所以要尽量取消STW，或减少STW的时间。可以通过调整第四步和第三步骤执行顺序，缩小STW的范围，清理的时候和程序并行去执行。

graph LR
1.启动SWT --> 2.Mark标记 --> 3.停止STW --> 4.Sweep清除,程序继续并行执行

在标记过程中还是比较浪费时间，能不能尝试采用新的标记模式来替代清除标记法呢？

三色标记法

Go V1.5版本开始使用了三色标记法。三色标记法会在整个的GC里面记录三个集合:

  1. 白色标记表：没有遍历到的,也是最终要回收的对象(剩余的是无法遍历到的对象)
  2. 灰色标记表：临时状态，表示可遍历
  3. 黑色标记表：表示已经彻底遍历过了

一开始，先将所有对象标记为白色。从程序对象根集合中开始遍历一层，找到的对象标记为灰色。然后将得到的灰色节点遍历一层，找到的对象标记为灰色，原灰色节点变为黑色。不断重复，直到不存在灰色对象，即直到只剩下白色和黑色对象。最终剩下的白色对象就是不可达的对象，也就是要清理的对象。

例如，程序中有以下对象：

graph LR
  RootSet --> 对象1 --> 对象2 --> 对象3
  RootSet --> 对象4 --> 对象7
  对象5 --> 对象2
  对象6:::white
  classDef white fill:#fff
  1. 程序起初创建会将所有节点标记为白色，将所有对象放入到白色集合中。
  2. 程序由根集合节点遍历,先得到灰色节点：1，4。
  3. 再继续遍历得到灰色节点：2，7，同时将1，4标记为黑色节点。
  4. 再继续遍历灰色节点2和7，找到对象3并标记为灰色，同时2与7标记为黑色。
  5. 再继续遍历灰色对象3，3没有其它对象，就将3标记为黑色。

到此时白色标记集合中只有 对象5 和 对象6，它们就是不可达的对象，最终回收掉白色的 对象5 和 对象6。

上面三色标记的过程理论上还是在STW的保护下。如果不使用STW的话，程序是在并行运行的，可能会在程序删除的同时恰巧这个对象被引用到了，这就会产生致命的问题。那它还是性能比较低的一种GC算法。那三色标记可以不可以不启动SWT?

那先看一下三色标记最不希望发生的两件事情：

  1. 一个白色对象被黑色对象引用。
  2. 灰色对象与它之间的可达关系的白色对象遭到破坏，也就灰色收丢失了该白色对象。

当这两个条件同时满足时，就会出现对象丢失的现象。这也是不使用STW可能会发生的事情。

为了不发生这种情况，最简单的方式还是使用STW。可是STW的过程有明显的资源浪费，对用户程序也有很大影响，那就要想办法保证对象不丢失的情况下尽可能提高GC效率，减少STW时间。

应对上面两种情况，Go团队研究了强、弱三色不变式两种方式来丢失对象。

强三色不变式

强三色不变式：强制性的不允许黑色对象引用白色对象。(破坏了上面的条件1)

flowchart LR
  black[黑色] --x white[白色]
  style black fill:#000,color:#fff
  style white fill:#fff

弱三色不变式

弱三色不变式：黑色可以引用白色，但是要存在其它灰色对象对该白色对象的引用，或者它的链路上游存在灰色对象，这样可以保证这个白色对象不会丢失。

graph LR
  黑色:::black --> 白色:::white
  灰色:::gray --> 白色:::white
  classDef black fill:#000,color:#fff
  classDef white fill:#fff
  classDef gray fill:#ccc

graph LR
  黑色:::black --> 白色1:::white
  灰色:::gray --> 白色2:::white --> 白色1:::white
  classDef black fill:#000,color:#fff
  classDef white fill:#fff
  classDef gray fill:#ccc

在三色标记中，如果满足强/弱之一，即可保证对象不丢失。

屏障机制

什么是屏障？在程序垃圾回收的过程中，不影响正常业务逻辑的情况下，加入一些额外的判断，来遏制两种情况的发生，它和hook、回调、handler的思想是类似的。在三色标记法中，有两种屏障机制:

  1. 插入屏障: 当一个对象被引用时，触发的机制。
  2. 删除屏障: 当一个对象被删除时，触发的机制。

插入写屏障

在A对象引用B对象的时候，会触发插入屏障判断，B对象被标记为灰色。这样就不存在黑色对象引用白色对象了，因为白色会强制变成灰色。它满足了强三色不变式。

那每创建一个对象,难道都要去做这样的一个判断吗，这样会影响整个程序的性能的。由于栈的空间比较小，为了不影响栈的运行效率，在栈上操作是不会触发插入屏障的，而堆上是启用插入屏障的。

对于栈在白色对象被回收之前需要短暂的启用STW机制，结束时候需要SWT来重新扫描栈，这也是插入写屏障的不足之处，大约需要10-100ms.

删除写屏障

被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。它是为了满足弱三色不变式（保护灰色对象到白色对象的路径不会断）。

例如：

graph LR
  RootSet --> 对象1 --> 对象2 --> 对象3 --> 对象4
  classDef white fill:#fff
  1. 首先4个对象全部被标记为白色。
  2. 扫描到对象1的时候，将对象1标记为灰色。
  3. 若此时对象1删除了对象2的引用，此时触发删除写屏障，将对象2标记为灰色。
  4. 接着继续扫描对象1、对象2，并标记为黑色，对象3则被标记为灰色。
  5. …

本轮GC检测没有回收对象，等到第二轮GC的时候，会将对象2清理掉。这也是删除写屏障的不足，一个对象即使被删除了最后一个指向它的指针，依旧可以再活一轮，在下一轮GC中被清理掉。

混合写屏障

上面了解到了插入写屏障和删除写屏障的一些不足，插入写屏障需要STW重新扫描栈，删除写屏障回收精度低。

在 Go v1.8版本之后采用三色标记法，并引入了混合写屏障机制。混合写屏障结合了插入写屏障和删除写屏障的优点。了解下它的基本流程：

  1. GC开始的时候，优先扫描栈，将栈上的全部可达对象标记为黑色。为了保证栈的执行效率，栈上操作是没有屏障机制的。（之后不再进行第二次重复扫描，无需STW）
  2. GC期间，任何在栈上创建的新对象，也全部标记为黑色。这么做也是为了避免进行二次扫描，不需要二次扫描就意味着不需要STW暂停了。那为什么标记为黑色就不需要二次扫描了呢？之所以需要扫描是因为栈上可能存在被标记为白色的合法对象，若不扫描可能会被GC回收掉。现在全部标记为黑色，就都是合法的对象，GC就不会去清理。那全部标记为黑色会不会导致内存泄露呢？并不会，因为第二次GC的时候会删除（延迟删除）。
  3. 被删除的对象标记为灰色。(这里沿用了删除写屏障的特点)
  4. 被添加的对象标记为灰色。

这4个操作的组合就达成了混合写屏障的机制，不需要STW也能保证一次GC的完成。它是一个变形的弱三色不变式，并结合了插入、删除写屏障两者的优点。

示例1

场景：堆对象7 被 堆对象4 删除引用，同时成为 栈对象1 的下游。

flowchart LR
  栈[栈:不启用屏障] --> 对象1 --> 对象2 --> 对象3
  堆[堆:启用屏障] --> 对象4 -.X删除引用X.-x 对象7
  对象1 --添加引用--> 对象7
  1. 将 对象7 添加到 对象1 的下游，因为栈不启用写屏障，则直接挂在 对象1 下面。
  2. 对象4 删除了 对象7 的引用，因为 对象4 在堆上，所以触发写屏障机制（删除即将值写为null），此时标记被删除的 对象7 为灰色。 下一轮就会遍历 对象7，如果 对象7 有下游就会继续遍历，如果 对象7 没有下游就会被标记为黑色。这样就保护了 对象7。

这样所有有效对象最终都会被标记为黑色，栈上也就不需要再次扫描了，也不用通过STW机制来进行保护了。

示例2

场景：对象3 被 栈对象2 删除引用，并成为另一个 栈对象9 的下游。

flowchart LR
  栈[栈:不启用屏障] --> 对象1 --> 对象2 -.X删除引用X.-x 对象3
  栈[栈:不启用屏障] --创建对象--> 对象9
  对象9 --添加引用--> 对象3
  1. 在栈上新创建 对象9，标记为黑色。(混合写屏障，GC过程种任何新创建的对象都标记为黑色）
  2. 对象9 添加下游引用 栈对象3。(直接添加，栈不启用屏障机制)
  3. 对象2 删除 对象3 的引用。（直接删除，栈不启用写屏障机制）

如果 对象9 没有引用 对象3，对象2 直接删除了 对象3：这种情况下 对象3 会先变为灰色被保护。等到下一轮GC,对象3 就会被标记为白色对象，然后被清理。

示例3

场景：堆对象7 被 堆对象4 删除引用，成为另一个 堆对象10 的下游。

flowchart LR
  堆[堆:启用屏障] --> 对象4 -.X删除引用X.-x 对象7 --> 对象8
  堆[堆:启用屏障] ---> 对象10 --> 对象11
  对象10 --添加引用--> 对象7
  1. 堆对象10 被扫描，并被标记为黑色。
  2. 堆对象10 添加引用 堆对象7。（触发插入写屏障机制，被添加的 对象7 被标记为灰色，对象8被保护）
  3. 堆对象4 删除引用 堆对象7。（触发删除写屏障机制，被删除的 对象7 被标记为灰色）

示例4

场景：对象2 从一个 栈对象1 删除引用，成为另一个 堆对象4 的下游。

//伪代码
栈对象1.对象2 = nuLl
堆对象4.对象2 = 栈对象2
堆对象4.对象7 = null

flowchart LR
  栈[栈:不启用屏障] --> 对象1 -.X删除引用X.-x 对象2 --> 对象3
  堆[堆:启用屏障] --> 对象4 -.X删除引用X.-x 对象7 --> 对象8
  对象4 --添加引用--> 对象2
  1. 栈对象1 删除对 栈对象2 的引用。（直接删除，栈不启用屏障机制）
  2. 堆对象4 删除引用 对象7，同时 对象4 添加引用 对象2。(启用删除写屏障机制，对象7 被删除引用同时被标记为灰色，后面会继续扫描 对象7，这样就保护了 对象7 与它的下游对象)