《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 老鸡 「老鸡」欢迎转载,保留摘要,谢谢!


🙂🙂🙂关注微信公众号:【芋道源码】有福利:

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言将得到认真回复。甚至不知道如何读源码也可以请教噢
  4. 新的源码解析文章实时收到通知。每周更新一篇左右
  5. 认真的源码交流微信群。

前言

很多程序员是从java语言中对“垃圾收集“有了一个印象和认识,但是垃圾收集这个概念其实早在1959年左右就被美国计算机科学家John McCarthy为了简化Lisp语言中的内存管理所发明出来的。

不论是从1960年以前人们为Lisp语言首先想到的“引用计数法”,

还是到1960年提出并成功运用于Lisp语言中的“标记-清除法”,

亦或是M. L. Minsky在1963年提出的“复制算法”。

从1970年开始,人们逐渐意识到一个理想的垃圾收集器不应该像“标记清除”算法般效率低下;

也不该像复制算法般牺牲大量内存,更不能长时间打断应用程序的执行;

所以1970到1985年之间,科学家们深入研究分析,不断的喷薄而出着优秀的垃圾收集算法,比如标记整理、增量收集、分代算法……

正文

在每日优鲜这种高频次的交易电商中,“低延迟高可用“是我们一直在极致追求的性能目标。就比如在每日优鲜首页上的某些接口要求100ms以内能够响应,且可用性必须保证4个9,其实这个要求并不过分,因为你永远不知道一个错误或者一次延时会带来多少用户的丢失甚至支付转换率的降低。而因为有了STW(stop the world)的存在,将会导致这种问题的可能性被放大(如下图)

图片

为何选择G1?

其实从上图的例子中我们会发现一个问题,有时候我们期望系统在进行垃圾收集的过程中能够满足“软实时性”。而纵观G1之前的垃圾收集器(并行GC、并发GC、增量GC等)都是在不断的尝试缩短最大暂停时间,而缩短最大暂停时间就很有可能导致吞吐量的下降,同时G1之前的垃圾收集器是无法像G1一样可以预测暂停时间的。这就很有可能会发生如上图的场景,因为应用系统垃圾收集的长时间停止,导致接口响应时间增加,降低了用户体验。

(tips:可能会有一些同学说,那我选择进行GC调优,让他满足我的要求呗,但其实复杂度相对比较高的电商场景的业务和流量是千变万化,风云莫测的,在你所认为已经调优好的情况下,很有可能在下一次的业务迭代或是任何一次线上突发的流量异常就会失效!)

软实时性

而“软实时性”是什么意思呢?我会先举一个“硬实时性”的例子,在医院的抢救病人使用的核心系统,即使是有1ms的延迟,那么将会带来非常严重的后果,所以这一类的系统,我们对他的要求是“硬实时性”,就说是你必须要严格保证实时性。

那这样子我们就很好理解“软实时性”了,不需要你严格保证,可以允许超出最后期限(deadLine)几次,但这个超出的次数一定是要在用户的可容忍范围之内,这就是软实时性

G1其实是通过如下两种手段去保证软实时性的:

1.支持用户自定义应用系统暂停时间的功能,尽量保证处理时间不超过用户定义的这个暂停时间

2.通过预测下一次GC会让应用系统暂停多长时间的功能,如果预测出来时间太长了,它会通过一些拆分GC目标对象和延迟执行GC的手段来保证去尽量能够达到用户自定义的暂停时间

(tips:当然,不少同学认识G1可能是听闻他的设计很适合处理大堆,并能够高效率利用服务器多核的性能,同时并不会降低GC的性能,这也是他很核心的一个特点)

G1的原理分析

缘起

图片

从G1的wiki中我们得知,G1垃圾收集算法是在Java6中引入,Java7中开始支持,Oracle想用G1来代替CMS,当然在Java9中已经将G1设置为默认的垃圾收集算法了。

一切缘起于始,善始者实繁,克终者盖寡

后面的内容将以OpenJDK7的代码作参考(当然一些很基础的概念在这里我不会再详细讲了,可以直接参考我公 众 号的另一篇文章<再见JVM> 和哔哩哔哩的视频的<再见JVM>),我们今天主要分析G1的以下内容

图片

1.G1GC堆的结构

首先我们要知道的一个基础概念是G1GC中的堆的结构长这样(如下图)

图片

G1GC中将一块连续的堆划分为了一个个区域(region),每个区域默认的大小是1MB,每个区域中塞入了各式各样的对象,剩下的区域就是空闲区域。

图片

从上述代码中,我们能看到他有这么几个参数

MIN_REGION_SIZE = 1MB(最小的regionSize)

MAX_REGION_SIZE= 32MB(最大的regionSize)

TARGET_REGION_NUMBER = 2048(堆中的的region数量)

继续往下看293行,这里拿最小的堆内存(也就是我们设置的-Xms的大小)除TARGET_REGION_NUMBER(2048),然后和MIN_REGION_SIZE(1MB)两者之间取大的那个。我们其实可以看到他将堆分成了均等的2048块区域,然后从1MB和拆分完的区域的大小里面取较大的那个。

当然为什么取-Xms的堆大小,而不是拿-Xmx的堆大小去除2048?

这里的原因作者也给出来了,说是怕有人这么设置(-Xms128m -Xmx32g),这样就会有问题。

然后我们看下301行,将算出来的区域的大小向上取2的指数幂。(其实在这里我们会发现很多jdk的数据结构里都有这种操作)

最后304行是作者用来确保区域的大小不会小于最小的1MB,同时要要求他不超过最大的32MB。

2.并发标记

2.1.初始标记-创建位图

我觉得大部分同学应该都知道初始标记干了些什么事?即使没有了解它做的意义,也应该会被各种面试逼的背概念。没错,初始标记的过程其实就是标记一下GC Roots能直接关联到的对象

当然G1并不是这样,他还会在这个操作之前先干点事情!为每一个区域创建两个位图(NextBitmap和PrevBitmap),那长什么样子呢?(如下图-论文图)

图片

当然这是论文中的原图,不好理解,于是我又自己画了一版好理解的图(如下图-手画图)

图片

NextBitmap(本次进行标记的位图)和PrevBitmap(上次标记位图的结果)。我们可以看到在G1堆中有6个对象,我们现在分别假设这6个对象的大小是(16个字节,24个字节,8个字节,8个字节,24个字节,16个字节)。我们假定以8个字节的那个对象为位图中的一位(也就是一个Bit),所以大家可以看到如上图,第一个对象对应2个比特位,第二个对应3个比特位,第三个对象对应1个比特位。这里的top指针指代的是这些区域内对象的开头bottom则指代的是这些区域內对象的结尾nextTAMS表示的是本次标记开始时间的top位置prevTAMS表示的是上次标记开始时间的top位置。如果对象是活的,那么它对应的位图的标记就是1(红色);如果对象是死的,那么它对应的位图的标记就是0(蓝色)。当然一个对象对应多个位图的时候,只要标记起始位置(mark bit)即可。(如图中24个字节的那个对象,它对应三个位,当他是存活的时候,只需要标记第一个位置的位图即可)。

好,我们再来回顾一下这个过程(参照上图的论文图)

A步骤:第一次初始标记,创建了一个本次标记位图(NextBitmap),当然因为之前不存在GC,所以上一次标记位图到(PrevBitmap)是个空的

B步骤:大家可以看到堆中的对象貌似增多了,这是因为在并发标记的过程可能有新的对象进入,但是没关系,我们上面说了NextTAMS就是用来记录本次GC标记的初始位置的,所以你会发现NextTAMS还是在原来的位置。然后这个过程就是给位图上进行标记,活的染黑,死的就还是白色

C步骤:到GC的尾声阶段,开始执行一些清理操作,会将当前位图NextBitmap和PrevBitmap对调一下,于是NextBitMap就变成空的了,为下一次的GC作准备。而PrevBitmap就变成了我们本次GC存留下来的结果。这时候PrevTAMS指向了我们这次GC一开始的NextTAMS的位置,nextTAMS指向了bootom的位置。

D步骤:这时候就来到了一次新的GC循环,首先创建位图(NextBitmap),然后将NextTAMS指向本次开始标记的位置。

E步骤和F步骤循环往复,这里就不强调了。

这里要说明一点GC线程为每个区域创建位图的这个过程是和应用线程并发进行的。

课外题:大家可以思考一个问题,为什么GC的分代年龄要放在对象头中(4个bit位)记录,而对象的生于死的标记却放在位图中?

2.2.初始标记-根扫描

图片

一图解千言,其实很简单就是暂停mutator线程(应用线程)让GC线程对根直接引用的对象进行扫描,也就是图中红色的线,由GCRoot出发标记到那个可以直接扫描的红色对象。

那我们可不可以不暂停mutator线程(应用线程)就让它完成根扫描呢?

不可以,G1中有一门功夫叫做写屏障(write barriers),它可以感知对象的修改变更,但是大多数GCroot并不是对象,所以他们的修改并不能被感知到,而且GCroot有时候会需要频繁的修改。作者也是两者权衡之下觉得还是通过暂停mutator线程会有比较好的性能

2.3.并发标记

总结一句话就是扫描在初始标记中被标记过的对象,并且同时会对大部分存活对象完成标记(可能同学们会有疑问,我第一阶段标记完根,第二阶段不就是把所有根下面的节点都标记一下不就好了,为什么你这里说是大部分存活对象而不是全部呢?别着急,详情可以等到后面看最终标记干了些什么事情?)

我用一张图简单解释下并发标记的样子(如下图)

图片

我们来解释一下这张图,我们可以看到在第一个阶段根扫描标记的过程只把3对象标红,并且在对应的NextBitmap上标记为1(标红),然后我们在看并发标记的过程做了什么?

首先因为这个过程中GC线程和mutator线程是并发的,所以在并发标记的过程中会有新对象产生,就是图中的7和8两个对象,因为他们两的引用关系在标记开始时并不存在,所以我们会看到图中7和8没有对应的位图,而且这种在标记过程中生成的新对象,我们都把它当成“已完成扫描和标记“的对象,所以它的颜色是红色的。然后我们会看到top移动到了最新对象的地方,3引用的子对象1和5都被标记上了,且对应位图已经标红。

但是,我们有没有考虑到这个问题:并发标记的过程是GCThread和mutatorThread并发进行的,如果1和5在这过程中不再被3引用了(被其他对象引用或者没有任何人再引用他),我们是不是标记的就有误了?

那G1又是怎么做的呢?

答案是SATB(snapshot at the beginning),他就是在并发标记开始的时候,将对象之间的引用关系以快照的形式保存下来。

我们看一下论文中是怎么描述它的(如下图)

图片

大致的意思如下图

图片

也就是说,在并发标记的过程中,对象的引用关系发生变化之后,需要记录变化之前的引用关系,而这个SATB**本地队列**是mutator线程各自持有的本地线程队列,所以在执行enqueue(入队操作)不会有竞争的问题,如图,当应用线程1的专用SATB本地队列满了之后会被放到SATB的全局队列集合中。而在并发标记的过程中,GCThread会定期的去检查全局到的SATB队列集合,如果发现里面有队列,那么会将队列中的对象进行扫描和标记。

2.4.最终标记

不知道大家是否还记得上面我说过并发标记的阶段的过程只是对大部分存活对象完成标记。原因就是有可能某些mutator线程的SATB本地队列没有被填满,所以它就不会被放到全局到的SATB队列集合中。所以我们在最终标记阶段要做的就是扫描这些余下的SATB本地队列

图片

我们可以从上图看到,最终标记前和最终标记后的区别:首先mutator线程2的SATB本地队列没有被填满,所以它不会被放到全局SATB的队列集合中,然后它的队列中有对象6的引用,因此在扫描mutator线程2SATB本地队列之后,6以及它的子对象4都会被标记。

当然最终标记的过程是会暂停mutator线程的,因为mutator线程的本地队列是会被mutator操作的。

2.5.存活对象计数

图片

我们可以从论文中得知,这个步骤其实就是统计每个区域的NextBitmap存活对象的字节数,然后将它放入区域内的next_marked_bytes

图片

结束之后如下图

图片

因为对象1、3、4、5、6是活着的所以存活对象的大小是(16+8+8+24+16=72字节),当然新生成的对象7、8并不算在內,prev_marked_bytes是0字节,因为这才是第一次GC。

2.6.收拾残局

其实就是做一些收尾工作,我们看下图

图片

就是GCThread扫描每个区域,将nextTAMS移动到了bottom的位置,prevTAMS移动到了上次并发标记开始的top指针的位置,next_marked_bytes置为0,prev_marked_bytes置为72,将NextBitmap移动到PrevBitmap的地方。当然在这一步的扫描过程中,会去计算每个区域的转移效率,按照降序排序。这里的转移效率是怎么计算的呢?我们后面会讲到。

3.转移

当标记的工作全部结束之后,剩下我们做的事情其实就是开始收垃圾了,那这个收垃圾的过程是什么样子的呢?

将存活对象转移到空闲区域,然后重置原来占用的区域,大概行为就是如下图

图片

我们可以看到转移前,GCroot引用1、1引用2、2引用4,这三个对象都是存活对象,5引用6,但是5和6都是死亡对象。转移之后,将第一块和第二块区域内存活的对象转移到了区域3,然后将区域1和区域2清空,重置为空闲区域。

在讲解转移的步骤之前,我先提出一个问题,就是在分代垃圾回收算法中都会遇到一个问题,就是跨代或者跨区域引用的场景,扫描时需要把整个区域或者老年代放入GCRoots的扫描范围,那G1是通过什么手段去避免这种问题的呢?

答案是Remembered Set(转移记忆集合),我们从下图的论文看看是怎么描述它的?

图片

大概的意思就是通过card table( 卡表)来实现这个转移记忆集合,在堆中每512B对应一个1B的卡表,而卡表是由一个个1B大小的卡片组成的,如下图

图片

这样子我们就能够很快速的确认到堆中某个对象对应卡片的索引地址。

论文中说到每一个区域都关联着一个转移记忆集合,(represented by hashtables)说明是通过散列表来实现的,如下图

图片

图中区域A中的A对象被区域B中的B和D对象引用着,也同时被区域C中的C对象引用着,此时区域A对应的Remembered Set里面的散列表结构如图,key是被引用的区域地址value是被引用对象的卡片索引。到这里我们就大概明白了,区域之间对象的引用关系是由Remembered Set以card Table为单位进行记录的。

我们前面在标记阶段给大家讲了一个SATB写屏障的概念,它的作用主要是记录对象之间引用关系的变化,Remembered set则是记录**区域之间的引用关系的变化。**

那我们举一反三,当对象的域被修改之后,那么我们怎么来感知和实现呢?

反观论文中有这么一句话,Each thread has an associated remembered set log,a current buffer or sequence of modified cards. In addition, there is a global set of filled RS buffers。意思就是每一个mutator线程都持有一个remembered set log(转移记忆集合日志,是一个存放卡片索引的缓冲区)

其实这里在G1中就有一个概念,“转移专用写屏障“,当对象的域发生改变的时候,转移专用写屏障就能感知到,就会把该对象所对应的卡片索引添加到remembered set log之中,这里和我们之前说的SATB的设计很像,当mutator线程的remembered set log满了之后,会添加到全局的转移记忆集合日志中(如下图)

图片

我来简单描述下这个过程,当区域A中的对象A突然新增一个指向区域B中的B对象的引用之后,会被转移专用写屏障感知,然后将区域A对应的卡表中的索引512添加到转移记忆集合线程日志中,当mutator线程的转移记忆集合日志被写满之后,将会被添加到全局的转移记忆集合日志的集合之中, 添加完之后就会给mutator线程分配一个新的转移记忆集合日志

tips:这里补充一个概念,脏卡片指的就是被转移专用写屏障感知之后添加到mutator线程的转移记忆集合日志之中的卡片;干净卡片就是指的是不在mutator线程的转移记忆集合日志之中的卡片。

我们看了前面的内容知道全局的SATB队列集合会在并发标记的过程中被GCThread定期检查,然后进行扫描和标记。那么在这里全局的转移记忆集合日志是干什么用的呢?

其实这里的会有专门的转移记忆集合维护线程,去根据全局的转移记忆集合日志维护每个区域的Remembered Set。**他是怎么做的呢?**

图片

论文中大致的意思是如下图

图片

先从全局转移记忆集合日志中取出mutator线程的转移记忆集合日志,然后将对应日志中卡片的索引对应的卡片标记成干净的卡片,第三步是将该卡片对应的区域范围內所有的对象的域扫描一下,最后就是将该范围內的对象(区域A中的A对象)引用的对象(如区域B中的B对象和区域C中的C对象)添加到他们区域的转移记忆集合的卡片中。

这时候一定有同学有疑问,如果区域A中的对象A在这个转移记忆集合维护线程的工作中又被mutator修改了引用,是不是又得再次添加到remembered set log之中?

是的,所以这里有一个热卡片到的概念,就是经常被修改的对象其实是会导致转移记忆集合维护线程压力过大。很简单,G1中有一个热卡片队列,当卡片变成脏卡片的次数超过一定次数(默认4次),会被放到热卡片队列的队尾,如果热卡片队列满了,就会从头取出卡片,然后交给转移记忆集合维护线程当作普通卡片处理。当如果热卡片队列没有满的情况下是不会交给转移记忆集合维护线程处理的,因为他注定会频繁的变成脏卡片,所以会被放在转移的过程中进行处理

3.1.选择回收集合

我们在收拾残局的过程中进行了按照转移效率的降序排列了,我们开始选择回收哪些区域集合,当然选择到用户可容忍的预测暂停时间边界的时候,后续的区域就得停止了,不然就会超过用户的预测暂停时间了。通常来说,垃圾比较多的区域,它的转移效率就越高。(如下图)

图片

3.2.根对象+对象转移

根转移会转移哪些对象呢?由根直接引用的对象+并发标记处理的对象+ 引用到本次回收集合内的对象的对象(不在本次回收集合的区域内)

对象转移的过程如下

首先是将本次回收集合内的对象A转移到一个空闲区域(如下图)

图片

转移完之后需要将A*的新地址写回转移前的位置(如下图)

图片

将A所有引用的对象(这里说的是仅限于本次回收集合內的被引用对象)的**引用方(也就是下图的A\.field1、A*.field2、A*.field3)加入下图黄色的转移队列中。你可能会好奇,为什么不直接把B、C、D三个对象放到转移队列中?是因为我们要在B、C、D转移完之后将新的地址写进转移队列的A*.field1、A*.field2、A*.field3里面。**

图片

当对象A**引用了**本次回收集合之外的对象E时,因为A已经转移位置了,所以在区域E的remembered set中对应的卡片的位置需要更新。

图片

当对象A****本次回收集合之外的对象引用时,同上述道理一样,因为A已经转移,所以A*对象的remembered set之中需要添加区域F中的对象F的卡片。

图片

最后,等待转移队列中引用的对象一次转移完成之后,队列清空的时候,也就是转移完成了。到此刻为止,回收集合内部的所有存活对象都已经完成转移。

4.G1GC是如何预测暂停时间的

他是通过历史记录来预测下一次的暂停时间,我们从代码中可以看到这是一种衰减方差的计算方式,从添加历史记录的方法中可以看到

图片

这种算法的好处是慢慢的减少过去数值的影响来进行计算。(这里就不细说了,感兴趣的同学可以自行了解一下)

论文中还给出了预测对象转移的公式如下图

图片

大致意思就是消耗的时间 = 转移的固定消耗时间 + 回收集合内所有区域的消耗总和 + 剩余的脏卡片的扫描消耗。当然转移的过程并不一定是在并发标记结束之后。

后记

本人才疏学浅,很多细节也都没有搞明白,所以文章难免有不少错误和漏洞,望见谅。

当然把性能和优化全部都寄托于最底层的JVM调优上,其实是不靠谱的,也是不负责任的。每日优鲜的内部流传着一句广为人知的名言:“摸着良心写代码“,当你因为工期紧,任务重等因素对自己写的代码得过且过的话,是对自己、对后人、对公司的不负责任。所以,你摸着良心写代码了嘛?

图片

参考文献

  1. Garbage-First Garbage Collection

2.The garbage collection handbook

2.Oracle G1

3.Java Hotspot G1 GC的一些关键技术

4.G1 wiki

5.JVMG1的算法与实践

6.Java性能优化实践

文章目录
  1. 1. 前言
  2. 2. 正文
  3. 3. 为何选择G1?
  4. 4. 软实时性
  5. 5. G1的原理分析
    1. 5.1. 缘起
    2. 5.2. 1.G1GC堆的结构
    3. 5.3. 2.并发标记
      1. 5.3.1. 2.1.初始标记-创建位图
      2. 5.3.2. 2.2.初始标记-根扫描
      3. 5.3.3. 2.3.并发标记
      4. 5.3.4. 2.4.最终标记
      5. 5.3.5. 2.5.存活对象计数
      6. 5.3.6. 2.6.收拾残局
    4. 5.4. 3.转移
      1. 5.4.1. 3.1.选择回收集合
      2. 5.4.2. 3.2.根对象+对象转移
      3. 5.4.3. 4.G1GC是如何预测暂停时间的
  6. 6. 后记
  7. 7. 参考文献