三色标记+混合写屏障｜Go 语言垃圾回收机制

发表于 | 分类于

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

Golang在GC的演进过程中也经历了很多次变革:

  1. V1.3之前的标记-清除(mark and sweep)算法
  2. V1.5的三色标记法
  3. V1.8混合写屏障机制

何时触发GC

触发条件从大方面说，可分为:

  • 手动触发: 一般很少用，主要由开发者通过调用 runtime.GC()
  • 系统触发: Go 的 runtime 根据一些条件判断来进行的

3 种系统触发，源码中定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// A gcTrigger is a predicate for starting a GC cycle. Specifically,
// it is an exit condition for the _GCoff phase.
type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: current time
    n    uint32 // gcTriggerCycle: cycle number to start
}
type gcTriggerKind int
const (
    // gcTriggerHeap indicates that a cycle should be started when
    // the heap size reaches the trigger heap size computed by the
    // controller.
    gcTriggerHeap gcTriggerKind = iota
    // gcTriggerTime indicates that a cycle should be started when
    // it's been more than forcegcperiod nanoseconds since the
    // previous GC cycle.
    gcTriggerTime
    // gcTriggerCycle indicates that a cycle should be started if
    // we have not yet started cycle number gcTrigger.n (relative
    // to work.cycles).
    gcTriggerCycle
)

gcTriggerHeap

当前分配的内存达到一定阈值时触发，这个阈值在每次GC过后都会根据堆内存的增长情况和CPU占用率来调整。例如：

运行时GC Percentage参数默认为100，你程序的上一次GC完，驻留内存是10MB，那么下一次堆内存达到20MB，会触发GC；如果设置的200，那么下一次堆内存达到30MB（30/10=200%）会触发GC。

gcTriggerTime

自从上次GC后间隔时间达到了 runtime.forcegcperiod 时间（默认为2分钟），将启动GC；sysmon 线程负责监控

gcTriggerCycle

如果当前还没有开始第 N 轮垃圾收集，则启动GC，主要是runtime.GC()

下面介绍 GO 垃圾回收机制的演进历史：

mark and sweep

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

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

具体步骤

  1. 暂停程序业务逻辑(STW)，分类出可达和不可达的对象，然后做上标记。
  2. 开始标记，程序找出它所有可达的对象，并做上标记。
  3. 标记完了之后，然后开始清除未标记的对象。
  4. 停止暂停，让程序继续跑。

循环重复上述过程，直到程序生命周期结束。

缺点

标记清除算法明了，过程鲜明干脆。但是也有非常严重的问题：

  • STW: stop the world，让程序暂停，程序出现卡顿 (重要问题)；
  • 标记需要扫描整个heap；
  • 清除数据会产生heap碎片。

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

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

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

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

三色标记法

​Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的STW(stop the world)，所谓三色标记法实际上就是通过三种颜色的标记来确定清楚的对象都有哪些？我们来看一下具体的过程。

第一步，每次新创建的对象，默认的颜色都是标记为“白色”，如图所示。

第二步, 每次GC回收开始, 会从根节点开始遍历所有对象，把 遍历到 的对象从白色集合放入“灰色”集合，如图所示。

第三步, 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合，如图所示。

第四步, 重复第三步, 直到灰色中无任何对象，如图所示。

当我们全部的可达对象都遍历完后，灰色标记表将不再存在灰色对象，目前全部内存的数据只有两种颜色，黑色和白色。那么黑色对象就是我们程序逻辑可达（需要的）对象，这些数据是目前支撑程序正常业务运行的，是合法的有用数据，不可删除，白色的对象是全部不可达对象，目前程序逻辑并不依赖他们，那么白色对象就是内存中目前的垃圾数据，需要被清除。

第五步: 回收所有的白色标记表的对象. 也就是回收垃圾，如图所示。

以上便是三色并发标记法，不难看出，我们上面已经清楚的体现三色的特性。但是：这里面可能会有很多并发流程均会被扫描，执行并发流程的内存可能相互依赖，为了在GC过程中保证数据的安全：

在开始三色标记之前就会加上STW，在扫描确定黑白对象之后再放开STW。

但是很明显这样的GC扫描的性能实在是太低了，那么Go是如何解决标记-清除算法中的卡顿问题的呢？

没有STW的三色标记法

如果三色标记过程不启动 STW，可能会发生什么情况？

由于没有 STW，在GC扫描过程中，任意的对象均可能发生读写操作。

我们把初始状态设置为已经经历了第一轮扫描，目前黑色的有对象1和对象4，灰色的有对象2和对象7，其他的为白色对象，且对象2是通过指针p指向对象3的。在还没有扫描到对象2的时候，已经标记为黑色的对象4，此时创建指针q，指向白色的对象3。如下图所示：

结果：本来是对象4合法引用的对象3，却被GC给“误杀”回收掉了，白色对象3还有很多下游对象的话, 也会一并都清理掉。

在三色标记法中，是不希望被发生的：

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

如果当以上两个条件同时满足时，就会出现对象丢失现象!

为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对用户程序有很大的性能影响。

那么是否可以在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？

只要使用一种机制，尝试去破坏上面的两个必要条件就可以了。

屏障机制

我们让GC回收器，满足下面两种情况之一时，即可保证对象不丢失。

  1. 强三色不变式：不存在黑色对象引用到白色对象的指针。

  2. 弱三色不变式：所有被黑色对象引用的白色对象都处于灰色保护状态。

为了遵循上述的两个方式，GC算法演进到两种屏障方式：

  • 插入屏障
  • 删除屏障

插入屏障

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

满足: 强三色不变式(不存在黑色对象引用白色对象的情况)

伪码如下:

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

场景：

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

黑色对象的内存槽有两种位置：栈和堆，栈空间的特点是容量小，但是要求相应速度快(因为函数调用弹出频繁使用)，所以:

插入屏障机制，在栈空间的对象操作中不使用，仅在堆空间的对象的操作中。

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

删除屏障

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

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

伪代码：

1
2
3
4
5
6
7
8
9
添加下游对象(当前下游对象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之前为白)

短板：

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

混合写屏障机制

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

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

伪代码：

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

这里注意：

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

具体操作:

  1. GC开始将栈上的可达对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)
  2. GC期间，任何在栈上创建的新对象，均为黑色。
  3. 被删除的对象标记为灰色。
  4. 被添加的对象标记为灰色。

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

伪代码：

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

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

伪代码:

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

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

伪代码：

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

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

伪代码：

1
2
3
栈对象1->对象2 = null；         //对象1 删除引用 对象2
堆对象4->对象2 = 栈对象2；       //对象4 挂在 添加 下游 栈对象2
堆对象4->对象7 = null；         //对象4 删除引用 对象7

总结

  1. GoV1.3：普通标记清除法，整体过程需要启动STW，效率低。
  2. GoV1.5：三色标记法，堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通。
  3. GoV1.8：三色标记法，混合写屏障机制，栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。
彦祖老师 wechat