垃圾回收算法

垃圾回收追踪主要分为两种收集方法，分别是引用计数收集和追踪收集；常见的算法有

Golang中的垃圾回收主要应用三色标记法，GC过程和其他用户goroutine可并发运行，但需要一定时间的STW(stop the world)，STW的过程中，CPU不执行用户代码，全部用于垃圾回收，这个过程的影响很大，Golang进行了多次的迭代优化来解决这个问题。

三色标记法属于追踪收集类算法，核心思想同样是通过分析某些“根”对象的引用关系，来确定需要保留的可访问对象。

对于 Go 而言，Go 的 GC 目前使用的是无分代（对象没有代际之分）、不整理（回收过程中不对对象进行移动与整理）、并发（与用户代码并发执行）的三色标记清扫算法。原因[1]在于：

1. 对象整理的优势是解决内存碎片问题以及“允许”使用顺序内存分配器。但 Go 运行时的分配算法基于 tcmalloc，基本上没有碎片问题。 并且顺序内存分配器在多线程的场景下并不适用。Go 使用的是基于 tcmalloc 的现代内存分配算法，对对象进行整理不会带来实质性的性能提升。
2. 分代 GC 依赖分代假设，即 GC 将主要的回收目标放在新创建的对象上（存活时间短，更倾向于被回收），而非频繁检查所有对象。但 Go 的编译器会通过逃逸分析将大部分新生对象存储在栈上（栈直接被回收），只有那些需要长期存在的对象才会被分配到需要进行垃圾回收的堆中。也就是说，分代 GC 回收的那些存活时间短的对象在 Go 中是直接被分配到栈上，当 goroutine 死亡后栈也会被直接回收，不需要 GC 的参与，进而分代假设并没有带来直接优势。并且 Go 的垃圾回收器与用户代码并发执行，使得 STW 的时间与对象的代际、对象的 size 没有关系。Go 团队更关注于如何更好地让 GC 与用户代码并发执行（使用适当的 CPU 来执行垃圾回收），而非减少停顿时间这一单一目标上。

Go 选择三色标记清除，而不是分代 GC，主要是为了减少 GC 停顿，提高并发性能。

• 分代 GC 适用于 Java 这类生命周期明显不同的对象，能优化批量回收，但并发支持较弱。分代假设并不适用于 Go 的运行栈机制，年轻代对象在栈上就已经死亡，扫描本就该回收的执行栈并没有为由于分代假设带来明显的性能提升。这也是这一设计最终没有被采用的主要原因。
• 三色标记清除适用于 Go 这类高并发环境，能够做到低延迟、增量 GC，但可能牺牲部分吞吐量。

Go 垃圾回收实现

作者:刘丹冰Aceld原文链接

内容提纲

本文将系统的详细介绍Golang中GC的全分析过程，包括垃圾回收的方式递进。 内容包括：

• G0 V1.3之前的标记-清除(mark and sweep)算法
• Go V1.3之前的标记-清扫(mark and sweep)的缺点
• Go V1.5的三色并发标记法
• Go V1.5的三色标记为什么需要STW
• Go V1.5的三色标记为什么需要屏障机制(“强-弱” 三色不变式、插入屏障、删除屏障 )
• Go V1.8混合写屏障机制
• Go V1.8混合写屏障机制的全场景分析

一、Go V1.3之前的标记-清除(mark and sweep)算法

此算法主要有两个主要的步骤：

• 标记(Mark phase)
• 清除(Sweep phase)

第一步，暂停程序业务逻辑, 找出不可达的对象，然后做上标记。第二步，回收标记好的对象。

操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 STW(stop the world)。也就是说，这段时间程序会卡在哪儿。

第二步, 开始标记，程序找出它所有可达的对象，并做上标记。如下图所示：

第三步, 标记完了之后，然后开始清除未标记的对象. 结果如下.

第四步, 停止暂停，让程序继续跑。然后循环重复这个过程，直到process程序生命周期结束。

二、标记-清扫(mark and sweep)的缺点

• STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)。
• 标记需要扫描整个heap
• 清除数据会产生heap碎片

所以Go V1.3版本之前就是以上来实施的, 流程是

Go V1.3 做了简单的优化,将STW提前, 减少STW暂停的时间范围.如下所示

这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序 。

Go是如何面对并这个问题的呢？接下来G V1.5版本 就用三色并发标记法来优化这个问题.

三、Go V1.5的三色并发标记法

三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些. 我们来看一下具体的过程.

第一步 , 就是只要是新创建的对象,默认的颜色都是标记为”白色”.

这里面需要注意的是, 所谓”程序”, 则是一些对象的跟节点集合.

所以上图,可以转换如下的方式来表示.

第二步, 每次GC回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入”灰色”集合。

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

第四步, 重复第三步, 直到灰色中无任何对象.

第五步: 回收所有的白色标记表的对象. 也就是回收垃圾.

以上便是三色并发标记法, 不难看出,我们上面已经清楚的体现三色的特性, 那么又是如何实现并行的呢?

Go是如何解决标记-清除(mark and sweep)算法中的卡顿(stw，stop the world)问题的呢？

四、没有STW的三色标记法

我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。我们举一个场景.

如果三色标记法, 标记过程不使用STW将会发生什么事情?

可以看出，有两个问题, 在三色标记法中,是不希望被发生的

• 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
• 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)

当以上两个条件同时满足时, 就会出现对象丢失现象!

当然, 如果上述中的白色对象3, 如果他还有很多下游对象的话, 也会一并都清理掉.

为了防止这种现象的发生，最简单的方式就是STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是STW的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？

答案就是, 那么我们只要使用一个机制,来破坏上面的两个条件就可以了.

五、屏障机制

我们让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式.

(1) “强-弱” 三色不变式

• 强三色不变式

不存在黑色对象引用到白色对象的指针。

• 弱三色不变式

所有被黑色对象引用的白色对象都处于灰色保护状态。解决了条件1

为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式”插入屏障”, “删除屏障”.

(2) 插入屏障

具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)

满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)

伪码如下:

添加下游对象(当前下游对象slot, 新下游对象ptr) {
  //1
  标记灰色(新下游对象ptr)

  //2
  当前下游对象slot = 新下游对象ptr
}

场景：

A.添加下游对象(nil, B)   //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象C 更换为B，  B被标记为灰色

这段伪码逻辑就是写屏障,. 我们知道,黑色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以”插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况(如上图的对象9). 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.

最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间在10~100ms间.

(3) 删除屏障

具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。

满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)

伪代码：

添加下游对象(当前下游对象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之前为白)

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。

六、Go V1.8的混合写屏障(hybrid write barrier)机制

插入写屏障和删除写屏障的短板：

• 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
• 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。

(1) 混合写屏障规则

具体操作:

1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，

2、GC期间，任何在栈上创建的新对象，均为黑色。

3、被删除的对象标记为灰色。

4、被添加的对象标记为灰色。

满足: 变形的弱三色不变式.

伪代码：

添加下游对象(当前下游对象slot, 新下游对象ptr) {
      //1
        标记灰色(当前下游对象slot)    //只要当前下游对象被移走，就标记灰色

      //2
      标记灰色(新下游对象ptr)

      //3
      当前下游对象slot = 新下游对象ptr
}

这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。

(2) 混合写屏障的具体场景分析

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

注意混合写屏障是Gc的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。

GC开始：扫描栈区，将可达对象全部标记为黑

场景一： 对象被一个堆对象删除引用，成为栈对象的下游

伪代码

//前提：堆对象4->对象7 = 对象7；  //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7；  //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null；    //对象4 删除引用 对象7

场景二： 对象被一个栈对象删除引用，成为另一个栈对象的下游

伪代码

new 栈对象9；
对象8->对象3 = 对象3；      //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null；      //对象2 删除引用 对象3

场景三：对象被一个堆对象删除引用，成为另一个堆对象的下游

伪代码

堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

场景四：对象从一个栈对象删除引用，成为另一个堆对象的下游

伪代码

堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

Golang中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。

总结:

• go1.3标记清除，先stw,再标记清除，然后恢复stw，效率极低。

• go1.5三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通。

• go1.8 三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。

当前版本的 Go 以 STW 为界限，可以将 GC 划分为五个阶段：

Key Points

参考

• 对于栈对象本身：

  • 栈对象是临时的，GC 不会直接清除栈对象，因为它们会在函数退出时由运行时自动释放。
  • 垃圾回收器的主要任务是处理栈中 指向堆对象的引用，而非清理栈内存。
  • 如果栈上的变量引用了堆上的对象，那么 GC 需要识别这些对象是否仍然可达，否则会错误地回收仍在使用的对象。

• 针对 Go 语言，垃圾回收器会从程序的“根节点”开始遍历，找出所有可以被访问到的对象，并标记它们为可达对象。根据上述“根节点”定义，Go 程序的根节点根对象通常包括以下几类对象：

  1. 全局变量：这些变量在整个程序执行过程中都可以被访问到，因此垃圾回收器会将它们作为根节点。

  2. 栈中的变量：每个 goroutine 都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。因此，在函数调用期间，它们被认为是根节点。比如下面的p, 它引用了堆变量，其实就是函数的实参。栈上保存着该 goroutine 在运行时的所有局部变量，包括函数的参数、局部变量以及一些由编译器生成的临时变量

     func greet(person *Person) {
         fmt.Println("Hello, " + person.Name)
     }
          
     func main() {
         p := &Person{Name: "Alice"}  // 栈上的局部变量 p
         greet(p)  // p 是传递给 greet 函数的参数
     }
     

  3. 寄存器中的变量。 一些局部变量可能会被保存在寄存器中，尤其是频繁使用的变量。Go 的垃圾回收器会根据寄存器和栈指针的值来确定哪些对象需要标记。

• 为何需要stw或者写屏障，有两个问题, 在三色标记法中,是不希望被发生的

  • 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)

  • 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色丢了该白色)

• 只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：

  • 如果条件 1 被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
  • 如果条件 2 被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

• 三色不变性

  • 当满足原有的三色不变性定义（或上面的两个条件都不满足时）的情况称为强三色不变性（strong tricolor invariant）
  • 当赋值器令黑色对象引用白色对象时（满足条件 1 时）的情况称为弱三色不变性（weak tricolor invariant）

• 对于 Go 而言，Go 的 GC 目前使用的是无分代（对象没有代际之分）、不整理（回收过程中不对对象进行移动与整理）、并发（与用户代码并发执行）的三色标记清扫算法。

• 可以go tool trace等观察go gc

• 有了 GC，为什么还会发生内存泄露？

  • 预期能被快速释放的内存因被根对象引用而没有得到迅速释放，比如全局对象引用了一个临时变量。
  • goroutine 泄漏。由于某些原因，Goroutine 无法正常退出或者结束，导致程序中有不再需要的 Goroutine 继续存在，消耗资源，最终可能导致系统性能下降，甚至崩溃。

• Go 语言中对 GC 的触发时机存在两种形式：

  1. 主动触发，通过调用 runtime.GC 来触发 GC，此调用阻塞式地等待当前 GC 运行完毕。
  2. 被动触发，分为两种方式：
     • 使用系统监控，当超过两分钟没有产生任何 GC 时，强制触发 GC。
     • 使用步调（Pacing）算法，其核心思想是控制内存增长的比例。通过参数 GOGC 或者 debug.SetGCPercent 进行控制（他们控制的是同一个变量，即堆的增长率。默认情况下，GOGC 的值为 100，这意味着当堆内存的大小增加到上次回收时的 100% 时，GC 会被触发。

• 如果内存分配速度超过了标记清除的速度怎么办？

  目前的 Go 实现中，当 GC 触发后，会首先进入并发标记的阶段。并发标记会设置一个标志，并在 mallocgc 调用时进行检查。当存在新的内存分配时，会暂停分配内存过快的那些 goroutine，并将其转去执行一些辅助标记（Mark Assist）的工作，从而达到放缓继续分配、辅助 GC 的标记工作的目的。

• Go 的 GC 如何调优？

  • GC 的调优是在特定场景下产生的，并非所有程序都需要针对 GC 进行调优。只有那些对执行延迟非常敏感、当 GC 的开销成为程序性能瓶颈的程序，才需要针对 GC 进行性能调优，几乎不存在于实际开发中 99% 的情况。
  • 总的来说，我们可以在现在的开发中处理的有以下几种情况：
    1. 对停顿敏感：GC 过程中产生的长时间停顿、或由于需要执行 GC 而没有执行用户代码，导致需要立即执行的用户代码执行滞后。
    2. 对资源消耗敏感：对于频繁分配内存的应用而言，频繁分配内存增加 GC 的工作量，原本可以充分利用 CPU 的应用不得不频繁地执行垃圾回收，影响用户代码对 CPU 的利用率，进而影响用户代码的执行效率。
  • 可优化空间
    • 控制内存分配的速度，限制 goroutine 的数量，从而提高赋值器对 CPU 的利用率。
    • 减少并复用内存，例如使用 sync.Pool 来复用需要频繁创建临时对象，例如提前分配足够的内存来降低多余的拷贝。
    • 需要时，增大 GOGC 的值，降低 GC 的运行频率。