Spark学习之路 (二十八)分布式图计算系统

Stella981
• 阅读 536

一、引言

  在了解GraphX之前,需要先了解关于通用的分布式图计算框架的两个常见问题:图存储模式图计算模式

二、图存储模式

  巨型图的存储总体上有边分割和点分割两种存储方式。2013年,GraphLab2.0将其存储方式由边分割变为点分割,在性能上取得重大提升,目前基本上被业界广泛接受并使用。

2.1 边分割(Edge-Cut)

每个顶点都存储一次,但有的边会被打断分到两台机器上。这样做的好处是节省存储空间;坏处是对图进行基于边的计算时,对于一条两个顶点被分到不同机器上的边来说,要跨机器通信传输数据,内网通信流量大。

2.2 点分割(Vertex-Cut)

每条边只存储一次,都只会出现在一台机器上。邻居多的点会被复制到多台机器上,增加了存储开销,同时会引发数据同步问题。好处是可以大幅减少内网通信量。

2.3 对比

  虽然两种方法互有利弊,但现在是点分割占上风,各种分布式图计算框架都将自己底层的存储形式变成了点分割。主要原因有以下两个。

  磁盘价格下降,存储空间不再是问题,而内网的通信资源没有突破性进展,集群计算时内网带宽是宝贵的,时间比磁盘更珍贵。这点就类似于常见的空间换时间的策略。

  在当前的应用场景中,绝大多数网络都是“无尺度网络”,遵循幂律分布,不同点的邻居数量相差非常悬殊。而边分割会使那些多邻居的点所相连的边大多数被分到不同的机器上,这样的数据分布会使得内网带宽更加捉襟见肘,于是边分割存储方式被渐渐抛弃了。

三、图计算模式

  目前的图计算框架基本上都遵循BSP(Bulk Synchronous Parallell)计算模式。Bulk Synchronous Parallell,即整体同步并行,它将计算分成一系列的超步(superstep)的迭代(iteration)。从纵向上看,它是一个串行模型,而从横向上看,它是一个并行的模型,每两个superstep之间设置一个栅栏(barrier),即整体同步点,确定所有并行的计算都完成后再启动下一轮superstep。

3.1 超步

  每一个超步(superstep)包含三部分内容:

1.计算compute,每一个processor利用上一个superstep传过来的消息和本地的数据进行本地计算;

2.消息传递,每一个processor计算完毕后,将消息传递个与之关联的其它processors;

3.整体同步点,用于整体同步,确定所有的计算和消息传递都进行完毕后,进入下一个superstep。

3.2 Pregel模型——像顶点一样思考

Pregel借鉴MapReduce的思想,采用消息在点之间传递数据的方式,提出了“像顶点一样思考”(Think Like A Vertex)的图计算模式,采用消息在点之间传递数据的方式,让用户无需考虑并行分布式计算的细节,只需要实现一个顶点更新函数,让框架在遍历顶点时进行调用即可。

常见的代码模板如下:

Spark学习之路 (二十八)分布式图计算系统

上图简要地描述了Pregel的计算模型:

1.master将图进行分区,然后将一个或多个partition分给worker;

2.worker为每一个partition启动一个线程,该线程轮询partition中的顶点,为每一个active状态的顶点调用compute方法;

3.compute完成后,按照edge的信息将计算结果通过消息传递方式传给其它顶点;

4.完成同步后,重复执行2,3操作,直到没有active状态顶点或者迭代次数到达指定数目。

这个模型虽然简洁,但很容易发现它的缺陷。对于邻居数很多的顶点,它需要处理的消息非常庞大,而且在这个模式下,它们是无法被并发处理的。所以对于符合幂律分布的自然图,这种计算模型下很容易发生假死或者崩溃。

作为第一个通用的大规模图处理系统,pregel已经为分布式图处理迈进了不小的一步,这点不容置疑,但是pregel在一些地方也不尽如人意:

1.在图的划分上,采用的是简单的hash方式,这样固然能够满足负载均衡,但是hash方式并不能根据图的连通特性进行划分,导致超步之间的消息传递开销可能会是影响性能的最大隐患。

2.简单的checkpoint机制只能向后式地将状态恢复到当前S超步的几个超步之前,要到达S还需要重复计算,这其实也浪费了很多时间,因此如何设计checkpoint,使得只需重复计算故障worker的partition的计算节省计算甚至可以通过checkpoint直接到达故障发生前一超步S,也是一个很需要研究的地方。

3.BSP模型本身有其局限性,整体同步并行对于计算快的worker长期等待的问题无法解决。

4.由于pregel目前的计算状态都是常驻内存的,对于规模继续增大的图处理可能会导致内存不足,如何解决尚待研究。

3.3 GAS模型——邻居更新模型

 相比Pregel模型的消息通信范式,GraphLab的GAS模型更偏向共享内存风格。它允许用户的自定义函数访问当前顶点的整个邻域,可抽象成Gather、Apply和Scatter三个阶段,简称为GAS。相对应,用户需要实现三个独立的函数gather、apply和scatter。常见的代码模板如下所示:

Spark学习之路 (二十八)分布式图计算系统

由于gather/scatter函数是以单条边为操作粒度,所以对于一个顶点的众多邻边,可以分别由相应的worker独立调用gather/scatter函数。这一设计主要是为了适应点分割的图存储模式,从而避免Pregel模型会遇到的问题。

1.Gather阶段

工作顶点的边(可能是所有边,也有可能是入边或者出边)从领接顶点和自身收集数据,记为gather_data_i,各个边的数据graphlab会求和,记为sum_data。这一阶段对工作顶点、边都是只读的。

2.Apply阶段

Mirror将gather计算的结果sum_data发送给master顶点,master进行汇总为total。Master利用total和上一步的顶点数据,按照业务需求进行进一步的计算,然后更新master的顶点数据,并同步mirror。Apply阶段中,工作顶点可修改,边不可修改。

3.Scatter阶段

工作顶点更新完成之后,更新边上的数据,并通知对其有依赖的邻结顶点更新状态。这scatter过程中,工作顶点只读,边上数据可写。

在执行模型中,graphlab通过控制三个阶段的读写权限来达到互斥的目的。在gather阶段只读,apply对顶点只写,scatter对边只写。并行计算的同步通过master和mirror来实现,mirror相当于每个顶点对外的一个接口人,将复杂的数据通信抽象成顶点的行为。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Stella981 Stella981
2年前
Spark GraphX图算法应用【分区策略、PageRank、ConnectedComponents,TriangleCount】
一.分区策略  !(https://img2018.cnblogs.com/ibeta/1343081/201911/1343081201911271536266281023000587.png)  GraphX采用顶点分割的方式进行分布式图分区。GraphX不会沿着边划分图形,而是沿着顶点划分图形,这可以减少通信和存储的开
Stella981 Stella981
2年前
Spark Graphx
Graphx   概述      SparkGraphX是一个分布式图处理框架,它是基于Spark平台提供对图计算和图挖掘简洁易用的而丰富的接口,极大的方便了对分布式图处理的需求。      众所周知·,社交网络中人与人之间有很多关系链,例如Twitter、Facebook、微博和微信等,这些都是大数据产生的地方都需要图计算,现
Stella981 Stella981
2年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
2年前
Nebula 架构剖析系列(一)图数据库的存储设计
摘要在讨论某个数据库时,存储(Storage)和计算(QueryEngine)通常是讨论的热点,也是爱好者们了解某个数据库不可或缺的部分。每个数据库都有其独有的存储、计算方式,今天就和图图来学习下图数据库NebulaGraph的存储部分。Nebula的Storage包含两个部分,一是meta相关的存储,我们
Wesley13 Wesley13
2年前
(绝对有用)iOS获取UUID,并使用keychain存储
UDID被弃用,使用UUID来作为设备的唯一标识。获取到UUID后,如果用NSUserDefaults存储,当程序被卸载后重装时,再获得的UUID和之前就不同了。使用keychain存储可以保证程序卸载重装时,UUID不变。但当刷机或者升级系统后,UUID还是会改变的。但这仍是目前为止最佳的解决办法了,如果有更好的解决办法,欢迎留言。(我整理的解决办法的参
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Easter79 Easter79
2年前
Storm VS Flink ——性能对比
!(https://oscimg.oschina.net/oscnet/2cec00eb2dccf5fdec8def77207da253a86.jpg)1.背景ApacheFlink和ApacheStorm是当前业界广泛使用的两个分布式实时计算框架。其中ApacheStorm(以下简称“Storm”)在美团点评实时
Stella981 Stella981
2年前
CPU推理性能提高数十倍,旷视天元计算图、MatMul优化深度解读
  机器之心发布  机器之心编辑部  !(http://dingyue.ws.126.net/2020/0806/6a6e4896j00qemtzy001ad000p000aop.jpg)本文针对旷视天元深度学习框架在推理优化过程中所涉及的计算图优化与MatMul优化进行深度解读。  背景及引言  在深度学