本文会介绍 Go 语言的垃圾回收机制，内容全部来自 Go 语言设计与实现 ，基于内容和自己的理解，做了一些排版上的设计便于个人的学习和回顾，有兴趣的可以直接阅读 Go 语言设计与实现 中的内容。

Go 语言为了实现高性能的并发垃圾收集器，使用三色抽象、并发增量回收、混合写屏障、调步算法以及用户程序协助等机制将垃圾收集的暂停时间优化至毫秒级以下。

设计原理

• 编程语言通常会使用手动和自动两种方式管理内存：
  • C、C++ 以及 Rust 等编程语言使用手动的方式管理内存，工程师需要主动申请或者释放内存;
  • Python、Ruby、Java 和 Go 等语言使用自动的内存管理系统，一般都是垃圾收集机制 ;
  • Objective-C 选择了自动引用计数，虽然引用计数也是自动的内存管理机制。
• 标记清除
  • 执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：
    • 标记阶段 — 从根对象出发查找并标记堆中所有存活的对象；
    • 清除阶段 — 遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；
  • 用户程序在垃圾收集的过程中不能执行，我们需要用到更复杂的机制来解决 STW 的问题。
• 三色抽象
  • 三色标记算法将程序中的对象分成白色、黑色和灰色三类:
    • 白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；
    • 黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
    • 灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；
  • 三色标记垃圾收集器的工作原理很简单，可以将其归纳成以下几个步骤：
    • 将垃圾收集的根对象标记成灰色；
    • 从灰色对象的集合中选择一个灰色对象并将其标记成黑色；
    • 将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；
    • 重复上述两个步骤直到对象图中不存在灰色对象；
    • 回收白色的垃圾。
  • 用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW，且可能产生悬挂指针，即指针没有指向特定类型的合法对象，影响了内存的安全性。
• 屏障技术
  • 屏障技术就是在并发或者增量标记过程中保证三色不变性的重要技术:
    • 强三色不变性 — 黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；
    • 弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。
    • 垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。
    • Go 语言中使用的两种写屏障技术
      • 插入写屏障
        • 用户程序和垃圾收集器在交替工作的情况下保证程序执行的正确性。
        • Dijkstra 的插入写屏障是一种相对保守的屏障技术，它会将有存活可能的对象都标记成灰色以满足强三色不变性。
        • 缺点：栈上的对象在垃圾收集中也会被认为是根对象，为了保证内存的安全，Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描，这两种方法各有各的缺点，前者会大幅度增加写入指针的额外开销，后者重新扫描栈对象时需要暂停程序。
      • 删除写屏障
        • 一旦该写屏障开始工作，会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）。
        • 删除写屏障保证了弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用，避免了发生悬挂指针以保证用户程序的正确性。
• 增量和并发

  • 为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，我们会使用下面的策略优化现代的垃圾收集器：

    • 增量垃圾收集 — 增量地标记和清除垃圾，降低应用程序暂停的最长时间；
    • 并发垃圾收集 — 利用多核的计算资源，在用户程序执行时并发标记和清除垃圾；

  • 增量和并发的垃圾收集需要提前触发并在内存不足前完成整个循环，避免程序的长时间暂停。

  • 增量收集器

    • 将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但减少了应用程序暂停的最大时间。
    • 需要与三色标记法一起使用，为了保证垃圾收集的正确性。
    • 在垃圾收集期间，写屏障的影响用户程序也需要承担额外的计算开销。

  • 并发收集器

    • 不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响。
    • 并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的。
    • 因为读写屏障的引入，并发的垃圾收集器也一定会带来额外开销，不仅会增加垃圾收集的总时间，还会影响用户程序。

演进过程

• 从不精确的单线程 STW 收集器 → 支持并发垃圾收集、去中心化协调等特性。
• 并发垃圾收集
  • 该垃圾收集器使用了我们上面提到的三色抽象和写屏障技术保证垃圾收集器执行的正确性。
  • 首先，并发垃圾收集器必须在合适的时间点触发垃圾收集循环。
  • Go 语言的并发垃圾收集器会在扫描对象之前暂停程序做一些标记对象的准备工作，其中包括启动后台标记的垃圾收集器以及开启写屏障，如果在后台执行的垃圾收集器不够快，应用程序申请内存的速度超过预期，运行时会让申请内存的应用程序辅助完成垃圾收集的扫描阶段，在标记和标记终止阶段结束之后就会进入异步的清理阶段，将不用的内存增量回收。
• 回收堆目标
  • STW 的垃圾收集器虽然需要暂停程序，但是它能够有效地控制堆内存的大小。
  • 因为并发垃圾收集器会与程序一起运行，所以它无法准确的控制堆内存的大小，并发收集器需要在达到目标前触发垃圾收集，这样才能够保证内存大小的可控，并发收集器需要尽可能保证垃圾收集结束时的堆内存与用户配置的 GOGC 一致。
• 混合写屏障
  • 在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描；
  • 写屏障会将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色；
  • 将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

实现原理

• 清理终止阶段
  • 暂停程序，所有的处理器在这时会进入安全点（Safe point）；
  • 如果当前垃圾收集循环是强制触发的，我们还需要处理还未被清理的内存管理单元；
• 标记阶段
  • 将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assists）并将根对象入队；
  • 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
  • 开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器；
  • 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；
  • 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；
• 标记终止阶段
  • 暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序；
  • 清理处理器上的线程缓存；
• 清理阶段
  • 将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障；
  • 恢复用户程序，所有新创建的对象会标记成白色；
  • 后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理；
• 触发时机
  • 后台触发
    • 运行时会在应用程序启动时在后台开启一个用于强制触发垃圾收集的 Goroutine，该 Goroutine 的职责非常简单 — 调用 runtime.gcStart 尝试启动新一轮的垃圾收集
  • 手动触发
    • 用户程序会通过 runtime.GC 函数在程序运行期间主动通知运行时执行，该方法在调用时会阻塞调用方直到当前垃圾收集循环完成，在垃圾收集期间也可能会通过 STW 暂停整个程序：
  • 申请内存
    • 运行时会将堆上的对象按大小分成微对象、小对象和大对象三类，这三类对象的创建都可能会触发新的垃圾收集循环：
• 垃圾收集的清理中包含对象回收器（Reclaimer）和内存单元回收器，这两种回收器使用不同的算法清理堆内存：
  • 对象回收器在内存管理单元中查找并释放未被标记的对象，但是如果 runtime.mspan 中的所有对象都没有被标记，整个单元就会被直接回收，该过程会被 runtime.mcentral.cacheSpan 或者 runtime.sweepone 异步触发；
  • 内存单元回收器会在内存中查找所有的对象都未被标记的 runtime.mspan，该过程会被 runtime.mheap.reclaim 触发；