云環(huán)境下大數(shù)據(jù)迭代計算研究.pdf

1、近年來，高速發(fā)展的計算機(jī)存儲和網(wǎng)絡(luò)技術(shù)產(chǎn)生了海量數(shù)據(jù)和大數(shù)據(jù)，云計算的興起也為大數(shù)據(jù)的存儲和計算提供了理想平臺。分析這些數(shù)據(jù)可以更好地幫助人們了解用戶行為和制定商業(yè)決策，而數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、應(yīng)用統(tǒng)計等數(shù)據(jù)分析技術(shù)通常包含迭代計算過程。對海量數(shù)據(jù)進(jìn)行數(shù)次迭代計算是一個極其耗時的過程，并且將消耗大量云資源。加速大數(shù)據(jù)迭代計算的收斂速度，縮短運(yùn)行時間，是當(dāng)今云計算領(lǐng)域的研究熱點(diǎn)，對現(xiàn)實(shí)生產(chǎn)有著重要意義。
　　Google提出的MapR

2、educe模型在批處理計算方面優(yōu)勢明顯，而在處理迭代計算方面存在諸多不足。近年來不斷有專門支持迭代處理的分布式計算框架出現(xiàn)，從優(yōu)化系統(tǒng)和改進(jìn)計算模型兩個方面提高大數(shù)據(jù)迭代計算的性能。
　　本文區(qū)別于這些已有工作，改進(jìn)現(xiàn)有的MapReduce模型，并在迭代計算理論方面做出了創(chuàng)新。論文取得的主要研究成果總結(jié)如下:
　　(1) iMapReduce:為了實(shí)現(xiàn)迭代計算，MapReduce模型需要處理一系列MapReduce作業(yè)，其中

3、每次迭代對應(yīng)一個或若干個MapReduce作業(yè)。這種批處理模型導(dǎo)致了反復(fù)多次的作業(yè)調(diào)度和數(shù)據(jù)加載開銷，限制了MapReduce迭代處理的性能。本文針對MapReduce在迭代處理方面的不足，提出了一種基于MapReduce模型的迭代處理框架——iMapReduce。它只建立一個作業(yè)來避免反復(fù)作業(yè)調(diào)度的開銷，維護(hù)本地靜態(tài)數(shù)據(jù)來避免反復(fù)加載傳輸靜態(tài)數(shù)據(jù)的開銷，并在一次迭代內(nèi)允許異步執(zhí)行Map任務(wù)。通過這些對迭代處理系統(tǒng)優(yōu)化，iMapRedu

4、ce可以有效提升大數(shù)據(jù)迭代計算性能。Amazon EC2上的大規(guī)模實(shí)驗(yàn)顯示，iMapReduce相比Hadoop（MapReduce模型的開源實(shí)現(xiàn)）在處理迭代計算方面可以減少高達(dá)5倍的運(yùn)行時間。
　　(2) PrIter:通過對大量迭代算法的研究，本文發(fā)現(xiàn)了可以提高迭代算法收斂速度的優(yōu)先級處理技術(shù)?，F(xiàn)有迭代計算不加區(qū)別地對所有數(shù)據(jù)單元執(zhí)行迭代更新計算，而在實(shí)際中，廣泛存在的數(shù)據(jù)冪率分布決定了這些數(shù)據(jù)存在較大差異。某些數(shù)據(jù)單元具有較

5、強(qiáng)的代表性，對迭代計算收斂起著更重要的作用。利用這個特點(diǎn)，可以對數(shù)據(jù)單元加以區(qū)分，對那些對算法收斂作用更大的數(shù)據(jù)單元執(zhí)行更頻繁的更新計算，而忽略那些無關(guān)緊要的數(shù)據(jù)單元。本文從理論上證明了優(yōu)先級迭代的正確性和收斂性，并設(shè)計實(shí)現(xiàn)了支持優(yōu)先級迭代的分布式框架——PrIter。大規(guī)模實(shí)驗(yàn)結(jié)果顯示PrIter可以加速Hadoop處理效率高達(dá)50倍，與iMapReduce相比也能得到5至10倍的性能提升。
　　(3) Maiter:迭代計算模

6、型中普遍采用的同步計算模式要求所有計算節(jié)點(diǎn)完成本次迭代的任務(wù)之后才可以開始下一次迭代，這要求首先完成分配任務(wù)的計算節(jié)點(diǎn)要等待未完成任務(wù)的節(jié)點(diǎn)。這在很大程度上限制了分布式系統(tǒng)的處理能力，尤其是在計算節(jié)點(diǎn)之間性能差異較大的分布式環(huán)境中。為了支持異步迭代，本文從理論上推導(dǎo)出累加迭代方法，并證明了異步累加迭代計算的正確性和收斂性，用抽象代數(shù)描述了異步累加迭代的計算模型，并基于此抽象模型設(shè)計實(shí)現(xiàn)了支持異步累加迭代的分布式框架——Maiter。大規(guī)

7、模實(shí)驗(yàn)結(jié)果顯示異步累加迭代模型相比較于同步模型可以獲得5至10倍的性能提升，同時比Hadoop中的迭代計算快達(dá)80倍左右。
　　上述成果的取得，大大提高了迭代計算在云環(huán)境下的收斂速度，減少了運(yùn)行時間。本文部分研究成果已經(jīng)被美國麻州大學(xué)(UMass Amherst)的圖片搜索系統(tǒng)Million Book、卡內(nèi)基梅隆大學(xué)(CMU)的機(jī)器學(xué)習(xí)項(xiàng)目GraphLab、微軟研究院(Microsoft Research)的Daytona項(xiàng)目所采