分布式图计算框架的目的：是将对于巨型图的各种操作包装为简单的接口，让分布式存
储、并行计算等复杂问题对上层透明，从而使复杂网络和图算法的工程师，更加聚焦在图相关的模型设计和使用上，而不用关心底层的分布式细节
需要解决两个通用问题：图存储模式和图计算模式
图存储模式
巨型图的存储总体上有边分割和点分割两种存储方式。2013年，GraphLab2.0将其存储方式由边分割变为点分割，在性能上取得重大提升，目前基本上被业界广泛接受并使用。
边分割：每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的好处是节省存储空间；坏处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大。
点分割：每条边只存储一次，都只会出现在一台机器上。邻居多的点会被复制到多台机器上，增加了存储开销，同时会引发数据同步问题。好处是可以大幅减少内网通信量。
现在是点分割占上风，各种分布式图计算框架都将自己底层的存储形式变成了点分割。主要原因有以下两个。
磁盘价格下降，存储空间不再是问题，而内网的通信资源没有突破性进展，集群计算时内网带宽是宝贵的，时间比磁盘更珍贵。这点就类似于常见的空间换时间的策略。 在当前的应用场景中，绝大多数网络都是“无尺度网络”，遵循幂律分布，不同点的邻居数量相差非常悬殊。而边分割会使那些多邻居的点所相连的边大多数被分到不同的机器上，这样的数据分布会使得内网带宽更加捉襟见肘，于是边分割存储方式被渐渐抛弃了。
图计算模型
目前的图计算框架基本上都遵循BSP（Bulk Synchronous Parallell）计算模式。在BSP中，一次计算过程由一系列全局超步组成，每一个超步由并发计算、通信和栅栏同步三个步骤组成。同步完成，标志着这个超步的完成及下一个超步的开始。BSP模式很简洁。基于BSP模式，目前有两种比较成熟的图计算模型。
Pregel模型——像顶点一样思考
2010年，Google的新的三架马车Caffeine、Pregel、Dremel发布。随着Pregel一起，BSP模型广为人知。Pregel借鉴MapReduce的思想，提出了“像顶点一样思考”（Think Like A Vertex）的图计算模式，让用户无需考虑并行分布式计算的细节，只需要实现一个顶点更新函数，让框架在遍历顶点时进行调用即可。
这个模型虽然简洁，但很容易发现它的缺陷。对于邻居数很多的顶点，它需要处理的消息非常庞大，而且在这个模式下，它们是无法被并发处理的。所以对于符合幂律分布的自然图，这种计算模型下很容易发生假死或者崩溃。
GAS模型——邻居更新模型
相比Pregel模型的消息通信范式，GraphLab的GAS模型更偏向共享内存风格。它允许用户的自定义函数访问当前顶点的整个邻域，可抽象成Gather、Apply和Scatter三个阶段，简称为GAS。相对应，用户需要实现三个独立的函数gather、apply和scatter。
由于gather/scatter函数是以单条边为操作粒度，所以对于一个顶点的众多邻边，可以分别由相应的worker独立调用gather/scatter函数。这一设计主要是为了适应点分割的图存储模式，从而避免Pregel模型会遇到的问题。
Giraph
Giraph是apache基金会开源项目之一，被定义为迭代式图处理系统。他架构在hadoop之上，提供了图处理接口，专门处理大数据的图问题。
Giraph计算的输入是由点和直连的边组成的图。例如，点可以表示人，边可以表示朋友请求。每个顶点保存一个值，每个边也保存一个值。输入不仅取决于图的拓扑逻辑，也包括定点和边的初始值。
Giraph应用还需要考虑Hadoop的兼容性。 Giraph的存在很有必要，现在的大数据的图问题又很多，例如表达人与人之间的关系的有社交网络，搜索引擎需要经常计算网页与网页之间的关系，而map-reduce接口不太适合实现图算法。
构成图的基本元素有哪些？
构成图的基本元素有顶点和边，边可以有权重和方向。 Giraph如何表示图？
Giraph里同样也有顶点和边，Giraph中的顶点也是有值的，可以用于保存计算的中间结果。在Giraph图处理模型中，顶点是一切的中心，运算也是围绕着顶点进行的，顶点可以收发消息，这里的消息跟通讯中的消息不同，这里的消息指的是从上一个计算步骤接收信息，在顶点进行计算，并把计算好的结果通过消息发给下一个顶点。而顶点计算的输入数据就是输入的消息、顶点的当前的值。一个顶点可以有多条输入的消息，也可以有多条输出的消息，把这些消息发给与当前顶点相连的边的另一端的顶点。 Giraph的应用：用于分析用户或者内容之间的联系或重要性。
GraphX
在设计GraphX时，点分割和GAS都已成熟，并在设计和编码中针对它们进行了优化，在功能和性能之间寻找最佳的平衡点。如同Spark本身，每个子模块都有一个核心抽象。GraphX的核心抽象是Resilient Distributed Property Graph，一种点和边都带属性的有向多重图。它扩展了Spark RDD的抽象，有Table和Graph两种视图，而只需要一份物理存储。两种视图都有自己独有的操作符，从而获得了灵活操作和执行效率。
如同Spark，GraphX的代码非常简洁。GraphX的核心代码只有3千多行，而在此之上实现的Pregel模型，只要短短的20多行。GraphX的代码结构其中大部分的实现，都是围绕Partition的优化进行的。这在某种程度上说明了点分割的存储和相应的计算优化，的确是图计算框架的重点和难点。
可以看到，GraphX设计这个模型的用意。它综合了Pregel和GAS两者的优点，即接口相对简单，又保证性能，可以应对点分割的图存储模式，胜任符合幂律分布的自然图的大型计算。
GraphX也提供了一套图算法工具包，方便用户对图进行分析。
GraphLab
GraphLab是面向机器学习的流处理并行框架。GraphLab将数据抽象成Graph结构，将算法的执行过程抽象成Gather、Apply、Scatter三个步骤。其并行的核心思想是对顶点的切分。 数据模型：GRAPH
顶点是其最小并行粒度和通信粒度，边是机器学习算法中数据依赖性的表现方式。
对于某个顶点，其被部署到多台机器，一台机器作为master顶点，其余机器上作为mirror。Master作为所有mirror的管理者，负责给mirror安排具体计算任务;mirror作为该顶点在各台机器上的代理执行者，与master数据的保持同步。
对于某条边，GraphLab将其唯一部署在某一台机器上，而对边关联的顶点进行多份存储，解了边数据量大的问题。
同一台机器上的所有edge（边）和vertex（顶点）构成local graph,在每台机器上，存在本地id到全局id的映射表。vertex是一个进程上所有线程共享的，在并行计算过程中，各个线程分摊进程中所有顶点的gather->apply->scatter操作。
执行模型：GATHER-APPLY-SCATTER
每个顶点每一轮迭代经过gather->apple->scatter三个阶段。
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相当于每个顶点对外的一个接口人，将复杂的数据通信抽象成顶点的行为。
基础组件层
提供Graphlab数据传输、多线程管理等基础并行结构的组件模块，下面将主要介绍其通信、数据序列化、数据交换、多线程管理四个功能模块。
1) 通信(dc_tcp_comm.cpp)
Graphlab基于TCP协议的长连接在机器之间进行数据通信。在Graphlab初始化阶段，所有机器建立连接，将socket数据存储在std::vector
Graphlab使用单独的线程来接收和发送数据，其中接收或发送都可以配置多个线程，默认每个线程中负责与64台机器进行通信。在接收连接中，tcp_comm基于libevent采用epoll的方式获取连接到达的通知，效率高。 需要补充的是，Graphlab在数据通信中，并没有采用MPI的接口，但在源码中封装了MPI_tools，其用途是在distributed_control::init时，获取系统参数(包括机器IP和端口)提供两种方式，一种是系统配置中初始化，一种是通过MPI接口实现（dc_init_from_mpi::init_param_from_mpi）。
2) 数据序列化(oarchive & iarchive)
Oarchive通过重载操作符>>将对象序列化后写入ostream中，在Graphlab中对于POD( Plain Old Data)和非POD数据区分对待， POD类型的数据直接转为为char*写入ostream, 而非POD数据需要用户实现save方法，否则将抛出异常。iarchive的过程与oarchive的过程相反。
所有通过rpc传输的数据都通过oarchive和iarchive转化为stream，比如vertex_program, vertex_data。
3) 数据传输流(buffered_stream_send2.cpp)
Oarchive，iarchive是数据序列化的工具， 在实际的传输过程中，数据并没有立即发送出去，而是缓存在buffered_stream_send。
4) Pthread_tools：
Thread类封装了lpthread的方法
提供thread_group管理线程队列
封装了锁、信号量、条件变量等同步方法。
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库图计算在线全文阅读。
相关推荐：
