增量更新与原始快照
增量更新与原始快照
Java 语言的垃圾回收一直有一个为人所诟病的点，即垃圾回收时会触发 “STW”，为了减少 “STW” 的时间，垃圾收集器也在不断改进。
在日常开发中，我们经常会通过多线程的手段缩短程序的执行时间，目前主流的垃圾收集器也使用了并发在某些阶段让 GC线程 和 用户线程 可以同时工作，以尽可能及时地对请求进行处理。
提到并发，那就一定会涉及线程安全问题。试想：如果一个扫地机器人（GC线程）处理完了一部分的区域的垃圾（部分对象），开始处理其他区域的垃圾（其他对象），但此时用户（用户线程）又向处理过的区域丢垃圾（引用未处理区域的对象或删除对象引用），那该怎么办呢？
“STW” 的过程中，如果所有用户线程暂停，对象间的引用关系就不会改变，没有这个问题。在并发情况下，是通过先记录所有标记过程中对于对象引用的修改，并发标记完成后再暂停进行处理来保证处理时的一致性。
三色标记法
三色标记法是一种经典的可达性分析师算法，它将对象分为三种颜色：
黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。
灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。
白色：表示对象尚未被垃圾收集器访问过。
以下面这个图来分析三色标记法的流程：
- 在可达性分析最开始的阶段，所有的对象都是白色的；
- 将
GC Roots直接引用到的对象 挪到 【灰色集合】中； - 从灰色集合中获取对象：
3.1. 将本对象引用到的其他对象（出边）全部挪到 【灰色集合】中；
3.2. 将本对象挪到 【黑色集合】里面； - 重复执行 3，直到【灰色集合】为空；
- 此时仍然是白色的对象，即代表不可达。
一般执行步骤 2 时是会暂停用户线程的，最终的图示如下：
现在思考下在并发标记时什么情况下会出问题？
- 有一个对象已经扫描完成是黑色的了，但此时引用该对象的那条引用被删除了，这个对象应该被清除的，误标记为存活对象。这会导致垃圾回收不彻底，但影响不大，可以在下个周期被回收。这种对象被称为浮动垃圾（多标）。
- 在遍历某个灰色对象的过程中，删除了它所引用的一个对象，这个对象还被一个黑色对象引用了。如果这么进行下去会导致本应该存活的对象消失（漏标），是不可接受的。
Wilson 于 1994 年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：
- 赋值器插入了一条或多条从黑色对象到白色对象的新引用；
- 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。
如果第一个条件是新增了灰色对象到白色对象的引用是否可行呢？例如在获取灰色对象引用集合和灰色对象变黑之间新增了对一个白色对象的引用。实现上这是不可以的，JVM 通过 屏障（ Barrier）维护了这个步骤的正确性。
既然对象消失必须同时满足这两个条件，那么只要打破其中一个条件就可以了，这就是接下来介绍的增量更新（Incremental Update）和原始快照（Snapshot At The Beginning， SATB）。
增量更新（Incremental Update）
CMS 是基于增量更新来做并发标记的，破坏的是条件一。
增量更新的核心逻辑是：当黑色对象插入新的指向白色对象的引用时，就将这个新加入的引用记录下来，待并发标记完成后，重新对这种新增的引用记录进行扫描。可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。
如下图所示，A 由黑色变为灰色，将在后续被重新扫描：
原始快照（Snapshot At The Beginning）
G1、Shenandoah 则是用原始快照来实现的，破坏的是条件二。
当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，在标记阶段中如果指针更新前引用的对象是白色对象，就将其涂成灰色。
如下图所示，C 由白色变为灰色，将在后续被重新扫描：
这里你可能有疑问，C 虽然是灰色，但根本没有黑色对象引用呀。原始快照就是这样，它只考虑灰色对象对白色对象的引用删除，只要一个对象在并发标记开始时是可达的（即存在于快照的有效中），即使随后它所有的入口引用都被删除，仍然会被本轮 GC 标记为存活。虽然这可能暂时保留垃圾，也做到了绝不漏标快照中的对象。
增量更新 VS SATB
增量更新通过写屏障拦截黑对象新增指向白对象的引用，把这个黑对象重新标为灰色，放入待扫描队列，最后 Remark（重新标记）时，只扫这些被修改过的对象。
SATB 以并发标记开始那一刻的对象图为 “快照”，写屏障拦截引用被删除（灰→白），把 旧值（被删掉的引用） 记下来，保证 “快照里活着的对象” 本轮一定不被误删，新产生的对象直接当黑色，本轮不回收。
为什么 CMS 采用增量更新而 G1 采用原始快照呢？
这个问题涉及到很多方面，包括堆内存的布局、记忆集的维护、垃圾收集器的目标。
CMS 工作的老年代是一整块连续内存，Remark 时只追踪新增引用，重新扫描的范围小、成本可控，而且浮动垃圾更少，符合 CMS 追求低内存占用的目标。代价则是 Remark 阶段要深度重扫部分对象。
G1 的堆被拆成几百个 Region，回收是 “按 Region 回收”，采用 SATB 只记录 “被删掉的引用”，不需要深度重扫整个 Region。代价是产生更多的浮动垃圾，但 G1 是分代 + 分区，浮动垃圾影响可控，换来更低、更可控的停顿是值得的。如果 G1 用增量更新，通过记忆集跨 Region 扫描代价极高、停顿不可控。