GraphX分布式存储

GraphX分布式存储

GraphX将图数据以RDD分布式地存储在集群的节点上，使用顶点RDD（VertexRDD）、边RDD（EdgeRDD）存储顶点集合和边集合。
顶点RDD通过按顶点的ID进行哈希分区，将顶点数据以多分区形式分布在集群上。边RDD按指定的分区策略（Partition Strategy）进行分区（默认使用边的srcId进行哈希分区），将边数据以多分区形式分布在集群上。另外，顶点RDD中还拥有顶点到边RDD分区的路由信息——路由表。路由表存在顶点RDD的分区中，它记录分区内顶点跟所有边RDD分区的关系。在边RDD需要顶点数据时（如构造边三元组），顶点RDD会根据路由表把顶点数据发送至边RDD分区。如图 5所示，按顶点分割方法将图分解后得到顶点RDD、边RDD和路由表（注意，此处RDD未按分区函数分区）。

在图计算过程中，有些边的计算需要顶点数据，即需形成边三元组视图，如PageRank算法生出边的权值，这需要将顶点的权值发送至出边所在的边RDD分区。GraphX依据路由表，从顶点RDD中生成与边RDD分区相对应的重复顶点视图（ReplicatedVertexView），它的作用是作为中间RDD，将顶点数据传送至边RDD分区。重复顶点视图按边RDD分区并携带顶点数据的RDD，如图 6所示，顶点分区A中便携带边RDD分区A中的所有的顶点，它与边RDD中的顶点是co-partition（即分区个数相同，且分区方法相同）。在图计算时，GraphX将重复顶点视图和边RDD进行拉链（zipPartition）操作，即将重复顶点视图和边RDD的分区一一对应地组合起来，从而将边与顶点数据连接起来，使边分区拥有顶点数据。整个形成边三元组过程，只有在顶点RDD形成重复顶点视图中存在分区间数据移动，拉链操作不需要移动顶点数据和边数据。由于顶点数据一般比边数据要少的多，而且随着迭代次数的增加，需要更新的顶点数目也越来越少，重复顶点视图中携带的顶点数据也相应减少，这样就可以大大减少数据的移动量，加快执行速度。
GraphX在顶点RDD和边RDD的分区中以数组形式存储顶点数据和边数据，目的是为了不损失元素访问性能。GraphX在分区里建立了众多索引结构，高效地实现快速访问顶点数据或边数据。在迭代过程中，图的结构不会发生变化，因而顶点RDD、边RDD以及重复顶点视图中的索引结构全部可以重用，当由一个图生成另一个图时，只须更新顶点RDD和RDD的数据存储数组。索引结构的重用，是GraphX保持高性能的关键，也是相对于原生RDD实现图模型性能能够大幅提高的主要原因