段劍峰（四川大學計算機學院，成都　610000）

基于Spark的大規(guī)模圖數(shù)據(jù)并行計算研究

段劍峰
（四川大學計算機學院，成都610000）

0　引言

圖是一種抽象的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)實世界中的許多場景都需要用圖結(jié)構(gòu)表示，例如在線地圖的最短路徑、社交網(wǎng)絡(luò)分析、科技文獻的引文網(wǎng)絡(luò)等。隨著Web2.0技術(shù)的發(fā)展，社交網(wǎng)絡(luò)用戶數(shù)量和網(wǎng)頁數(shù)量猛增，導致圖數(shù)據(jù)規(guī)模迅速增長。云計算對于處理大規(guī)模圖數(shù)據(jù)[1-2]有諸多優(yōu)勢，然而云計算只提供通用的處理框架，圖計算需要復雜的迭代計算和網(wǎng)絡(luò)通信，采用Hadoop的MapReduce[5]計算框架進行大規(guī)模圖數(shù)據(jù)處理，會存在磁盤I/O過多而導致時間代價過高等問題。Spark[3，6-7]利用其內(nèi)存計算的優(yōu)勢，提供了一套圖計算框架Graphx，其中，Pregel類似于MapReduce框架，是一套靈活高效，擴展性強，可供用戶自定義的計算框架，適用于圖的并行迭代計算。

1　PageRank算法與Pregel計算框架

1.1PageRank 算法

PageRank算法[4]是一種搜索引擎常用的算法，用于計算網(wǎng)頁的排名，向用戶提供以PageRank值為參考的搜索結(jié)果。網(wǎng)頁用圖頂點表示，網(wǎng)頁之間的鏈接關(guān)系用有向邊表示。頂點屬性表示網(wǎng)頁的PageRank值，頂點入度越高，說明指向該網(wǎng)頁的鏈接越多，PageRank值越大。一個頂點的出度為d，則向每個指向的頂點貢獻1/d的PageRank值。一個頁面有較多的鏈入頁面有較高的PageRank值，如果沒有鏈入頁面，則PageRank值為0。為防止頁面?zhèn)鞒鋈サ闹禐?，每個頁面設(shè)定一個最小值。數(shù)學公式如（1）:

pi∈P，P=｛p1，p2，…，pN｝表示數(shù)據(jù)集的所有頁面，N是頁面總數(shù)，pj表示鏈入的頁面，N（pj）表示pj鏈出的頁面總數(shù)，q是確定頁面最小值的可變參數(shù)。

算法開始時，為每個頁面隨機分配一個PageRank值，依據(jù)公式（1）進行迭代計算，當|PageRank（pi）t-PageRank（pi）t-1|<著，即本次和上次計算的PageRank值小于某閾值，頁面的值趨向穩(wěn)定，算法迭代結(jié)束。

1.2Pregel 計算框架

Pregel計算框架是一個約束到圖拓撲的批量同步并行消息抽象的接口。Pregel執(zhí)行一系列的超步（super steps）運算。每一次超步運算，頂點從之前的超步中接收鄰居消息的總和，為頂點計算一個新的屬性，向鄰居發(fā)送更新的屬性，判斷是否達到收斂條件，如果不收斂，則繼續(xù)接收鄰居消息。類似于Hadoop的MapRe-duce框架，用戶需要實現(xiàn)Map和Reduce函數(shù)，Pregel框架需要用戶實現(xiàn)vprog，sendMsg，mergeMsg三個函數(shù)。Pregel定義如下：

VD是圖頂點的屬性類型，A是消息類型，ED是圖的邊類型，EdgeTriplet是圖的節(jié)點對類型。包含兩組參數(shù)，第一組參數(shù)為常量參數(shù)，initialMsg是觸發(fā)圖進行迭代計算的初始消息，maxIterations是最大迭代次數(shù)，ac-tiveDirection表示有向圖的消息傳播方向。第二組參數(shù)為用戶自定義函數(shù)，vprog函數(shù)功能是根據(jù)類型為A的鄰居消息總和，將一個節(jié)點的屬性更新為類型為VD的新屬性。sendMsg函數(shù)功能是依據(jù)節(jié)點對中節(jié)點和鄰居的屬性，向鄰居發(fā)送類型為A的消息。mergeMsg函數(shù)功能是將兩個鄰居的消息合并為一個類型為A的消息。

在傳統(tǒng)的圖計算框架下，圖節(jié)點的迭代運算是順序執(zhí)行，即一個頂點運算完成后運算下一個頂點。或利用多線程，達到多個頂點并發(fā)運算。由于在傳統(tǒng)單機環(huán)境下，CPU和內(nèi)存等計算資源受到限制，多線程方式受到限制。在分布式環(huán)境下，Pregel高效并發(fā)執(zhí)行。圖的每個頂點運算是獨立的，vprog，sendMsg，mergeMsg三個函數(shù)針對每個頂點，分別在不同計算節(jié)點并行運算。其中，mergeMsg在各計算節(jié)點分別進行合并，大大提升了運算效率。

2　PageRank算法并行化

PageRank算法中，各節(jié)點運算只依賴于本身和其鄰居節(jié)點，故適合于使用Pregel計算框架實現(xiàn)。本文給出了PageRank算法在Pregel框架下的一種實現(xiàn)，核心為實現(xiàn)vprog，sendMsg，mergeMsg三個函數(shù)。為方便計算，將圖的頂點屬性初始化為PageRank=0和 差值σ= 0，邊屬性初始化為頂點的，表示頂點能向其他每個鄰居貢獻的PageRank值比例。

2.1PageRank 值更新

vprog函數(shù)根據(jù)節(jié)點本身的PageRank值和所有鏈入的鄰居合并后的PageRank值計算新的PageRank值。返回新的節(jié)點屬性和差值，節(jié)點屬性用于下次迭代時向鏈出的鄰居發(fā)送消息，差值用于在sendMSg函數(shù)中判斷是否達到收斂。函數(shù)實現(xiàn)：

2.2 傳播消息

sendMsg函數(shù)根據(jù)vprog函數(shù)的計算后的差值是否大于閾值，向鄰居節(jié)點發(fā)送消息，消息值為節(jié)點的PageRank值乘以節(jié)點的貢獻比值。函數(shù)實現(xiàn)：

2.3消息合并

mergeMsg函數(shù)將一個節(jié)點的任意兩個鄰居的消息合并為一個類型一致的消息，該操作在從計算節(jié)點上執(zhí)行，提高了運算的并行度，減輕了主計算節(jié)點的運算壓力，提升了運算速度。函數(shù)實現(xiàn):

3　實驗分析

定義頂點數(shù)量為10000，20000條連邊，頂點屬性初始為0的圖，分別選取 2000、4000、6000、8000和10000個頂點的子圖進行對比實驗。實驗設(shè)備為3臺物理機，每臺物理機的CPU為2核，內(nèi)存為4G。實驗比較不同計算節(jié)點和不同頂點對算法運行時間的影響。

實驗表明，并行化的PageRank算法相比傳統(tǒng)的單節(jié)點實現(xiàn)的算法，運行效率有明顯提升。隨著圖頂點數(shù)量的增長，算法的時間消耗成線性增長，說明Pregel計算框架適合于大規(guī)模的圖數(shù)據(jù)運算。

另外，實驗比較算法迭代次數(shù)對算法運行效率的影響。

圖1　頂點規(guī)模對時間的影響

圖2　迭代次數(shù)對時間的影響

圖2可知，隨著迭代次數(shù)的增加，算法運行時間增長趨于平滑，說明Spark的內(nèi)存計算模型在迭代計算上體現(xiàn)明顯優(yōu)勢，Pregel計算框架適合大規(guī)模圖數(shù)據(jù)的迭代算法。

4　結(jié)語

本文通過PageRank算法在Spark上的實現(xiàn)，驗證了Pregel圖計算框架時間效率高，說明Spark處理大規(guī)模圖數(shù)據(jù)具有明顯的優(yōu)勢。此外，Pregel計算框架供用戶自定義接口，具有良好的擴展性，可靈活應(yīng)用到社交網(wǎng)絡(luò)分析和社會化推薦等算法中。

[1]Malewicz G,Austern M H,Bik A J C,et al.Pregel:a System for Large-Scale Graph Processing[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.ACM,2010:135-146.

[2]Kang U,Tong H,Sun J,et al.Gbase:a Scalable and General Graph Management System[C].Proceedings of the 17th ACM SIGKDD

International Conference on Knowledge Discovery and Data Mining.ACM,2011:1091-1099.

[3]Zaharia M,Chowdhury M,Das T,et al.Resilient Distributed Datasets:A Fault-Tolerant Abstraction for In-Memory Cluster Computing[C].Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation.USENIX Association,2012:2-2. [4]Brin S,Page L.Reprint of:The Anatomy of a Large-Scale Hypertextual Web Search Engine[J].Computer Networks,2012,56（18）:3825-3833.

[5]Hadoop MapReduce Tutorial[EB/OL].http://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html.

[6]Spark Programming Guides[EB/OL].http://spark.apache.org/docs/1.1.0/quick-start.html.

[7]Scala[EB/OL].https://www.scala-lang.org.

Research on Large-Scale Graph Parallel Computing Based on Spark

DUAN Jian-feng
（College of Computer Science，Sichuan University，Chengdu 610000）

1007-1423（2016）07-0044-04

10.3969/j.issn.1007-1423.2016.07.010

段劍峰（1989-），男，云南大理人，在讀研究生，研究方向為移動與分布式計算

2016－01－26

2016－02－25

1007-1423（2016）07-0065-0410.3969/j.issn.1007-1423.2016.07.015

隨著社交網(wǎng)絡(luò)的興起，大規(guī)模圖數(shù)據(jù)處理技術(shù)成為研究的熱點，從海量的社交數(shù)據(jù)中分析數(shù)據(jù)的關(guān)系具有巨大的商業(yè)價值。Spark利用其內(nèi)存計算模型和適合迭代運算的優(yōu)勢，為大規(guī)模圖數(shù)據(jù)并行運算提供Graphx框架。以經(jīng)典的PageRank算法為例，分析Graphx框架下的Pregel迭代計算模型，總結(jié)Pregel計算模型的優(yōu)勢和應(yīng)用場景。

大規(guī)模圖數(shù)據(jù)；并行計算；Spark；Pregel

With the development of social network,large-scale graph processing technology become a hot spot of research.Analyzing relationship from massive social data has great commercial value.Taking the advantages of memory-computing model and iterative computation,Spark provides Graphx for large-scale graph parallel computing framework.Analyzes the Pregel iterative computing model under Graphx in the example of classical PageRank algorithm,summarizes the advantages and application of Pregel computing model.

Large-Scale Graph;Parallel Computing;Spark;Pregel