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

1.2 相關(guān)數(shù)據(jù)結(jié)構(gòu)定義為了減少數(shù)據(jù)冗余, 本文對于圖的表示方法采用鄰接表的 方式進(jìn)行存儲,以各頂點(diǎn)為中心,每一行代表圖中的一個頂點(diǎn),各頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)描述如下:其中,id 為頂點(diǎn)標(biāo)識;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 用鄰接表表示圖 1 的數(shù)據(jù)結(jié)構(gòu)圖 3 基于 mapreduce 的單源最短路徑算法的執(zhí)行過程文章編號: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摘要: 通 過 對 mapreduce 模型執(zhí)行過程的分析 ,針 對 單 源最短路徑算法難以隨著云計算的產(chǎn)生和發(fā)展而應(yīng)用及提高搜索效 率 的 問 題, 本文設(shè)計和實(shí)現(xiàn)了一種基于 mapreduce 架構(gòu)的并行單源最短路徑算法 。 并 基 于 hadoop 平臺集群環(huán)境進(jìn)行了研究 與 實(shí) 驗(yàn), 結(jié) 果 表 明, 文中算法可以有效地找出整個圖結(jié)構(gòu)中的單源最短路徑 , 且驗(yàn)證了算法性能的優(yōu)越性 。關(guān)鍵詞: mapreduce; 并行; 最短路徑; hadoop中圖分類號: tp393.0文獻(xiàn)標(biāo)識碼: aabstract: via the analysis to implementation process of mapreduce, aimming at the problem that single source shortest path algorithmis 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 experimental 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ī)網(wǎng)絡(luò)的飛速發(fā)展促進(jìn)了云計算的產(chǎn)生。mapreduce 并行編程模型是云計算的核心技術(shù)之一,2005 年 4 月 6 日, google 實(shí) 驗(yàn) 室 的 jeffrey dean 和 sanjay ghemawat 提 出 了 mapreduce 模型并進(jìn)行了詳細(xì)地闡述, 它為并行系統(tǒng)的數(shù)據(jù)處 理提供了一個簡單、優(yōu)雅的解決方案。apache 基金會基于 java 開發(fā)了一個分布式基礎(chǔ)架構(gòu) hadoop, 實(shí)現(xiàn)了 mapreduce 模型, 并提供了分布式計算平臺。在通信網(wǎng)絡(luò)與交通網(wǎng)絡(luò)中, 并行問題和最短路徑問題一直 是研究的熱點(diǎn), 有著極其重要的作用。在處理實(shí)際問題的過程 中, 通常將現(xiàn)實(shí)問題轉(zhuǎn)化為圖的網(wǎng)狀形式來研究最短路徑。而 mapreduce 并行計算模型的出現(xiàn), 為解決大規(guī)模數(shù)據(jù)處理問題 提供了一種新的途徑, 也為最短路徑的并行計算帶來了一種新 的解決方法,有效提高了計算效率。本文提出了基于 mapreduce 的單源最短路徑算法。首先利 用 mapreduce 架構(gòu)來形成算法的并行化思想,分析并設(shè)計了算法的過程,然后通過 hadoop 平臺來實(shí)現(xiàn)算法,最后對實(shí)驗(yàn)結(jié)果 進(jìn)行了分析。算法及其數(shù)據(jù)結(jié)構(gòu)的定義11.1 單源最短路徑算法單源最短路徑是指給定一個帶權(quán)有向圖 g=(v,e,w),其中 v 為頂點(diǎn)集,e 為有向邊集,w 為權(quán)集且每條邊的權(quán)是一個非負(fù)實(shí) 數(shù)。另外,還給定 v 中的一個頂點(diǎn),稱為源,計算從源到所有其他 各頂點(diǎn)的最短路徑長度。這里的長度是指各邊權(quán)之和,根據(jù)不同 的實(shí)際情況,邊上權(quán)值的長度可以表示成時間、距離、成本、損失、損耗或其它任何沿一條路徑的相加累積量,且為最小值。楊 玲: 碩士研究生郵局訂閱號：82-946 120 元 / 年 - 97 -plc 技術(shù)應(yīng)用 200 例2 基 于 mapreduce 的 單 源 最 短 路 徑算法的設(shè)計與實(shí)現(xiàn)mapreduce 用戶用兩個函數(shù)表達(dá)這個計算:map 和 reduce。 在 mapredcue 模型中,用戶指定一個 map 函數(shù)來處理一個輸入 的 key/value 對,產(chǎn)生中間結(jié)果 key/value 對集,再通過 reduce 函 數(shù)來處理中間結(jié)果中具有相同 key 值的 value?；?mapreduce 的單源最短路徑算法的執(zhí)行過程如圖 3所示。(1)輸入數(shù)據(jù)的切分:mapreduce 對輸入文件按行(每行代表 圖中的一個頂點(diǎn)) 進(jìn)行自動切分, 并將數(shù)據(jù)分發(fā)到每個 map 任務(wù), 其中 key 值為 id,value 值為 distance、flag 和 adjacent infor圖 5 map 算法過程mation;(2)map 任務(wù)的執(zhí)行:接收 key/value 對,當(dāng) value 中的 flag 的 值為 1 時,則處理當(dāng)前頂點(diǎn),主要處理當(dāng)前頂點(diǎn)的鄰接點(diǎn),并將其鄰接點(diǎn)的 flag 也置為 1,最后產(chǎn)生臨時的 key/value 對集;圖 6 reduce 過程的輸入和輸出(3)臨時結(jié)果的分組:mapreduce 框架對 map 執(zhí)行過程輸出 的臨時結(jié)果進(jìn)行分組, 將相同的 key 值即 id 號合并成同一組,并將其分發(fā)給空閑的 reduce;(4)reduce 任務(wù)的執(zhí)行:接收 key/value 對,對相同 id 的 value進(jìn)行合并,找到當(dāng)前的最短路徑;(5)mapreduce 的迭代:如圖 3 所示,每次 reduce 后的結(jié)果 又分發(fā)給下一輪的 map 過程,通過多次迭代尋找到最終的最短 路徑。當(dāng)沒有發(fā)現(xiàn)更好的距離時,節(jié)點(diǎn)間的遍歷會停止,本文中是以 flag 位來判斷的, 即當(dāng) reduce 中所有記錄的 flag 位都不為1 時,則停止迭代,算法結(jié)束。2.1 map 過程map 函數(shù)對整個圖的結(jié)構(gòu)進(jìn)行遍歷,采用 bfs 算法(即廣度優(yōu)先算法)思路,按層依次遍歷整個圖。map 函數(shù)根據(jù)所接到的圖 7 reduce 算法過程key/value 對(即每個頂點(diǎn)的相關(guān)信息)來產(chǎn)生相關(guān)的輸出。輸出 主要分兩種,一種是本身結(jié)點(diǎn)的信息,在處理完后,僅對信息的標(biāo)志位進(jìn)行更改;一種是對本結(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ì)過程可參見圖 3。業(yè)的 reduce 輸出作為下一個 mapreduce 作業(yè)的 map 輸入,這map 算法過程如圖 5 所示。樣就形成了整個工作鏈。當(dāng)某個作業(yè)的輸出中所有的節(jié)點(diǎn)都沒2.2 reduce 過程有標(biāo)志位為 1 的節(jié)點(diǎn)時,則停止迭代,算法終結(jié)。具體可參見圖 3reduce 過程對從各個 map 對各頂點(diǎn)的處理結(jié)果進(jìn)行聚集中所示的整個算法執(zhí)行過程,圖 8 給出了基于 mapreduce 的有運(yùn)算,取相同 id 中最小的距離,修改標(biāo)志位,并加上鄰接點(diǎn)信息,向圖 g 的第一次迭代過程。具體如圖 6 所示。對于圖 1 中的有向圖 g 的頂點(diǎn) v2,其 reduce 的輸入值為、,經(jīng)過 reduce 過程處理后,其輸出結(jié)hadoop 是由雅虎資助的開源項(xiàng)目, 是一個類似于 google 果為,詳細(xì)過程可參見圖 3?！霸朴嬎恪钡募夹g(shù)平臺,專注于海量數(shù)據(jù)存儲、處理的分布式系 reduce 算法過程如圖 7 所示:統(tǒng),同時提供了基于 java 的 mapreduce 框架,能夠?qū)⒎植际綉?yīng)網(wǎng) 絡(luò) 與 通 信微計算機(jī)信息2011 年第 27 卷第 12 期- 98 -120 元 / 年 郵局訂閱號：82-946現(xiàn)場總線技術(shù)應(yīng)用 200 例用部署到大型廉價集群上。hadoop 能夠?qū)崿F(xiàn)高效計算,存儲的核心在于其可運(yùn)行于大規(guī)模集群上的分布式文件系統(tǒng) hdfs (hadoop distributed file system)以及 mapreduce 分布式并行編程框架。文中的實(shí)驗(yàn)采用的是 hadoop 完全分布式集群環(huán)境,整個基 于 mapreduce 的單源最短路徑算法的程序編寫由 java 語言來 實(shí)現(xiàn)。采用 8 臺實(shí)體機(jī)進(jìn)行完全分布式集群的搭建,每個節(jié)點(diǎn)的 運(yùn)行環(huán)境如下:windowsxp、jdk、cygwin 和 hadoop。且每臺機(jī)器 的配置為:intel (r) pentium (r) 4 cpu 3.0ghz、1 gb ram 及80gb 可用硬盤空間。其中一臺機(jī)器作 jobtracker,namenode 為 master,其余機(jī)器皆作 datanode,tasktracker 為 slave。對上述算法 描述的圖 1 的每次迭代結(jié)果片段數(shù)據(jù)如表 1 所示:實(shí)驗(yàn)中, 根據(jù)所給數(shù)據(jù)量較小的情況下, 采用多節(jié)點(diǎn)的hadoop 計算速度明顯不如采用 hadoop 單節(jié)點(diǎn)的速度快, 也比 hadoop 并行技術(shù)的方式慢很多。因此,對于小規(guī)模的運(yùn)算,不適 宜采用 hadoop。為了能進(jìn)一步地比較實(shí)驗(yàn)結(jié)果, 在實(shí)驗(yàn)中分別測試了圖的 頂點(diǎn)個數(shù)為 10000 和 90000 來做了測試, 表 2 給出了不同節(jié)點(diǎn)數(shù)下基于 mapreduce 的單源最短路徑算法的并行加速比的測 試與比較,且在圖 9 中作出了曲線比較。圖 9 加速比測試比較由圖 9 中的數(shù)據(jù)可以看出, 在數(shù)據(jù)規(guī)模即頂點(diǎn)數(shù) n 相同的 情況下,并不是橫軸上集群中節(jié)點(diǎn)數(shù)目越多,縱軸上的加速比就會增加,而是有一個峰值,達(dá)到一定的峰值后,加速比反而會下 降。我們分析原因是由于 map 數(shù)和 reduce 數(shù)的增加會導(dǎo)致節(jié) 點(diǎn)間通信量和同步的增加,另外,局域網(wǎng)內(nèi)部的網(wǎng)絡(luò)吞吐量也會 導(dǎo)致并行性能的下降。因此,在實(shí)際的應(yīng)用過程中,應(yīng)該采用恰 當(dāng)數(shù)目的節(jié)點(diǎn)機(jī),選擇合適的 map 和 reduce 數(shù)目,以避免資源的浪費(fèi)。表 1 有向圖 1 的每一次迭代結(jié)果表 2 并行加速比測試數(shù)據(jù)從實(shí)驗(yàn)的過程中,基于 mapreduce 的單源最短路徑算法模 型的使用較方便,對于大型的計算需求也可以較輕松地完成。事 實(shí)上,也可從實(shí)驗(yàn)中推導(dǎo)出,通過 hadoop,應(yīng)用程序也可以在超 大型集群上運(yùn)行,也就是說系統(tǒng)的易擴(kuò)展性較高。結(jié)語4文中實(shí)現(xiàn)了一種基于 mapreduce 的單源最短路徑算法。研究表明,在云計算環(huán)境中,文中算法可以有效地找出整個圖結(jié)構(gòu) 中的單源最短路徑。同時本算法也存在著一定的缺點(diǎn):在某種極 端的情況下, 其所花費(fèi)的時間可能會與 dijkstra 算法差不多,這是因?yàn)樗惴〞?dǎo)致浪費(fèi)一定的擴(kuò)展路徑。 盡管如此,基于mapreduce 的應(yīng)用正被越來越多人所關(guān)注和使用,隨著 mapreduce 的不斷發(fā)展,它將會得到更多人的關(guān)注與應(yīng)用。在今后的 研究工作中,我們將進(jìn)一步研究基于 mapreduce 的單源最短路 徑算法的應(yīng)用,將側(cè)重于以邊為中心去處理圖結(jié)構(gòu)的遍歷。本文作者創(chuàng)新點(diǎn):在基于 mapreduce 的單源最短路徑算法 的研究與應(yīng)用之上,對其進(jìn)行理論分析,并對其加速比進(jìn)行了研究,且驗(yàn)證了其性能的優(yōu)越性。作者對本文版權(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.2cutting 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 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陳國良. 并行算法的設(shè)計與分析m. 北京: 高等教育出版社,2002.6dean j. experiences with mapreduce,an abstraction for large - scale computation 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,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)代圖書情報技術(shù),2009(4):23-26.作者簡介:楊玲(1984-),女,碩士研究生,主要研究領(lǐng)域?yàn)樵朴嬎?李仁發(fā)(1956-),男,教授,主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)、云計算;唐 卓(1981-),男,博士,主要研究領(lǐng)域?yàn)樵朴嬎恪?下轉(zhuǎn)第 101 頁)郵局訂閱號：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ī)資源和網(wǎng)絡(luò)通訊。是連 接兩個獨(dú)立應(yīng)用程序或獨(dú)立系統(tǒng)的軟件。相連接的系統(tǒng),即使它 們具有不同的接口,但通過中間件相互之間仍能交換信息。執(zhí)行 中間件的一個關(guān)鍵途徑是信息傳遞。通過中間件,應(yīng)用程序可以 工作于多平臺或 os 環(huán)境。而通信中間件就是管理網(wǎng)絡(luò)通信的 消息通訊平臺。2.2. 基于消息的 msgmidware 體系msgmidware 體系是指基于 udp 協(xié)議, 采用 c/s 與分布式 結(jié)構(gòu)相結(jié)合的方式, 即將通訊模塊分成通信管理服務(wù)器模塊和 通信客戶模塊兩類模塊, 而通信管理服務(wù)器之間作為對等的通 信實(shí)體,為各客戶模塊提供一定程度的分布式處理功能,實(shí)現(xiàn)在同一臺機(jī)器內(nèi)模塊間采用 ipc 及共享內(nèi)存通信, 而在不同機(jī)器 間采用 udp 的連接的通信。如圖 2 所示。圖 22.3. msgmidware 的工作原理msgmidware 的工作原理上由通信管理服務(wù)和通信客戶模 塊兩部分組成, 通信管理器主要目的是管理通信客戶模塊和實(shí)現(xiàn)本機(jī)通信客戶模塊間的消息通信。結(jié)合這種工作原理 msgmidware 的通信層次結(jié)構(gòu)圖如圖 3 所示。圖 3通信客戶端模塊(應(yīng)用層):采用消息驅(qū)動機(jī)制,用戶看到的 是自行定義的消息內(nèi)容。通信管理層:相對通信客戶模塊是透明的。通過 rudp 協(xié)議 實(shí)現(xiàn)消息的高效可靠傳輸機(jī)制,管理通信客戶模塊,將包在通信客戶模塊間傳遞,溝通不同的進(jìn)程。udp 層:實(shí)現(xiàn)數(shù)據(jù)的傳遞,溝通不同的機(jī)器和操作系統(tǒng),為 不同機(jī)器上的模塊之間通信的透明管道。之前介紹了 msgmidware 的體系, 它是一種消息通信中間 件, 每一個通信客戶模塊都維護(hù)一個接收消息隊(duì)列和一個發(fā)送消息隊(duì)列,自動具備與通信服務(wù)器端的交互能力,每個通信客戶模塊在啟動時向通信服務(wù)器注冊本模塊,在退出是注銷本模塊。下圖 4 是通信客戶模塊在通信時的消息傳送圖。圖 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ò)平臺的多層結(jié)構(gòu)應(yīng)用系統(tǒng)的開發(fā)、部署及運(yùn)行,提供了靈活易用的消息通訊平臺基礎(chǔ)。本文作者創(chuàng)新點(diǎn):改進(jìn)基于 udp 的協(xié)議應(yīng)用到通信中間件 當(dāng)中。作者對本文版權(quán)全權(quán)負(fù)責(zé),無抄襲。參考文獻(xiàn)1gu yunhong,hong xinwei,grosman r.experiences in design 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 的滑動窗口協(xié)議的設(shè)計與實(shí)現(xiàn)j.南 京郵電大學(xué)學(xué)報,2007,27(4):80-84. 4譚寧,常毅等.一種網(wǎng)絡(luò)擁塞控制體系的設(shè)計j.微計算機(jī)信息.2007,4-3:p142-1435王海軍, 劉彩霞, 程東年.一種基于 udp 的可靠傳輸協(xié)議分析 與研究j.計算機(jī)應(yīng)用研究.2005,11(3) :181-183作者簡 介:張良春(1986-),男(漢族),湖南省長沙市人,長沙理工 大學(xué),碩士,2008 年在長沙理工大學(xué)研修,主要從事計算機(jī)通信研究。biography: zhan