揭秘Go语言GC(垃圾回收)的技术演进

程序员小饭

发布于 2023-09-06 09:04:07

7680

发布于 2023-09-06 09:04:07

文章被收录于专栏：golang+php

前言

垃圾回收（Garbage Collection，简称GC）是现代编程语言中的重要特性之一，它可以自动地管理内存，帮助开发人员避免内存泄漏和悬空指针等问题。Go语言（Golang）作为一门以效率和并发性为特点的编程语言，也采用了一种高效的垃圾回收机制来管理内存，让开发者能够专注于业务逻辑而不必过多关心内存管理的问题。

Golang在GC的演进过程中也经历了很多次变革，大概分为「3个阶段」

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

接下来我们来一个一个的剖析

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

标记清除法主要有三个步骤

暂停STW(stop the world)
标记(Mark phase)
清除(Sweep phase)
停止暂停

标记清除法的具体步骤

「暂停」整个程序业务逻辑，区分出「可达对象」和不可达对象，然后做上标记

可达对象主要是指程序和对象有可达关系的对象。以上图为例，可达对象为 「对象1->对象2->对象3」、「对象4->对象7」五个对象。

不可达对象为对象5、对象6

对程序的可达对象进行标记，如下图所示

标记完成之后，对未标记的对象进行清除，如下图所示

程序停止暂停，继续跑起来。然后一直循环重复这个过程，一直到整个程序生命周期结束

标记清除法的缺点

整个标记清除法其实非常简单，过程也很明了，但是也有很严重的问题

首先他的第一步就是STW(stop the world),程序暂停之后会出现卡顿的，这个影响非常严重
标记可达对象和非可达对象的时候需要扫描整个heap，复杂度也比较高
在清除非可达对象的时候会产生很多heap碎片

上面最严重的问题其实是STW，Go V1.3 专门针对这个问题做了一期的优化

我们可以看到标记和清除过程都是在整个STW的生命周期里面的，所以STW的时间就特别长Go V1.3 做了简单的优化,将STW的步骤提前, 减少STW暂停的时间范围(如下图所示)，因为在清除非可达对象的时候，是不需要程序停止的。

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

所谓三色标记法其实就是用三种不同的颜色(灰白黑)来标记各个对象的状态，最后统一回收白色对象，保留黑色对象（灰色对象为过渡态）的方式。让我们来看一看具体过程。

三色标记法的步骤

每次新建的对象，默认全部都是白色

右边的标记表其实就是三种不同颜色的集合，被标记成哪种颜色，则对象就在哪个集合中。左边所说的程序，其实是一系列对象的根节点，如果我们把程序展开，则得到类似的表现形式

GC开始回收，则从根节点开始遍历对象，把遍历到的对象全部标记为灰色

注意这里所说的遍历，只遍历根节点下面一个层级的对象(也就是对象1和对象4)，把他们标记为灰色
右边对应的把对象1和对象4从白色标记表的集合中放到了灰色的标记表集合中

把上一步的所有灰色标记表集合中的对象（对象1、对象4）全部遍历一遍，把「遍历到的可达对象标记为灰色」，同时把「灰色对象本身(对象1、对象4)，标记为黑色」

遍历对象1，则可以把对象2标记为灰色，同时把对象1标记为黑色
遍历对象4，则可以把对象7标记为灰色，同时把对象4标记为黑色

一直重复上一步，直到灰色标记表中无任何对象为止

第一次重复

第二次重复

回收所有被标记为白色的对象，也就是进行垃圾回收

三色标记法存在的问题

我们从三色标记法的过程不难看出，里面会有很多并发流程均会被扫描，执行并发流程的内存可能存在相互依赖。所以为了保证GC过程中的数据安全性，三色标记法在开始之前同样会加上「STW」(stop the world),在扫描确定所有黑白对象之后才会停止「STW」。这样的效率和性能同样是比较低的，同时会引起程序卡顿。

如果不启动STW会发生什么

我们回到上面的例子，假设我们已经执行完了初始一次的扫描，标记了部分对象颜色，此时对象2是指向对象3的，也就是说正常情况下下一次扫描执行之后应该是对象2被标记为黑色，对象3被标记为灰色。

因为整个过程是没有启动STW的，所以任何情况都是有可能发生的。所以如果标记扫描还没有扫描到2的时候，「对象4突然指向了对象3」，「同时对象2对对象3的指向断开」(不要习惯性的觉得不会这么巧，程序在跑着的时候任何情况都是会发生的)，情况如下图。

然后我们按照三色标记法的计算逻辑执行下去，将所有灰色对象标记为黑色，那么2和7就会被被标记为黑色，如图所示

然后白色对象会被全部清除，剩下黑色对象。明显这样的GC处理是不合理的，因为对象3是不应该被清除的。

屏障机制

GC在进行垃圾回收的时候，满足下面两种情况之一时，即可保对象不丢失。这两种方式就是「强三色不变式」和「弱三色不变式」。

强三色不变式

不允许黑色对象直接指向白色对象，这样就不会有白色对象被误删的情况

弱三色不变式

所有被黑色对象引用的白色对象都处于灰色保护状态。弱三色不变式强调，黑色对象可以引用白色对象，但是白色对象上游必须有灰色对象来保证其安全被扫描到

基于上面两种方式，golang的GC算法演化出了两种屏障方式，他们就是「插入屏障」和「删除屏障」

插入屏障

方式：在A对象引用(指向)B对象的时候，B对象被强制标记为灰色。

依据:「强三色不变式」

源码(伪代码)实现

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

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

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

程序根节点是分为栈空间和堆空间的，只有堆空间的对象启用插入屏障机制
因为并发等各种原因，此时对象4需要指向对象8，对象1需要指向对象9

因为对象4在堆空间，启用了插入屏障，所以对象8被标记为灰色
因为对象1在栈空间，未启用插入屏障，所以对象9依然为白色。
上述流程三色标记循环完之后状态如下

一般情况下现在就应该回收白色元素了。但是我们直接肉眼观察是有问题的，因为对象9其实是不应该被回收的，但是栈空间的元素又没有启动插入屏障机制，所以为了解决这个问题，于是对栈空间的元素在准备回收之前，「重新进行了一次三色标记扫描」，为了扫描数据不被丢失，在「重新扫描之前还启动了一次STW的保护」，直到栈空间的元素三色扫描结束

开始重新扫描

重新扫描结束

最后直接全部清除白色元素即可。虽然这个流程也启动了STW，但是只是对栈空间的启动，相对之前的全局启动STW性能要提高很多倍。

删除屏障

方式：被删除的对象，如果自身为灰色或者白色，则被强制标记为灰色

依据：弱三色不变式

实现源码(伪代码)

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

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

为了更好的理解，我们来看看下面的流程。