英昌甜 于 炯, 卞 琛 魯 亮 錢育蓉

(1新疆大學(xué)信息科學(xué)與工程學(xué)院, 烏魯木齊 830046)(2新疆大學(xué)軟件學(xué)院, 烏魯木齊 830008)

并行計(jì)算框架Spark的自動(dòng)檢查點(diǎn)策略

英昌甜1于 炯1,2卞 琛1魯 亮1錢育蓉2

(1新疆大學(xué)信息科學(xué)與工程學(xué)院, 烏魯木齊 830046)(2新疆大學(xué)軟件學(xué)院, 烏魯木齊 830008)

針對(duì)現(xiàn)有的Spark檢查點(diǎn)機(jī)制需要編程人員根據(jù)經(jīng)驗(yàn)選擇檢查點(diǎn),具有一定的風(fēng)險(xiǎn)和隨機(jī)性,可能導(dǎo)致恢復(fù)開(kāi)銷較大的問(wèn)題，通過(guò)對(duì)RDD屬性的分析,提出了自動(dòng)檢查點(diǎn)策略,包括權(quán)重生成 (WG)算法和檢查點(diǎn)自動(dòng)選擇(CAS)算法.首先,WG算法分析作業(yè)的DAG結(jié)構(gòu),獲取RDD的血統(tǒng)長(zhǎng)度和操作復(fù)雜度等屬性,計(jì)算RDD權(quán)重;然后,CAS算法選擇權(quán)重大的RDD作為檢查點(diǎn)進(jìn)行異步備份,來(lái)實(shí)現(xiàn)數(shù)據(jù)的快速恢復(fù).結(jié)果表明:在使用CAS算法時(shí),不同數(shù)據(jù)集執(zhí)行時(shí)間和檢查點(diǎn)容量大小都有所增加,其中Wiki-Talk由于其計(jì)算量較大,增幅明顯;使用CAS算法設(shè)置檢查點(diǎn)后,在單點(diǎn)失效恢復(fù)的情況下,數(shù)據(jù)集的恢復(fù)時(shí)間較短.因此,自動(dòng)檢查點(diǎn)策略在略微增加執(zhí)行時(shí)間開(kāi)銷的基礎(chǔ)上,能夠有效地降低作業(yè)的恢復(fù)開(kāi)銷.

自動(dòng)檢查點(diǎn);RDD權(quán)重; Spark; 恢復(fù)時(shí)間

近年來(lái),隨著數(shù)據(jù)量的爆炸式增長(zhǎng),對(duì)大數(shù)據(jù)[1-2]的處理和分析已經(jīng)成為企業(yè)界和學(xué)術(shù)界的迫切需求,利用內(nèi)存的低延遲特性來(lái)提升系統(tǒng)性能成為了研究的熱點(diǎn).Spark[3-4]以其低延時(shí)的出色表現(xiàn),利用Scala強(qiáng)有力的函數(shù)式編程、Actor通信模式、閉包、容器、泛型,借助統(tǒng)一資源分配調(diào)度框架Mesos,融合了MapReduce和Dryad,正在成為最具影響的基于內(nèi)存的并行計(jì)算框架之一.

現(xiàn)有的多種計(jì)算框架的容錯(cuò)和檢查點(diǎn)[5-7]策略各有不同,例如Storm和Apache S4[8]都由Zookeeper為其提供容錯(cuò),但Storm不設(shè)置檢查點(diǎn),Apache S4提供設(shè)置異步檢查點(diǎn)的機(jī)制.而基于內(nèi)存的分布式文件系統(tǒng)RAMCloud[9]和Tachyon[10]則分別利用集群并發(fā)能力和高速帶寬的Infiniband,以及使用Edge算法對(duì)有向無(wú)環(huán)圖(directed acyclic graph, DAG)葉子節(jié)點(diǎn)所對(duì)應(yīng)的文件進(jìn)行信息備份,來(lái)實(shí)現(xiàn)容錯(cuò)的目的.

與已有研究不同的是,Spark通過(guò)數(shù)據(jù)集血統(tǒng)(lineage)和檢查點(diǎn)(checkpoint)機(jī)制實(shí)現(xiàn)容錯(cuò),由編程人員負(fù)責(zé)選擇檢查點(diǎn)并進(jìn)行設(shè)置.由于編程人員往往根據(jù)經(jīng)驗(yàn)選擇檢查點(diǎn),如果檢查點(diǎn)選擇不當(dāng),不僅降低應(yīng)用程序的恢復(fù)效率,還可能增加程序異常的風(fēng)險(xiǎn).為此,本文通過(guò)分析Spark作業(yè)執(zhí)行機(jī)制,定義了作業(yè)和彈性分布式數(shù)據(jù)集(resilient distribution datasets,RDD)的執(zhí)行時(shí)間和恢復(fù)時(shí)間,并在此基礎(chǔ)上,根據(jù)RDD的不同屬性,提出自動(dòng)檢查點(diǎn)策略(包括權(quán)重生成算法和自動(dòng)檢查點(diǎn)算法),從而應(yīng)對(duì)突發(fā)性的宕機(jī)風(fēng)險(xiǎn),提高作業(yè)恢復(fù)效率.

1 模型與相關(guān)定義

1.1 作業(yè)執(zhí)行模型

定義1 集群節(jié)點(diǎn).設(shè)Spark并行計(jì)算集群由集合N={n1,n2,…,nm}組成,其中nm表示第m個(gè)節(jié)點(diǎn).節(jié)點(diǎn)nm上的資源可由三元組〈fm,gm,hm〉表示,分別表示內(nèi)存大小、磁盤讀寫速率和網(wǎng)絡(luò)速率.

定義2 節(jié)點(diǎn)狀態(tài).設(shè)S表示集群所有的節(jié)點(diǎn)狀態(tài),U={u1,u2,…,um},ui∈{a,ua}表示節(jié)點(diǎn)nm當(dāng)前所處的狀態(tài),其中a, ua分別表示可用和不可用,系統(tǒng)故障、電源中斷、硬件故障等原因都有可能造成節(jié)點(diǎn)處于ua狀態(tài).

定義3 資源分配.記J={1,2,…,n}為Spark框架一個(gè)時(shí)間段內(nèi)同時(shí)運(yùn)行的作業(yè),對(duì)于作業(yè)i,記Ai={Ai1,Ai2,…,Ail}為在群集中的資源分配量.由于Spark保證所有作業(yè)的并發(fā)執(zhí)行,當(dāng)且僅當(dāng)每個(gè)工作節(jié)點(diǎn)的資源都不會(huì)溢出,即

(1)

定義4 作業(yè)執(zhí)行時(shí)間.Spark根據(jù)寬依賴作為分界,將作業(yè)劃分為多個(gè)階段(stage)執(zhí)行.若作業(yè)劃分為u個(gè)階段,每個(gè)階段的計(jì)算時(shí)間定義為Tst,i,則作業(yè)的執(zhí)行時(shí)間Tjob為

(2)

若第i個(gè)階段包含v個(gè)RDD,記TR,ij為其第j個(gè)RDD的計(jì)算時(shí)間,那么該階段的執(zhí)行時(shí)間應(yīng)為該階段所有RDD計(jì)算時(shí)間的總和,即

(3)

因此,作業(yè)執(zhí)行時(shí)間Tjob則為

(4)

定義5 RDD執(zhí)行時(shí)間.記TP,ijk表示第i個(gè)階段中第j個(gè)RDD的第k個(gè)分區(qū)的計(jì)算時(shí)間,則該RDD計(jì)算時(shí)間為所有分區(qū)計(jì)算時(shí)間的最大值,即

TR,ij=max(TP,ij1,TP,ij2,…,TP,ijk)

(5)

分區(qū)的執(zhí)行時(shí)間TP,ijk為讀取父分區(qū)數(shù)據(jù)的時(shí)間dPa,ijk與父分區(qū)處理時(shí)間cPa,ijk之和,即

TP,ijk=dPa,ijk+cPa,ijk

(6)

若所有父分區(qū)都存儲(chǔ)在同一節(jié)點(diǎn)內(nèi)存中,則數(shù)據(jù)讀取代價(jià)可以忽略,即

dPa,ijk=0

若父分區(qū)存儲(chǔ)在節(jié)點(diǎn)nm的內(nèi)存中,則數(shù)據(jù)讀取的代價(jià)與其數(shù)據(jù)容量Sijk大小成正比，網(wǎng)絡(luò)帶寬速率成反比,即

(7)

若父分區(qū)存儲(chǔ)在節(jié)點(diǎn)nm磁盤中,則為

(8)

1.2 作業(yè)恢復(fù)模型

定義6 作業(yè)恢復(fù)時(shí)間.在作業(yè)執(zhí)行過(guò)程中,若單個(gè)或多個(gè)節(jié)點(diǎn)產(chǎn)生故障,即節(jié)點(diǎn)處于ua狀態(tài),則作業(yè)恢復(fù)時(shí)間為恢復(fù)節(jié)點(diǎn)上所丟失RDD需要的時(shí)間.若故障次數(shù)為0,則沒(méi)有作業(yè)恢復(fù)開(kāi)銷.若故障次數(shù)為k,則為k次故障時(shí),恢復(fù)RDD所用時(shí)間eR,ij.設(shè)找到空閑節(jié)點(diǎn),并分配恢復(fù)工作所需的調(diào)度開(kāi)銷定義為α,則作業(yè)的恢復(fù)開(kāi)銷ejob為

(9)

定義7 RDD恢復(fù)時(shí)間.設(shè)檢查點(diǎn)集合為O={o1,o2,…,op},其中op為作業(yè)的第k個(gè)RDD,也是設(shè)置的最新檢查點(diǎn).當(dāng)前執(zhí)行到第i個(gè)階段第j個(gè)RDD時(shí),節(jié)點(diǎn)故障宕機(jī)導(dǎo)致RDD丟失,此時(shí)所需的恢復(fù)時(shí)間為

eR,ij=α+TR,i(k+1)+TR,i(k+2)+…+TR,ij=

(10)

若未設(shè)置檢查點(diǎn)時(shí),則重新計(jì)算所有RDD，即

(11)

而丟失分區(qū)的恢復(fù)需要通過(guò)父分區(qū)進(jìn)行恢復(fù),最終需要檢查點(diǎn)進(jìn)行恢復(fù).因此,恢復(fù)第j個(gè)分區(qū)的時(shí)間為

eP,ijk=α+dPa,ijk+cPa,ijk

(12)

由此可知,檢查點(diǎn)的選擇和恢復(fù)檢查點(diǎn)所用的時(shí)間都是影響作業(yè)恢復(fù)效率的重要因素.在宕機(jī)時(shí), 作業(yè)用于恢復(fù)的開(kāi)銷越小,對(duì)作業(yè)執(zhí)行效率的影響就越小.因此,自動(dòng)檢查點(diǎn)策略則在系統(tǒng)資源滿足作業(yè)需求的情況下,以最小化作業(yè)恢復(fù)開(kāi)銷為目的.

定義8 RDD權(quán)重.通過(guò)分析,與恢復(fù)開(kāi)銷相關(guān)的主要因素有血統(tǒng)長(zhǎng)度LR,ij、操作類型OR,ij、計(jì)算時(shí)間TR,ij和容量大小SR,ij.因此,將RDD的權(quán)重表示如下:

(13)

式(13)表明,血統(tǒng)長(zhǎng)度對(duì)權(quán)重起決定性作用,血統(tǒng)越長(zhǎng),表示恢復(fù)時(shí)的計(jì)算路徑越長(zhǎng),作為檢查點(diǎn)備份的必要性就越大.而RDD類型、計(jì)算時(shí)間和RDD容量對(duì)權(quán)重起輔助作用,因?yàn)檫@3個(gè)因素對(duì)恢復(fù)開(kāi)銷的影響有限.

2 自動(dòng)檢查點(diǎn)策略

自動(dòng)檢查點(diǎn)策略根據(jù)作業(yè)的血統(tǒng)圖,分析RDD屬性,利用權(quán)重生成算法計(jì)算RDD的權(quán)重.在作業(yè)執(zhí)行時(shí),后臺(tái)執(zhí)行檢查點(diǎn)設(shè)置算法,根據(jù)當(dāng)前的執(zhí)行狀態(tài),選擇權(quán)重最大的RDD作為檢查點(diǎn)備份到磁盤.在節(jié)點(diǎn)失效時(shí),Spark系統(tǒng)的恢復(fù)機(jī)制利用已設(shè)置的檢查點(diǎn)進(jìn)行快速恢復(fù).

2.1 權(quán)重生成算法

權(quán)重生成(weight generated, WG)算法在執(zhí)行作業(yè)前,遍歷作業(yè)的DAG圖,生成RDD結(jié)構(gòu)樹(shù),獲得每個(gè)RDD的操作和屬性,并根據(jù)式(13)計(jì)算權(quán)重,具體過(guò)程如算法1所示.

算法1 權(quán)重生成算法

輸入:結(jié)構(gòu)樹(shù)RDDtree; RDD計(jì)算時(shí)間T;

fori=0 to RDDtree.Length-1 do

RDD[i].L←GetDepth(RDDtree[i])

//獲得血統(tǒng)長(zhǎng)度

if (RDDtree[i].operation==WideDependency)

then

RDD[i].O←RDDtree[i].partition(num)

Widedependencylist.add(treeRDDs[i]);

else if (RDDtree[i].operation==NarrowDep endency)

RDD[i].O←1

//生成操作復(fù)雜度

end if

Weightlist.add(RDD[i]);

Weightlist [i]←calcWeight(RDD[i]);

//計(jì)算權(quán)重

end for

2.2 檢查點(diǎn)自動(dòng)選擇算法

檢查點(diǎn)自動(dòng)選擇算法(checkpoint automatic selection, CAS)的步驟為:① 作業(yè)開(kāi)始執(zhí)行時(shí),設(shè)置檢查點(diǎn)列表為空;② 添加生成的第1個(gè)RDD作為檢查點(diǎn),并添加到檢查點(diǎn)列表;③ 獲取當(dāng)前最新生成的RDD列表;④ 通過(guò)Spark 用戶接口(user interface, UI)獲取已生成RDD的開(kāi)始時(shí)間和結(jié)束時(shí)間,則結(jié)束時(shí)間與開(kāi)始時(shí)間之差為RDD的計(jì)算代價(jià);⑤ 獲取已生成RDD所屬多個(gè)分區(qū)的容量大小,求和計(jì)算得到RDD容量大小;⑥ 通過(guò)調(diào)用算法1,計(jì)算 RDD的權(quán)重;⑦ 比較已生成列表中的RDD,并將權(quán)重最大的RDD自動(dòng)設(shè)置為檢查點(diǎn),添加到檢查點(diǎn)序列;⑧ 等待檢查點(diǎn)寫入HDFS成功后,對(duì)結(jié)構(gòu)樹(shù)RDDtree剪枝, 切斷已設(shè)置檢查點(diǎn)前的血統(tǒng);⑨ 若作業(yè)結(jié)束, 則跳出循環(huán),否則跳轉(zhuǎn)到步驟③.

算法2 檢查點(diǎn)自動(dòng)選擇算法

輸入:結(jié)構(gòu)樹(shù)RDDtree;

checkpointList←null;

maxWeight←0;

visit(RDDTree);

RDDtree.length←getlength(RDDtree);

fori=0 to RDDtree.length-1

newRDD [i]←generatenewRDD;

while(newRDD[1]!=null&&checkpointList==null)

checkpoint(newRDD[0]);

checkpointList←addToList(newRDD[0]);

end while

//設(shè)置生成的第1個(gè)RDD為檢查點(diǎn)

if(newRDD!=null)

newRDD.length←getLength(newRDD)

end if

forj=0 to newRDD.length-1 do

newRDD[j].T←newRDD[j].finishTime-newRDD[j].startTime;

fork=0 to RDD[j].partition.num-1

RDD[j].S←sum(partition[j][k].size);

end for

//獲取RDD的計(jì)算時(shí)間和容量大小

call algorithm1;//計(jì)算RDD的權(quán)重

if(RDD[j].wt>maxwt)

then maxwt←RDD[j].wt;

maxwtRDD←RDD[j];

//選擇權(quán)重最大的RDD

end if

end for

checkpoint(maxwtRDD);

writeToHDFS(maxwtRDD);

checkpointList←addToList(maxwtRDD);

cutlineage(RDDTree, maxwtRDD);

end for

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)環(huán)境用1臺(tái)服務(wù)器和8個(gè)工作節(jié)點(diǎn)建立計(jì)算群集,服務(wù)器作為Spark和Hadoop的主節(jié)點(diǎn),工作節(jié)點(diǎn)配置如表1所示.

表1 工作節(jié)點(diǎn)配置參數(shù)

3.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用PageRank算法進(jìn)行系統(tǒng)性能測(cè)試,使用nmon監(jiān)控任務(wù)執(zhí)行時(shí)間和檢查點(diǎn)大小.實(shí)驗(yàn)數(shù)據(jù)選用斯坦福網(wǎng)絡(luò)分析平臺(tái)(stanford network analysis platform, SNAP)提供的有向圖數(shù)據(jù)集.不同數(shù)據(jù)集在PageRank任務(wù)下檢查點(diǎn)自動(dòng)選擇算法的執(zhí)行效率、檢查點(diǎn)大小和檢查點(diǎn)存儲(chǔ)處理平均時(shí)間如圖1～3所示.

如圖1所示,4個(gè)不同的數(shù)據(jù)集(Web-Standard,Amazon0312,Wiki-Talk,Web-Google)在使用CAS時(shí)對(duì)PageRank作業(yè)都有額外影響,導(dǎo)致作業(yè)的執(zhí)行時(shí)間比原Spark略微增加.由于使用CAS時(shí),需要獲取RDD屬性信息和作業(yè)執(zhí)行狀態(tài)信息,基于權(quán)重值選擇檢查點(diǎn)備份會(huì)產(chǎn)生額外開(kāi)銷.另外, 在相同迭代次數(shù)不同數(shù)據(jù)集之間對(duì)比,Wiki-Talk的執(zhí)行時(shí)間最長(zhǎng),而Web-Standard的執(zhí)行時(shí)間最短.數(shù)據(jù)集的節(jié)點(diǎn)數(shù)和連線數(shù)越大,則需要計(jì)算的數(shù)據(jù)量越大,執(zhí)行時(shí)間越長(zhǎng).由圖2可知,在相同數(shù)據(jù)集時(shí),由于迭代次數(shù)的增加,設(shè)置作為檢查點(diǎn)的RDD數(shù)量增加,檢查點(diǎn)的總?cè)萘恳搽S之增

圖1 檢查點(diǎn)自動(dòng)選擇算法的執(zhí)行時(shí)間

圖2 檢查點(diǎn)自動(dòng)選擇算法的檢查點(diǎn)大小

圖3 檢查點(diǎn)自動(dòng)選擇算法的檢查點(diǎn)平均時(shí)間開(kāi)銷

加.同時(shí),Wiki-Talk相同迭代次數(shù)下,檢查點(diǎn)大小明顯高于其他3個(gè)數(shù)據(jù)集,Wiki-Talk的計(jì)算數(shù)據(jù)量較大,因此作為檢查點(diǎn)的RDD容量也較大.

由圖3可看出,不同數(shù)據(jù)集之間,當(dāng)數(shù)據(jù)集計(jì)算量較大,檢查點(diǎn)個(gè)數(shù)增加時(shí),對(duì)應(yīng)檢查點(diǎn)存儲(chǔ)設(shè)置的平均時(shí)間開(kāi)銷也隨之增加,并且隨著迭代次數(shù)的增加, 對(duì)檢查點(diǎn)平均時(shí)間開(kāi)銷的影響也減少.

如圖4所示,4個(gè)數(shù)據(jù)集在節(jié)點(diǎn)單次失效的情況下,PageRank算法在設(shè)置與未設(shè)置檢查點(diǎn)時(shí)執(zhí)行時(shí)間和恢復(fù)情況對(duì)比.隨著迭代次數(shù)的增加,設(shè)置檢查點(diǎn)的執(zhí)行效率明顯優(yōu)于未設(shè)置檢查點(diǎn)的情況,因?yàn)槲丛O(shè)置檢查點(diǎn)時(shí)僅通過(guò)RDD血統(tǒng)從頭計(jì)算來(lái)實(shí)現(xiàn)恢復(fù),在宕機(jī)時(shí)迭代次數(shù)越大,則恢復(fù)所需的時(shí)間就越長(zhǎng).

圖4 設(shè)置檢查點(diǎn)與未設(shè)置檢查點(diǎn)的恢復(fù)效率對(duì)比

結(jié)合圖1～4可知,當(dāng)Spark采用檢查點(diǎn)自動(dòng)選擇算法執(zhí)行PageRank時(shí),其執(zhí)行時(shí)間要略高于傳統(tǒng)Spark任務(wù).然而,在出現(xiàn)單點(diǎn)故障需要恢復(fù)時(shí), 4個(gè)數(shù)據(jù)集使用自動(dòng)設(shè)置檢查點(diǎn)算法時(shí),恢復(fù)效率較高,比未設(shè)置檢查點(diǎn)算法所用的恢復(fù)時(shí)間短.

4 結(jié)語(yǔ)

為了避免Spark框架下人工設(shè)置檢查點(diǎn)可能出現(xiàn)的不確定性和風(fēng)險(xiǎn),定義了Spark框架下RDD和作業(yè)的計(jì)算代價(jià)、恢復(fù)代價(jià),通過(guò)分析RDD屬性,確定了與恢復(fù)開(kāi)銷相關(guān)的RDD權(quán)重.在此基礎(chǔ)上設(shè)計(jì)了權(quán)重生成算法和檢查點(diǎn)自動(dòng)選擇算法,使系統(tǒng)在作業(yè)執(zhí)行時(shí)自動(dòng)識(shí)別有價(jià)值的RDD作為檢查點(diǎn)，進(jìn)行持久化存儲(chǔ),并在系統(tǒng)宕機(jī)時(shí)利用檢查點(diǎn)執(zhí)行恢復(fù).最后通過(guò)不同數(shù)據(jù)集的實(shí)驗(yàn),驗(yàn)證了自動(dòng)檢查點(diǎn)策略的有效性.下一步的研究方向是分析在多點(diǎn)多次故障時(shí),不同的檢查點(diǎn)恢復(fù)策略對(duì)于作業(yè)恢復(fù)效率的影響.

References)

[1]孟小峰, 慈祥. 大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1):146-169.DOI:10.7544/issn1000-1239.2013.20121130. Meng Xiaofeng,Ci Xiang. Big data management: Concepts,techniques and challenges [J].JournalofComputerResearchandDevelopment, 2013, 50(1): 146-169.DOI:10.7544/issn1000-1239.2013.20121130. (in Chinese)

[2]王元卓, 靳小龍, 程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù):現(xiàn)狀與展望[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(6):1125-1138.DOI: 10.3724/SP.J.1016.2013.01125. Wang Yuanzhuo, Jin Xiaolong, Cheng Xueqi. Network big data: Present and future [J].ChineseJournalofComputers, 2013, 36(6):1125-1138.DOI: 10.3724/SP.J.1016.2013.01125. (in Chinese)

[3]Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[C]//UsenixConferenceonHotTopicsinCloudComputing.Berkeley, CA, USA: USenix Association, 2010:1765-1773.

[4]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]//UsenixConferenceonNetworkedSystemsDesignandImplementation.Berkeley,CA, USA:USenix Association, 2012:141-146.

[5]易會(huì)戰(zhàn), 王鋒, 左克, 等. 基于內(nèi)存緩存的異步檢查點(diǎn)容錯(cuò)技術(shù)[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(6):1229-1239. DOI: 10.7544/issn1000-1239.2014.20121125. Yi Huizhan, Wang Feng, Zuo Ke, et al. Asynchronous checkpoint/restart based on memory buffer[J].JournalofComputerResearchandDevelopment, 2014, 51(6): 1229-1239. DOI: 10.7544/issn1000-1239.2014.20121125. (in Chinese)

[6]慈軼為,張展,左德承,等. 可擴(kuò)展的多周期檢查點(diǎn)設(shè)置[J]. 軟件學(xué)報(bào), 2010, 21(2): 218-230. DOI: 10.3724/SP.J.1001.2010.03787. Ci Yiwei, Zhang Zhan, Zuo Decheng, et al. Scalable time-based multi-cycle checkpointing[J].JournalofSoftware, 2010, 21(2): 218-230. DOI: 10.3724/SP.J.1001.2010.03787. (in Chinese)

[7]吳俊.基于雙優(yōu)先級(jí)隊(duì)列的異構(gòu)分布式控制系統(tǒng)容錯(cuò)調(diào)度算法[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,38(3):407-412. DOI:10.3321/j.issn:1001-0505.2008.03.009. Wu Jun.Fault-tolerant scheduling algorithm for heterogeneous distributed control systems based on dual priorities queues[J].JournalofSoutheastUniversity(NaturalScienceEdition),2008,38(3):407-412. DOI:10.3321/j.issn:1001-0505.2008.03.009. (in Chinese)

[8]Neumeyer L, Robbins B, Nair A, et al. S4: Distributed stream computing platform[C]//IEEEInternationalConferenceonDataMiningWorkshops. Piscataway, New Jersey, USA: IEEE, 2010: 170-177. DOI: 10.1109/ICDMW.2010.172.

[9]Ongaro D, Rumble S M, Stutsman R, et al. Fast crash recovery in RAMCloud[C]//ACMSymposiumonOperatingSystemsPrinciples. New York, US:ACM, 2011:29-41. DOI: 10.1145/2043556.2043560.

[10]Li H Y,Ghodsi A, Zaharia M, et al.Tachyon: Reliable, memory speed storage for cluster computing frameworks [C]//IEEEConferenceonSYSTEM-ON-CHIP. Piscataway, New Jersey, USA: IEEE, 2014: 1-15. DOI: 10.1145/2670979.2670985.

Automatic checkpoint strategy for parallel computing frame with Spark

Ying Changtian1Yu Jiong1,2Bian Chen1Lu Liang1Qian Yurong2

(1School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China)(2School of Software, Xinjiang University, Urumqi 830008,China)

The existing Spark checkpoint mechanism required the programmer to choose the checkpoint according to the experience, thus it had a certain risk and randomness, resulting in large recovery overhead. To address this problem, the resilient distribution datasets (RDD) characteristics were analyzed, and the weight generated (WG)algorithm and checkpoint automatic selection (CAS) algorithm were put forward.First, in the WG algorithm, the directed acyclic graph (DAG) of the job was analyzed, and the lineage length and the operation complexity of RDD were obtained to compute the RDD weight. Secondly, in the CAS algorithm, the RDD with the maximum weight was selected for setting checkpoints asynchronously to fast recovery. The experimental results show that comparing with the original Spark, the execution time and the checkpoint size of different datasets are increased by the CAS algorithm, while the increasing extent of Wiki-Talk is more obvious. For the single node failure recovery, the datasets have smaller recovery overhead after setting checkpoint by using the CAS algorithm. Therefore, the strategy can efficiently decrease the recovery overhead of jobs with sacrificing the slight extra overhead.

automatic checkpoint; resilient distribution dataset (RDD) weight;Spark; recovery time

10.3969/j.issn.1001-0505.2017.02.006

2016-11-12. 作者簡(jiǎn)介: 英昌甜(1989—), 女, 博士生；于炯(聯(lián)系人), 男, 博士, 教授, 博士生導(dǎo)師, yujiong@xju.edu.cn.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61462079，61262088，61562086，61363083，61562078)、新疆維吾爾自治區(qū)高校科研計(jì)劃資助項(xiàng)目(XJEDU2016S106).

英昌甜，于炯,卞琛,等.并行計(jì)算框架Spark的自動(dòng)檢查點(diǎn)策略[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(2):231-235.

10.3969/j.issn.1001-0505.2017.02.006.

TP311

A

1001-0505(2017)02-0231-05