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

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

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

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

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

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

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

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