操作方法:Java虚拟机垃圾回收(二) 垃圾回收算法：标记-清除算法 复制算法 标记

　　操作方法:Java虚拟机垃圾回收(二) 垃圾回收算法：标记-清除算法 复制算法 标记

　　Java虚拟机垃圾采集（二）垃圾采集算法

　　标记清除算法 复制算法 标记组织算法 分代采集算法优采云算法

　　在《Java虚拟机垃圾回收（一）基础》中学习了如何判断一个对象是活还是死？本文介绍了垃圾回收的基本算法：引用计数算法、可达性分析算法，以及在HotSpot虚拟机中实现对象可达性分析的一些问题。

　　我们先来了解一下Java虚拟机垃圾回收的几种常用算法：mark-sweep算法、copy算法、mark-sort算法、分代回收算法、优采云算法，介绍一下它们的算法思路，有哪些优缺点，以及主要应用场景。

　　1. 标记扫描算法

　　Mark-Sweep 算法是一种基本的采集算法。

　　1.算法思路

　　“mark-sweep”算法分为两个阶段：

　　（标记

　　首先标记所有需要回收的对象；

　　标记过程如《Java虚拟机垃圾回收（一）基础知识》中的“2-4.判断对象是活还是死”中所述——分为两个标记过程（请参考上一节细节）：

　　(1)、第一个标记

　　经过可达性分析，发现对象第一次被标记是在没有引用链连接到GC Roots的情况下；

　　并执行一个过滤器：这个对象是否需要执行finalize()方法；

　　需要执行finalize()方法的对象放入F-Queue队列；

　　(2)、第二个标记

　　GC 会对 F-Queue 队列中的对象进行第二次小规模标记；

　　在其finalize()方法中与引用链上的任意对象重新关联，并在第二次标记时将其移出“待回收”集合；

　　第一次被标记，第二次被标记（如果需要，但没有从“待采集”集合中删除），对象被认为是死的，可以被采集。

　　(二)、清除

　　被标记两次后，“待回收”集合中的对象将被统一回收；

　　执行过程如下：

　　2、优势

　　基于最基本的可达性分析算法，是最基本的集合算法；

　　后续的采集算法就是基于这个思想，改进它的缺点；

　　3.缺点

　　有两个主要缺点：

　　(一)、效率问题

　　标记和清除都是低效的；

　　(二)、空间问题

　　清除标记后，会产生大量不连续的内存碎片；

　　这导致在分配大内存对象时无法找到足够的连续内存；

　　因此，需要提前触发另一个垃圾回收动作；

　　四、应用场景

　　cms 老年采集器；

　　2.复制算法算法

　　“复制”采集算法，以解决mark-sweep算法的效率问题；

　　1.算法思路

　　(A) 将内存分成大小相等的两个块，一次只使用其中一个；

　　(B)、当一块内存用完时，将幸存的对象复制到另一个块（然后使用这个块）；

　　(C)、然后清除一次已用的内存空间，然后重复步骤2；

　　执行过程如下：

　　2、优势

　　这使得每次只对整个半区进行内存回收；

　　内存分配时无需考虑内存碎片等问题（内存可以通过“指针冲突”进行分配）；

　　实现简单，运行高效；

　　（“指针冲突”请参考“HotSpot虚拟机中Java对象的创建过程”）

　　3.缺点

　　(一)、浪费空间

　　可用内存减少到原来的一半，太浪费了（解决方法：可以改进，不要按1:1的比例划分）；

　　(B)、效率随着对象存活率的增加而降低

　　

　　当对象存活率高时，需要更多的复制操作，效率会变低（解决方法：后面的标记排序算法）；

　　四、应用场景

　　现在商业JVM使用这个算法（通过改进缺点1）来回收新一代；

　　如Serial采集器、ParNew采集器、Parallel Scavenge采集器、G1（从局部看）；

　　5. HotSpot虚拟机算法改进

　　(一)、弱生成论

　　分代垃圾回收基于弱分代假设，描述如下：

　　（1）大多数分配内存的对象在年轻代中存活时间不长，死亡；

　　（2）很少有对象会从老年代到年轻代；

　　其中，IBM 研究表明，98% 的新一代对象都是“生死攸关”；

　　所以不需要按1:1的比例划分内存（解决缺点1）；

　　(二)、HotSpot虚拟机新一代内存布局及算法

　　（1）将新生代内存划分为一个较大的Eden空间和两个较小的Survivor空间；

　　(2)、每次使用伊甸园和幸存者之一；

　　（3）回收时，将Eden和Survivor中正在使用的残存物一次性复制给另一个Survivor；

　　(4)、然后清理Eden和使用过的Survivor空间；

　　(5)、稍后使用Eden和复制的Survivor空间，重复步骤3；

　　默认Eden：Survivor=8:1，即每次可以使用90%的空间，只浪费一块Survivor空间；

　　(三)、经销保证

　　如果另一块Survivor空间没有足够的空间存放上一次新生代采集的幸存对象，这些对象会通过分配保证机制（Handle Promotion）直接进入老年代；

　　分配保证会在后面讲解垃圾采集器执行规则的时候详细讲解；

　　阅读更多：#sthref16

　　3. 标记-整理算法

　　“Mark-Compact”算法是根据老年代的特点提出的。

　　1.算法思路

　　(1)、标记

　　标记过程与“mark-sweep”算法相同；

　　(2)、整理

　　但后续并不是直接将可回收的物体清理干净，而是将所有幸存的物体移到一端；

　　然后直接清理结束边界外的内存；

　　执行过程如下：

　　2、优势

　　(A)、与复制算法不同，效率随着对象存活率的增加而降低

　　老年特征：

　　对象存活率高，没有额外空间分配保证；

　　因此，老年代一般不能直接使用复制算法；

　　相反，使用标记整理算法；

　　(B)、不会像mark-sweep算法那样产生内存碎片

　　由于在搬家前进行了清扫，残留物集中在空间的一侧；

　　3.缺点

　　主要问题是效率：除了像marking-clearing算法这样的marking流程，需要整理的流程比较多，效率比较低；

　　四、应用场景

　　许多垃圾采集器使用这种算法来回收老年代；

　　如Serial Old collector、G1（从整体上看）；

　　4. 分代采集算法

　　“Generational 采集”算法结合了不同的采集算法来处理不同的区域。

　　1.算法思路

　　基于上面提到的弱生成理论，其实并没有什么新思路；

　　只需按照对象的生命周期将内存分成若干块即可；

　　这样就可以根据各个年龄段的特点，采用最合适的采集算法；

　　Java堆一般分为新生代和老年代；

　　(一)、新一代

　　每次垃圾回收都会有大量对象死亡，只有少数存活；

　　

　　因此，可以使用复制算法；

　　(二)、老年

　　对象存活率高，没有额外空间分配保证；

　　使用“mark-clean”或“mark-clean”算法；

　　结合上面对新生代的内存划分的介绍和上一篇文章中对Java堆的介绍，可以得出HotSpot虚拟机的一般年龄内存划分，如下图所示：

　　2、优势

　　可以根据各个年龄段的特点，采用最合适的采集算法；

　　3.缺点

　　还是不能控制每次垃圾回收的时机；

　　四、应用场景

　　目前，几乎所有商用虚拟机垃圾采集器都使用分代采集算法；

　　比如HotSpot虚拟机中的所有垃圾回收器：Serial、ParNew、Parallel Scavenge、Serial Old、Parallel Old、cms、G1（也保留）；

　　5. 优采云算法

　　优采云算法，也称为train算法，是一种更彻底的次区域处理和采集算法，是对分代采集算法的有力补充。

　　1.算法思路

　　在优采云算法中，内存被划分为块，多个块组成一个集合。为了可视化，一个马车代表一个块，一个列优采云代表一个集合，如下图所示；

　　优采云和车厢都是按照创建顺序编号的，每个车厢大小相等，但每个优采云收录的车厢数量不一定相等；

　　每辆车都有一个记忆集，每个优采云的记忆集是其所有汽车的记忆集之和；

　　内存集由对同一 优采云 对象在较高序列号的树干中的对象和较高序列号中的对象的引用组成；

　　垃圾回收以车厢为单位，整体算法流程如下：

　　(1)、选择最小的标签优采云；

　　(2)如果优采云的内存集为空，则释放整列优采云并终止，否则进行第三步；

　　(3) 选择优采云中编号最小的小车；

　　(4) 对于隔间记忆集的每个元素：

　　如果是根引用所引用的对象，则将其复制到一个新的优采云列表中；

　　如果是另一个优采云对象指向的对象，则将其复制到指向它的优采云；

　　假设已经保留了一些对象，那么通过这些对象可以到达的对象将被复制到同一列优采云；

　　如果一个对象被多个优采云s的对象引用，它可以被复制到任何一个优采云s；

　　在此步骤中，需要相应地更新受影响的参考集合；

　　(5)、解除运输并终止；

　　采集过程会删除一些空车和空车，并在需要时创建一些车和优采云。更多内容请参考：《编译原理》第二版7.75《训练算法》、《渐进式垃圾回收：优采云算法》；

　　执行过程如下：

　　2、优势

　　在成熟的对象空间中可以提供有限时间的渐近集合；

　　无需每次都进行大面积的垃圾回收过程；

　　即可以控制垃圾回收的时间，可以在规定时间内回收一些小区域；

　　3.缺点

　　实现更复杂。例如，使用类似算法的 G1 采集器仅在 JDK7 中实现；

　　在某些情况下，它可能不划算；

　　四、应用场景

　　JDK7之后，HotSpot虚拟机G1采集器采用了类似的算法，可以建立可预测的停顿时间模型；

　　至此，我们对Java虚拟机垃圾回收的几种常用算法有了一个大致的了解。后面我们会学习JVM垃圾采集器以及相关的调优方法……

　　【参考】

　　1.《编译原理》第二版第7章

　　2、《深入理解Java虚拟机：JVM高级特性与最佳实践》第二版第3章

　　3、《Java虚拟机规范》Java SE 8版：

　　4.《Java平台标准版HotSpot虚拟机垃圾回收调优指南》：

　　5.“Java HotSpot™ 虚拟机中的内存管理”：

　　6、HotSpot虚拟机参数官方说明：

　　7.《Thinking in Java》第四版5.5清理：终结和垃圾回收；

　　8.渐进式垃圾采集：优采云算法：

　　直观:关于数据埋点采集，你需要了解这些

　　数据采集是数据分析的基础，跟踪是最重要的采集方法。那么数据埋点采集收录哪些问题呢？本文作者从什么是埋点、埋点如何设计、埋点的应用三个方面对这个问题进行梳理，分享给大家。

　　1. 数据采集 和常见问题解答 1. 数据采集

　　数据采集的方式有很多，而埋采集是其中非常重要的一环，是c端和b端产品的主要采集方式。

　　数据采集，顾名思义是采集对应的数据，是整个数据流的起点。采集的不完整性，对与错，直接决定了数据的广度和质量，影响后续的所有环节。在数据采集有效性和完整性较差的公司中，企业经常会发现数据发生了重大变化。

　　数据处理通常包括以下五个步骤：

　　2. 常见数据问题

　　在大致了解了data采集及其结构之后，我们再来看看工作中遇到的问题，有多少与data采集链接有关：

　　数据与背景差距较大，数据不准确——统计口径不同，埋点定义不同，采集方法带来误差；想用的时候却没有我要的数据——我没有提到数据采集不正确和不完整的需求和埋点；事件过多，含义不明确——埋点设计方法、埋点更新迭代规则及维护；分析数据不知道要看哪些数据和指标——数据定义不明确，缺乏分析思路。

　　我们需要根本原因的解决方案：将 采集 视为独立的研发业务，而不是产品开发的附属品

　　2. 什么是墓地 1. 什么是墓地

　　所谓埋点，是data采集领域的一个名词。它的学名应该叫event tracking，对应的英文是Event Tracking，是指捕获、处理和发送特定用户行为或事件的相关技术和实现过程。

　　数据埋点是数据分析师、数据产品经理和数据运营商，他们根据业务需求或产品需求，针对用户行为对应的每个事件开发埋点，通过SDK上报埋点数据结果，记录汇总数据。分析、推动产品优化和指导运营。

　　该过程伴随着规范。通过定义可以看出，具体的用户行为和事件是我们采集关注的焦点，也需要处理和发送相关的技术和实现流程；数据嵌入服务于产品，来自产品。，所以和产品息息相关，重点在于具体的实战过程，这关系到大家对底层数据的理解。

　　2、为什么要埋点？

　　埋点的目的是对产品进行全方位的持续跟踪，通过数据分析不断引导和优化产品。数据埋点的质量直接影响数据质量、产品质量和运营质量。

　　数据驱动埋点将分析深度下钻到流量分布和流量层面，通过统计分析，对宏观指标进行深度分析，发现指标背后的问题，洞察用户之间的潜在关系行为和价值提升；产品优化——对于产品，用户在产品中做了什么，他们在产品中停留的时间，以及需要注意哪些异常。这些问题可以通过埋点来实现；精细化运营——埋点可以实现整个产品生命周期、流量质量和不同来源的分布、人群的行为特征和关系，以及用户行为与商业价值提升之间的潜在关联。3.埋点方式

　　埋点方法有哪些？大多数公司目前使用客户端和服务器的组合：

　　准确度：代码掩埋 > 视觉掩埋 > 完全掩埋

　　

　　三、埋点架构及设计 1、埋点顶层设计采集

　　所谓顶层设计，就是想清楚怎么埋点，用什么方式埋点，上传机制是什么，怎么定义，怎么实现等等；我们遵循唯一性、可扩展性、一致性等，需要设计一些常用的字段和生成机制，比如：cid、idfa、idfv等。

　　2.埋采集事件和属性设计

　　在设计属性和事件时，我们需要知道哪些是经常变化的，哪些是不变化的，哪些是业务行为，哪些是基本属性。

　　基于基本的属性事件，我们认为属性一定是采集项，但是属性中的事件属性会根据不同的业务进行调整。因此，我们可以将埋点采集分为协议层和业务层Bury。

　　3.数据采集事件和属性设计

　　Ev 事件的命名也遵循一些规则。当相同类型的函数出现在不同的页面或位置时，根据函数名进行命名，并在ev参数中区分页面和位置。只有当按钮被点击时，它才会以按钮名称命名。

　　ev事件格式：ev分为ev标志和ev参数

　　规则：

　　在ev标识符和ev参数之间使用“#”（一级连接符）；

　　在ev参数和ev参数之间使用“/”（二级连接符）；

　　ev参数使用key=value的结构。当一个key对应多个value值时，value1和value2的连接为","（三级连接符）；

　　当埋点只有ev标志，没有ev参数时，不需要#；

　　评论：

　　ev标识：作为埋点的唯一标识，用于区分埋点的位置和属性，不可变、不可修改；

　　ev参数：埋点需要返回的参数。ev参数的顺序是可变的，可以修改；）

　　调整app嵌入点时，ev logo不变，仅修改以下嵌入点参数（更改参数值或添加参数类型）

　　eg：一般埋点文档中收录的sheet名称和功能：

　　A. 暴露埋点汇总；

　　B、点击浏览埋点汇总；

　　

　　C、故障埋点汇总：一般会记录埋点的故障版本或时间；

　　D、PC和M侧页面埋点对应的pageid；

　　E、各版本上线时间记录；

　　在埋点文档中，都收录了列名和函数：

　　4.基于埋点的数据统计

　　如何使用埋点统计找到埋藏的 ev 事件：

　　明确追踪点的类型（点击/曝光/浏览）——过滤类型字段，指定按钮追踪点所属的页面（页面或功能）——过滤功能模块字段，指定追踪点事件的名称——过滤name字段就可以知道ev logo，可以直接用ev来过滤

　　如何根据ev事件查询统计：当点击查询按钮进行统计时，可以直接使用ev标志查询。有区别时，可以限制埋点参数的取值；因为ev参数的顺序不要求是可变的，查询统计的时候，不能根据参数的顺序来限制；

　　4.应用数据处理的基础

　　一、指标体系

　　系统化的指标可以整合不同的指标、不同的维度进行综合分析，可以更快的发现当前产品和业务流程中存在的问题。

　　2. 可视化

　　人类解释图像信息比文本更有效。可视化对于数据分析非常重要。使用数据可视化可以揭示数据中固有的复杂关系。

　　3.提供埋点元信息API

　　data采集服务会将采集收到的埋点写入Kafka。针对各个业务的实时数据消费需求，我们为各个业务提供单独的Kafka，流量分发模块会定时读取。取埋点管理平台提供的元信息，将流量实时分发到各个业务的Kafka。

　　数据采集就像设计一个产品，不应该过分，留有扩展的空间，但要不断思考有没有数据，是否完整、详细、稳定或快速。