An Innovative Memory Prediction Approach for Mapreduce Job

Java虚拟机使用分代内存管理^[12]，将管理的堆内存划分为年轻代(young)、年长代(old)两个区域。按照一定的比例(如默认为8:1)，JVM将年轻代进一步划分为eden、from和to这3个区域。

JVM首先尝试将Java对象分配在eden区域，仅当Java对象的大小超过某个阈值时，JVM才直接从年长代分配该对象所需内存。当eden或年长代内存空间不够时，分别触发minor GC或major GC，即分别回收年轻代或年长代中不再被使用的对象。执行垃圾回收期间，JVM暂停Java应用程序的运行。通常minor GC暂停时间较短，major GC暂停时间较长。

一个mapreduce作业由多个map任务和reduce任务组成。每个任务可以看成是一个Java应用。map或reduce任务分配的对象可以分为以下两类。

1)临时对象：具有单个对象占用空间小、有效时间短(即有效期通常不会超过连续两次minor GC的时间)、对象数量庞大等特征。

2)任务缓存对象：map任务或reduce任务运行期间用于缓存数据的对象通常很大，且几乎在整个任务生命周期内均有效。

第1类对象分配在eden，且minor GC后被回收，因此eden内存空间可以被重用。第2类对象可以进一步分为mapreduce框架缓存对象(S_mr)和用户定义的缓存对象(S_u)。S_mr的1个实例是mapreduce框架用于缓存map函数输出记录的对象。用户缓存对象表示用户在自定义的map类或reduce类中定义的数据缓存对象。例如使用mapreduce实现K-means聚类算法时，reduce函数需要缓存属于同一簇的原始数据，以便从中选择新的聚类中心。S_u与用户设计的map函数和reduce函数直接相关，不具有通用性，且大量mapreduce作业的map任务和reduce任务的S_u较小，因此不予考虑。

因此，本文使用以下2种思路分别预测年轻代与年长代的大小。

1)年轻代：根据map任务或reduce任务的运行时间确定期望的minor GC总时间，然后寻找满足该时间要求的eden最小值；

2)年长代：年长代主要分配mapreduce框架的缓存对象，缓存空间的大小会影响map任务与reduce任务的运行性能，因此需要根据map任务与reduce任务的数据流和工作流来计算年长代的大小。

假设任务的运行时间为T_task，设置任务minor GC总暂停时间占任务运行时间的比值为p，则希望的minor GC总时间${T_{{\rm{gc}}}} = p{T_{{\rm{task}}}}$。假设eden大小为e，当任务处理程序不变，且处理数据相当的情况下，任务运行过程中第1类对象的总大小s基本保持不变，则寻找合理的eden大小问题可以转换为满足以下约束条件的优化问题。

最小化目标函数f(e)=e，约束条件为：

式中，e_train表示minor GC回归模型训练数据集中eden的取值；$g(e, s)$表示在已知第1类对象的总大小s和给定的eden条件下minor GC的总时间。约束条件的核心是minor GC时间小于等于计算的期望时间T_gc。

通过实验发现，在其他条件不变的情况下，增加eden将减少minor GC总时间，减少eden会增加minor GC总时间。基于上述发现，设计算法1来求解上述优化问题。算法1的主要思路为：随机选择eden大小，计算对应的GC时间，大于期望值时增加eden，小于期望值时减少eden，直到找到接近期望时间所对应的eden或超过设定的最大值或最小值为止。算法1中l和u与式(1)含义相同，m₀表示每次增加或减少内存的大小。

算法1：eden搜索算法

输入：g(e, s)，l，u，m₀，T_gc

输出：预测eden的大小

1)随机选择x₁，使得$l \le {x_1} \le u$，将x₁设置为起始搜索点

2)求${T_1} = g({x_1}, s)$，如果${T_1} < {T_{{\rm{th}}}}$，${\rm{step}} = - {m_0}$，执行步骤3)；如果${T_1} > {T_{{\rm{th}}}}$，${\rm{step}} = {m_0}$，执行步骤4)；否则返回x₁

3)${x_2} = {x_1} + {\rm{step}}$，求${T_2} = g({x_2}, s)$，如果${T_2} < {T_{{\rm{th}}}}$，依次检查${x_3}, {x_4}, \cdots $，直到x_i使得${T_i} \le {T_{{\rm{th}}}}$，返回x_i-1；如果${T_2} \le {T_{{\rm{th}}}}$，返回x₁

4)${x_2} = {x_1} + {\rm{step}}$，求${T_2} = g({x_2}, s)$，如果${T_2} > {T_{{\rm{th}}}}$，依次检查${x_3}, {x_4}, \cdots $，直到${x_i}$使得${T_i} \le {T_{{\rm{th}}}}$，返回${x_i}$；如果${T_2} \le {T_{{\rm{th}}}}$，返回${x_2}$。

mapreduce提供了多个配置参数分别设置map任务和reduce任务的缓存大小。这些配置参数设置不合理时会导致map任务和reduce任务发生多次溢写操作，直接影响任务性能和作业性能。

map任务或reduce任务缓存对象用${S_{{\rm{mr}}}}$表示，在整个任务运行期间有效，因此这些对象将驻留年长代，通过计算${S_{{\rm{mr}}}}$的大小即可获得年长代的大小。

对map任务，${S_{{\rm{mr}}}}$缓存map函数输出记录；对reduce任务，${S_{{\rm{mr}}}}$缓存shuffle数据。单个map任务或reduce任务的${S_{{\rm{mr}}}}$大小需要结合任务的数据流和工作流确定。

同一个mapreduce作业的所有map任务和reduce使用相同的配置。因此需要根据同一作业下不同map任务和reduce任务的期望大小计算合理的统一值。

1) map任务的${S_{{\rm{mr}}}}$

map函数输出记录序列化后保存在S_rd中，该记录的分区号及在S_rd中的地址索引保存在S_idx中，因此S_mr为S_rd与S_idx之和。第i个map任务的记录索引缓存$S_{{\rm{idx}}}^{(i)}$和记录数据缓存$S_{{\rm{rd}}}^{(i)}$通过下文计算方法获得。$S_{{\rm{idx}}}^{(i)}$和$S_{{\rm{rd}}}^{(i)}$能确保第i个map不发生溢写操作，因此分别选择$S_{{\rm{idx}}}^{(i)}$和$S_{{\rm{rd}}}^{(i)}$的最大值S_idx和S_rd作为统一配置，可以确保每个任务均不发生溢写。定义P_idx表示map任务的索引数据所占百分比，则有：

此时必然有${S_{{\rm{idx}}}} \ge S_{{\rm{idx}}}^{(i)}, {S_{{\rm{rd}}}} \ge S_{{\rm{rd}}}^{(i)}$，即每个map任务均不会执行溢写操作。为了避免发生内存溢出错误，当S_idx和S_rd的占用比例超过β时触发溢写操作，为了避免溢写发生，实际分配的缓存大小为计算所得缓存大小${S'_{{\rm{mr}}}}$除以β。为了避免内存资源浪费，将β设置为接近于1的值，设置为0.99，因此有：

2) reduce任务的S_mr

reduce任务将拷贝的数据缓存到S_R中，只要S_R大于每个任务的实际缓存数据大小，reduce任务就不会发生溢写，从而获得最佳运行性能。设S_R^(j)表示第j个reduce任务的内存需求，为了确保每个reduce任务不发生溢写操作，S_R必须取S_R^(j)的最大值，即：

设每次minor GC平均暂停时间为t_gc，通过实验数据分析发现t_gc是e的函数，即：

$\psi $可以通过回归建模获得。当已知年轻代对象的总大小s和eden大小e时，可计算出需要执行的minor GC的次数N_gc，即：

则minor GC的总时间估计值g(e, s)为：

式(7)为在年轻代对象总需求不变、给定eden大小的条件下，minor GC的总暂停时间。

将式(5)、式(6)带入式(7)，得：

s可以通过对minor GC日志信息进行统计分析获得，即：

式中，O_i表示第i-1次minor GC与第i次minor GC期间分配在年轻代对象的大小；n表示minor GC发生的次数。使用式(8)可以计算任务在某个eden大小下的GC暂停时间。

map任务的数据流和工作流如图 1所示，其中灰色方框表示操作，白色方框表示文件。当缓存(即S_mr)设置过小时，map任务执行过程会发生多次不必要的溢写操作，形成多个中间文件。当map处理完所有输入数据时，将缓存中的记录以及中间文件中的记录进行归并排序，形成单个输出文件。每条记录发生1次溢写操作将增加1次本地文件读写操作，增加归并排序的时间，因此优化目标通过计算合理配置参数达到不执行图 1中虚线框部分的操作的目的。

map任务优化的实现思路是根据map任务的计数器值计算该任务所需的$S_{{\rm{idx}}}^{(i)}$和$S_{{\rm{rd}}}^{(i)}$大小，并分配相应的缓存空间，因此本文优化map任务时不需要构建性能模型。

每条map输出记录需要占用16 byte的索引空间，令$N_{{\rm{rd}}}^{(i)}$表示第i个map任务输出的记录数，则有：

$S_{{\rm{rd}}}^{(i)}$可以直接从map任务的计数器中获得。

例如某个作业的第i个map任务的输出记录数为10 485 760，输出记录数据为200 MB，则该map任务的$S_{{\rm{idx}}}^{(i)} = {\rm{10 485 760}} \times 16 = 160{\rm{ MB}}$，$S_{{\rm{rd}}}^{(i)} = 200{\rm{ MB}}$，则$P_{{\rm{idx}}}^{(i)} = 45\% $。

reduce阶段包含3个子阶段，即shuffle阶段、排序阶段和执行reduce函数阶段，如图 2所示。shuffle阶段主要功能是从map端拷贝数据并保存到缓存$S_{\rm{R}}^{(i)}$中，当$S_{\rm{R}}^{(i)}$的使用比例超过${P_{{\rm{sf}}}}{P_{{\rm{sp}}}}$后将数据溢写到中间文件，当中间文件数量超过阈值后执行归并操作，形成单个更大的中间文件。shuffle阶段完成后进入排序阶段，主要功能是使用归并排序算法将中间文件及保留在$S_{\rm{R}}^{(i)}$中的数据进行归并排序。在执行归并排序之前，mapreduce框架首先将超过JVM最大堆与P_red乘积的数据溢写到中间文件。排序阶段完成后进入执行reduce函数的阶段，此阶段主要将记录交由reduce函数处理，将结果写入HDFS文件。本文主要对shuffle阶段和排序阶段进行优化。

本文采用以下两项措施优化reduce的数据流和工作流：1)修改Hadoop框架，取消原有框架中reduce任务缓存使用量不能超过2 GB的限制，为实现reduce阶段零溢写提供架构支持；2)通过reduce任务历史数据计算最优的内存配置，获得零溢写的最优执行流程。优化后的reduce任务工作流程减少了图 2中的虚线框内的操作。

每个reduce任务的优化配置计算过程如下：令$S_{{\rm{rd}}}^{(i)}$表示第i个reduce任务拷贝的数据大小(通过历史数据获得)，P_sf为shuffle操作能使用内存的百分比，P_sp为发生溢写的阈值，为获得最优的执行流程，则必须有：

即保证第i个reduce任务实际拷贝的数据小于$S_{\rm{R}}^{(i)}$，以确保该任务不执行溢写操作，从而获得最优的运行性能。为了避免内存资源浪费，取${P_{{\rm{sf}}}}{\rm{ = }}{P_{{\rm{sp}}}} = 0.99$。为了避免将已缓存的数据在进入排序阶段之前被溢写到中间文件，设置P_red为1.0。

Hadoop测试集群有8个从节点，每个从节点分配5 GB内存，排他性使用一个E5-2609@2.4GHz的物理核。每个从节点分配2个map任务槽和1个reduce任务槽，Hadoop以apache发布版本1.2.1为基础，修改了reduce任务内存管理，修改日志保存机制。本文选择PUMA测试套件^[14]的wordcount (WD)、invertedindex (ID)、TeraSort (TS)、adjlist (ADJ)这4个测试程序。wordcount、invertedindex测试程序的输入数据为多个文件组成的10 GB wikipedia数据集。adjlist输入数据集为从图数据集中随机选出10 GB数据。TeraSort输入数据使用mapreduce提供的程序自动生成，总共10 GB左右。

使用loess^[15]对WD、ID、TS、ADJ的map任务和reduce任务的minor GC进行回归建模。使用算法1预测的年轻代大小进行测试，统计了4种测试程序的所有map和reduce任务GC暂停时间占任务运行时间的百分比，如图 3所示。可得知除WD和ADJ的reduce任务的GC暂停时间的比例大于1%以外，其他任务的GC暂停时间均小于1%。

为避免年轻代分配过大导致不必要的资源浪费，分析了WD的map任务和reduce任务运行时间平均值与年轻代的关系，如图 4所示。

从图 4得知，年轻代为180 MB左右能获得较好的运行性能。ID、TS和ADJ也呈现相似的的特征。图 4中获得的年轻代合理值可以和算法1所得值综合考虑，选择两者的最小值为最终的年轻代大小。

统计WD、ID、TS和ADJ的map任务和reduce任务的S_mr累计分布函数，其中map任务S_mr非常集中，ADJ和TS的reduce任务的S_mr也非常集中，WD和ID较分散，但差距也较小，如图 5所示。因此即使采用最大内存需求也不会造成过多内存资源浪费。

pred (即本文提出的内存预测方法)和starfish的优化内存配置对比如表 1所示。从表 1得知pred给出的内存配置均比starfish小。为评价S_mr分配是否合理，分别统计了默认配置、starfish和pred这3种配置条件下发生溢写的任务数量，如表 2所示，其中MSC、MNSC、RSC和RNSC分别表示发生溢写的map任务数、未发生溢写的map任务数、发生溢写的reduce任务数和未发生溢写的reduce任务数。未发生溢写是任务获得最佳运行性能的基本条件。从表 1和表 2得知，pred方法能在比starfish更少的内存配置条件下获得最佳的任务执行流程，即未发生溢写操作。

mapreduce配置参数调优以starfish最为全面，效果最佳。与基于经验的配置参数优化相比，starfish能获得更好的性能提升^[4]。在starfish0.3.0版本的基础之上增加了adjlist和invertedindex测试程序的支持，在相同的集群资源下分别比较4种测试程序在默认配置、starfish优化配置和pred配置下的运行时间，结果如图 6所示。starfish和pred给出的配置参数显著提升了作业性能，且pred性能在4种测试程序下均优于starfish。与默认配置相比，starfish在测试集群上平均加速比为3.5，最大加速比为6.1。与默认配置相比，pred的平均加速比为6.4，最大加速比为8。

starfish目前只支持Hadoop0.20版本，要求mapreduce必须使用新API编写。pred只需要作业的历史记录文件和任务JVM输出的垃圾回收日志，mapreduce的各个版本均支持通过简单配置获得这些数据，因此从部署难度及适应Hadoop版本更新两个方面讲，pred比starfish更易于使用。

文献[16-17]表明，在facebook、雅虎和淘宝的Hadoop生产集群中，绝大部分的mapreduce作业的输入数据只是GB级别，当前的Hadoop集群内存资源足够将这些待处理的数据全部缓存在内存中。对于这种数据规模的mapreduce作业，pred能提供很好的性能优化。

本文提出一种分代内存大小的预测方法。根据JVM的分代内存管理特点，分别使用不同的方法预测JVM不同分代内存区域的大小。本文提出的分代内存预测方法综合考虑了mapreduce层和JVM层的内存配置，是一种更为全面mapreduce作业内存配置参数优化方法。测试结果表明，与默认配置相比，本文给出的内存优化配置平均性能提升至6倍，最大达到8倍。与starfish相比，本文提出的方法在提供更好的性能前提下，使用更少的内存资源。