垃圾回收(Garbage Collection)是编程语言提供的自动内存管理机制,能够自动释放不需要的内存对象,无需程序员手动管理。Go语言的GC也经历了多次变革,从V1.3之前的标记清除法,到V1.5的三色并发标记法,再到V1.8的混合写屏障机制,今天我们就来了解一下这几种方法以及他们的优缺点。
标记清除法
此算法主要有两个步骤:标记、清除。过程非常清晰明了,实际是找到需要被清除的内存数据,然后一次性清除。
详细过程
第一步,暂停程序业务逻辑, 分类出可达和不可达的对象,然后做上标记。
第二步,对程序的所有可达对象做上标记。
第三步,清除未被标记的对象,结果如下:
操作非常简单,但是标记清除算法在执行的时候,需要程序暂停!即 STW(stop the world)
,STW的过程中,CPU不执行用户代码,全部用于垃圾回收,这个过程的影响很大,STW也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间,程序会暂定停止任何工作,等待回收执行完毕。
缺点
标记清除算法的过程非常清晰明了,但它有几个严重的问题:
- STW会让程序出现卡顿
- 标记时需要扫描整个堆内存
- 清除数据时会产生堆内存碎片
我们知道,STW主要包括:启动STW、标记、清除、停止STW这几个过程。实际上,清除的时候不需要STW,因为这些对象已经不可达了,所有可以把STW优化为启动STW、标记、停止STW这三个过程,但还是会暂停整个程序,因此,Go在V1.5版本引入了三色标记法。
三色标记法
Go语言中的垃圾回收主要应用三色标记法,GC过程和用户协程可以并发运行,但还是需要一定时间的STW,三色标记法实际上就是通过三个阶段的标记来确定需要清楚的对象有哪些。
三色标记法的过程
首先,每次新创建的对象都被标记为白色,每种颜色的对象我们用一个集合来存放。
注意,我们可以把程序看做是对象的根节点的集合,展开后就如下图所示。
然后,每次GC开始,会从根节点开始遍历所有对象,把遍历到的对象从白色集合放入灰色集合(一次遍历,不递归):
接着,遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,完成后将此灰色对象放入黑色集合,重复此步骤直到灰色集合为空。
这时,程序中的所有对象要么被黑色标记、要么被白色标记,白色的对象是全部不可达对象。
最后,回收所有的白色标记表的对象. 也就是回收垃圾。
为了在GC过程中保证数据的安全,我们在开始三色标记之前就会加上STW,在扫描确定黑白对象之后再放开STW。但是很明显这样的GC扫描的性能实在是太低了。
那么Go是如何解决卡顿(STW,Stop The World)问题的呢?
没有STW的三色标记法
没有STW,就不会存在性能上的问题,那如果我们使用三色标记法的时候不加入STW会发生什么?
我们把状态设置为如图所示,目前黑色的有对象1和对象4, 灰色的有对象2和对象7,其他的为白色对象,且对象2通过指针p指向对象3:
如果三色标记过程不启动STW,那么在GC扫描过程中,任意的对象均可能发生读写操作,如图所示,在还没有扫描到对象2的时候,已经标记为黑色的对象4,此时创建指针q,并且指向白色的对象3。
与此同时灰色的对象2将指针p移除,那么白色的对象3实则就是被挂在了已经扫描完成的黑色的对象4下,如图所示。
然后我们正常指向三色标记的算法逻辑,将所有灰色的对象标记为黑色,那么对象2和对象7就被标记成了黑色,如图所示。
然后清除白色对象。
我们发现,对象4引用的对象3被误杀了,可以看出,当GC过程中发生以下事件时,就会出现对象丢失现象:
- 一个白色对象被一个黑色对象引用
- 原本引用该白色对象的灰色对象与该白色对象之间的可达关系遭到破坏
更严重的事,该白色对象引用的对象都可能被删除!
为了防止这种现象的发生,最简单的方式就是STW,直接禁止掉其他用户程序对对象引用关系的干扰,但是STW的过程有明显的资源浪费,对所有的用户程序都有很大影响。那么是否可以在保证对象不丢失的情况下合理的尽可能的提高GC效率,减少STW时间呢?答案是可以的,我们只要使用一种机制,尝试去破坏上面的两个必要条件就可以了。
屏障机制
GC回收器在满足下述两种情况之一时,即可确保对象不丢失。
强/弱三色不变式
强三色不变式,强制性的不允许黑色对象引用白色对象,这样就不会出现白色对象被误删的情况。
弱三色不变式,所有被黑色对象引用的白色对象都处于灰色保护状态。
为了遵循上述两种方式,GC算法演进到两种屏障方式:插入屏障和删除屏障。
插入屏障
插入屏障的具体操作就是,在A对象引用B对象的时候,B对象被标记为灰色,这就满足强三色不变式了。
插入屏障的伪代码如下:
添加下游对象(当前下游对象slot, 新下游对象ptr) {
//1
标记灰色(新下游对象ptr)
//2
当前下游对象slot = 新下游对象ptr
}
该方法的应用场景如下:
A.添加下游对象(nil, B) //A 之前没有下游, 新添加一个下游对象B, B被标记为灰色
A.添加下游对象(C, B) //A 将下游对象C 更换为B, B被标记为灰色
我们知道,黑色的对象既可能在栈区,也可能在堆区,栈空间的特点是容量小,调用频繁,速度快。栈中如果每次添加下游对象都进行检查,会拖累栈的速度,因此我们只对堆中对象进行检查,对于栈中对象,我们使用STW。接下来是模拟的一个详细的过程:
当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况。所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束。
最后将栈和堆空间剩余的全部白色节点清除,STW大约的时间在10~100ms。
删除屏障
一个对象删除它引用的对象,如果被删除对象为灰色或者白色,那么将它标记为灰色。
伪代码:
添加下游对象(当前下游对象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之前为白)
接下来模拟一个详细的过程:
这种方式回收精度低,本应被回收到对象5及其下游对象都未被回收,不过在下一轮即可回收成功。
混合写屏障机制
Go语言V1.8引入了混合写屏障机制,结合了插入写屏障和删除写屏障两种方式的优点。
- 插入写屏障:结束时需要STW来重新扫描栈,标记栈上引用的白色对象的存活。
- 删除写屏障:回收精度低,GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象。
混合写屏障规则
- GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描,无需STW)
- GC期间,任何在栈上创建的新对象,均为黑色。
- 被删除的对象标记为灰色。
- 被添加的对象标记为灰色。
满足变形的弱三色不变式。注意, 屏障技术是不在栈上应用的,因为要保证栈的运行效率。
场景分析
注意混合写屏障是GC的一种屏障机制,所以只是当程序执行GC的时候,才会触发这种机制。
GC开始:扫描栈区,将可达对象全部标记为黑
场景一: 对象被一个堆对象删除引用,成为栈对象的下游
删除堆区对象的引用对象,将该引用对象标记为灰色。