羅永剛，陳興蜀，楊　露

(四川大學網絡空間安全研究院　成都　610065)

一種Mapreduce作業(yè)內存精確預測方法

羅永剛，陳興蜀，楊露

(四川大學網絡空間安全研究院成都610065)

針對準確預測mapreduce作業(yè)內存資源需求困難的問題，根據Java虛擬機(JVM)的分代(JVM將堆內存劃分為年輕代和年長代)內存管理特點，該文提出一種分代內存預測方法。建立年輕代大小與垃圾回收時間的模型，將尋找合理年輕代大小的問題轉換為一個受約束的非線性優(yōu)化問題，并設計搜索算法求解該優(yōu)化問題。建立mapreduce作業(yè)的map任務和reduce任務性能與內存的關系模型，求解最佳性能的內存需求，從而獲得map任務和reduce任務的年長代內存大小。實驗結果表明，本文提出的方法能準確預測作業(yè)的內存需求；與默認配置相比，能提供平均6倍的性能提升。

垃圾回收;Java虛擬機;mapreduce;資源管理

Apache Hadoop[1](包含HDFS和mapreduce兩個核心組件，本文只考慮mapreduce，因此在沒有特殊說明情況下Hadoop和mapreduce等價使用)是谷歌公司提出的mapreduce編程模式的開源版本，得到了學術界、工業(yè)界的大力支持。隨著mapreduce應用規(guī)模不斷擴大，為Hadoop集群分配合理的資源以及優(yōu)化mapreduce應用的運行性能一直是研究熱點[2]。Hadoop官方路線圖規(guī)劃在Hadoop3.0版本中增加了內存自動預測機制[3]。

已有大量研究工作關注mapreduce性能與配置參數的關系。這些研究的核心思想是通過構建性能模型獲得特定作業(yè)在某個配置下的運行時間，然后使用優(yōu)化算法獲得最優(yōu)的配置參數。文獻[4]使用基于代價的方式構建性能模型[5]，使用遞歸隨機搜索算法找到優(yōu)化的配置參數。文獻[6]的性能模型與文獻[4]類似，但使用的是遺傳算法尋找最優(yōu)配置參數。文獻[7]未構建性能模型，通過修改hadoop框架在線獲得任務運行時間，使用拉丁超立方體抽樣方法進行配置參數采樣，使用智能爬山算法搜索最優(yōu)配置參數。這些研究存在以下不足：1)構建性能模型增加了不必要的復雜度；2)搜索算法需要限定內存資源配置參數的搜索空間，增加用戶使用難度。

Hadoop應用程序運行在Java虛擬機之上，JVM的配置對Hadoop應用的性能和穩(wěn)定性有直接影響。文獻[8]通過定期采樣作業(yè)的內存使用量來預測內存的使用，沒有說明預測的內存配置是否提升作業(yè)性能。文獻[9]通過隨機森林算法優(yōu)化JVM配置，但給出的優(yōu)化配置的年輕代與年長代比例僅有1:2與1:8這兩種配置。文獻[10-11]沒有考慮mapreduce作業(yè)的特殊性，也沒有給出JVM內存大小的建議。

為解決這些問題，根據JVM分代內存管理原理，結合年輕代和年長代對mapreduce作業(yè)性能影響不同，提出分代內存預測方法，具體包括：

1)使用回歸模型建模年輕代垃圾回收平均暫停時間，將尋找合理的年輕代大小問題轉換為非線性優(yōu)化問題，并設計求解算法；

2)分析map任務和reduce任務的性能與內存配置的關系，建立內存模型，通過內存模型求解年長代內存需求。不需要構建性能模型和使用優(yōu)化算法，也不需要用戶指定內存范圍。

1　分代內存大小預測方法

1.1分代內存預測

Java虛擬機使用分代內存管理[12]，將管理的堆內存劃分為年輕代(young)、年長代(old)兩個區(qū)域。按照一定的比例(如默認為8:1)，JVM將年輕代進一步劃分為eden、from和to這3個區(qū)域。

JVM首先嘗試將Java對象分配在eden區(qū)域，僅當Java對象的大小超過某個閾值時，JVM才直接從年長代分配該對象所需內存。當eden或年長代內存空間不夠時，分別觸發(fā)minor GC或major GC，即分別回收年輕代或年長代中不再被使用的對象。執(zhí)行垃圾回收期間，JVM暫停Java應用程序的運行。通常minor GC暫停時間較短，major GC暫停時間較長。

一個mapreduce作業(yè)由多個map任務和reduce任務組成。每個任務可以看成是一個Java應用。map或reduce任務分配的對象可以分為以下兩類。

1)臨時對象：具有單個對象占用空間小、有效時間短(即有效期通常不會超過連續(xù)兩次minor GC的時間)、對象數量龐大等特征。

2)任務緩存對象：map任務或reduce任務運行期間用于緩存數據的對象通常很大，且?guī)缀踉谡麄€任務生命周期內均有效。

第1類對象分配在eden，且minor GC后被回收，因此eden內存空間可以被重用。第2類對象可以進一步分為mapreduce框架緩存對象(Smr)和用戶定義的緩存對象(Su)。Smr的1個實例是mapreduce框架用于緩存map函數輸出記錄的對象。用戶緩存對象表示用戶在自定義的map類或reduce類中定義的數據緩存對象。例如使用mapreduce實現(xiàn)K-means聚類算法時，reduce函數需要緩存屬于同一簇的原始數據，以便從中選擇新的聚類中心。Su與用戶設計的map函數和reduce函數直接相關，不具有通用性，且大量mapreduce作業(yè)的map任務和reduce任務的Su較小，因此不予考慮。

因此，本文使用以下2種思路分別預測年輕代與年長代的大小。

1)年輕代：根據map任務或reduce任務的運行時間確定期望的minor GC總時間，然后尋找滿足該時間要求的eden最小值；

2)年長代：年長代主要分配mapreduce框架的緩存對象，緩存空間的大小會影響map任務與reduce任務的運行性能，因此需要根據map任務與reduce任務的數據流和工作流來計算年長代的大小。

1.1.1預測年輕代內存大小

假設任務的運行時間為Ttask，設置任務minor GC總暫停時間占任務運行時間的比值為p，則希望的minor GC總時間。假設eden大小為e，當任務處理程序不變，且處理數據相當的情況下，任務運行過程中第1類對象的總大小s基本保持不變，則尋找合理的eden大小問題可以轉換為滿足以下約束條件的優(yōu)化問題。

最小化目標函數f( e)=e，約束條件為：

式中，etrain表示minor GC回歸模型訓練數據集中eden的取值；g( e,s)表示在已知第1類對象的總大小s和給定的eden條件下minor GC的總時間。約束條件的核心是minor GC時間小于等于計算的期望時間Tgc。

通過實驗發(fā)現(xiàn)，在其他條件不變的情況下，增加eden將減少minor GC總時間，減少eden會增加minor GC總時間。基于上述發(fā)現(xiàn)，設計算法1來求解上述優(yōu)化問題。算法1的主要思路為：隨機選擇eden大小，計算對應的GC時間，大于期望值時增加eden，小于期望值時減少eden，直到找到接近期望時間所對應的eden或超過設定的最大值或最小值為止。算法1中l(wèi)和u與式(1)含義相同，m0表示每次增加或減少內存的大小。

算法1：eden搜索算法

輸入：g( e,s)，l，u，m0，Tgc

輸出：預測eden的大小

1.1.2預測年長代內存大小

mapreduce提供了多個配置參數分別設置map任務和reduce任務的緩存大小。這些配置參數設置不合理時會導致map任務和reduce任務發(fā)生多次溢寫操作，直接影響任務性能和作業(yè)性能。

map任務或reduce任務緩存對象用Smr表示，在整個任務運行期間有效，因此這些對象將駐留年長代，通過計算Smr的大小即可獲得年長代的大小。

對map任務，Smr緩存map函數輸出記錄；對reduce任務，Smr緩存shuffle數據。單個map任務或reduce任務的Smr大小需要結合任務的數據流和工作流確定。

同一個mapreduce作業(yè)的所有map任務和reduce使用相同的配置。因此需要根據同一作業(yè)下不同map任務和reduce任務的期望大小計算合理的統(tǒng)一值。

1)map任務的Smr

map函數輸出記錄序列化后保存在Srd中，該記錄的分區(qū)號及在Srd中的地址索引保存在Sidx中，因此Smr為Srd與Sidx之和。第i個map任務的記錄索引緩存和記錄數據緩存通過下文計算方法獲得。和能確保第i個map不發(fā)生溢寫操作，因此分別選擇和的最大值S和S作為統(tǒng)一idxrd配置，可以確保每個任務均不發(fā)生溢寫。定義Pidx表示map任務的索引數據所占百分比，則有：

2)reduce任務的Smr

reduce任務將拷貝的數據緩存到SR中，只要SR大于每個任務的實際緩存數據大小，reduce任務就不會發(fā)生溢寫，從而獲得最佳運行性能。設表示第j個reduce任務的內存需求，為了確保每個reduce任務不發(fā)生溢寫操作，必須取的最大值，即：

2　求解g( e,s)

設每次minor GC平均暫停時間為tgc，通過實驗數據分析發(fā)現(xiàn)tgc是e的函數，即：

ψ可以通過回歸建模獲得。當已知年輕代對象的總大小s和eden大小e時，可計算出需要執(zhí)行的minor GC的次數Ngc，即：

則minor GC的總時間估計值g( e,s)為：

式(7)為在年輕代對象總需求不變、給定eden大小的條件下，minor GC的總暫停時間。

將式(5)、式(6)帶入式(7)，得：

s可以通過對minor GC日志信息進行統(tǒng)計分析獲得，即：

式中，Oi表示第i-1次minor GC與第i次minor GC期間分配在年輕代對象的大?。籲表示minor GC發(fā)生的次數。使用式(8)可以計算任務在某個eden大小下的GC暫停時間。

3　作業(yè)性能分析與優(yōu)化

3.1map任務性能分析與優(yōu)化

map任務的數據流和工作流如圖1所示，其中灰色方框表示操作，白色方框表示文件。當緩存(即Smr)設置過小時，map任務執(zhí)行過程會發(fā)生多次不必要的溢寫操作，形成多個中間文件。當map處理完所有輸入數據時，將緩存中的記錄以及中間文件中的記錄進行歸并排序，形成單個輸出文件。每條記錄發(fā)生1次溢寫操作將增加1次本地文件讀寫操作，增加歸并排序的時間，因此優(yōu)化目標通過計算合理配置參數達到不執(zhí)行圖1中虛線框部分的操作的目的。

圖1 map任務詳細工作流程

map任務優(yōu)化的實現(xiàn)思路是根據map任務的計數器值計算該任務所需的和大小，并分配相應的緩存空間，因此本文優(yōu)化map任務時不需要構建性能模型。

例如某個作業(yè)的第i個map任務的輸出記錄數為10 485 760，輸出記錄數據為200 MB，則該map任務的則=45%。

3.2reduce任務性能分析與優(yōu)化

reduce階段包含3個子階段，即shuffle階段、排序階段和執(zhí)行reduce函數階段，如圖2所示。shuffle階段主要功能是從map端拷貝數據并保存到緩存中，當的使用比例超過后將數據溢寫到中間文件，當中間文件數量超過閾值后執(zhí)行歸并操作，形成單個更大的中間文件。shuffle階段完成后進入排序階段，主要功能是使用歸并排序算法將中間文件及保留在中的數據進行歸并排序。在執(zhí)行歸并排序之前，mapreduce框架首先將超過JVM最大堆與Pred乘積的數據溢寫到中間文件。排序階段完成后進入執(zhí)行reduce函數的階段，此階段主要將記錄交由reduce函數處理，將結果寫入HDFS文件。本文主要對shuffle階段和排序階段進行優(yōu)化。

圖2 reduce任務詳細工作流程

本文采用以下兩項措施優(yōu)化reduce的數據流和工作流：1)修改Hadoop框架，取消原有框架中reduce任務緩存使用量不能超過2 GB的限制，為實現(xiàn)reduce階段零溢寫提供架構支持；2)通過reduce任務歷史數據計算最優(yōu)的內存配置，獲得零溢寫的最優(yōu)執(zhí)行流程。優(yōu)化后的reduce任務工作流程減少了圖2中的虛線框內的操作。

4　實驗與分析

4.1實驗環(huán)境

Hadoop測試集群有8個從節(jié)點，每個從節(jié)點分配5 GB內存，排他性使用一個E5-2609@2.4GHz的物理核。每個從節(jié)點分配2個map任務槽和1個reduce任務槽，Hadoop以apache發(fā)布版本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左右。

4.2任務年輕代內存分析

使用loess[15]對WD、ID、TS、ADJ的map任務和reduce任務的minor GC進行回歸建模。使用算法1預測的年輕代大小進行測試，統(tǒng)計了4種測試程序的所有map和reduce任務GC暫停時間占任務運行時間的百分比，如圖3所示?？傻弥齏D和ADJ的reduce任務的GC暫停時間的比例大于1%以外，其他任務的GC暫停時間均小于1%。

圖3 年輕代大小預測精度

圖4 wordcount map和reduce任務時間與年輕代的關系

為避免年輕代分配過大導致不必要的資源浪費，分析了WD的map任務和reduce任務運行時間平均值與年輕代的關系，如圖4所示。從圖4得知，年輕代為180 MB左右能獲得較好的運行性能。ID、TS和ADJ也呈現(xiàn)相似的的特征。圖4中獲得的年輕代合理值可以和算法1所得值綜合考慮，選擇兩者的最小值為最終的年輕代大小。

4.3任務年長代內存分析

圖5 4種測試程序的map和reduce任務的Smr分布

統(tǒng)計WD、ID、TS和ADJ的map任務和reduce任務的Smr累計分布函數，其中map任務Smr非常集中，ADJ和TS的reduce任務的Smr也非常集中，WD和ID較分散，但差距也較小，如圖5所示。因此即使采用最大內存需求也不會造成過多內存資源浪費。

pred(即本文提出的內存預測方法)和starfish的優(yōu)化內存配置對比如表1所示。從表1得知pred給出的內存配置均比starfish小。為評價Smr分配是否合理，分別統(tǒng)計了默認配置、starfish和pred這3種配置條件下發(fā)生溢寫的任務數量，如表2所示，其中MSC、MNSC、RSC和RNSC分別表示發(fā)生溢寫的map任務數、未發(fā)生溢寫的map任務數、發(fā)生溢寫的reduce任務數和未發(fā)生溢寫的reduce任務數。未發(fā)生溢寫是任務獲得最佳運行性能的基本條件。從表1和表2得知，pred方法能在比starfish更少的內存配置條件下獲得最佳的任務執(zhí)行流程，即未發(fā)生溢寫操作。

表1 starfish和pred推薦的內存配置

表2 默認配置、starfish推薦配置和pred推薦配置下4種測試程序溢寫任務統(tǒng)計

4.4作業(yè)性能分析

mapreduce配置參數調優(yōu)以starfish最為全面，效果最佳。與基于經驗的配置參數優(yōu)化相比，starfish能獲得更好的性能提升[4]。在starfish0.3.0版本的基礎之上增加了adjlist和invertedindex測試程序的支持，在相同的集群資源下分別比較4種測試程序在默認配置、starfish優(yōu)化配置和pred配置下的運行時間，結果如圖6所示。starfish和pred給出的配置參數顯著提升了作業(yè)性能，且pred性能在4種測試程序下均優(yōu)于starfish。與默認配置相比，starfish在測試集群上平均加速比為3.5，最大加速比為6.1。與默認配置相比，pred的平均加速比為6.4，最大加速比為8。

starfish目前只支持Hadoop0.20版本，要求mapreduce必須使用新API編寫。pred只需要作業(yè)的歷史記錄文件和任務JVM輸出的垃圾回收日志，mapreduce的各個版本均支持通過簡單配置獲得這些數據，因此從部署難度及適應Hadoop版本更新兩個方面講，pred比starfish更易于使用。

圖6 4種測試程序在不同配置下的運行時間對比

文獻[16-17]表明，在facebook、雅虎和淘寶的Hadoop生產集群中，絕大部分的mapreduce作業(yè)的輸入數據只是GB級別，當前的Hadoop集群內存資源足夠將這些待處理的數據全部緩存在內存中。對于這種數據規(guī)模的mapreduce作業(yè)，pred能提供很好的性能優(yōu)化。

5　結 束 語

本文提出一種分代內存大小的預測方法。根據JVM的分代內存管理特點，分別使用不同的方法預測JVM不同分代內存區(qū)域的大小。本文提出的分代內存預測方法綜合考慮了mapreduce層和JVM層的內存配置，是一種更為全面mapreduce作業(yè)內存配置參數優(yōu)化方法。測試結果表明，與默認配置相比，本文給出的內存優(yōu)化配置平均性能提升至6倍，最大達到8倍。與starfish相比，本文提出的方法在提供更好的性能前提下，使用更少的內存資源。

[1]DEAN J,GHEMAWAT S. Mapreduce: Simplified data processing on large clusters[C]//Proceedings of the 6th Conference on Eperating Systems Design and Implementation. Berkeley,CA,USA: USENIX Association,2004,6: 137-150.

[2]POLATO I,Ré R,GOLDMAN A,et al. A comprehensive view of Hadoop research—a systematic literature review[J]. Journal of Network and Computer Applications,2014,46: 1-25.

[3]GERA S. Derive heap size or mapreduce.*.memory.mb. automatically[EB/OL]. [2014-03-08]. https://issues.apache. org/jira/browse/MAPREDUCE-5785.

[4]HERODOTOU H,BABU S. Profiling,what-if analysis,and cost-based optimization of mapreduce programs[J]. Proceedings of the VLDB Endowment,2011,4(11): 1111-1122.

[5]HERODOTOU H. Hadoop performance models[EB/OL]. [2014-12-04]. http://arxiv.org/pdf/1106.0940v1.pdf .

[6]LIU C,ZENG D,YAO H,et al. MR-COF: a genetic mapreduce configuration optimization framework[M]. [S.l.]: Springer International Publishing,2015: 344-357.

[7]LI M,ZENG L,MENG S,et al. MRONLINE: Mapreduce online performance tuning[C]//Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing. Vancouver,Canada: ACM,2014: 165-176.

[8]XU L,LIU J,WEI J. FMEM: a fine-grained memory estimator for mapreduce jobs[C]//Proceedings of the 10th International Conference on Autonomic Computing. California,USA: USENIX in Cooperation with ACM SIGARCH,2013: 65-68.

[9]SINGER J,KOVOOR G,BROWN G,et al. Garbage collection auto-tuning for java mapreduce on multi-cores[J]. ACM SIGPLAN Notices,2011,46(11): 109-118.

[10]KEJARIWAL A. A tool for practical garbage collection analysis in the cloud[C]//2013 IEEE International Conference on Cloud Engineering (IC2E). Boston,USA: IEEE,2013: 46-53.

[11]ANGELOPOULOS V,PARSONS T,MURPHY J,et al. GcLite: an expert tool for analyzing garbage collection behavior[C]//2012 36th IEEEAnnual Computer Software and Applications Conference Workshops (COMPSACW). Lzmir,Turkey: IEEE,2012: 493-502.

[12]SUN M. Memory management in the Java hotspot virtual machine[EB/OL]. [2014-08-28]. http://www. oracle.com/ technetwork/java/javase/memorymanagement-whitepaper-150215.pdf.

[13]RAO S S. Engineering optimization: Theory and practice[M]. New Jersey,USA: John Wiley & Sons,2009.

[14]FARAZ A,SEYONG L,MITHUNA T，et al. PUMA: Purdue mapreduce benchmarks suite[EB/OL]. [2013-09-26]. http://web.ics.purdue.edu/～fahmad/benchmarks. htm.

[15]CLEVELAND W S,DEVLIN S J. Locally weighted regression: an approach to regression analysis by local fitting[J]. Journal of the American Statistical Association,1988,83(403): 596-610.

[16]REN Z,XU X,WAN J,et al. Workload characterization on a production hadoop cluster: A case study on taobao[C]// 2012 IEEE International Symposium on Workload Characterization (IISWC). California,USA: IEEE Computer Society,2012: 3-13.

[17]CHEN Y,GANAPATHI A,GRIFFITH R,et al. The case for evaluating mapreduce performance using workload suites[C]//2011 19th IEEEInternational Symposium on Modeling,Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS). Singapore: IEEE,2011: 390-399

編輯葉芳

An Innovative Memory Prediction Approach for Mapreduce Job

LUO Yong-gang,CHEN Xing-shu,and YANG Lu
(Cybersecurity Research Institutes,Sichuan UniversityChengdu610065)

It is difficult to predict the amount of memory for a mapreduce job. Based on the fact that Java virtual machine (JVM)divides the heap space managed by the JVM garbage collector into young and old generations,a generational memory prediction method is put forward. We build up a function that models the relationship between the amount of young generation and the total garbage collection time,and then we use a constrained nonlinear optimization model to find the rational footprint of young generation. The memory model for the map phase is established,the phase of a mapreduce job is reduced,then a relationship between map/reduce tasks’ performance (runtime of a task)and the amount of memory of the old generation is set up,and finally,the reasonable old generation memory size is obtained. The experimental results show that the proposed approach can accurately predict the memory size of map and reduce the tasks of a mapreduce job. In comparison with the default configuration,the proposed approach can give us 6 times performance improvement than default settings.

garbage collection;JVM;mapreduce;resource management

TP393.08

A

10.3969/j.issn.1001-0548.2016.06.019

2015 ? 11 ? 03；

2016 ? 07 ? 07

國家科技支撐計劃(2012BAH18B05)

羅永剛(1980 ? )，男，博士，主要從事大數據安全方面的研究.