GraphX

Spark GraphX是一个分布式图处理框架，基于Spark，提供对图计算和图挖掘简洁、易用、丰富接口，极大的方便了对分布式图处理的需求。GraphX的特点是离线批量处理，基于同步的BSP模型（Bulk Synchronous Parallel Computing Model，整体同步并行计算模型），优势在于可以提升数据处理的吞吐量和规模。GraphX核心抽象是弹性分布式属性图（Resilient Distribute Property Graph）,一种点和边都带有属性的有向多重图。在逻辑上，图计算等价于一系列RDD的转换。具备了RDD的3个关键特性：Immutable、Distributed和Fault-Tolerant。

Graph也包含一个三元组视图，逻辑上将顶点和边的属性保存为一个RDD[EdgeTriplet[VD, ED]]。
下面的SQL表达式表示这个连接。

1
2
3
4
5
SELECT src.id, dst.id, src.attr, e.attr, dst.attr

FROM edges AS e LEFT JOIN vertices AS src, vertices AS dst

ON e.srcId = src.Id AND e.dstId = dst.Id

GraphFrame 是类似于 Spark 的 GraphX 库，支持图处理。但 GraphFrame 建立在 Spark DataFrame 之上，具有以下重要的优势：

支持 Scala ，Java 和 Python API：GraphFrame 提供统一的三种编程语言 APIs.

方便、简单的图查询：GraphFrame 允许用户使用 Spark SQL 和 DataFrame 的 API 查询

支持导出和导入图：GraphFrame 支持 DataFrame 数据源，使得可以读取和写入多种格式的图，比如，Parquet、JSON 和 CSV 格式。

备用：

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

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

Graphx 使用的是Vertex-Cut(点分割)方式存储图，

Bulk Synchronous Parallell，即整体同步并行，它将计算分成一系列的超步（superstep）的迭代（iteration）。从纵向上看，它是一个串行模式，而从横向上看，它是一个并行的模式，每两个superstep之间设置一个栅栏（barrier），即整体同步点，确定所有并行的计算都完成后再启动下一轮superstep。

属性图对应一对类型化的集合RDD，包含了每一个顶点和边属性。

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

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

存储层和原语层: Graph类是图计算的核心类，内部含有VertexRDD、EdgeRDD和RDD[EdgeTriplet].

SQL

ConstantFolding

ConstantPropagation

ReorderAssociativeOperator

OptimizeIn

RDD

A Resilient Distributed Dataset, the basic abstraction in Spark.

Represents an immutable, partitioned collection of elements that can be operated on in parallel.

DataSource

The main class responsible for representing a pluggable Data Source in Spark SQL.

In addition to acting as the canonical set of parameters that can describe a Data Source, this class is used to resolve a description to a concrete implementation that can be used in a query plan or to write out data using an external library.

reference :

  1. Spark入门实战系列–9.Spark图计算GraphX介绍及实例