Spark高速计算引擎之Spark GraphX(四)

前言

Spark GraphX是一个分布式图处理框架，它是基于Spark平台提供对图计算和图挖掘简洁易用的而丰富的接口，极大的方便了对分布式图处理的需求。

一、Spark GraphX概述

GraphX是一个新的Spark API，它用于图和分布式图(graph-parallel)的计算。GraphX通过引入弹性分布式属性图(Resilient Distributed Property Graph)：顶点和边均有属性的有向多重图，来扩展Spark RDD。
为了支持图计算， GraphX 公开了一系列基本运算符（比如：mapVertices、mapEdges、subgraph）以及优化后的 Pregel API 变种。此外，还包含越来越多的图算法和构建器，以简化图形分析任务。

1.1图的相关术语

图是一种较线性表和树更为复杂的数据结构，图表达的是多对多的关系。

如上图所示，G1 是一个简单的图，其中 V1、V2、V3、V4 被称作顶点（Vertex），任意两个顶点之间的通路被称为边（Edge），它可以由（V1、V2）有序对来表示，这时称 G1 为有向图，意味着边是有方向的，若以无序对来表示图中一条边，则该图为无向图，如 G2。
在 G1 中，与顶点相关联的边的数量被称为顶点的度（Degree）。其中，以顶点为起点的边的数量被称为该顶点的出度（OutDegree），以顶点为终点的边的数量被称为该顶点的入度（InDegree）。

1.2图计算模式

目前基于图的并行计算框架已经有很多，比如来自Google的Pregel、来自Apache开源的图计算框架Giraph / HAMA以及最为著名的GraphLab，其中Pregel、HAMA和Giraph都是非常类似的，都是基于BSP模式。
BSP即整体同步并行，它将计算分成一系列超步的迭代。从纵向上看，它是一个串行模式，而从横向上看，它是一个并行的模式，每两个超步之间设置一个栅栏（barrier），即整体同步点，确定所有并行的计算都完成后再启动下一轮超步。

每一个超步包含三部分内容：

• 计算compute：每一个processor利用上一个超步传过来的消息和本地的数据进行本地计算
• 消息传递：每一个processor计算完毕后，将消息传递个与之关联的其它processors
• 整体同步点：用于整体同步，确定所有的计算和消息传递都进行完毕后，进入下一个超步

二、Spark GraphX 基础

2.1 GraphX 架构

GraphX的整体架构可以分为三个部分：

• 算法层：基于 Pregel 接口实现了常用的图算法。包括 PageRank、SVDPlusPlus、TriangleCount、 ConnectedComponents、StronglyConnectedConponents 等算法
• 接口层：在底层 RDD 的基础之上实现了 Pregel 模型 BSP 模式的计算接口
• 底层：图计算的核心类，包含：VertexRDD、EdgeRDD、RDD[EdgeTriplet]

2.2存储模式

巨型图的存储总体上有边分割和点分割两种存储方式。2013年，GraphLab2.0将其存储方式由边分割变为点分割，在性能上取得重大提升，目前基本上被业界广泛接受并使用。

• 边分割（Edge-Cut）： 每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的好处是节省存储空间；坏处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大
• 点分割（Vertex-Cut）： 每条边只存储一次，都只会出现在一台机器上。邻居多的点会被复制到多台机器上，增加了存储开销，同时会引发数据同步问题。好处是可以大幅减少内网通信量

虽然两种方法互有利弊，但现在是点分割占上风，各种分布式图计算框架都将自己底层的存储形式变成了点分割。主要原因有以下两个：

• 磁盘价格下降，存储空间不再是问题，而内网的通信资源没有突破性进展，集群计算时内网带宽是宝贵的，时间比磁盘更珍贵。这点就类似于常见的空间换时间的策略；
• 在当前的应用场景中，绝大多数网络都是“无尺度网络”，遵循幂律分布，不同点的邻居数量相差非常悬殊。而边分割会使那些多邻居的点所相连的边大多数被分到不同的机器上，这样的数据分布会使得内网带宽更加捉襟见肘，于是边分割存储方式被渐渐抛弃了；

2.3核心数据结构

核心数据结构包括：graph、vertices、edges、triplets
1.Graph
GraphX 用属性图的方式表示图，顶点有属性，边有属性。存储结构采用边集数组的形式，即一个顶点表，一个边表，如下图所示：

顶点 ID 是非常重要的字段，它不光是顶点的唯一标识符，也是描述边的唯一手段。顶点表与边表实际上就是 RDD，它们分别为 VertexRDD 与 EdgeRDD。在 Spark 的源码中，Graph 类如下：

• vertices 为顶点表，VD 为顶点属性类型
• edges 为边表，ED 为边属性类型
• 可以通过 Graph 的 vertices 与 edges 成员直接得到顶点 RDD 与边 RDD
• 顶点 RDD 类型为 VerticeRDD，继承自 RDD[(VertexId, VD)]
• 边 RDD 类型为 EdgeRDD，继承自 RDD[Edge[ED]]

2、vertices
vertices对应着名为 VertexRDD 的RDD。这个RDD由顶点id和顶点属性两个成员变量。
3.edges
edges对应着EdgeRDD。这个RDD拥有三个成员变量，分别是源顶点id、目标顶点id以及边属性。
4、triplets
triplets 表示边点三元组，如下图所示（其中圆柱形分别代表顶点属性与边属性）：

通过 triplets 成员，用户可以直接获取到起点顶点、起点顶点属性、终点顶点、终点顶点属性、边与边属性信息。triplets 的生成可以由边表与顶点表通过 ScrId 与DstId 连接而成。
triplets对应着EdgeTriplet。它是一个三元组视图，这个视图逻辑上将顶点和边的属性保存为一个RDD[EdgeTriplet[VD, ED]]。