一.图计算简介
1.1 图计算是专门针对图结构数据的处理．
- 许多大数据都是以大规模图或网络的形式呈现；
- 许多非图结构的大数据，也常常被转换为图模型后进行分析；
- 图结构很好地表达了数据之间的关联性；
- 关联性计算是大数据计算的核心------通过获得数据的关联性，可以从噪音很多的海量数据中抽取有用的信息；
1.2 传统的图计算算法存在典型问题
- 常常表现出比较差的内存访问局部性；
- 针对单个节点的处理工作过少；
- 计算过程中伴随着并行度的改变；
1.3 解决方案
- 为特定的图应用定制相应的分布式实现，通用性不好；
- 基于现有的分布式计算平台进行图计算；
- 使用单机的图算法库：BGL,LEAD,NetworkX,JDSL,Standford GraphBase 和FGL等，对于大规模计算能力有限．
- 使用已有的并行图计算系统：Parallel BGL 和CGM Graph ,实现了很多并行图算法，存在容错性问题；
1.4 MapReduce 是分布式计算平台．
- MapReduce 在图计算方面的性能和易用性不好，是粗粒度的计算，以块为单位进行数据分析；
1.5 通用的图计算软件
- 基于遍历算法的，实时的图数据库；如，Neo4j,OrientDB,DEX,Infinite Graph;
- 以图顶点为中心的，基于消息传递批处理的并行引擎；如,GoldenOrb,Giraph,Pregel,Hama;
- 共同特点：BSP 模型；
- BSP(Bulk Synchronous Parallel Computing Mode) 模型叫整体同步并行计算模型或者简称为大同步模型．
- BSP(Bulk Synchronous Parallel Computing Mode) 模型叫整体同步并行计算模型或者简称为大同步模型．
二. Pregel
2.1 简介
1.Pregel 是谷歌公司发布的一款商业图计算产品；
- Caffeine:快速用于大规模网页索引的构建；
- Dremel:实时性的交互分析产品，是一种只读嵌套数据的分析，支持分析PB 级别的数据；
- Pregel:基于BSP 模型实现的并行图计算系统；
2.2 Pregel 图计算模型
1.有向图和顶点
2.传递消息的基本方法
- 远程读取；
- 基于共享内存；
- 基于消息传递模型；
3.Pergel 采用消息传递模型主要基于以下两个原因：
- 远程读取具有较高的延迟，如MapReduce；
- 消息传递采用的是异步的批量的方式传递，延迟低；
4.Pregel 的计算过程
5.顶点的状态
6.Pregel 实例
2.3 Pregel C++ API
-
定义基类Vertex
-
消息传递机制和Combiner
顶点之间的通讯是通过消息传递机制来实现的，每条消息包含了消息值和需要到达的目标顶点ID.
在一个超步S 中，一个顶点可以发送任意数量的消息，这些消息将在下一个超步(s+1)中被其他顶点接收．
Combiner:
-
Aggregator，拓扑改变和输入输出
- 可以通过Aggregator实现全局协调功能；
拓扑改变：
输入输出:
2.3 Pregel体系结构
1.Pregel执行过程
- 用户程序的执行过程:
- 选择集群中的多台机器执行图计算任务，有一台及其会被选为Master 其他机器作为Worker;
- Master把一个图分成多个分区，并把分区分配到多个Worker,一个Worker会领到一个或多个分区，每个Worker知道所有其他Worker所分配到的分区情况;
2.容错性
3.Worker,Master和Aggregator
-
worker : 一般在执行过程中它的信息保存在内存当中，顶点当前的值，出射边列表，消息队列，标志位；worker会对自己所管辖的分区中的每个顶点进行遍历，并调用顶点上的Compute() 函数，Computer 函数接收顶点当前值，消息迭代器和出射边迭代器三个参数；
保存两份，一份用于当前超步，一份用于下一个超步．
-
Master:
4.Pregel的应用实例------单源最短路径
三.Hama的安转使用
3.1 Hama 简介
