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实现图模型性能能够大幅提高的主要原因