三色标记算法是什么？并发标记为什么会漏标？SATB 和增量更新有什么区别？

简化版

三色标记是并发 GC 的核心标记算法，把对象按标记状态分白（未访问）、灰（自己被访问但引用还没扫完）、黑（自己和引用都扫完） 三色。GC 从 GC Roots 出发把可达对象逐步染黑，最后剩下的白色就是垃圾。问题出在并发标记——标记的同时业务线程还在改引用，可能把「本该存活的对象」误判成垃圾（漏标）。漏标只在两个条件同时满足时发生。解决靠写屏障：CMS 用「增量更新」（记录新增的黑→白引用），G1 用「SATB」（记录被删除的引用，保留标记开始时的快照）。

详细版

三色定义：

颜色	含义
白	还没被 GC 访问过；标记结束仍为白 = 垃圾
灰	自己被访问了，但它引用的对象还没全部扫描完（正在处理）
黑	自己被访问了，且它引用的对象都已扫描完（安全，不会再看它）

标记过程：GC Roots 直接引用的对象先变灰 → 逐个处理灰色对象（扫描它的引用，把引用的白对象变灰，自己变黑）→ 直到没有灰色 → 剩下的白色回收。

漏标问题（并发标记时业务线程改引用导致存活对象被误回收）——必须同时满足两个条件：

条件1：某个黑色对象，新增了一条指向白色对象的引用（黑 → 白）
条件2：所有从灰色对象到该白色对象的引用都被删除了
两个条件同时成立 → 白对象没有任何"灰色路径"能到达，
                    黑对象又不会被重新扫描 → 白对象被漏标 → 误当垃圾回收（对象消失，程序出错）

两种解决方案（都靠写屏障在引用变化时记录）：

方案	破坏哪个条件	记录什么	谁用
增量更新（Incremental Update）	破坏条件1	黑对象新增指向白对象的引用时，记下这个「黑对象」，重新扫它	CMS
SATB（Snapshot At The Beginning）	破坏条件2	引用被删除时，记下「被删除的白对象」，视为存活	G1

⚠️ SATB 保留「标记开始那一刻的快照」——只要在标记开始时可达，本轮就当它活着，哪怕标记期间真的变成垃圾了（这叫浮动垃圾，留到下次 GC 回收）。这是「宁可错留、不可错删」的保守策略，用一点浮动垃圾换正确性。

完整版教学

一、为什么需要三色：并发标记的诉求

老式 GC 标记阶段要 STW（Stop The World）——暂停所有业务线程，慢慢标记，标记完再恢复。堆大了这个停顿就长得无法接受（几秒）。现代 GC（CMS、G1、ZGC）想让标记和业务线程并发跑，减少停顿。

但并发标记有个根本矛盾：GC 一边标记，业务线程一边改引用，标记到一半的「世界」在不断变化。三色标记就是为了在这种「动态变化的对象图」里，清晰地追踪「哪些扫过了、哪些正在扫、哪些还没扫」。三种颜色本质是给标记进度打的三个状态标签，让 GC 能增量地、可中断地推进标记。

二、三色标记的推进过程

用一个对象图走一遍。假设 Roots 直接引用 A，A→B，B→C：

初始：A B C 全白，Roots→A
① 把 Roots 直接引用的 A 变灰：      A(灰) B(白) C(白)
② 处理灰色 A：扫描 A 的引用(→B)，
   把 B 变灰，A 自己变黑：           A(黑) B(灰) C(白)
③ 处理灰色 B：扫描 B 的引用(→C)，
   把 C 变灰，B 变黑：              A(黑) B(黑) C(灰)
④ 处理灰色 C：C 没有引用，直接变黑： A(黑) B(黑) C(黑)
⑤ 没有灰色了 → 标记结束 → 白色(无)回收

规律：灰色是「工作队列」——GC 不断从灰色集合取对象处理，处理完变黑，把它引用的白对象变灰入队。当灰色集合空了，标记就完成了。黑色对象 GC 认为「已彻底处理，不会再看」——这个「不再看黑色」的假设，正是漏标的隐患来源。

三、漏标：两个条件缺一不可

并发标记时业务线程改引用，可能造成两类错误：多标（本是垃圾却被标活）和漏标（本该活却被标死）。多标只产生浮动垃圾（下次回收，无害）；漏标是致命的——存活对象被当垃圾回收，程序会访问到已释放的内存，直接出错。

漏标必须两个条件同时成立，用数字场景看清：

标记进行中：A 已黑（扫完了），B 还灰，白对象 D 只被 B 引用
此刻业务线程做两件事：
  ① A.field = D    （黑对象 A 新增一条 → D 的引用）  ← 条件1
  ② B.field = null （删掉 B → D 的唯一引用）         ← 条件2

结果：D 现在只被黑色 A 引用。
  - A 是黑的，GC 不会再扫它 → 发现不了 A→D
  - B 到 D 的路径断了 → 灰色路径也没了
  → D 永远是白色 → 被误回收！但 D 明明还被 A 引用着，存活对象丢失

关键洞察：只破坏其中一个条件，漏标就不会发生。这就是两种解决方案的思路——各自盯死一个条件。

四、增量更新（CMS）：破坏条件 1

CMS 用「增量更新」，盯住条件 1（黑对象新增指向白对象的引用）：

写屏障逻辑（引用赋值时触发）：
  当发生 "黑对象.field = 白对象" 时
  → 记录下这个「黑对象」，把它重新变灰（放回灰色队列）
  → 重新标记阶段再扫一遍它，就能发现新增的 → 白引用

效果：黑对象一旦新增白引用，就"退回"灰色重新处理，条件1被破坏 → 不漏标

代价：重新标记阶段要重新扫描这些「退回灰色」的对象及其引用，如果新增引用多，重新扫描的量就大。而且 CMS 的重新标记（Remark）是 STW 的，增量更新记录的对象越多，这个 STW 停顿越长。

五、SATB（G1）：破坏条件 2

G1 用「SATB（Snapshot At The Beginning，起始快照）」，盯住条件 2（引用被删除）：

写屏障逻辑（引用删除/覆盖前触发）：
  当发生 "B.field = null" 或 "B.field = 其他"（即将删除 B→D 的旧引用）时
  → 在删除前，把旧引用指向的「白对象 D」记录下来，本轮标记视它为存活（变灰）

效果：任何"标记开始时可达"的对象，其引用即使被删，也被记下来当活的
      → 条件2被破坏（被删的引用对象仍被保留）→ 不漏标
思想：维护"标记开始那一刻的对象图快照"，快照里活的，本轮都算活

代价是浮动垃圾：如果 D 在标记开始时可达、但标记期间真的变成了垃圾，SATB 也会保守地留下它，本轮不回收，等下轮。这是「宁可错留一个浮动垃圾，也绝不错删一个存活对象」的取舍。G1 选 SATB 是因为它更适合 G1 的 Region 结构，且重新标记的 STW 更短更可控。

六、两种方案的对比与本质

维度	增量更新（CMS）	SATB（G1）
盯住的条件	条件1：黑→白新增引用	条件2：引用被删除
写屏障时机	引用赋值后（记录黑对象）	引用删除前（记录旧对象）
记录内容	新增引用的黑对象（重新扫）	被删引用指向的对象（当存活）
副作用	重新标记扫描量大	产生浮动垃圾
重新标记 STW	较长	较短（只处理 SATB 队列）

本质上两者都是「用写屏障捕捉并发期间的引用变化，破坏漏标的一个必要条件」。增量更新是「事后补扫」（发现黑对象变了，退回重扫），SATB 是「事前留底」（快照里的对象本轮都保住）。G1 选 SATB 让重新标记停顿更短、更可预测，契合它「可控停顿」的设计目标——这也是面试深挖「G1 为什么用 SATB 而不是增量更新」的答案。

记忆钩子：「白未扫、灰在扫、黑扫完；漏标需两条件同时成立（黑增白引用 + 删灰到白引用）；CMS 增量更新破坏条件1（重扫黑对象）、G1 SATB 破坏条件2（保留起始快照，代价是浮动垃圾）」。

七、常见误区与追问

误区：三色标记是某个收集器独有的。 它是所有并发标记收集器（CMS、G1、ZGC）的通用基础算法，只是各家用不同的写屏障方案解决漏标。
误区：多标和漏标都很严重。 多标只产生浮动垃圾（下次回收，无害）；漏标会误回收存活对象导致程序错误，才是致命的。
误区：只要有并发标记就一定漏标。 漏标需要两个条件同时成立；写屏障破坏其中任一条件即可避免。
误区：SATB 不会有多余对象残留。 它会保留「标记开始时可达但期间变垃圾」的对象（浮动垃圾），本轮不回收，用保守换正确。
追问：为什么 G1 用 SATB 而 CMS 用增量更新？ SATB 的重新标记只需处理写屏障记录的旧引用队列，STW 更短更可预测，契合 G1「可控停顿」目标；增量更新要重新扫描退回灰色的对象，停顿相对长。
追问：写屏障是什么？和内存屏障一样吗？ 这里的写屏障是「引用字段赋值时插入的一段 GC 记录逻辑」（AOP 式钩子），和保证可见性/有序性的 CPU 内存屏障不是一回事，别混淆。
追问：浮动垃圾会一直堆积吗？ 不会，本轮 SATB 保守留下的浮动垃圾会在下一轮 GC 被正常回收，只是延迟一轮，不会永久泄漏。

八、加强记忆

三色标记是并发 GC 追踪标记进度的通用算法：白=未访问、灰=自己访问了但引用没扫完（工作队列）、黑=自己和引用都扫完（GC 不再看），从 Roots 出发把可达对象逐步染黑，剩下的白色回收。并发标记的隐患是漏标——存活对象被误回收，它需要两个条件同时成立：①一个黑对象新增了指向白对象的引用，②所有从灰对象到该白对象的引用都被删除。解决靠写屏障破坏其一：CMS 用「增量更新」破坏条件①（黑对象新增白引用时把它退回灰色重扫，代价是重新标记扫描量大）；G1 用「SATB 起始快照」破坏条件②（引用删除前记下旧对象、本轮当存活，代价是浮动垃圾，但重新标记 STW 更短更可预测）。多标只是浮动垃圾无害、漏标才致命。一句话「白灰黑三色标记，漏标要两条件同时成立，CMS 增量更新重扫黑对象、G1 SATB 留起始快照」。

简化版

详细版