三色标记法：垃圾回收标记算法完全指南

三色标记法（Tri-Color Marking）是现代垃圾收集器（GC）中的一项基础技术。它优雅地解决了识别内存中哪些对象仍然可达、哪些可以安全回收的问题。这个算法被广泛应用于许多生产系统中，从 Go 运行时到 V8 JavaScript 引擎。

结合我在微软、Booking.com 和阿里巴巴 11 年以上的高性能系统开发经验，我将通过交互式可视化带你深入理解这个算法，让抽象概念变得具体可感。

交互式可视化

让我们先看看算法的实际运行。尝试不同的示例来理解对象如何在三种颜色之间转换：

什么是三色标记法？

三色标记法是垃圾回收标记阶段使用的一种标记策略。它使用颜色将对象分为三个集合：

白色集合：尚未被访问的对象。标记完成后，白色对象被视为垃圾。
灰色集合：已被发现但其引用尚未完全探索的对象。
黑色集合：已被完全探索的对象——它们是可达的，所有引用都已被处理。

核心不变式

算法在执行过程中维护一个关键不变式：

黑色对象不能直接指向白色对象。

这个不变式确保了正确性：如果一个黑色对象（已扫描）指向白色对象（未扫描），那个白色对象可能会被错误地当作垃圾回收。

算法工作原理

阶段 1：初始化

堆中的所有对象开始时都在白色集合中。这代表了”无罪推定”的方法——每个对象在被证明可达之前都可能是垃圾。

// 初始化伪代码
function initialize(heap) {
  for (object in heap) {
    object.color = WHITE;
  }
}

阶段 2：标记根对象

根集合包含所有可直接访问的对象——通常包括：

全局变量
栈变量
CPU 寄存器

这些根对象被标记为灰色，因为我们知道它们可达，但还没有扫描它们的引用。

function markRoots(roots) {
  for (root in roots) {
    root.color = GRAY;
    graySet.add(root);
  }
}

阶段 3：处理灰色对象

这是算法的主循环。我们重复执行：

从灰色集合中取出一个灰色对象
对于该对象中的每个引用：
- 如果被引用的对象是白色，标记为灰色
将当前对象标记为黑色（已完全处理）

function processGrayObjects() {
  while (graySet.isNotEmpty()) {
    let current = graySet.removeAny();
    
    // 扫描所有引用
    for (reference in current.references) {
      if (reference.color == WHITE) {
        reference.color = GRAY;
        graySet.add(reference);
      }
    }
    
    // 标记当前对象为已完全处理
    current.color = BLACK;
    blackSet.add(current);
  }
}

阶段 4：清扫

标记完成后，所有白色对象都不可达，可以被回收：

function sweep(heap) {
  for (object in heap) {
    if (object.color == WHITE) {
      // 这个对象是垃圾
      freeMemory(object);
    } else {
      // 为下一次 GC 循环重置颜色
      object.color = WHITE;
    }
  }
}

逐步示例

让我们追踪一个简单的例子，对象关系为 A → B → C，还有一个孤立的循环 D ↔ E：

初始状态：
Root → A → B → C
D ↔ E（孤立循环）

所有对象：WHITE

步骤 1： 标记根对象 A 为灰色

A: GRAY
B, C, D, E: WHITE
灰色集合：[A]

步骤 2： 处理 A，发现 B

A: BLACK（已扫描）
B: GRAY（已发现）
C, D, E: WHITE
灰色集合：[B]

步骤 3： 处理 B，发现 C

A: BLACK
B: BLACK（已扫描）
C: GRAY（已发现）
D, E: WHITE
灰色集合：[C]

步骤 4： 处理 C

A, B, C: BLACK
D, E: WHITE（不可达！）
灰色集合：[]（空）

结果： D 和 E 保持白色——它们形成了一个从根不可达的孤立循环。它们可以作为垃圾被回收。

为什么使用三种颜色？

你可能会想：为什么不只用两种颜色（可达/不可达）？

三色方案提供了几个优势：

1. 增量回收

灰色集合代表标记过程的”波前”。我们可以：

处理几个灰色对象
暂停让程序（mutator）运行
稍后恢复处理

这使得增量 GC 成为可能，不会长时间暂停程序。

2. 并发回收

通过适当的同步，GC 可以与程序并发运行：

程序可能创建新对象或改变引用
灰色集合帮助跟踪还需要扫描的内容
不变式防止回收可达对象

3. 清晰的进度跟踪

三个集合清楚地显示：

白色： 尚未探索
灰色： 正在探索（进行中）
黑色： 完全探索（已完成）

处理并发修改

当 GC 与程序（mutator）并发运行时，mutator 可能会：

创建新对象：新对象开始时是白色或灰色
更新引用：这可能违反我们的不变式！

问题

考虑这个场景：

初始：
Black → Gray → White

Mutator 更新：
Black → White（现在指向白色！）
Gray → null（移除原始路径）

现在黑色对象指向白色对象，违反了我们的不变式！白色对象可能被错误地回收。

解决方案

两种主要方法解决这个问题：

写屏障（Dijkstra 算法）

当黑色对象获得对白色对象的引用时，将白色对象标记为灰色：

function writeBarrier(blackObject, newReference) {
  if (blackObject.color == BLACK && newReference.color == WHITE) {
    newReference.color = GRAY;
    graySet.add(newReference);
  }
}

读屏障（Yuasa 算法）

当引用被移除时，如果它指向白色对象，将该对象标记为灰色：

function readBarrier(object, oldReference) {
  if (oldReference.color == WHITE) {
    oldReference.color = GRAY;
    graySet.add(oldReference);
  }
}

实际应用

Go 运行时

Go 的垃圾收集器使用三色标记法，具有：

并发标记（GC 与 goroutine 同时运行）
写屏障来维护不变式
根据分配速率调整 GC 频率的调度器

// 简化的 Go GC 伪代码
func gcMark() {
    // 短暂停止世界
    stopTheWorld()
    
    // 标记根对象
    scanRoots()
    
    // 启动世界，并发标记
    startTheWorld()
    
    // 并发处理灰色对象
    for hasGrayObjects() {
        processGrayObjects()
    }
}

V8 JavaScript 引擎

V8 在以下场景使用三色标记：

主 GC（标记-压缩）
增量标记
并发标记

Java HotSpot

一些 Java 收集器如 G1 和 ZGC 使用三色标记进行并发和增量回收。

复杂度分析

时间复杂度

标记阶段： O(R + E)，其中：
- R = 可达对象数量
- E = 可达对象之间的引用数量

每个对象被访问一次，每个引用被遍历一次。

空间复杂度

灰色集合： O(W)，其中 W 是对象图的最大”宽度”
- 最坏情况（长链），W = 1
- 最好情况（星形模式），W = R - 1

优缺点

优点 ✅

增量性： 可以暂停和恢复标记
并发性： 可以与程序同时运行
精确性： 正确识别所有可达对象
可扩展性： 时间与可达对象成正比（而非总堆大小）

缺点 ❌

开销： 需要跟踪三个集合
屏障： 写/读屏障增加执行成本
复杂性： 比停止世界方法更复杂
浮动垃圾： 并发标记可能错过一些垃圾（下次循环回收）

常见面试问题

Q1：为什么不能只用两种颜色？

两种颜色（已标记/未标记）无法为增量或并发回收提供足够的信息。灰色代表我们正在积极探索的对象的”前沿”，允许我们暂停和恢复。

Q2：这如何处理循环引用？

算法自然地处理循环引用。即使对象相互引用，只有从根可达时它们才会变成灰色。孤立的循环保持白色并被回收。

Q3：与引用计数有什么区别？

引用计数：

跟踪每个对象的引用数量
无法处理循环引用
立即回收

三色标记：

从根追踪可达性
自然处理循环引用
批量回收

练习题

问题 1：追踪算法

给定这个对象图：

Root1 → A → C
Root2 → B → C
D → E → D（循环）

逐步追踪算法。哪些对象会被回收？

解答

初始：所有 WHITE

步骤 1：标记根对象
A: GRAY, B: GRAY
其他：WHITE

步骤 2：处理 A
A: BLACK, C: GRAY（从 A 发现）
B: GRAY, D, E: WHITE

步骤 3：处理 B
A, B: BLACK
C：已经是 GRAY
D, E: WHITE

步骤 4：处理 C
A, B, C: BLACK
D, E: WHITE

结果：D 和 E 是垃圾（孤立循环）

问题 2：设计写屏障

为三色标记算法实现一个写屏障，维护”黑色对象不指向白色对象”的不变式。

解答

function writeBarrier(
  sourceObj: Object,
  field: string,
  targetObj: Object
) {
  // 执行写操作
  sourceObj[field] = targetObj;
  
  // 如果源是黑色且目标是白色，
  // 将目标标记为灰色以维护不变式
  if (sourceObj.color === 'BLACK' && targetObj.color === 'WHITE') {
    targetObj.color = 'GRAY';
    graySet.add(targetObj);
  }
}

多语言实现

JavaScript/TypeScript

class TriColorMarking {
  private whiteSet = new Set<number>();
  private graySet = new Set<number>();
  private blackSet = new Set<number>();
  
  mark(roots: number[], graph: Map<number, number[]>): Set<number> {
    // 初始化所有为白色
    for (const node of graph.keys()) {
      this.whiteSet.add(node);
    }
    
    // 标记根对象为灰色
    for (const root of roots) {
      this.whiteSet.delete(root);
      this.graySet.add(root);
    }
    
    // 处理灰色对象
    while (this.graySet.size > 0) {
      const current = this.graySet.values().next().value;
      this.graySet.delete(current);
      
      // 标记引用
      const refs = graph.get(current) || [];
      for (const ref of refs) {
        if (this.whiteSet.has(ref)) {
          this.whiteSet.delete(ref);
          this.graySet.add(ref);
        }
      }
      
      // 标记当前为黑色
      this.blackSet.add(current);
    }
    
    // 返回垃圾（剩余的白色对象）
    return this.whiteSet;
  }
}

Python

class TriColorMarking:
    def __init__(self):
        self.white_set = set()
        self.gray_set = set()
        self.black_set = set()
    
    def mark(self, roots, graph):
        """
        使用三色算法标记可达对象。
        返回垃圾（白色）对象集合。
        """
        # 初始化所有为白色
        self.white_set = set(graph.keys())
        
        # 标记根对象为灰色
        for root in roots:
            if root in self.white_set:
                self.white_set.remove(root)
                self.gray_set.add(root)
        
        # 处理灰色对象
        while self.gray_set:
            current = self.gray_set.pop()
            
            # 标记引用
            for ref in graph.get(current, []):
                if ref in self.white_set:
                    self.white_set.remove(ref)
                    self.gray_set.add(ref)
            
            # 标记当前为黑色
            self.black_set.add(current)
        
        # 返回垃圾
        return self.white_set

Java

public class TriColorMarking {
    private Set<Integer> whiteSet = new HashSet<>();
    private Set<Integer> graySet = new HashSet<>();
    private Set<Integer> blackSet = new HashSet<>();
    
    public Set<Integer> mark(
        List<Integer> roots,
        Map<Integer, List<Integer>> graph
    ) {
        // 初始化所有为白色
        whiteSet.addAll(graph.keySet());
        
        // 标记根对象为灰色
        for (int root : roots) {
            if (whiteSet.contains(root)) {
                whiteSet.remove(root);
                graySet.add(root);
            }
        }
        
        // 处理灰色对象
        while (!graySet.isEmpty()) {
            int current = graySet.iterator().next();
            graySet.remove(current);
            
            // 标记引用
            List<Integer> refs = graph.getOrDefault(
                current,
                Collections.emptyList()
            );
            for (int ref : refs) {
                if (whiteSet.contains(ref)) {
                    whiteSet.remove(ref);
                    graySet.add(ref);
                }
            }
            
            // 标记当前为黑色
            blackSet.add(current);
        }
        
        // 返回垃圾
        return whiteSet;
    }
}

性能优化技巧

1. 灰色集合实现

在并行收集器中使用工作窃取双端队列作为灰色集合：

class WorkStealingDeque<T> {
  private items: T[] = [];
  
  pushBottom(item: T) {
    this.items.push(item);
  }
  
  popBottom(): T | undefined {
    return this.items.pop();
  }
  
  popTop(): T | undefined {
    return this.items.shift();
  }
}

2. 预取

处理灰色对象时预取对象数据以减少缓存未命中：

// C++ 示例
while (!graySet.empty()) {
    auto current = graySet.front();
    graySet.pop();
    
    // 预取下一批对象
    for (auto& ref : current->references) {
        __builtin_prefetch(ref);
    }
    
    // 处理当前对象
    processObject(current);
}

3. 并行标记

多个线程可以使用线程本地灰色集合并发标记：

function parallelMark(roots: number[], graph: Map<number, number[]>) {
  const workers = [];
  const localGraySets = [];
  
  // 在工作线程之间分配根对象
  for (let i = 0; i < NUM_WORKERS; i++) {
    localGraySets[i] = new Set();
    workers[i] = new Worker(() => {
      while (hasWork()) {
        processLocalGraySet(localGraySets[i]);
      }
    });
  }
}

总结

三色标记法是一种优雅而强大的垃圾回收技术。它能够增量和并发运行的能力使其成为无法容忍长 GC 暂停的现代系统的理想选择。

关键要点：

三种颜色跟踪标记进度：白色（未访问）、灰色（前沿）、黑色（已完成）
不变式： 无黑色→白色指针防止回收可达对象
屏障（写/读）在并发执行期间维护正确性
广泛应用于 Go、V8、Java 和许多其他生产系统

本文顶部的交互式可视化让你可以探索不同的场景。尝试创建自己的对象图来加深理解！