第九章-GraphX源码剖析20160223资源-CSDN文库

需积分: 9 33 浏览量 2019-03-21 11:05:25 上传评论收藏 4.8MB DOC 举报

资源推荐

资源详情

资源评论



第一章 Graphx

本章旨在由宏观到微观的介绍图计算、，梳理  学习时的关键知识

结构。

一.1 相关系统资料（2016.02.01 统计）

、源代码，没有单独的源代码，集成在  源码的  包中，目前是  版本。

、《》，共  页，直接就  介绍，阅读门槛低。

、《 》第七章对  的应用有所涉及，阅读门槛高。

、《Spark+GraphX 大规模图计算和图挖掘（V3.0）》，质量很低主要是对源代码

的复制粘贴。

一.2 分布式图计算与 GraphX

GraphX 是 Spark 的分布式图计算引擎。

一.2.1 分布式图计算框架的目的

将对于巨型图的各种操作包装为简单的接口，让分布式存储、并行计算等复杂问题对

上层透明，从而使复杂网络和图算法的工程师，更加聚焦在图相关的模型设计和使用上，

而不用关心底层的分布式细节。为了实现该目的，需要解决两个通用问题：图存储模式和

图计算模式。

一.2.2 Spark 图计算发展历程

早在 !" 版本， 就带了一个小型的 # 模块，提供了类似  的功能。当然，

这个版本还非常原始，性能和功能都比较弱，属于实验型产品。到 ! 版本时，鉴于业界

对分布式图计算的需求日益见涨， 开始独立一个分支 $#，作为独立的图

计算模块，借鉴 %&，开始设计开发 。在 !' 版本中，这个模块被正式集成到

主干，虽然是  版本，但已可以试用，小面包圈 # 告别舞台。! 版本， 正

式投入生产使用。现在  已经更新到  版本。

值得注意的是， 目前依然处于快速发展中，从 ! 的分支到 !' 和 !，每个版

本代码都有不少的改进和重构。根据观察，在没有改任何代码逻辑和运行环境，只是升级

版本、切换接口和重新编译的情况下，每个版本有 !()!( 的性能提升。虽然和

%& 的性能还有一定差距，但凭借  整体上的一体化流水线处理，社区热烈的活

跃度及快速改进速度， 具有强大的竞争力。

一.2.3 GraphX 及同类计算框架

一.2.3.1 GraphX

在设计  时，点分割和  都已成熟，并在设计和编码中针对它们进行了优化，



在功能和性能之间寻找最佳的平衡点。如同  本身，每个子模块都有一个核心抽象。

 的核心抽象是 *+&,，一种点和边都带属性的有向多重

图。它扩展了 *++ 的抽象，有 -& 和  两种视图，而只需要一份物理存储。

两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。

如同 ， 的代码非常简洁。 的核心代码只有  千多行，而在此之上

实现的  模型，只要短短的 ! 多行。 的代码结构其中大部分的实现，都是围

绕  的优化进行的。这在某种程度上说明了点分割的存储和相应的计算优化，的确

是图计算框架的重点和难点。

可以看到， 设计这个模型的用意。它综合了  和  两者的优点，即接

口相对简单，又保证性能，可以应对点分割的图存储模式，胜任符合幂律分布的自然图的

大型计算。

 也提供了一套图算法工具包，方便用户对图进行分析。

一.2.3.2 Giraph

 是  基金会开源项目之一，被定义为迭代式图处理系统。他架构在 

之上，提供了图处理接口，专门处理大数据的图问题。

 计算的输入是由点和直连的边组成的图。例如，点可以表示人，边可以表示朋

友请求。每个顶点保存一个值，每个边也保存一个值。输入不仅取决于图的拓扑逻辑，也

包括定点和边的初始值。

 应用还需要考虑 . 的兼容性。

Giraph 的存在很有必要，现在的大数据的图问题又很多，例如表达人与人之间的关系

的有社交网络，搜索引擎需要经常计算网页与网页之间的关系，而 map-reduce 接口不太适

合实现图算法。构成图的基本元素有哪些？

构成图的基本元素有顶点和边，边可以有权重和方向。Giraph 如何表示图？

Giraph 里同样也有顶点和边，Giraph 中的顶点也是有值的，可以用于保存计算的中间

结果。在 Giraph 图处理模型中，顶点是一切的中心，运算也是围绕着顶点进行的，顶点可

以收发消息，这里的消息跟通讯中的消息不同，这里的消息指的是从上一个计算步骤接收

信息，在顶点进行计算，并把计算好的结果通过消息发给下一个顶点。而顶点计算的输入

数据就是输入的消息、顶点的当前的值。一个顶点可以有多条输入的消息，也可以有多条

输出的消息，把这些消息发给与当前顶点相连的边的另一端的顶点。Giraph 的应用：用于

分析用户或者内容之间的联系或重要性。

一.2.3.3 GraphLab

%& 是面向机器学习的流处理并行框架。%& 将数据抽象成  结构，将

算法的执行过程抽象成 、、 三个步骤。其并行的核心思想是对顶点的切

分。

%& 由 /01 的  实验室提出，它是一个异步分布式共享存储模型。在

%& 模型中，运行在顶点上的用户自定义程序可以对图中的顶点和边数据进行共享访



问。程序可以访问当前作用的顶点、顶点相连接的边（包括入边和出边），以及相邻的顶

点。

%& 在进行图运算时，顶点是其最小的并行粒度和通信粒度，某个顶点可能被部

署到多台机器上，其中一台机器上的为主顶点（ 2），其余机器上的为镜像顶点

（2），与主顶点的数据保持同步。对边而言，%& 将其唯一部署在某一台机器

上，当图比较密，即边的数目较大时，可以减少边数据的存储量。如图  所示，包含四个

顶点的图使用点切分的方式被分为三个分区，五条边被分配给三个分区，和这些边相连接

的点也被镜像分配至相应的分区，顶点为实线圆，镜像为虚线圆。例如，顶点 / 被  和

 中的边连接，则顶点 / 被镜像分配给  和 。



图 33图的顶点切分

%& 将算法的执行过程抽象成收集（）、执行（）和分发（）

三个步骤。

收集阶段：工作顶点的边，可以是出边或入边，也可以同时包含入边和出边，从邻接

顶点和自身收集数据，并对收集的数据使用用户定义的函数进行运算。这一阶段对顶点和

边都是只读的。

执行阶段：镜像顶点将收集阶段的计算结果发送给主顶点，主顶点对从各个镜像顶点

收集的数据进行聚集运算，并利用聚集结果和上一步的顶点数据，按照用户定义的更新函

数进行计算，更新主顶点的数据，并同步给镜像顶点。在执行阶段中，工作顶点可修改，

边不可修改。

3分发阶段：工作顶点更新完成之后，更新边上的数据，通知对其有依赖的邻接边更新

状态。在分发阶段，工作顶点只读，边上数据可写。

在执行过程中，%& 通过控制三个阶段的读写权限来达到互斥的目的，并行计算

的同步通过主顶点和镜像顶点来实现。

一.3 GraphX 前期准备

一.3.1 了解 Map Reduce 概念

2 和 , 两个词没有什么意义， 的分布式计算框架分为两个阶段，第一个



是 2 阶段，第二个是 , 阶段。2 阶段负责对输入文件进行切分处理，然后汇总再

分组给 , 进行处理，以达到高效的分布式计算效率。

一.3.2 了解 Scala 语法

 很多函数操作和  是一样的。下面的 *++ 函数操作也是基于  的。

一.3.3 了解 RDD

*++ 是  中的抽象数据结构类型，任何数据在  中都被表示为 *++。从编程

的角度来看，*++ 可以简单看成是一个数组。和普通数组的区别是，*++ 中的数据是分

区存储的，这样不同分区的数据就可以分布在不同的机器上，同时可以被并行处理。因此

 应用程序所做的无非是把需要处理的数据转换为 *++，然后对 *++ 进行一系列的变

换和操作从而得到结果。

一.3.3.1 创建 RDD

一.3.3.1.1 从普通数组创建 *++

*++ 可以从普通数组创建出来，也可以从文件系统或者 .+4 中的文件创建出来。

举例：从普通数组创建 *++，里面包含了  到 ' 这 ' 个数字，它们分别在  个分区中。

5678'9:

;*++<=>6/*++<>7?5;

一.3.3.1.1 从文件系统或者 .+4 中的文件创建 *++

举例：读取文件 *@+0@2 来创建 *++，文件中的每一行就是 *++ 中的一个元素

5&648A*@+0@2A:

&;*++<>60*++<>4?5;

虽然还有别的方式可以创建 *++，但在本文中我们主要使用上述两种方式来创建

*++ 以说明 *++ 的 =。

一.3.3.2 RDD 操作清单

一.3.3.3 Map

2 是对 *++ 中的每个元素都执行一个指定的函数来产生一个新的 *++。任何原

*++ 中的元素在新 *++ 中都有且只有一个元素与之对应。

举例：

scala> val a = sc.parallelize(1 to 9, 3) // 第二个参数

表示分区数

5&62865B:

5

!;<=>689999"99C99':

5&

;<=>689999!9999:

上述例子中把原 *++ 中每个元素都乘以  来产生一个新的 *++。

一.3.3.4 map、zip

D2<1;/->8D;-651:;*++<1>

D2D,2D*++,,

*++

D7<1;/->8;*++<1>:;*++<8-91:>

@2

678%8AA9A2A9A2A9AA9AA:9:

&628E:

&



678&:



!;<89=:>6889:9829:9829:989:989::

一.3.3.5 mapPartitions*

2 是 2 的一个变种。2 的输入函数是应用于 *++ 中每个元素，而

2 



的输入函数是应用于每个分区， 也就是把每个分区中的内容作为整体来处理

的。

它的函数定义为：

D2<1;/->8D;=<->65=<1>9;#

6D:;*++<1>

D 即为输入函数，它处理每个分区里面的内容。每个分区中的内容将以 =<->传递

给输入函数 D，D 的输出结果是 =<1>。最终的 *++ 由所有分区经过输入函数处理后的

结果合并起来的。

举例：

5678'9:

5D2D,<->8;=<->:;=<8-9-:>6F

6%<8-9-:>8:

6 8G:F

,6H

;;689,:6,H

I



5282D,:

剩余55页未读，继续阅读

评论收藏

内容反馈

BrotherDongDong

粉丝: 64
资源: 25

第九章 - GraphX源码剖析 20160223

最新资源

第九章 - GraphX源码剖析 20160223

GraphX图数据库的源码剖析

大数据高级开发工程师自学资源

Visual C++音频视频处理技术及工程实践(分卷0)

Visual C++音频视频处理技术及工程实践(含源码2/2)

Visual C++音频视频处理技术及工程实践(分卷9)

Visual C++ 音频/视频 处理技术及工程实践(分卷3)

Visual C++音频/视频处理技术及工程实践(分卷2)

Visual C++音频视频处理技术及工程实践(分卷7)

Visual C++音频视频处理技术及工程实践(分卷6)

Visual C++音频/视频处理技术及工程实践 (分卷1)

Scala-升级版.docx

大数据期末课设~基于spark的气象数据处理与分析

基于spark的图书推荐系统

spark-3.3.1-bin-3.0.0-cdh6.3.2.tgz

全国职业技能大赛大数据赛项十套赛题（shtd）

基于hadoop和echarts的教育大数据可视化系统

Spark气象监测数据分析：代码整合，包括预处理，分析，数据可视化

项目名称：微博热搜情绪分析

大数据面试大总结300页.zip

spark-3.1.3-bin-hadoop3.2.tgz

基于Spark的零售交易数据分析

Link Prediction相似性计算方法示例.rar

实验七：Spark初级编程实践

基于Spark的电影数据集分析

工信部：工业数据分类分级指南（试行）

spark-3.0.0-bin-hadoop3.2.tgz

sbt-1.9.0.tgz

2012phm.zip

PeMS部分公共数据集下载

最新资源

Visual C++ 音频/视频处理技术及工程实践(分卷3)