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

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

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

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

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

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

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

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