GraphX 图数据建模和存储

简介:

背景

简单分析一下GraphX是怎么为图数据建模和存储的。

入口

可以看GraphLoader的函数,

def edgeListFile(
      sc: SparkContext,
      path: String,
      canonicalOrientation: Boolean = false,
      numEdgePartitions: Int = -1,
      edgeStorageLevel: StorageLevel = StorageLevel.MEMORY_ONLY,
      vertexStorageLevel: StorageLevel = StorageLevel.MEMORY_ONLY)
    : Graph[Int, Int]
  1. path可以是本地路径(文件或文件夹),也可以是hdfs路径,本质上是使用sc.textFile来生成HadoopRDD的,numEdgePartitions是分区数。
  2. Graph的存储是分EdgeRDD和VertexRDD两块,可以分别设置StorageLevel。默认是内存。
  3. 这个函数接受边文件,即’1 2’, ‘4 1’这样的点到点的数据对组成的文件。把这份文件按分区数和存储level转化成一个可以操作的图。

流程

  1. sc.textFile读文件,生成原始的RDD
  2. 每个分区(的计算节点)把每条记录放进PrimitiveVector里,这个结构是spark里为primitive数据优化的存储结构。
  3. PrimitiveVector里的数据一条条取出,转化成EdgePartition,即EdgeRDD的分区实现。这个过程中生成了面向列存的结构:src点的array,dst点的array,edge的属性array,以及两个正反向map(用于对应点的local id和global id)。
  4. EdgeRDD 做一次count触发这次边建模任务,真正persist起来。
  5. EdgePartition去生成一个RoutingTablePartition,里面是vertexId到partitionId的对应关系,借助RoutingTablePartition生成VertexRDD
  6. EdgeRDDVertexRDD生成Graph。前者维护了边的属性、边两头顶点的属性、两头顶点各自的global vertexID、两头顶点各自的local Id(在一个edge分区里的array index)、用于寻址array的正反向map。后者维护了点存在于哪个边的分区上的Map。

以下是代码,比较清晰地展现了内部存储结构。

private[graphx]
class EdgePartition[
    @specialized(Char, Int, Boolean, Byte, Long, Float, Double) ED: ClassTag, VD: ClassTag](
    localSrcIds: Array[Int],
    localDstIds: Array[Int],
    data: Array[ED],
    index: GraphXPrimitiveKeyOpenHashMap[VertexId, Int],
    global2local: GraphXPrimitiveKeyOpenHashMap[VertexId, Int],
    local2global: Array[VertexId],
    vertexAttrs: Array[VD],
    activeSet: Option[VertexSet])
  extends Serializable {
/**
 * Stores the locations of edge-partition join sites for each vertex attribute in a particular
 * vertex partition. This provides routing information for shipping vertex attributes to edge
 * partitions.
 */
private[graphx]
class RoutingTablePartition(
    private val routingTable: Array[(Array[VertexId], BitSet, BitSet)]) extends Serializable {

细节

分区摆放

EdgeRDD的分区怎么切分的呢?因为数据是根据HadoopRDD从文件里根据offset扫出来的。可以理解为对边数据的切分是没有任何处理的,因为文件也没有特殊排列过,所以切分成多少个分区应该就是随机的。

VertexRDD的分区怎么切分的呢?EdgeRDD生成的vertexIdToPartitionId这份RDD数据是RDD[VertexId, Int]型,它根据hash分区规则,分成和EdgeRDD分区数一样大。所以VertexRDD的分区数和Edge一样,分区规则是Long取hash。

所以我可以想象的计算过程是:

对点操作的时候,首先对vertexId(是个Long)进行hash,找到对应分区的位置,在这个分区上,如果是内存存储的VertexRDD,那很快可以查到它的边所在的几个Edge分区的所在位置,然后把计算分到这几个Edge所在的分区上去计算。
第一步根据点hash后找边分区位置的过程就类似一次建好索引的查询。

配官方图方面理解:
这里写图片描述

高效数据结构

对原生类型的存储和读写有比较好的数据结构支持,典型的是EdgePartition里使用的map:

/**
 * A fast hash map implementation for primitive, non-null keys. This hash map supports
 * insertions and updates, but not deletions. This map is about an order of magnitude
 * faster than java.util.HashMap, while using much less space overhead.
 *
 * Under the hood, it uses our OpenHashSet implementation.
 */
private[graphx]
class GraphXPrimitiveKeyOpenHashMap[@specialized(Long, Int) K: ClassTag,
                              @specialized(Long, Int, Double) V: ClassTag](

以及之前提到的vector

/**
 * An append-only, non-threadsafe, array-backed vector that is optimized for primitive types.
 */
private[spark]
class PrimitiveVector[@specialized(Long, Int, Double) V: ClassTag](initialSize: Int = 64) {
  private var _numElements = 0
  private var _array: Array[V] = _

全文完 :)

目录
相关文章
|
6月前
|
SQL 存储 NoSQL
GQL图查询语言:高效处理复杂图数据
GQL是一种新型的查询语言,它可以处理复杂图数据,以提供比传统 SQL更快、更高效的查询方式。GQL图查询语言具有可扩展性,可以使用最少的编程知识来访问图数据库。在本文中,我们将探讨 GQL的概念和实际使用案例。同时,我们还将提供一些 GQL的示例代码,以帮助您更好地了解和应用 GQL。
|
存储 数据挖掘 关系型数据库
数仓学习---6、数据仓库概述、 数据仓库建模概述、维度建模理论之事实表、维度建模理论之维度表
数仓学习---6、数据仓库概述、 数据仓库建模概述、维度建模理论之事实表、维度建模理论之维度表
|
存储 分布式计算 MaxCompute
基于MaxCompute的图计算实践分享-图加载过程
一、前言 MaxCompute Graph 是基于飞天平台实现的面向迭代的图处理框架,为用户提供了类似于 Pregel 的编程接口。MaxCompute Graph(以下简称 Graph )作业包含图加载和计算两个阶段: 加载,将存储在表中的数据载入到内存中,以点和边的形式存在;
6007 1
|
分布式计算 算法 NoSQL
GraphX 在图数据库 Nebula Graph 的图计算实践
不同来源的异构数据间存在着千丝万缕的关联,这种数据之间隐藏的关联关系和网络结构特性对于数据分析至关重要,图计算就是以图作为数据模型来表达问题并予以解决的过程。
819 0
GraphX 在图数据库 Nebula Graph 的图计算实践
GraphScope 图分析引擎 - GRAPE 介绍
GraphScope 中的图分析引擎继承自 GRAPE,该系统实现了论文 Parallelizing Sequential Graph Computations 中提出的不动点计算模型
|
机器学习/深度学习 数据采集 SQL
|
分布式计算 大数据 Java
Graphx处理janusGraph数据实现
Graphx处理janusGraph数据实现
3486 0
|
分布式计算 大数据 API
基于MaxCompute的图计算实践分享-Aggregator机制介绍
Aggregator是MaxCompute-GRAPH作业中常用的feature之一,特别是解决机器学习问题时。MaxCompute-GRAPH中Aggregator用于汇总并处理全局信息。本文将详细介绍的Aggregator的执行机制、相关API,并以Kmeans Clustering为例子说明Aggregator的具体用法。
4434 0
BI领域的分析利器交叉表使用详解
交叉表是在BI分析场景中使用占比最多的分析利器。通过交叉表对数据的承载和管理,用户可以一目了然地分析出各种场景指标以及对比,帮助用户作出决策。
1306 0
|
数据可视化 数据安全/隐私保护 自然语言处理