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

提纲 9.1图计算简介 92 Pregel简介 9.3 Pregel图计算模型 9.4 Pregel的c++AP 9.5Pege的体系结构 9.6 Pregel的应用实例 97Hama的安装和使用 本PPT是如下教材的配套讲义: 21世纪高等教育计算机规划教材 《大数据技术原理与应用 概念、存储、处理、分析与应用》 (2015年8月第1版) 厦门大学林子雨编著,人民邮电出版社 SBN:978-7115392879 欢迎访问《大数据技术原理与应用》教材官方网站: http:/dblab.xmu.edu.cn/post/bigdata 欢迎访问“中国高校大数据课程公共服务平台”旗下 子栏目“大数据课程学生服务站”,为学生学习大数 据课程提供全方位、一站式免费服务 http://dblab.xmu.edu.cn/post/4331/ 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 xmu. edu. cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 提纲 • 9.1 图计算简介 • 9.2 Pregel简介 • 9.3 Pregel图计算模型 • 9.4 Pregel的C++ API • 9.5 Pregel的体系结构 • 9.6 Pregel的应用实例 • 9.7 Hama的安装和使用 本PPT是如下教材的配套讲义： 21世纪高等教育计算机规划教材 《大数据技术原理与应用 ——概念、存储、处理、分析与应用》 （2015年8月第1版） 厦门大学 林子雨 编著，人民邮电出版社 ISBN:978-7-115-39287-9 欢迎访问《大数据技术原理与应用》教材官方网站： http://dblab.xmu.edu.cn/post/bigdata 欢迎访问“中国高校大数据课程公共服务平台”旗下 子栏目“大数据课程学生服务站”，为学生学习大数 据课程提供全方位、一站式免费服务： http://dblab.xmu.edu.cn/post/4331/

●91图计算简介 ·9.1.1图结构数据 ·9.1.2传统图计算解决方案的不足之处 ·9.1.3图计算通用软件 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.1 图计算简介 • 9.1.1 图结构数据 • 9.1.2 传统图计算解决方案的不足之处 • 9.1.3 图计算通用软件

91.1图结构数据 许多大数据都是以大规模图或网络的形式呈现 许多非图结构的大数据,也常常会被转换为图模型后进 行分析 图数据结构很好地表达了数据之间的关联性 关联性计算是大数据计算的核心—通过获得数据的关 联性,可以从噪音很多的海量数据中抽取有用的信息 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn •许多大数据都是以大规模图或网络的形式呈现 •许多非图结构的大数据，也常常会被转换为图模型后进 行分析 •图数据结构很好地表达了数据之间的关联性 •关联性计算是大数据计算的核心——通过获得数据的关 联性，可以从噪音很多的海量数据中抽取有用的信息 9.1.1 图结构数据

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

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

912传统图计算解决方案的不足之处 针对大型图(比如社交网络和网络图)的计算问题,可 能的解决方案及其不足之处具体如下: (1)为特定的图应用定制相应的分布式实现 ·(2)基于现有的分布式计算平台进行图计算 ·(3)使用单机的图算法库:比如BGL、LEAD、 NetworkX、JDSL、 Standford GraphBase和FGL等 (4)使用已有的并行图计算系统:比如,Parl|lel BGL和 CGM Graph,实现了很多并行图算法 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.1.2传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可 能的解决方案及其不足之处具体如下： •（1）为特定的图应用定制相应的分布式实现 •（2）基于现有的分布式计算平台进行图计算 •（3）使用单机的图算法库：比如BGL、LEAD、 NetworkX、JDSL、Standford GraphBase和FGL等 •（4）使用已有的并行图计算系统：比如，Parallel BGL和CGM Graph，实现了很多并行图算法

9.1.3图计算通用软件 针对大型图的计算,目前通用的图计算软件主要包括两种: 第一种主要是基于遍历算法的、实时的图数据库,如 Ne4、 OrientDB、DEX和 nfinite Graph 第二种则是以图顶点为中心的、基于消息传递批处理的并 行引擎,如 Goldenorb、 Graph、 Pregel和Hama,这些 图处理软件主要是基于BSP模型实现的并行图处理系统 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn

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

91.3图计算通用软件 次BSP( Bulk Synchronous Parallel computing Model,又称“大同 步”模型)计算过程包括一“系列全局超步(所谓的超步就是计算中的 次迭代),每个超步主要包括三个组件: 局部计算:每个参与的处理器都有自身的计算任务 通讯:处理器群相互交换数据 栅栏同步( Barrier Synchronization):当一个处理器遇到“路障”(或 栅栏),会等到其他所有处理器完成它们的计算步骤 处理器 用户定义函数 F/vertex 局部计算 O 栅栏同步 超级步(S1) 超级步S 超级步(S+1) 图9-1一个超步的垂直结构图 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.1.3图计算通用软件 一次BSP(Bulk Synchronous Parallel Computing Model，又称“大同 步”模型)计算过程包括一系列全局超步（所谓的超步就是计算中的一 次迭代），每个超步主要包括三个组件： •局部计算：每个参与的处理器都有自身的计算任务 •通讯：处理器群相互交换数据 •栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或 栅栏），会等到其他所有处理器完成它们的计算步骤 处理器 局部计算 通讯 栅栏同步 图9-1 一个超步的垂直结构图

●92Pege简介 谷歌公司在2003年到2004年公布了GFS、 MapReduce和 Big table 谷歌在后 Hadoop时代的新“三驾马车” caffeine Dremel Pregel Pregel是一种基于BSP模型实现的并行图处理系统 为了解决大型图的分布式计算问题, Pregel搭建了一套可 扩展的、有容错机制的平台,该平台提供了一套非常灵活的 APl,可以描述各种各样的图计算 Pregel作为分布式图计算的计算框架,主要用于图遍历、 最短路径、 PageRank计算等等 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn

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

9.3 Pregel图计算模型 ·9.3.1 有向图和顶点 ·9.3.2 顶点之间的消息传递 9.33 Pregel的计算过程 ·9.3.4 实例 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn

《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3 Pregel图计算模型 • 9.3.1 有向图和顶点 • 9.3.2 顶点之间的消息传递 • 9.3.3 Pregel的计算过程 • 9.3.4 实例

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

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