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 顶点