垃圾回收是什么？

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

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

1. 暂停程序，分析当前程序可达的对象
2. 对于所有可达的对象做上标记
3. 清除未标记的对象
4. 停止暂停，程序业务逻辑继续运行，然后重复该过程。

缺点

1. stw：gc时程序需要暂停
2. 标记需要扫描整个heap
3. 清楚数据会产生heap碎片

gov1.3版本将步骤4提前到步骤3，即sweep清楚时，并不需要暂停整个程序

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

1. 每次新创建的对象，默认的颜色都是标记为“白色”
2. 每次GC回收开始, 会从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合【遍历是一次遍历，非递归形式，是从程序抽次可抵达的对象遍历一层】
3. 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合【遍历是一次遍历，非递归形式，是从程序抽次可抵达的对象遍历一层】
4. 重复第三步, 直到灰色中无任何对象
5. 回收所有白色对象

没STW的三色标记法

当三色标记法同时出现以下两种情况时，会出现对象丢失：

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

屏障机制

为了避免不使用STW，同时不存在对象丢失的情况，于是设计了屏障机制。

通过上述描述发现，当GC回收期满足以下两种情形之一时，即可不丢失对象。

• “强-弱” 三色不变式
  1. 强三色不变式：不存在黑色对象引用到白色对象的指针。
  2. 弱三色不变式：所有被黑色对象引用的白色对象都处于灰色保护状态。【灰色对象直接引用或它的链路上游存在灰色对象】

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

• 插入屏障

具体操作：当黑色对象引用白色对象时，白色对象被标记为灰色。 满足：强三色不变式

伪代码：

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

场景：

1. 黑色对象直接添加下游对象
2. 黑色对象替换下游引用对象

适用情况： 这段伪码逻辑就是写屏障, 黑色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小, 但是要求相应速度快, 因此栈空间内并不使用，仅适用于堆

• 删除屏障

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

伪代码：

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

场景：

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

适用情况： 一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。

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

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

Go V1.8 混合写屏障

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
}

• 注意点 屏障技术是不在栈上应用的，因为要保证栈的运行效率

场景

1. 对象被一个堆对象删除引用，成为栈对象的下游【堆对象删除引用置为灰】
2. 对象被一个栈对象删除引用，成为另一个栈对象的下游【栈对象删除引用，不变色】
3. 对象被一个堆对象删除引用，成为另一个堆对象的下游【堆对象删除引用、被另一个堆对象添加引用，置为灰】
4. 对象从一个栈对象删除引用，成为另一个堆对象的下游【栈对象本身为黑，堆对象转移引用，删除引用的堆对象置为灰】

总结

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

总结

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

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

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

引用

Golang三色标记混合写屏障GC模式全分析 (opens new window)