Spark的图计算框架：GraphX

孙海

（四川大学计算机学院，成都 610065）

Spark的图计算框架：GraphX

孙海

（四川大学计算机学院，成都 610065）

Spark是UC Berkeley AMP Lab所开源的类Hadoop MapReduce的通用并行框架，是专为大规模数据处理而设计的快速通用的计算引擎，在如今的大数据环境下，Spark所发挥的作用正越来越大。介绍Spark的图计算框架GraphX。

Spark；并行；大数据；GraphX

1 Spark生态圈介绍

Spark生态圈即BDAS（伯克利数据分析栈）包含了 Spark Core、Spark Streaming、Spark SQL、MLLib和GraphX等组件，其中Spark Core提供内存计算、Spark Streaming主要处理实时应用、Spark SQL提供及时查询、MLLib的机器学习和GraphX的图处理，它们都是由AMP实验室提供，能够无缝地集成并提供一站式解决平台[1]。

图1

GraphX是Spark中用于图的并行计算的模块，可以认为是GraphLab和Pregel在Spark上的重写及优化，与其他分布式图计算框架相比，GraphX具有的优势在于，它是依附于Spark之上的，天然的具备了Spark的一些特点，并且它提供了数据的一栈式解决方案，可以非常快速且有效地完成一整套图计算的流水作业。GraphX是Spark生态中的非常重要的组件，融合了图并行计算以及数据并行计算的优势，虽然在单纯的计算阶段的性能相比不如GraphLab等计算框架，但是如果从整个图处理流水线的视角（图构建，图合并，最终结果的查询）看，那么性能就非常具有优势了。流水作业处理过程如图2所示。

图2

2 属性图

在GraphX中，图的点和边都带有属性，而且这种属性图拥有Table和Graph两种视图，但是只有一份物理存储。Table视图将图看成Vertex Property Table和Edge Property Table等的组合，这些Table继承了Spark RDD的API[2]。具体说明如图3所示：

图3

可知点和边都带有属性，在实际应用中，我们可以根据需求自定义点和边的属性，从而更好地解决我们的问题。Graph视图上包括了reverse/subgraph/mapV（E）/mrTriplets等操作，这些操作可以使我们更加灵活地对目标图进行一系列的操作。

GraphX的这种属性图的特质带来了如下的好处：

点分割：graphX存储图的方式为点分割方式。这种存储图方式与传统图计算框架不同的是，不同的机器有可能存储相同的点，但是任何一条边只会出现在一台机器上。所以当点被分割到不同机器上时，会是相同的镜像，有一个点是作为主点（master）,其他的点作为虚拟点（ghost）。之所以这样设计，是因为当出现点的数据发生变化时,首先要做的是更新该点的master的数据，然后该点的ghost所在的机器接受该点所有更新好的数据，更新该点的虚拟点。这样做的好处是对于某个点与它的邻居的交互操作，只要满足结合律和交换律，极大地节省了操作消耗，并且可以保证在边的存储上是没有冗余的。例如求邻居权重的和，求点的所有边的条数这样的操作，可以在不同的机器上并行进行，然后对其进行汇总，这样做可以减少网络开销。

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所示，其中的数字表示该模块在源码中的代码量。

图4

由上图可知，GraphX对图计算的算法支持性较好，既包括了像PageRank这样的经典算法，也涵盖类SVD、K-core等主流的图计算算法，可以基本满足用户对图计算的要求。

如同Spark一样，GraphX的Graph类提供了丰富的图运算符，大致结构如图5所示。

图5

GraphX在Spark 1.3.1改变了部分用户正在使用API：

（1）为了改进性能，引入了一个新版的 mapReduceTriplets称为aggregateMessages，它取先前返回信息从mapReduceTriplets通过一个回调 EdgeContext而不是通过返回值。我们正在遗弃mapReduceTriplets，鼓励用户查阅过度指南。

（2）在spark1.0和1.1，EdgeRDD的签名切换从EdgeRDD[ED]到EdgeRDD[ED,VD]来进行一些缓存优化。我们已经发现了一个更加优雅的解决方案，恢复了签名到更加自然地EdgeRDD[ED]类型。

4 GraphX的应用

随着智能化手机的普遍应用，我们也处在了一个信息化的时代，人们每天的衣食住行都可以产生大量的数据。国内外一些互联网公司为了更好地了解消费者的消费习惯，从而提高经济效益，所以人类行为产生的海量数据就被应用到了广告、报表、推荐系统等这些业务上。这些应用场景的普遍特点是效率要求高、计算量大。其中涉及大量的图计算。GraphX对于这种情况具有天然的优势，因为它依附于并行化处理框架Spark之上，自然地就拥有Spark处理大数据的优势；同时GraphX自己就包含了很多关于图计算的算法，其属性图的特质可以使用户自定义点和边的属性，极大地提高了图的效率。

阿里巴巴旗下的天猫和淘宝两大平台的广告和搜索业务最开始为了解决一些复杂的机器学习上的一些问题，使用的是机器学习框架Mahout，但这样做的后果是代码不易维护且效率低下。在使用了Spark中的GraphX模块来挖掘用户商品关系的生产问题时，取得了较好的结果。同时在商品推荐、社区发现，关系挖掘、基于三角形计数的关系衡量、基于随机游走的用户属性传播等[4]方面表现良好。

优酷土豆在使用Hadoop的突出问题主要包括：第一是商业智能BI方面，分析师提交任务之后需要等待很长时间才得到结果;第二就是海量数据的计算，例如进行一些模拟广告投放之时，计算量非常大的同时对效率要求也比较高，最后就是机器学习和图计算的迭代运算也是需要耗费大量资源且运算速度很慢。

合一集团下的优酷土豆最开始在进行广告投放和商业智能BI方面的技术所用的是Hadoop，最开始也能满足商业上的需求，但随着视频会员的不断增长以及广告类型的多样化，海量的数据运算就对Hadoop带来了很大的压力。在广告投放这一块，优酷土豆的广告技术部门使用了GraphX来进行图计算，实际生产中发现集群相较于使用Hadoop时压力陡然减小。在对比Spark和 Hadoop的性能时可以发现，Spark要比Hadoop高出100倍左右，同时Spark提供了诸多模块来适应不同的需求，可以很好地满足工业生产需求。

综上所述，Spark在如今的互联网公司中应用较为广泛，而GraphX更是在公司的核心业务上发挥着举足轻重的作用。可以预见，在大数据时代下，GraphX必将拥有更加辉煌的明天。

5 结语

本文详细介绍了Spark的图计算框架GraphX，使我们对GraphX有了一个较为清楚的认识。同其他图计算框架相比，GraphX在计算、图优化和性能方面都具有一定的优势。同时，GraphX依附于Spark之上，其计算引擎提供了强大的计算接口，方便了编程，可以很容易地实现PageRank等图算法。其在一些互联网公司的应用也很广泛，是一种图计算比较好的计算框架。

[1]黎文阳.大数据处理模型Apache Spark研究[J].现代计算机:专业版,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-），男，硕士，研究方向为大数据

2017-02-21

2017-03-10