基于MapReduce的單源最短路徑算法研究

1、1.2 相關(guān)數(shù)據(jù)結(jié)構(gòu)定義為了減少數(shù)據(jù)冗余, 本文對(duì)于圖的表示方法采用鄰接表的 方式進(jìn)行存儲(chǔ),以各頂點(diǎn)為中心,每一行代表圖中的一個(gè)頂點(diǎn),各頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)描述如下:其中,id 為頂點(diǎn)標(biāo)識(shí);distance 表示從源點(diǎn)到頂點(diǎn)的距離,除 到本身的距離為 0 外,其余初始值皆為無窮大 max;flag 為標(biāo)志 位, 其值可分別取 0、1、2,0 表示未處理的頂點(diǎn),1 表示正待處理 的頂點(diǎn),2 表示已經(jīng)處理了的頂點(diǎn),源點(diǎn)的初始值為 1,其余頂點(diǎn) 皆為 0;adjacent information 代表鄰接信息,包括頂點(diǎn)的鄰接點(diǎn)及 其權(quán)值。如圖 1 用鄰接表表示的數(shù)據(jù)結(jié)構(gòu)如圖 2 所示:圖 1 帶權(quán)有向圖 g

2、圖 2 用鄰接表表示圖 1 的數(shù)據(jù)結(jié)構(gòu)圖 3 基于 mapreduce 的單源最短路徑算法的執(zhí)行過程文章編號(hào):1008-0570(2011)12-0097-03基于的單源最短路徑算法研究mapreduceresearch on the single source shortest path algorithm using mapreduce(湖南大學(xué)) 楊玲 李仁發(fā) 唐 卓yang ling li ren-fa tang zhuo摘要: 通 過 對(duì) mapreduce 模型執(zhí)行過程的分析 ,針 對(duì) 單 源最短路徑算法難以隨著云計(jì)算的產(chǎn)生和發(fā)展而應(yīng)用及提高搜索效 率 的 問 題, 本文設(shè)計(jì)和實(shí)現(xiàn)

3、了一種基于 mapreduce 架構(gòu)的并行單源最短路徑算法 。 并 基 于 hadoop 平臺(tái)集群環(huán)境進(jìn)行了研究 與 實(shí) 驗(yàn), 結(jié) 果 表 明, 文中算法可以有效地找出整個(gè)圖結(jié)構(gòu)中的單源最短路徑 , 且驗(yàn)證了算法性能的優(yōu)越性 。關(guān)鍵詞: mapreduce; 并行; 最短路徑; hadoop中圖分類號(hào): tp393.0文獻(xiàn)標(biāo)識(shí)碼: aabstract: via the analysis to implementation process of mapreduce, aimming at the problem that single source shortest path algorithm

4、is hard to be used with the appearance and development of cloud computing and the problem of searching efficiency,a parallel single source shortest path algorithm based on mapreduce framework is designed and implemented .research and experiment are done based on hadoop platform.as shown by the exper

5、imental results,the proposed algorithm can search the single source shortest path efficiently in the whole graphic structure,and its good performance is testified.key words: mapreduce; parallel; shortest path; hadoop引言計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展促進(jìn)了云計(jì)算的產(chǎn)生。mapreduce 并行編程模型是云計(jì)算的核心技術(shù)之一,2005 年 4 月 6 日, google 實(shí) 驗(yàn) 室 的 jef

6、frey dean 和 sanjay ghemawat 提 出 了 mapreduce 模型并進(jìn)行了詳細(xì)地闡述, 它為并行系統(tǒng)的數(shù)據(jù)處 理提供了一個(gè)簡(jiǎn)單、優(yōu)雅的解決方案。apache 基金會(huì)基于 java 開發(fā)了一個(gè)分布式基礎(chǔ)架構(gòu) hadoop, 實(shí)現(xiàn)了 mapreduce 模型, 并提供了分布式計(jì)算平臺(tái)。在通信網(wǎng)絡(luò)與交通網(wǎng)絡(luò)中, 并行問題和最短路徑問題一直 是研究的熱點(diǎn), 有著極其重要的作用。在處理實(shí)際問題的過程 中, 通常將現(xiàn)實(shí)問題轉(zhuǎn)化為圖的網(wǎng)狀形式來研究最短路徑。而 mapreduce 并行計(jì)算模型的出現(xiàn), 為解決大規(guī)模數(shù)據(jù)處理問題 提供了一種新的途徑, 也為最短路徑的并行計(jì)算帶來了一種

7、新 的解決方法,有效提高了計(jì)算效率。本文提出了基于 mapreduce 的單源最短路徑算法。首先利 用 mapreduce 架構(gòu)來形成算法的并行化思想,分析并設(shè)計(jì)了算法的過程,然后通過 hadoop 平臺(tái)來實(shí)現(xiàn)算法,最后對(duì)實(shí)驗(yàn)結(jié)果 進(jìn)行了分析。算法及其數(shù)據(jù)結(jié)構(gòu)的定義11.1 單源最短路徑算法單源最短路徑是指給定一個(gè)帶權(quán)有向圖 g=(v,e,w),其中 v 為頂點(diǎn)集,e 為有向邊集,w 為權(quán)集且每條邊的權(quán)是一個(gè)非負(fù)實(shí) 數(shù)。另外,還給定 v 中的一個(gè)頂點(diǎn),稱為源,計(jì)算從源到所有其他 各頂點(diǎn)的最短路徑長(zhǎng)度。這里的長(zhǎng)度是指各邊權(quán)之和,根據(jù)不同 的實(shí)際情況,邊上權(quán)值的長(zhǎng)度可以表示成時(shí)間、距離、成本、損失

8、、損耗或其它任何沿一條路徑的相加累積量,且為最小值。楊 玲: 碩士研究生郵局訂閱號(hào)：82-946 120 元 / 年 - 97 -plc 技術(shù)應(yīng)用 200 例2 基 于 mapreduce 的 單 源 最 短 路 徑算法的設(shè)計(jì)與實(shí)現(xiàn)mapreduce 用戶用兩個(gè)函數(shù)表達(dá)這個(gè)計(jì)算:map 和 reduce。 在 mapredcue 模型中,用戶指定一個(gè) map 函數(shù)來處理一個(gè)輸入 的 key/value 對(duì),產(chǎn)生中間結(jié)果 key/value 對(duì)集,再通過 reduce 函 數(shù)來處理中間結(jié)果中具有相同 key 值的 value。基于 mapreduce 的單源最短路徑算法的執(zhí)行過程如圖 3所示。(

9、1)輸入數(shù)據(jù)的切分:mapreduce 對(duì)輸入文件按行(每行代表 圖中的一個(gè)頂點(diǎn)) 進(jìn)行自動(dòng)切分, 并將數(shù)據(jù)分發(fā)到每個(gè) map 任務(wù), 其中 key 值為 id,value 值為 distance、flag 和 adjacent infor圖 5 map 算法過程mation;(2)map 任務(wù)的執(zhí)行:接收 key/value 對(duì),當(dāng) value 中的 flag 的 值為 1 時(shí),則處理當(dāng)前頂點(diǎn),主要處理當(dāng)前頂點(diǎn)的鄰接點(diǎn),并將其鄰接點(diǎn)的 flag 也置為 1,最后產(chǎn)生臨時(shí)的 key/value 對(duì)集;圖 6 reduce 過程的輸入和輸出(3)臨時(shí)結(jié)果的分組:mapreduce 框架對(duì) map

10、 執(zhí)行過程輸出 的臨時(shí)結(jié)果進(jìn)行分組, 將相同的 key 值即 id 號(hào)合并成同一組,并將其分發(fā)給空閑的 reduce;(4)reduce 任務(wù)的執(zhí)行:接收 key/value 對(duì),對(duì)相同 id 的 value進(jìn)行合并,找到當(dāng)前的最短路徑;(5)mapreduce 的迭代:如圖 3 所示,每次 reduce 后的結(jié)果 又分發(fā)給下一輪的 map 過程,通過多次迭代尋找到最終的最短 路徑。當(dāng)沒有發(fā)現(xiàn)更好的距離時(shí),節(jié)點(diǎn)間的遍歷會(huì)停止,本文中是以 flag 位來判斷的, 即當(dāng) reduce 中所有記錄的 flag 位都不為1 時(shí),則停止迭代,算法結(jié)束。2.1 map 過程map 函數(shù)對(duì)整個(gè)圖的結(jié)構(gòu)進(jìn)行遍

11、歷,采用 bfs 算法(即廣度優(yōu)先算法)思路,按層依次遍歷整個(gè)圖。map 函數(shù)根據(jù)所接到的圖 7 reduce 算法過程key/value 對(duì)(即每個(gè)頂點(diǎn)的相關(guān)信息)來產(chǎn)生相關(guān)的輸出。輸出 主要分兩種,一種是本身結(jié)點(diǎn)的信息,在處理完后,僅對(duì)信息的標(biāo)志位進(jìn)行更改;一種是對(duì)本結(jié)點(diǎn)的鄰接點(diǎn)進(jìn)行遍歷。具體如圖 4所示。圖 4 map 過程的輸入和輸出本文將圖 1 中的有向圖 g 的頂點(diǎn) v0 的基本信息作為 map 圖 8 基于 mapreduce 的有向圖 g 的第一次迭代過程 的輸入,其輸入值為0,經(jīng)過 map 函數(shù)2.3 mapreduce 的迭代過程執(zhí)行后,其輸出結(jié)果為0,、,詳細(xì)過程可參見圖

12、 3。業(yè)的 reduce 輸出作為下一個(gè) mapreduce 作業(yè)的 map 輸入,這map 算法過程如圖 5 所示。樣就形成了整個(gè)工作鏈。當(dāng)某個(gè)作業(yè)的輸出中所有的節(jié)點(diǎn)都沒2.2 reduce 過程有標(biāo)志位為 1 的節(jié)點(diǎn)時(shí),則停止迭代,算法終結(jié)。具體可參見圖 3reduce 過程對(duì)從各個(gè) map 對(duì)各頂點(diǎn)的處理結(jié)果進(jìn)行聚集中所示的整個(gè)算法執(zhí)行過程,圖 8 給出了基于 mapreduce 的有運(yùn)算,取相同 id 中最小的距離,修改標(biāo)志位,并加上鄰接點(diǎn)信息,向圖 g 的第一次迭代過程。具體如圖 6 所示。對(duì)于圖 1 中的有向圖 g 的頂點(diǎn) v2,其 reduce 的輸入值為、,經(jīng)過 reduce

13、過程處理后,其輸出結(jié)hadoop 是由雅虎資助的開源項(xiàng)目, 是一個(gè)類似于 google 果為,詳細(xì)過程可參見圖 3?！霸朴?jì)算”的技術(shù)平臺(tái),專注于海量數(shù)據(jù)存儲(chǔ)、處理的分布式系 reduce 算法過程如圖 7 所示:統(tǒng),同時(shí)提供了基于 java 的 mapreduce 框架,能夠?qū)⒎植际綉?yīng)網(wǎng) 絡(luò) 與 通 信微計(jì)算機(jī)信息2011 年第 27 卷第 12 期- 98 -120 元 / 年 郵局訂閱號(hào)：82-946現(xiàn)場(chǎng)總線技術(shù)應(yīng)用 200 例用部署到大型廉價(jià)集群上。hadoop 能夠?qū)崿F(xiàn)高效計(jì)算,存儲(chǔ)的核心在于其可運(yùn)行于大規(guī)模集群上的分布式文件系統(tǒng) hdfs (hadoop distributed fi

14、le system)以及 mapreduce 分布式并行編程框架。文中的實(shí)驗(yàn)采用的是 hadoop 完全分布式集群環(huán)境,整個(gè)基 于 mapreduce 的單源最短路徑算法的程序編寫由 java 語言來 實(shí)現(xiàn)。采用 8 臺(tái)實(shí)體機(jī)進(jìn)行完全分布式集群的搭建,每個(gè)節(jié)點(diǎn)的 運(yùn)行環(huán)境如下:windowsxp、jdk、cygwin 和 hadoop。且每臺(tái)機(jī)器 的配置為:intel (r) pentium (r) 4 cpu 3.0ghz、1 gb ram 及80gb 可用硬盤空間。其中一臺(tái)機(jī)器作 jobtracker,namenode 為 master,其余機(jī)器皆作 datanode,tasktracke

15、r 為 slave。對(duì)上述算法 描述的圖 1 的每次迭代結(jié)果片段數(shù)據(jù)如表 1 所示:實(shí)驗(yàn)中, 根據(jù)所給數(shù)據(jù)量較小的情況下, 采用多節(jié)點(diǎn)的hadoop 計(jì)算速度明顯不如采用 hadoop 單節(jié)點(diǎn)的速度快, 也比 hadoop 并行技術(shù)的方式慢很多。因此,對(duì)于小規(guī)模的運(yùn)算,不適 宜采用 hadoop。為了能進(jìn)一步地比較實(shí)驗(yàn)結(jié)果, 在實(shí)驗(yàn)中分別測(cè)試了圖的 頂點(diǎn)個(gè)數(shù)為 10000 和 90000 來做了測(cè)試, 表 2 給出了不同節(jié)點(diǎn)數(shù)下基于 mapreduce 的單源最短路徑算法的并行加速比的測(cè) 試與比較,且在圖 9 中作出了曲線比較。圖 9 加速比測(cè)試比較由圖 9 中的數(shù)據(jù)可以看出, 在數(shù)據(jù)規(guī)模即頂

16、點(diǎn)數(shù) n 相同的 情況下,并不是橫軸上集群中節(jié)點(diǎn)數(shù)目越多,縱軸上的加速比就會(huì)增加,而是有一個(gè)峰值,達(dá)到一定的峰值后,加速比反而會(huì)下 降。我們分析原因是由于 map 數(shù)和 reduce 數(shù)的增加會(huì)導(dǎo)致節(jié) 點(diǎn)間通信量和同步的增加,另外,局域網(wǎng)內(nèi)部的網(wǎng)絡(luò)吞吐量也會(huì) 導(dǎo)致并行性能的下降。因此,在實(shí)際的應(yīng)用過程中,應(yīng)該采用恰 當(dāng)數(shù)目的節(jié)點(diǎn)機(jī),選擇合適的 map 和 reduce 數(shù)目,以避免資源的浪費(fèi)。表 1 有向圖 1 的每一次迭代結(jié)果表 2 并行加速比測(cè)試數(shù)據(jù)從實(shí)驗(yàn)的過程中,基于 mapreduce 的單源最短路徑算法模 型的使用較方便,對(duì)于大型的計(jì)算需求也可以較輕松地完成。事 實(shí)上,也可從實(shí)驗(yàn)中推

17、導(dǎo)出,通過 hadoop,應(yīng)用程序也可以在超 大型集群上運(yùn)行,也就是說系統(tǒng)的易擴(kuò)展性較高。結(jié)語4文中實(shí)現(xiàn)了一種基于 mapreduce 的單源最短路徑算法。研究表明,在云計(jì)算環(huán)境中,文中算法可以有效地找出整個(gè)圖結(jié)構(gòu) 中的單源最短路徑。同時(shí)本算法也存在著一定的缺點(diǎn):在某種極 端的情況下, 其所花費(fèi)的時(shí)間可能會(huì)與 dijkstra 算法差不多,這是因?yàn)樗惴〞?huì)導(dǎo)致浪費(fèi)一定的擴(kuò)展路徑。 盡管如此,基于mapreduce 的應(yīng)用正被越來越多人所關(guān)注和使用,隨著 mapreduce 的不斷發(fā)展,它將會(huì)得到更多人的關(guān)注與應(yīng)用。在今后的 研究工作中,我們將進(jìn)一步研究基于 mapreduce 的單源最短路 徑算

18、法的應(yīng)用,將側(cè)重于以邊為中心去處理圖結(jié)構(gòu)的遍歷。本文作者創(chuàng)新點(diǎn):在基于 mapreduce 的單源最短路徑算法 的研究與應(yīng)用之上,對(duì)其進(jìn)行理論分析,并對(duì)其加速比進(jìn)行了研究,且驗(yàn)證了其性能的優(yōu)越性。作者對(duì)本文版權(quán)全權(quán)負(fù)責(zé),無抄襲。參考文獻(xiàn)1dean j, ghemawat s.mapreduce:simplified data processing on large clusters c/proc. of the 6th symposium on operating sys tems design and implementation. san francisco,usa:s.n.,2004.2

19、cutting d.scalable computing with mapreducec /proc. of oreilly open source convention. poland:s.n., 2005.3tan g z, ping x h. a parallel algorithm for computing shortest paths in large-scale networks c/proc. of the 5th international conference on computational science. atlanta,ga,usa: s.n.,2005.4tan

20、g z, li d, ping x h, et al.network-tree routing model for large scale networks:theories and algorithms/proc. of the 4th international conference on networking.reunion island,france: s. n.,2005.5陳國(guó)良. 并行算法的設(shè)計(jì)與分析m. 北京: 高等教育出版社,2002.6dean j. experiences with mapreduce,an abstraction for large - scale co

21、mputation c /proc. of pact06. washington d.c.,usa: s.n.,2006.7yang h c, dasdan a, hsiao r l,et al.map -reduce -merge:simplified relational data processing on large clusters c /proc. of2007 acm sigmod conference,2007.8cohen j. graph twiddling in a mapreduce worldj. computing in science & engineering,

22、2009,11(4):29-41.9borthakur d. the hadoop distributed file system:architecture and designeb/ol. /common/docs/r0.18.0/ hdfs_design.pdf, 2007.10楊代慶,張智雄.基于 hadoop 的海量共現(xiàn)矩陣生成方法j.現(xiàn)代圖書情報(bào)技術(shù),2009(4):23-26.作者簡(jiǎn)介:楊玲(1984-),女,碩士研究生,主要研究領(lǐng)域?yàn)樵朴?jì)算;李仁發(fā)(1956-),男,教授,主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)、云計(jì)算;唐 卓(1981-),男,博

23、士,主要研究領(lǐng)域?yàn)樵朴?jì)算。(下轉(zhuǎn)第 101 頁(yè))郵局訂閱號(hào)：82-946 120 元 / 年 - 99 -plc 技術(shù)應(yīng)用 200 例2 rudp 的應(yīng)用2.1 .通信中間件 中間件是一種獨(dú)立的系統(tǒng)軟件或服務(wù)程序, 分布式應(yīng)用軟件借助這種軟件在不同的技術(shù)之間共享資源。中間件位于客戶機(jī)/ 服務(wù)器的操作系統(tǒng)之上,管理計(jì)算機(jī)資源和網(wǎng)絡(luò)通訊。是連 接兩個(gè)獨(dú)立應(yīng)用程序或獨(dú)立系統(tǒng)的軟件。相連接的系統(tǒng),即使它 們具有不同的接口,但通過中間件相互之間仍能交換信息。執(zhí)行 中間件的一個(gè)關(guān)鍵途徑是信息傳遞。通過中間件,應(yīng)用程序可以 工作于多平臺(tái)或 os 環(huán)境。而通信中間件就是管理網(wǎng)絡(luò)通信的 消息通訊平臺(tái)。2.2.

24、基于消息的 msgmidware 體系msgmidware 體系是指基于 udp 協(xié)議, 采用 c/s 與分布式 結(jié)構(gòu)相結(jié)合的方式, 即將通訊模塊分成通信管理服務(wù)器模塊和 通信客戶模塊兩類模塊, 而通信管理服務(wù)器之間作為對(duì)等的通 信實(shí)體,為各客戶模塊提供一定程度的分布式處理功能,實(shí)現(xiàn)在同一臺(tái)機(jī)器內(nèi)模塊間采用 ipc 及共享內(nèi)存通信, 而在不同機(jī)器 間采用 udp 的連接的通信。如圖 2 所示。圖 22.3. msgmidware 的工作原理msgmidware 的工作原理上由通信管理服務(wù)和通信客戶模 塊兩部分組成, 通信管理器主要目的是管理通信客戶模塊和實(shí)現(xiàn)本機(jī)通信客戶模塊間的消息通信。結(jié)合這

25、種工作原理 msgmidware 的通信層次結(jié)構(gòu)圖如圖 3 所示。圖 3通信客戶端模塊(應(yīng)用層):采用消息驅(qū)動(dòng)機(jī)制,用戶看到的 是自行定義的消息內(nèi)容。通信管理層:相對(duì)通信客戶模塊是透明的。通過 rudp 協(xié)議 實(shí)現(xiàn)消息的高效可靠傳輸機(jī)制,管理通信客戶模塊,將包在通信客戶模塊間傳遞,溝通不同的進(jìn)程。udp 層:實(shí)現(xiàn)數(shù)據(jù)的傳遞,溝通不同的機(jī)器和操作系統(tǒng),為 不同機(jī)器上的模塊之間通信的透明管道。之前介紹了 msgmidware 的體系, 它是一種消息通信中間 件, 每一個(gè)通信客戶模塊都維護(hù)一個(gè)接收消息隊(duì)列和一個(gè)發(fā)送消息隊(duì)列,自動(dòng)具備與通信服務(wù)器端的交互能力,每個(gè)通信客戶模塊在啟動(dòng)時(shí)向通信服務(wù)器注冊(cè)本

26、模塊,在退出是注銷本模塊。下圖 4 是通信客戶模塊在通信時(shí)的消息傳送圖。圖 4網(wǎng) 絡(luò) 與 通 信結(jié)論3以往的通信中間件很多都是基于 tcp 的, 通過改進(jìn)基于udp 的協(xié)議融入到中間件技術(shù),形成一種高性能、安全、可靠的 消息傳輸系統(tǒng),很好地支持 c/s 模式和分布式系統(tǒng)的開發(fā)、集成 和運(yùn)行, 為跨越不同操作系統(tǒng)和網(wǎng)絡(luò)平臺(tái)的多層結(jié)構(gòu)應(yīng)用系統(tǒng)的開發(fā)、部署及運(yùn)行,提供了靈活易用的消息通訊平臺(tái)基礎(chǔ)。本文作者創(chuàng)新點(diǎn):改進(jìn)基于 udp 的協(xié)議應(yīng)用到通信中間件 當(dāng)中。作者對(duì)本文版權(quán)全權(quán)負(fù)責(zé),無抄襲。參考文獻(xiàn)1gu yunhong,hong xinwei,grosman r.experiences in de

27、sign and implementation of a high performance transport protocol c/ proceedings of the acm/ieee sc2004 conference,2004.2bova t, krivoruchka t. reliable udp protocal draft -ietf -sigtranreliable-udp-00.txt. cisco systems, 1999-02 3黃遠(yuǎn)峰,宗平.基于 udp 的滑動(dòng)窗口協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)j.南 京郵電大學(xué)學(xué)報(bào),2007,27(4):80-84. 4譚寧,常毅等.一種網(wǎng)絡(luò)擁塞控制體系的設(shè)計(jì)j.微計(jì)算機(jī)信息.2007,4-3:p142-1435王海軍, 劉彩霞, 程?hào)|年.一種基于 udp 的可靠傳輸協(xié)議分析 與研究j.計(jì)算機(jī)應(yīng)用研究.2005,11(3) :181-183作者簡(jiǎn) 介:張良春(1986-),男(漢族),湖南省長(zhǎng)沙市人,長(zhǎng)沙理工 大學(xué),碩士,2008 年在長(zhǎng)沙理工大學(xué)研修,主要從事計(jì)算機(jī)通信研究。biography: zhan