Spark-GraphX框架下的大規模加權圖最短路徑查詢

宋寶燕，張永普，單曉歡

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

Spark-GraphX框架下的大規模加權圖最短路徑查詢

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

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

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

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

0 引言

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

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

1 相關工作

1.1 最短路徑查詢算法

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

1.2 圖分割及Spark-GraphX

●圖分割

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

圖1 邊分割策略

圖2 點分割策略

●Spark-GraphX

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

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

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

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

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

圖3 GraphX的代碼結構

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

2 大規模圖最短路徑查詢方法

2.1 大規模圖分割

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

圖4 DAG圖分割前

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

圖5 分割后子圖

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

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

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

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

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

●類集中式方法

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

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

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

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

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

●分布式方法

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

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

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

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

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

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

以類集中式查詢為例，若客戶端需要查詢頂點v19→v13的最短路徑，master通過讀取頂點存儲文件信息，判斷出頂點v19和頂點v13同屬于節點2，此時采用類集中式方法，即：將該查詢發送到節點2，由節點2進行查詢，查詢完畢后將結果返回master，master接收結果后返回給客戶端，至此，一次路徑查詢結束.

節點2查詢過程如下：

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

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

3)將v18設置為源點，循環迭代2)，直到終點v13；

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

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

3 實驗分析

3.1 實驗環境及數據集

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

表1 數據集參數

3.2 實驗結果分析

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

圖6 算法運行時間對比圖

4 結束語

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

[1] 富麗貞，孟小峰.大規模圖數據可達性索引技術：現狀與展望[J].計算機研究與發展，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] 謝希仁,陳鳴,張興元.計算機網絡[M].北京：電子工業出版社，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的大規模圖最短路徑查詢方法[J].遼寧大學學報：自然科學版,2016,44(2):109-113.

(責任編輯鄭綏乾)

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

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

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

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

*

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