GC垃圾回收：三色标记法与混合写屏障

Posted on In Views:
常用的垃圾回收机制，以及Golang中的三色标记与混合写屏障(Write Barrier)

1. 什么是垃圾回收？

垃圾回收（GC） 是一种自动内存管理机制。它的核心任务是识别并释放程序中不再使用的内存资源，防止内存泄漏。

如果没有 GC，程序员需要手动 malloc 和 free 内存（如 C/C++），这容易导致：

  • 悬挂指针：使用了已经被释放的内存。
  • 内存泄漏：忘记释放不再使用的内存。

2. 常见的垃圾回收算法

在 Go 语言确立现在的 GC 模式之前，业界已经有几种经典的算法：

2.1 引用计数 (Reference Counting)

每个对象维护一个引用计数器。

  • 原理：
    • 对象被创建或赋值给变量时，计数器 +1。
    • 引用失效（变量离开作用域、被重新赋值）时，计数器 -1。
    • 当计数器为 0 时，立即回收。
  • 优点：
    • 实时性高：不需要等到内存耗尽才回收，垃圾产生的瞬间即可回收。
  • 缺点：
    • 维护成本大：频繁更新计数器影响性能。
    • 循环引用问题：致命伤。如果对象 A 引用 B，B 也引用 A，但外界不再引用它们，它们的计数永远不为 0，导致内存泄漏。

2.2 标记-清除 (Mark and Sweep)

这是很多语言（包括早期的 Go）GC 的基础。

  • 原理：
    1. 标记阶段：从根变量（Root，如全局变量、栈上的局部变量）出发，遍历所有引用的对象，打上“存活”标记。
    2. 清除阶段：遍历堆内存，回收所有未被标记的对象。
  • 优点：解决循环引用问题。
  • 缺点：
    • STW (Stop The World)：为了保证标记准确，必须暂停程序运行，导致卡顿。
    • 内存碎片：回收后的内存是不连续的。

2.3 分代收集 (Generational Collection)

Java 等语言的主流算法。

  • 原理：基于“大部分对象都是朝生夕死”的假设。
    • 新生代：存放生命周期短的对象，GC 频率高，通常用复制算法。
    • 老年代：存放生命周期长的对象，GC 频率低，通常用标记-清除/整理。
  • 优点：性能极好，针对性优化。
  • 缺点：算法实现复杂。
  • 注：Go 目前并未采用分代收集，而是专注于低延迟的并发标记。

3. Go 的三色标记法

Go 语言为了降低 STW 的时间，采用了 三色标记法。它将对象逻辑上分成三种颜色：

  • ⚪ 白色：未被扫描的对象（潜在的垃圾）。
  • 🔘 灰色：已被扫描，但其引用的子对象还没扫描（中间状态）。
  • ⚫ 黑色：已被扫描，且其引用的子对象也已扫描（存活对象）。

3.1 标记过程

  1. 初始状态：所有对象都是 白色。
  2. 扫描根节点：从 Root Set（根节点）开始遍历，找到所有直接引用的对象，将其标记为 灰色。
  3. 遍历灰色节点：
    • 从灰色对象集合中取出一个对象，将其引用的所有白色子对象标记为 灰色。
    • 将该对象自身标记为 黑色。
  4. 循环：重复步骤 3，直到灰色集合为空。
  5. 清除：此时剩余的 白色 对象即为不可达垃圾，进行回收。

3.2 为什么还需要 STW？

如果三色标记过程是并发运行的（即用户代码和 GC 程序同时跑），会发生什么？

假设 GC 正在扫描，此时用户代码修改了引用关系：

  1. 一个黑色对象（已扫描完毕）突然引用了一个白色对象。
  2. 同时，该白色对象原本的上游灰色对象断开了对它的引用。

结果：该白色对象依然存活（被黑色引用），但 GC 认为黑色已经处理完不会再看它，且灰色也不再引用它。于是 GC 会错误地回收这个白色对象，导致程序崩溃。

这就是著名的 “对象丢失” 问题。为了安全，早期的 Go 必须在标记阶段全程 STW，但这对性能影响太大。

4. 屏障机制 (Barrier)

为了在并发标记时防止对象丢失，必须破坏导致丢失的两个必要条件之一：

  1. 条件 1：黑色对象引用了白色对象。
  2. 条件 2：灰色对象与该白色对象之间的引用关系被破坏（且该白色对象没有其他灰色路径）。

只要破坏其中一个，就能保证安全。这就引入了 写屏障（Write Barrier）：在用户代码修改指针（引用）时，由编译器插入的一段钩子代码（Hook）。

4.1 Dijkstra 插入写屏障 (破坏条件 1)

  • 原则（强三色不变性）：强制不允许黑色对象直接引用白色对象。
  • 实现：
    当对象 A 引用对象 B 时 (A.ptr = B)，如果 B 是白色，强制把 B 标记为 灰色。

    “既然你要引用它，我就把它推到灰色集合里，等下会扫描到它。”

  • 缺点：
    Go 的栈空间极其频繁地进行指针操作，如果在栈上也加写屏障，性能开销太大。因此 Go 选择只在堆上开启写屏障。这意味着栈上的黑色节点可能引用白色节点，所以在 GC 结束前，必须 STW 并重新扫描栈，以确保准确性。

4.2 Yuasa 删除写屏障 (破坏条件 2)

  • 原则（弱三色不变性）：允许黑色引用白色，但必须保证该白色对象有路可走（被灰色保护）。
  • 实现：
    当对象 A 删除对 B 的引用时 (A.ptr = NULL 或 A.ptr = C)，如果 B 是白色，强制把 B 标记为 灰色。

    “不管你是不是垃圾，既然刚才还有人引用你，我就悲观地认为你可能还需要，先把本轮命保住。”

  • 优点：不需要结束时重新扫描栈。
  • 缺点：回收精度低。即使 B 真是垃圾，这一轮也会幸存，成为浮动垃圾，只能等下一轮 GC 回收。

5. Go v1.8+ 的混合写屏障 (Hybrid Write Barrier)

Go 1.8 之前，为了解决 Dijkstra 屏障需要在结束时 STW 重新扫描栈的问题（在大并发场景下，STW 可能高达 10~100ms），官方引入了 混合写屏障。

它结合了 Dijkstra 和 Yuasa 的优点，极大地压缩了 STW 时间（通常在 1ms 以下）。

5.1 核心规则

  1. GC 开始时：将栈上的所有可达对象全部标记为 黑色（不需要二次扫描）。
  2. GC 期间：任何在栈上创建的新对象，均为 黑色。
  3. 堆上被删除的引用：触发 Yuasa 屏障，标记为 灰色。
  4. 堆上新添加的引用：触发 Dijkstra 屏障，标记为 灰色。

5.2 伪代码逻辑

1
2
3
4
5
// 混合写屏障伪代码
writePointer(slot, ptr):
    shade(slot.oldValue)  // 删除屏障：保护旧值 (Yuasa)
    shade(ptr)            // 插入屏障：保护新值 (Dijkstra)
    *slot = ptr           // 赋值

5.3 总结优势

  • 不再需要 STW 重新扫描栈（得益于 Yuasa 的思想和栈对象全黑的处理）。
  • 精度适中：虽然会有浮动垃圾，但保证了并发标记的安全性。
  • 性能强劲：几乎消除了 GC 带来的长时间停顿。

6. 回答

如果面试官问：“Go 的 GC 是怎么实现的？”，可以这样回答：

  1. 基础：Go 采用 三色标记法 进行垃圾回收，将对象分为白、灰、黑三类。
  2. 痛点：并发标记过程中，如果用户修改引用关系，可能导致“对象丢失”。
  3. 演进：
    • Go v1.5 使用 Dijkstra 插入写屏障，但需要在 GC 结束时 STW 重新扫描栈。
    • Go v1.8 引入 混合写屏障，结合了插入屏障和删除屏障的优点。
  4. 最终效果：混合写屏障允许栈操作无屏障（提升性能），且 GC 结束时无需 STW 重扫栈（极大降低延迟），仅在 GC 开始和结束的极其短暂时间需要 STW。