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

段劍峰（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610000）

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

段劍峰
（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610000）

0　引言

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

1　PageRank算法與Pregel計(jì)算框架

1.1PageRank 算法

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

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

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

1.2Pregel 計(jì)算框架

Pregel計(jì)算框架是一個(gè)約束到圖拓?fù)涞呐客讲⑿邢⒊橄蟮慕涌凇regel執(zhí)行一系列的超步（super steps）運(yùn)算。每一次超步運(yùn)算，頂點(diǎn)從之前的超步中接收鄰居消息的總和，為頂點(diǎn)計(jì)算一個(gè)新的屬性，向鄰居發(fā)送更新的屬性，判斷是否達(dá)到收斂條件，如果不收斂，則繼續(xù)接收鄰居消息。類似于Hadoop的MapRe-duce框架，用戶需要實(shí)現(xiàn)Map和Reduce函數(shù)，Pregel框架需要用戶實(shí)現(xiàn)vprog，sendMsg，mergeMsg三個(gè)函數(shù)。Pregel定義如下：

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

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

2　PageRank算法并行化

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

2.1PageRank 值更新

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

2.2 傳播消息

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

2.3消息合并

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

3　實(shí)驗(yàn)分析

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

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

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

圖1　頂點(diǎn)規(guī)模對時(shí)間的影響

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

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

4　結(jié)語

本文通過PageRank算法在Spark上的實(shí)現(xiàn)，驗(yàn)證了Pregel圖計(jì)算框架時(shí)間效率高，說明Spark處理大規(guī)模圖數(shù)據(jù)具有明顯的優(yōu)勢。此外，Pregel計(jì)算框架供用戶自定義接口，具有良好的擴(kuò)展性，可靈活應(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-），男，云南大理人，在讀研究生，研究方向?yàn)橐苿优c分布式計(jì)算

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ù)成為研究的熱點(diǎn)，從海量的社交數(shù)據(jù)中分析數(shù)據(jù)的關(guān)系具有巨大的商業(yè)價(jià)值。Spark利用其內(nèi)存計(jì)算模型和適合迭代運(yùn)算的優(yōu)勢，為大規(guī)模圖數(shù)據(jù)并行運(yùn)算提供Graphx框架。以經(jīng)典的PageRank算法為例，分析Graphx框架下的Pregel迭代計(jì)算模型，總結(jié)Pregel計(jì)算模型的優(yōu)勢和應(yīng)用場景。

大規(guī)模圖數(shù)據(jù)；并行計(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