Spark之GraphX图计算

【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[84]篇文章，欢迎阅读和收藏】

1 基本概念

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

2 术语解释

图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为 G(V,E) ，其中， G 标示一个图， V 是图 G 中顶点的集合， E 是图 G 中边的集合。

无向图：若顶点 Vi 到 Vj 之间的边没有方向，则称这条边为无向边（ Edge ），用序偶对 (Vi,Vj) 标示。

有向图：若从顶点 Vi 到 Vj 的边是有方向的，则成这条边为有向边，也称为弧（ Arc ）。用有序对（ Vi ， Vj ）标示， Vi 称为弧尾， Vj 称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。

权（ Weight ）：有些图的边和弧有相关的数，这个数叫做权（ Weight ）。这些带权的图通常称为网（ Network ）。

图计算：图的分布式或者并行处理其实是把图拆分成很多的子图，然后分别对这些子图进行计算，计算的时候可以分别迭代进行分阶段的计算，即对图进行并行计算

3 详细说明

3.1 GraphX 框架

设计 GraphX 时，点分割和 GAS 都已成熟，在设计和编码中针对它们进行了优化，并在功能和性能之间寻找最佳的平衡点。如同 Spark 本身，每个子模块都有一个核心抽象。GraphX 的核心抽象是 Resilient Distributed Property Graph ，一种点和边都带属性的有向多重图。它扩展了 Spark RDD 的抽象，有 Table 和 Graph 两种视图，而只需要一份物理存储。两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。

如同 Spark ， GraphX 的代码非常简洁。GraphX 的核心代码只有 3 千多行，而在此之上实现的 Pregel 模式，只要短短的 20 多行。GraphX 的代码结构整体下图所示，其中大部分的实现，都是围绕 Partition 的优化进行的。这在某种程度上说明了点分割的存储和相应的计算优化，的确是图计算框架的重点和难点。

3.2 GraphX 实现分析

如同 Spark 本身，每个子模块都有一个核心抽象。GraphX 的核心抽象是 Resilient Distributed Property Graph ，一种点和边都带属性的有向多重图。它扩展了 Spark RDD 的抽象，有 Table 和 Graph 两种视图，而只需要一份物理存储。两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。

GraphX 的底层设计有以下几个关键点。

对 Graph 视图的所有操作，最终都会转换成其关联的 Table 视图的 RDD 操作来完成。这样对一个图的计算，最终在逻辑上，等价于一系列 RDD 的转换过程。因此， Graph 最终具备了 RDD 的 3 个关键特性：Immutable 、 Distributed 和 Fault-Tolerant ，其中最关键的是 Immutable （不变性）。逻辑上，所有图的转换和操作都产生了一个新图；物理上， GraphX 会有一定程度的不变顶点和边的复用优化，对用户透明。

两种视图底层共用的物理数据，由 RDD[Vertex-Partition] 和 RDD[EdgePartition] 这两个 RDD 组成。点和边实际都不是以表 Collection[tuple] 的形式存储的，而是由 VertexPartition/EdgePartition 在内部存储一个带索引结构的分片数据块，以加速不同视图下的遍历速度。不变的索引结构在 RDD 转换过程中是共用的，降低了计算和存储开销。

图的分布式存储采用点分割模式，而且使用 partitionBy 方法，由用户指定不同的划分策略（ PartitionStrategy ）。划分策略会将边分配到各个 EdgePartition ，顶点 Master 分配到各个 VertexPartition ， EdgePartition 也会缓存本地边关联点的 Ghost 副本。划分策略的不同会影响到所需要缓存的 Ghost 副本数量，以及每个 EdgePartition 分配的边的均衡程度，需要根据图的结构特征选取最佳策略。目前有 EdgePartition2d 、 EdgePartition1d 、 RandomVertexCut 和 CanonicalRandomVertexCut 这四种策略。

3.3 存储模式

3.3.1 图存储模式

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

l 边分割（ Edge-Cut ）：每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的好处是节省存储空间；坏处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大。

l 点分割（ Vertex-Cut ）：每条边只存储一次，都只会出现在一台机器上。邻居多的点会被复制到多台机器上，增加了存储开销，同时会引发数据同步问题。好处是可以大幅减少内网通信量。

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

1. 磁盘价格下降，存储空间不再是问题，而内网的通信资源没有突破性进展，集群计算时内网带宽是宝贵的，时间比磁盘更珍贵。这点就类似于常见的空间换时间的策略。

2. 在当前的应用场景中，绝大多数网络都是 “ 无尺度网络 ” ，遵循幂律分布，不同点的邻居数量相差非常悬殊。而边分割会使那些多邻居的点所相连的边大多数被分到不同的机器上，这样的数据分布会使得内网带宽更加捉襟见肘，于是边分割存储方式被渐渐抛弃了。

3.3.2 GraphX 存储模式

Graphx 借鉴 PowerGraph ，使用的是 Vertex-Cut( 点分割 ) 方式存储图，用三个 RDD 存储图数据信息：

lVertexTable(id, data) ：id 为 Vertex id ， data 为 Edge data

lEdgeTable(pid, src, dst, data) ：pid 为 Partion id ， src 为原定点 id ， dst 为目的顶点 id

lRoutingTable(id, pid) ：id 为 Vertex id ， pid 为 Partion id