Spark的圖計算框架：GraphX

孫海

（四川大學計算機學院，成都 610065）

Spark的圖計算框架：GraphX

孫海

（四川大學計算機學院，成都 610065）

Spark是UC Berkeley AMP Lab所開源的類Hadoop MapReduce的通用并行框架，是專為大規(guī)模數(shù)據(jù)處理而設計的快速通用的計算引擎，在如今的大數(shù)據(jù)環(huán)境下，Spark所發(fā)揮的作用正越來越大。介紹Spark的圖計算框架GraphX。

Spark；并行；大數(shù)據(jù)；GraphX

1 Spark生態(tài)圈介紹

Spark生態(tài)圈即BDAS（伯克利數(shù)據(jù)分析棧）包含了 Spark Core、Spark Streaming、Spark SQL、MLLib和GraphX等組件，其中Spark Core提供內(nèi)存計算、Spark Streaming主要處理實時應用、Spark SQL提供及時查詢、MLLib的機器學習和GraphX的圖處理，它們都是由AMP實驗室提供，能夠無縫地集成并提供一站式解決平臺[1]。

圖1

GraphX是Spark中用于圖的并行計算的模塊，可以認為是GraphLab和Pregel在Spark上的重寫及優(yōu)化，與其他分布式圖計算框架相比，GraphX具有的優(yōu)勢在于，它是依附于Spark之上的，天然的具備了Spark的一些特點，并且它提供了數(shù)據(jù)的一棧式解決方案，可以非常快速且有效地完成一整套圖計算的流水作業(yè)。GraphX是Spark生態(tài)中的非常重要的組件，融合了圖并行計算以及數(shù)據(jù)并行計算的優(yōu)勢，雖然在單純的計算階段的性能相比不如GraphLab等計算框架，但是如果從整個圖處理流水線的視角（圖構建，圖合并，最終結果的查詢）看，那么性能就非常具有優(yōu)勢了。流水作業(yè)處理過程如圖2所示。

圖2

2 屬性圖

在GraphX中，圖的點和邊都帶有屬性，而且這種屬性圖擁有Table和Graph兩種視圖，但是只有一份物理存儲。Table視圖將圖看成Vertex Property Table和Edge Property Table等的組合，這些Table繼承了Spark RDD的API[2]。具體說明如圖3所示：

圖3

可知點和邊都帶有屬性，在實際應用中，我們可以根據(jù)需求自定義點和邊的屬性，從而更好地解決我們的問題。Graph視圖上包括了reverse/subgraph/mapV（E）/mrTriplets等操作，這些操作可以使我們更加靈活地對目標圖進行一系列的操作。

GraphX的這種屬性圖的特質(zhì)帶來了如下的好處：

點分割：graphX存儲圖的方式為點分割方式。這種存儲圖方式與傳統(tǒng)圖計算框架不同的是，不同的機器有可能存儲相同的點，但是任何一條邊只會出現(xiàn)在一臺機器上。所以當點被分割到不同機器上時，會是相同的鏡像，有一個點是作為主點（master）,其他的點作為虛擬點（ghost）。之所以這樣設計，是因為當出現(xiàn)點的數(shù)據(jù)發(fā)生變化時,首先要做的是更新該點的master的數(shù)據(jù)，然后該點的ghost所在的機器接受該點所有更新好的數(shù)據(jù)，更新該點的虛擬點。這樣做的好處是對于某個點與它的鄰居的交互操作，只要滿足結合律和交換律，極大地節(jié)省了操作消耗，并且可以保證在邊的存儲上是沒有冗余的。例如求鄰居權重的和，求點的所有邊的條數(shù)這樣的操作，可以在不同的機器上并行進行，然后對其進行匯總，這樣做可以減少網(wǎng)絡開銷。

Join Elimination：例如在PageRank計算中，一個點值的更新只跟鄰居點的值有關，而跟該點本身的值無關，那么在mrTriplets計算中，就不需要Vertex Table和Edge Table的3-way join，而只需要2-way join。

Caching for Iterative mrTriplets&Indexing Active Edges：在算法迭代的后期，只有較少的點有更新，因此對沒有更新的點使用local cached能夠大幅度降低通信所耗。

3 GraphX所支持的算法

在最新版本的Spark2.1.0中，GraphX包含了一系列的圖計算的算法來簡化用戶對圖分析的工作[3]，具體情況如圖4所示，其中的數(shù)字表示該模塊在源碼中的代碼量。

圖4

由上圖可知，GraphX對圖計算的算法支持性較好，既包括了像PageRank這樣的經(jīng)典算法，也涵蓋類SVD、K-core等主流的圖計算算法，可以基本滿足用戶對圖計算的要求。

如同Spark一樣，GraphX的Graph類提供了豐富的圖運算符，大致結構如圖5所示。

圖5

GraphX在Spark 1.3.1改變了部分用戶正在使用API：

（1）為了改進性能，引入了一個新版的 mapReduceTriplets稱為aggregateMessages，它取先前返回信息從mapReduceTriplets通過一個回調(diào) EdgeContext而不是通過返回值。我們正在遺棄mapReduceTriplets，鼓勵用戶查閱過度指南。

（2）在spark1.0和1.1，EdgeRDD的簽名切換從EdgeRDD[ED]到EdgeRDD[ED,VD]來進行一些緩存優(yōu)化。我們已經(jīng)發(fā)現(xiàn)了一個更加優(yōu)雅的解決方案，恢復了簽名到更加自然地EdgeRDD[ED]類型。

4 GraphX的應用

隨著智能化手機的普遍應用，我們也處在了一個信息化的時代，人們每天的衣食住行都可以產(chǎn)生大量的數(shù)據(jù)。國內(nèi)外一些互聯(lián)網(wǎng)公司為了更好地了解消費者的消費習慣，從而提高經(jīng)濟效益，所以人類行為產(chǎn)生的海量數(shù)據(jù)就被應用到了廣告、報表、推薦系統(tǒng)等這些業(yè)務上。這些應用場景的普遍特點是效率要求高、計算量大。其中涉及大量的圖計算。GraphX對于這種情況具有天然的優(yōu)勢，因為它依附于并行化處理框架Spark之上，自然地就擁有Spark處理大數(shù)據(jù)的優(yōu)勢；同時GraphX自己就包含了很多關于圖計算的算法，其屬性圖的特質(zhì)可以使用戶自定義點和邊的屬性，極大地提高了圖的效率。

阿里巴巴旗下的天貓和淘寶兩大平臺的廣告和搜索業(yè)務最開始為了解決一些復雜的機器學習上的一些問題，使用的是機器學習框架Mahout，但這樣做的后果是代碼不易維護且效率低下。在使用了Spark中的GraphX模塊來挖掘用戶商品關系的生產(chǎn)問題時，取得了較好的結果。同時在商品推薦、社區(qū)發(fā)現(xiàn)，關系挖掘、基于三角形計數(shù)的關系衡量、基于隨機游走的用戶屬性傳播等[4]方面表現(xiàn)良好。

優(yōu)酷土豆在使用Hadoop的突出問題主要包括：第一是商業(yè)智能BI方面，分析師提交任務之后需要等待很長時間才得到結果;第二就是海量數(shù)據(jù)的計算，例如進行一些模擬廣告投放之時，計算量非常大的同時對效率要求也比較高，最后就是機器學習和圖計算的迭代運算也是需要耗費大量資源且運算速度很慢。

合一集團下的優(yōu)酷土豆最開始在進行廣告投放和商業(yè)智能BI方面的技術所用的是Hadoop，最開始也能滿足商業(yè)上的需求，但隨著視頻會員的不斷增長以及廣告類型的多樣化，海量的數(shù)據(jù)運算就對Hadoop帶來了很大的壓力。在廣告投放這一塊，優(yōu)酷土豆的廣告技術部門使用了GraphX來進行圖計算，實際生產(chǎn)中發(fā)現(xiàn)集群相較于使用Hadoop時壓力陡然減小。在對比Spark和 Hadoop的性能時可以發(fā)現(xiàn)，Spark要比Hadoop高出100倍左右，同時Spark提供了諸多模塊來適應不同的需求，可以很好地滿足工業(yè)生產(chǎn)需求。

綜上所述，Spark在如今的互聯(lián)網(wǎng)公司中應用較為廣泛，而GraphX更是在公司的核心業(yè)務上發(fā)揮著舉足輕重的作用。可以預見，在大數(shù)據(jù)時代下，GraphX必將擁有更加輝煌的明天。

5 結語

本文詳細介紹了Spark的圖計算框架GraphX，使我們對GraphX有了一個較為清楚的認識。同其他圖計算框架相比，GraphX在計算、圖優(yōu)化和性能方面都具有一定的優(yōu)勢。同時，GraphX依附于Spark之上，其計算引擎提供了強大的計算接口，方便了編程，可以很容易地實現(xiàn)PageRank等圖算法。其在一些互聯(lián)網(wǎng)公司的應用也很廣泛，是一種圖計算比較好的計算框架。

[1]黎文陽.大數(shù)據(jù)處理模型Apache Spark研究[J].現(xiàn)代計算機:專業(yè)版,2015（3）:55-60.

[2]Xin R S,Crankshaw D,Dave A,et al.GraphX:Unifying Data-Parallel and Graph-Parallel Analytics[J].Computer Science,2014.

[3]陳虹君.Spark框架的GraphX算法研究[J].電腦知識與技術,2015（1）:75-77.

[4]黃明,吳煒.快刀初試:Spark GraphX在淘寶的實踐[J].程序員,2014（8）:98-103.

Spark's Graph Calculation Framework:GraphX

SUN Hai
（College of Computer Science,Sichuan University，Chengdu 610065）

Spark is a generic parallel framework for the open source Hadoop MapReduce from UC Berkeley AMP Lab,a fast and versatile computing engine designed for large-scale data processing.In today′s big data environment,Spark′s role is growing.Introduces Spark′s graph calculation framework GraphX.

Spark;Parallel;Big Data;GraphX

18212

1007-1423（2017）09-0120-04

10.3969/j.issn.1007-1423.2017.09.027

孫海（1991-），男，碩士，研究方向為大數(shù)據(jù)

2017-02-21

2017-03-10