GraphX 介绍&简单样例

一、总体框架

image.gif

总体框架分为三个部分：

l 存储层和原语层：Graph类是图计算的核心类，内部含有VertextRDD、EdgeRDD、RDD[EdgeTriplet]引用；GraphImpl是Graph紫烈，实现图操作；

l 接口层：在底层RDD的基础上实现Pregel模型，BSP模式的计算接口；

l 算法层：基于Pregel接口实现了常用的图算法。

二、BSP是什么

BSP全称Bulk Synchronous Parallel，即整体同步并行。

BSP中，一次计算过程是由一系列全局超步组成，每个超步由并发计算、通信和同步三个步骤组成。

image.gif

每个超步包括三个阶段：

• 本地计算阶段，每个处理器值对本地内存的数据计算

• 全局通信阶段，对任何非本地数据进行操作

• 栅栏同步阶段，等待所有通信行为的结束

image.gif

总结BSP模型有如下特点：

• 计算划分为超步集合，有效避免死锁

• 计算和通信分开，简化了网络拓扑和通信协议

• 采用障碍同步方式，所有进程需要等待其他进程都完成计算

三、底层存储

A、数据存储结构（点分割）

1、vertexTable(id,data)：id为顶点id，data为顶点属性

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

3、routingTable(id,pid)：id为顶点id，pid为分区id

image.gif

B、内部索引结构（大概意思就是建立索引，在图结构发生变化时，不需要改变RDD数据，只需要改变索引结构即可。这也是graphx高性能的一个重要原因）

1、data：存储当前分区所有边的attr属性数组；

2、vertexAttrs：存储顶点的数组。

3、index：相同srcId第一次出现的srcId及其下标；

4、global2local：spark私有的Map数据结构GraphXPrimitiveKyeOpenHashMap，保存vertexId和本地索引的映射关系。其中包含当前partition中所有srcId、dstId与本地索引的映射关系；

5、localSrcIds/localDstIds：global2local.changeValue()返回的本地索引，global是顶点的实际ID，其对应的索引称为local；

6、local2global：记录所有的vertextId数组。其中会包含相同的ID。

使用过程：

1、根据本地下标取vertexId：localSrcIds/localDstIds->index->local2global->VertextId

2、根据vertextId取本地下标&属性：VertextId->global2local->index->data->attr object

四、分区策略及数据更新

A、分区策略

共4种分区方式

1、RandomVertexCut：根据srcId和dstId进行hash后分区；

image.gif

2、CanonicalRandomVertexCut：与RandomVertexCut类似，但会将两个顶点之间的所有边在同一个分区（如，有向图1->2，2<-1，则这两条边会分到同一个分区）；

image.gif

3、EdgePartition1D分区：根据srcId进行分配，一个顶点连接的所有边都存储在一个分区，存在超级节点问题（某节点几乎连接了所有边）；graphx默认分区方式；

image.gif

4、EdgePartition2D分区：整个图看成一个系数矩阵。行号根据dstId获得，列号根据srcId获得。源码中乘以一个较大的素数是为了减缓分区不平衡的问题。

image.gif

B、数据更新机制

如图所示，一个拥有6个顶点的图被划分成了3个分区。顶点RDD、边RDD、路由表如图所示：

image.gif

graphx会根据路右边从顶点RDD中生成与边RDD分区相对应的重复顶点视图（ReplicatedVertextView），它的作用是作为中间RDD，将顶点数据传送至边RDD分区。

重复顶点视图与边RDD进行拉链（zipPartition）操作。即，将点数据赋值到边RDD中形成triplet三元组。分区内部更新顶点数据，同时随着迭代次数的增加，需要更新的顶点在减少，因此集群中数据移动的量也会相应减少。

重复顶点视图有四种模式：bothAttr（src和dst都要）、srcAttrOnly（只要src）、destAttrOnly（只要dst）、noAttr（不需要顶点数据）。

image.gif

五、Pregel API介绍

A、核心函数

1、节点处理消息函数：vprog

2、节点发送信息函数：sendMsg

3、消息合并函数：mergeMsg

B、详细介绍

1、vprog:(VertextId, VD, A) => VD表示 (节点id, 节点属性, 消息) => 节点属性。作用是接受消息，并进行处理，根据处理结果更新节点属性；

2、sendMsg:EdgeTriplet[VD, ED] => Iterrator[(VertextId, A)]表示(边三元组) => Iterator[(目标节点Id, 消息)]。其作用是根据所定义的标准，判断是否向邻接点发送信息，如果条件满足，则发送Iterator[(目标节点, 消息)]；否则发送Iterator.empty。

3、mergeMsg:(A, A) => A表示(消息, 消息) => 消息。作用是，由于途中每一个节点可能有多个邻接点，该函数将接收到的多个信息进行合并处理。

C、举例讲解

题目：计算出指定ID的二跳邻居有哪些？

测试代码如下（求解ID==1的顶点的二跳邻居）：分别定义了vertextProgram、sendMsg、mergeMsg三个核心功能函数。

image.gif

画图展示具体执行过程：

1、原始图

image.gif

2、经过第一轮迭代

image.gif

3、经过第二轮迭代

image.gif

4、最终结果

1的二跳邻居分别是3和5

六、与图数据库的关系（如neo4j）

1、针对简单查询（如，指定顶点的N度关系人）或简单的图可视化，可以使用neo4j

2、若OLTP类的任务，则neo4j更适合

3、若做挖掘更多，则graphx更适合。因为graphx提供了pregel通用编程接口。而neo4j除了自带的算法，其他情况就得完全自己去写代码实现了，更加复杂

七、GraphX提供的常用算法及可能的应用场景

1、PageRank

做什么：估计当前节点对其相邻节点的重要性，然后再从其邻居那里获得节点的重要性。一个节点的排名来源于其传递链接的数量和质量。PageRank虽然被谷歌抛弃了，但它还是被广泛认为是检测任何网络中有影响力的节点的常用方式。

可能的应用场景：用于广告投放或者给用户打标签。如，1000个人微博里关注了一个影响值很高的博客，而该博主是美食博主，则可以给关注用户推送美食广告，或者给关注用户加上美食标签。

2、LabelPropagation

做什么：基于邻域多数的标签作为推断集群的手段。这种极其快速的图形分割需要很少的先验信息，并且被广泛地应用于大规模的社区检测网络中。这是理解图组织的一个关键方法，通常是其他分析的主要步骤。

可能的应用场景：社区发现

3、StronglyConnectedComponents

做什么：定位节点组，其中每个节点可从同一组中的所有其他节点按照关系的方向到达，常被应用于深度优先算法。

可能的应用场景：在零售推荐中，它有助于识别具有强亲和性的组，然后将向那些尚未购买商品的群体推荐首选商品。

4、ShortestPaths

做什么：计算节点与所有其他节点之间的路径，以及其与所有其他节点的总和值(成本，距离，时间或容量等关系的权重)并得出总和最小。

可能的应用场景****：在可用数据维度较少的情况下，可以获取用户的K近邻。如，只有用户之间交互数据，则可构建用户间的交互图，计算与目标用户交互最频繁的K个其他用户。

5、TriangleCount

做什么：一种社区分析算法，它被用于确定经过图中每个节点的三角形的数量。如果一个节点有两个相邻节点而且这两个相邻节点之间有一条边，那么该节点是三角形的一部分。三角形是一个三节点的子图，其中每两个节点是相连的。算法返回一个图对象，我们可以从它上面提取节点。

可能的应用场景****：大量地用于社交网络分析中。它提供了衡量图数据聚类分析的方法，这对在社交网站（如LinkedIn 或Facebook）中寻找社区和度量区域群落的粘度很有用。Clustering Coefficient 是社交网络中的一个重要的度量标准，它显示了一个节点周围的社区之间的紧密程度。