Spark的圖計(jì)算框架：GraphX

孫海

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

Spark的圖計(jì)算框架：GraphX

孫海

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

Spark是UC Berkeley AMP Lab所開(kāi)源的類Hadoop MapReduce的通用并行框架，是專為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的快速通用的計(jì)算引擎，在如今的大數(shù)據(jù)環(huán)境下，Spark所發(fā)揮的作用正越來(lái)越大。介紹Spark的圖計(jì)算框架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)存計(jì)算、Spark Streaming主要處理實(shí)時(shí)應(yīng)用、Spark SQL提供及時(shí)查詢、MLLib的機(jī)器學(xué)習(xí)和GraphX的圖處理，它們都是由AMP實(shí)驗(yàn)室提供，能夠無(wú)縫地集成并提供一站式解決平臺(tái)[1]。

圖1

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

圖2

2 屬性圖

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

圖3

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

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

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

Join Elimination：例如在PageRank計(jì)算中，一個(gè)點(diǎn)值的更新只跟鄰居點(diǎn)的值有關(guān)，而跟該點(diǎn)本身的值無(wú)關(guān)，那么在mrTriplets計(jì)算中，就不需要Vertex Table和Edge Table的3-way join，而只需要2-way join。

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

3 GraphX所支持的算法

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

圖4

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

如同Spark一樣，GraphX的Graph類提供了豐富的圖運(yùn)算符，大致結(jié)構(gòu)如圖5所示。

圖5

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

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

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

4 GraphX的應(yīng)用

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

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

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

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

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

5 結(jié)語(yǔ)

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

[1]黎文陽(yáng).大數(shù)據(jù)處理模型Apache Spark研究[J].現(xiàn)代計(jì)算機(jī):專業(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].電腦知識(shí)與技術(shù),2015（1）:75-77.

[4]黃明,吳煒.快刀初試:Spark GraphX在淘寶的實(shí)踐[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-），男，碩士，研究方向?yàn)榇髷?shù)據(jù)

2017-02-21

2017-03-10