在吸取了前辈 CMS 的经验教训之后, G1 的设计团队最终以一种脱胎换骨的姿态重磅推出了具有划时代意义的 Gabage First 收集器;
跳脱出 jvm 历史 GC 框架的局限性从 0 开始重新设计, G1 引入了 Region、Card、RSet 等多种创新性的数据结构, 极大地提升了年轻代及局部老年代收集的效率, 而这些设计思想也为后续的 ZGC、Shenandoah、Dragonwell Jade 等更先进的收集器所吸收采纳;

G1 的数据结构

G1 为了实现高效的垃圾收集, 使用了很多复杂的数据结构以记录并控制内存的使用情况:

Region

G1 将堆划分为一系列大小不等的内存区域, 称为 Region, 每个 Region 大小为 1 ~ 32M, 且必须是 2 的幂次方:

  • 2 的幂次方大小可以确保堆区域的起始地址和结束地址对齐到特定的边界, 这有助于提高内存访问效率, 对齐后 CPU 可以更高效地访问内存, 减少缓存未命中和内存碎片;
  • G1 内部使用位运算来管理堆区域, 2 的幂次方大小使得这些运算更高效;
G1 Heap Region
G1 Heap Region

虽然 Eden、Survivor、Old 的概念和传统收集器类似, 但 G1 的内存管理是以 Region 为单位的, 这为更精细的内存回收提供了可能, 而不像传统 GC 只能以整个 Young 区 / Old 区为单位进行回收, 粒度很粗, 回收时长不容易控制;

G1 Heap Region
G1 Heap Region

Card

G1 对 Region 内部的空间做了更进一步的精细管理:

  • G1 将 Region 按照 512 Byte 为单位划分成多个 卡 (Card);
  • G1 定义了一个全局字节数组 卡表 (Card Table), 其中的每个字节元素都唯一映射到 Region 中的一个 Card (稀疏索引);
    卡表的元素有两种值:
    • 0 (Clean Card): 表示该 Card 内的对象对其他 Region Card 的引用关系已经全部更新到了 RSet;
    • 1 (Dirty Card): 表示该 Card 内的对象对其他 Region 的引用关系发生了新的变更, 暂未同步到 RSet;
  • 因为 Region 是连续分配的, 所以当给定任何一个对象的内存地址, 都可以快速定位到其在卡表中的索引 Card Index: $\frac{addr(instance) - addr(heap_start)}{512B}$;
G1 Card Table
G1 Card Table

需要注意的是: 卡表本身不是目的, G1 引入卡表是高效维护 Remember Set 的一种手段, 这一点在下一小节将会详细介绍;

Remember Set

记忆集 (Remember Set) 简称 RSet, 是一个哈希表结构:

  • key: 引用本 Region 的其他 Region 的起始地址;
  • value: 本 Region 中被 key 对应的 Region 引用的 Card Index 索引位置;
G1 RSet
G1 RSet

每一个 Region 都有自己的 RSet, 于是当给定了一个 Card, 我们通过其对应的 RSet 可以非常高效地查询到哪些 Region 引用了目标 Card 中的对象;
理论上 RSet 应该记录任何跨 Region 的引用关系, 但实际上 G1 做了特定的优化, 并不会全部记录; 我们将 Region 按照代际划分, 那么 RSet 的引用关系可以分为四类:

  1. 年轻代 Region 引用 年轻代 Region
  2. 年轻代 Region 引用 年老代 Region
  3. 年老代 Region 引用 年轻代 Region
  4. 年老代 Region 引用 年老代 Region

其中 G1 不会记录年轻代 Region 对其他 Region Card 的引用关系, 也就是不会记录上述第 1、2 种类型:

1
2
3
4
5
6
7
void HeapRegionRemSet::add_reference(oop* from, HeapRegion* from_hr) {
  if (from_hr->is_young()) {
    // 如果引用来自年轻代，则不需要记录
    return;
  }
  _other_regions.add_reference(from, from_hr);
}

因为 RSet 的主要使用场景有两种 (后面章节会详细说明):

  1. 在 Young GC 时, 跳过对 被老年代 Region 引用的 年轻代对象的扫描, 根据 RSet 直接执行快速标记, 从而降低整体标记阶段的开销;
  2. 在 Mixed GC 时, 跳过对 被其他老年代 Region 引用的 需要收集的老年代对象的扫描, 根据 RSet 直接执行快速标记, 从而降低整体标记阶段的开销;

无论是什么类型的 GC, G1 本来就会扫描整个年轻代, 不存在需要通过 RSet 排除某些年轻代对象的场景, 额外记录年轻代 Region 对其他 Region Card 的引用关系反而会占用更多的内存;

RSet 的三级结构

RSet 并非永远都会记录 Region => Card Index 的关系, 因为 RSet 本质是一个哈希表, 当表中某个 slot 冲突严重, 就会发生退化:

RSet level
RSet level

  • 无退化场景 (最细粒度): regionId => cardIndex (数组);
  • 无损压缩退化 (中等粒度): regionId => cardIndex (bitmap, 仅压缩, 信息不会丢失);
  • 有损压缩退化 (粗粒度): regionId => 是否引用了当前 Region 中的对象 (布尔值);

G1 的收集过程

从宏观框架上看, G1 和 CMS 有着类似的思路, 都经历了几个经典过程: 初始标记、并发标记、最终标记、回收; 但在实现细节上, G1 相比 CMS 的差异就十分巨大了, 基于更精细的数据结构和引用关系追踪算法, G1 以空间换时间, 获得了比 CMS 更高的回收效率;
在展开 G1 的详细收集过程之前, 需要先讨论一下 G1 的写屏障实现思路:

G1 的写屏障

与 CMS 类似, 为了能与用户线程并发执行, G1 的收集也使用了三色标记法, 这意味着 G1 也必须要有自己的方案解决三色标记的漏标和多标问题;
与 CMS 使用 Incremental Update 聚焦于引用源头的写屏障不同, G1 垃圾收集器将写屏障拆分成了 写前屏障 (Pre-Write Barrier) 和写后屏障 (Post-Write Barrier), 它们的用途和触发时机不同, 共同协作实现了比 CMS 更加高效的并发垃圾回收;

写后屏障

G1 写后屏障的主要作用是维护 RSet (具体手段是通过标记 Card Table 再间接维护 RSet), 这是一个在整个 jvm 生命周期内都一直启用的特性;
当 jvm 执行到下面这个语句:

1
2
// 假设 oldObj 位于老年代 Region, newObj 位于年轻代 Region 
oldObj.field = newObj;

以上语句会改变 oldObj.field 的引用值, jvm 需要及时维护 newObj 对象所属 Region 的 RSet: 将 oldObj 对象所在的 Region 引用到 newObj 对象所属的 Card Index;
为了尽量减少 java 语句的执行开销, G1 将该逻辑分成了两个部分:

  • 第一部分: 引用变更发生后, 先做标记, 而不做真正处理 (相对轻量的操作):

    • 先将 oldObj 所在的 Card 标记为 Dirty Card:
      dirty card
    • 再将该 Dirty Card 放入脏卡队列 (Dirty Card Queue, DCQ):
      • 优先加入当前线程的本地队列 (DirtyCardQueue);
      • 当本地队列已满, 将本地队列的脏卡刷入全局队列 (DirtyCardQueueSet, DCQS), 并申请新的本地缓存;
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        void G1BarrierSet::write_ref_field_post(void* field, oop new_val) {
            if (new_val != NULL) {
                // 标记脏卡
                CardTable::card_mark(field);
                // 将脏卡加入队列
                G1ThreadLocalData::dirty_card_queue(Thread::current()).enqueue(field);
            }
        }

        void G1DirtyCardQueueSet::enqueue(void* card) {
            // 优先将脏卡加入本地队列
            _queue->enqueue(card);
            if (_queue->is_full()) {
                // 如果本地队列已满，刷入全局队列
                flush();
            }
        }

  • 第二部分: 使用指定线程消费 Dirty Card Queue (相对重量的操作):

    • G1 会根据全局队列 DCQS 的容量变化自适应决定脏卡消费处理的线程数量:
      DCQ 状态
      • 当队列容量水位很低, 处于上图白色区域时: 没有线程会消费队列;
      • 当队列容量进入上图绿色区域时: G1 中专门用于消费 DCQS 的线程 Refinement 被激活, 可以用 -XX:G1ConcRefinementGreenZone=N 指定该阶段的线程数量;
      • 当队列容量进入上图黄色区域时: 说明产生 Dirty Card 的速度过快, G1 将激活更多的 Refinement 线程, 可以用 -XX:G1ConcRefinementYellowZone=N 指定该阶段的线程数量;
      • 当队列容量进入上图红色区域时: 队列即将溢出, 除了 Refinement 之外, 用户线程 (Mutator Thread) 也会一起参与消费 DCQS 处理脏卡;
        注意: 为了保障引用变更写屏障的高效和轻量, 用户线程参与处理脏卡, 依旧会先将脏卡放入队列, 后续再异步从队列中取出脏卡处理;
    • 当 G1 Refinement 线程取出一个 Dirty Card 的处理逻辑:
      • 先反向定位出该 Card 所在的 Region;
      • 再扫描该 Card 中的每一个对象, 找出每个对象所引用的其他对象, 根据被引用对象的地址定位出 Card Index;
      • 根据上面两个步骤, 便可以建立 Region => Card Index 的引用关系, 更新到 RSet;

写前屏障

G1 的写前屏障通过 SATB (Snapshot-At-The-Beginning) 实现, 这是一个只在 G1 开始执行垃圾收集才激活的特性; SATB 的发明者 Taiichi Yuasa 用两句话概括了该算法的核心思想:

  1. Anything live at Initial Marking is considered live.
  2. Anything allocated since Initial Marking is considered live.

也就是说, 当 G1 开始新的一轮收集时, 在开始时刻之前还活着的对象、以及开始时刻之后新创建的对象, G1 都认为是活着的, 不会被当前收集轮次给清理掉, 所以这个算法的名字很形象: 初始时刻快照;
虽然名字叫快照, 但是 SATB 并不是真正遍历去建立一个关于所有存活对象的物理快照 (如果那样就太耗费时间了, 而且还得 stw 才能准确构建不重不漏), 它以一种轻量级的方式对堆中的对象图建立了一个逻辑快照:

  1. 在一个 GC 周期中, 如果创建了一个新对象, 那么不管它后续是否死掉, 本次 GC 都认为它存活;
  2. 在一个 GC 周期中, 如果某个存活对象的引用从未被修改, 那么它最终一定能被三色标记法成功标记, 我们不需要额外干涉;
  3. 在一个 GC 周期中, 一个之前就死掉的对象一定不会被三色标记法给标记到, 我们也不需要额外干涉;
  4. 在一个 GC 周期中, 如果某个对象的引用被切断了 (比如从 obj.a = b 变成了 obj.a = null 或 obj.a = c, 则 obj 对 b 的引用被切断), 证明其在切断前 (收集初始时刻) 一定是存活的 (否则将不可达, 也就不会有被切断的机会), 那么需要主动将该对象 (b) 及其成员逐一标记;

 
要实现以上逻辑, 主要有两个关键点:

  • 针对上文第 (1) 点: 我们需要一个高效的方案快速排除本轮 GC 中新建的对象, 将收集区域限定在旧对象里: 鉴于 G1 使用的是标记整理算法, 可以在给定空间里顺序分配对象, 那么在一个 region 中我们便可以引入几个指针:

    • BOTTOM: 指向当前 region 的起始地址;
    • TOP: 指向当前 region 分配下一个新对象的起始地址;
    • TAMS: Top-At-Mark-Start, 在标记开始时 TOP 指针指向的地址;
      G1 TAMS
      G1 TAMS
      在新一轮 GC 启动, 进行初始标记时, 将 TOP 赋值给 TAMS, 那么在整个 GC 周期期间分配的新对象都落在 [TAMS, TOP) 之间, G1 直接对这个区间内的对象做隐式标记, 而只在 [BOTTOM, TAMS) 区间内应用三色标记, 就可以实现上文第 (1) 点;

  • 针对上文第 (4) 点: 首先我们可以明确地发现, 只有 [BOTTOM, TAMS) 区间内的对象会遇到相关问题; 与写后屏障类似, 为了尽量减少 java 语句的执行开销, 以及尽可能快速执行并发标记, G1 将 “主动标记被切断引用的对象” 这个逻辑分成了两部分:

    1. 引用变更之前: 只将目标引用放入目标队列, 而不做真正处理 (相对轻量的操作):

      1
      2
      3
      4
      5
      6
      7
      8
      // 用伪代码表示该逻辑
      void pre_write_barrier(oop* field) {
          oop old_value = *field;
          if (old_value != null && is_marking_active()) {
              // 将旧引用加入 SATB 队列, 确保后续扫描
              satb_queue.push(old_value);
          }
      }

    2. 在最终标记 (Remark) 阶段消费 SATB 队列, 取出旧引用并对其及其成员做真正的重新标记 (相对重量的操作);

 
总体来看, SATB 以极小的代价解决了漏标问题, 但也同时导致多标问题变得更严重: 因为某个对象的引用被切断了, 只要后续没有再被其他对象引用, 那这个对象确实就不可达了, 可当前轮次的 GC 并不会将其回收, 只能等下一次 GC 了;
其实如果将写前屏障与 RSet 结合起来, 就可以很大程度上缓解多标问题了: 只需在写前屏障第二阶段做 Remark 时:

  1. 取出旧引用, 计算其所属 Region 和所属 Card Index;
  2. 遍历 Region 对应的 RSet, 判断是否存在目标 Card Index 的引用关系:
    • 如有: 说明该对象很可能后续又被其他对象引用 (并不能 100% 肯定, 因为 RSet 的记录粒度最多只到 Card, 而一个 Card 内可能有多个对象), 本轮可以对其做标记;
    • 如没有: 说明该对象已不可达, 不应对其标记;

上述优化思路在某些资料中有描述, 但笔者并未找到 jvm 使用该方案的直接证据, 故将其作为额外补充记录下来;

Young GC 流程

Young GC 主要针对年轻代 Region, 包括 Eden 和 Survivor; 当所有 Eden 区使用率达到了最大阈值 (默认 60%) 或者 G1 计算出来的回收时间接近用户设定的最大暂停时间时, 会触发 Young GC; G1 的 Young GC 是全程 Stop-The-World 的, 且一次 Young GC 会回收全部年轻代 Region;
Young GC 的流程:

  1. 初始标记 (Initial Mark): 从合并过 RSet 的 GC Roots 出发遍历标记所有存活的新生代对象
    • 部分线程直接从 GC Roots 开始扫描标记;
      • 注意: 需要过滤掉指向老年代对象的 GC Roots: 因为可以使用 RSet 更高效地获取被老年代引用的年轻代对象;
    • 部分线程排空 Dirty Card Queue: 把存量引用关系更新到 RSet, 再将 RSet 映射中记录的 Card Index 对应的对象作为 GC Roots 继续扫描标记;
  2. 并发复制:
    • 对象年龄 < 15: 复制对象到 Survivor Region, 记录对象年龄 + 1;
    • 对象年龄 = 15: 晋升复制到 Old Region;
  3. 清理垃圾;

Mixed GC 流程

Mixed GC 是 G1 特有的收集类型, 它会收集所有的 Young Region + 收益高的若干个 Old Region;

1
2
3
# 触发 全局并发标记 的已分配内存占整堆大小的比例, 简称 IHOP, 默认 45 (单位是 %)
# 关于已分配内存: jdk 8 之前是整体使用量; jdk 8 之后是老年代使用量
-XX:InitiatingHeapOccupancyPercent=n

当已分配的内存占内存总量比例超过了 IHOP 设置的阈值, 将会启动一轮 Global Concurrent Marking; 相比于 Young GC 的 stw, 全局并发标记因为涉及 Old Region, 其执行时间必然会远超 Young GC, 便不能再全程阻塞用户线程了, 对此 G1 使用了允许部分阶段与用户线程并发执行的策略, Global Concurrent Marking 的主要阶段和停顿类型如下:

阶段 停顿类型 注释
Initial Mark stw 复用了 Young GC 的 stw
Concurrent Mark concurrent
Remark (Final Mark) stw
Cleanup stw 并非真实清理, 而是统计标记为活的对象

当已分配内存达到 IHOP 阈值时, 仅仅是触发了 Global Concurrent Marking, 而非真正的 Mixed GC, Mixed GC 的触发时机还受到以下几个条件的限制:

  1. -XX:G1HeapWastePercent: 允许垃圾大小占内存的最大比例, 当低于此值时不会触发 Mixed GC;
  2. -XX:G1MixedGCLiveThresholdPercent: 老年代 Region 中的存活对象的占比, 只有在此参数之下才会被选入 Collection Set;
  3. -XX:G1MixedGCCountTarget: 一次 Global Concurrent Marking 之后, 最多执行 Mixed GC 的次数;

我们可以设置一次 Mixed GC 需要回收的 Old Region 数量占比:

1
2
# 默认是 8: 意味着要在 8 次以内回收完所有的 Old Region
-XX:MixedGCCountTarget

极端场景: Full GC

当 Mixed GC 实在无法跟上程序分配内存的速度, 导致老年代填满无法继续进行 Mixed GC, 就会使用 Serial Old GC (后来被优化为多线程, 但相比 Mixed GC 依旧很慢) 来收集整个堆:

gc phase state transform
gc phase state transform

G1 实战

相关选项

通用选项:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 开启 g1 收集
-XX:+UseG1GC

# 设置最大暂停时间 (默认 200 ms)
-XX:MaxGCPauseMillis=n

# 指定Region的内存大小, n 必须是 2 的幂次方, 其取值范围是从 1M 到 32M
-XX:G1HeapRegionSize=n

# 指定垃圾回收工作的线程数量, 8 核机器默认 5 个线程
-XX:ParallelGCThreads=n
# 默认值跟随 -XX:ParallelGCThread
-XX:ConcGCThreads=N

诊断选项:

1
2
3
# 开启并发标记阶段的时间消耗记录诊断
-XX:+UnlockDiagnosticVMOptions
-XX:+G1SummarizeConcMark

GC 线程

  • STW 线程:

    • 线程名: GC Thread#{n}
    • 作用:
      • young gc;
      • mixed gc;
    • 设置方式:
      1
      -XX:ParallelGCThreads=N

  • 并发线程:

    • 线程名: G1 Conc#{n}
    • 作用:
      • concurrent mark;
      • 并发清理;
      • 并发引用处理;
    • 设置方式:
      1
      -XX:ConcGCThreads=N

参考资料