Golang 垃圾回收原理

背景

垃圾回收 GC 是一种内存管理的策略，垃圾收集器基于 runtime 在用户程序之下进行后台运作，根据一定策略回收用户不用的空间。

使用 GC 有下面的优势：

可以向用户屏蔽内存回收的细节，避免手动管理内存
以全局视野管理内存，避免不同模块的临界资源加大开发者的心智负担

也会引入一定劣势：

降低了内存管理的性能上限，无法绕开gc机制的限制
为程序增加了额外的成本，维护额外信息管理内存情况，甚至可能 stop the world

综合来看，除了少数比较追求极致性能的项目，在大多数的业务开发里 GC 可以极大帮助降低开发压力，提高开发速度。

垃圾回收算法

标记清扫

标记清扫顾名思义，分为标记+清扫两个步骤：

标记：标记当前还存活的对象
清扫：清扫未标记的对象

类似排除法，找存活对象而非垃圾对象来完成清扫。（和我的 IDL trimmer 的思路一样）

这种方法有一个缺点，因为清的是全部扫剩下的内容，经过几轮清扫以后，空闲的内存块很可能是碎片化的零散分布，产生内存碎片。这样不利于大对象的再次分配。

标记压缩

标记压缩是对标记清扫的改进，在第二步清扫的时候会对存活对象进行压缩整合，让空间更紧凑，不产生内存碎片的问题。

这个方法会导致一些压缩开销，可能需要额外的时间复杂度。

半空间复制

这是 java 的 gc 采用的一种策略，会将 gc 作为分水岭划分内存，其实本质是一个空间换时间的策略：

分配两片等大的空间，fromspace 和 tospace
每轮只使用 fromspace
gc时，将 fromspace 的活对象转移到 tospace 里，转移的同时对空间进行压缩整合

这样既用压缩解决了内存碎片的问题，又避免了太多的压缩时间复杂度。缺点就是比较浪费空间。

引用计数

引用计数是另一种反向策略，对对象的引用进行计数，这样在 gc 时直接删掉计数为0的即可。

对象被引用一次，计数器+1
对象被删除引用一次，计数器-1
gc 时，删掉计数=0的对象

但是，如果这样朴素的实现，没有办法解决循环引用或者自引用的问题。

Golang 垃圾回收机制

三色标记法

三色标记法是 Dijkstra 提出的一种算法，是一种标记清扫算法的实现：

将对象分为黑灰白三种颜色
黑：对象自身存活，且其指向对象已标记完成
灰：对象自身存活，但其指向对象还没标记好
白：对象尚未被标记到（或者是垃圾对象）
标记开始前，将根变量（全局对象、栈上的局部变量等）置黑，将其指向对象置灰
从灰对象出发，将其锁指向对象都置灰，然后将当前对象置黑。
标记结束以后，白对象就是不可达的垃圾

golang 采用三色标记法进行垃圾回收。

并发垃圾回收

在 golang 1.5 之前，GC 时需要停止全局的用户协程，也就是 stop the world，然后进行 gc，再恢复用户协程。这样是实现比较简单，但用户程序的性能就比较难看了。

在 1.5 版本之后，golang 引入了并发垃圾回收机制，允许用户协程和后台 gc 协程并发运行，从用户视角看体验就好了很多。然而，并发垃圾回收可能会产生一些问题。

并发垃圾回收可能导致漏标，也就是部分存活对象没被标记到导致被删掉。这是因为并发下用户协程删除、创建引用，以及 gc 协程涂色都是非原子的，可能会出现 race （不是说真的会data race，只是会因为非原子操作产生步骤间并发的问题，例如gc协程将某对象置黑后用户协程又为它添加了对其他对象的引用，另一个对象就无法被扫描），导致有些节点漏标记而被删除。这个问题是不可接受的，可能会导致致命错误。

此外，并发垃圾回收也可能出现多标的问题，也就是部分垃圾被误标记从而没法及时回收的问题。条件也是非原子操作的步骤间冲突，例如在置灰后被用户协程删除引用的，之后也会被置黑，但他事实上已经是垃圾了。错标没有那么不能接受，因为在下一轮 gc 中它还是可以被回收。

屏障机制

为了解决上述引入并发 gc 导致的问题，golang 引入了屏障机制。

漏标问题的本质是扫描完成后黑对象又去指向一个已经被灰/白对象删除引用的白对象。

这种情况发生的根源是两个：

黑对象指向了白色对象
之后灰色对象到它之间的链路上的白色对象被破坏

为了解决这个问题，可以用下面的方法：

强三色不变式：使白色对象不能被黑色对象直接引用
弱三色不变式：白色对象可以被黑色对象引用，但从某个灰对象出发仍然可以到达白对象

要实现强三色不变式，我们可以实现一个插入写屏障（ Dijkstra barrier）。这种屏障机制类似一种回调保护机制，也就是在完成某个动作前必须完成屏障设置的内容。插入写屏障保证在黑色对象指向白色对象前，会先触发配置修改白对象为灰色，再建立引用。

要实习弱三色不变式，可以实现删除写屏障，保证在一个白色对象即将被上游删除引用时，触发屏障将其置灰，然后再删除引用。

看起来这两种屏障二选其一即可解决漏标的问题。至于误标记，留到下一次 gc 即可。然而，对于栈操作，可能会出现用户协程中的频繁轻量级修改，如果每一次都要触发屏障插入代码，可能导致性能瓶颈。为了避免这个性能瓶颈，golang 1.8 之前的版本都会引入一个 stop the world 阶段，对栈对象的处理进行兜底，重新扫描清除白对象。

混合写屏障

然而，一次 stop the world 可能导致很长的停滞，所以 golang 1.8 引入了混合写屏障机制：

gc 开始前，对每个栈进行扫描，将每个栈上可达对象全部置黑（不用二次扫描，不会 stop the world）
gc 时，栈上创建的新对象直接置黑
堆对象正常启用插入写和删除写屏障。

这样，导致问题的堆和堆、堆和栈之间的引用-解引用条件就可以被插入写和删除写屏障破坏；对于一个栈中灰对象A删除C的引用、另一个栈中黑对象B建立C的引用的情况，假若B的这个C的引用来自于B的同栈，那么必然存在经灰色节点到C的路线，或者C被置灰；除此之外的唯一可能是这个引用是经过对A的间接引用来的，但如果是这样，A一定会被升级到堆里，会过屏障，因此直接排除。

所以，混合写屏障可以满足并发 gc 的要求，并且无需为栈添加屏障或经历 rescan 导致的长时间 stop the world。

内存碎片问题

另外前面提到，标记清扫算法会产生内存碎片。但其实，在内存管理部分（见 http://mcyou.cc/archives/1707484030538 ），golang 使用了类似 tcmalloc 的机制，根据对象大小分配到相应的分级块中，从而减少了不可控的散乱内存碎片问题，将外碎片转换成可控可量化的内碎片，很大程度上解决了标记清扫带来的内存碎片问题，从而直接避免采用复杂度更高的标记压缩算法。

分代垃圾回收？

那为什么 golang 不用 java 同款分代垃圾回收机制呢？

分代算法主要是将对象氛围年轻代和老年代等等，然后用不同的 gc 策略分类讨论。但是考虑到 golang 是一门强编译型语言，在编译的时候就存在内存逃逸分析，将生命周期短的直接分配在栈上，并以栈为单位对这部分对象直接进行回收。而类似 java 的分代机制是一种运行时的优化技术，需要维护对象的有关年龄信息等，会引入对应的复杂逻辑。考虑到 golang 已经在编译时完成了逃逸分析，所以没有必要再引入这些额外的成本。

总结

一段话总结 golang 垃圾回收：

golang 采用三色标记法和混合写屏障机制来完成垃圾回收，将对象分为黑白灰三种颜色进行管理，采用并发 gc 的方式来缩短用户程序 stop the world 的时间，使用混合写屏障来确保并发 gc 下不会出现误清理问题，对堆空间启用屏障而栈空间不启用，避免对栈空间再次扫描而延长 gc 耗时。配合多线程内存分配模型，三色标记法也可以尽量减少内存碎片的产生。