文档介绍：大数据技术应用基本原理和应用图计算
提纲
图计算简介
Pregel简介
Pregel图计算模型
Pregel的C++ API
Pregel的体系结构
Pregel的应用实例
Pregel和MapReduce实现PageRank算法的对比
欢迎访问《大数据技术原理与应用》教材官方网站：
本PPT是如下教材的配套讲义：
21世纪高等教育计算机规划教材
《大数据技术原理与应用
——概念、存储、处理、分析与应用》
（2015年6月第1版）
厦门大学 林子雨 编著，人民邮电出版社
ISBN:978-7-115-39287-9
图计算简介
传统图计算解决方案的不足之处
图计算通用软件
传统图计算解决方案的不足之处
很多传统的图计算算法都存在以下几个典型问题：
（1）常常表现出比较差的内存访问局部性；
（2）针对单个顶点的处理工作过少；
（3）计算过程中伴随着并行度的改变。
针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及其不足之处具体如下：
为特定的图应用定制相应的分布式实现：通用性不好
基于现有的分布式计算平台进行图计算：在性能和易用性方面往往无法达到最优
使用单机的图算法库：在可以解决的问题的规模方面具有很大的局限性
使用已有的并行图计算系统：对大规模分布式系统非常重要的一些方面（比如容错），无法提供较好的支持
图计算通用软件
一次BSP计算过程包括一系列全局超步（所谓的超步就是计算中的一次迭代），每个超步主要包括三个组件：
局部计算：每个参与的处理器都有自身的计算任务，它们只读取存储在本地内存中的值，不同处理器的计算任务都是异步并且独立的
通讯：处理器群相互交换数据，交换的形式是，由一方发起推送(put)和获取(get)操作
栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或栅栏），会等到其他所有处理器完成它们的计算步骤；每一次同步也是一个超步的完成和下一个超步的开始。图9-1是一个超步的垂直结构图
图9‑1 一个超步的垂直结构图
Pregel简介
Pregel是一种基于BSP模型实现的并行图处理系统
为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容错机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的图计算
Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、PageRank计算等等
Pregel图计算模型
有向图和顶点
顶点之间的消息传递
Pregel的计算过程
实例
有向图和顶点
Pregel计算模型以有向图作为输入，有向图的每个顶点都有一个String类型的顶点ID，每个顶点都有一个可修改的用户自定义值与之关联，每条有向边都和其源顶点关联，并记录了其目标顶点ID，边上有一个可修改的用户自定义值与之关联
在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数。每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其出射边的状态，并发送消息给其他顶点，甚至是修改整个图的拓扑结构。需要指出的是，在这种计算模式中，边并不是核心对象，在边上面不会运行相应的计算，只有顶点才会执行用户自定义函数进行相应计算
顶点之间的消息传递
图9‑2 纯消息传递模型图
采用消息传递模型主要基于以下两个原因：
（1）消息传递具有足够的表达能力，没有必要使用远程读取或共享内存的方式
（2）有助于提升系统整体性能
Pregel的计算过程
图9‑3 一个简单的状态机图
Pregel的计算过程是由一系列被称为“超步”的迭代组成的。在每个超步中，每个顶点上面都会并行执行用户自定义的函数，该函数描述了一个顶点V在一个超步S中需要执行的操作。该函数可以读取前一个超步(S-1)中其他顶点发送给顶点V的消息，执行相应计算后，修改顶点V及其出射边的状态，然后沿着顶点V的出射边发送消息给其他顶点，而且，一个消息可能经过多条边的传递后被发送到任意已知ID的目标顶点上去。这些消息将会在下一个超步(S+1)中被目标顶点接收，然后像上述过程一样开始下一个超步(S+1)的迭代过程
在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点的状态决定的，当图中所有的顶点都已经标识其自身达到“非活跃（inactive）”状态时，算法就可以停止运行