首页/资讯中心/详情

三色标记算法：现代垃圾回收的并发标记核心原理与屏障技术

三色标记算法：现代垃圾回收的并发标记核心原理与屏障技术
📅 发布时间：2026/8/2 4:14:57

1. 三色标记算法：垃圾回收世界的“交通信号灯”

如果你写过Java、Go或者用过一些现代语言的运行时，大概率听说过“垃圾回收”（Garbage Collection, GC）这个词。GC就像程序世界的清洁工，自动帮我们回收不再使用的内存，避免内存泄漏。但清洁工怎么知道哪些东西是垃圾，哪些东西还要用呢？这就引出了今天要聊的核心——三色标记算法（Tri-color marking）。这可以说是现代追踪式垃圾回收器的基石算法，理解它，你就能看懂很多GC日志里晦涩的停顿、并发标记在忙活什么。

简单来说，三色标记算法通过给内存中的对象“贴颜色标签”（白、灰、黑）的方式，以一种系统化、无遗漏的逻辑，找出所有存活对象。它解决了最基础的“标记-清扫”算法在并发执行时会遇到的致命问题：在标记过程中，用户程序（也称为“Mutator”）如果修改了对象引用关系，可能会导致存活对象被误删。你可以把它想象成在一个不断有人搬家的城市里（程序在运行），清洁工（GC）要准确找出所有空房子（垃圾）。如果清洁工查看时房子有人（对象被引用），但查看完离开后，住户搬走了（引用被删），这房子会被正确标记为空。但麻烦的是，如果清洁工还没查看这房子，住户却从A房搬到了B房（引用被改变），并且清洁工已经检查过B房了，那么B房这个新住户就可能被漏掉，被当成空房清理掉，程序直接就崩溃了。三色标记及其衍生的读写屏障，就是为了应对这种“搬家”情况而设计的“交通规则”。

2. 核心原理与抽象状态机

三色标记的本质是一个状态机，它抽象了垃圾回收器对对象图的遍历过程。这里的“对象图”可以理解为内存中所有对象通过引用关系连接成的一张巨大的网。算法的目标是从一组确定的根对象（如全局变量、栈上的局部变量等）出发，找到所有能被触及到的对象，剩下的就是垃圾。

2.1 三种颜色的定义与状态转移

颜色的定义非常直观，反映了对象在标记过程中的探索状态：

  • 白色（White）：表示“尚未访问”。在垃圾回收周期开始时，所有对象都被初始化为白色。这意味着回收器还没有检查过它们，它们的生死未卜。在标记结束时，仍然为白色的对象，就被判定为不可达，即垃圾，等待被回收。
  • 灰色（Gray）：表示“已访问，但其引用的子对象尚未全部检查”。灰色对象是标记过程的“前沿”或“工作集”。回收器知道这个对象是存活的（从根可达），但它所指向的其他对象（它的字段、数组元素等）还没有被扫描。灰色对象是待处理的任务。
  • 黑色（Black）：表示“已访问，且其引用的所有子对象也已被检查”。黑色对象是已经完成扫描的存活对象。回收器确信，从黑色对象出发，不会直接引用到白色对象（注意：这里说的是“直接引用”，并发环境下需要屏障保证）。

整个标记过程，就是对象颜色从白 -> 灰 -> 黑的状态转移过程。这个状态机必须遵守两个核心不变式（Invariants），这是算法正确性的根基：

  1. 强三色不变式：黑色对象绝对不能直接引用白色对象。
  2. 弱三色不变式：黑色对象可以引用白色对象，但前提是存在灰色对象作为中间人，处于到该白色对象的可达路径上。

强不变式是保证不会漏标垃圾的充分条件，但比较严格。弱不变式则放宽了条件，允许黑引用白，只要存在灰色“保护”即可。大部分并发标记算法（如CMS、G1的部分阶段）维护的是弱三色不变式，因为它对并发修改的限制更少，性能更好。如何维护这些不变式？答案就是屏障技术（Barrier），我们后面会详细讲。

2.2 标记过程的步骤拆解

让我们抛开并发，先看一个最简单的、停顿式的三色标记流程，这有助于建立直觉：

  1. 初始标记（Initial Marking）：

    • 暂停所有应用线程（Stop-The-World, STW）。
    • 将所有的根对象（GC Roots）直接标记为灰色，放入一个灰色对象栈或队列中。
    • 此时，堆中除根对象外的所有对象都是白色。

  2. 并发标记/标记传播（Concurrent Marking / Mark Propagation）：

    • 这是一个循环处理灰色对象的过程，直到灰色集合为空。
    • 从灰色集合中取出一个对象（例如，对象A）。
    • 扫描对象A的所有引用字段。对于它引用的每一个对象（例如，对象B、C）：
      • 如果被引用的对象是白色，则将其颜色改为灰色，并放入灰色集合。这相当于发现了新的待探索区域。
      • 如果被引用的对象已经是灰色或黑色，则无需处理。
    • 对象A的所有引用扫描完毕后，将其颜色从灰色改为黑色。这表示对象A处理完毕。
    • 重复此过程，直到灰色集合为空。

  3. 标记终止（Mark Termination）：

    • 当灰色集合为空时，标记阶段结束。
    • 此时，所有存活对象都已被标记为黑色，所有垃圾对象仍然是白色。
    • 随后的清扫（Sweep）或整理（Compact）阶段，就可以安全地回收白色对象所占用的内存了。

这个过程就像一滴墨水滴入清水，从根节点（灰色）开始，颜色逐渐向四周扩散（灰色传播），被完全浸染的区域变为黑色，最终未被浸染的白色区域就是孤立的垃圾。

注意：这个简单流程是“停顿式”的，即标记期间不允许用户程序运行。现代GC追求低延迟，核心挑战就在于如何实现“并发标记”，即让标记线程和用户线程同时运行。一旦并发，不变式就可能被破坏，这就需要引入“屏障”这个关键机制。

3. 并发环境下的挑战与屏障技术

在并发标记阶段，用户线程（Mutator）也在同时修改对象图，这会导致前面提到的“搬家”问题，破坏三色不变式，从而产生两种致命错误：

  • 浮动垃圾（Floating Garbage）：对象已经死了（应标为白），但被误标为黑。这没关系，只是本次GC没回收，下次回收即可。属于可以容忍的“精度”问题。
  • 对象丢失（Object Loss）：对象还活着（应标为黑），却被误标为白，导致被回收。这是绝对致命的错误，必须避免。

对象丢失的典型场景就是“写入屏障”要解决的“增量更新”或“删除引用”问题。假设我们有黑对象A引用白对象B，灰对象C引用白对象D。用户线程执行了A.field = D（将黑对象A的引用指向白对象D），同时删除了C.field = D。此时，从根到D的唯一路径（C->D）被切断，而新路径（A->D）因为A是黑色，不会被重新扫描，导致D永远保持白色，最终被回收。

为了在并发下维护弱三色不变式，垃圾回收器在编译代码或解释器执行时，插入一些额外的指令，这些指令就是屏障（Barrier）。它们像哨兵一样，在用户线程修改引用时进行拦截和记录，确保GC的正确性。主要有两种屏障：

3.1 写屏障（Write Barrier）

写屏障是在对象引用字段写入（赋值）操作前后插入的片段。它是解决并发标记问题的核心。根据维护不变式的策略不同，主要有两种经典实现：

  • Dijkstra插入屏障（Snapshot-In-The-Beginning, SATB风格）：

    • 核心思想：关注引用关系的删除。它试图保留“标记开始那一刻”的对象图快照。所有在标记开始时存活的对象，最终都会被标记。
    • 屏障操作：当要写入一个引用时（*slot = new_ref），无论新引用是什么，都将原引用（old_ref）标记为灰色（如果它是白色）。void dijikstra_write_barrier(void* slot, void* new_ref) { if (is_white(old_ref)) { set_gray(old_ref); // 关注被覆盖的旧引用 } *slot = new_ref; }
    • 原理：通过保护可能被删除的引用（旧值），确保任何在快照中存活的对象都不会被漏掉。即使这个对象后来变得不可达，它也会被标记为灰色进而变黑，成为本次GC的浮动垃圾，但绝不会被误回收。G1和Shenandoah GC的初始标记阶段使用了类似SATB的屏障。
    • 优点：不需要对黑色对象进行重新扫描。
    • 缺点：会产生更多的浮动垃圾。

  • Yuasa删除屏障（Incremental Update风格）：

    • 核心思想：关注引用关系的插入。它维护“标记结束那一刻”的对象图。所有在标记结束时存活的对象，都必须被标记。
    • 屏障操作：当要写入一个引用，且写入者是黑色对象时（black_obj.field = white_ref），将新引用的白色对象（white_ref）标记为灰色。void yuasa_write_barrier(void* obj, void* field, void* new_ref) { if (is_black(obj) && is_white(new_ref)) { set_gray(new_ref); // 关注新插入的引用 } *field = new_ref; }
    • 原理：当黑色对象（已扫描完）试图引用一个白色对象时，屏障会介入，把这个白色对象“推”进灰色集合，保证它会被后续扫描到。这维护了“强三色不变式”的一个变体。
    • 优点：浮动垃圾相对较少。
    • 缺点：因为黑色对象可能重新引用白色，所以标记结束后需要重新扫描一次根集合（Rescan Roots），以确保所有新产生的灰色对象被处理。CMS GC的并发标记阶段就使用了类似增量更新的屏障。

实操心得：选择哪种屏障，是GC设计上的权衡。SATB（Dijkstra）更关注“不丢对象”，安全性极高，适合追求低延迟、容忍更多浮动垃圾的场景。增量更新（Yuasa）则更追求标记精度，但需要最终的重扫描，可能带来稍长的停顿。现代GC如ZGC和Shenandoah，采用了更复杂的读屏障或混合屏障来追求亚毫秒级的停顿。

3.2 读屏障（Read Barrier）

读屏障是在对象引用字段读取操作前后插入的片段。它不如写屏障常见，但在一些“移动式”回收器（如复制、整理）中至关重要，用于解决“对象被移动后，旧地址的访问”问题。在并发标记中，它也可以用于维护不变式。

  • 核心操作：当线程读取一个引用时（ref = obj.field），屏障会检查该引用是否指向一个“已转发”或“待处理”的对象，如果是，则可能返回新地址或触发标记操作。
  • 应用场景：在Shenandoah和ZGC这类几乎全并发的回收器中，读屏障被大量使用。例如，ZGC使用读屏障来染色指针，在加载引用时检查元数据位，如果发现对象正在被转移或需要标记，则触发相应的处理程序，从而实现了并发转移和并发标记。

屏障的性能开销：无论是写屏障还是读屏障，都是在每一条指针读写操作上增加的额外指令，虽然每条指令开销很小，但累积起来对整体程序性能有可观测的影响（通常认为是几个百分点到十个百分点）。因此，GC算法的演进，很大程度上是在设计更精巧、开销更低的屏障。

4. 算法在主流GC中的实现与演进

三色标记不是一个孤立的算法，而是嵌入在各种GC收集器中的核心步骤。我们来看几个典型例子：

4.1 在CMS收集器中的应用

CMS（Concurrent Mark-Sweep）是HotSpot JVM中老年代的一个经典并发低延迟收集器。它的标记过程清晰地体现了三色标记和写屏障的应用：

  1. 初始标记（Initial Mark， STW）：仅标记GC Roots直接关联的对象，速度极快。这些对象被标记为灰色。
  2. 并发标记（Concurrent Mark）：GC线程与用户线程并发执行。从初始标记的灰色对象开始，遍历老年代对象图。此阶段使用增量更新写屏障。用户线程修改引用时，如果符合条件（黑引用白），屏障会将白色对象置灰。
  3. 重新标记（Remark， STW）：由于并发标记期间用户线程还在运行，需要修正标记结果。这个阶段会暂停应用，重新扫描一部分对象（主要是从并发标记开始后发生变化的对象，以及根集合），处理那些在并发阶段因屏障而新产生的灰色对象，确保标记完整。这是为了弥补增量更新屏障需要最终重扫描的特点。
  4. 并发清除（Concurrent Sweep）：回收白色（垃圾）对象占用的空间。

CMS的问题在于，它使用增量更新屏障，重新标记阶段虽然比Full GC短，但依然可能产生不可预测的停顿。并且它无法处理“并发失败”和空间碎片问题。

4.2 在G1收集器中的演进

G1（Garbage-First）采用了分区模型和更复杂的标记策略。

  1. 初始标记（Initial Mark， STW）：同CMS，标记GC Roots直达的对象。这个阶段通常与一次年轻代GC（Young GC）捆绑进行，借后者的根扫描结果，性价比高。
  2. 根区域扫描（Root Region Scanning）：扫描在初始标记阶段被标记为“根区域”的幸存者区（Survivor），找出它们对老年代的引用。这个阶段是并发的。
  3. 并发标记（Concurrent Marking）：在整个堆中并发地进行可达性分析。G1在此阶段主要使用SATB写屏障。用户线程在覆盖引用时，会将旧引用记录到一个线程本地的缓冲区，满了之后放入全局队列。并发标记线程会定期处理这些队列，将其中记录的旧引用对象标记为灰色。
  4. 最终标记（Final Marking， STW）：处理剩余的SATB缓冲区，并执行类卸载等收尾工作。由于SATB屏障的特性，这个阶段通常比CMS的重新标记更快、更稳定。
  5. 筛选回收（Live Data Counting and Evacuation， STW）：根据标记结果，计算出各个区域的存活对象比例和回收价值，选择若干区域进行复制清理。

G1通过SATB屏障和区域化，提供了比CMS更可预测的停顿时间模型。

4.3 在ZGC/Shenandoah中的革命

ZGC和Shenandoah将并发性推向了极致，目标是将STW停顿控制在10毫秒甚至1毫秒以下。它们的关键创新之一就是染色指针和负载屏障。

  • 染色指针：将对象的元数据（如标记位、转发状态）存储在指针本身的高位中，而不是对象头里。这使得GC线程在移动对象时，无需修改所有指向该对象的引用，只需修改对象本身和少数元数据。
  • 负载屏障（读屏障）：当应用程序线程通过指针加载对象时，屏障代码会检查指针中的元数据位。如果发现对象正在被转移或需要标记，则屏障会“拦截”这次访问，可能完成转移操作，或者更新标记状态，然后返回正确的引用。

以ZGC为例，其并发标记阶段：

  1. 标记开始时，所有对象指针的标记位为0（可视为白色）。
  2. GC线程并发遍历对象图，将存活对象的指针标记位置1（可视为黑色/灰色）。这个操作是原子性的，直接在指针上完成。
  3. 用户线程在加载引用时，读屏障会检查标记位。如果发现对象存活但标记位为0（即GC线程刚标记完，但用户线程还没看到），屏障可能会帮助完成标记，或者确保线程看到一致的视图。
  4. 由于标记信息在指针上，标记阶段不需要修改对象头，减少了缓存行竞争，提升了并发效率。

在这里，三色标记的状态（白、灰、黑）被编码到了指针的比特位中，通过读屏障来保证并发下的视图一致性，完全摒弃了传统写屏障在并发标记阶段的大部分工作，实现了更高的并发度。

5. 实践中的问题排查与调优思路

理解了原理，我们来看如何应对实际问题。GC日志是你的第一手资料。

5.1 从GC日志识别标记阶段

以HotSpot JVM的G1 GC日志为例（添加-Xlog:gc*或-XX:+PrintGCDetails）：

[GC pause (G1 Evacuation Pause) (young) (initial-mark), 0.0052343 secs] // 初始标记，伴随Young GC ... [GC concurrent-root-region-scan-start] // 并发根区域扫描开始 [GC concurrent-root-region-scan-end, 0.0002345 secs] [GC concurrent-mark-start] // 并发标记开始 [GC concurrent-mark-end, 0.1256789 secs] // 并发标记耗时 [GC remark [Finalize Marking, 0.0001456 secs] ... [GC ref-proc, 0.0000876 secs] ... , 0.0012345 secs] // 最终标记（STW） [GC cleanup ... , 0.0004567 secs]
  • 关注点：
    • concurrent-mark阶段的耗时：如果这个时间非常长，说明堆内存大或对象图复杂，并发标记跟不上分配速度，可能导致“并发模式失败”，退化为Full GC。
    • remark阶段的耗时：这是必须的STW停顿。如果时间过长，可能意味着并发标记阶段应用修改的对象非常多（“脏”页多），SATB缓冲区队列处理量大。优化方向是减少不必要的内存写入。

5.2 常见问题与调优策略

  1. 并发模式失败 / 晋升失败：

    • 现象：在CMS或G1中，老年代并发回收还未完成，空间已被填满，或者年轻代对象晋升时老年代没有足够碎片空间。
    • 日志：出现concurrent mode failure或to-space exhausted，随后触发长时间的Full GC。
    • 排查与调优：
      • 增加堆大小：最直接的方法，给并发回收更多时间窗口。
      • 调整触发阈值：例如，让CMS更早启动（-XX:CMSInitiatingOccupancyFraction，如设为60%）。让G1更积极地进行混合回收。
      • 优化分配速率：检查代码是否存在大量短命大对象或分配热点，优化其生命周期或使用对象池。
      • 减少对象持有：避免不必要的全局或长时间引用，让对象尽快死亡。

  2. 最终标记停顿时间过长：

    • 现象：G1的remark阶段停顿远超预期（如>10ms）。
    • 排查：使用-XX:+PrintReferenceGC查看引用处理耗时。使用-XX:+G1SummarizeRSetStats查看记忆集优化情况。
    • 调优：
      • 增大SATB缓冲区：-XX:G1SATBBufferSize增加每个线程的缓冲区大小，减少全局队列的同步压力。
      • 调整并行线程数：-XX:ConcGCThreads增加并发标记线程数，但需平衡CPU资源。
      • 减少内存修改：这是根本。检查是否有频繁更新的全局数据结构，考虑使用并发容器或减少更新频率。

  3. 堆内存碎片化：

    • 现象：老年代使用率不高，但无法找到连续空间分配大对象，触发Full GC。
    • 调优：
      • 切换到有整理功能的收集器：如G1、ZGC、Shenandoah。G1虽然整体是标记-复制，但只在回收集合内整理。
      • 调整GC参数：在CMS中，可以启用压缩（-XX:+UseCMSCompactAtFullCollection）并在一定次数后强制压缩（-XX:CMSFullGCsBeforeCompaction）。

  4. 屏障带来的额外开销：

    • 现象：应用吞吐量有可感知的下降（几个百分点）。
    • 排查：使用-XX:+PrintGC和-XX:+PrintGCDetails观察GC频率和耗时是否正常。使用性能剖析工具（如Async-Profiler）查看热点，是否有很多屏障相关的代码（如write_barrier）。
    • 理解：这是为低延迟付出的代价。通常无法彻底消除，但可以通过选择更高效的GC器来降低。例如，从CMS切换到G1或ZGC，可能会因为算法优化而降低总体屏障开销。

5.3 内存泄漏的排查思路

三色标记算法本身是准确的，但如果存在内存泄漏（即对象逻辑上已无用，但仍有引用可达），GC会认为它们是存活的（黑色），无法回收。排查此类问题，三色标记的概念能帮你理解堆转储分析：

  1. 获取堆转储：使用jmap -dump:live,format=b,file=heap.hprof或通过OOM自动生成。
  2. 使用分析工具：MAT（Eclipse Memory Analyzer）、JProfiler等。
  3. 分析支配树与GC Roots：在MAT中，查找占用内存最大的对象。查看其“Path to GC Roots” -> “exclude weak/soft references”。这条引用链就是阻止它被回收的“罪魁祸首”。常见的泄漏源包括：未关闭的集合（如静态Map）、监听器未注销、线程局部变量未清理、第三方库的资源未释放等。
  4. 结合代码审查：根据分析工具找到的引用链，定位到业务代码，检查对象生命周期管理是否正确。

理解三色标记，让你在看这些引用链时，能清晰地知道，链上的每一个对象，在GC眼中都是“黑色”的存活对象，链的起点就是GC Roots。你的任务就是找出那个本应断开却未断开的错误引用。