数据库实验室林子雨老师团队2013—2014学年秋季学期
第5次小组讨论会会议纪要
会议时间：2013年11月9日（星期六）上午9点到11点40分
会议地点：厦门大学海韵园科研二号楼303室
与会者：林子雨、赖明星、刘颖杰、叶林宝、蔡珉星、李雨倩、谢荣东、罗道文
会议纪要：叶林宝
会议内容：
厦门大学计算机系数据库实验室林子雨老师小组2013-2014学年第一学期第5次小组会议在2013年11月9日举行，在本次讨论会上，李雨倩同学继续讲解图计算相关知识。
内容如下：
- 图计算简介
（1）大型图常常作为现在系统计算需要的一部分。现在存在许多图计算问题像最短路径、集群、网页排名、最小切割、连通分支等等，但还没有一个可扩展的通用系统来解决这些问题。
（2）目前通用的图处理软件主要包括两种。一种主要基于遍历算法、实时的图数据库，另一种则是以图顶点为中心的消息传递批处理的并行引擎。
（3）以图顶点为中心的消息传递批处理的并行引擎主要是基于BSP(Bulk Synchronous Parallel)模型所实现的并行图处理包。
（4）Pregel是由Google开发的一个用于分布式图计算的计算框架，主要用于图遍历（BFS）、最短路径（SSSP）、PageRank计算等等。
- Google Pregel图计算模型
（1）个典型的Pregel计算过程如下：读取输入初始化该图，当图被初始化好后，运行一系列的超级步直到整个计算结束，这些超级步之间通过一些全局的同步点分隔开，输出结果结束计算。
- 计算模型是一种纯消息传递模型，忽略远程数据读取和其他共享内存的方式。
- Pregel C++ API
相关内容有：Vertex类（Pregel中已预定义好的一个基类），Compute()函数，消息传递机制，Combiner（用于减少通信负荷），aggregator（提供全局通信，监控和数据查看的机制），自定义handler，topology mutation（Compute()算法也可以用来修改图的拓扑结构）。
- Pregel模型的执行过程
（1）用户程序的多个copy开始在集群中的机器上执行。
（2）Master将图进行分区，然后将一个或多个partition分给worker。
（3）Master为每个worker分配用户输入的一部分。
（4）在一个超步中，master通知每一个worker去执行，只要存在active顶点worker一直执行，并为每一个active状态的顶点调用compute()方法。它也会传送以前的超步发送的消息。
（5）计算结束后，master会通知所有的worker保存它那部分的计算结果。
- 改进的图计算模型
PowerGraph将基于vertex的图计算抽象成一个通用的计算模型：GAS模型，分为三个阶段：Gather，Apply和Scatter。
