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