一文搞懂 go gc 垃圾回收原理

什么是垃圾回收

我们在程序中定义一个变量，会在内存中开辟相应内存空间进行存储，当不需要此变量后，需要手动销毁此对象，并释放内存。而这种对不再使用的内存资源进行自动回收的功能即为垃圾回收（Garbage Collection，缩写为GC），是一种自动内存管理机制

如何识别垃圾

引用计数算法(reference counting)

引用计数通过在对象上增加自己被引用的次数，被其他对象引用时加1，引用自己的对象被回收时减1，引用数为0的对象即为可以被回收的对象，这种算法在内存比较紧张和实时性比较高的系统中使用比较广泛，如php，Python等。

优点：

1. 方式简单，回收速度快。

缺点：

1. 需要额外的空间存放计数。
2. 无法处理循环引用(如a.b=b; b.a=a)。
3. 频繁更新引用计数降低了性能。

追踪式回收算法(Tracing)

追踪式算法(可达性分析)的核心思想是判断一个对象是否可达，如果这个对象一旦不可达就可以立刻被GC回收了，那么我们怎么判断一个对象是否可达呢？

第一步从根节点开始找出所有的全局变量和当前函数栈里的变量，标记为可达。第二步，从已经标记的数据开始，进一步标记它们可访问的变量，以此类推，专业术语叫传递闭包。当追踪结束时，没有被打上标记的对象就被判定是不可触达。

优点：

1. 解决了循环引用的问题
2. 占用的空间少了

和引用计数法相比，有以下缺点：

1. 无法立刻识别出垃圾对象，需要依赖GC线程
2. 算法在标记时必须暂停整个程序，即STW(stop the world)，否则其他线程有可能会修改对象的状态从而回收不该回收的对象

如何清理垃圾

标记清除算法(Mark Sweep)

标记清除算法是最常见的垃圾收集算法，标记清除收集器是跟踪式垃圾收集器，其执行过程可以分成标记(Mark)和清除(Sweep)两个阶段：

1. 标记阶段：暂停应用程序的执行，从根对象触发查找并标记堆中所有存活的对象；
2. 清除阶段：遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表，恢复应用程序的执行；

优点：

1. 实现简单。

缺点：

1. 执行期间需要把整个程序完全暂停，不能异步的进行垃圾回收。
2. 容易产生大量不连续的内存随便，碎片太多可能会导致后续没有足够的连续内存分配给较大的对象，从而提前触发新的一次垃圾收集动作。

标记复制算法

它把内存空间划分为两个相等的区域，每次只使用其中一个区域。在垃圾收集时，遍历当前使用的区域，把存活对象复制到另一个区域中，最后将当前使用的区域的可回收对象进行回收。

实现：

1. 首先这个算法会把对分成两块，一块是From、一块是To
2. 对象只会在From上生成，发生GC之后会找到所有的存活对象，然后将其复制到To区，然后整体回收From区。

优点：

1. 不用进行大量垃圾对象的扫描：标记复制算法需要从GC-root对象出发，将可达的对象复制到另外一块内存后直接清理当前这块内存即可。
2. 解决了内存碎片问题，防止分配大空间对象是提前gc的问题。

缺点：

1. 复制成本问题：在可达对象占用内存高的时候，复制成本会很高。
2. 内存利用率低：相当于可利用的内存仅有一半。

标记压缩算法

在标记可回收的对象后将所有存活的对象压缩到内存的一端，使他们紧凑地排列在一起，然后对边界以外的内存进行回收，回收后，已用和未用的内存都各自一边。

优点：

1. 避免了内存碎片化的问题。
2. 适合老年代算法，老年代对象存活率高的情况下，标记整理算法由于不需要复制对象，效率更高。

缺点：

1. 整理过程复杂：需要多次遍历内存，导致STW时间比标记清除算法高。

设计原理

三色标记算法

为了解决原始标记清除算法带来的长时间STW, Go从v1.5版本实现了基于三色标记清除的并发垃圾收集器，在不暂停程序的情况下即可完成对象的可达性分析，三色标记算法将程序中的对象分成白色、黑色和灰色三类：

• 白色对象 - 潜在的垃圾，表示还未搜索到的对象，其内存可能会被垃圾收集器回收；
• 黑色对象 - 活跃的对象，表示搜索完成的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象
• 灰色对象 - 活跃的对象，表示正在搜索还未搜索完的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

三色标记法属于增量式GC算法，回收器首先将所有对象标记成白色，然后从gc root出发，逐步把所有可达的对象变成灰色再到黑色，最终所有的白色对象都是不可达对象。

具体实现：

• 初始时所有对象都是白色的
• 从gc root对象出发，扫描所有可达对象标记为灰色，放入待处理队列
• 从队列取出一个灰色对象并标记为黑色，将其引用对象标记为灰色，放入队列
• 重复上一步骤，直到灰色对象队列为空
• 此时剩下的所有白色对象都是垃圾对象

优点：

• 不需要STW

缺点：

• 如果产生垃圾速度大于回收速度时，可能会导致程序中垃圾对象越来越多而无法及时收集
• 线程切换和上下文转换的消耗会使得垃圾回收的总体成本上升，从而降低系统吞吐量

三色标记法存在并发性问题，

• 可能会出现野指针(指向没有合法地址的指针)，从而造成严重的程序错误
• 漏标，错误的回收非垃圾对象

三色不变性

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

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

屏障技术

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

插入写屏障

当一个对象引用另外一个对象时，将另外一个对象标记为灰色，以此满足强三色不变性，不会存在黑色对象引用白色对象。

删除写屏障

在灰色对象删除对白色对象的引用时，将白色对象置为灰色，其实就是快照保存旧的引用关系，这叫STAB(snapshot-at-the-beginning),以此满足弱三色不变性。

混合写屏障

v1.8版本之前，运行时会使用插入写屏障保证强三色不变性；

在v1.8中，组合插入写屏障和删除写屏障构成了混合写屏障，保证弱三色不变性；该写屏障会将覆盖的对象标记成灰色(删除写屏障)并在当前栈没有扫描时将新对象也标记成灰色(插入写屏障)：

写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新建的对象都会被直接标记成黑色。

执行周期

Go语言的垃圾收集可以分成清除终止、标记、标记终止和清除四个不同阶段：

1. 清理终止阶段

1. 暂停程序，所有的处理器在这时会进入安全点(safe point)；
2. 如果当前垃圾收集循环是强制触发的，我们还需要处理还未清理的内存管理单元；

2. 标记阶段

1. 将状态切换至_GCmark、开启写屏障、用户程序协助(Mutator Assists)并将根对象入队；
2. 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
3. 开始扫描根对象，包括所有Goroutine的栈、全局对象以及不在堆中的运行时数据结构，扫描Goroutine栈期间会暂停当前处理器；
4. 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；
5. 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；

3. 标记终止阶段

1. 暂停程序、将状态切换至_GCmarktermination 并关闭辅助标记的用户程序；
2. 清理处理器上的线程缓存；

4. 清理阶段

1. 将状态切换至_GCoff 开始清理阶段、初始化清理状态并关闭写屏障；
2. 恢复用户程序，所有新创建的对象会标记成白色；
3. 后台并发清理所有的内存管理单元，当Goroutine申请新的内存管理单元时就会触发清理；

GC触发时机

当满足触发垃圾收集的基本条件：允许垃圾收集、程序没有崩溃并且没有处于垃圾循环；

注：运行时会通过如下所示的runtime.gcTrigger.test方法决定是否需要触发垃圾收集，该方法会根据三种不同方式触发进行不同的检查。

func (t gcTrigger) test() bool {
 if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
  return false
 }
 switch t.kind {
 case gcTriggerHeap:
  return memstats.heap_live >= memstats.gc_trigger
 case gcTriggerTime:
  if gcpercent < 0 {
   return false
  }
  lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
  return lastgc != 0 && t.now-lastgc > forcegcperiod
 case gcTriggerCycle:
  return int32(t.n-work.cycles) > 0
 }
 return true
}

• 超过内存大小阙值，分配内存时，当前已分配内存与上一次GC结束时存活对象的内存达到某个比例时就触发GC。(默认配置会在堆内存达到上一次垃圾收集的2倍时，触发新一轮的垃圾收集，可以通过环境变量GOGC调整，在默认情况下他的值为100，即增长100%的堆内存才会触发GC)；比如一次回收完毕后，内存的使用量为5M，那么下次回收的机制则是内存分配达到10M的时候，也就是说，并不是内存分配越多，垃圾回收频率越高。
• 如果一直达不到内存大小的阙值，sysmon检测出一段时间内（由runtime.forcegcperiod变量控制，默认为2分钟）没有触发过GC，就会触发新的GC。
• 调用runtime.GC()强制触发GC

GC调优

减少堆内存的分配是最好的优化方式。比如合理重复利用对象；避免string和byte[]之间的转化等，两者发生转换的时候，底层数据结构会进行复制，因此导致gc效率会变低，少量使用+连接string，Go里面string是最基础的类型，是一个只读类型，针对他的每一个操作都会创建一个新的string，如果是少量小文本拼接，用“+”就好，如果是大量小文本拼接，用strings.Join;如果是大量大文本拼接，用bytes.Buffer。

优化努力的方向：

• 尽可能保持最小的堆内存
• 最佳的GC频率
• 保持每次垃圾收集的内存大小
• 最小化每次垃圾收集的STW和Mark Assist的持续时间