G1算法详解 | HeapDump性能社区

有哪位大大能详细介绍一下G1算法的原理吗，看了“Garbage-First Garbage Collection”这篇论文，但感觉还是没有搞懂，比如2.2节开头说每个region都对应一个remembered set（以下简称rs），该rs记录所有可能包含指向当前region的指针的位置（which indicates all locations that might contain pointers to (live) objects within the region），但从下文看我怎么觉得rs中记录的应该是那些包含inter-region的指针的位置呢。另外每个collector线程都有一个remembered set log，它和region的rs是什么关系。然后又还有全局的filled RS buffers，等等等等，真的感觉有些乱了。而且论文中作者配的两个介绍原理的图实在太潦草了，完全没有说清楚。
不知有哪位大大搞懂了吗，能否详细解释一下整个算法的过程，谢谢。

参考之前我在另一帖的回复：http://hllvm.group.iteye.com/group/topic/21468#post-272070

使用card table的remembered set，只要card的粒度大于一个word，那它都是不准确的。这种不准确性跟保守式GC的不准确性类似，虽然不影响GC的正确性（活的对象在GC后仍然会式活的），但却会带来一定程度的内存开销（少量死的对象在某次GC后可能还没被回收）。这种死了的对象叫做floating garbage。使用card marking的取舍就是要尽量让mutator快，而collector付出更多代价，消耗内存也增多。

===========================================

至于G1的算法⋯大体概念其实还挺直观的？到底是哪里没明白？

从最高层看，G1的collector一侧其实就是两个大部分：

全局并发标记（global concurrent marking）
拷贝存活对象（evacuation）
而这两部分可以相对独立的执行。

Global concurrent marking基于SATB形式的并发标记。它具体分为下面几个阶段：

1、初始标记（initial marking）：暂停阶段。扫描根集合，标记所有从根集合可直接到达的对象并将它们的字段压入扫描栈（marking stack）中等到后续扫描。G1使用外部的bitmap来记录mark信息，而不使用对象头的mark word里的mark bit。在分代式G1模式中，初始标记阶段借用young GC的暂停，因而没有额外的、单独的暂停阶段。

2、并发标记（concurrent marking）：并发阶段。不断从扫描栈取出引用递归扫描整个堆里的对象图。每扫描到一个对象就会对其标记，并将其字段压入扫描栈。重复扫描过程直到扫描栈清空。过程中还会扫描SATB write barrier所记录下的引用。

3、最终标记（final marking，在实现中也叫remarking）：暂停阶段。在完成并发标记后，每个Java线程还会有一些剩下的SATB write barrier记录的引用尚未处理。这个阶段就负责把剩下的引用处理完。同时这个阶段也进行弱引用处理（reference processing）。

注意这个暂停与CMS的remark有一个本质上的区别，那就是这个暂停只需要扫描SATB buffer，而CMS的remark需要重新扫描mod-union table里的dirty card外加整个根集合，而此时整个young gen（不管对象死活）都会被当作根集合的一部分，因而CMS remark有可能会非常慢。

4、清理（cleanup）：暂停阶段。清点和重置标记状态。这个阶段有点像mark-sweep中的sweep阶段，不过不是在堆上sweep实际对象，而是在marking bitmap里统计每个region被标记为活的对象有多少。这个阶段如果发现完全没有活对象的region就会将其整体回收到可分配region列表中。

Evacuation阶段是全暂停的。它负责把一部分region里的活对象拷贝到空region里去，然后回收原本的region的空间。
Evacuation阶段可以自由选择任意多个region来独立收集构成收集集合（collection set，简称CSet），靠per-region remembered set（简称RSet）实现。这是regional garbage collector的特征。
在选定CSet后，evacuation其实就跟ParallelScavenge的young GC的算法类似，采用并行copying（或者叫scavenging）算法把CSet里每个region里的活对象拷贝到新的region里，整个过程完全暂停。从这个意义上说，G1的evacuation跟传统的mark-compact算法的compaction完全不同：前者会自己从根集合遍历对象图来判定对象的生死，不需要依赖global concurrent marking的结果，有就用，没有拉倒；而后者则依赖于之前的mark阶段对对象生死的判定。

论文里提到的纯G1模式下，CSet的选定完全靠统计模型找处收益最高、开销不超过用户指定的上限的若干region。由于每个region都有RSet覆盖，要单独evacuate任意一个或多个region都没问题。

分代式G1模式下有两种选定CSet的子模式，分别对应young GC与mixed GC：

Young GC：选定所有young gen里的region。通过控制young gen的region个数来控制young GC的开销。
Mixed GC：选定所有young gen里的region，外加根据global concurrent marking统计得出收集收益高的若干old gen region。在用户指定的开销目标范围内尽可能选择收益高的old gen region。
可以看到young gen region总是在CSet内。因此分代式G1不维护从young gen region出发的引用涉及的RSet更新。

分代式G1的正常工作流程就是在young GC与mixed GC之间视情况切换，背后定期做做全局并发标记。Initial marking默认搭在young GC上执行；当全局并发标记正在工作时，G1不会选择做mixed GC，反之如果有mixed GC正在进行中G1也不会启动initial marking。
在正常工作流程中没有full GC的概念，old gen的收集全靠mixed GC来完成。

如果mixed GC实在无法跟上程序分配内存的速度，导致old gen填满无法继续进行mixed GC，就会切换到G1之外的serial old GC来收集整个GC heap（注意，包括young、old、perm）。这才是真正的full GC。Full GC之所以叫full就是要收集整个堆，只选择old gen的部分region算不上full GC。进入这种状态的G1就跟-XX:+UseSerialGC的full GC一样（背后的核心代码是两者共用的）。
顺带一提，G1 GC的System.gc()默认还是full GC，也就是serial old GC。只有加上 -XX:+ExplicitGCInvokesConcurrent 时G1才会用自身的并发GC来执行System.gc()——此时System.gc()的作用是强行启动一次global concurrent marking；一般情况下暂停中只会做initial marking然后就返回了，接下来的concurrent marking还是照常并发执行。

然后G1在mutator一侧需要使用write barrier来实现：

SATB snapshot的完整性
跨region的引用记录到RSet里。
这两个动作都使用了logging barrier，其处理有一部分由collector一侧并发执行。

可以看到在这么多步骤里，G1只有两件事是并发执行的：(1) 全局并发标记；(2) logging write barrier的部分处理。而“拷贝对象”（evacuation）这个很耗时的动作却不是并发而是完全暂停的。那G1为何还可以叫做低延迟的GC实现呢？
重点就在于G1虽然会mark整个堆，但并不evacuate所有有活对象的region；通过只选择收益高的少量region来evacuate，这种暂停的开销就可以（在一定范围内）可控。每次evacuate的暂停时间应该跟一般GC的young GC类似。所以G1把自己标榜为“软实时”（soft real-time）的GC。

但是毕竟要暂停来拷贝对象，这个暂停时间再怎么低也有限。G1的evacuation pause在几十到一百甚至两百毫秒都很正常。所以切记不要把 -XX:MaxGCPauseMillis 设得太低，不然G1跟不上目标就容易导致垃圾堆积，反而更容易引发full GC而降低性能。通常设到100ms、250ms之类的都可能是合理的。设到50ms就不太靠谱，G1可能一开始还跟得上，跑的时间一长就开始乱来了。
这也提醒大家：如果您的程序要长时间运行，那么在技术选型评估GC性能的时候要让测试程序跑足够长时间才能看清状况。多久才够长取决于实际应用要连续运行多久。不然一个要运行一个月才重启一次的程序，如果测试的时候只测了两个小时就觉得没问题，实际上线跑起来可能正好两个半小时的时候来了一次几分钟的full GC暂停，那就纱布了⋯

G1需要暂停来拷贝对象，而CMS在暂停中只需要扫描（mark）对象，那算法上G1的暂停时间会比CMS短么？
其实CMS在较小的堆、合适的workload的条件下暂停时间可以很轻松的短于G1。在2011年的时候Ramki告诉我堆大小的分水岭大概在10GB～15GB左右：以下的-Xmx更适合CMS，以上的才适合试用G1。现在到了2014年，G1的实现经过一定调优，大概在6GB～8GB也可以跟CMS有一比，我之前见过有在-Xmx4g的环境里G1比CMS的暂停时间更短的案例。
合适的workload：CMS最严重的暂停通常发生在remark阶段，因为它要扫描整个根集合，其中包括整个young gen。如果在CMS的并发标记阶段，mutator仍然在高速分配内存使得young gen里有很多对象的话，那remark阶段就可能会有很长时间的暂停。Young gen越大，CMS remark暂停时间就有可能越长。所以这是不适合CMS的workload。相反，如果mutator的分配速率比较温和，然后给足时间让并发的precleaning做好remark的前期工作，这样CMS就只需要较短的remark暂停，这种条件下G1的暂停时间很难低于CMS。

要在拷贝对象的前提下实现真正的低延迟就需要做并发拷贝（concurrent compaction）。但是现在已知的实现concurrent compaction的GC算法无一例外需要使用某种形式的read barrier，例如Azul的C4和Red Hat的Shenendoah。不用read barrier的话，没办法安全的实现一边移动对象一边修正指向这些对象的引用，因为mutator也可以会并发的访问到这些引用。
而G1则坚持只用write barrier不用read barrier，所以无法实现concurrent compaction。

大体概念其实就这样。有许多细节是挺麻烦的，例如如何提高并发减少瓶颈，如何处理收集到一半需要提前终止（abort，例如evacuation failure）的情况，等等。这样在读源码的时候会很头疼，但只是理解大体概念不需要关心到那种细节。

其实影响G1实际性能的许多地方都在细节里，而不在基本算法上。例如整个开销-收益模型，收集时机的预测模型，选取CSet的策略等等。影响用户对G1做性能调优的也是在这些地方。可惜现在的G1在这些细节上做得仍然不算很好，所以预测得不够准确，性能潜力还无法完全发挥。我每天听同事吐槽感到甚欢乐orz

IBM的Balanced GC，也叫incremental generational GC，其核心概念和基本算法都跟G1 GC非常相似。它也是一个regional garbage collector，使用多层的points-into remembered set，也有相对独立的并行增量式/并发式global marking和partial GC（与G1的evacuation/mixed GC对应）。只是一些实现细节和调优策略有差别而已，例如Balanced GC的global marking用的是incremental update式的write barrier而不是SATB；另外它支持arraylet和in-place compaction（可选不同region间的copy-forward，或同region内的mark-compact）。
关于Balanced GC，可以参考：

===========================================

我猜楼主的困惑的几个主要来源是：
1、对SATB的要求不熟悉
2、对logging write-barrier不熟悉
3、对多层的"points-into" remembered set不熟悉

光读G1的原始论文确实会比较头疼。写得太简单抽象，来龙去脉介绍得不够清楚。
嗯⋯但是我要咋讲解好呢？人家nari3都写了一本完整的书来讲解G1的算法，写得还不错；Monica从使用调优方面写的Garbage First Garbage Collector Tuning也总结得很好。我要在一帖里把问题彻底说清楚感觉挺麻烦。
另外，理解G1所需的基本知识其实在The Garbage Collection Handbook里都说得很清楚，买本来耐心读读就啥都解决了。

就上面的3点来说说吧：

1、SATB，snapshot-at-the-beginning，是维持并发GC的正确性的一个手段。G1 GC的并发理论基础就是SATB，而CMS则是“incremental update”。如果你读到有文章说CMS是SATB的话它肯定说错了。嗯Christine大概太久没关注CMS了⋯

SATB抽象的说就是在一次GC开始的时候是活的对象就被认为是活的，此时的对象图形成一个逻辑“快照”（snapshot）；然后在GC过程中新分配的对象都当作是活的。其它不可到达的对象就是死的了。

很容易知道哪些对象是一次GC开始之后新分配的：每个region记录着两个top-at-mark-start（TAMS）指针，分别为prevTAMS和nextTAMS。在TAMS以上的对象就是新分配的，因而被视为隐式marked。

但是在并发GC里，collector一边动mutator也一边动，如果collector并发mark的过程中mutator覆盖了某些引用字段的值而collector还没mark到那里，那collector不就得不到完整的snapshot了么？

为了解决这个问题就有了SATB write barrier。G1 GC具体使用的是“湯浅”（Yuasa）式的SATB write barrier的变种。它的相关论文是：
Real-time garbage collection on general-purpose machines, Taiichi Yuasa（湯淺太一）

Write barrier是对“对引用类型字段赋值”这个动作的环切，也就是说赋值的前后都在barrier覆盖的范畴内。在赋值前的部分的write barrier叫做pre-write barrier，在赋值后的则叫做post-write barrier。
在HotSpot VM里，在引入G1 GC之前，其它GC都只用了post-write barrier，所以它在源码里没有特别的前后缀；而G1 GC特有的pre-write barrier则在源码里有_pre的后缀，可以留意一下。
C代码

void oop_field_store(oop* field, oop value) {
pre_write_barrier(field);
*field = value; // the actual store
post_write_barrier(field, value);
}

Pre/post-write barrier跟SATB有啥关系呢？

前面提到SATB要维持“在GC开始时活的对象”的状态这个逻辑snapshot。除了从root出发把整个对象图mark下来之外，其实只需要用pre-write barrier把每次引用关系变化时旧的引用值记下来就好了。这样，等concurrent marker到达某个对象时，这个对象的所有引用类型字段的变化全都有记录在案，就不会漏掉任何在snapshot里活的对象。当然，很可能有对象在snapshot中是活的，但随着并发GC的进行它可能本来已经死了，但SATB还是会让它活过这次GC。

所以在G1 GC里，整个write barrier+oop_field_store是这样的：
C代码

void oop_field_store(oop* field, oop new_value) {
pre_write_barrier(field); // pre-write barrier: for maintaining SATB invariant
*field = new_value; // the actual store
post_write_barrier(field, new_value); // post-write barrier: for tracking cross-region reference
}

按照湯浅式SATB barrier的设计，pre-write barrier里面的抽象逻辑应当如下：
C++代码

void pre_write_barrier(oop* field) {
if ($gc_phase == GC_CONCURRENT_MARK) { // SATB invariant only maintained during concurrent marking
oop old_value = *field;
if (old_value != null && !is_marked(old_value)) {
mark_object(old_value);
$mark_stack->push(old_value); // scan all of old_value's fields later
}
}
}

在每次引用关系发生变化时，旧的引用所指向的对象就会被mark上，其子孙也会被递归mark上，这样就不会漏mark任何对象，snapshot的完整性也就得到了保证。

但实际去看G1的论文和代码，会发现它的pre-write barrier却是类似这样的：
C++代码

void pre_write_barrier(oop* field) {
oop old_value = *field;
if (old_value != null) {
if ($gc_phase == GC_CONCURRENT_MARK) { // SATB invariant only maintained during concurrent marking
$current_thread->satb_mark_queue->enqueue(old_value);
}
}
}

这比原本的湯浅式设计少了些东西：没有检查目标对象是否已经mark，也不去对目标对象做mark和扫描它的字段。
实际上该做的事情还是得做，只是不在这里做而已。后面讲到logging barrier的时候就会展开说明了。

（Pre-write barrier的实际代码有好几个版本，其中最简单明白的版本是：
C++代码

// This notes that we don't need to access any BarrierSet data
// structures, so this can be called from a static context.
template <class T> static void write_ref_field_pre_static(T* field, oop newVal) {
T heap_oop = oopDesc::load_heap_oop(field);
if (!oopDesc::is_null(heap_oop)) {
enqueue(oopDesc::decode_heap_oop(heap_oop));
}
}

enqueue动作的实际代码则在G1SATBCardTableModRefBS::enqueue(oop pre_val)。
它判断当前是否在concurrent marking phase用的是：
C++代码

JavaThread::satb_mark_queue_set().is_active()
SATBMarkQueueSet只有在concurrent marking时才会被置为active。
）

CMS的incremental update设计使得它在remark阶段必须重新扫描所有线程栈和整个young gen作为root；G1的SATB设计在remark阶段则只需要扫描剩下的satb_mark_queue。

2、logging write barrier

为了尽量减少write barrier对mutator性能的影响，G1将一部分原本要在barrier里做的事情挪到别的线程上并发执行。
实现这种分离的方式就是通过logging形式的write barrier：mutator只在barrier里把要做的事情的信息记（log）到一个队列里，然后另外的线程从队列里取出信息批量完成剩余的动作。

以SATB write barrier为例，每个Java线程有一个独立的、定长的SATBMarkQueue，mutator在barrier里只把old_value压入该队列中。一个队列满了之后，它就会被加到全局的SATB队列集合SATBMarkQueueSet里等待处理，然后给对应的Java线程换一个新的、干净的队列继续执行下去。

并发标记（concurrent marker）会定期检查全局SATB队列集合的大小。当全局集合中队列数量超过一定阈值后，concurrent marker就会处理集合里的所有队列：把队列里记录的每个oop都标记上，并将其引用字段压到标记栈（marking stack）上等后面做进一步标记。

3、“Points-into” remembered set

G1 GC的heap与HotSpot VM的其它GC一样有一个覆盖整个heap的card table。
逻辑上说，G1 GC的remembered set（下面简称RSet）是每个region有一份。这个RSet记录的是从别的region指向该region的card。所以这是一种“points-into”的remembered set。

用card table实现的remembered set通常是points-out的，也就是说card table要记录的是从它覆盖的范围出发指向别的范围的指针。以分代式GC的card table为例，要记录old -> young的跨代指针，被标记的card是old gen范围内的。

G1 GC则是在points-out的card table之上再加了一层结构来构成points-into RSet：每个region会记录下到底哪些别的region有指向自己的指针，而这些指针分别在哪些card的范围内。
这个RSet其实是一个hash table，key是别的region的起始地址，value是一个集合，里面的元素是card table的index。

举例来说，如果region A的RSet里有一项的key是region B，value里有index为1234的card，它的意思就是region B的一个card里有引用指向region A。所以对region A来说，该RSet记录的是points-into的关系；而card table仍然记录了points-out的关系。

Monica写的Tips for Tuning the Garbage First Garbage Collector里有幅图形象的描述了points-into remembered set的关系，下面引用过来：
Monica Beckwith 写道

为了维持这种RSet，G1 GC的post-write barrier的抽象逻辑需要做下面的事情：
(暂时忽略hot card的特殊处理，同时忽略evacuation已经开始之后对collection set内的card的特殊处理）
C代码

void post_write_barrier(oop* field, oop new_value) {
uintptr_t field_uint = (uintptr_t) field;
uintptr_t new_value_uint = (uintptr_t) new_value;
uintptr_t comb = (field_uint ^ new_value_uint) >> HeapRegion::LogOfHRGrainBytes;
if (comb == 0) return; // field and new_value are in the same region
if (new_value == null) return; // filter out null stores
// Otherwise, add to remembered set
// first, add to card table
volatile jbyte* card_ptr = card_for(field); // get pointer to the card for this field
// in generational G1 mode, skip dirtying cards for young gen regions,
// -- young gen regions are always collected
// if (*card_ptr == g1_young_gen) return;
if (*card_ptr != dirty_card) {
// dirty the card to reduce the work for multiple stores to the same card
*card_ptr = dirty_card;
// clean the card the get ready to do the real work
*card_ptr = clean_card;
// find the memory region representing the card
HeapWord* start = $card_table->addr_for(card_ptr);
HeapWord* end = start + CARD_SIZE_IN_WORDS;
MemRegion* dirty_mem_region(start, end);
// and find the G1 heap region containing the card
HeapRegion* from_region = $g1_heap->heap_region_containing(start);
// scan all reference fields in dirtied region
foreach (oop from_obj in dirty_mem_region) {
foreach (oop* f in from_obj->oop_fields()) {
oop to_obj = *f;
HeapRegion* to_region = $g1_heap->heap_region_containing(to_obj);
if (from_region != to_region) {
CardIdx_t from_card = from_region->card_index_for(card_ptr);
to_region->remembered_set->add_reference(from_region, from_card);
}
}
}
}
}

可以看到一个region的RSet是如何与card table里的card关联在一起的。
中间有一处“奇怪”的代码，把card给涂黑然后又马上清掉。这在实际代码里其实是在两个不同线程上做的：在mutator线程上把card给dirty了之后加到一个队列里，然后ConcurrentG1RefineThread从队列里把card拿出来之后再置为clean。上面是为了把整体过程放在一起方便说明所以写成这样。
另外还有一部分注释掉的关于分代式G1模式的代码，这部分代码的作用就是过滤掉从young gen region出发的引用涉及的RSet维护。G1的论文讲解的基本算法是不分代的纯G1（pure garbage-first）只是简单提到了有分代式G1（generational garbage-first）。实际在JDK7或以上可以用的只有分代模式的G1，没有可用参数选择纯G1模式。为了贴合原始算法描述，这里就把分代相关的处理列出来但注释掉。

每次向引用类型字段赋值都要经过这么多步骤来更新RSet的话开销实在太大，而实际G1的实现是类似：
C代码

void post_write_barrier(oop* field, oop new_value) {
uintptr_t field_uint = (uintptr_t) field;
uintptr_t new_value_uint = (uintptr_t) new_value;
uintptr_t comb = (field_uint ^ new_value_uint) >> HeapRegion::LogOfHRGrainBytes;
if (comb == 0) return; // field and new_value are in the same region
if (new_value == null) return; // filter out null stores
// Otherwise, log it
volatile jbyte* card_ptr = card_for(field); // get address of the card for this field
// in generational G1 mode, skip dirtying cards for young gen regions,
// -- young gen regions are always collected
// if (*card_ptr == g1_young_gen) return;
if (*card_ptr != dirty_card) {
// dirty the card to reduce the work for multiple stores to the same card
*card_ptr = dirty_card;
// log the card for concurrent remembered set refinement
JavaThread::current()->dirty_card_queue->enqueue(card_ptr);
}
}

这是logging barrier在G1 write barrier上的又一次应用。

跟SATB marking queue类似，每个Java线程有一个dirty card queue，也就是论文里说的每个线程的remembered set log；然后有一个全局的DirtyCardQueueSet，也就是论文里说的全局的filled RS buffers。
实际更新RSet的动作就交由多个ConcurrentG1RefineThread并发完成。每当全局队列集合超过一定阈值后，ConcurrentG1RefineThread就会取出若干个队列，遍历每个队列记录的card并将card加到对应的region的RSet里去。

先写到这里，有啥问题我再更新到这个回复来。