算法 自动采集列表(1.概述1.2垃圾收集器的考量指标(1.2)_概述)

　　算法 自动采集列表(1.概述1.2垃圾收集器的考量指标(1.2)_概述)

　　1.概述1.2 垃圾采集器注意事项

　　垃圾采集器也有类似CAP理论的矛盾，具体有以下三个方面的考虑：

　　吞吐量

　　响应性、延迟（Latency）

　　内存占用（容量）

　　以上三个考虑不能同时满足最优，只能满足其中两个，牺牲其中之一的部分效率。

　　1.3 吞吐量

　　吞吐量与在指定时间范围内最大化应用程序的工作负载有关。

　　以下方法用于测量系统的吞吐量：

　　在一小时内，完成同一事务（任务或请求）的次数。

　　数据库在一小时内完成了多少查询。

　　对于注重吞吐量的系统，偶尔的停顿是可以接受的，因为这种系统注重长时间执行大量任务的能力，单一的快速响应不值得考虑。

　　1.4 响应能力

　　响应性是指应用程序或系统是否能够及时快速地响应，例如：

　　桌面 UI 程序对事件的响应速度。

　　网站 返回页面请求的速度有多快。

　　数据库返回查询结果的速度有多快。

　　对于这种响应敏感、低延迟的场景，长期卡顿是不能容忍的。

　　内存使用情况

　　为了加快内存扫描的数据，GC垃圾采集器通常会使用内存中的一些数据结构，比如卡表、内存集等，来存储对对象的直接引用，而这些数据本身就需要占用堆的内存空间。记录的信息越多，扫描时间越快，占用的内存也越大。

　　1.5 G1的诞生背景

　　随着硬件成本越来越低，机器的内存也越来越大。GC回收器占用的内存基本可以容忍，吞吐量可以通过集群（加机器）解决，所以STW时间对于JVM来说就变得迫切要解决的问题，如果还是按照传统的分代方式使用传统的垃圾回收器模型，那么STW时间会越来越长。

　　在传统的垃圾采集器中，STW 时间是不可预测的。有没有办法先定义一个暂停时间，然后向后计算采集到的内容？就像领导在年初制定KPI一样，多做多做，少做少做。

　　G1的思路类似。不需要每次都清理垃圾。它只是尝试做它认为正确的事情。

　　G1还有一个极其重要的特性：软实时（soft real time）。所谓实时垃圾回收，是指在规定的时间内完成垃圾回收。“软实时”意味着用户可以指定垃圾采集的时间限制。G1会尽量在这个时限内完成垃圾采集，但是G1不保证每次都能在这个时限内完成垃圾采集。通过设定一个合理的目标，90%以上的垃圾回收时间都可以在这个时间限制内。

　　我们要求 G1 在任何一秒的时间内暂停不超过 10 毫秒。这是为其制定KPI。G1将尽最大努力实现这一目标。可以逆向计算本次要采集的总面积，增量式完成采集。

　　这也是使用G1垃圾采集器必须设置的一个参数（-XX:+UseG1GC）：-XX:MaxGCPauseMillis=10，这个参数默认为200ms。

　　G1的适用场景：

　　服务器端多核CPU、JVM内存占用应用。

　　应用程序运行过程中会产生大量的内存碎片，空间需要经常进行压缩。

　　想要一个更可控和可预测的GC暂停期，以防止高并发下的应用程序雪崩。

　　2. G1的内存模型2.1 Partition概念

　　

　　2.1.1师区域

　　G1采用了region的思想，将整个堆空间划分为若干大小相等的内存区域，每次分配对象空间时，都会逐段使用内存。因此，在堆的使用上，G1并不要求对象的存储必须物理上连续，只要逻辑上连续即可；每个分区都不会肯定服务于某一代，它可以用于年轻代和老年代之间的切换。分区大小（1MB~32MB，必须是2的幂）可以在启动时通过参数-XX:G1HeapRegionSize=n指定。默认情况下，整个堆被划分为 2048 个分区。

　　对于那些超过整个 Region 容量的超大对象，它们将被存储在 N 个连续的 Humongous Region 中。大多数情况下，G1的回收都会将洪门地区视为老年的一部分。

　　G1在逻辑上划分了Eden（所有Eden区域的总和）、Survivor（所有Survivor区域的总和）和OLd（所有Old区域的总和），但物理上它们是不连续的，同一个区域在不同区域的作用期间可以不同。有可能当前区域存储了 Eden 对象。执行 YGC 后，分配给它的下一个对象可能是 Old 对象。

　　2.1.2张卡片

　　卡片表的诞生是为了解决跨代引用。假设在cms垃圾采集器中，如果要回收新生代的对象，那么就必须扫描整个老年代，而要引入卡表，只需要扫描卡表的中间脏区就够了，避免了扫描整个老年代，大大加快了并发标记的速度。

　　每个Region分为若干张固定大小的卡片（Card）。每张卡片使用一个Byte来记录是否被修改过。卡片表是这些字节的集合。标识堆内存和所有分区的最小可用粒度的卡将记录在全局卡表中。分配的对象将占用多个物理上连续的卡片。当对象被引用时，可以通过记录卡找到被引用的对象（见RSet）。每次回收内存时，都会处理指定分区中的卡片。

　　

　　2.1.3Memory Set RSet

　　RS（Remember Set）是一个抽象概念，用于记录从非集合部分到集合部分的指针集合。

　　在传统的分代垃圾采集算法中，RS（Remember Set）用于记录代际之间的指针。在 G1 采集器中，RS 用于记录从其他区域到一个区域的指针。因此，一个Region就有一个RS。这种记录可以带来很大的好处：回收一个Region的时候，不需要进行全堆扫描，只需要检查它的RS就可以找到外部引用，而这些引用是初始的root之一标记。

　　RSet底层是通过HashTable实现的（可以理解，这其实是一个抽象的概念），key是被引用对象所在Region的内存起始地址，value是Card Table的索引引用对象所在的位置。

　　也假设现在Region A中object的第四个block引用了Region B中的object，那么Region A的card table的第三位设置为Dirty（1），然后Region B中的RSet添加一条记录，其中key为Region A的内存起始地址，value为Region A的对象所在卡片表中的索引3，这样回收Region B时，只需要扫描Region B 的 RSet 作为 GC ROOTS 对象。

　　RSet 的更新不是同步完成的。G1会将所有的引用关系放到一个队列中，称为Dirty Card Queue（DCQ），然后使用一个单独的线程来消费这个队列来完成更新。这是因为对象的引用变化太频繁，队列用于异步削峰。参数 -XX:G1ConcRefinementThreads 可用于指定消费者线程的数量。

　　使用空间来交换时间，使用额外的空间来维护参考信息通常会消耗5%到10%的空间。

　　写屏障（write barrier）：当对象的引用发生变化时，插入一个写屏障来维护RSet。这个写屏障不是Java内存模型中写屏障的概念。

　　事实上，并不是所有的引用都需要记录在 RSet 中。如果确定要扫描某个分区，则无需RSet就可以无遗漏地获得引用关系。那么对源自该分区的对象的引用当然不需要落入 RSet；同时，G1 GC 每次都将年轻代作为一个整体采集，因此对源自年轻代的对象的引用不需要记录在 RSet 中。最后，只有老一代分区可能有 RSet 记录。这些分区被称为一个 RSet 的拥有区域（an RSet's owning region）。

　　修改RS也会遇到并发问题。因为一个Region可能会被多个线程并发修改，所以他们也会并发修改RS。为了避免这样的冲突，G1垃圾采集器进一步将RS划分为多个哈希表。每个线程都在其自己的哈希表中进行修改。最后，从逻辑上讲，RS 是这些哈希表的集合。哈希表是实现 RS 的常用方法之一。它有一个很大的优点，就是可以去除重复。这意味着 RS 的大小将等于修改指针的数量。不进行重复数据删除时，RS 的数量相当于写操作的数量。

　　图中RS的虚线表的名称是，RS不是与Card Table分离的不同数据结构，而是将RS作为概念模型来指代。实际上，Card Table 是 RS 的一个实现。

　　关联：

　　2.1.4Per Region Table

　　RSet 内部使用 Per Region Table (PRT) 来记录分区的引用。由于RSet记录占用了分区的空间，如果一个分区很“流行”，RSet占用的空间就会增加，从而减少了该分区的可用空间。G1通过改变RSet的密度来应对这个问题，并且会在PRT中以三种模式记录引用：

　　从上面可以看出，粗粒度的PRT只记录引用次数，需要扫描整个栈才能找到所有引用，所以扫描速度也是最慢的。

　　2.1.5 堆 堆

　　G1 还可以通过 -Xms/-Xmx 指定堆空间大小。当发生年轻代回收或混合回收时，通过计算GC和应用的耗时比例自动调整堆空间大小。如果GC频率太高，通过增加heap size来降低GC频率，GC占用的时间也相应减少；目标参数-XX:GCTimeRatio是GC到应用的耗时比例，G1默认为9，而cms默认为99，因为cms的设计原则是花为尽可能少花时间在 GC 上。另外，当空间不足时，比如对象空间分配或者传输失败，G1会先尝试增加堆空间。如果扩展失败，它将启动一个有保证的 Full GC。Full GC 后，

　　2.2代机型2.2.1代

　　分代垃圾回收可以专注于最近分配的对象，而无需扫描整个堆，避免复制长期存在的对象，独立回收可以帮助减少响应时间。虽然分区使得内存分配不再需要紧凑的内存空间，但 G1 仍然使用生成的思想。与其他垃圾回收器类似，G1在逻辑上将内存划分为年轻代和老年代，年轻代划分为Eden空间和Survivor空间。但是，年轻代空间并不是固定的。当现有的年轻代分区已满时，JVM 会分配一个新的空闲分区加入年轻代空间。

　　整个年轻代内存会在初始空间-XX:G1NewSizePercent（默认整堆5%）和最大空间（默认60%）之间动态变化，参数目标暂停时间-XX:MaxGCPauseMillis（默认200ms），需要被扩展和收缩的内容的大小是通过-XX:G1MaxNewSizePercent和分区的内存集（RSet）来计算的。当然，G1 仍然可以设置一个固定的年轻代大小（参数 -XX:NewRatio, -Xmn），但是同时挂起目标是没有意义的。

　　2.2.2 本地分配缓冲区

　　本地分配缓冲区（实验室）

　　值得注意的是，由于分区的思想，每个线程都可以“声明”一个分区用于线程本地内存分配，而不管分区是否连续。因此，每个应用线程和GC线程都会独立使用分区，从而减少同步时间，提高GC效率。此分区称为本地分配缓冲区 (Lab)。

　　其中，应用线程可以独占一个本地缓冲区（TLAB）来创建对象，大部分都会落入Eden区（巨大对象或分配失败除外），所以TLAB分区属于Eden空间；并且每次垃圾回收时，每个GC线程也可以使用一个独占的本地缓冲区（GCLAB）来传输对象。每次采集对象时，都会将对象复制到Suvivor空间或旧空间；用于从Eden/Survivor 空间提升到Survivor/old 空间GC 的对象也有一个GC 专用的本地缓冲区用于操作，这部分称为提升本地缓冲区（PLAB）。

　　2.3 分区模型

　　

　　G1以区域为内存单位，以卡片（Card）为单位分配对象。

　　2.3.1 巨域

　　大小达到或超过分区大小一半的对象称为巨型对象。当一个线程为huge分配空间时，不能简单地在TLAB中分配，因为huge对象的移动成本非常高，一个分区可能无法容纳huge对象。因此，巨大的对象会直接分配到老年代，占用的连续空间称为Humongous Region。G1做了内部优化。一旦发现没有引用指向一个巨型对象，就可以直接在年轻代回收循环中回收。

　　一个巨大的对象将独占一个或多个连续的分区。第一个分区标记为StartsHumongous，相邻的连续分区标记为ContinuesHumongous。由于无法享受Lab带来的优化，而且需要扫描整堆来确定一个连续的内存空间，因此确定巨物起始位置的成本非常高。如果可能，应用程序应避免生成巨型对象。

　　2.4 采集集（CSet）

　　

　　采集集 (CSet) 表示每次 GC 暂停时回收的一系列目标分区。在任何采集暂停中，CSet 的所有分区都将被释放，内部幸存的对象将被转移到分配的空闲分区。因此，无论是年轻代采集还是混合采集，工作机制都是一样的。年轻代集合CSet只容纳年轻代分区，而混合集合会使用启发式算法在老年代的候选回收分区中筛选出回收收益最高的分区，加入到CSet中。

　　可以通过活动阈值-XX:G1MixedGCLiveThresholdPercent（默认85%）设置候选老年代分区的CSet访问条件，从而拦截那些回收成本巨大的对象；同时，每个混合集合可以收录候选老年代分区，可以根据CSet占堆总大小的比例设置数量上限-XX:G1OldCSetRegionThresholdPercent（默认10%）。

　　从上面可以看出G1的集合是按照CSet来操作的。年轻代采集和混合采集没有明显区别。最大的区别在于两个集合的触发条件。

　　2.4.1C集Young 采集

　　应用线程不断活跃后，年轻代空间会逐渐被填满。当JVM分配对象到Eden区失败（Eden区已满）时，会触发STW式的年轻代集合。在年轻代集合中，Eden分区中幸存的对象会被复制到Survivor分区；原Survivor分区中的存活对象将根据tenuring阈值、新的Survivor分区和旧的分区被提升到PLAB中。原来的年轻代分区会被整体回收。

　　同时，年轻代集合还负责维护对象的年龄（存活次数），并辅助判断tenuring对象是提升到Survivor分区还是老年代分区。年轻代集合首先在年龄表中维护提升对象的总大小和对象的年龄信息，然后根据年龄表，Survivor大小，和Survivor填充容量-XX:TargetSurvivorRatio（默认50%），最大任期阈值-XX:MaxTenuringThreshold（默认15)，计算一个合适的任期阈值。超过任期阈值的人将被提升到老年。

　　2.4.2C 混合集合

　　年轻代不断采集后，年老代的空间会逐渐被填满。当老年代占用的空间超过IHOP阈值-XX:InitiatingHeapOccupancyPercent（默认45%）时，G1将启动混合垃圾回收循环。为了满足暂停目标，G1 可能无法一次性采集所有候选分区。因此，G1 可能会生成多个连续的混合集合和应用程序线程的交替执行。每个 STW 的混合采集类似于年轻代的采集过程。

　　为了确定收录年轻代集合CSet的老年代分区，JVM通过参数最大混合周期总数-XX：G1MixedGCCountTarget（默认8)，堆浪费百分比-XX：G1HeapWastePercent（默认5 %). 通过候选老年代的分区总数和混合循环的最大总数决定了每次收录在CSet中的最小分区数；根据堆浪费的百分比，当集合达到参数，不会开始新的混合采集，并且每次将partition添加到CSet中，都会根据计算出的GC效率进行安排。

　　2.4.3 并发标记算法（三色标记法）

　　cms和G1使用相同的算法进行并发标记：三色标记法，使用白、灰、黑三种颜色来标记对象。白色没有标记；灰色本身是被标记的，被引用的对象是未标记的；黑色本身和引用的对象都被标记。

　　

　　2.4.5 缺少标签问题

　　在重新标记过程中，黑色指向白色，如果不重新扫描黑色，则会丢失标记。白色 D 对象将被回收，因为没有对它的新引用。

　　

　　在并发标记过程中，Mutator 将所有引用从灰色删除为白色，这将导致标记丢失。这个时候应该回收白色物体

　　标签不足问题有两个条件：

　　1.黑色物体指向白色物体

　　2.灰色物体对白色物体的引用消失

　　因此，要解决缺少标签的问题，可以打破两个条件之一：

　　跟踪黑到白的增加

　　增量更新：增量更新，注意引用的增加，remark黑色到灰色，下次重新扫描属性。cms 使用此方法。记录灰到白的消失

　　开头的SATB快照：注意删除引用。当灰色 -> 白色消失时，将引用推送到 GC 堆栈，以确保白色仍然可以被 GC 扫描。G1 使用这种方法。

　　为什么G1采用SATB而不是增量更新？

　　因为使用增量更新后，将黑色重新标记为灰色后，还得重新扫描之前的扫描，效率太低。

　　G1有RSet配合SATB。Card Table记录了RSet，RSet记录了其他对象指向自己的引用，这样就不需要扫描其他区域，只需扫描RSet即可。

　　也就是说，当灰色->白色参考消失时，如果没有黑色->白色，则将参考压入堆栈，在下次扫描时获取参考。由于RSet的存在，不需要扫描整个堆来找到白色的引用引用，效率比较高。SATB 和 RSet 是天作之合。

　　3. G1 活动周期3.1 G1 垃圾回收活动总结

　　

　　3.2RSet的维护

　　由于无法扫描整个堆栈，需要计算分区的确切活动，因此G1需要一种增量全标记并发算法，通过维护RSet来获取准确的分区参考信息。在G1中，RSet的维护主要来自两个方面：Write Barrier和Concurrence Refinement Threads。

　　3.2.1 个屏障

　　

　　我们首先介绍障碍的概念。Fence 是指在原生代码片段中，当某些语句被执行时，fence 代码也会被执行。而G1在赋值语句中主要使用Pre-Write Barrrier和Post-Write Barrrier。事实上，写fence的指令序列开销是非常昂贵的，应用的吞吐量会根据fence的复杂程度而降低。

　　预写屏障

　　当一个赋值语句即将执行时，等式左边的对象会修改对另一个对象的引用，那么等式左边的对象原来引用的对象所在的分区将失去一个引用，那么JVM需要在赋值语句生效前丢失记录 引用的对象。JVM 不会立即维护 RSet，而是通过批处理，将来会更新 RSet（参见 SATB）。

　　写后屏障

　　执行赋值语句时，等式右边的对象得到对左边对象的引用，等式右边的对象所在分区的RSet也要更新。同样为了减少开销，RSet 不会在写屏障发生后立即更新。它也只会记录以后批处理的更新日志（参见并发细化线程）。

　　3.2.2开头的快照（SATB）

　　Taiichi Tuasa 对增量全并发标记算法 Start Snapshot Algorithm (SATB) 的贡献主要是针对标记清除垃圾采集器的并发标记阶段。非常适合G1子块堆结构，解决了cms的主要烦恼：重新标记长时间停顿带来的潜在风险。

　　SATB会创建一个对象图，相当于堆的一个逻辑快照，从而保证并发标记阶段的所有垃圾对象都可以通过快照识别出来。当赋值语句发生时，应用程序会改变它的对象图，然后JVM需要记录被覆盖的对象。因此，write-before 栅栏将在引用更改之前记录SATB 日志或缓冲区中的值。每个线程将独占一个 SATB 缓冲区，最初有 256 个记录空间。当空间用完时，线程会分配一个新的SATB缓冲区继续使用，并将原来的缓冲区加入到全局列表中。最后，在并发标记阶段，Concurrent Marking Threads 会在标记的同时定期检查和处理全局缓冲区列表的记录，然后根据标记位图片段的标记位扫描参考域更新RSet。此过程也称为并发标记/SATB 写前栅栏。

　　在并发标记阶段，应用程序可以修改原创引用，例如删除原创引用。这会导致并发标记结束后存活对象的快照与SATB不一致。G1通过在并发标记阶段引入写屏障来解决这个问题：每当有引用更新时，G1都会将修改前的值写入日志缓冲区（这条记录会过滤掉原来的空引用），扫描SATB中的最后标记阶段以纠正SATB错误。

　　SATB的日志缓冲区和RS的写屏障使用的日志缓冲区一样，有两级结构，作用机制也是一样的。