第7章图计算
第7章 图计算
提纲 7.1图计算简介 7.2 Prege简介 7.3 Prege图计算模型 74 Pregel的c++AP 75 Pregel的体系结构 7.6 Prege的应用实例 77 Pregel和 MapReduce实现 PageRank算法的对比 7.8Hama的安装和使用
提纲 • 7.1 图计算简介 • 7.2 Pregel简介 • 7.3 Pregel图计算模型 • 7.4 Pregel的C++ API • 7.5 Pregel的体系结构 • 7.6 Pregel的应用实例 • 7.7 Pregel和MapReduce实现PageRank算法的对比 • 7.8 Hama的安装和使用
7.1图计算简介 ·7.1.1图结构数据 7.1.2传统图计算解决方案的不足之处 7.1.3图计算通用软件
7.1 图计算简介 • 7.1.1 图结构数据 • 7.1.2 传统图计算解决方案的不足之处 • 7.1.3 图计算通用软件
7.1.1图结构数据 许多大薮据都是以大规模图或网络的形式呈现,如社交网 络、传染病传播途径、交通事故对路网的影响 ·许多非图结构的大数据,也常常会被转换为图模型后进行 分析 ·图数据结构很好地表达了数据之间的关联性 ·关联性计算是大数据计算的核心——通过获得数据的关联 性,可以从噪音很多的海量数据中抽取有用的信息 比如,通过为购物者之间的关系建模,就能很快找到口 味相似的用户,并为之推荐商品 或者在社交网络中,通过传播关系发现意见领袖
•许多大数据都是以大规模图或网络的形式呈现，如社交网 络、传染病传播途径、交通事故对路网的影响 •许多非图结构的大数据，也常常会被转换为图模型后进行 分析 •图数据结构很好地表达了数据之间的关联性 •关联性计算是大数据计算的核心——通过获得数据的关联 性，可以从噪音很多的海量数据中抽取有用的信息 –比如，通过为购物者之间的关系建模，就能很快找到口 味相似的用户，并为之推荐商品 –或者在社交网络中，通过传播关系发现意见领袖 7.1.1 图结构数据
7.1.2传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题: (1)常常表现出比较差的内存访问局部性 (2)针对单个顶点的处理工作过少 (3)计算过程中伴随着并行度的改变
7.1.2传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性 （2）针对单个顶点的处理工作过少 （3）计算过程中伴随着并行度的改变
7.1.2传统图计算解决方案的不足之处 针对大型图(比如社交网络和网络图)的计算问题,可能的解决方案及 其不足之处具体如下 (1)为特定的图应用定制相应的分布式实现:通用性不好 ·(2)基于现有的分布式计算平台进行图计算:在性能和易用性方面往 往无法达到最优 现有的并行计算框架像 MapReduce还无法满足复杂的关联性计算 MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架,在表达多迭代、稀疏结构和细粒度数据时,力不从心 比如,有公司利用 MapReduce进行社交用户推荐,对于5000万注 册用户,50亿关系对,利用10台机器的集群,需要超过10个小时的 计算 ·(3)使用单机的图算法库:比如BGL、LEAD、 NetworkX、JDsL Standford GraphBase和FGL等,但是,在可以解决的问题的规模方面 具有很大的局限性 (4)使用已有的并行图计算系统:比如, Parallel BGL和 CGM Graph, 实现了很多并行图算法,但是,对大规模分布式系统非常重要的一些方 面(比如容错),无法提供较好的支持
7.1.2传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及 其不足之处具体如下： •（1）为特定的图应用定制相应的分布式实现：通用性不好 •（2）基于现有的分布式计算平台进行图计算：在性能和易用性方面往 往无法达到最优 •现有的并行计算框架像MapReduce还无法满足复杂的关联性计算 •MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架，在表达多迭代、稀疏结构和细粒度数据时，力不从心 •比如，有公司利用MapReduce进行社交用户推荐，对于5000万注 册用户，50亿关系对，利用10台机器的集群，需要超过10个小时的 计算 •（3）使用单机的图算法库：比如BGL、LEAD、NetworkX、JDSL、 Standford GraphBase和FGL等，但是，在可以解决的问题的规模方面 具有很大的局限性 •（4）使用已有的并行图计算系统：比如，Parallel BGL和CGM Graph， 实现了很多并行图算法，但是，对大规模分布式系统非常重要的一些方 面（比如容错），无法提供较好的支持
7.1.3图计算通用软件 ·传统的图计算解决方案无法解决大型图的计算问题,因此, 就需要设计能够用来解决这些问题的通用图计算软件 ·针对大型图的计算,目前通用的图计算软件主要包括两种 第一种主要是基于遍历算法的、实时的图数据库,如 Neo4j、 OrientDB、DEX和 Infinite Graph 第二种则是以图顶点为中心的、基于消息传递批处理的并 行引擎,如 GoldenOrb、 Graph、 Pregel和Hama,这些 图处理软件主要是基于BSP模型实现的并行图处理系统
• 传统的图计算解决方案无法解决大型图的计算问题，因此， 就需要设计能够用来解决这些问题的通用图计算软件 • 针对大型图的计算，目前通用的图计算软件主要包括两种： – 第一种主要是基于遍历算法的、实时的图数据库，如 Neo4j、OrientDB、DEX和 Infinite Graph – 第二种则是以图顶点为中心的、基于消息传递批处理的并 行引擎，如GoldenOrb、Giraph、Pregel和Hama，这些 图处理软件主要是基于BSP模型实现的并行图处理系统 7.1.3 图计算通用软件
7.1.3图计算通用软件 次BSP( Bulk Synchronous Parallel Computing Model,又称“大同步”模型)计算过 程包括一系列全局超步(所谓的超步就是计算中的一次迭代),每个超步主要包括三 个组件 局部计算:每个参与的处理器都有自身的计算任务,它们只读取存储在本地内存中的 值,不同处理器的计算任务都是异步并且独立的 ˉ通讯:处理器群相互交换数据,交换的形式是,由一方发起推送(puυ和获取(get)操作 栅栏同步( Barrier Synchronization):当一个处理器遇到“路障”(或栅栏),会等到 其他所有处理器完成它们的计算步骤;每一次同步也是一个超步的完成和下一个超步 的开始 处理器 用户定义函数 局部计算 通讯 栅栏同步 超级步(S1) 超级步5 超级步(S+1) 图9-1一个超步的垂直结构图
7.1.3图计算通用软件 一次BSP(Bulk Synchronous Parallel Computing Model，又称“大同步”模型)计算过 程包括一系列全局超步（所谓的超步就是计算中的一次迭代），每个超步主要包括三 个组件： •局部计算：每个参与的处理器都有自身的计算任务，它们只读取存储在本地内存中的 值，不同处理器的计算任务都是异步并且独立的 •通讯：处理器群相互交换数据，交换的形式是，由一方发起推送(put)和获取(get)操作 •栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或栅栏），会等到 其他所有处理器完成它们的计算步骤；每一次同步也是一个超步的完成和下一个超步 的开始 图9-1 一个超步的垂直结构图
7.2 Pregel简介 谷歌公司在2003年到2004年公布了GFS、 MapReduce和 Big Table,成为 后来云计算和 Hadoop项目的重要基石 谷歌在后 Hadoop时代的新“三驾马车”— -Caffeine、 Dremel和 Pregel 再一次影响着圈子与大数据技术的发展潮流 pregel是一种基于BSP模型实现的并行图处理系统 为了解决大型图的分布式计算问题, Pregel搭建了一套可扩展的、有容错 机制的平台,该平台提供了一套非常灵活的AP,可以描述各种各样的图 计算 pregel作为分布式图计算的计算框架,主要用于图遍历、最短路径、 PageRank计算等等
7.2 Pregel简介 •谷歌公司在2003年到2004年公布了GFS、MapReduce和BigTable，成为 后来云计算和Hadoop项目的重要基石 •谷歌在后Hadoop时代的新“三驾马车”——Caffeine、Dremel和Pregel ，再一次影响着圈子与大数据技术的发展潮流 •Pregel是一种基于BSP模型实现的并行图处理系统 •为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容错 机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的图 计算 •Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、 PageRank计算等等
7.3 Pregel图计算模型 7.3.1 有向图和顶点 732顶点之间的消息传递 ·73.3 Pregel的计算过程 7.34 实例
7.3 Pregel图计算模型 • 7.3.1 有向图和顶点 • 7.3.2 顶点之间的消息传递 • 7.3.3 Pregel的计算过程 • 7.3.4 实例