文章>G1算法详解>

G1算法详解原创

2周前
1891115

有哪位大大能详细介绍一下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里去。

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

原帖地址:https://hllvm-group.iteye.com/group/topic/44381

请先登录,再评论

R大 yyds~

11周前

为你推荐