厦门大学：《大数据技术原理与应用》课程教学资源（PPT课件讲稿，2017）第11章 图计算

提纲 ·11.1图计算简介 112 Pregel简介 113 Pregel图计算模型 114 Pregel的c++AP 115 Pregell的体系结构 116 Pregel的应用实例 117 Pregel和 MapReduce实现 PageRank算法的对 118Hama的安装和使用 本PPT是如下教材的配套讲义 《大数据技术原理与应用 —概念、存储、处理、分析与应用》 (2017年2月第2版) SBN:978-7-115443304 厦门大学林子雨编著,人民邮电出版社 欢迎访问《大数据技术原理与应用》教材官方网站: http://dblab.xmu.edu.cn/post/bigdata 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 提纲 • 11.1图计算简介 • 11.2Pregel简介 • 11.3Pregel图计算模型 • 11.4Pregel的C++ API • 11.5Pregel的体系结构 • 11.6Pregel的应用实例 • 11.7 Pregel和MapReduce实现PageRank算法的对比 • 11.8 Hama的安装和使用 欢迎访问《大数据技术原理与应用》教材官方网站： http://dblab.xmu.edu.cn/post/bigdata 本PPT是如下教材的配套讲义： 《大数据技术原理与应用 ——概念、存储、处理、分析与应用》 （2017年2月第2版） ISBN:978-7-115-44330-4 厦门大学 林子雨 编著，人民邮电出版社

●11图计算简介 ·11.1.1图结构数据 ·11.1.2传统图计算解决方案的不足之处 ·11.1.3图计算通用软件 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1 图计算简介 • 11.1.1 图结构数据 • 11.1.2 传统图计算解决方案的不足之处 • 11.1.3 图计算通用软件

●111图结构数据 许多大数据都是以大规模图或网络的形式呈现,如社交网 络、传染病传播途径、交通事故对路网的影响 ˉ许多非图结构的大数据,也常常会被转换为图模型后进行 分析 图数据结构很好地表达了数据之间的关联性 关联性计算是大数据计算的核心——通过获得数据的关联 性,可以从噪音很多的海量数据中抽取有用的信息 比如,通过为购物者之间的关系建模,就能很快找到口 味相似的用户,并为之推荐商品 或者在社交网络中,通过传播关系发现意见领袖 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn •许多大数据都是以大规模图或网络的形式呈现，如社交网 络、传染病传播途径、交通事故对路网的影响 •许多非图结构的大数据，也常常会被转换为图模型后进行 分析 •图数据结构很好地表达了数据之间的关联性 •关联性计算是大数据计算的核心——通过获得数据的关联 性，可以从噪音很多的海量数据中抽取有用的信息 –比如，通过为购物者之间的关系建模，就能很快找到口 味相似的用户，并为之推荐商品 –或者在社交网络中，通过传播关系发现意见领袖 11.1.1 图结构数据

●1121传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题: (1)常常表现出比较差的内存访问局部性 (2)针对单个顶点的处理工作过少 (3)计算过程中伴随着并行度的改变 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1.2 传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性 （2）针对单个顶点的处理工作过少 （3）计算过程中伴随着并行度的改变

1112传统图计算解决方案的不足之处 针对大型图(比如社交网络和网络图)的计算问题,可能的解决方案及 其不足之处具体如下: (1)为特定的图应用定制相应的分布式实现:通用性不好 (2)基于现有的分布式计算平台进行图计算:在性能和易用性方面往 往无法达到最优 现有的并行计算框架像 MapReduce还无法满足复杂的关联性计算 MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架,在表达多迭代、稀疏结构和细粒度数据时,力不从心 比如,有公司利用 MapReduce进行社交用户推荐,对于5000万注 册用户,50亿关系对,利用10台机器的集群,需要超过10个小时的 计算 (3)使用单机的图算法库:比如BGL、LEAD、 NetworkX、JDSL、 Standford GraphBase和FGL等,但是,在可以解决的问题的规模方面 具有很大的局限性 (4)使用已有的并行图计算系统:比如, Parallel bcl和 CGM Graph, 实现了很多并行图算法,但是,对大规模分布式系统非常重要的一些方 面(比如容错),无法提供较好的支持 大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1.2 传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及 其不足之处具体如下： •（1）为特定的图应用定制相应的分布式实现：通用性不好 •（2）基于现有的分布式计算平台进行图计算：在性能和易用性方面往 往无法达到最优 •现有的并行计算框架像MapReduce还无法满足复杂的关联性计算 •MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架，在表达多迭代、稀疏结构和细粒度数据时，力不从心 •比如，有公司利用MapReduce进行社交用户推荐，对于5000万注 册用户，50亿关系对，利用10台机器的集群，需要超过10个小时的 计算 •（3）使用单机的图算法库：比如BGL、LEAD、NetworkX、JDSL、 Standford GraphBase和FGL等，但是，在可以解决的问题的规模方面 具有很大的局限性 •（4）使用已有的并行图计算系统：比如，Parallel BGL和CGM Graph， 实现了很多并行图算法，但是，对大规模分布式系统非常重要的一些方 面（比如容错），无法提供较好的支持

11.13图计算通用软件 传统的图计算解决方案无法解决大型图的计算问题,因此, 就需要设计能够用来解决这些问题的通用图计算软件 ·针对大型图的计算,目前通用的图计算软件主要包括两种: 第一种主要是基于遍历算法的、实时的图数据库,如 Neo4、 OrientDB、DEX和 Infinite Graph 第二种则是以图顶点为中心的、基于消息传递批处理的并 行引擎,如 GoldenOrb、 Graph、 Pregel和Hama,这些 图处理软件主要是基于BSP模型实现的并行图处理系统 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn • 传统的图计算解决方案无法解决大型图的计算问题，因此， 就需要设计能够用来解决这些问题的通用图计算软件 • 针对大型图的计算，目前通用的图计算软件主要包括两种： – 第一种主要是基于遍历算法的、实时的图数据库，如 Neo4j、OrientDB、DEX和 Infinite Graph – 第二种则是以图顶点为中心的、基于消息传递批处理的并 行引擎，如GoldenOrb、Giraph、Pregel和Hama，这些 图处理软件主要是基于BSP模型实现的并行图处理系统 11.1.3 图计算通用软件

11.1.3图计算通用软件 次BSP( Bulk Synchronous Parallel Computing Model,又称“大同步”模型)计算过 程包括一系列全局超步(所谓的超步就是计算中的一次迭代),每个超步主要包括三 个组件 局部计算:每个参与的处理器都有自身的计算任务,它们只读取存储在本地内存中的 值,不同处理器的计算任务都是异步并且独立的 通讯:处理器群相互交换数据,交换的形式是,由一方发起推送(put)和获取(get)操作 栅栏同步( Barrier Synchronization):当一个处理器遇到“路障”(或栅栏),会等到 其他所有处理器完成它们的计算步骤;每一次同步也是一个超步的完成和下一个超步 的开始 处理器 用户定义函数 F/vertex 局部计算 O 栅栏同步 超级步(S1) 超级步5级步(S+1) 图9-1一个超步的垂直结构图 大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1.3 图计算通用软件 一次BSP(Bulk Synchronous Parallel Computing Model，又称“大同步”模型)计算过 程包括一系列全局超步（所谓的超步就是计算中的一次迭代），每个超步主要包括三 个组件： •局部计算：每个参与的处理器都有自身的计算任务，它们只读取存储在本地内存中的 值，不同处理器的计算任务都是异步并且独立的 •通讯：处理器群相互交换数据，交换的形式是，由一方发起推送(put)和获取(get)操作 •栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或栅栏），会等到 其他所有处理器完成它们的计算步骤；每一次同步也是一个超步的完成和下一个超步 的开始 处理器 局部计算 通讯 栅栏同步 图9-1 一个超步的垂直结构图

●112eg简介 谷歌公司在2003年到2004年公布了GFS、 MapReduce和 Big Table,成为 后来云计算和 Hadoop项目的重要基石 谷歌在后 Hadoop时代的新“三驾马车”— Caffeine、 Dremel和 Pregel 再一次影响着圈子与大数据技术的发展潮流 ˉ Pregel是一种基于BSP模型实现的并行图处理系统 为了解决大型图的分布式计算问题, Pregel搭建了一套可扩展的、有容错 机制的平台,该平台提供了一套非常灵活的APl,可以描述各种各样的图 计算 亼^ regel作为分布式图计算的计算框架,主要用于图遍历、最短路径、 geRak计算等等 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.2 Pregel简介 •谷歌公司在2003年到2004年公布了GFS、MapReduce和BigTable，成为 后来云计算和Hadoop项目的重要基石 •谷歌在后Hadoop时代的新“三驾马车”——Caffeine、Dremel和Pregel ，再一次影响着圈子与大数据技术的发展潮流 •Pregel是一种基于BSP模型实现的并行图处理系统 •为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容错 机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的图 计算 •Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、 PageRank计算等等

113 Pregel图计算模型 11.3.1有向图和顶点 11.32顶点之间的消息传递 1133 Pregel的计算过程 ·1134实例 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.3 Pregel图计算模型 • 11.3.1 有向图和顶点 • 11.3.2 顶点之间的消息传递 • 11.3.3 Pregel的计算过程 • 11.3.4 实例

11.3.1有向图和顶点 ˉ Pregel计算模型以有向图作为输入 有向图的每个顶点都有一个 String类型的顶点|D 每个顶点都有一个可修改的用户自定义值与之关联 每条有向边都和其源顶点关联,并记录了其目标顶点ID 边上有一个可修改的用户自定义值与之关联 边e1 顶点 sing类型的顶点D 2)可修改的用户自定义值 边上有一个可修改的用户自定义值 4 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu

《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.3.1 有向图和顶点 •Pregel计算模型以有向图作为输入 •有向图的每个顶点都有一个String类型的顶点ID •每个顶点都有一个可修改的用户自定义值与之关联 •每条有向边都和其源顶点关联，并记录了其目标顶点ID •边上有一个可修改的用户自定义值与之关联 String类型的顶点ID 可修改的用户自定义值 边上有一个可修改的用户自定义值 边e1 顶点