垃圾回收(Garbage Collection，简称GC)是编程语言中提供的自动的内存管理机制，自动释放不需要的对象，让出存储器资源，无需程序员手动执行。

Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的STW(stop the world)，STW的过程中，CPU不执行用户代码，全部用于垃圾回收，这个过程的影响很大，Golang进行了多次的迭代优化来解决这个问题。

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

标记清除算法有两个主要步骤：即标记(Mark phase)和清楚(Sweep phase)

第一步，暂停程序业务逻辑，找出不可达的对象，做上标记。第二步，回收标记好的对象

这两步操作非常简单，但需要注意的是中间会有STW(stop the world)，即让程序暂停，这一点是对程序的使用体验非常致命的

第二步，开始标记，程序找出它所有可达的对象，并做上标记

第三步，标记完了之后，然后开始清除未标记的对象

第四步，停止暂停，程序继续运行。然后循环重复这个过程，直到process程序生命周期结束

标记-清除(mark and sweep)算法的缺点

• STW，即stop the world，会让程序出现卡顿（这一点最为致命）
• 标记需要扫描整个Heap
• 清除数据会产生Heap碎片

Go V1.3版本之前就是通过以上算法来实施GC的，流程如下

Go V1.3 做了简单的优化，将STW提前，减少STW暂停的时间范围，如下所示

STW是这个版本GC最致命的缺点，接下来的Go V1.5版本依靠三色并发标记法来进行优化

Go V1.5的三色并发标记法

三色标记法实际上就是通过三个阶段的标记来确定清楚的对象的状态

第一步，程序创建伊始，全部对象标记为白色并放入白色集合

注意：所谓“程序“，是一些对象的根节点集合

第二步，每次GC回收开始，从根节点遍历所有对象，将遍历到的对象从白色集合放入灰色集合

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

第四步，重复第三步，直至灰色集合中无任何对象

第五步，回收所有白色集合的对象

上述即是三色并发标记法的具体流程

没有STW的三色标记法

在三色标记法中，有两种问题如果同时发生便会造成对象丢失

1. 一个白色对象被黑色对象引用**(白色被挂在黑色下)**
2. 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)**

为了防止这种情况造成的丢失，最简单的方法就是STW，但STW的过程有非常巨大的资源浪费并对用户体验有极大影响，所以我们需要一种机制去破坏上述两个条件来达成这个问题的解决。

屏障机制

”强-弱“三色不变式

• 强三色不变式

不存在黑色对象引用到白色对象的指针，强制性的不允许黑色对象引用白色对象

• 弱三色不变式

所有被黑色对象引用的白色对象都处于灰色保护状态。即黑色对象可以引用白色对象，白色对象存在其他灰色对象对它的引用，或者可达它链路上游存在灰色对象

插入屏障

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

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

伪码如下:

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

场景：

A.添加下游对象(nil, B)   //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象C 更换为B，  B被标记为灰色

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

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

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

删除屏障

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

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

伪代码：

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

场景：

A.添加下游对象(B, nil)   //A对象，删除B对象的引用。  B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C)		 //A对象，更换下游B变成C。   B被A删除，被标记为灰(如果B之前为白)

Go V1.8的混合写屏障(hybrid write barrier)机制

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

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

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

---

混合写屏障规则

具体操作:

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

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

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

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

满足: 变形的弱三色不变式

伪代码：

添加下游对象(当前下游对象slot, 新下游对象ptr) {
  	//1 
		标记灰色(当前下游对象slot)    //只要当前下游对象被移走，就标记灰色
  	
  	//2 
  	标记灰色(新下游对象ptr)
  		
  	//3
  	当前下游对象slot = 新下游对象ptr
}

这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。

混合写屏障的具体场景分析

GC开始：扫描栈区，将可达对象全部标记为黑

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

伪代码

//前提：堆对象4->对象7 = 对象7；  //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7；  //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null；    //对象4 删除引用 对象7

场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游

伪代码

new 栈对象9；
对象8->对象3 = 对象3；      //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null；      //对象2 删除引用 对象3

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

伪代码

堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

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

伪代码

堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

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

总结

以上便是Golang的GC全部的标记-清除逻辑及场景演示全过程

GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低

GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通

GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高

参考

Golang修养之路