1. 基本的框架

论文地址: https://amplab.cs.berkeley.edu/wp-content/uploads/2014/09/graphx.pdf

论文是基于Spark 0.9版本做的, 所以有一些细节会和1.6.0以及2.4.0不太一样.

GraphX

GraphX参考了CMU的GAS模型来做计算部分, 然后把整个计算模型放在Spark上进行运行. 从之前的介绍我们知道, CMU核心的提升在GAS操作和Vertex Split两个点上

2. GAS的模拟, 这里贴了个论文slider里的原文

• Gather: the groupBy stage gathers messages destined to the same
  vertex.
• Apply: an intervening map operation applies the message sum to
  update the vertex property.
• Scatter: the join stage scatters the new vertex property to all
  adjacent vertices.

3. 程序部分的模型

3.1 Property Table

GraphX用Vertex RDD 和Edge RDD的概念来表现一张图. 在RDD里, key是vertex, edge. value是用于计算的属性, 如果一个计算完全用不到property, graphx会抛弃掉value部分以压缩存储. GraphX甚至会分析计算过程的字节码, 只把那些计算过程用的到的Property读到内存里, 这也是GraphX论文中一个重要的优化点.

Property Table

3.2 Triplets

在GraphX中使用一个矩阵来表示一个图的结构, 这是一个三元结构.

Triplets

有了这个三元表之后, 就可以用SQL来模拟很多的图操作

CREATE VIEW triplets AS
SELECT s.Id, d.Id, s.P, e.P, d.P
FROM edges AS e
JOIN vertices AS s JOIN vertices AS d
ON e.srcId = s.Id AND e.dstId = d.Id

生成Triplets

SELECT t.dstId, 0.15+0.85*sum(t.srcP*t.eP)
FROM triplets AS t GROUP BY t.dstId

PageRank中一轮迭代

GraphX对图计算中每一轮的建模就建立在这样的Triplets表的SQL里, 图本身就可以表现成一个表, 然后每一轮迭代被模拟成一个对表的SQL操作.

4. 图的数据建模部分

GraphX也是采用了vertex cut的策略来分散一个图

4.1 分布式图

Distribution Graph

• vertex collection
  在RDD的基础之上, 每个parition会维护一个vertexId到Partition的映射表, 这样在做join操作的时候可以更快. 同时还会维护一个bitmask表来表示这个点是否visible从而快速的从整个图中删除点以及重用点

• edge collection
  通过2D hash partitioner算法, spark把一个图快速的进行vertex cut. 然后GraphX通过CSR(稀疏矩阵存储法)来保存一个Routing表, 存储edge(以及它关联的vertex) 到 parition 的对应关系, 这样就可以快速的检索每个edge在哪个partition里