Golang GC(垃圾回收)机制

Go的所有实现版本都没有单独用过删除写屏障，GoGC的历次迭代为标记清楚-插入写屏障-混合写屏障，且插入写屏障和混合写屏障对栈上都不操作。

GC机制简介

GC，Garbage Collection，垃圾回收机制。
在Golang版本更迭中，GC的实现方法也经历了几次大的改进，分别是Go V1.3、Go V1.5以及Go V1.8三个版本。
注:文章中的图片均引自Golang中GC回收机制三色标记与混合写屏障

Before Go V1.3 标记-清除(mark and sweep)法

假设当前某个程序与对象之间的引用关系如下图所示，箭头表示某个对象引用另一个对象：
这时，如果触发GC操作，首先第一步会执行一个STW暂停，并将全部的可达对象进行一个标记。
而没有被标记的对象(对象5和对象6)，说明当前程序已经不需要它了，因此回收。回收之后。STW暂停就结束了，程序恢复。

标记-清除法的缺点

• 在标记之前会有一个STW(stop the world)暂停操作，让程序暂停，程序会出现卡顿（最重要的缺点）
• 标记需要扫描整个heap
• 清除数据会产生heap碎片

Go V1.5 三色标记法

三色标记法在GC中统计三个表，分别是White白色标记表、Grey灰色标记表以及Black黑色标记表。

• 程序起初创建，全部标记为白色，将所有对象放入白色集合中。
  注：程序中是有根节点的，程序包括根节点集合，GC根据当前程序的业务逻辑，从根集合中遍历根节点，看他们指向的对象。
• 遍历Root Set（非递归形式，只遍历一次，即只遍历与根节点挨着的对象），得到灰色节点。
  
• 遍历Grey灰色标记表，将可达的对象，从白色标记为灰色；遍历之后的灰色，标记为黑色
  注：我们的目标是灰色节点集合为空，只有白色和黑色节点，回收白色节点，因此还要继续遍历
• 重复上一步，直到灰色标记表中无任何对象
• 回收白色对象
  

STW讨论

整体的三色标记是没有加STW的
在没有STW的情况下，三色标记法最不希望发生的事：

• 一个白色对象被黑色对象引用（白色对象被挂在黑色对象下）
• 这个白色对象与一个灰色对象间的可达关系遭到破坏（即有一个灰色丢弃了这个被黑色对象引用的白色）

上面的两种情况同时发生会导致黑色对象引用的白色对象被回收，造成错误。

但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响。

如何能在保证对象不丢失的情况尽可能的提高GC效率，减少STW时间呢？

破坏两个条件同时成立！

强三色不变式

即强制性的不允许黑色对象引用白色对象来破坏条件1

弱三色不变式

黑色对象可以引用白色对象，但白色对象存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象 来破坏条件2

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

采用屏障机制来实现强三色/弱三色……

屏障机制

屏障：在我们程序执行的某个流程中，可以额外的在中间加一层判断机制。如图所示： 思想：在不打扰正常业务的流程的情况下，做一些额外的判断。
屏障机制有插入屏障和删除屏障：

插入屏障

• 具体操作：在A对象引用B对象的时候，B对象被标记为灰色。（将B挂载A的下游，B被标记为灰色）
• 满足：强三色不变式。（不存在黑色对象引用白色对象的情况了，因为白色会强制变成灰色）
  场景：

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

  注：为了不影响性能，插入屏障不在栈上使用。
  
  
  
  
  
  然后停止STW，再做清除。

插入写屏障的不足：
结束时需要STW来重新扫描栈，大约需要10~100ms

删除屏障

具体操作：被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。
满足：弱三色不变式。（保护灰色对象到白色对象的路径不会断）
场景：

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

对象5已经被对象1删除，但是为什么没有回收呢？

• 清除对象5，如果对象5又被一个黑色对象引用了，那样就会造成错误；所以本轮先不删除，在下一轮GC的时候，对象5就会被删除，即保留一轮，下一轮删。

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

删除写屏障也有一个STW的过程。

Go V1.8的三色标记法+混合写屏障机制

具体操作

1. GC开始将栈上的对象全部扫描标记为黑色（之后不再进行第二次重复扫描，无需STW）
2. GC期间，任何在栈上创建的新对象，均为黑色。
3. 被删除的对象标记为灰色
4. 被添加的对象标记为灰色
   满足：变形的弱三色不变式。（结合了插入、删除写屏障两者的优点）