GraphX介绍

1 GraphX的优势

  GraphX是一个新的Spark API，它用于图和分布式图(graph-parallel)的计算。GraphX通过引入弹性分布式属性图（Resilient Distributed Property Graph）：
顶点和边均有属性的有向多重图，来扩展Spark RDD。为了支持图计算，GraphX开发了一组基本的功能操作以及一个优化过的Pregel API。另外，GraphX包含了一个快速增长的图算法和图builders的
集合，用以简化图分析任务。

  从社交网络到语言建模，不断增长的规模以及图形数据的重要性已经推动了许多新的分布式图系统（如Giraph和GraphLab）的发展。
通过限制计算类型以及引入新的技术来切分和分配图，这些系统可以高效地执行复杂的图形算法，比一般的分布式数据计算（data-parallel，如spark、MapReduce）快很多。

2.1

  分布式图（graph-parallel）计算和分布式数据（data-parallel）计算类似，分布式数据计算采用了一种record-centric的集合视图，而分布式图计算采用了一种vertex-centric的图视图。
分布式数据计算通过同时处理独立的数据来获得并发的目的，分布式图计算则是通过对图数据进行分区（即切分）来获得并发的目的。更准确的说，分布式图计算递归地定义特征的转换函数（这种转换函数作用于邻居特征），通过并发地执行这些转换函数来获得并发的目的。

  分布式图计算比分布式数据计算更适合图的处理，但是在典型的图处理流水线中，它并不能很好地处理所有操作。例如，虽然分布式图系统可以很好的计算PageRank以及label diffusion，但是它们不适合从不同的数据源构建图或者跨过多个图计算特征。
更准确的说，分布式图系统提供的更窄的计算视图无法处理那些构建和转换图结构以及跨越多个图的需求。分布式图系统中无法提供的这些操作需要数据在图本体之上移动并且需要一个图层面而不是单独的顶点或边层面的计算视图。例如，我们可能想限制我们的分析到几个子图上，然后比较结果。
这不仅需要改变图结构，还需要跨多个图计算。

2.2

  我们如何处理数据取决于我们的目标，有时同一原始数据可能会处理成许多不同表和图的视图，并且图和表之间经常需要能够相互移动。如下图所示：

2.3

  所以我们的图流水线必须通过组合graph-parallel和data- parallel来实现。但是这种组合必然会导致大量的数据移动以及数据复制，同时这样的系统也非常复杂。
例如，在传统的图计算流水线中，在Table View视图下，可能需要Spark或者Hadoop的支持，在Graph View这种视图下，可能需要Prege或者GraphLab的支持。也就是把图和表分在不同的系统中分别处理。
不同系统之间数据的移动和通信会成为很大的负担。

  GraphX项目将graph-parallel和data-parallel统一到一个系统中，并提供了一个唯一的组合API。GraphX允许用户把数据当做一个图和一个集合（RDD），而不需要数据移动或者复制。也就是说GraphX统一了Graph View和Table View，
可以非常轻松的做pipeline操作。

2 弹性分布式属性图

  GraphX的核心抽象是弹性分布式属性图，它是一个有向多重图，带有连接到每个顶点和边的用户定义的对象。
有向多重图中多个并行的边共享相同的源和目的顶点。支持并行边的能力简化了建模场景，相同的顶点可能存在多种关系(例如co-worker和friend)。
每个顶点用一个唯一的64位长的标识符（VertexID）作为key。GraphX并没有对顶点标识强加任何排序。同样，边拥有相应的源和目的顶点标识符。

  属性图扩展了Spark RDD的抽象，有Table和Graph两种视图，但是只需要一份物理存储。两种视图都有自己独有的操作符，从而使我们同时获得了操作的灵活性和执行的高效率。
属性图以vertex(VD)和edge(ED)类型作为参数类型，这些类型分别是顶点和边相关联的对象的类型。

  在某些情况下，在同样的图中，我们可能希望拥有不同属性类型的顶点。这可以通过继承完成。例如，将用户和产品建模成一个二分图，我们可以用如下方式：

  1. class VertexProperty()
  2. case class UserProperty(val name: String) extends VertexProperty
  3. case class ProductProperty(val name: String, val price: Double) extends VertexProperty
  4. // The graph might then have the type:
  5. var graph: Graph[VertexProperty, String] = null

  和RDD一样，属性图是不可变的、分布式的、容错的。图的值或者结构的改变需要生成一个新的图来实现。注意，原始图中不受影响的部分都可以在新图中重用，用来减少存储的成本。
执行者使用一系列顶点分区方法来对图进行分区。如RDD一样，图的每个分区可以在发生故障的情况下被重新创建在不同的机器上。

  逻辑上,属性图对应于一对类型化的集合(RDD),这个集合包含每一个顶点和边的属性。因此，图的类中包含访问图中顶点和边的成员变量。

  1. class Graph[VD, ED] {
  2.   val vertices: VertexRDD[VD]
  3.   val edges: EdgeRDD[ED]
  4. }

  VertexRDD[VD]和EdgeRDD[ED]类是RDD[(VertexID, VD)]和RDD[Edge[ED]]的继承和优化版本。VertexRDD[VD]和EdgeRDD[ED]都提供了额外的图计算功能并提供内部优化功能。

  1. abstract class VertexRDD[VD](
  2.     sc: SparkContext,
  3.     deps: Seq[Dependency[_]]) extends RDD[(VertexId, VD)](sc, deps) 
  5. abstract class EdgeRDD[ED](
  6.     sc: SparkContext,
  7.     deps: Seq[Dependency[_]]) extends RDD[Edge[ED]](sc, deps)

3 GraphX的图存储模式

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

  • VertexTable(id, data)：id为顶点id， data为顶点属性

  • EdgeTable(pid, src, dst, data)：pid 为分区id ，src为源顶点id ，dst为目的顶点id，data为边属性

  • RoutingTable(id, pid)：id 为顶点id ，pid 为分区id

  点分割存储实现如下图所示：

2.3

  在后文的图构建部分，我们会详细介绍这三个部分。

4 GraphX底层设计的核心点

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

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

  • 3 图的分布式存储采用点分割模式，而且使用partitionBy方法，由用户指定不同的划分策略。下一章会具体讲到划分策略。

5 参考文献

【1】spark graphx参考文献

【2】快刀初试：Spark GraphX在淘宝的实践

【3】GraphX: Unifying Data-Parallel and Graph-Parallel