垃圾回收(Garbage Collection,简称GC)是现代编程语言中的重要特性之一,它可以自动地管理内存,帮助开发人员避免内存泄漏和悬空指针等问题。Go语言(Golang)作为一门以效率和并发性为特点的编程语言,也采用了一种高效的垃圾回收机制来管理内存,让开发者能够专注于业务逻辑而不必过多关心内存管理的问题。
Golang在GC的演进过程中也经历了很多次变革,大概分为「3个阶段」
接下来我们来一个一个的剖析
标记清除法主要有三个步骤
可达对象主要是指程序和对象有可达关系的对象。以上图为例,可达对象为 「对象1->对象2->对象3」、「对象4->对象7」五个对象。
不可达对象为 对象5、对象6
整个标记清除法其实非常简单,过程也很明了,但是也有很严重的问题
上面最严重的问题其实是STW,Go V1.3 专门针对这个问题做了一期的优化
我们可以看到标记和清除过程都是在整个STW的生命周期里面的,所以STW的时间就特别长Go V1.3 做了简单的优化,将STW的步骤提前, 减少STW暂停的时间范围(如下图所示),因为在清除非可达对象的时候,是不需要程序停止的。
所谓三色标记法其实就是用三种不同的颜色(灰白黑)来标记各个对象的状态,最后统一回收白色对象,保留黑色对象(灰色对象为过渡态)的方式。让我们来看一看具体过程。
右边的标记表其实就是三种不同颜色的集合,被标记成哪种颜色,则对象就在哪个集合中。左边所说的程序,其实是一系列对象的根节点,如果我们把程序展开,则得到类似的表现形式
我们从三色标记法的过程不难看出,里面会有很多并发流程均会被扫描,执行并发流程的内存可能存在相互依赖。所以为了保证GC过程中的数据安全性,三色标记法在开始之前同样会加上「STW」(stop the world),在扫描确定所有黑白对象之后才会停止「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被标记为灰色
这段伪码逻辑就是写屏障, 我们知道,黑色对象的内存槽有两种位置, 「栈」和「堆」. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,「在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中」. 为了更好的理解,我们来看这样的一个过程
一般情况下现在就应该回收白色元素了。但是我们直接肉眼观察是有问题的,因为对象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之前为白)
为了更好的理解,我们来看看下面的流程。
在三色标记的过程中,对象1还未来得及把对象5标记为灰色的时候就已经断开了链接。可想而知,这么执行下去的话对象5以及对象2对象3后面都会被清除。
但是如果触发了删除写屏障,那么对象5会被标记为灰色。这样后面循环下去,对象5,2,3都会逐一被标记为黑色。从而正确的被保护
这种方式的回收精度低,一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮,在下一轮GC中被清理掉。
Go V1.8版本引入了混合写屏障机制(hybrid write barrier),避免了对栈re-scan的过程,极大的减少了STW的时间。结合了两者的优点。
接下来我们来看看全流程。
先把栈上的对象全部标记为黑色。
因为在堆对象删除的时候,触发了写屏障,所以对象7被标记成了灰色。保证后续安全
我们可以看到对象3被对象2删除引用,成为了对象9(因为对象9在栈空间,所以一创建就是黑色)的下游,因为对象3一直都是黑色,所以一直安全。
GoV1.3- 普通标记清除法,整体过程需要启动STW,效率极低。
GoV1.5- 三色标记法, 堆空间启动写屏障,栈空间不启动,全部扫描之后,需要重新扫描一次栈(需要STW),效率普通
GoV1.8-三色标记法,混合写屏障机制, 栈空间不启动,堆空间启动。整个过程几乎不需要STW,效率较高。