Go GC机制

5、Golang三色标记混合写屏障GC模式全分析 (yuque.com)

垃圾回收(Garbage Collection，简称GC)是编程语言中提供的自动的内存管理机制，自动释放不需要的内存对象，让出存储器资源。GC过程中无需程序员手动执行。GC机制在现代很多编程语言都支持，GC能力的性能与优劣也是不同语言之间对比度指标之一。

发展过程

Go V1.3之前的标记-清除(mark and sweep)算法，Go V1.3之前的标记-清扫(mark and sweep)的缺点

Go V1.3之前的标记-清除(mark and sweep)算法

接下来我们来看一下在Golang1.3之前的时候主要用的普通的标记-清除算法，此算法主要有两个主要的步骤：

• 标记(Mark phase)
• 清除(Sweep phase)

STW会对可达对象做上标记，然后对不可达对象进行GC回收

操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 STW(stop the world)，STW的过程中，CPU不执行用户代码，全部用于垃圾回收，这个过程的影响很大，所以STW也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间，程序会暂定停止任何工作，卡在那等待回收执行完毕。

mark and sweep 算法 缺点

1. STW会让程序暂停，使程序出现卡顿(重要问题)
2. 标记需要扫描整个heap
3. 清除数据会产生heap碎片

stw暂停范围

从上图来看，全部的GC时间都是包裹在STW范围之内的，这样貌似程序暂停的时间过长，影响程序的运行性能。所以Go V1.3 做了简单的优化,将STW的步骤提前, 减少STW暂停的时间范围.如下所示

上图主要是将STW的步骤提前了一步，因为在Sweep清除的时候，可以不需要STW停止，因为这些对象已经是不可达对象了，不会出现回收写冲突等问题。

但是无论怎么优化，Go V1.3都面临这个一个重要问题，就是mark-and-sweep 算法会暂停整个程序 。

Go是如何面对并这个问题的呢？接下来G V1.5版本 就用三色并发标记法来优化这个问题.

GoV1.5三色标记法

三色标记法无STW的问题

我们加入如果没有STW，那么也就不会再存在性能上的问题，那么接下来我们假设如果三色标记法不加入STW会发生什么事情？ 我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性，我们来看看一个场景，如果三色标记法, 标记过程不使用STW将会发生什么事情?

我们把初始状态设置为已经经历了第一轮扫描，目前黑色的有对象1和对象4， 灰色的有对象2和对象7，其他的为白色对象，且对象2是通过指针p指向对象3的，如图所示。

现在如何三色标记过程不启动STW，那么在GC扫描过程中，任意的对象均可能发生读写操作，如图所示，在还没有扫描到对象2的时候，已经标记为黑色的对象4，此时创建指针q，并且指向白色的对象3。

与此同时灰色的对象2将指针p移除，那么白色的对象3实则就是被挂在了已经扫描完成的黑色的对象4下，如图所示。

然后我们正常指向三色标记的算法逻辑，将所有灰色的对象标记为黑色，那么对象2和对象7就被标记成了黑色，如图所示。

那么就执行了三色标记的最后一步，将所有白色对象当做垃圾进行回收，如图所示。

但是最后我们才发现，本来是对象4合法引用的对象3，却被GC给“误杀”回收掉了。

GC误杀条件

可以看出，有两种情况，在三色标记法中，是不希望被发生的。

• 条件1: 一个白色对象被黑色对象引用**(白色被挂在黑色下)**
• 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)** 如果当以上两个条件同时满足时，就会出现对象丢失现象!

屏障机制

为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响。那么是否可以在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？答案是可以的，我们只要使用一种机制，尝试去破坏上面的两个必要条件就可以了。

强三色不变式

强制性的不允许黑色对象引用白色对象

破坏条件1

弱三色不变式

黑色对象可以引用白色对象，但是要保证白色独享存在其它灰色对象对它的引用，或者可达它的链路上游存在灰色对象

破坏条件2

为了遵循上述的两个方式，GC算法演进到两种屏障方式，他们“插入屏障”, “删除屏障”。

插入屏蔽

不在栈上使用

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

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

1
2
3
4
5
6
7

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

这里说一下这个过程，首先因为插入屏障不在栈上使用

下面的图里面，已经进行了一次三色标记，外界向对象4添加对象8，对象1添加对象9，但是我们知道，对象1在栈上，所以它不会应用插入屏障，也就是说，这个时候对象 9不会按照插入屏障的规则设置为灰色，而对象4在堆上，因此它会应用插入屏障，所以会把对象8设置为灰色，然后我们进行第二次三色标记，从灰色对象出发(对象2，对象7，对象8) ，找可达对象(对象3)，因此将对象3设置为灰色，然后对象2,7,8设置为黑色，接着进行第三次三色标记，从灰色对象出发(对象3)，发现没有可达对象，因此设置对象3为黑色，这个时候我们有黑色对象: 对象1，对象2，对象3，对象4，对象7，对象8.

按照常理我们这个时候应该进行垃圾回收了对吧，其实不然，我们这个时候要把栈空间的对象全部设置为白色，然后使用STW暂停栈空间(对象1，对象2，对象3，对象9，对象5)，防止外界干扰（再有对象被添加到黑色对象下)

然后我们对栈空间重新进行一次三色标记，直到没有灰色对象

过程如下：

从对象1出发，设置对象1为灰色，接下来看从对象1走的可达对象，发现可达对象有对象2和对象9，因此我们把对象2和对象9设置为灰色对象，把对象1设置为黑色对象，然后我们再从灰色对象出发(对象2和对象9)，发现对象2可达对象3，对象9没有可达对象，因此把对象3设置为灰色对象，对象2,9设置为黑色对象，接下来从灰色对象(此时只有对象3)出发，发现对象3没有可达对象，设置对象3为黑色对象。至此栈里面已经没有灰色对象，我们先暂停STW，然后进行最后的GC回收，可以发现白色对象只有 对象5，对象6，因此对白色对象进行清除。

至此，GC三色标记并发情况下的插入屏障流程完毕

删除屏蔽

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

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

1
2
3
4
5
6
7
8
9

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

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

混合屏障Go V1.8

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

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

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

具体操作:

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

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

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

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