基于内存计算模型的分布式数据处理系统,如Flink和Spark,经常遭受严重的内存压力,尤其在平台内存资源紧张,且被多个用户或组织共享情况下,内存资源竞争进一步加剧。用户应用被分配的内存空间不足,会在运行期间产生严重的垃圾回收(garbage collect,GC)开销,而分配过量的内存会导致平台资源的浪费。因此平台中如何为用户应用配置合适的内存成为关键问题。通过研究分析发现,平台上的多个应用会多次共同处理某个特定的数据集,且应用对数据的处理逻辑具有相似性,如图计算和机器学习应用;大数据应用框架的算子API和用户自定义方法(UDF)与数据处理逻辑有着密切的关系,继而影响运行时内存的使用。基于该发现,我们提出了一种预估新提交应用的合理内存阈值的方法。该方法利用程序分析与历史应用处理数据特征分析,基于kTree判断与历史应用的数据路径的相似性来预估新应用的合理内存阈值,并在Spark系统上实现了该方法。
该成果获得了美国专利,专利名称Method of Memory Estimation and Configuration Optimization for Distributed Data Processing System,专利授权号US 10,725,754 B2,专利发明人有石宣化、金海、柯志祥、吴文超;该成果还发表在期刊《中国科学:信息科学》上(2020,50:1178-1196)。《中国科学:信息科学》涵盖了计算机科学与技术、控制科学与控制工程、通信与信息系统、微电子与固体电子学等领域,是F5000来源期刊、中国计算机学会(CCF) A类期刊、中国通信学会A类期刊。
论文链接:http://scis.scichina.com/cn/2020/N112018-00108.pdf
背景与动机
1) 缓存数据对象
在基于内存计算模型的大数据框架中,通常包括两部分重要的缓存数据:一是重复使用的数据会被驻留到内存中,避免重算的开销;二是Shuffle过程在内存中持续聚合的数据。这两类缓存数据占用应用中很大的内存比例,且具有较长的生命周期。为预估应用运行期间的合理内存阈值,首先需要预估这两类缓存数据所占用的内存空间大小。如Spark框架中的Shuffle Buffer和Cached Data,这两项缓存数据会几乎占用典型Spark作业的所有内存空间。
2) 不同内存配置的影响
大数据处理系统如Spark、Flink,其应用的开发者只能一次性地设置其静态配置,无法控制程序运行期间的具体GC情况。JVM中的垃圾回收机制将堆中的对象分成多代,一般包括年轻代和老年代。JVM上大量的数据对象由框架和用户应用程序生成并缓存起来,它们长久地存在于老年代中直到它们生命周期的结束,而临时分配的对象都生存在JVM的年轻代中。一次全局GC (Full GC)操作会触发直接回收被老年代对象所占用空间的操作。对于平台上应用来说,如果内存空间不足以容纳这些长生命周期对象或者剩余内存空间非常少,应用的性能将会因为频繁的Full GC操作而明显恶化,甚至有可能发生Out-Of-Memory (OOM)错误。
设计与实现
1) 程序分析
我们基于Soot工具以及迭代融合在Spark上实现了程序分析器,它在每个job提交到driver时,分析整个job的数据路径。该过程主要分为两个阶段,第1阶段为预处理阶段,该阶段通过融合每个作业的stage中的链式调用的UDF以避免分析Spark框架代码;第2阶段为指针分析阶段,该阶段为后续的数据路径分析提供UDT的详细信息。
在预处理阶段中,我们通过观察stage的特征,决定循环体的层次。一般地,一个stage生成一个循环体用于放置融合的代码,当stage中有缓存操作时,我们需要将循环体一分为二,第1个循环体用于存放缓存之前的操作,第2个循环体用于存放从缓存中读取数据然后处理缓存数据的操作,这样便于我们分析缓存的数据路径。在决定了循环体的层次之后,程序分析器利用Java反射提取转换算子中的UDF,并结合算子语义将UDF融入到循环体中。最后程序分析器利用Soot生成一个合成类,将循环体作为一个方法置于该类中。
指针分析阶段给数据路径分析提供UDT的信息,程序分析器用Soot来对上一阶段生成的合成类中的循环体进行指针分析。指针分析可以确定数据变量在循环体中的赋值位置,以及赋值表达式,从而确定数据变量的具体类型。
2) 数据路径分析
为预估应用的合理内存阈值,预估方法首先需要分析缓存数据对象的处理流程。通常,Spark应用数据单元由Hadoop,文件系统迭代地读取到内存中,然后经过UDF和算子API处理,在stage的开始和末尾生成聚合的Key-Value对象并存储到Shuffle Buffer中。类似地,属于Cache RDD的数据对象会进入缓存块中,如图1所示,该流程就是数据路径。
图1 Spark应用中stage的数据路径
数据路径的提取需要采用程序分析技术对代码循环体中Shuffle Buffer与CacheData中的数据对象进行指针分析,以确定长生命周期对象的数据路径。技术上,我们选择使用kTree这种与抽象语法树(AST)类似的树结构,用于描述长生命周期对象如何生成和处理的过程。kTree的节点代表对象实体,对应的边记录了方法调用或表达式。为了更清晰地说明kTree的构建和形式,我们选择了数据路径较为复杂的Logistic Regression (LR)应用。如图2所示, LR应用Cache Data中的数据对象的数据路径以kTree的形式展现。LR读取输入数据集中的每一行生成一个DataPoint对象,数据路径的源头是一行String类型数据,根节点是最终创建的Cache Data中的数据对象。其他节点和边显示了从数据集到最终缓存对象的中间对象和方法调用或表达式,并且每个对象都进行了拆解,展示出由原生类型对象组成的层次化数据结构,用数据值来表示该对象的对象大小,若存在未知长度的数组对象,则采用表达式来定义它的长度。图中的D就是double数组的长度,则DenseVector节点的对象大小是8D+12。
图2 LR应用的kTree,根节点代表Cache Data中的数据对象
3) 预估合理内存阈值
程序分析模块主要是生成缓存对象数据路径对应的kTree,而这里的预估模块包含的功能有:(1)获取与存储历史应用运行时的重要数据特征;(2)通过匹配kTree来计算新提交应用的合理内存阈值。
我们以较细粒度的一种方式,以Spark的stage为单位来分析每个stage的合理内存阈值,再决定整个应用的合理内存阈值。具体的方法是统计这个stage的shuffle buffer对象与cache对象的内存大小的和,而临时对象生命周期很短,不会长时间占据内存空间,以及Spark框架代码本身运行的内置对象所占内存大小比例很低,所以将之前计算的和除以一个比例Ratio,该比例为shuffle buffer对象与cache对象的内存大小占spark执行总内存的比值,除之后的结果即一个stage的合理内存阈值。
上述情况讲述了如何预估一个stage的内存,这个过程发生在job真正执行前。但在stage形成任务集运行之后,预估模块需要统计运行时重要的数据特征,包括迭代过程中数据项数ItemNum,运行期间占用缓存内存Cached_Data_Size和Origin_Shuffle_Size,Origin_Shuffle_Size包含Shuffle Read和Shuffle Write阶段生成buffer的大小。它们都可以直接通过Spark内部采样的接口获得,Shuffle Buffer会在一个数据分区聚合完成之后将缓存释放掉,数据分区数等于总任务数(partitions),并发线程数为threadsnum,最终的Shuffle_Buffer_Size通过式(1)计算得到。
如何基于kTree与数据特征预估任意新stage在运行期间的合理内存阈值成为一个根本性的问题。本方法需要去获取新stage中长生命周期对象的kTree,与已存储的历史应用的数据路径,即kTree进行匹配与比较,直到匹配成功为止,若匹配全部失败则放弃预估,按照原配置对应用进行提交。具体的匹配方法分为两种情形:
通常,匹配两个kTree需要依次比较对象大小,原生类型对象层次结构和kTree的具体结构。匹配成功,则说明该stage与某个历史stage的数据路径相同,预估模块会调取该历史stage的数据特征Shuffle_Buffer_Size, Cached_Data_Size, Ratio为Spark默认的内存配置比例,通过式(2)计算得出新stage的合理内存阈值。
存在这样一种特殊情况, Shuffle Buffer中的二元组key为原生类型对象,包括Int,Double,Float,Char,Long。当符合这种条件的新的stage,该kTree与历史kTrees都无法匹配,但存在一个历史kTree,且新的kTree与历史kTree的顶层原生对象呈一次线性关系,使得历史kTree中任意一个key,新kTree都会有唯一的新key存在,使得最后Shuffle Buffer中的key个数仍然不变,即新kTree对应缓存数据的ItemNum是没变的。若数据类型(DataType)不同,但都是原生类型时,可以根据大小的比例来换算总数据对象大小。因此,尽管kTree不完全一致,但新kTree对应的缓存数据大小仍然可以预估出来。
参考文献:
胡振宇, 石宣化, 柯志祥, 金海, 王斐。基于程序分析的大数据应用内存预估方法[J]。中国科学:信息科学, 2020, 50:1178-1196。