解析三色标记清除算法（Tri-color Marking）：如何通过写屏障（Write Barrier）实现并发扫描？

各位同仁，各位对运行时系统和垃圾回收机制充满热情的开发者们，下午好。

今天，我们将深入探讨现代垃圾回收领域的一个核心议题：三色标记清除算法（Tri-color Marking）如何通过写屏障（Write Barrier）实现并发扫描。这是一个复杂而精妙的设计，它使得我们的应用程序能够在几乎不停顿的情况下进行垃圾回收，极大地提升了用户体验和系统吞吐量。

1. 垃圾回收的挑战与并发的需求

在自动内存管理的世界里，垃圾回收（Garbage Collection, GC）是避免内存泄漏、简化程序员心智负担的关键技术。然而，传统的垃圾回收器，特别是早期的标记-清除（Mark-Sweep）或标记-复制（Mark-Copy）算法，往往需要暂停应用程序的所有执行线程，即所谓的“Stop-The-World”（STW）阶段。在STW期间，应用程序完全停止响应，这对于延迟敏感型应用（如交互式桌面应用、高并发服务器）来说是不可接受的。

为了解决STW带来的问题，并发垃圾回收应运而生。并发GC的目标是让GC线程与应用程序线程（Mutator）并行执行大部分工作，从而将STW暂停时间缩短到毫秒甚至微秒级别。三色标记算法是实现并发GC的基石，而写屏障则是确保并发正确性的核心机制。

2. 三色标记算法的基础原理

三色标记算法是图遍历的一种应用，它将堆中的所有对象划分为三种颜色，以表示其在垃圾回收过程中的不同状态：

• 白色 (White)：
  • 初始状态，代表对象尚未被GC访问，也尚未被确定为可达。
  • 在标记阶段结束时，所有保持白色的对象都将被视为垃圾，可以被回收。
• 灰色 (Gray)：
  • 代表对象已经被GC访问，并且确认是可达的，但其所有的引用字段（子对象）尚未被扫描。
  • 灰色对象是GC工作队列中的待处理项。
• 黑色 (Black)：
  • 代表对象已经被GC访问，确认是可达的，并且其所有的引用字段都已经被扫描完毕。
  • 黑色对象不会再有指向白色对象的引用（这是并发GC需要维护的关键不变式）。

基本的三色标记过程（非并发）：

1. 初始阶段： 假定所有对象都是白色。
2. 根集扫描： 从根集（栈变量、全局变量、寄存器等）开始，所有直接被根集引用的对象被标记为灰色，并放入一个工作队列。
3. 标记阶段： GC线程从工作队列中取出一个灰色对象：
   • 将其所有直接引用的对象标记为灰色（如果它们是白色），并加入工作队列。
   • 将该对象自身标记为黑色。
   • 重复此过程，直到工作队列为空，不再有灰色对象。
4. 清除阶段： 遍历整个堆，所有仍然保持白色的对象都是不可达的垃圾，将其回收。

这个过程在单线程或STW环境下是完美无缺的。然而，当应用程序线程与GC线程并发运行时，情况就变得复杂起来。

3. 并发标记的挑战：不变式的破坏

并发标记最大的挑战在于应用程序线程（mutator）在GC线程扫描对象图的同时，可能会修改对象之间的引用关系。这种修改可能导致三色不变式被破坏，进而引发严重的错误：对象被错误地回收。

三色标记算法的核心不变式是：“不允许黑色对象直接指向白色对象”。

设想以下场景，GC线程正在并发执行标记阶段：

1. 场景一：悬挂指针（Floating Garbage）—— 黑色对象指向了新的白色对象

   • Mutator创建了一个新对象 C (白色)。
   • GC已经将对象 A 标记为黑色。
   • Mutator修改 A 的一个字段，使其引用 C (A.field = C)。
   • 此时，A 是黑色，C 是白色，并且 A 指向 C。这违反了“黑色对象不指向白色对象”的强三色不变式。
   • 结果：C 是可达的，但GC可能不会扫描到它，因为它不是灰色，也未被其他灰色对象引用。最坏的情况是 C 在本轮GC中被误判为垃圾而回收，导致程序崩溃。

2. 场景二：丢失可达对象（Lost Object）—— 唯一的引用路径被切断

   • 对象 A (黑色)， B (灰色)， C (白色)。
   • 假设 A 曾经通过 B 间接引用 C (A -> B -> C)。
   • GC线程正在处理 B，将其子对象 C 标记为灰色。
   • 并发地，Mutator执行了以下操作：
     • A.field = B 被修改为 A.field = null (切断了 A 到 B 的唯一引用)。
     • 同时，另一个对象 D (黑色) 创建了一个新的引用 D.field = C。
   • 如果GC线程还没有来得及扫描到 B 并将其子对象 C 标记为灰色，或者它已经扫描了 B 但 B 已经被 A 移除，那么 C 就可能被误认为不可达，即使它现在通过 D 是可达的。
   • 这种场景更常发生在 A 引用 B，B 引用 C，然后 A 的引用被移除了，C 失去了一个可达路径。如果 C 没有其他路径，它就可能被回收。

要解决这些问题，我们需要一个机制来“观察”和“干预”Mutator对对象图的修改，这就是写屏障（Write Barrier）。

4. 写屏障：并发GC的守护者

写屏障是一段由编译器或JVM在特定内存写操作（通常是引用类型的字段赋值）之前或之后自动插入的代码。它的作用是在Mutator修改对象引用时，通知GC系统，从而维护三色不变式，防止可达对象被错误回收。

写屏障的开销是不可避免的，因为它会增加每次引用赋值操作的指令数。因此，设计高效的写屏障是并发GC的关键之一。

根据维护三色不变式的策略不同，写屏障可以分为两大类：

1. Snapshot-At-The-Beginning (SATB) Barrier (预写屏障)
2. Incremental Update Barrier (后写屏障 / Dijkstra Barrier)

我们来分别详细探讨这两种屏障。

4.1. Snapshot-At-The-Beginning (SATB) Barrier

SATB屏障的核心思想是：“在GC开始时，对整个对象图拍一张快照。所有在快照中可达的对象，即使在GC期间变得不可达，也应该在本轮GC中被保留。” 换句话说，它保证了在GC周期开始时所有可达的对象都不会被回收。

工作原理：

当Mutator执行一个引用赋值操作 object.field = new_ref 时，SATB屏障在赋值发生之前被触发，它会检查 object.field 的旧值。

SATB屏障的逻辑：

// 假设 GC 正在进行并发标记
// 这是一个预写屏障，在赋值操作发生之前执行

void SATB_WriteBarrier(Object current_object_being_modified, Object old_ref_value_at_field) {
    if (GC_IsMarkingPhaseActive()) {
        // 如果旧引用指向的对象是白色的，说明它可能在当前GC周期开始时是可达的
        // 但现在它的唯一引用路径可能被切断了
        // 为了确保它及其子图不会被错误回收，将其标记为灰色，加入GC工作队列
        if (old_ref_value_at_field != null && GetColor(old_ref_value_at_field) == White) {
            SetColor(old_ref_value_at_field, Gray); // 将旧引用指向的对象染灰
            GC_AddToWorkQueue(old_ref_value_at_field);
        }
    }
}

// Mutator 的引用赋值操作伪代码
void Mutator_Assign(Object obj, Field field, Object new_value) {
    // 1. 触发写屏障
    SATB_WriteBarrier(obj, obj.field); // 传入旧值
    // 2. 执行实际的赋值
    obj.field = new_value;
}

SATB如何解决不变式破坏问题？

SATB屏障主要针对的是“丢失可达对象”的问题（Mutator切断了从黑色对象到白色对象的唯一引用路径）。通过将旧引用指向的对象染灰，即使这个旧引用被切断了，该对象及其子图也会被GC扫描到，从而保证了GC开始时可达的对象不会被错误回收。

SATB的特点：

• 优点：
  • 屏障逻辑相对简单，通常只涉及一次颜色检查和潜在的染灰操作。
  • 在GC的初始标记阶段之后，Mutator可以自由地创建新对象，这些新对象通常默认是白色，但它们不会影响GC对旧对象图的快照。
• 缺点：
  • 浮动垃圾 (Floating Garbage)： SATB最大的缺点是可能产生“浮动垃圾”。一个对象在GC开始时是可达的（因此被快照保护），但在GC过程中Mutator将所有指向它的引用都切断了，使其变得真正不可达。由于SATB的保守性，它仍然会在本轮GC中被标记为黑色并保留下来，直到下一轮GC才会被回收。这增加了内存的瞬时占用。
  • 需要更长的Remark阶段： 为了处理浮动垃圾和确保所有活跃对象都被正确标记，SATB通常需要一个较短的STW“再标记”（Remark）阶段。在这个阶段，GC会重新扫描根集和所有灰色对象，以处理并发标记期间的变更，确保最终的正确性。

应用：
Go语言的垃圾回收器就是基于SATB并发标记的。

4.2. Incremental Update (Dijkstra) Barrier

Incremental Update (IU) 屏障，有时也被称为Dijkstra屏障，其核心思想是：“维护强三色不变式：任何黑色对象都不能直接指向白色对象。” 如果Mutator试图创建一个黑色到白色的引用，屏障会立即将白色对象染灰，从而使得这个引用不再违反不变式。

工作原理：

当Mutator执行一个引用赋值操作 object.field = new_ref 时，IU屏障在赋值发生之后（或同时）被触发，它会检查 object (赋值操作的源对象) 和 new_ref (赋值操作的目标对象)。

Incremental Update屏障的逻辑：

// 假设 GC 正在进行并发标记
// 这是一个后写屏障，在赋值操作发生之后执行（逻辑上）

void IncrementalUpdate_WriteBarrier(Object source_object, Object new_ref_value_at_field) {
    if (GC_IsMarkingPhaseActive()) {
        // 如果源对象是黑色的，并且新引用指向的对象是白色的
        // 这将违反“黑色对象不指向白色对象”的不变式
        // 必须立即将新引用指向的对象染灰，使其被GC扫描
        if (GetColor(source_object) == Black && new_ref_value_at_field != null && GetColor(new_ref_value_at_field) == White) {
            SetColor(new_ref_value_at_field, Gray); // 将新引用指向的对象染灰
            GC_AddToWorkQueue(new_ref_value_at_field);
        }
    }
}

// Mutator 的引用赋值操作伪代码
void Mutator_Assign(Object obj, Field field, Object new_value) {
    // 1. 执行实际的赋值
    obj.field = new_value;
    // 2. 触发写屏障
    IncrementalUpdate_WriteBarrier(obj, new_value); // 传入源对象和新值
}

Incremental Update如何解决不变式破坏问题？

IU屏障主要针对的是“黑色对象指向了新的白色对象”的问题（场景一）。通过将新引用的目标对象染灰，GC就能在后续扫描中处理这个对象，确保它不会因为被黑色对象引用而遗漏。

Incremental Update的特点：

• 优点：
  • 无浮动垃圾 (No Floating Garbage)： IU屏障能够精确地标记所有在GC结束时可达的对象。如果一个对象在GC过程中变得不可达，它会最终被回收，不会像SATB那样产生浮动垃圾。
  • 更短的Remark阶段： 由于屏障直接维护了强三色不变式，通常可以在并发标记阶段结束后进行一个非常短的Remark阶段，甚至可能在某些情况下完全消除。
• 缺点：
  • 屏障逻辑更复杂： 需要检查源对象和目标对象的颜色，可能需要更多的内存访问，开销可能略高。
  • 可能将已扫描对象重新染灰： 如果一个黑色对象在GC扫描完成其所有子对象后，又通过Mutator添加了一个新的引用，指向了一个新的白色对象，那么这个白色对象会被染灰，然后GC需要再次扫描它。这可能导致GC工作量的增加。

应用：
HotSpot JVM的CMS (Concurrent Mark Sweep) 垃圾回收器在其并发标记阶段使用了类似的Incremental Update屏障（CMS Barrier）。G1 GC也使用了一个混合屏障，结合了SATB和Incremental Update的特点。

4.3. 写屏障的开销与优化

无论是SATB还是Incremental Update，写屏障都会带来运行时开销。每次引用赋值都需要执行额外的检查和潜在的修改。为了降低这种开销，通常会采用以下优化措施：

• 条件执行： 写屏障只在GC的并发标记阶段激活。在其他阶段（如清除、初始标记前、完全停顿GC时），屏障代码不会被执行或执行极简逻辑。
• 硬件支持： 一些现代处理器提供了内存访问监听机制，可以辅助写屏障的实现，但通常GC是在软件层面实现屏障。
• 卡片标记 (Card Marking)： 对于大型对象或数组，如果每次修改一个元素都触发完整的写屏障，开销会非常大。卡片标记将堆划分为小块（卡片），当修改某个卡片中的引用时，只将该卡片标记为“脏”，表示它需要被GC重新扫描。GC在Remark阶段只扫描脏卡片，而不是整个对象图。这是一种降低写屏障粒度，提高效率的常用技术。

5. 并发扫描的完整流程与写屏障的集成

现在，我们将三色标记、并发执行和写屏障结合起来，描绘一个完整的并发GC周期。

GC并发标记-清除的典型阶段：

1. 初始标记 (Initial Mark) – STW (短暂停顿)

   • 应用程序线程暂停。
   • GC线程扫描根集（栈、寄存器、全局变量等），将所有直接可达的对象标记为灰色，并加入GC工作队列。
   • 同时，激活写屏障。
   • 这个阶段需要STW来确保根集的一致性，但由于只扫描根集，暂停时间非常短。
   • 解除暂停，应用程序线程恢复执行。

2. 并发标记 (Concurrent Mark) – GC与Mutator并行

   • GC线程从工作队列中取出灰色对象，将其所有子对象（如果为白色）染灰并加入队列，然后将自身染黑。
   • Mutator线程并发执行，创建新对象，修改引用关系。
   • 写屏障在此阶段全程活跃。 每当Mutator修改一个引用字段时，写屏障就会被触发：
     • 如果使用SATB： 屏障会记录旧引用指向的对象，并将其染灰（如果它是白色）。
     • 如果使用Incremental Update： 屏障会检查新引用指向的对象，并将其染灰（如果源对象是黑色且目标对象是白色）。
   • GC线程持续处理灰色队列，直到队列为空。此时，大部分可达对象已经被标记，但由于Mutator的并发修改，可能存在一些漏网之鱼或浮动垃圾。

3. 最终标记/再标记 (Final Mark / Remark) – STW (短暂停顿)

   • 应用程序线程再次暂停。
   • 这个阶段的目的是处理并发标记阶段中因Mutator修改而产生的漏标对象，或处理写屏障所积累的“脏”数据。
   • GC线程会重新扫描根集、所有仍然是灰色的对象，以及写屏障可能维护的特殊集合（例如，SATB可能需要处理所有在并发阶段被染灰的对象，IU可能需要处理所有被屏障标记为需要重新扫描的区域）。
   • 这个阶段也需要STW，以确保对象图在最终确认可达性时是静态的。但由于大部分工作已在并发阶段完成，这个暂停时间通常也非常短。
   • 解除暂停，应用程序线程恢复执行。

4. 并发清除 (Concurrent Sweep) – GC与Mutator并行

   • GC线程遍历整个堆，回收所有仍然是白色的对象。这些对象被确定为不可达的垃圾。
   • 应用程序线程并发执行，继续运行。
   • 写屏障在此阶段通常会关闭或不执行任何操作，因为标记阶段已经结束。
   • 此阶段的开销取决于堆大小和垃圾数量，但由于是并发执行，对Mutator的直接影响很小。

5. 重置 (Reset) – GC线程内部

   • GC系统清理内部状态，为下一轮GC做准备。所有对象颜色重置为白色（逻辑上），或者通过指针碰撞等方式进行空间分配。

表格总结：两种写屏障的比较

特性	Snapshot-At-The-Beginning (SATB) Barrier	Incremental Update Barrier (Dijkstra)
触发时机	预写屏障：在引用赋值 obj.field = new_ref 之前	后写屏障：在引用赋值 obj.field = new_ref 之后
检查对象	obj.field 的旧值	obj (源对象) 和 new_ref (目标对象)
屏障逻辑	如果 旧值 为白色，则将其染灰。	如果 源对象 为黑色且 新值 为白色，则将 新值 染灰。
维护不变式	保证GC开始时可达的对象不会被回收（“快照”）。	保证“黑色对象不指向白色对象”的强不变式。
浮动垃圾	可能产生浮动垃圾（GC开始时可达，GC期间变为不可达）。	通常不产生浮动垃圾（更精确）。
Remark阶段	通常需要一个稍长的Remark阶段来处理并发期间的变化。	通常需要一个较短的Remark阶段，甚至可能优化掉。
复杂性	相对简单。	相对复杂，可能需要更多内存访问。
常见应用	Go语言GC	HotSpot CMS (部分), G1 (混合屏障)

6. 深入代码：伪代码示例

为了更好地理解，我们用伪代码来模拟一个简单的并发三色标记清除GC，并演示两种写屏障的实现。

通用数据结构和辅助函数：

enum Color { WHITE, GRAY, BLACK };

class Object {
    Color color;
    Map<String, Object> fields; // 模拟引用字段
    // ... 其他数据字段

    Object() {
        this.color = WHITE;
        this.fields = new HashMap<>();
    }

    // 获取/设置颜色
    Color getColor() { return this.color; }
    void setColor(Color c) { this.color = c; }

    // 获取/设置字段引用
    Object getField(String name) { return fields.get(name); }
    void setField(String name, Object ref) {
        // 实际赋值操作会触发写屏障
        fields.put(name, ref);
    }
}

// 假设有一个全局的堆对象列表
List<Object> heap;

// GC 工作队列 (例如 ConcurrentQueue)
Queue<Object> gcWorkQueue;

// 根集 (例如一个列表，实际可能更复杂)
List<Object> roots;

// GC 状态标志
boolean gcMarkingPhaseActive = false;

// 模拟互斥锁，用于保护共享资源（如工作队列或颜色修改）
Lock gcLock;

GC 线程逻辑 (核心扫描函数)：

void GC_MarkLoop() {
    while (gcMarkingPhaseActive || !gcWorkQueue.isEmpty()) {
        Object obj = null;
        gcLock.acquire();
        if (!gcWorkQueue.isEmpty()) {
            obj = gcWorkQueue.poll();
        }
        gcLock.release();

        if (obj == null) {
            // 如果队列为空，GC线程可以短暂休眠或等待通知
            // 在并发模式下，Mutator可能会添加新的灰色对象
            continue;
        }

        // 扫描当前对象的子对象
        for (Object child : obj.fields.values()) {
            if (child != null && child.getColor() == WHITE) {
                child.setColor(GRAY); // 发现白色子对象，染灰
                gcLock.acquire();
                gcWorkQueue.add(child); // 加入工作队列
                gcLock.release();
            }
        }
        obj.setColor(BLACK); // 当前对象扫描完毕，染黑
    }
}

void GC_AddToWorkQueue(Object obj) {
    if (obj != null && obj.getColor() == WHITE) { // 避免重复添加或添加非白色对象
        obj.setColor(GRAY);
        gcLock.acquire();
        gcWorkQueue.add(obj);
        gcLock.release();
    } else if (obj != null && obj.getColor() == BLACK) {
        // 如果黑色对象被屏障染灰，则需要重新加入队列
        // 这一步在某些屏障实现中可能是需要的，但会增加工作量
        // 更常见的是，屏障直接将对象染灰并加入队列，GC_AddToWorkQueue只检查白色
        // 对于Incremental Update，可能需要强制将黑染灰再入队
        // 这里简化为只在白色时入队，屏障负责染灰
    }
}

Mutator 线程的引用赋值操作与写屏障：

1. SATB 写屏障实现：

// Mutator 的引用赋值操作
void Mutator_Assign_SATB(Object obj, String fieldName, Object newRef) {
    Object oldRef = obj.getField(fieldName); // 获取旧值

    // 1. 触发 SATB 预写屏障
    if (gcMarkingPhaseActive) {
        if (oldRef != null && oldRef.getColor() == WHITE) {
            // 保护旧引用指向的对象，将其染灰，确保在GC快照中可达
            GC_AddToWorkQueue(oldRef); // 屏障逻辑调用GC的入队函数
        }
    }

    // 2. 执行实际的赋值
    obj.setField(fieldName, newRef);
}

2. Incremental Update 写屏障实现：

// Mutator 的引用赋值操作
void Mutator_Assign_IncrementalUpdate(Object obj, String fieldName, Object newRef) {
    // 1. 执行实际的赋值
    obj.setField(fieldName, newRef); // 先修改引用

    // 2. 触发 Incremental Update 后写屏障
    if (gcMarkingPhaseActive) {
        if (obj.getColor() == BLACK && newRef != null && newRef.getColor() == WHITE) {
            // 如果源对象是黑色，且新引用指向白色对象，则违反不变式
            // 将新引用指向的对象染灰，使其被GC扫描
            GC_AddToWorkQueue(newRef); // 屏障逻辑调用GC的入队函数
        }
    }
}

GC 启动与运行流程：

void StartConcurrentGC() {
    // 1. 初始标记 (STW)
    gcLock.acquire(); // 全局GC锁，模拟STW
    gcMarkingPhaseActive = true;
    gcWorkQueue.clear();

    for (Object root : roots) {
        GC_AddToWorkQueue(root); // 根对象染灰并入队
    }
    gcLock.release(); // 释放锁，Mutator 恢复

    // 2. 启动并发标记线程
    Thread gcMarkThread = new Thread(() -> GC_MarkLoop());
    gcMarkThread.start();

    // Mutator 线程在此期间并行执行，并触发写屏障

    // 3. 等待并发标记完成 (通常通过GC线程的队列为空判断)
    // 实际系统中，GC_MarkLoop 会周期性检查队列并休眠
    // GC协调器会在某个时间点决定进入Remark阶段
    gcMarkThread.join(); // 简单示例，实际不会join

    // 4. 最终标记/再标记 (STW)
    gcLock.acquire(); // 再次STW
    // 处理剩余灰色对象，或根据屏障类型进行特定扫描
    // 例如，对SATB，可能需要重新扫描根和所有在并发阶段被染灰的对象
    // 对IU，只需确保所有灰色对象都被处理完
    while (!gcWorkQueue.isEmpty()) {
        GC_MarkLoop(); // 再次运行扫描，确保所有灰色都变黑
    }
    gcMarkingPhaseActive = false; // 标记阶段结束
    gcLock.release(); // 释放锁

    // 5. 并发清除 (与Mutator并行)
    // 启动一个或多个GC线程遍历heap，回收所有 WHITE 对象
    // 清除器可以并发运行，不需要STW
    new Thread(() -> {
        for (int i = 0; i < heap.size(); ) {
            Object obj = heap.get(i);
            if (obj.getColor() == WHITE) {
                // 回收对象，例如从heap列表中移除，或标记为可重用
                heap.remove(i);
            } else {
                obj.setColor(WHITE); // 为下一轮GC重置颜色
                i++;
            }
        }
    }).start();
}

请注意，上述伪代码是高度简化的，用于说明核心概念。真实的GC实现会涉及更复杂的并发控制、内存布局、弱引用处理、分代回收、以及更精细的屏障优化（如卡片标记）。

7. 高级考量与未来趋势

• 混合屏障： 像G1这样的现代GC，可能会结合SATB和Incremental Update的优点，使用一种混合屏障策略。例如，SATB用于保护旧代对象的引用更新，而Incremental Update或更轻量级的屏障用于新生代。
• 读屏障 (Read Barrier)： 对于一些更激进的并发GC（如ZGC, Shenandoah），为了实现并发的堆整理或引用更新，可能需要引入读屏障。读屏障在对象引用被读取时触发，确保读取到的引用是最新的、正确的。这比写屏障的开销更大，但能实现更短的STW时间。
• 编译器与运行时协作： 写屏障的插入通常由编译器完成，例如在JVM中，JIT编译器会在字节码级别插入屏障代码。这种紧密的协作对于性能至关重要。
• 无屏障优化： 在某些情况下，如果编译器能够证明某个引用更新不会影响GC的正确性（例如，在一个局部变量中对一个新创建的对象赋值），则可以省略写屏障。

8. 并发GC的价值所在

三色标记结合写屏障的设计，是现代高性能运行时系统（如JVM, Go Runtime, V8 JavaScript Engine）能够提供低延迟、高吞吐量垃圾回收的关键。它将大部分GC工作从STW阶段转移到与应用程序并发执行，从而显著减少了用户可感知的暂停时间。虽然写屏障带来了额外的运行时开销，但在大多数场景下，这种开销被并发GC带来的低延迟优势所抵消，甚至带来整体性能的提升，因为它允许应用程序更长时间地运行而无需长时间停顿。

理解三色标记和写屏障的机制，不仅能帮助我们更深入地理解运行时系统，也为我们在设计和优化高性能应用时提供了宝贵的视角。GC不再是遥远而神秘的黑箱，而是可以被理解和驾驭的精密工程。