三色标记算法：从CMS到G1的并发垃圾回收核心原理

面试官一问到JVM垃圾收集器十有八九会接着问三色标记算法。第一次听到这名字我还以为是某个图形算法后来才发现它和颜色没关系是用来描述垃圾回收过程中对象状态的抽象模型。CMS能用G1能用ZGC也绕不开它。这篇内容就把三色标记算法和垃圾收集器串起来讲清楚它解决什么问题、怎么解决、各收集器怎么落地以及面试和调优时真正要注意的点。适合正在啃JVM面试题的同学也适合给线上服务做GC调优的工程师对照参考。1. 先理清楚垃圾收集器和JVM内存模型的关系1.1 内存分代是垃圾收集的前提聊三色标记光盯着对象图不够得先知道收集器在什么环境里干活。JVM的堆虽然是连续的逻辑内存但在垃圾收集器眼里通常被分成新生代和老年代。新生代里继续拆出Eden区和两块Survivor区绝大多数对象都先出生在Eden老年代更像个“养老区”存放躲过多轮GC、生命周期比较长的对象。为什么要分代最朴素的原因是统计规律绝大多数Java对象都是“朝生夕死”在方法里new出来方法跑完就没人引用它了。如果每次GC都把全堆扫一遍大堆会很吃亏分代之后新生代可以用高频、小范围的Minor GC把大部分垃圾快速处理掉老年代则用低频、较大范围的Major GC回收整体吞吐和延迟都能兼顾。不少朋友喜欢把“垃圾收集器”和“分代模型”混在一起谈其实两者不是一回事。分代是堆空间的规划方式垃圾收集器是在这个规划之上做标记和回收的执行者。三色标记算法恰恰是执行者并发工作时最重要的那张“地图”只有理解了地图再看Serial、CMS、G1这些收集器的差异才不会懵。1.2 收集器家族和它们的分代偏好从实现历史来看JVM里的收集器大致可以分成几个流派。Serial和Parallel是“STW派”标记、清理都要暂停应用线程CMS是“第一代并发派”把耗时的标记阶段和业务线程并行起来G1是“分区派”把堆拆成多个Region兼顾了吞吐和停顿控制ZGC和Shenandoah则把并发标记、并发整理都推到极致是超低延迟场景的选择。我用一张表把这几个典型收集器和三色标记的关系列出来收集器主要应用区域标记方式是否依赖三色标记Serial新生代老年代单线程STW标记不依赖Parallel新生代老年代多线程STW标记不依赖CMS老年代并发标记STW重新标记依赖G1整个堆Region并发标记STW最终标记依赖ZGC整个堆并发标记并发整理依赖但用染色指针改进看到这里你可能会问为什么Serial和Parallel不依赖三色标记因为它们在标记的整个过程中应用线程都停着对象引用关系固定不变从GC Roots出发沿着引用链一遍扫完标记结果就是准确的不需要额外的抽象去处理“并发修改”。而CMS、G1这些并发收集器启动标记后业务线程还在跑引用关系随时可能被改写必须用一套能容忍并发修改的标记模型三色标记就是这样诞生的。2. 三色标记算法到底在说什么2.1 从“全停顿”到“并发标记”要解决的核心矛盾判断一个Java对象是否存活标准做法是可达性分析从GC Roots栈上的局部变量、静态字段、JNI引用等出发把所有能直接或间接引用到的对象都走一遍。这个过程可以理解成遍历一张以对象为节点、以引用为边的有向图。能走到的是存活对象走不到的就可以回收。早先的Serial、Parallel在遍历这张图时会把业务线程全部停掉。STW虽然粗暴但有一个天然好处对象图在标记期间不会变化标记完是什么样就是什么样。坏处也显而易见堆越大标记时间越长停顿越长。线上服务要求响应时间稳定停顿几百毫秒甚至几秒业务根本接受不了。因此CMS和G1选择了并发标记让标记线程和业务线程同时运行。可是问题来了标记线程刚把某个对象标成黑色业务线程马上改一条引用那标记结果还算数吗三色标记算法就是为回答这个“一致性”问题而出现的。2.2 白、灰、黑三种状态的定义三色标记把对象在遍历过程中的状态分成三种。白色对象是“尚未被访问到”的对象标记开始时堆里除了GC Roots之外几乎所有对象都是白色。灰色对象是“已经被访问到、但它直接引用的对象还没全部扫描完”的对象类似遍历队列里正在排队处理的任务。黑色对象则是“这个对象本身及其直接引用到的对象都已经被扫描完”它相当于处理完的任务后续不会再被扫描。这里的颜色只是逻辑概念不是对象头上真的涂了颜色。实现时一般通过标记位、对象头里的Mark Word或者独立的位图来表示我们分析算法时把它们看成三种状态即可。当遍历结束时只有白色对象仍是“从未被确认存活”的它们就是本轮GC回收的候选者。遍历过程也很直白先令所有对象为白色把GC Roots直接引用的对象标记为灰色放入工作队列然后取出一个灰色对象扫描它引用的其他对象把其中仍为白色的对象标记为灰色当前灰色对象的所有引用扫描完成后把它变成黑色重复上面的步骤直到灰色队列为空。2.3 并发标记下最致命的问题漏标三色标记在单线程、全停顿环境下很美好可一旦并发就不一样了。业务线程在并发标记期间会做两件事删掉旧引用、写入新引用。最糟糕的情况是同时发生某个白色对象被标记线程遗漏了但业务线程又给它保留了唯一一条从黑色对象出发的引用链。这样这个白色对象虽然实际上还活着却不会被后续扫描发现最终被当成垃圾回收直接导致业务数据丢失甚至程序崩溃。用个具体例子说明。标记线程已经把对象A扫描完毕A是黑色对象B还没被扫描是白色对象C是灰色当前正好通过引用指向B。这时业务线程执行了两步操作第一步把C到B的引用删除第二步让A新增一个指向B的引用。C后面再被扫描时已经找不到BA又不会再次扫描于是B永远保持白色。这个现象在并发垃圾收集的资料中叫“漏标”是绝对不可接受的。为什么不可接受漏标意味着把活对象当垃圾回收轻则数据丢失重则JVM直接崩溃。相比之下“错标”把已经没人引用的垃圾对象继续当作存活对象虽然会让对象多存活一轮产生所谓的浮动垃圾但至少不会引发致命错误最多牺牲一点回收效率。所以并发收集器的标记阶段核心任务不是追求零错误而是无论如何都不能漏标。3. 两套解决方案增量更新与原始快照3.1 增量更新Incremental UpdateCMS的答案怎么避免漏标最简单的思路是“谁搞脏了谁负责”。既然漏标的根源是黑色对象新增了对白色对象的引用那么在检测到这种写入动作时就把这个黑色对象“退回”成灰色记到一张待处理列表里。等到重新标记阶段再扫描它一遍就能顺着新增引用找到那个白色对象。这个方案叫增量更新CMS老年代收集器用的就是它。实际操作中JVM需要一个写屏障write barrier来拦截“引用写入”这个动作。业务线程往某个黑色对象里写入新引用时写屏障触发把该黑色对象放入脏对象队列。之所以叫“增量更新”是因为它不重新全量扫描对象图而是只扫描被修改过的那些对象尽量把工作量控制在增量范围内。不过要注意黑色对象重新变灰后它引用的白色对象虽然会被标记但如果业务线程又在这条引用链上继续做并发修改重新标记阶段可能还要兜底所以CMS的重新标记阶段需要STW来保证最终一致性。选择增量更新而不是另一种方案有它的历史原因CMS的定位是低延迟它希望尽量少暂停增量更新实现相对直接配合重新标记阶段可以在合理停顿内完成修正。缺点也很明显如果并发期间引用修改非常频繁脏对象列表会很大重新标记阶段就可能拖长。3.2 原始快照Snapshot At The BeginningG1的答案G1换了一条完全不同的思路。它不再去追踪“新增的引用”而是记录“开始时对象图长什么样”。并发标记启动那一刻所有可达对象构成一个逻辑快照之后不管业务线程怎么删引用、怎么改引用G1都只对当前被修改的引用关系做记录并保证快照中可达的对象在本轮标记中至少被标记一次。具体落地上G1使用SATB写屏障。当业务线程删除一个从灰色对象指向某个对象的引用时写屏障会记录下“旧引用指向的目标对象”把这个目标对象继续保留为需要扫描的对象。这么做的妙处是只要对象在并发标记开始时是可达的哪怕后来引用全被删了它也会被标记成存活不会被回收而原本不可达的垃圾对象即使被新增引用指向也可能因此多存活一轮。这就是浮动垃圾的来源之一。G1为什么宁愿要浮动垃圾也不愿用增量更新因为它把堆分成了大量Region增量更新的“重新扫描脏对象”在Region之间会造成很大的扫描负担而SATB只需要维护一组队列在最终标记阶段统一处理整体结构更规整也更适合G1这种分区收集器。代价是浮动垃圾更多所以G1在老年代回收后往往不会一下清得很干净这属于正常现象。3.3 两种方案的区别一目了然我把两种方案放在一张表里面试时如果被问到基本照着这张表答就够维度增量更新原始快照记录时机写入新引用时删除旧引用时记录内容被写入引用的黑色对象脏对象被解除引用的原目标对象对标记结果的影响重新扫描脏对象修正漏标保证快照对象可达多产生浮动垃圾额外工作重新标记阶段扫描脏对象队列最终标记阶段处理SATB队列代表收集器CMSG1、Shenandoah一句话总结这两种方案的区别增量更新盯的是“谁被新增引用了”SATB盯的是“谁被删掉引用了”。都是通过写屏障介入只是记录的方向不一样。理解到这一层后面看CMS和G1的标记流程就不会晕。4. 看具体收集器怎么落地这套算法4.1 CMS初始标记、并发标记、重新标记怎么配合很多人说CMS已经被移除没必要再学。但CMS是把三色标记和增量更新落到实处的典型教材了解它再看G1很顺。CMS处理老年代完整周期一般分成四个主要阶段。首先是初始标记initial mark这个阶段必须STW但它只做两件事枚举GC Roots并把根对象直接引用的对象标记为灰色。停顿很短因为只做了“第一跳”。接下来是并发标记concurrent mark标记线程和应用线程同时运行标记线程从灰色对象出发按三色规则遍历对象图。这个阶段最长但无需STW。再往后是重新标记remark必须STW作用是处理并发标记阶段被增量更新记录下来的脏对象重新扫描它们引用的对象修复可能存在的漏标。最后是并发清理concurrent sweep把不再存活的对象从逻辑上释放。CMS在重新标记之前还有一个常见的参数开关-XX:CMSScavengeBeforeRemark。它的意思是在进入重新标记之前先触发一次Minor GC把新生代里临时对象清掉。这样重新标记阶段需要扫描的引用范围更小STW时间也就更短。如果你看到线上CMS的remark阶段停顿异常先检查这个参数有没有生效往往比盲目调堆大小更有效。4.2 G1的并发标记循环SATB队列与TAMSG1已经把堆拆成大小相等的Region每个Region仍然有Eden、Survivor、Old这样的角色但角色是可以动态变化的。G1的并发标记不是每次Young GC都做而是当老年代占用率达到阈值后由-XX:InitiatingHeapOccupancyPercent默认45%触发。G1的并发标记循环通常分四步初始标记initial mark会和一次Young GC绑定完成Root Scanning并发标记concurrent mark阶段从GC Roots出发并发标记所有可达对象同时SATB队列不断记录并发期间的引用变化最终标记final mark阶段是STW的它把并发阶段积攒的SATB队列全部处理完并统计每个Region的存活对象信息最后是清理阶段包含存活对象统计和可选的部分Region回收。你会发现G1一个完整的并发标记周期完全可以映射到三色标记模型上SATB队列里那些对象本质上是“快照中被删过引用的白色对象”。G1还有一个经常被忽略的机制叫TAMSTop At Mark Start。并发标记开始时每个Region记录下一个顶部指针并发标记期间业务线程新分配的对象都在TAMS指针之上。这些新对象默认当作存活对象处理不会被本轮标记误杀等到下一轮GC再判断它们的真实可达性。这种处理方式也属于“宁可错标不可漏标”的保守策略。4.3 ZGC与Shenandoah三色标记在新时代的延伸ZGC和Shenandoah都主打超低延迟很多朋友觉得它们和三色标记关系不大其实它们也是三色模型只是实现载体变了。ZGC把对象状态直接编码到64位对象指针里用指针中的几个位来表示对象的颜色信息比如Marked0、Marked1、Remapped等等。读屏障在访问对象时根据指针颜色决定下一步动作。这里指针颜色不再是抽象的白灰黑而是具体到寄存器里能看到的数据但逻辑上仍然是“已访问、未访问”的三色变化。Shenandoah则通过Brooks Pointer转发指针配合读屏障实现并发回收标记过程同样基于三色标记。区别在于它的并发整理阶段可以在应用线程运行时搬移对象并且通过读屏障把访问转发到新地址。对大多数应用开发者来说未必需要深入到指针位布局那么底层但理解白灰黑状态在并发下的增量更新、SATB选择能帮你快速定位ZGC/Shenandoah的GC日志异常不至于两眼一抹黑。5. 面试与实战这些细节值得记住5.1 面试高频问答为什么漏标、方案区别怎么答JVM面试题基本绕不开可达性分析、STW、CMS、G1、三色标记这一串。建议面试时别急着背结论先画一张对象引用图把白灰黑标注清楚再现场演一遍“C到B引用被删、A新增引用B”的漏标例子面试官很难不认可。三色标记是什么可以说它是并发标记时描述对象遍历状态的一种抽象模型白色未访问灰色已访问但引用未扫描完黑色已扫描完。为什么并发会漏标漏标需要同时满足两个条件第一黑色对象新增了对某个白色对象的引用第二所有灰色对象到该白色对象的引用都被删除。只要打破任何一个条件就能防漏标。CMS用增量更新把新增引用的黑色对象重新变灰重新标记时再扫G1用SATB记录被删除引用的白色对象保住快照可达对象。区别就一句话增量更新管“新写的引用”SATB管“被删的引用”。答到这里再聊浮动垃圾的取舍已经能算优秀。5.2 调优时遇到Concurrent Mode Failure怎么办CMS一个常见故障是Concurrent Mode Failure。它发生在并发标记或并发清理期间老年代空间不足以容纳新晋升对象CMS只能放弃并发回收退化到Serial Old的Full GC停顿一下飙到数秒。遇到这种情况最直接的有效手段是给老年代多留些余量也就是把触发老年代GC的阈值调低让CMS尽量提前启动。CMS有-XX:CMSInitiatingOccupancyFraction和-XX:UseCMSInitiatingOccupancyOnly两个参数配合使用设置后CMS不会因为动态阈值改变触发点。同时可以适当增加并发标记线程数-XX:ConcGCThreads但要留意线程多了会和业务线程抢CPU不一定总是好事。G1里的类似问题叫Evacuation Failure或者Full GC。G1在转移阶段如果发现某些Region对象没有足够空间放下也会退化成Full GC。排查时别急着调堆大小先看是不是RSet过大、存活率估算不准或者并发标记周期太频繁。必要时可以调节-XX:G1HeapRegionSize、-XX:InitiatingHeapOccupancyPercent但凡是动GC参数每次只改一个变量用A/B对比看日志不要一次改一堆否则问题归属都说不清。5.3 从GC日志里判断标记阶段是否健康看GC日志是最基本的功夫。JDK9以上建议直接使用统一日志参数java -Xlog:gc*:filegc.log:tags,uptime,level -Xlog:gcheapdebug -XX:UseG1GC -jar app.jarG1日志里会看到Concurrent Mark Cycle的字样从Concurrent Mark Cycle开始到Concurrent Mark Cycle结束中间会穿插Concurrent Mark、Concurrent Cleanup等阶段。一个健康的并发标记周期应该平稳推进而且不要和业务高峰抢CPU如果你发现Concurrent Mark阶段耗时越来越长甚至被打断说明并发标记线程工作异常或者对象图已经大到必须调整触发阈值。CMS的日志则会有CMS Initial Mark、CMS-concurrent-mark-start/end、CMS Final Remark这样的记录。重新标记时间拉长优先怀疑脏对象队列过大或新生代残留对象过多前者看增量更新压力后者可以通过CMSScavengeBeforeRemark改善。5.4 我自己踩过的坑和几条实在建议我第一次理解三色标记是在线上CMS频繁Full GC的时候。当时只看到日志里Concurrent Mode Failure完全没把“重新标记耗时变长”和“增量更新脏对象太多”联系起来。后来用工具把脏对象队列长度、remark耗时拉在一起看才发现是业务里有个高并发缓存持续往一个热点对象里写新引用CMS的写屏障被不停触发重新标记阶段要扫一大堆脏对象停顿自然降不下来。换成G1之后SATB模型虽然仍有浮动垃圾但至少重新标记阶段可控问题立刻缓解。这个经历让我养成了一个习惯调GC之前先确认用的是哪套标记模型再决定从哪类日志参数入手。另外JDK9之后CMS被标记为废弃JDK14正式移除不要在JDK11以上的环境里还硬写-XX:UseConcMarkSweepGC跑不起来的。JDK8依然能用JDK11以上默认G1追求超低延迟且堆内存足够大时再考虑ZGC或Shenandoah。GC参数的调整没有银弹理解标记算法会让你更有把握“对症下药”。我自己体会最深的一点是三色标记算法不是面试八股它决定了垃圾收集器在并发环境下能否安全标记。把白灰黑状态、增量更新、SATB这几个概念吃透以后看GC日志、排查Full GC、做收集器选型都会有清晰的方向。如果条件允许你现在就可以打开测试环境的GC日志亲手找一次Concurrent Mark Cycle的完整记录把每个阶段的时间戳对照一遍比背十篇文章都管用。