Spark入门实战系列—9.Spark图计算GraphX介绍及实例
http://www.cnblogs.com/shishanyuan/p/4747793.html

1 GraphX介绍

GraphX可以认为是GraphLab(C++)和Pregel(C++)在Spark(Scala)上的重写及优化
GraphX可以提供一种Table View和一种Graph View
GraphX的核心抽象是Resilient Distributed Property Graph，一种点和边都带属性的有向多重图。
它扩展了Spark RDD的抽象，有Table和Graph两种视图，而只需要一份物理存储。
两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。
Graphx大部分的实现，都是围绕Partition的优化进行的。这在某种程度上说明了点分割的存储和相应的计算优化，是图计算框架的重点和难点。

  • 优点：

引入弹性分布式属性图来扩展Spark RDD，支持分布式属性图计算
能与Spark框架上的组件无缝集成

  • 缺点：

邻居数较多的顶点通信量大，计算容易假死或崩溃
整体同步并行，导致计算快的worker长期等待

2 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转换过程中是共用的，降低了计算和存储开销。

3 存储模式

  • 2013年GraphLab将存储方式从边分割变成点分割，在性能上获得重大提升，目前被业界广泛接受并采用。

  • GraphX的图数据存储

  • 点切割：以边为中心，每个边只保存一次，每条边只出现在一台机器上，切割后的点会被保存到不同的机器上

  • 边切割：以点为中心，每个点只保存一次，切断后的边保存到多台机器上

    点分割：每个边仅存储一次，邻居多的点(热点)将被复制到多台机器上，增加了存储开销和数据同步开销 好处：可以大大减少内网通信量，解决热点问题。

边分割：好处是每个顶点仅存储一次，节省了存储空间。坏处是对于分到不同机器上的边来说，需要跨机器传输数据，内网通信量大 需求：设法解决cut-edge的问题，减少其存在，即将遍历的相邻节点放在相同分区，减少通信消耗

JanusGraph 目前貌似是边分割？
两种分割方式，目前点分割占上风。

  • GraphX的图切分策略

    图切分策略指：如何将图切分成不同的分区进行存储

    • EdgePartition1D
    • EdgePartition2D
    • RandomVertexCut
    • CanonicalRandomVertexCut

      4 计算模式

      基于BSP计算模式
      Graphx中的Pregel，其实并不严格遵循Pregel，它是一个参考GAS改进的Pregel，可以综合Pregel和GAS的好处

      疑问：这里的切分策略，怎么又有边切分了？？

  1. val pregelGraph = Pregel(ccGraph, initialMessage,
  2. maxIterations, EdgeDirection.Either)(
  3. vprog = (id, attr, msg) => math.min(attr, msg),
  4. sendMsg = sendMessage,
  5. mergeMsg = (a, b) => math.min(a, b))

Pregel函数的大致流程？
vprog 并行地在所有接受到消息的节点上运行
sendMsg 对当前迭代中接收到数据的点的出边进行操作，产生消息。
mergeMsg 对流入同一个点的消息，进行合并
defaultValue—>vprog—>sendMsg—>mergeMsg —>vprog—>sendMsg—>mergeMsg —>vprog，然后再发送消息，再循环？

  • _@_param activeDirection the direction of edges incident to a vertex that received a message in
  • the previous round on which to run sendMsg. For example, if this is EdgeDirection.Out, only
  • out-edges of vertices that received a message in the previous round will run. The default is
  • EdgeDirection.Either, which will run sendMsg on edges where either side received a message
  • in the previous round. If this is EdgeDirection.Both, sendMsg will only run on edges where
  • both vertices received a message.

EdgeDirection.Out 上一轮接收到消息点的出边才会执行sendMsg
EdgeDirection.Either 上一轮该边的两点，有一个点接收到消息，就会对该边执行sendMsg
EdgeDirection.Both 上一轮该边的两点，两点同时接收到消息，才会对该边执行sendMsg