Go 语言内存管理三部曲（三）图解 GC 算法和垃圾回收原理

前面两篇文章介绍了Go语言的内存分配原理以及Go协程动态扩充和收缩栈内存的原理，今天这篇文章我们主要来聊一下内存管理的另外一大块内容：垃圾回收。



下面首先我们会聊一下什么是GC，GC的作用是什么，然后再结合图示用每个人都能听懂的大白话解释Go的GC原理。



什么是GC？



现代高级编程语言管理内存的方式分为两种：自动和手动，像C、C++ 等编程语言使用手动管理内存的方式，工程师编写代码过程中需要主动申请或者释放内存；而 PHP、Java 和 Go 等语言使用自动的内存管理系统，有内存分配器和垃圾收集器来代为分配和回收内存，其中垃圾收集器就是我们常说的GC。



GC回收的是什么？



在应用程序中会使用到两种内存，分别为堆（Heap）和栈（Stack），GC负责回收堆内存，而不负责回收栈中的内存。那么这是为什么呢？



主要原因是栈是一块专用内存，专门为了函数执行而准备的，存储着函数中的局部变量以及调用栈。除此以外，栈中的数据都有一个特点——简单。比如局部变量不能被函数外访问，所以这块内存用完就可以直接释放。正是因为这个特点，栈中的数据可以通过简单的编译器指令自动清理，并不需要通过 GC 来回收。



GC算法的种类



主流的垃圾回收算法有两大类，分别是追踪式垃圾回收算法和引用计数法（ Reference counting ）。而Go语言现在用的三色标记法就属于追踪式垃圾回收算法的一种。



追踪式算法的核心思想是判断一个对象是否可达，一旦这个对象不可达就可以在垃圾回收的控制循环里被 GC 回收了。那么我们怎么判断一个对象是否可达呢？很简单，第一步找出所有的全局变量和当前函数栈里的变量，标记为可达。第二步，从已经标记的数据开始，进一步标记它们可访问的变量，以此类推。



Go的垃圾回收算法



Go的垃圾收集器从一开始到现在一直在演进，在v1.5版本开始三色标记法作为垃圾回收算法前使用Mark-And-Sweep（标记清除）算法。从v1.5版本Go实现了基于三色标记清除的并发垃圾收集器，大幅度降低垃圾收集的延迟从几百 ms 降低至 10ms 以下。在v1.8又使用混合写屏障将垃圾收集的时间缩短至 0.5ms 以内。



标记清除算法的缺点



Mark-And-Sweep，这个算法就是严格按照追踪式算法的思路来实现的。这个垃圾回收算法的执行流程可以用下面这张图来表示。





此算法主要有两个步骤：



• 暂停应用程序的执行, 从根对象出发标记出可达对象。

• 清除未标记的对象，恢复应用程序的执行。



这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，不能异步地进行垃圾回收，对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需要一个算法来解决 GC 运行时程序长时间挂起的问题。



三色标记清除法



从v1.5版本Go实现了基于三色标记清除的并发垃圾收集器，注意三色标记这个算法不是Go的垃圾收集器独有的。这个算法背后的核心思想是由Edsger W. Dijkstra，Leslie Lamport，A.J.Martin，C.S.Scholten和E.F.M.Steffens提出的，算法首先于1978年发表在论文On-the-fly Garbage Collection：An Exercise in Cooperation上面。三色标记清除算法背后的首要原则就是它把堆中的对象根据它们的颜色分到不同集合里面。



三色标记算法将程序中的对象分成白色、黑色和灰色三类：



• 白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；

• 黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象，垃圾回收器不会扫描这些对象的子对象；

• 灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；



文字解释起来不太好理解，我用下面几张图演示一下三色标记清除的整个过程：



第一步：在进入GC的三色标记阶段的一开始，所有对象都是白色的。





第二步, 遍历根节点集合里的所有根对象，把根对象引用的对象标记为灰色，从白色集合放入灰色集合。





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

第四步：重复第三步, 直到灰色集合中无任何对象。

第五步：回收白色集合里的所有对象，本次垃圾回收结束。



这里所说的根节点集合里的根对象就是栈上的对象或者堆上的全局变量。



写屏障



Go 在GC阶段执行三色标记前，还需要先做一个准备工作——打开写屏障(Write Barrier)。那么写屏障是什么呢？我们知道三色标记法是一种可以并发执行的算法。所以在GC运行过程中程序的函数栈内可能会有新分配的对象，那么这些对象该怎么通知到 GC，怎么给他们着色呢？如果还是按照之前新建的对象标记为白色就有可能出现下图中的问题：





在GC进行的过程中，应用程序新建了对象I，此时如果已经标记成黑的对象F引用了对象I，那么在本次GC执行过程中因为黑色对象不会再次扫描，所以如果I着色成白色的话，会被回收掉，这显然是不允许的。



这个时候就需要我们的写屏障出马了。写屏障主要做一件事情，修改原先的写逻辑，然后在对象新增的同时给它着色，并且着色为灰色。因此打开了写屏障可以保证了三色标记法在并发下安全正确地运行。那么有人就会问这些写屏障标记成灰色的对象什么时候回收呢？答案是后续的GC过程中回收，在新的GC过程中所有已存对象就又从白色开始逐步被标记啦。



三色不变性



想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的任意一种：



• 强三色不变性 — 黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；

• 弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径



屏障技术



垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。



Go的混合写屏障



在Go 语言 v1.7 版本之前，使用的是Dijkstra插入写屏障保证强三色不变性，但是运行时并没有在所有的垃圾收集根对象上开启插入写屏障。因为 Go 语言的应用程序可能包含成百上千的 goroutine，而垃圾收集的根对象一般包括全局变量和栈对象，如果运行时需要在几百个 goroutine 的栈上都开启写屏障，会带来巨大的额外开销，所以 Go 团队在实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描，在活跃 goroutine 非常多的程序中，重新扫描的过程需要占用 10 ~ 100ms 的时间。



Go 语言在 v1.8 组合 Dijkstra 插入写屏障和 Yuasa 删除写屏障构成了如下所示的混合写屏障，该写屏障会将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色：



writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr



为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。



一次完整的GC过程



Go的垃圾回收器在使用了三色标记清除算法和混合写屏障后大大减少了暂停程序（STW）的时间，主要是在开启写屏障前和移除写屏障前暂停应用程序。



Go的垃圾收集的整个过程可以分成标记准备、标记、标记终止和清除四个不同阶段，每个阶段完成的工作如下：



标记准备阶段



• 暂停程序，所有的处理器在这时会进入安全点（Safe point）；



标记阶段



• 将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assiste）并将根对象入队；



• 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，标记用的算法就是上面介绍的三色标记清除法。写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；



• 开始扫描根对象，包括所有 goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 goroutine 栈期间会暂停当前处理器；



• 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；



• 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；



在标记开始的时候，收集器会默认抢占 25% 的 CPU 性能，剩下的75%会分配给程序执行。但是一旦收集器认为来不及进行标记任务了，就会改变这个 25% 的性能分配。这个时候收集器会抢占程序额外的 CPU，这部分被抢占 goroutine 有个名字叫 Mark Assist。而且因为抢占 CPU的目的主要是 GC 来不及标记新增的内存，那么抢占正在分配内存的 goroutine 效果会更加好，所以分配内存速度越快的 goroutine 就会被抢占越多的资源。



除此以外 GC 还有一个额外的优化，一旦某次 GC 中用到了 Mark Assist，下次 GC 就会提前开始，目的是尽量减少 Mark Assist 的使用，从而避免影响正常的程序执行。



标记终止阶段



• 暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序；



• 清理处理器上的线程缓存；



清理阶段



• 将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障；



• 恢复用户程序，所有新创建的对象会标记成白色；



• 后台并发清理所有的内存管理单元，当 goroutine 申请新的内存管理单元时就会触发清理；



清理这个过程是并发进行的。清扫的开销会增加到分配堆内存的过程中，所以这个时间也是无感知的，不会与垃圾回收的延迟相关联。



总结



Go语言的垃圾收集的实现非常复杂，难懂的技术概念和原理也比较多，这篇文章意在用每个人都能看懂的白话文字结合图示把Go的垃圾回收原理解释清楚，让读者能对垃圾回收的大体流程有个概念。



下面用一句话总结概况Go的垃圾回收原理：



Go的GC最早期使用的回收算法是标记-清除算法，该算法需要在执行期间需要暂停应用程序(STW)，无法满足并发程序的实时性。后面Go的GC转为使用三色标记清除算法，并通过混合写屏障技术保证了Go并发执行GC时内存中对象的三色一致性（这里的并发指的是GC和应用程序的goroutine能同时执行）。

一次完整的垃圾回收会分为四个阶段，分别是标记准备、标记、结束标记以及清理。在标记准备和标记结束阶段会需要 STW，标记阶段会减少程序的性能，而清理阶段是不会对程序有影响的。



这句话有点长，哈哈哈。看了今天的文章你对Go的垃圾回收有大体的理解了吗？能用自己的话总结一下吗？欢迎把自己的总结发在留言里，也欢迎把文章分享给朋友阅读。关注公众号「网管叨bi叨」，获取我整理的所有关于Go语言的技术文章。



参考资料

垃圾收集器



Go 垃圾回收——三色标记法



相关阅读

Go 语言内存管理三部曲（一）内存分配原理



Go 语言内存管理三部曲（二）解密栈内存管理