精华内容
下载资源
问答
  • 图计算
    千次阅读
    2019-03-30 17:30:08

    图计算学习

    本文总结自AMiner《图计算研究报告》

    概述

    图计算定义

    图(Graph)是一种重要的数据结构,它由节点 V V V(或称为顶点,即个体) ,与边 E E E(即个体之间的联系)构成,我们一般将图表示为 G ( V , E ) G(V,E) GVE 。图数据的典型例子有网页链接关系、社交网络、商品推荐等。

    图计算系统中最基础的数据结构由顶点 V V V(或节点)、边 E E E、权重 D D D 这三因素组成,即 G = ( V , E , D ) G=(V,E,D) G=(VED),其中 V V V 为顶点(vertex), E E E 为边(edge), D D D 为权重(data)。

    图计算的特征

    图数据结构很好地表达了数据之间的关联性, 关联性计算是大数据计算的核心——通过获得数据的关联性, 可以从噪音很多的海量数据中抽取有用的信息。 图计算技术解决了传统的计算模式下关联查询的效率低、 成本高的问题,在问题域中对关系进行了完整的刻画,并且具有丰富、高效和敏捷的数据分析能力,其特征有如下三点:

    • 基于图抽象的数据模型

      图计算系统将图结构化数据表示为属性图,它将用户定义的属性与每个顶点和边缘相关联。属性可以包括元数据(例如,用户简档和时间戳)和程序状态(例如顶点的PageRank或相关的亲和度)。源自社交网络和网络图等自然现象的属性图通常具有高度偏斜的幂律度分布和比顶点更多的边数。

    • 图数据模型并行抽象

      图的经典算法中,从PageRank到潜在因子分析算法都是基于相邻顶点和边的属性迭代地变换顶点属性,这种迭代局部变换的常见模式形成了图并行抽象的基础。在图并行抽象中,用户定义的顶点程序同时为每个顶点实现,并通过消息(例如Pregel)或共享状态(例如PowerGraph)与相邻顶点程序交互。每个顶点程序都可以读取和修改其顶点属性,在某些情况下可以读取和修改相邻的顶点属性。

    • 图模型系统优化

      对图数据模型进行抽象和对稀疏图模型结构进行限制,使一系列重要的系统得到了优化。比如 GraphLab 的 GAS 模型更偏向共享内存风格,允许用户的自定义函数访问当前顶点的整个邻域,可抽象成 Gather、Apply 和 Scatter 三个阶段。GAS模式的设计主要是为了适应点分割的图存储模式, 从而避免 Pregel 模型对于邻域很多的顶点、 需要处理的消息非常庞大时会发生的假死或崩溃问题。

    常用技术

    图算法

    • 遍历算法

      图的遍历的复杂性主要表现在以下四个方面:

      1. 在图结构中,没有一个明显的首结点,图中任意一个顶点都可作为第一个被访问的结点,所以要提供首结点。
      2. 在非连通图中,从一个顶点出发,只能够访问它所在的连通分量上的所有顶点,因此,还需考虑如何选取下一个出发点,以访问图中其余的连通分量。
      3. 在图结构中, 可能有回路存在, 那么一个顶点被访问之后, 有可能沿回路又回到该顶点, 在访问之前, 需要判断结点是否已经被访问过。
      4. 在图结构中,一个顶点可以和其它多个顶点相连, 当这样的顶点访问过后,存在如何选取下一个要访问的顶点的问题。
    • 社区发现(Community Detection)

      社区发现算法是用来发现网络中的社区结构,也可以看做是一种聚类算法。 社区发现算法可以用来发现社交网络中三角形的个数(圈子),可以分析出哪些圈子更稳固,关系更紧密,用来衡量社群耦合关系的紧密程度。从一个人的社交圈子里面可以看出,三角形个数越多,说明他的社交关系越稳固、紧密。

    • PageRank

      PageRank源自搜索引擎,用来解决链接分析中网页排名的问题。它是搜索引擎里面非常重要的图算法,可用来对网页做排序。

    • 最短路径

      最短路径用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

    图数据计算模型

    图计算模型即针对图数据和图计算特点设计的计算模型,一般应用于图计算系统中。与传统计算模型相比,图计算模型主要针对解决以下问题:

    1. 图计算的频繁迭代带来的读写数据等待和通信开销大的问题;
    2. 图算法对节点和边的邻居信息的计算依赖问题;
    3. 图数据的复杂结构使得图算法难以实现分布不均匀的分块上并行计算的问题。

    屏幕快照 2019-03-27 09.52.38.png

    • 节点中心计算模型

      将图算法细粒度划分为每个节点上的计算操作,节点中心模型将频繁迭代的全局计算转换成多次超步运算,且所有节点独立的并行执行计算操作,数据间的依赖关系仅催在于两个相邻超步之间

      • 同步节点计算模型

        将节点分为活跃和不活跃两种状态,节点接收到消息后进行计算,否则置为不活跃状态

      • 异步节点中心计算模型

        计算节点选择性的读取邻居节点的消息并进行计算,根据每个节点可异步读取和更新的关联边和邻居节点的范围又有三种一致性方案.

      • GAS(gather、apply、scatter)节点计算模型

        沿用同步节点中心计算模型中超步的概念,通过划分大都数节点在单个计算节点内实现并行计算

    • 边中心计算模型

      将图算法的迭代计算转换为可在边列表上顺序执行,避免了随机读写数据对内存资源的高要求.

    • 路径中心计算模型

      将图数据组织为前向边遍历树和后向边遍历树,从而将图计算转换为在树上的迭代计算

    • 子图计算模型

      将图算法转换为多个子图上的迭代运算,减少了计算时的通信开销和迭代操作次数

    无标题.png

    图计算系统

    1.png

    • 单机内存图处理系统

      Ligra、Galois、GraphMat、Polymer

    • 单机外存图处理系统

      GraphChi、X-Stream、VENUS、GridGraph

    • 分布式内存图处理系统

      Pregel、Giraph、GraphLab、PowerGraph、GraphX、Gemin

    • 分布式外存图处理系统

      Chaos

    • 面向机器学习的分布式图计算系统

      TuX 2 ^2 2

    图计算中的关键技术

    • 异构计算平台
    • 通信模型
    • 执行模型
      • 同步执行
      • 异步执行
    • 图的划分
    • 负载均衡
    • 容错

    技术挑战

    • 局部性差
    • 数据及图结构驱动的计算
    • 图数据的非结构化特性
    • 高访存/计算比

    高引论文

    • Pregel: a system for large-scale graph processing
    • Distributed GraphLab: a framework for machine learning and data mining in the cloud
    • PowerGraph: distributed graph-parallel computation on natural graphs
    • GraphLab: A New Framework For Parallel Machine Learning.
    • GraphChi: large-scale graph computation on just a PC
    • Graphx: Graph processing in a distributed dataflow framework
    • X-Stream: edge-centric graph processing using streaming partitions
    • Ligra: a lightweight graph processing framework for shared memory
    • PowerLyra: differentiated graph computation and partitioning on skewed graphs
    • GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning
    更多相关内容
  • 1.2 图处理的难点:1.3 图储存方式:(1) 邻接矩阵:(2) 邻接表:(3) 十字链表(有向图):(4) 邻接多重表(无向图):(5) 边集数组(权重图):二、图计算概论:2.1 基本概念:2.2 开源框架:Ligra:Gemini:Plato:...

    如非作者允许,本文禁止转载。

    博主主页:https://blog.csdn.net/weixin_44936889

    一、图结构概论:

    1.1什么是图?

    图 (graph) 具有很强的抽象性与灵活性,相比线性表、层次树等组织方式,图在结构和语义等方面
    具有更强的表示能力,是最常用、最重要的数据结构之一。

    在这里插入图片描述

    正是由于图结构丰富的表现力,现实生活中的诸多应用场景都用图结构表示,例如社交网络、文献网络、交通网络与知识图谱等。因此,依托图计算的应用无处不在,如深度学习、计算机视觉、模式识别、信息检索以及语义 Web 分析等,广泛渗透于经济建设、国防安全、社会生活等诸多重要领域。

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,表示为G(V, E)。其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

    根据E是否有方向,图可以分为有向图和无向图:

    在这里插入图片描述

    根据E是否有权重,图可以分为权重图(网)和非权重图等。

    1.2 图处理的难点:

    图结构处理的于每个顶点的逻辑位置都是相对的,顶点之间的关联依赖也是不确定的,所以无法以数据元素在内存中的物理位置来表示元素之间的关系,即无法用简单的顺序存储结构来表示。

    1.3 图储存方式:

    常见的图储存方式有:

    (1) 邻接矩阵:

    即用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

    如:

    在这里插入图片描述

    可表示为:

    在这里插入图片描述

    (2) 邻接表:

    即将结点存放入数组,对结点的孩子进行链式存储。

    如:

    在这里插入图片描述

    可表示为:

    在这里插入图片描述

    (3) 十字链表(有向图):

    综合邻接表和逆邻接表形式的一种链式存储结构,为了便于求得图中顶点的度(出度和入度)而提出。

    如:

    在这里插入图片描述
    可表示为:
    在这里插入图片描述

    (4) 邻接多重表(无向图):

    在邻接多重表在邻接多重表中,所有依附于同一顶点的边串联在同一链表中,由于每条边依附于两个顶点,则每个边结点同时链接在两个链表中。

    如:

    在这里插入图片描述
    可表示为:
    在这里插入图片描述

    (5) 边集数组(权重图):

    边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息。

    如:
    在这里插入图片描述
    可表示为:
    在这里插入图片描述

    二、图计算概论:

    2.1 基本概念:

    图数据库存储直接从真实世界中获取的数据,按照一定的规则对图数据库中存储的数据进行抽取和转换后,得到的图结构数据将作为输入数据由图处理引擎进行处理。以图计算引擎运行的硬件平台来进行分类,则主要分为三类:

    (1)基于分布式环境的大规模图计算系统
    (2)基于单机的大规模图计算系统
    (3)基于硬件加速器的大规模图计算系统

    由于传统的关系型数据本身存在建模缺陷、水平伸缩等问题,而图数据具有更强大的表达能力,且可以将不同来源、不同类型的数据融合到同一个图里进行分析,得到原本独立分析难以发现的结果,因此,图计算可以广泛地应用在社交网络、推荐系统、网络安全、文本检索和生物医疗等领域。

    2.2 开源框架:

    主要调研了三个分布式框架(Ligra,gemini和plato):

    Ligra:

    Ligra是用于共享内存的轻量级图形处理框架。它特别适用于实现并行图遍历算法,其中在迭代中仅处理一部分顶点。该项目的基本观点是最大的公开可用的现实世界图形都适合共享内存。当图形适合共享内存时,与分布式内存图形处理系统相比,使用Ligra处理图形可以将性能提高多达几个数量级。

    项目地址:https://people.csail.mit.edu/jshun/ligra.shtml

    论文地址:https://www.cs.cmu.edu/~jshun/ligra.pdf

    源码地址:https://github.com/jshun/ligra

    公开视频:https://www.youtube.com/watch?v=W5mDx_G45RQ

    在这里插入图片描述

    Gemini:

    Gemini项目建立的目标是通过减小分布式开销和优化本地计算实现实现一个兼具扩展性和高性能的分布式图计算系统。它的贡献之一是将双模式计算引擎(推动模式和拉动模式)从单机的共享内存扩展到了分布式环境中。并且进一步将两种模式下的计算过程都细分成发送端和接收端两个部分,从而将分布式系统的通信从计算中剥离出来。同时gemini将顶点集进行块式划分,将这些块分配给各个节点,然后让每个顶点的拥有者(即相应节点)维护相应的出边/入边,从而保留了图数据的局部性特点。Gemini 的劣势主要来源于一些不可避免的分布式实现所带来的开销,例如额外的用于消息收发的指令和访存,以及分布式内存环境下慢于共享内存的收敛速度。

    论文地址:https://www.usenix.org/system/files/conference/osdi16/osdi16-zhu.pdf

    源码地址:https://github.com/thu-pacman/GeminiGraph

    公开PPT:https://myslide.cn/slides/3004

    在这里插入图片描述

    Plato:

    Plato继承于gemini,它认为原有的主流图计算开源框架的如果要完成超大规模数据的图计算,需要花费超长的时间或者需要大量的计算资源。而许多真实业务场景要求超大规模图计算必须在有限时间和有限资源内完成。因此Plato致力于提供超大规模图数据的离线图计算和图表示学习。它的特点是计算能力强、内存消耗较小(只选取了Plato与Spark GraphX在PageRank和LPA这两个benchmark算法的性能对比),并且为开发者同时提供了底层API和应用层的接口工具。

    源码地址:https://github.com/Tencent/plato

    在这里插入图片描述

    2.3 图计算的实现:

    图计算实现的主要瓶颈在于承载图结构的数据库能否支持低延迟高吞吐 I/O 并保证数据的完整性,并针对图结构做计算框架的优化,遍历子的实现。

    核心算法包括:

    1. 社区发现、图聚类;

    2. 稠密子图挖掘算法;

    3. 中心性计算算法;

    4. 基础图算法;

    5. 图匹配算法;

    (以下为Plato的核心算法)
    在这里插入图片描述

    2.4 图计算的应用:

    图论中的算法可以直接应用在地理信息系统(GIS)和 建筑信息模型(BIM)上。这些算法都基于广度优先搜索(BFS)和深度优先搜索(DFS):
    在这里插入图片描述

    在这里插入图片描述

    通过图计算模型可以将物联网数据都用图表达,使得复杂关系称为可表达可计算的数据类型:

    在这里插入图片描述

    构建超大型的生物、物理、社会科学仿真:

    在这里插入图片描述

    推荐系统、反欺诈应用等:

    在这里插入图片描述

    总结:

    图计算就是研图计算就是研究如何高效计算、存储并管理大量图数据等问题的方法。

    图计算以一种灵活的抽象方式将不同的人与物连接在一起,为传统数据分析应用提供了一种新的设计和计算方式。未来,随着可获取数据的进一步增多,传统方式难以有效表达和处理各实体间的关系,图计算势必会成为大数据领域一种新的通用计算模型,从而带来巨大的理论和应用创新机遇。

    在这里插入图片描述

    关注我的公众号:

    感兴趣的同学关注我的公众号——可达鸭的深度学习教程:
    在这里插入图片描述

    展开全文
  • SparkGraphX图计算(一)

    千次阅读 2019-09-04 15:28:07
    SparkGraphX图计算(一)一、什么是图二、什么是SparkGraphX三、常见的图算法1、PageRank算法2、最短路径算法3、社群发现4、推荐算法ALS和SVD++四、GraphX数据抽象RDPG五、图基本结构1、GraphX的底层设计2、图数据...

    一、什么是图

    什么是图?图计算都在计算什么?我们可以从社交网络、人物关系挖掘、节点之间依赖计算等方面来理解图计算。首先,图数据存在于我们生活的方方面面,如果将数据相关方分别定位为一个点,而他们之间的互相联系抽象为边,那整个不同事物时间的错综复杂的联系就构成了一幅幅“图数据”。

    社交关系数据:将每个人作为一个点,而人与人之间的互动关系是边,那么庞大的社交圈子中,不同人之间的互动联系就构成了庞大的社交关系数据。

    网页链接数据:通过一个网页链接,可以跳转到其他多个网页,这么一来,网页与网页之间的多个跳转联系就构成了一个复杂的网页链接数据。通过这些数据可以进行多个研究,比如可以分析出来哪个网页是入口大的重要网页等。

    图数据和图计算应用,比如可以通过交易网络数据图来分析出哪些交易是欺诈交易、通过通信网络数据图来分析企业员工之间不正常的社交、通过用户—商品图数据图来分析用户需求,做个性化推荐等。

    二、什么是SparkGraphX

    GraphX官网:http://spark.apache.org/graphx/

    Spark GraphX是一个分布式图处理框架,它是基于Spark平台提供对图计算和图挖掘简洁易用的而丰富的接口,极大的方便了对分布式图处理的需求。

    GraphX是一个使用非常广泛的图计算库,而在GraphX之前,也有许多的图计算库,比如Pregel、Giraph、GraphLab等,他们有着共同的特点:定义了独特的图计算API,简化图算法的实现;充分利用图数据结构特点加速计算,比通用的数据驱动的计算引擎更快。但随着需求的变化,这些图计算库逐渐被淘汰了,这是为什么呢?
    观察近现代图计算整个流程,在图计算整个流程里面涉及了两部分的计算:一是结构化数据的计算和提取,二是图数据计算与分析。为了完成结构化数据和图数据的处理,在GraphX出来之前,公司主要是用Hadoop和Spark这种通用的计算引擎来解决,后半部分是用专门的图计算引擎Pregel来处理,这就需要同时维护和学习两套计算引擎,比较麻烦。如下图表示:

    在这里插入图片描述

    可能有人会说:用两套系统就可以解决问题了啊。但你有所不知的是,同时混用多个引擎会出现非常多的问题,如成本高,效率低下,数据冗余等问题,这样会使整个计算过程变得复杂。

    在这里插入图片描述
    在传统的图计算流水线中,在Table View视图下,可能需要Spark或者Hadoop的支持,在Graph View这种视图下,可能需要Prege或者GraphLab的支持。也就是把图和表分在不同的系统中分别处理。 不同系统之间数据的移动和通信会成为很大的负担。

    而GraphX就解决了这一问题,将分布式图graph-parallel和分布式数据data-parallel统一到一个系统中,并提供了一个唯一的组合API ,GraphX允许用户把数据当做一个图和一个集合(RDD),而不需要数据移动或者复制。作为统一的图计算引擎,GraphX可以实现在一个数据流水线中,使用一种技术解决图计算相关所有问题!

    GraphX包含两大特色:

    新API:打破了结构化数据和图数据的界限。
    新Library:直接在Spark上完成图计算。
    

    三、常见的图算法

    通常,在图计算中,基本的数据结构表达就是:G = (V,E,D) V = vertex (顶点或者节点) E = edge (边) D = data (权重)。 图数据结构很好的表达了数据之间的关联性,因此,很多应用中出现的问题都可以抽象成图来表示,以图论的思想或者以图为基础建立模型来解决问题。

    1、PageRank算法

    PageRank源自搜索引擎,它是搜索引擎里面非常重要的图算法,可用来对网页做排序。比如我们在网页里搜索spark,会出来非常多有着spark关键字的网页,可能有上千上万个相关网页,而PageRank可以根据这些网页的排序算法将其排序,将一些用户最需要的网页进行优先展示。

    在这里插入图片描述

    2、最短路径算法

    在社交网络里面,有一个六度空间的理论,表示你和任何一个陌生人之间所间隔的人不会超过五个,也就是说,最多通过五个中间人你就能够认识任何一个陌生人。这也是图算法的一种,也就是说,任何两个人之间的最短路径都是小于等于6。

    在这里插入图片描述

    3、社群发现

    用来发现社交网络中三角形的个数(圈子),可以分析出哪些圈子更稳固,关系更紧密。用来衡量社群耦合关系的紧密程度。一个人的社交圈子里面,三角形个数越多,说明他的社交关系越稳固、紧密。像微信、微博、Facebook、Twitter等社交网站,常用到的的社交分析算法就是社群发现。

    在这里插入图片描述

    4、推荐算法ALS和SVD++

    ALS是一个矩阵分解算法,比如购物网站要给用户进行商品推荐一些推荐,就需要知道哪些用户对哪些商品感兴趣,这时,可以通过ALS构建一个矩阵图,在这个矩阵图里,假如被用户购买过的商品是1,没有被用户购买过的是0,这时我们需要计算的就是有哪些0有可能会变成1。

    在这里插入图片描述

    四、GraphX数据抽象RDPG

    Spark的每一个模块,都有自己的抽象数据结构(如下图),GraphX的核心抽象是弹性分布式属性图(resilient distribute property graph),一种点和边都带有属性的有向多重图。

    在这里插入图片描述
    Spark关键抽象如下图:
    属性图扩展了Spark RDD的抽象,它同时拥有Table和Graph两种视图,而只需一种物理存储,这两种操作符都有自己独有的操作符,从而获得灵活的操作和较高的执行效率。
    在这里插入图片描述
    GraphX支持并行边的能力简化了建模场景,相同的顶点可能存在多种关系(例如co-worker和friend)。 每个顶点用一个唯一的64位长的标识符(VertexID)作为key。GraphX并没有对顶点标识强加任何排序。同样,边拥有相应的源和目的顶点标识符。

    顶点以VertexId的顶点ID和属性VD作为参数类型,边以Edge(ED)作为参数类型,属性图以vertex(VD)和edge(ED)类型作为参数类型,这些类型分别是顶点和边相关联的对象的类型。
    在这里插入图片描述

    五、图基本结构

    GraphX的整体架构可以分为三个部分:

    实现层:Graph类是图计算的核心类,内部含有VertexRDD、EdgeRDD和RDD[EdgeTriplet]引用。GraphImpl是Graph类的子类,实现了图操作。

    接口层:在底层RDD的基础之上实现Pragel模型,BSP模式的计算接口。

    算法层:基于Pregel接口实现了常用的图算法。包含:PageRank、SVDPlusPlus、TriangleCount、ConnectedComponents、StronglyConnectedConponents等算法。

    在这里插入图片描述
    在图的基本架构基础上我们进一步分析构成弹性分布式属性图的特性:

    RDPG和RDD一样,属性图是不可变的、分布式的、容错的。图的值或者结构的改变需要生成一个新的图来实现。注意,原始图中不受影响的部分都可以在新图中重用,用来减少存储的成本。 执行者使用一系列顶点分区方法来对图进行分区。如RDD一样,图的每个分区可以在发生故障的情况下被重新创建在不同的机器上。
    逻辑上,属性图对应于一对类型化的集合(RDD),这个集合包含每一个顶点和边的属性。因此,图的类中包含访问图中顶点和边的成员变量。

    class Graph[VD, ED] {
      val vertices: VertexRDD[VD]
      val edges: EdgeRDD[ED]
    }
    //注意:
    //VertexRDD[VD]和EdgeRDD[ED]类是RDD[(VertexID, VD)]和RDD[Edge[ED]]的继承和优化版本。
    //VertexRDD[VD]和EdgeRDD[ED]都提供了额外的图计算功能并提供内部优化功能。
    
    abstract class VertexRDD[VD](sc: SparkContext, deps: Seq[Dependency[_]]) extends RDD[(VertexId, VD)](sc, deps)
    abstract class EdgeRDD[ED](sc: SparkContext, deps: Seq[Dependency[_]]) extends RDD[Edge[ED]](sc, deps)
    
    

    在同样的图中,我们可能希望拥有不同属性类型的顶点。这可以通过继承完成。例如,将用户和产品建模成一个二分图,我们可以用如下方式:

    class VertexProperty()
    case class UserProperty(val name: String) extends VertexProperty
    case class ProductProperty(val name: String, val price: Double) extends VertexProperty
    // The graph might then have the type:
    var graph: Graph[VertexProperty, String] = null
    

    1、GraphX的底层设计

    对Graph视图的所有操作,最终都会转换成其关联的Table视图的RDD操作来完成。这样对一个图的计算,最终在逻辑上,等价于一系列RDD的转换过程。因此,Graph最终具备了RDD的3个关键特性:Immutable、Distributed和Fault-Tolerant,其中最关键的是Immutable(不变性)。逻辑上,所有图的转换和操作都产生了一个新图;物理上,GraphX会有一定程度的不变顶点和边的复用优化,对用户透明。

    两种视图底层共用的物理数据,由RDD[Vertex-Partition]和RDD[EdgePartition]这两个RDD组成。点和边实际都不是以表Collection[tuple]的形式存储的,而是由VertexPartition/EdgePartition在内部存储一个带索引结构的分片数据块,以加速不同视图下的遍历速度。不变的索引结构在RDD转换过程中是共用的,降低了计算和存储开销。

    图的分布式存储采用点分割模式,而且使用partitionBy方法,由用户指定不同的划分策略(PartitionStrategy)。划分策略会将边分配到各个EdgePartition,顶点分配到各个VertexPartition,EdgePartition也会缓存本地边关联点的Ghost副本。划分策略的不同会影响到所需要缓存的Ghost副本数量,以及每个EdgePartition分配的边的均衡程度,需要根据图的结构特征选取最佳策略。目前有EdgePartition2d、EdgePartition1d、RandomVertexCut和CanonicalRandomVertexCut这四种策略。

    2、图数据存储方式

    在这里插入图片描述
    一般在工业级的应用中,图的规模很大,为了提高处理的速度和数据量,我们希望使用分布式的方式来存储,处理图数据。图的分布式存储大致有两种方式,边分割(Edge Cut),点分割(Vertex Cut),在早期的图计算框架中,使用的是边分割的存储方式,后期考虑到真实世界中大规模图大多是边多于点的图。所以采用点分割方式来存储,见上图。

    在这里插入图片描述
    点分割能减少网络传输和存储开销,底层实现是将边放到各个节点存储,而进行数据交换的时候将点在各个机器之间广播进行传输。对于边的存储和分区算法主要基于PartitionStrategy中封装的分区方法,用户可以根据具体的需求 进行分区方式的选择,可以在程序中指定边的分区方式。如:

    val graph=Graph(vertices,partitionBy(edges,PartitionStrategy.EdgePartition2D))
    

    当边在集群中分布式存储的时候,在有些场景中,我们需要使用顶点的属性,因此,需要点的属性连接到边,那么如何将顶点在集群中传播移动呢?GraphX内部维持了一个路由表(routing table),这样当广播点的所在区时就可以通过路由表映射,将需要的点属性传输到边分区。

    使用点分割,好处在于边上没有冗余的数据,而且对于某个点与它的邻居的交互操作,只要满足交换律和结合律即可。不过点分割这样做的代价是有的顶点的属性可能要冗余存储多份,更新点数据时要有数据同步开销。
    如下图所示理解Graphx存储结构。
    在这里插入图片描述

    六、GraphX简单案例-社交网络关系查询

    1、需求分析

    假设我们要构建一个由GraphX项目上的各种协作者组成的属性图。vertex属性可能包含用户名和职业。我们可以使用描述协作者之间关系的字符串来注释边:
    在这里插入图片描述
    2、代码演示

    import org.apache.spark.graphx.{Edge, Graph, VertexId}
    import org.apache.spark.rdd.RDD
    import org.apache.spark.{SparkConf, SparkContext}
    import org.slf4j.LoggerFactory
    
    object GraphXDemo{
      val logger = LoggerFactory.getLogger(GraphXDemo.getClass)
      def main(args: Array[String]) {
        //创建SparkConf()来包含整个Spark配置信息
        val conf = new SparkConf().setMaster("local[*]").setAppName("GraphX")
        //创建SparkContext,该对象是提交spark App的入口
        val sc = new SparkContext(conf)
        // 创建一个顶点的集合,VertexID是一个long类型的,顶点的属性是一个二元组
        val users: RDD[(VertexId, (String, String))] =sc.parallelize(Array((3L, ("rxin", "student")), (7L, ("jgonzal", "postdoc")),(5L, ("franklin", "prof")), (2L, ("istoica", "prof"))))
        // 创建一个边的集合,边的类型是string类型
        val relationships: RDD[Edge[String]] =sc.parallelize(Array(Edge(3L, 7L, "collab"), Edge(5L, 3L, "advisor"),
            Edge(2L, 5L, "colleague"), Edge(5L, 7L, "pi")))
        // Define a default user in case there are relationship with missing user---默认(缺失)用户 
    	val defaultUser = ("DT Liu", "Missing")
    
        // 创建图,传入顶点和边
        val graph = Graph(users, relationships, defaultUser)
        // 过滤图上所有的顶点和边。如果顶点属性第二个至是posdoc博士后那就过滤出来,计算满足条件的顶点个数
        val verticesCount = graph.vertices.filter { case (id, (name, pos)) => pos == "postdoc" }.count
    	println(verticesCount)
    	
    	//GraphX也包含了一个三元组视图,用一个三元组视图渲染字符串集合用来描述用户之间的关系
    	val graph: Graph[(String, String), String] 
    	// Use the triplets view to create an RDD of facts.
    	val facts: RDD[String] =graph.triplets.map(triplet =>triplet.srcAttr._1 + " is the " + triplet.attr + " of " + triplet.dstAttr._1)
    	facts.collect.foreach(println(_))
    
        // 计算满足条件的边的个数,条件是边的sourceid>目的id
        val edgeCount = graph.edges.filter(e => e.srcId > e.dstId).count
        println(edgeCount)
        //关闭sparkContext
        sc.stop()
      }
    }
    
    
    展开全文
  • 基于图查询系统的图计算引擎

    千次阅读 2019-08-28 16:28:41
    基于图查询系统的图计算引擎柯学翰, 陈榕上海交通大学软件学院并行与分布式系统研究所,上海 200240摘要:在目前的研究中,图查询和图计算系统是相互独立的,但在实际应用中...

    柯学翰, 陈榕

    上海交通大学软件学院并行与分布式系统研究所,上海 200240

    摘要在目前的研究中,图查询和图计算系统是相互独立的,但在实际应用中两者通常是同时存在的。为解决相互独立的系统带来的存储空间浪费、数据一致性维护等问题,基于图查询系统设计了一种图计算引擎,使得在单一系统中支持查询和计算操作。通过为键值对存储增加图计算索引、基于拉取模式的数据更新等方式,有效地提高系统中数据遍历的性能和减少数据传输的成本,同时针对数据更新和负载均衡等方面提出了相关优化。实验表明,该图计算引擎能够达到与传统图计算系统PowerLyra和Gemini相近或比其更优的性能,且具有较好的可扩展性。

    关键词 分布式系统 ; 图计算 ; 图查询 ; 键值对存储

    640?wx_fmt=jpeg

    论文引用格式:柯学翰, 陈榕. 基于图查询系统的图计算引擎. 大数据[J], 2019, 5(4):16-26

    KE X H,CHEN R. Graph processing engine based on graph query system. Big Data Research[J], 2019, 5(4): 16-26

    640?wx_fmt=jpeg

    1 引言

    近年来,随着互联网和社交网络的快速发展,大规模的图结构数据逐渐增多,例如将知识图谱、社交网络等信息抽象成的图结构数据。相比于传统的大数据处理系统,图系统能更好地利用图的结构信息,对图数据的处理更为高效。目前对图系统的研究可分为图查询系统和图计算系统两个方面。

    图查询系统需要找到符合用户需求的图数据,常见的图查询系统有Wukong、TriAD、Trinity.RDF等。图查询任务通常只需要访问全图中小部分的数据,但对时延非常敏感,需要在秒甚至毫秒级返回结果。因此,图查询系统通常使用键值对的存储模式,使得对单个顶点的访问更加高效。与图查询系统不同,在图计算系统中,一般使用稀疏矩阵存储图的结构。图计算任务通常需要访问全图上所有的顶点,对全图上的数据进行多轮迭代计算后才能结束,时延通常是分钟甚至小时级别的。因此,在图计算系统中,单个顶点的访问时延不是最重要的,其更关注的是整个系统的计算吞吐率。常见的图计算系统有Pregel、PowerGraph、PowerLyra、Gemini等。

    目前对图查询系统和图计算系统的研究一般是相互独立的,但在实际应用中,图查询和图计算任务通常是同时存在的。例如对于一个记录了电商平台上用户和商品之间的关系的图数据,电商平台既有查询用户历史订单的需求(图查询任务),又有基于该图数据进行商品推荐的需求(图计算任务)。传统的做法是在图查询系统和图计算系统中分别加载该图数据进行分析。但是一份数据多份存储会带来许多的问题,例如内存空间的浪费、维护不同系统间数据的一致性等问题。

    为了避免以上问题,本文在现有图查询系统基础上设计和实现了一种高效的图计算引擎,其能够在单个系统中同时支持高效的图查询和图计算操作。首先给键值对的存储结构增加针对图计算的索引,使其加快对图的遍历效率;其次针对图系统中的数据划分,为其设计了基于拉取(pull)模型的消息传递模式;最后针对该计算引擎的数据更新和负载均衡等方面进行了优化。在不同的测试集中的测试结果表明,该计算引擎图计算性能可达到PowerLyra系统的4.7倍到20倍,同时具有良好的可扩展性。

    2 背景介绍

    2.1 图数据的存储结构

    键值对存储因具有可扩展强、结构简单、查找迅速等特点被广泛应用于图查询系统中,如Wukong、Trinity.RDF。在Wukong系统中,图上的边会转换成键值对进行存储,将顶点编号、边的类型、边的方向、值的地址和大小等信息组合成键(key),对应邻居顶点构成值(value),如图1所示。当需要查询顶点1、边类型为2的所有入边(in)时,先通过Hash函数找到对应的键的存储位置,然后根据键得到值的存储地址(offset),最后再通过远端或者本地访问的方式获取值的信息,即对应的邻居有顶点8和顶点9。

    640?wx_fmt=jpeg

    图1   键值对存储

    在图计算系统中广泛使用压缩稀疏矩阵来存储图的结构,如图2所示,包括GraphLab、PowerGraph、Gemini等系统。行压缩稀疏矩阵(compressed sparse row,CSR)表示出边的信息,列压缩稀疏矩阵(compressed sparse column,CSC)表示入边的信息。顶点索引(vertex index)记录了每个顶点在边数组中的起始位置,并且顶点编号与顶点索引数组的序号保持一致。如顶点2,在顶点索引中的值为4,则顶点2的邻居顶点从边数组中下标为4的元素开始,一直到下一个顶点对应的索引值6,也就是说顶点1、顶点3是顶点2的邻居顶点。若该结构为CSC,则(1,2)和(3,2)是原图中的边;若为CSR,则(2,1)和(2,3)为原图中的边。压缩稀疏矩阵的图存储方式对于遍历图上所有边的计算而言是高效的。

    640?wx_fmt=jpeg

    图2   压缩稀疏矩阵存储边的数据

    2.2 图计算系统的图划分和执行模式

    在图计算系统中,图划分在减少数据跨机器通信、负载均衡等方面发挥着很重要的作用。目前的划分方式可以分为边划分(edge-cut)和点划分(vertex-cut),如图3所示。

    640?wx_fmt=jpeg

    图3   边划分和点划分

    边划分是指图从边切开,每个顶点被放置在一台服务器上(通常通过Hash的方式),也就是该顶点对应的边信息都存储在该机器上,其他服务器上只有该顶点的镜像顶点,因此每条边会在多台机器上出现。边划分的优点是计算过程中对邻居顶点信息的聚集都可以在本地完成;缺点是对于幂律分布的图,会出现负载不均衡的问题。幂律分布的图的特点是少部分的点拥有大量的边,因此拥有着这些点的机器的信息计算和通信开销会远大于其他的机器。点划分是将每条边唯一放置在一台机器上,顶点可能会被切分在不同的机器中。点划分的优点是对于幂律分布的图也能实现很好的负载均衡。但是存在的问题是,在计算的过程中,由于一个顶点被切分在不同服务器上,则聚合邻居顶点的信息需要进行跨机器通信。还有一些工作是将点划分和边划分的方法相互结合,为图上不同的顶点提供不同的划分方法。

    图计算引擎的实现通常有两种方式:基于推送(push-based)模式和基于拉取(pull-based)模式。基于推送模式是对源顶点进行遍历,然后源顶点将自身的状态通过出边更新邻居顶点的状态。相反地,基于拉取模式是对目标顶点进行遍历,通过入边拉取邻居顶点的状态更新自己。相比于基于推送模式的更新邻居顶点(写)操作,基于拉取模式的引擎只需要拉取邻居顶点的信息(读)即可,因此其能够达到更高的计算吞吐率。基于推送模式比较适合图中活跃顶点较少的算法,可以方便地跳过该轮迭代中没有活跃的顶点,减少计算量。同时也有系统混合使用了两种更新方式,在执行的过程中动态地选择适合的更新模式,如Gemini、Polymer等系统。

    3 图计算引擎的设计和优化

    该节主要介绍了如何在图查询系统中设计和实现一个高效的图计算引擎。首先总结了在图查询系统上实现图计算引擎的两点挑战;然后针对两点挑战分别提出了针对图计算索引优化和基于拉取模式的消息传递模式两种技术;接着介绍了图计算引擎的编程接口;最后给出了两种图计算引擎的优化方法:非阻塞式更新和负载均衡。

    3.1 挑战

    在单一系统中,所有的设计是为了该类型系统而设计的,包括数据的存储结构、数据的传输模型等。因此,不同系统间的设计是不匹配的,甚至是相互冲突的。首先,不同的系统对底层存储结构的要求不同。图查询系统一般使用键值对的方式存储图的结构信息,这样的存储方式有利于特定数据的快速查找,同时具有良好的可扩展性。而在图计算系统中,为了提升计算性能,需要的是支持高效图数据遍历的存储结构,例如CSR和CSC。其次,图计算系统进行数据传输的模式在很大程度上取决于图数据的划分方式。在一个图查询系统的数据划分方法下,一般不能直接套用现有图计算系统的数据传输模型,因为会出现顶点或者边的信息缺失等问题。

    本文基于目前性能出色的分布式图查询系统Wukong实现图计算引擎。键值对的存储结构具有很好的可扩展性,因此笔者希望在不改变原来图查询系统的基本的数据存储模式的情况下,增加高效的图计算引擎支持。基于以上分析,目前面临的挑战主要有以下两个方面。

    挑战1:图计算系统需要高效的图遍历存储结构,如何针对键值对的存储进行高效的图计算。

    直接使用键值对存储进行图计算存在的问题是计算性能不理想。在Wukong中,每个顶点访问其邻居顶点的信息时需要先构造对应的键,然后通过Hash表查找,最后才能获得邻居顶点的存储位置。这主要是因为图查询任务对于顶点的访问是随机的,Hash表可以加速一次随机的查找。而在图计算系统中,对于顶点的访问是顺序遍历的。CSC或CSR存储模式不仅可以通过一次访存操作获得邻居顶点的地址,而且使得数据具有很好的空间局部性。相比之下,使用Hash表查找的方式顺序遍历所有的顶点无疑是比较低效的。针对该问题本文提出了针对图计算的索引优化技术。

    挑战2:图计算的数据传递模式在很大程度上取决于图数据的划分,如何在图查询系统中为图计算引擎设计合适的数据传递模式。

    在Wukong系统中,非查询索引部分的图数据是按照边划分的模式进行的,即每个顶点属于唯一一台机器,并且为了加速查询,边的信息会进行双向的存储。这种图划分的模式不同于PowerGraph、Gemini等图计算系统的划分方式,因此在Wukong系统上直接使用这些图计算系统的消息传递模式是不合适的。针对该挑战,本文提出了一种基于拉取模型的消息传递模式。

    3.2 针对图计算的索引优化技术

    为了解决第3.1节中的挑战1,图查询系统的存储结构需要支持高效的顺序遍历。高效的顺序遍历是指图系统能够快速地遍历图中所有的点和点对应的邻居,同时,原图查询系统的随机访问的性能不能受到影响。基于此目的,本文提出了针对图计算的索引优化技术。

    针对图计算的索引优化是指在原先键值对的存储结构下,增加高效地顺序遍历索引的支持,使得顶点的遍历不需要通过Hash表获取顶点存储位置的地址偏移量,而是可以直接从索引中得到。这样能够大大地缩短数据访问的时间。

    如图4所示,本文在原系统的存储结构中增加了索引的结构。原查询系统(Wukong)中的数据存储结构主要包括两个部分:键存储和值存储。索引是一个数组的结构,数组的下标与对应的顶点ID一致,数组中的值为该顶点在值存储中的起始地址偏移量,对应的终止偏移量可以根据下一个顶点的起始地址偏移量来计算。例如,1号顶点对应的起始偏移量是0, 2号顶点对应的起始偏移量为4,说明1号顶点对应的邻居顶点为值数组中0号到3号的位置的数,分别为4号、5号、8号、9号顶点。需要注意的是,在原图查询系统中,不同键对应的值的存储可以是不连续的。在新的存储模式下,为了便于索引的访问,值需要按顶点ID有序并且连续存储。但这样的限制不会对原先的图查询系统产生性能影响。

    640?wx_fmt=jpeg

    图4   基于图计算引擎的索引

    在增加了图计算索引的存储结构下,图数据的访问模式主要分为以下两种。

    ● 图查询任务:与原查询系统一致,首先通过Hash函数找到特定顶点的键的位置,然后根据键找到值的存储位置,即可获得邻居顶点的信息。

    ● 图计算任务:当图计算引擎需要遍历所有顶点的信息时,通过遍历图计算索引上的数据,就可以直接获得对应顶点的邻居信息的偏移量。

    通过添加图计算的索引,图计算引擎对顶点的遍历基本与使用压缩稀疏存储结构一致,因此对图数据的访问也可以达到与单一图计算系统相似的性能。通过索引,对于每个顶点只需要一次内存访问就可以获得其对应的邻居顶点的偏移量。对于图的遍历,只需要顺序遍历一次索引数组和值数组即可,并且在计算过程中数据也具有很好的空间局部性。

    3.3 基于拉取模式的消息传递

    图计算引擎的消息传递模式与图的划分方式有很大的关系,因为图数据划分的模式影响了顶点收集邻居顶点的消息来更新自己的方式。在Wukong中,键值对的存储模式事实上是一种边划分的方式,即每一个顶点只属于一台服务器,在其他服务器上的只是它的镜像顶点。

    根据图查询系统的数据划分特点,本文使用基于拉取模式的消息传递,类似于Ligra、Polymer等系统中使用的pull模式。在每轮迭代中主要分为两个步骤进行,如图5所示。

    640?wx_fmt=jpeg

    图5   基于拉取模型的消息传递模式

    步骤1 每台服务器上的顶点拉取其入边顶点的消息来更新自身的值。例如顶点2通过入边信息,聚合邻居顶点1、顶点3的值,然后更新自己的值。

    步骤2 每台服务器上的顶点会将步骤1中更新的值发送给其他机器,更新其镜像顶点的值,到此一轮迭代的计算完成。例如服务器0上的顶点2、顶点4会发送信息给服务器1,以更新服务器1上顶点2、顶点4的镜像顶点的值。

    在图查询系统Wukong中选择拉取模式而不是推送模式,是由其数据的存储模式决定的。因为每台服务器存储的信息是主顶点(master)聚集起来的,如果选择推送的模式,则每个顶点需要发送信息更新它的出边邻居顶点,发送的消息数量为O(E)(E表示边的数量,发送消息的数量与边的数量成正比)。例如服务器0上的顶点2需要更新服务器1上的顶点1、顶点3,因为服务器1上没有顶点2的邻居信息(只能通过顶点1、顶点3访问顶点2,不能通过顶点2访问顶点1、顶点3),因此服务器0需要发送两条信息,分别更新服务器1上的顶点1和顶点3。而在拉取模式下,顶点的聚合操作都是在本地进行的,不同服务器间只需要进行主顶点和镜像顶点的通信即可,消息发送数量由O(E)减少为O(V)(V表示顶点的数量)。

    同时,对于不同机器间的顶点更新,本文采用了批量更新(batch)的方法,以减少单次数据更新的开销。批量更新是指将需要更新的顶点数据聚集在一起,然后一次性发送给其他的机器进行更新,而不是每个顶点单独发送一条更新消息。批量更新的方法虽然增加了单次数据发送的时间,但是大大地降低了数据发送的次数,因此平均下来每一条数据的传播时间被极大地缩短。

    3.4 图计算模型抽象接口

    本文借鉴了其他图计算工作中提出的抽象接口,为用户提供了两种操作接口:Vertex_map和Edge_map。在接口设计上,保持了图计算系统中“像顶点一样去思考”的设计原则,接口介绍如下。

    ● Vertex_map(F_Vertex,Active):这个接口通过F_Vertex定义了单个顶点本地的操作。F_Vertex 为用户自定义函数,参数为当前顶点ID。用户可以自己定义如何对单个顶点进行操作。Active为活跃顶点的集合,每轮迭代中,只有活跃的顶点参与计算。

    ● Edge_map(F_Edge,Active):这个接口通过F_Edge定义用户如何在边上进行数据聚集操作。参数F_Edge是一个用户自定义函数,该函数的参数为当前顶点ID和该顶点所有入边顶点。

    算法1给出了PageRank算法使用上述接口的具体实现。

    算法1:Pagerank 算法。

    Dnext<- {0.0,0.0 … 0.0}

    Dcurr<- {0.0,0.0 … 0.0}

    F_Vertex (v){

    Dcurr[v]= 1/|V|;

    }

    F_Edge(s,dst[]) {

    for(i =0;i <dst.size;i ++) {

    Dnext[s]<- Dcurr[dst[i]]/Out[dst[i]];

    }

    Dnext[s]<-0.15/|V| + 0.85*Dnext[s];

    }

    PageRank(iter_num) {

    iter<- 0

    A<- V

    Vertex_map(F_Vertex,A);

    while iter<iter_num do {

    Edge_map(F_Edge,A);

    Swap(Dcurr,Dnext);

    }

    }

    3.5 优化

    3.5.1 非阻塞式更新

    在拉取模式下的步骤2,需要将本地更新的主顶点数据发送给其他机器,更新对应的镜像顶点。阻塞式更新是指服务器在接收别的服务器发送过来的更新数据时一直处于等待的状态,直到所有的数据接收完成后才开始本地的更新操作。

    而非阻塞式更新在接受消息时不会阻塞整个更新的过程,即在接收数据的同时也在更新本地的数据。具体实现如图6所示,将数据接收和计算交由不同的线程负责。通信线程(communication thread)负责数据的接收,当接收一部分数据后就通知前台计算线程(computation thread)。计算线程发现有可更新的数据时,就将数据更新到本地,此时通信线程仍在继续接收新的数据,这样数据的接收和更新是并行的。当数据接收完成时,数据的更新也基本完成,使得消息传播的时间“覆盖”更新时间。

    640?wx_fmt=jpeg

    图6   非阻塞式更新

    3.5.2 负载均衡

    负载均衡是分布式并行计算系统一个重要的研究方向。对于一个同步的图计算引擎来说,计算的时间取决于最慢的机器的执行时间。其中,同步的图计算引擎是指新一轮迭代的开始需要等待所有的点完成上一轮迭代。因此,不同机器间以及单个机器中不同线程间的计算任务需要尽可能均衡。不同机器间的负载均衡由图的划分来保证,本文主要关注单台机器上不同线程间的负载均衡问题。针对该问题,笔者提出两个优化方案:基于边数量的任务划分和任务窃取。

    基于边数量的任务划分方法是基于Grazelle系统中的思想提出的,指依据边的数量为每个线程划分负责的点的数量。拉取引擎的计算过程包括两层循环,外层循环对所有目标顶点进行遍历,内层循环对每个目标顶点通过入边聚集源顶点的信息。不同的系统通常在外层循环中使用并行方法进行优化,即每个线程负责不同的目标顶点的计算。一种简单的划分策略是按照外层循环的顶点数量进行划分,但不同顶点对应边的数量不一致,这可能导致不同线程的计算量差异较大。因此,本文基于边数量预先为每个线程分配好需要负责的顶点。如图7所示,将下面的计算任务划分给两个线程,线程0负责0号顶点,线程1负责1~5号顶点,每个线程中的计算都包含了7条边。如果使用基于点的数量的任务划分方法,则线程1负责0~2号顶点,一共10条边,而线程2负责3~5号顶点,一共4条边,会出现负载不均衡的问题。

    任务窃取技术被广泛应用在分布式并行系统中,它让已经完成任务的线程“窃取”其他线程未完成的任务来执行。在本系统中其可以与基于边数量的任务划分技术共同使用,具体实现如下:首先每个线程维护一个任务队列;然后将被分配好的任务划分成更多的子任务,保存在各自的任务队列里;最后每个线程从各自的任务队列里获取子任务并执行,当任务队列为空时,检查旁边线程的任务队列,“窃取”其他线程的任务来执行。

    640?wx_fmt=jpeg

    图7   基于边的数量的任务划分

    4 测试

    PowerGraph是一个功能完善、业界认可度比较高的图计算系统, PowerLyra是在PowerGraph基础上针对幂律图进行改进的系统。Gemini是目前性能比较出色的图计算系统,性能优于PowerGraph和PowerLyra。因此,本文选择PowerLyra和Gemini作为主要比较的系统。以下主要从性能和可扩展性两个方面对本文的图计算引擎进行分析。

    4.1 实验环境

    本文所有实验均在6台多核服务器组成的集群上完成,单节点配置如下:两个10核Intel(R) Xeon(R) E5-2650 v3 2.30 GHz处理器,内存分别为64 GB,其中远程直接内存访问(remote direct memory access,RDMA)网络使用ConnectX-3 MCX353A 56 Gbit/s InfiniBand网卡,通过Mellanox IS5025 40 Gbit/s交换机连接;以太网使用Intel X520 10GbE 网卡,通过Force10 S4810P 10GbE交换机连接。Wukong系统支持RDMA,因此在其基础上实现的图计算引擎使用RDMA进行机器通信,其他不支持RDMA的图计算系统使用普通以太网进行通信。表1给出了用于测试的数据集(UK、Twitter、RoadUS、Wiki)的相关信息,其中,|V|表示顶点数量,|E|表示边的数量。

    640?wx_fmt=png

    4.2 性能测试

    图8是在4台服务器配置下,不同系统在多种数据集下的执行Pagerank算法(20次迭代)的时间对比。Pull-based表示在直接图查询系统中使用基于拉取模式的消息传递,没有使用其他的优化。Pull-optimal表示使用了相关技术优化后的图计算引擎,包括针对索引的优化技术、非阻塞式更新以及负载均衡等。其中Pull-based作为自身对照的基线系统, PowerLyra和Gemini作为与图计算系统对照的基线系统。

    640?wx_fmt=jpeg

    图8   性能对比测试

    从图8可以看出,相比于自身基线系统Pull-based,Pull-optimal的运行速度是其2.08~3.14倍。在图计算任务中,对图数据的遍历访问主要集中在核心计算路径上,因此增加图计算的索引结构、加快图数据遍历速度可以极大地缩短图计算的整体执行时间。

    相比于图查询系统PowerLyra,Pulloptimal的运行速度是其4.75~19.98倍。这一方面是因为PowerLyra是一个功能比较完善的图计算系统,其提供了更多的抽象和复杂图的操作,同时也带来了较大的开销;另一方面是因为在Pull-optimal中使用了高速网络RDMA,使得数据传输的时间大大缩短。相比于Gemini系统,在UK和RoadUS数据集下,本文中图计算引擎执行时间分别为Gemini的1.99倍和1.06倍。Gemini系统针对图存储结构做出了更多的优化,例如针对非统一内存访问架构(non-uniform memory access, NUMA)结构的存储、按块的图划分等。但是这些优化与现有的图查询系统存储是冲突的,不能应用于本文的系统上,因此Pull-optimal性能差于Gemini。在Twitter和Wiki数据集下,由于Gemini系统中机器间的通信数据量增大,占据了执行时间的绝大部分,而本文中图计算引擎使用高速网络RDMA,大大减少了网络的开销,因此性能优于Gemini系统。整体来看,本文基于图查询的图计算引擎相比独立的图计算系统,带来的额外开销不超过1倍,最优性能接近原性能的20倍。

    4.3 可扩展性测试

    图9展示了本文中图计算引擎随着服务器数目的增加整体运行时间的变化。测试使用Twitter作为测试的数据集,机器数量从1台变化到6台,运行PageRank算法。从图9中可以看出,该图计算引擎有很好的可扩展性。相对于2台机器(分布式模式下最小的机器数)的执行时间,当机器数目扩展到4台和6台时,分别可以达到2台机器性能的1.71倍和2.77倍。这是因为键值对的存储系统本身具有良好的可扩展性。

    640?wx_fmt=jpeg

    图9   可扩展性测试

    5 结束语

    随着图结构化数据的增多,如何高效处理大量图结构数据成为研究的热点。但由于目前相互独立的图查询系统和图计算系统与实际应用的需要不相符,本文提出了基于图查询系统的图计算引擎。首先通过为键值对存储添加图计算索引的方式,提高图计算的效率;其次,基于图系统中的图划分模式,使用基于拉取模式的消息传递;最后针对数据更新和负载均衡进行了优化。通过测试表明,本文提出的图计算引擎能够在兼容图查询系统的同时,利用各种优化技术提供与PowerLyra和Gemini接近或比其更优的性能,并具有较好的可扩展性。

    作者简介

    柯学翰(1996- ),男,上海交通大学软件学院并行与分布式系统研究所硕士生,主要研究方向为分布式 图计算系统。

    陈榕(1981- ),男,博士,上海交通大学软件学院并行与分布式系统研究所副教授,主要研究方向为并 行与分布式系统、内存计算等。

    《大数据》期刊

    《大数据(Big Data Research,BDR)》双月刊是由中华人民共和国工业和信息化部主管,人民邮电出版社主办,中国计算机学会大数据专家委员会学术指导,北京信通传媒有限责任公司出版的中文科技核心期刊。

    640?wx_fmt=jpeg

    关注《大数据》期刊微信公众号,获取更多内容


    往期文章回顾

    综合交通大数据应用技术的发展展望

    边缘智能:现状和展望

    我国地方大数据政策的扩散模式与转移特征研究

    知识图谱中的关系方向与强度研究

    面向大数据的索引结构研究进展


    展开全文
  • 本文将对字节跳动自研的分布式图数据库和图计算专用引擎做深度解析和分享,展示新技术是如何解决业务问题,影响几亿互联网用户的产品体验。 1. 图状结构数据广泛存在 字节跳动的所有产品的大部分业务数据,几乎都...
  • Pregel(图计算)技术原理

    万次阅读 多人点赞 2018-06-02 14:32:51
    图计算简介 图结构数据: 许多大数据都是以大规模图或网络的形式呈现。 许多非图结构的大数据,也常常会被转换为图模型后进行分析。 图数据结构很好地表达了数据之间的关联性。 关联性计算是大数据计算的核心...
  • 王家林+Spark+GraphX大规模图计算和图

    热门讨论 2014-09-26 22:28:23
    王家林+Spark+GraphX大规模图计算和图 挺不错的
  • 图计算的作用2. 本专题的写作目的3. Flink Gelly引擎总览3.1. Gelly的源码结构1. Graph的存储数据结构2. 图的分类3. 图的验证以及指标4. 图的生成器5. Library6.图的迭代操作7. examples案例4. 后记 1. 图计算的...
  • 单代号网络计划表示的方法和参数标注的形式和双代号网络计划不一样,但是解网络计算方法和理解过程是一样的,所以,我们可以利用在“计算考点三:解双代号网络”中学习过的解网络思路来进行单代号网络...
  • 直方能够描述一幅图像中颜色的全局分布,而且容易理解和实现,所以入门级的图像相似度计算都是使用它的。 直方算法是对源图像与要筛选的图像进行直方数据采集,对采集的各自图像直方进行归一化再使用巴氏...
  • 网络计划即网络计划技术(Network Planning Technology),是指用于工程项目的计划与控制的一项管理技术。它既是一种科学的计划方法,又是一种有效的生产管理方法...此篇为第二类单代号网络计划的基本概念及计算方法的...
  • 图计算实现ID_Mapping、Oneid打通数据孤岛ID_Mapping与Oneid的作用我们能用来做什么实现原理输入数据源格式样例当日代码生成引用jar包启动命令辛苦码字如有转载请标明出处谢谢!——拜耳法 ID_Mapping与Oneid的作用 ...
  • Spark GraphX图计算框架原理概述

    万次阅读 2018-08-24 13:38:59
    言之易而为之难,学习大数据之图计算,就是从“浊”中找出“静”的规律,达到“清”的境界;从“安”中找出“生”的状态。 概述 GraphX是Spark中用于图和图计算的组件,GraphX通过扩展Spark RDD引入了一个新...
  • 腾讯地图计算两点间距离

    万次阅读 2019-02-21 13:40:11
    上一篇没来得及说,之所以把百度地图换成腾讯地图,是因为在IOS中,小程序不能正确显示,具体出错如下(我真是费老大劲找出来的),网上百度了好多,也有出现类似情况的,心痛,在小程序官方也没找到解决方案,若...
  • 图像的灰度直方图计算Matlab代码<一>

    热门讨论 2008-12-18 11:37:15
    该代码对图像灰度直方图的计算均采用了概率统计的方式,只是在统计的过程中采用了三种不同的统计算法,最后还比较了这三种不同的统计算法各自在计算...建议用户与“图像灰度直方图计算的Matlab代码<二>”进行比较学习。
  • 图像显著图计算

    千次阅读 2017-01-23 15:38:44
     因为需求原因,看了下显著这块,本篇主要是对论文:Saliency Filters: Contrast Based Filtering for Salient Region Detection的实现和总结。 基本原理  主要涉及超像素和一些基本假设:1、超像素分割和滤波...
  • 直方图计算

    千次阅读 2013-08-02 18:53:18
    接下来,我们介绍如何用(C语言版和C++语言版的)OpenCV来计算一维直方图计算,然后,给合python开发工具和NumPy计算和绘制直方图。在数字图像处理中,灰度直方图是一种最简单、最有用的工具之一,它概括了一幅图像的...
  • 图计算的种类和应用场景

    千次阅读 2018-08-20 16:03:55
    图计算主要将客观世界中事物间关系完整地刻画、计算和分析的一门技术。它根据人工智能三个基本特点运作:理解、推理和学习。它可以用于银行对于不良贷款的预测,也可以用于网站大数据分析推荐等功能。图算法有很多种...
  • OpenCV视差图计算

    千次阅读 热门讨论 2018-05-14 21:43:52
    OpenCV视差图计算 如今立体视觉越来越多的被应用到工业检测、机器人、自动驾驶、AR/VR领域,因为目前自己也在一个产品研发期,自己倒腾了几天做了一些通过双目进行避障的小实验,把一些比较流程化的代码以及相应...
  • 在数据规模越来越大、数据结构越来越复杂的大数据时代,传统的关系型数据暴露出了建模缺陷、水平伸缩等问题,于是具有更强大表达能力的数据受到业界极大的重视。如果把关系数据模型比做火车的话,那么现在的数据...
  • /* 版权声明:可以任意转载,转载时请务必标明文章原始出处和作者信息 .*/ CopyMiddle: 张俊林 节选自《大数据...使用Mapreduce进行图计算 使用MapReduce框架来针对大规模图数据进行计算的研究工作相对较少,这主
  • echarts堆叠柱状图计算总数

    万次阅读 2018-10-11 19:55:42
    //legend点击事件,根据传过来的obj.selected得到状态是true的legend对应的series的下标,再去计算总和 myChart.on("legendselectchanged", function(obj) { var b = obj.selected , d = []; //alert(JSON....
  • 图计算的表示中: 1.节点表示某种运算,一般都是二元运算 2.有向边,表示数据和数据的流向比如 上面的图中 有三个节点u=bc,v=a+u,J=3v 它们都在做运算。 而那些边就表示数据的流动。什么意思嘞? 比如 节点u=...
  • 1单选 Pregel是一种基于 模型实现的并行图处理系统 A.BSP B.STP C.TSP D.SBP 2单选 谷歌在后Hadoop时代的新...下列哪些是以图顶点为中心的,基于消息传递批处理的并行图计算框架 A.Pregel B.Neo4j C.G...
  • 立体视觉——固定窗口的视差图计算 1. 视差图计算[1] 深度信息可以通过计算1幅图像和其它图像的特征位置的像素差获得。视差图和深度图很像,因为视差大的像素离摄像机近,而视差小的像素离摄像机远。按以米为...
  • 对于每个活动,列出它的前驱,并计算最早开始时间、最晚开始时间和时差,然后确定出关键路径。 —— 《软件工程 第 4 版》中的原题 写文缘由 网上的文章大都是对于 “点” 求最早开始时间和最晚开始时间。在我看来...
  • 图计算框架回顾

    千次阅读 2017-03-27 15:43:41
    框架历史回归
  • 软考—必考考点之网络图计算专题

    千人学习 2016-04-06 11:00:27
    软考教程,软考考点网络图计算专题分析,进度管理中的工期和关键路径的计算是每年的必考题目,又是一个难点。该课程内容包括1.双代号网络图的绘制、最早开始时间、最早结束时间、最晚开始时间、最晚结束时间、自由...
  • 相对于目前全球范围内其它的图计算框架,Plato 可满足十亿级节点的超大规模图计算需求,将算法计算时间从天级缩短到分钟级,性能全面领先领先于其它主流分布式图计算框架,并且打破了原本动辄需要数百台服务器的资源...
  • 图计算思维与实践 (一)概览

    万次阅读 2020-12-27 15:51:34
    本文介绍了以知识图谱、网络分析为主的图计算的应用,阐述了图思维的方式。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,499,700
精华内容 1,399,880
关键字:

图计算