Spark-GraphX框架下的大規(guī)模加權(quán)圖最短路徑查詢

宋寶燕，張永普，單曉歡

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽 110036)

Spark-GraphX框架下的大規(guī)模加權(quán)圖最短路徑查詢

宋寶燕，張永普，單曉歡*

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽 110036)

最短路徑問題一直是計算機等學(xué)科的熱點研究問題，常應(yīng)用于社交網(wǎng)、交通網(wǎng)等諸多領(lǐng)域.圖規(guī)模爆炸式的增長導(dǎo)致傳統(tǒng)單機環(huán)境下的存儲、查詢已無法滿足大規(guī)模圖的處理需求.提出一種基于Spark-GraphX平臺的大規(guī)模圖最短路徑查詢方法(LSGSP-SG)：首先利用經(jīng)典算法對大規(guī)模圖進行分割并標記，將割點的信息記錄在文本文件中，然后利用大數(shù)據(jù)平臺Spark的GraphX框架進行迭代式分布計算并進行各個計算機節(jié)點的消息通信及同步，最后返回最短路徑查詢結(jié)果.

Spark；圖分割；最短路徑；分布式

0 引言

圖可以反應(yīng)現(xiàn)實世界實體間的復(fù)雜關(guān)系，圖中節(jié)點表示實體對象，實體間的聯(lián)系則通過邊表示[1].現(xiàn)實應(yīng)用中的設(shè)備更新問題、工程問題、路線推薦等均可轉(zhuǎn)換為最短路徑查詢問題求解.圖規(guī)模較小時，判斷過程簡單，因此經(jīng)典最短路徑查詢方法均采用單機存儲計算模式，然而隨著信息技術(shù)的發(fā)展，實體間聯(lián)系越來越復(fù)雜，導(dǎo)致圖規(guī)模迅速膨脹，經(jīng)典方法已無法適應(yīng)大規(guī)模圖[1]的處理需求，分布式并行技術(shù)因可良好地滿足大數(shù)據(jù)處理而被廣泛應(yīng)用，因此研究適合大規(guī)模圖數(shù)據(jù)的并行計算算法成為新的研究熱點.

Spark是一種與 Hadoop 相似的分布式并行計算平臺，兩者之間的不同在于其啟用了內(nèi)存分布式數(shù)據(jù)集，除了能夠提供交互式查詢外，還可以優(yōu)化迭代工作負載.GraphX是Spark的子框架，是Spark處理圖的有力工具，采用GAS模型，利用Spark提供的內(nèi)存緩存RDD，實現(xiàn)高效的圖計算.本文提出一種基于Spark-GraphX的最短路徑算法，首先利用已有分割算法將大規(guī)模圖進行分割存儲，然后將割點的信息記錄在文本文件中，最后利用大數(shù)據(jù)平臺Spark的GraphX框架進行迭代式分布計算并進行各個計算機節(jié)點的消息通信及同步，最后返回最短路徑查詢結(jié)果.

1 相關(guān)工作

1.1 最短路徑查詢算法

最短路經(jīng)典算法包括Dijkstra算法[2]、 Floyd算法[3]及Bellman-Ford算法[4]等.Dijkstra算法是求一個頂點到其余各頂點的最短路徑，F(xiàn)loyd算法是一種利用動態(tài)規(guī)劃的思想尋找加權(quán)圖中多源點之間最短路徑的算法，Bellman-ford算法是求含負權(quán)圖的單源最短路徑算法.上述算法應(yīng)用于大規(guī)模圖時，常因存儲開銷大、查詢效率低等原因無法滿足現(xiàn)有的查詢需求.

1.2 圖分割及Spark-GraphX

●圖分割

由于圖規(guī)模龐大，單節(jié)點無法存儲完整數(shù)據(jù)圖，因此考慮將圖進行分割并分別存儲于不同的計算機節(jié)點上.高效的圖分割算法是提高大規(guī)模圖計算的有效手段，大規(guī)模圖有兩種分割策略：一種是邊分割策略，即將邊打破，分別存儲到兩個計算機節(jié)點上，如圖1所示；另外一種則是點分割策略，即將頂點復(fù)制存儲到不同的計算節(jié)點上，如圖2所示.兩種策略各有優(yōu)劣，目前點分割策略被廣泛應(yīng)用.Guerrieri等人提出了基于點分割的D-fep算法[5]，該算法大大減少了跨機器通信開銷，進一步表明了點分割的優(yōu)勢.

圖1 邊分割策略

圖2 點分割策略

●Spark-GraphX

GraphX是Spark的子框架，是Spark處理圖的有力工具.GraphX框架參考并優(yōu)化了分布式圖計算框架Pregel，采用GAS模型，利用Spark提供的內(nèi)存緩存RDD，實現(xiàn)高效的圖計算.

GraphX的核心抽象是Resilient Distributed Property Graph，一種點和邊都帶屬性的有向多重圖.它擴展了Spark RDD的抽象，有Table和Graph兩種視圖，只需要一份物理存儲.兩種視圖都有自己獨有的操作符，從而獲得了靈活操作和執(zhí)行效率[6].GraphX的代碼結(jié)構(gòu)整體如圖3所示，其底層設(shè)計有以下幾個關(guān)鍵點.

1)GraphX對圖的所有操作最終都會轉(zhuǎn)換成一系列的RDD操作來完成.

2)物理數(shù)據(jù)由RDD[Vertex-Partition]和RDD[EdgePartition]這兩個RDD組成.點和邊實際都是存儲在帶索引結(jié)構(gòu)的分片數(shù)據(jù)塊中，不變的索引結(jié)構(gòu)在RDD轉(zhuǎn)換過程中是共用的，降低了計算和存儲開銷.

3)圖的分布式存儲采用點分割模式，而且使用partitionBy方法，由用戶指定不同的劃分策略(PartitionStrategy).劃分策略會將邊分配到各個EdgePartition，頂點Master分配到各個VertexPartition，EdgePartition也會緩存本地邊關(guān)聯(lián)點的Ghost副本.

圖3 GraphX的代碼結(jié)構(gòu)

但是Spark自帶的最短路徑算法不支持自定義權(quán)重，顯然這是不符合現(xiàn)實生活的，比如在地圖中，可以根據(jù)最短路徑為用戶推薦線路，此時則需要利用權(quán)重信息.因此本文對該算法進行優(yōu)化，自定義加權(quán)DAG圖來計算源點到目的點的最短路徑.

2 大規(guī)模圖最短路徑查詢方法

2.1 大規(guī)模圖分割

本文首先利用D-fep算法進行圖分割，該算法采用點分割策略，對某些與其他點聯(lián)系較少的點進行分割，復(fù)制到不同的計算機節(jié)點進行存儲，以保證負載均衡.同時，為滿足后文的計算需求，本文將記錄分割信息和存儲節(jié)點序號.為避免混淆，本文將圖中的點稱之為頂點，將集群中其他計算機稱之為節(jié)點.分割之前如圖4所示.

圖4 DAG圖分割前

分割后的頂點和邊分別存儲在不同的計算機節(jié)點上，例如對于頂點20，master節(jié)點記錄分割信息和存儲信息{20，<1,2>}，表示該點為割點，分別存儲在節(jié)點1和節(jié)點2上，如圖5所示.對于頂點8，存儲信息為{8，<1>}，表示該點為非分割點，儲存在節(jié)點1上.

圖5 分割后子圖

2.2 基于Spark-Graphx的最短路徑查詢方法

本文提出的LSGSP-SG算法是將大規(guī)模圖利用已有的分割算法進行分割，并利用本文給出的標記方法進行標記.當查詢到達時，通過分析兩點之間的信息判斷是否在同一存儲節(jié)點上，分別給出類集中式方法和分布式方法.在介紹算法之前，我們先來介紹幾個概念：

頂點Vertex(Id,Property(V))，每個頂點由一個64位數(shù)字標識，其中Id表示頂點編號，Property則表示該頂點的屬性，本文中存放該點到源點的距離和頂點所在節(jié)點序號.

邊Edge(SrcId,DstId,Property(E))，其中SrcId代表源頂點Id，DstId代表目的頂點Id，Property代表邊的權(quán)值.

三元組Triplet({SrcId,Property(V)},{DstId,Property(V)},{Property(E)})詳細記錄源點和目的點以及二者的權(quán)值.

●類集中式方法

若查詢?yōu)?->4的最短路徑，首先通過查詢文件信息，根據(jù)點所在節(jié)點序號第一位是否相同判斷兩點是否屬于同一節(jié)點，若是，則采用類集中式方法查詢，具體步驟如下：

1) 首先設(shè)置源點屬性值為0，其他點的屬性為無窮大并初始化一個空隊列；

2) 對源點的鄰接點進行遍歷，若該點不在隊列中，則判斷源點的屬性值與到該點的邊權(quán)值之和是否小于該鄰接點的屬性值，若是且無下一個鄰接點，則修改該點的屬性值為源點的屬性值與到該點的邊權(quán)值之和，否則繼續(xù)判斷下一個鄰接點，將屬性值小的點入隊列，并記錄該路徑；

3) 將該點作為新的源點，迭代循環(huán)(2)；

4) 將每個點的Id作為key，該點到源點的距離作為value進行結(jié)果合并，得到該點到初始源點的最短路徑.

●分布式方法

master節(jié)點接收查詢需求后，通過判斷頂點存儲文件信息，若頂點x和頂點y所在序號第一位不相同，則采用分布式方法查詢，該方法最短路徑查詢具體步驟如下：

1) master節(jié)點查詢文件中割點集合P(x)、P(y)；

2) 將頂點x到割點集合P(x)的查詢發(fā)送到對應(yīng)的節(jié)點，同時將割點集合P(y)到頂點y的查詢發(fā)送到對應(yīng)的節(jié)點；

3) 各個節(jié)點分別計算頂點x、頂點y到P(x)和P(y)上割點之間的最短路徑，得到相應(yīng)的最短路徑集合；

4) master節(jié)點將兩個最短路徑集合進行合并，得出頂點x到頂點y的最短路徑集合；

5) master節(jié)點將最短路徑集合返回客戶端，算法結(jié)束；

以類集中式查詢?yōu)槔艨蛻舳诵枰樵冺旤cv19→v13的最短路徑，master通過讀取頂點存儲文件信息，判斷出頂點v19和頂點v13同屬于節(jié)點2，此時采用類集中式方法，即：將該查詢發(fā)送到節(jié)點2，由節(jié)點2進行查詢，查詢完畢后將結(jié)果返回master，master接收結(jié)果后返回給客戶端，至此，一次路徑查詢結(jié)束.

節(jié)點2查詢過程如下：

1)設(shè)置v19為源點，其屬性值為0，其他頂點屬性值為無窮大，初始化一個空隊列；

2)判斷鄰接點v18是否在隊列中，若不在，判斷v19的屬性值和鄰接點v18之間邊的屬性值之和是否小于無窮大，若是，繼續(xù)判斷v19是否存在下一個鄰接點，若存在，則繼續(xù)判斷v19到該鄰接點的屬性值之和是否小于上一個鄰接點屬性值之和，若小于，則設(shè)置該點到v19的屬性值并將該點入隊列，否則，將v18入隊列；

3)將v18設(shè)置為源點，循環(huán)迭代2)，直到終點v13；

4)將頂點v19，v18，v17，v15，v13的id作為key，屬性值作為value進行合并，得到最短路徑為18；

5)節(jié)點2將該結(jié)果返回master，master返回給客戶端，查詢結(jié)束.

3 實驗分析

3.1 實驗環(huán)境及數(shù)據(jù)集

本文所有實驗均在由三臺計算機建立的Spark集群上完成，一臺作為集群的主機master，另外兩臺作為集群的分機slave.每臺計算機配置為英特爾雙核CPU 3.00 GHz，6G內(nèi)存，1T硬盤，均裝有Ubuntu 14.04 LTS操作系統(tǒng)，使用Spark 2.1.1開發(fā)環(huán)境，開發(fā)語言為Scala.本文采用Scale-Free模型生成圖模型，生成的圖數(shù)據(jù)如表1所示.

表1 數(shù)據(jù)集參數(shù)

3.2 實驗結(jié)果分析

本文在不同規(guī)模數(shù)據(jù)集上進行實驗，以驗證LSGSP-SG算法與Dijkstra算法、D-CH算法[6]的優(yōu)劣如圖6所示.根據(jù)實驗結(jié)果可以看出，當圖規(guī)模較小時，D-CH 算法查詢時間最長， Dijkstra 算法次之，LSGSP-SG算法的查詢時間最短.隨著圖規(guī)模的增大，傳統(tǒng)算法時間復(fù)雜度明顯增加，hadoop平臺下查詢時間次之，而LSGSP-SG算法查詢時間依然最短，且隨著圖規(guī)模的增大，差距越來越明顯.

圖6 算法運行時間對比圖

4 結(jié)束語

隨著圖規(guī)模的增大，單機環(huán)境已無法滿足數(shù)據(jù)圖的存儲及最短路徑查詢需求.本文提出的基于Spark-GraphX的大規(guī)模圖最短路徑查詢方法采用分布式的處理技術(shù)，可有效解決任何規(guī)模圖數(shù)據(jù)的最短路徑查詢問題.

[1] 富麗貞，孟小峰.大規(guī)模圖數(shù)據(jù)可達性索引技術(shù)：現(xiàn)狀與展望[J].計算機研究與發(fā)展，2015，52(3):116-129.

[2] Dijkstra E.W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.

[3] Ford L,Fulkerson D.Flows in Networks[M].Princeton NJ:Princeton University Press,1962.

[4] 謝希仁,陳鳴,張興元.計算機網(wǎng)絡(luò)[M].北京：電子工業(yè)出版社，1994.

[5] Guerrieri A,Montresor A.Distributed Edge Partitioning for Graph Processing[J].Eprint Arxiv,2014,32(1):48-74.

[6] 黃明，吳煒.快刀初試：Spark GraphX在淘寶的實踐[EB/OL].http://www.csdn.net/article/2014-08-07/2821097?locationNum=3,2017-08-01.

[7] 宋寶燕，張瑞浩，單曉歡.一種基于Hadoop的大規(guī)模圖最短路徑查詢方法[J].遼寧大學(xué)學(xué)報：自然科學(xué)版,2016,44(2):109-113.

(責(zé)任編輯鄭綏乾)

AShortestPathMethodonLarge-scaleGraphBasedonSpark-GraphX

SONG Bao-yan,ZHANG Yong-pu,SHAN Xiao-huan*

(InformationCollege,LiaoningUniversity,Shenyang110036,China)

The shortest path problem has always been a hot topic in computer science and other issues,often used in social networks,transportation networks and many other areas.The increase of graphs leads to the storage of the traditional stand-alone environment,and the query can not meet the processing requirements of large-scale graphs.In this paper,we propose a LSGSP-SG method based on the Spark-GraphX platform.Firstly,we use the classical algorithm to segment and mark the large-scale graphs,and record the information of the cut in the text file ,Then use the large data platform Spark′s GraphX framework for iterative distribution calculation and the various computer nodes in the message communication and synchronization,and finally the shortest path calculation results output to the client.

Spark，graph partition，shortest path，distributed

TP 311

A

1000-5846(2017)04-0289-05

2017-08-15

國家自然科學(xué)基金項目(61472169，61502215)資助

宋寶燕(1965-)，女，滿族，遼寧開原人，教授，主要研究方向：大數(shù)據(jù)技術(shù)、數(shù)據(jù)庫技術(shù)，圖數(shù)據(jù)技術(shù)等，E-mail：bysong@lnu.edu.cn;

張永普(1994-)，男，漢族，山東菏澤人，碩士研究生，主要研究方向：圖數(shù)據(jù)技術(shù).

*

單曉歡(1987-)，女，漢族，遼寧沈陽人，助理實驗師，主要研究方向：大數(shù)據(jù)技術(shù)，圖數(shù)據(jù)技術(shù).