垃圾回收器比较: G1 vs CMS
最近看了Garbage-First Garbage Collection 和 A Generational Mostly-concurrent Garbage Collector这两篇论文，这里总结下两者的异同。
1. 分代收集
这个现在是垃圾回收器的标配，G1和CMS也不例外。但是G1同时回收老年代和年轻代，而CMS只能回收老年代，需要配合一个年轻代收集器。另外G1的分代更多是逻辑上的概念，G1将内存分成多个等大小的region，Eden/ Survivor/Old分别是一部分region的逻辑集合，物理上内存地址并不连续。
G1逻辑分代
CMS在old gc的时候会回收整个Old区，对G1来说没有old gc的概念，而是区分
Fully young gc和Mixed gc，前者对应年轻代的垃圾回收，后者混合了年轻代和部分老年代的收集，因此每次收集肯定会回收年轻代，老年代根据内存情况可以不回收或者回收部分或者全部(这种情况应该是可能出现)。
2. 如何处理跨代引用
在垃圾回收的时候都是从Root开始搜索，这会先经过年轻代再到老年代，对于年轻代引用老年代的这种跨代不需要单独处理。但是老年代引用年轻代的会影响young gc，这种跨代需要处理。
为了避免在回收年轻代的时候扫描整个老年代，需要记录老年代对年轻代的引用，young gc的时候只要扫描这个记录。CMS和G1都用到了Card Table，但是用法不太一样。JVM将内存分成一个个固定大小的card，然后有一个专门的数据结构(即这里的Card Table)维护每个Card的状态，一个字节对应一个Card，有点像内存page的概念，只是page是硬件上的，Card Table是软件上的。当一个Card上的对象的引用发生变化的时候，就将这个Card对应的Card Table上的状态置为dirty，young gc的时候扫描状态是dirty的Card即可。这是基本的用法，CMS基本上就是这么使用。
G1在Card Table的基础上引入的remembered set(下面简称RSet)。每个region都会维护一个RSet，记录着引用到本region中的对象的其他region的Card。比如A对象在regionA，B对象在regionB，且B.f = A，则在regionA的RSet中需要记录B所在的Card的地址。这样的好处是可以对region进行单独回收，这要求RSet不只是维护老年代到年轻代的引用，也要维护这老年代到老年代的引用，对于跨代引用的每次只要扫描这个region的RSet上的Card即可。
上面说过年轻代到老年代的引用不需要单独处理，这带来了很大的性能上的提升，因为年轻代的对象引用变化很大，如果都需要记录下来成本会很高。同时也说明只需要在老年代维护Card Table。
3. 如何处理并发过程的对象变化
CMS和G1都有并发处理过程，这个过程应用程序跟着gc线程一起运行，会产生新对象，也会有旧的对象死去，对象之间的引用关系也会发生变化。这部分数据可以暂时不处理，留到下一次再处理吗？如果可以这样的话问题就会变得很简单，但是答案是不行。考虑下图的场景(图中每一行表示一个内存状态，每一列表示一个Card，这里有4个)：第一步a是并发标记中途的一个状态，标记了a b c e四个对象，0 1两个Card已经标记好；第二步b并发标记的同时引用发生变化，g不再指向d，而b不再指向c，变成指向d，这个时候处理Card 2，会标记到g，然后就标记结束了，导致d对象丢失。
image.png
CMS初始标记的时候会标记所有从root直接可达的对象，并发标记的时候再从这些对象进一步搜索其他可达对象，最终构成一个存活的对象图。并发标记过程中引用发生变化的也是通过Card Table来记录。但是young gc的时候如果一个dirty card没有包含到年轻代的引用，这个card会重新标记为clean，这有可能将并发标记过程产生的dirty card错误清除，因此CMS引入了另一个数据结构mod union table，这里一个bit对应一个Card，young gc在将Card Table设置为clean的时候会将对应的mod union table置为dirty。最终标记的时候会将Card Table或者mod union table是dirty的Card也作为root去扫描，从而解决并发标记过程产生的引用变化。CMS还需要处理并发过程从年轻代晋升到老年代的对象，处理方式是将这部分对象也作为root去扫描。
G1使用一个称为snapshot at the beginning(下面简称SATB)的算法，在初始标记的时候得到一个从root直接可达的snapshot，之后从这个snapshot不可达的对象都是可以回收的垃圾，并发过程产生的对象都默认是活的对象，留到下一次再处理。对于引用关系发生变化的，将这个对象对应的Card放到一个SATB队列里，在最终标记的时候进行处理(如果超过一定的阈值并发标记的时候也会处理一部分)，处理的过程就是以队列中的Card作为root进行扫描。
4. Write Barrier
Write Barrier可以理解为在写的时候插入一条特定的操作。
在CMS中老年代引用年轻代的时候就是通过触发一个Write Barrier来更新Card Table的标志位。这是一个同步操作，在更新引用的时候顺带执行，只需要两个指令，引入的消耗不大。
G1比较复杂，在两个地方用到了Write Barrier，分别是更新RSet的rememberd set Write Barrier和记录引用变化的Concurrent Marking Write Barrier，前者发生在引用更新之后，称为Post Write Barrier，后者发生在引用变化之前，称为Pre Write Barrier。G1为了提高性能，这两个Write Barrier都是先放到队列中，再异步进行处理。具体可以参考Garbage-First Garbage Collection 论文笔记
5. Full GC
导致CMS Full GC的可能原因主要有两个：Promotion Failure和Concurrent Mode Failure，前者是在年轻代晋升的时候老年代没有足够的连续空间容纳，很有可能是内存碎片导致的；后者是在并发过程中jvm觉得在并发过程结束前堆就会满了，需要提前触发Full GC。CMS的Full GC是一个多线程STW的Mark-Compact过程，，需要尽量避免或者降低频率。
G1的初衷就是要避免Full GC的出现，Full GC会会对所有region做Evacuation-Compact，而且是单线程的STW，非常耗时间。导致G1 Full GC的原因可能有两个：1. Evacuation的时候没有足够的to-space来存放晋升的对象；2. 并发处理过程完成之前空间耗尽。这两个原因跟CMS类似。
以上是目前想到的5点主要的比较点，理解可能有误，欢迎指正。
参考：
Garbage-First Garbage Collection
A Generational Mostly-concurrent Garbage Collector
Java Garbage Collection handbook
Java Performance Companion
