1. 三色标记算法垃圾回收世界的“交通信号灯”如果你写过Java、Go或者用过一些现代语言的运行时大概率听说过“垃圾回收”Garbage Collection, GC这个词。GC就像程序世界的清洁工自动帮我们回收不再使用的内存避免内存泄漏。但清洁工怎么知道哪些东西是垃圾哪些东西还要用呢这就引出了今天要聊的核心——三色标记算法Tri-color marking。这可以说是现代追踪式垃圾回收器的基石算法理解它你就能看懂很多GC日志里晦涩的停顿、并发标记在忙活什么。简单来说三色标记算法通过给内存中的对象“贴颜色标签”白、灰、黑的方式以一种系统化、无遗漏的逻辑找出所有存活对象。它解决了最基础的“标记-清扫”算法在并发执行时会遇到的致命问题在标记过程中用户程序也称为“Mutator”如果修改了对象引用关系可能会导致存活对象被误删。你可以把它想象成在一个不断有人搬家的城市里程序在运行清洁工GC要准确找出所有空房子垃圾。如果清洁工查看时房子有人对象被引用但查看完离开后住户搬走了引用被删这房子会被正确标记为空。但麻烦的是如果清洁工还没查看这房子住户却从A房搬到了B房引用被改变并且清洁工已经检查过B房了那么B房这个新住户就可能被漏掉被当成空房清理掉程序直接就崩溃了。三色标记及其衍生的读写屏障就是为了应对这种“搬家”情况而设计的“交通规则”。2. 核心原理与抽象状态机三色标记的本质是一个状态机它抽象了垃圾回收器对对象图的遍历过程。这里的“对象图”可以理解为内存中所有对象通过引用关系连接成的一张巨大的网。算法的目标是从一组确定的根对象如全局变量、栈上的局部变量等出发找到所有能被触及到的对象剩下的就是垃圾。2.1 三种颜色的定义与状态转移颜色的定义非常直观反映了对象在标记过程中的探索状态白色White表示“尚未访问”。在垃圾回收周期开始时所有对象都被初始化为白色。这意味着回收器还没有检查过它们它们的生死未卜。在标记结束时仍然为白色的对象就被判定为不可达即垃圾等待被回收。灰色Gray表示“已访问但其引用的子对象尚未全部检查”。灰色对象是标记过程的“前沿”或“工作集”。回收器知道这个对象是存活的从根可达但它所指向的其他对象它的字段、数组元素等还没有被扫描。灰色对象是待处理的任务。黑色Black表示“已访问且其引用的所有子对象也已被检查”。黑色对象是已经完成扫描的存活对象。回收器确信从黑色对象出发不会直接引用到白色对象注意这里说的是“直接引用”并发环境下需要屏障保证。整个标记过程就是对象颜色从白 - 灰 - 黑的状态转移过程。这个状态机必须遵守两个核心不变式Invariants这是算法正确性的根基强三色不变式黑色对象绝对不能直接引用白色对象。弱三色不变式黑色对象可以引用白色对象但前提是存在灰色对象作为中间人处于到该白色对象的可达路径上。强不变式是保证不会漏标垃圾的充分条件但比较严格。弱不变式则放宽了条件允许黑引用白只要存在灰色“保护”即可。大部分并发标记算法如CMS、G1的部分阶段维护的是弱三色不变式因为它对并发修改的限制更少性能更好。如何维护这些不变式答案就是屏障技术Barrier我们后面会详细讲。2.2 标记过程的步骤拆解让我们抛开并发先看一个最简单的、停顿式的三色标记流程这有助于建立直觉初始标记Initial Marking暂停所有应用线程Stop-The-World, STW。将所有的根对象GC Roots直接标记为灰色放入一个灰色对象栈或队列中。此时堆中除根对象外的所有对象都是白色。并发标记/标记传播Concurrent Marking / Mark Propagation这是一个循环处理灰色对象的过程直到灰色集合为空。从灰色集合中取出一个对象例如对象A。扫描对象A的所有引用字段。对于它引用的每一个对象例如对象B、C如果被引用的对象是白色则将其颜色改为灰色并放入灰色集合。这相当于发现了新的待探索区域。如果被引用的对象已经是灰色或黑色则无需处理。对象A的所有引用扫描完毕后将其颜色从灰色改为黑色。这表示对象A处理完毕。重复此过程直到灰色集合为空。标记终止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设计上的权衡。SATBDijkstra更关注“不丢对象”安全性极高适合追求低延迟、容忍更多浮动垃圾的场景。增量更新Yuasa则更追求标记精度但需要最终的重扫描可能带来稍长的停顿。现代GC如ZGC和Shenandoah采用了更复杂的读屏障或混合屏障来追求亚毫秒级的停顿。3.2 读屏障Read Barrier读屏障是在对象引用字段读取操作前后插入的片段。它不如写屏障常见但在一些“移动式”回收器如复制、整理中至关重要用于解决“对象被移动后旧地址的访问”问题。在并发标记中它也可以用于维护不变式。核心操作当线程读取一个引用时ref obj.field屏障会检查该引用是否指向一个“已转发”或“待处理”的对象如果是则可能返回新地址或触发标记操作。应用场景在Shenandoah和ZGC这类几乎全并发的回收器中读屏障被大量使用。例如ZGC使用读屏障来染色指针在加载引用时检查元数据位如果发现对象正在被转移或需要标记则触发相应的处理程序从而实现了并发转移和并发标记。屏障的性能开销无论是写屏障还是读屏障都是在每一条指针读写操作上增加的额外指令虽然每条指令开销很小但累积起来对整体程序性能有可观测的影响通常认为是几个百分点到十个百分点。因此GC算法的演进很大程度上是在设计更精巧、开销更低的屏障。4. 算法在主流GC中的实现与演进三色标记不是一个孤立的算法而是嵌入在各种GC收集器中的核心步骤。我们来看几个典型例子4.1 在CMS收集器中的应用CMSConcurrent Mark-Sweep是HotSpot JVM中老年代的一个经典并发低延迟收集器。它的标记过程清晰地体现了三色标记和写屏障的应用初始标记Initial Mark STW仅标记GC Roots直接关联的对象速度极快。这些对象被标记为灰色。并发标记Concurrent MarkGC线程与用户线程并发执行。从初始标记的灰色对象开始遍历老年代对象图。此阶段使用增量更新写屏障。用户线程修改引用时如果符合条件黑引用白屏障会将白色对象置灰。重新标记Remark STW由于并发标记期间用户线程还在运行需要修正标记结果。这个阶段会暂停应用重新扫描一部分对象主要是从并发标记开始后发生变化的对象以及根集合处理那些在并发阶段因屏障而新产生的灰色对象确保标记完整。这是为了弥补增量更新屏障需要最终重扫描的特点。并发清除Concurrent Sweep回收白色垃圾对象占用的空间。CMS的问题在于它使用增量更新屏障重新标记阶段虽然比Full GC短但依然可能产生不可预测的停顿。并且它无法处理“并发失败”和空间碎片问题。4.2 在G1收集器中的演进G1Garbage-First采用了分区模型和更复杂的标记策略。初始标记Initial Mark STW同CMS标记GC Roots直达的对象。这个阶段通常与一次年轻代GCYoung GC捆绑进行借后者的根扫描结果性价比高。根区域扫描Root Region Scanning扫描在初始标记阶段被标记为“根区域”的幸存者区Survivor找出它们对老年代的引用。这个阶段是并发的。并发标记Concurrent Marking在整个堆中并发地进行可达性分析。G1在此阶段主要使用SATB写屏障。用户线程在覆盖引用时会将旧引用记录到一个线程本地的缓冲区满了之后放入全局队列。并发标记线程会定期处理这些队列将其中记录的旧引用对象标记为灰色。最终标记Final Marking STW处理剩余的SATB缓冲区并执行类卸载等收尾工作。由于SATB屏障的特性这个阶段通常比CMS的重新标记更快、更稳定。筛选回收Live Data Counting and Evacuation STW根据标记结果计算出各个区域的存活对象比例和回收价值选择若干区域进行复制清理。G1通过SATB屏障和区域化提供了比CMS更可预测的停顿时间模型。4.3 在ZGC/Shenandoah中的革命ZGC和Shenandoah将并发性推向了极致目标是将STW停顿控制在10毫秒甚至1毫秒以下。它们的关键创新之一就是染色指针和负载屏障。染色指针将对象的元数据如标记位、转发状态存储在指针本身的高位中而不是对象头里。这使得GC线程在移动对象时无需修改所有指向该对象的引用只需修改对象本身和少数元数据。负载屏障读屏障当应用程序线程通过指针加载对象时屏障代码会检查指针中的元数据位。如果发现对象正在被转移或需要标记则屏障会“拦截”这次访问可能完成转移操作或者更新标记状态然后返回正确的引用。以ZGC为例其并发标记阶段标记开始时所有对象指针的标记位为0可视为白色。GC线程并发遍历对象图将存活对象的指针标记位置1可视为黑色/灰色。这个操作是原子性的直接在指针上完成。用户线程在加载引用时读屏障会检查标记位。如果发现对象存活但标记位为0即GC线程刚标记完但用户线程还没看到屏障可能会帮助完成标记或者确保线程看到一致的视图。由于标记信息在指针上标记阶段不需要修改对象头减少了缓存行竞争提升了并发效率。在这里三色标记的状态白、灰、黑被编码到了指针的比特位中通过读屏障来保证并发下的视图一致性完全摒弃了传统写屏障在并发标记阶段的大部分工作实现了更高的并发度。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 常见问题与调优策略并发模式失败 / 晋升失败现象在CMS或G1中老年代并发回收还未完成空间已被填满或者年轻代对象晋升时老年代没有足够碎片空间。日志出现concurrent mode failure或to-space exhausted随后触发长时间的Full GC。排查与调优增加堆大小最直接的方法给并发回收更多时间窗口。调整触发阈值例如让CMS更早启动-XX:CMSInitiatingOccupancyFraction如设为60%。让G1更积极地进行混合回收。优化分配速率检查代码是否存在大量短命大对象或分配热点优化其生命周期或使用对象池。减少对象持有避免不必要的全局或长时间引用让对象尽快死亡。最终标记停顿时间过长现象G1的remark阶段停顿远超预期如10ms。排查使用-XX:PrintReferenceGC查看引用处理耗时。使用-XX:G1SummarizeRSetStats查看记忆集优化情况。调优增大SATB缓冲区-XX:G1SATBBufferSize增加每个线程的缓冲区大小减少全局队列的同步压力。调整并行线程数-XX:ConcGCThreads增加并发标记线程数但需平衡CPU资源。减少内存修改这是根本。检查是否有频繁更新的全局数据结构考虑使用并发容器或减少更新频率。堆内存碎片化现象老年代使用率不高但无法找到连续空间分配大对象触发Full GC。调优切换到有整理功能的收集器如G1、ZGC、Shenandoah。G1虽然整体是标记-复制但只在回收集合内整理。调整GC参数在CMS中可以启用压缩-XX:UseCMSCompactAtFullCollection并在一定次数后强制压缩-XX:CMSFullGCsBeforeCompaction。屏障带来的额外开销现象应用吞吐量有可感知的下降几个百分点。排查使用-XX:PrintGC和-XX:PrintGCDetails观察GC频率和耗时是否正常。使用性能剖析工具如Async-Profiler查看热点是否有很多屏障相关的代码如write_barrier。理解这是为低延迟付出的代价。通常无法彻底消除但可以通过选择更高效的GC器来降低。例如从CMS切换到G1或ZGC可能会因为算法优化而降低总体屏障开销。5.3 内存泄漏的排查思路三色标记算法本身是准确的但如果存在内存泄漏即对象逻辑上已无用但仍有引用可达GC会认为它们是存活的黑色无法回收。排查此类问题三色标记的概念能帮你理解堆转储分析获取堆转储使用jmap -dump:live,formatb,fileheap.hprof或通过OOM自动生成。使用分析工具MATEclipse Memory Analyzer、JProfiler等。分析支配树与GC Roots在MAT中查找占用内存最大的对象。查看其“Path to GC Roots” - “exclude weak/soft references”。这条引用链就是阻止它被回收的“罪魁祸首”。常见的泄漏源包括未关闭的集合如静态Map、监听器未注销、线程局部变量未清理、第三方库的资源未释放等。结合代码审查根据分析工具找到的引用链定位到业务代码检查对象生命周期管理是否正确。理解三色标记让你在看这些引用链时能清晰地知道链上的每一个对象在GC眼中都是“黑色”的存活对象链的起点就是GC Roots。你的任务就是找出那个本应断开却未断开的错误引用。