引用集存储
首先探讨一下如何执行增量回收的问题。对于老生代进行增量回收，方法是选择部分分区进行回收，为了保证应用在回收后能正确运行，通常会引入STW，然后执行回收。那么就会存在两种类型的回收：针对新生代的MinorGC和针对老生代的增量回收。这种设计非常自然，但存在两种回收，两种GC之间需要同步，例如在执行Minor GC时不能执行增量回收，同理，执行增量回收时也不能执行Minor GC。另外，还需要考虑两种回收不同的触发时机。
除了对老生代的分区进行单独的回收之外，还有一种方法是在进行MinorGC时，增量回收部分老生代分区。该方法本质上是把两种类型的回收合并为一种，G1中采用的就是这种方法。为了区别一般的Minor GC和同时执行新生代和部分老生代的增量回收，把后者称为混合回收（Mixed GC）。使用混合回收的方式可以减少多种回收交互带来的复杂性，但是混合回收给保证停顿时间这一目标带来了不确定性。
增量回收加上分区的设计，给跨代交互的引用集也带来了新的挑战。下面来看看基于当前的设计，G1如何处理引用集。
G1是分代的垃圾回收实现，对于Minor GC来说，要实现复制算法中的快速标记，需要记录老生代到新生代的引用。虽然内存是按照分区组织的，但是每一个分区都明确属于一个空间。如果仅仅记录老生代到新生代的引用，可以简单地使用卡表。假设这里采用卡表记录老生代到新生代的引用，对于是否需要记录引用关系（即写卡表），逻辑更为复杂一些。在前面介绍的垃圾回收器中，可以通过新生代和老生代的边界快速判断是否存在跨代引用。
但在G1中，由于使用分区管理内存，新生代和老生代之间并不存在一个边界，所以需要在写卡表时先根据地址找到所在的分区，再找到分区所属的代，最后判断是否记录引用关系。实际上这一过程所需的成本并不高，业界有一些垃圾回收器采用这种方法。使用卡表记录代际引用示意图如图6-5所示。
图6-5 使用卡表记录代际引用
对于Mixed GC来说，由于需要同时回收新生代分区和部分老生代分区，Mixed GC和Minor GC使用相同的处理逻辑，也就是说在复制算法中也需要快速完成标记处理。
对于新生代可以通过卡表记录老生代到新生代的引用，但是对于部分需要回收的老生代分区该如何处理？当回收这部分老生代分区时，必须能通过引用关系找到活跃对象，其引用关系来自其他老生代分区对于回收分区的引用，这时也可以采用卡表进行保存。
但因为回收的分区并不确定，所以引用关系的记录粒度只能进一步细化到分区之间，也就说，在老生代空间中，分区之间的引用关系都需要记录。按照这样的设计，在混合回收时需要处理两张卡表，分别记录老生代到新生代的引用和老生代分区之间的引用。
实际上老生代空间比较大，分区较多，分区之间引用也比较多，这会导致卡表记录的数据不够准确，即卡表记录的引用关系的目标分区不在Mixed GC的回收范围内。这会导致大量无用的引用者被扫描，极端情况下，除了待回收的老生代分区以外，其他分区都要参与扫描，这就等价于扫描整个老生代。使用卡表记录老生代、新生代代际引用的示意图如图6-6所示。
图6-6 代际引用和代内引用的卡表管理
图6-6中为了演示需要，使用了两个卡表分别记录老生代到新生代的引用、老生代到老生代的引用。这两个卡表在实现中可以合并为一个，只不过合并后在Minor GC中的效率可能会降低。
使用卡表存储引用关系，可以加速回收过程中的扫描进度。通过卡表存储引用关系，本质上把引用关系保存在引用者关联的位置，除此以外，还可以考虑把引用关系保存在被引用者关联的位置。那么一个自然的方法就是把引用者的地址放在引用者关联的位置，如图6-7所示。
图6-7 在被引用者处保存引用关系
通过这种方式，Minor GC和Mixed GC都只需要关注回收分区关联的引用者，把这些引用者作为根，就可以保证标记的正确性。两者在算法上完全一致，唯一不同的就是两者处理的分区集合不同。
这里再稍微讨论一下引用集存储的优化：是否所有的引用关系都需要保存？直接保存引用者的地址是否会存在过度消耗内存的问题？
先来回答第一个问题，结论是有些引用关系并不需要保存。主要有3种引用关系不需要保存：
1）新生代到老生代的引用。
2）新生代内部分区之间的引用。
3）一个分区内部的引用关系。
第一点是冗余信息，回收时不会使用，第二点和第三点，无论是MinorGC还是Mixed GC，都以分区作为回收单位，即一个分区要么回收要么不回收。在分区回收的时候，如果分区中的对象是活跃的，则该对象会作为待扫描对象，继续处理成员变量，也就说只要分区中的引用者是活跃的，那么分区中的被引用者都能被找到。所以无须记录这两种引用关系。总结下来真正需要的记录的是：老生代到新生代的引用，老生代空间内部分区之间的记录。
对于第二个问题，直接保存引用地址，在引用关系多的情况下，内存消耗可能很多，所以需要一个好的引用存储机制来平衡引用少、一般、非常多的场景。为此，G1实现了3种数据结构，分别处理这3种情况。这3种数据结构分别是：稀疏表、细粒度表和粗粒度位图。其结构和适用场景如图6-8所示。
图6-8 G1中多种结构保存引用关系
在使用时并不知道分区需要保存多少引用，所以总是从稀疏表开始。当发现稀疏表无法满足存储需求时，会从稀疏表升级到细粒度表；当细粒度表仍然无法满足存储需求时，会升级到粗粒度位图。
稀疏表的长度通常都不长，所以在实际场景中，经常会发生从稀疏表到细粒度表的晋升。注意，在晋升时，由于数据结构不同，因此存在数据迁移的问题。在JDK 12之前，有一个开发参数G1HRRSUseSparseTable控制是否使用稀疏表，因为该参数并未暴露给用户，所以在JDK 12中被移除。如果用户没有设置稀疏表的大小，其大小可以通过公式计算得到，其计算方式为log（RegionSize/1M）×G1RSetSparseRegionEntriesBase。其中G1RSetSparseRegionEntriesBase仍然是一个开发参数，默认值为4。用户可以通过G1RSetSparseRegionEntries来直接设置稀疏表的大小。
由于粗粒度位图把整个分区都作为潜在的引用者，因此在扫描时效率较低，可能会对GC带来较大的性能问题。在实际工作中如果发现这样的情况，应该调整细粒度表的存储长度，避免其升级到粗粒度位图。
同样，当使用者没有设置细粒度表的大小时，其大小可以通过分区的大小、控制参数计算得到，其计算方式为log（RegionSize/1M+1）×G1RSetRegionEntriesBase。其中G1RSetRegionEntriesBase是一个开发参数，默认值为256。用户可以通过G1RSetRegionEntries来直接设置细粒度表的大小。
引用集处理流程
被引用者关联的内存中存储引用者信息与引用者关联的内存中存储被引用者信息还有一个区别：一个成员变量在同一时间最多关联一个被引用者，而一个被引用者在同一时间可能赋值给多个引用者。
所以通过卡表的存储方式，卡表中的值总是可以唯一地确定，在写卡表时不会存在并发冲突（由于卡表覆盖一定的内存区域，当一个区域内有多个对象时，它们可以同时被多个线程更新引用关系，多个线程需要并发地写卡表，由于多个对象属于同一个区域，实际上相当于多个对象写一个地址，从这一点来说写卡表可能存在冲突。
但多个线程并发往同一个地址写同一个数据，写冲突不会影响结果的正确性，所以可以简单地认为卡表的写操作不会导致冲突）。而在被引用者关联的内存中存储引用者信息，当多个线程并发地更新引用者的成员变量时，需要被引用者存储多个引用者，这多个引用值并不相同，并且引用更新先后顺序会影响最终的结果。
为什么要保证有序？保证数据有序最主要的原因在于，当一个引用者多次（可以在一个线程执行多次中或者多个线程）更新被引用者时，实际上只有最后一次更新所指向的被引用者才是有效的。如果要准确地记录对象之间的引用关系，则必须保证时间有序。这意味着多个线程需要按照时间顺序并发地操作一个存储结构，这样的操作必须通过锁机制才能达到，而使用锁一定会带来性能急剧下降，所以需要一个合适的方法来实现无锁地记录引用者地址。
要实现按时间顺序的无锁写操作并不容易。实际上这个问题可以抽象为多个客户端同时往一个数据结构中写数据，同时要求数据按照时间有序。写引用集的抽象模型如图6-9所示。
图6-9 多个引用者指向同一个被引用者示意图
第一个解决问题的方法就是不要求准确记录对象的引用关系，即可以保持冗余。也就是说当一个引用者多次更新被引用者时，在每一个被引用者上都记录这个引用者。这相当于把一个引用者变成了多个引用者，会造成一定的冗余。这样做的效果就是不再需要时间有序，只要保证引用者能在垃圾回收之前被成功记录就可以了。对这一方案继续优化，可以在写操作之前引入一个队列，那么只要让多个线程把数据放入队列中，再慢慢地把队列中的数据放入引用集中，就解决了有序的问题。此时写引用集的抽象模型如图6-10所示。
图6-10 引入队列解决对象引用关系修改的顺序
但是上述模型还有一个问题，那就是多个线程并发写一个队列，仍然存在锁竞争问题。对于这个问题的解决方法是：在每一个线程中都建立一个队列，线程通常只需要写自己的私有队列，满足一定条件的情况下，如果私有队列满了以后，把私有队列放入一个全局队列集合中，然后把全局队列集合的数据写入引用集中即可。此时写引用集的抽象模型如图6-11所示。
图6-11 引入队列集合解决多线程写入的锁竞争
在数据写入真正存储空间的地方还可以继续优化处理，由于此时有一个全局队列集合保存所有引用者的地址，而且对写入顺序不做任何要求，那么这个操作可以放在后续的垃圾回收阶段再执行，也可以不放在垃圾回收阶段执行。如果在垃圾回收阶段执行，则会造成垃圾回收的停顿时间增加；但是如果不在垃圾回收阶段执行，即通过并发线程执行写引用集，则需要保证在垃圾回收阶段执行之前，把全局队列集合的所有队列都写入引用集，这样就能保证正确性。所以接下来需要解决的问题就是，通过并发线程写引用集，同时保证正确性。
应用运行会带来大量的写操作，这意味着全局队列集合的数量很多，最好通过多线程机制来并发处理。注意在多线程写引用集的过程中仍然可能涉及锁的问题，这也是为什么在前面提到的细粒度表中按照分区设计，不仅仅是方便组织，也是为了减少锁的冲突，只有当多个线程写同一个数组元素（也就是同一个分区）时才会产生真正的锁等待。
但是如何保证垃圾回收之前，并发线程把全局队列的数据都写入引用集中呢？要达到这样的目标非常困难，原因在于：全局队列集合随着应用的执行会不断地增长，要保证全局队列集合没有数据几乎是不可能的，除非应用暂停，但是如果应用暂停，就不应该再要求并发线程去处理全局引用队列集合，而应该由垃圾回收线程进行处理。所以合理的方案是让并发线程尽量处理全局队列集合中的队列，当垃圾回收发生时，就由垃圾回收线程继续处理尚未处理的队列。在G1中并发处理引用关系的线程被称为Refine线程。注意，Refine线程和垃圾回收线程之间需要同步操作。当垃圾回收线程启动以后，Refine需要暂停执行。多个Refine线程并发处理数据的示意图如图6-12所示。
图6-12 引入多个Refine线程读待处理的引用关系
接下来的问题就是：该如何设计Refine线程，让Refine尽可能处理更多的引用关系，且不影响应用的执行，并让垃圾回收线程尽可能少地处理引用关系。
引用集写入
如何才能让Refine线程尽可能处理更多的引用关系？简单的做法是使用多个线程处理。因为引用集队列不直接依赖于Mutator，所以Refine线程和Mutator可以并发运行。那该启动多少个Refine线程并发处理引用集队列呢？
在JVM的实现中提供了一个参数用于控制Refine线程数。我们知道，由于Refine线程和Mutator并发运行，Refine线程过多一定会影响Mutator的运行效率；Refine线程过少则会影响引用关系的处理，会把更多的任务留到垃圾回收阶段处理，可能导致停顿时间过长。
在G1中的实现方案是：根据队列个数弹性地选择Refine线程的个数，当引用集队列个数很少的时候，为了减少Refine线程和GC工作线程的同步操作，此时Refine线程不工作，把所有的写入任务推迟到GC工作线程中处理；
当引用集队列增加到一定个数之后，Refine线程并发地把引用关系保存到分区的引用集结构中；当引用集队列继续增加，超过一个较高的阈值以后，Refine负载很重，此时一个好的方法是让Mutator（产生引用关系的应用线程）直接把引用关系保存到分区的引用集结构中，即Mutator协助Refine线程进行工作。
虽然JVM中提供了一个参数用于控制Refine线程的个数，但Refine线程个数并不容易设置，过多或过少都有可能发生。Refine线程的个数最好与引用关系的个数成正比，当引用关系多的时候，Refine线程个数多一些，当引用关系少的时候，Refine线程个数少一些。
综上所述，可以把整个引用集队列划分成4个区，称为白区、绿区、黄区和红区，如图6-13所示。
图6-13 将待处理的引用关系划分为4个区
这4个区在不同的情况下的工作如下。
白区：留给GC工作线程处理的引用集队列。
绿区：留给Refine线程处理的引用集队列，只有部分Refine线程参与引用写入工作，说明Refine线程任务并不重。
黄区：留给Refine线程处理的引用集队列，所有的Refine线程都参与引用写入工作，说明Refine线程任务开始趋向于过载。
红区：留给Mutator处理的引用集队列。
这个4个分区采用不同数量的Refine线程进行并发处理，如图6-14所示。
图6-14 4个分区并发处理任务
本文给大家讲解的内容是JVM垃圾回收器详解：垃圾优先，引用集设计
- 下篇文章给大家讲解的内容是JVM垃圾回收器详解：垃圾优先，新生代回收和混合回收
- 感谢大家的支持！