《大数据技术原理与应用》 第十二讲 图计算 （2016春季学期）

Presentation on theme: "《大数据技术原理与应用》 第十二讲 图计算 （2016春季学期）"— Presentation transcript:

1 《大数据技术原理与应用》 http://dblab.xmu.edu.cn/post/bigdata 第十二讲 图计算 （2016春季学期）
第十二讲 图计算 （2016春季学期） 林子雨 厦门大学计算机科学系 主页： 厦门大学计算机科学系 年版

2 课堂内容与教材对应关系说明 厦门大学林子雨编著《大数据技术原理与应用》 2015年8月1日人民邮电出版社出版发行 第1版教材共包含13章内容
第一章 大数据概述 第二章 大数据处理架构Hadoop 第三章 分布式文件系统HDFS 第四章 分布式数据库HBase 第五章 NoSQL数据库 第六章 云数据库 第七章 MapReduce 第八章 流计算 第九章 图计算 第十章 数据可视化（自学） 第十一章 大数据在互联网领域的应用 第十二章 大数据在生物医学领域的应用（自学） 第十三章 大数据的其他应用（自学） 2016年新增章节（将加入到第2版教材中） 第14章基于Hadoop的数据仓库Hive 第15章Hadoop架构再探讨 第16章Spark

3 对应的《大数据技术原理与应用》（第1版）教材章节
课堂内容与教材对应关系说明 课堂章节 对应的《大数据技术原理与应用》（第1版）教材章节 第1讲-大数据概述 第1章-大数据概述 第2讲-大数据处理架构Hadoop 第2章-大数据处理架构Hadoop 第3讲-分布式文件系统HDFS 第3章-分布式文件系统HDFS 第4讲-分布式数据库HBase 第4章-分布式数据库HBase 第5讲-NoSQL数据库 第5章-NoSQL数据库 第6讲-云数据库 第6章-云数据库 第7讲-MapReduce 第7章-MapReduce 第8讲-基于Hadoop的数据仓库Hive 新增第14章，不在当前第1版教材中，将放入第2版教材 第9讲-Hadoop架构再探讨 新增第15章，不在当前第1版教材中，将放入第2版教材 第10讲-Spark 新增第16章，不在当前第1版教材中，将放入第2版教材 第11讲-流计算 第8章-流计算 第12讲-图计算 第9章-图计算 第13讲-大数据在互联网领域的应用 第11章-大数据在互联网领域的应用 备注：教材的第10章数据可视化、第12章大数据在生物医学领域的应用和第13章大数据在其他领域的应用，为自学章节，不录制视频

4 《大数据技术原理与应用》 http://dblab.xmu.edu.cn/post/bigdata 第九章 图计算 （2016春季学期）
第九章 图计算 （2016春季学期） 林子雨 厦门大学计算机科学系 主页： 厦门大学计算机科学系 年版

5 全方位、一站式服务 中国高校大数据课程公共服务平台 免费提供 课程教材 讲义PPT 学习指南 备课指南 上机习题 授课视频 技术资料
百度搜索“厦门大学数据库实验室”访问平台主页 免费提供 课程教材 讲义PPT 学习指南 备课指南 上机习题 授课视频 技术资料 全方位、一站式服务

6 提纲 9.1 图计算简介 9.2 Pregel简介 9.3 Pregel图计算模型 9.4 Pregel的C++ API
9.1 图计算简介 9.2 Pregel简介 9.3 Pregel图计算模型 9.4 Pregel的C++ API 9.5 Pregel的体系结构 9.6 Pregel的应用实例 9.7 Hama的安装和使用 本PPT是如下教材的配套讲义： 21世纪高等教育计算机规划教材 《大数据技术原理与应用 ——概念、存储、处理、分析与应用》 （2015年8月第1版） 厦门大学 林子雨 编著，人民邮电出版社 ISBN: 欢迎访问《大数据技术原理与应用》教材官方网站： 欢迎访问“中国高校大数据课程公共服务平台”旗下子栏目“大数据课程学生服务站”，为学生学习大数据课程提供全方位、一站式免费服务：

7 9.1 图计算简介 图结构数据 传统图计算解决方案的不足之处 图计算通用软件

8 9.1.1 图结构数据 许多大数据都是以大规模图或网络的形式呈现 许多非图结构的大数据，也常常会被转换为图模型后进行分析
图结构数据 许多大数据都是以大规模图或网络的形式呈现 许多非图结构的大数据，也常常会被转换为图模型后进行分析 图数据结构很好地表达了数据之间的关联性 关联性计算是大数据计算的核心——通过获得数据的关联性，可以从噪音很多的海量数据中抽取有用的信息

9 9.1.2 传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性
9.1.2 传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性 （2）针对单个顶点的处理工作过少 （3）计算过程中伴随着并行度的改变

10 9.1.2 传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及其不足之处具体如下：
9.1.2 传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及其不足之处具体如下： （1）为特定的图应用定制相应的分布式实现 （2）基于现有的分布式计算平台进行图计算 （3）使用单机的图算法库：比如BGL、LEAD、NetworkX、JDSL、Standford GraphBase和FGL等 （4）使用已有的并行图计算系统：比如，Parallel BGL和CGM Graph，实现了很多并行图算法

11 9.1.3 图计算通用软件 针对大型图的计算，目前通用的图计算软件主要包括两种：
图计算通用软件 针对大型图的计算，目前通用的图计算软件主要包括两种： 第一种主要是基于遍历算法的、实时的图数据库，如Neo4j、OrientDB、DEX和 Infinite Graph 第二种则是以图顶点为中心的、基于消息传递批处理的并行引擎，如GoldenOrb、Giraph、Pregel和Hama，这些图处理软件主要是基于BSP模型实现的并行图处理系统

12 9.1.3 图计算通用软件 一次BSP(Bulk Synchronous Parallel Computing Model，又称“大同步”模型)计算过程包括一系列全局超步（所谓的超步就是计算中的一次迭代），每个超步主要包括三个组件： 局部计算：每个参与的处理器都有自身的计算任务 通讯：处理器群相互交换数据 栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或栅栏），会等到其他所有处理器完成它们的计算步骤 图9‑1 一个超步的垂直结构图

13 9.2 Pregel简介 谷歌公司在2003年到2004年公布了GFS、MapReduce和BigTable
谷歌在后Hadoop时代的新“三驾马车” Caffeine Dremel Pregel Pregel是一种基于BSP模型实现的并行图处理系统 为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容错机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的图计算 Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、PageRank计算等等

14 9.3 Pregel图计算模型 9.3.1 有向图和顶点 9.3.2 顶点之间的消息传递 9.3.3 Pregel的计算过程
9.3.1 有向图和顶点 9.3.2 顶点之间的消息传递 9.3.3 Pregel的计算过程 9.3.4 实例

15 9.3.1 有向图和顶点 Pregel计算模型以有向图作为输入 有向图的每个顶点都有一个String类型的顶点ID
9.3.1 有向图和顶点 Pregel计算模型以有向图作为输入 有向图的每个顶点都有一个String类型的顶点ID 每个顶点都有一个可修改的用户自定义值与之关联 每条有向边都和其源顶点关联，并记录了其目标顶点ID 边上有一个可修改的用户自定义值与之关联 边e1 String类型的顶点ID 可修改的用户自定义值 顶点 边上有一个可修改的用户自定义值

16 9.3.1 有向图和顶点 在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数
9.3.1 有向图和顶点 在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数 每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其出射边的状态，并发送消息给其他顶点，甚至是修改整个图的拓扑结构 在这种计算模式中，“边”并不是核心对象，在边上面不会运行相应的计算，只有顶点才会执行用户自定义函数进行相应计算 表示顶点 表示发送消息

17 9.3.2 顶点之间的消息传递 采用消息传递模型主要基于以下两个原因：
9.3.2 顶点之间的消息传递 采用消息传递模型主要基于以下两个原因： （1）消息传递具有足够的表达能力，没有必要使用远程读取或共享内存的方式 （2）有助于提升系统整体性能 图9‑2 纯消息传递模型图

18 9.3.3 Pregel的计算过程 Pregel的计算过程是由一系列被称为“超步”的迭代组成的
在每个超步中，每个顶点上面都会并行执行用户自定义的函数，该函数描述了一个顶点V在一个超步S中需要执行的操作 该函数可以读取前一个超步(S-1)中其他顶点发送给顶点V的消息，执行相应计算后，修改顶点V及其出射边的状态，然后沿着顶点V的出射边发送消息给其他顶点，而且，一个消息可能经过多条边的传递后被发送到任意已知ID的目标顶点上去 这些消息将会在下一个超步(S+1)中被目标顶点接收，然后象上述过程一样开始下一个超步(S+1)的迭代过程 1 2 3 4 5 6 表示顶点 表示发送消息

19 9.3.3 Pregel的计算过程 在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点的状态决定的
在第0个超步，所有顶点处于活跃状态 当一个顶点不需要继续执行进一步的计算时，就会把自己的状态设置为“停机”，进入非活跃状态 当一个处于非活跃状态的顶点收到来自其他顶点的消息时，Pregel计算框架必须根据条件判断来决定是否将其显式唤醒进入活跃状态 当图中所有的顶点都已经标识其自身达到“非活跃（inactive）”状态，并且没有消息在传送的时候，算法就可以停止运行 图9‑3 一个简单的状态机图

20 9.3.4 实例 活跃 非活跃 A B C D 3 6 2 1 图9‑4 一个求最大值的Pregel计算过程图

21 9.4 Pregel的C++ API Pregel已经预先定义好一个基类——Vertex类：
template <typename VertexValue, typename EdgeValue, typename MessageValue> class Vertex { public: virtual void Compute(MessageIterator* msgs) = 0; const string& vertex_id() const; int64 superstep() const; const VertexValue& GetValue(); VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo(const string& dest_vertex, const MessageValue& message); void VoteToHalt(); }; 在Vetex类中，定义了三个值类型参数，分别表示顶点、边和消息。每一个顶点都有一个给定类型的值与之对应 编写Pregel程序时，需要继承Vertex类，并且覆写Vertex类的虚函数Compute()

22 9.4 Pregel的C++ API 9.4.1 消息传递机制 9.4.2 Combiner 9.4.3 Aggregator
9.4.1 消息传递机制 9.4.2 Combiner 9.4.3 Aggregator 9.4.4 拓扑改变 9.4.5 输入和输出

23 9.4.1 消息传递机制 顶点之间的通讯是借助于消息传递机制来实现的，每条消息都包含了消息值和需要到达的目标顶点ID。用户可以通过Vertex类的模板参数来设定消息值的数据类型 在一个超步S中，一个顶点可以发送任意数量的消息，这些消息将在下一个超步（S+1）中被其他顶点接收 一个顶点V通过与之关联的出射边向外发送消息，并且，消息要到达的目标顶点并不一定是与顶点V相邻的顶点，一个消息可以连续经过多条连通的边到达某个与顶点V不相邻的顶点U，U可以从接收的消息中获取到与其不相邻的顶点V的ID

24 9.4.2 Combiner Pregel计算框架在消息发出去之前，Combiner可以将发往同一个顶点的多个整型值进行求和得到一个值，只需向外发送这个“求和结果”，从而实现了由多个消息合并成一个消息，大大减少了传输和缓存的开销 在默认情况下，Pregel计算框架并不会开启Combiner功能 当用户打算开启Combiner功能时，可以继承Combiner类并覆写虚函数Combine() 此外，通常只对那些满足交换律和结合律的操作才可以去开启Combiner功能 图9-5 Combiner应用的例子

25 9.4.3 Aggregator Aggregator提供了一种全局通信、监控和数据查看的机制
在一个超步S中，每一个顶点都可以向一个Aggregator提供一个数据，Pregel计算框架会对这些值进行聚合操作产生一个值，在下一个超步（S+1）中，图中的所有顶点都可以看见这个值 Aggregator的聚合功能，允许在整型和字符串类型上执行最大值、最小值、求和操作，比如，可以定义一个“Sum”Aggregator来统计每个顶点的出射边数量，最后相加可以得到整个图的边的数量 Aggregator还可以实现全局协同的功能，比如，可以设计“and” Aggregator来决定在某个超步中Compute()函数是否执行某些逻辑分支，只有当“and” Aggregator显示所有顶点都满足了某条件时，才去执行这些逻辑分支

26 9.4.4 拓扑改变 Pregel计算框架允许用户在自定义函数Compute()中定义操作，修改图的拓扑结构，比如在图中增加（或删除）边或顶点 对于全局拓扑改变，Pregel采用了惰性协调机制 对于本地的局部拓扑改变，是不会引发冲突的，顶点或边的本地增减能够立即生效，很大程度上简化了分布式编程

27 9.4.5 输入和输出 在Pregel计算框架中，图的保存格式多种多样，包括文本文件、关系数据库或键值数据库等
9.4.5 输入和输出 在Pregel计算框架中，图的保存格式多种多样，包括文本文件、关系数据库或键值数据库等 在Pregel中，“从输入文件生成得到图结构”和“执行图计算”这两个过程是分离的，从而不会限制输入文件的格式 对于输出，Pregel也采用了灵活的方式，可以以多种方式进行输出

28 9.5 Pregel的体系结构 9.5.1 Pregel的执行过程 9.5.2 容错性 9.5.3 Worker 9.5.4 Master
9.5.2 容错性 9.5.3 Worker 9.5.4 Master Aggregator

29 9.5.1 Pregel的执行过程 在Pregel计算框架中，一个大型图会被划分成许多个分区，每个分区都包含了一部分顶点以及以其为起点的边
一个顶点应该被分配到哪个分区上，是由一个函数决定的，系统默认函数为hash(ID) mod N，其中，N为所有分区总数，ID是这个顶点的标识符；当然，用户也可以自己定义这个函数 这样，无论在哪台机器上，都可以简单根据顶点ID判断出该顶点属于哪个分区，即使该顶点可能已经不存在了 图9-6图的划分图

30 9.5.1 Pregel的执行过程 在理想的情况下（不发生任何错误），一个Pregel用户程序的执行过程如下：
（1）选择集群中的多台机器执行图计算任务，有一台机器会被选为Master，其他机器作为Worker （2）Master把一个图分成多个分区，并把分区分配到多个Worker。一个Worker会领到一个或多个分区，每个Worker知道所有其他Worker所分配到的分区情况 图9-7 Pregel的执行过程图

31 9.5.1 Pregel的执行过程 （3）Master会把用户输入划分成多个部分。然后，Master会为每个Worker分配用户输入的一部分。如果一个Worker从输入内容中加载到的顶点，刚好是自己所分配到的分区中的顶点，就会立即更新相应的数据结构。否则，该Worker会根据加载到的顶点的ID，把它发送到其所属的分区所在的Worker上。当所有的输入都被加载后，图中的所有顶点都会被标记为“活跃”状态。 图9-7 Pregel的执行过程图

32 9.5.1 Pregel的执行过程 （4）Master向每个Worker发送指令，Worker收到指令后，开始运行一个超步。当一个超步中的所有工作都完成以后，Worker会通知Master，并把自己在下一个超步还处于“活跃”状态的顶点的数量报告给Master。上述步骤会被不断重复，直到所有顶点都不再活跃并且系统中不会有任何消息在传输，这时，执行过程才会结束。 图9-7 Pregel的执行过程图 （5）计算过程结束后，Master会给所有的Worker发送指令，通知每个Worker对自己的计算结果进行持久化存储

33 9.5.2 容错性 Pregel采用检查点机制来实现容错。在每个超步的开始，Master会通知所有的Worker把自己管辖的分区的状态写入到持久化存储设备 Master会周期性地向每个Worker发送ping消息，Worker收到ping消息后会给Master发送反馈消息 每个Worker上都保存了一个或多个分区的状态信息，当一个Worker发生故障时，它所负责维护的分区的当前状态信息就会丢失。Master监测到一个Worker发生故障“失效”后，会把失效Worker所分配到的分区，重新分配到其他处于正常工作状态的Worker集合上，然后，所有这些分区会从最近的某超步S开始时写出的检查点中，重新加载状态信息

34 9.5.3 Worker 在一个Worker中，它所管辖的分区的状态信息是保存在内存中的。分区中的顶点的状态信息包括： 顶点的当前值
以该顶点为起点的出射边列表，每条出射边包含了目标顶点ID和边的值 消息队列，包含了所有接收到的、发送给该顶点的消息 标志位，用来标记顶点是否处于活跃状态 在每个超步中，Worker会对自己所管辖的分区中的每个顶点进行遍历，并调用顶点上的Compute()函数，在调用时，会把以下三个参数传递进去： 该顶点的当前值 一个接收到的消息的迭代器 一个出射边的迭代器

35 9.5.3 Worker 在Pregel中，为了获得更好的性能，“标志位”和输入消息队列是分开保存的
如果一个顶点V在超步S接收到消息，那么，它表示V将会在下一个超步S+1中（而不是当前超步S中）处于“活跃”状态

36 9.5.3 Worker 当一个Worker上的一个顶点V需要发送消息到其他顶点U时，该Worker会首先判断目标顶点U是否位于自己机器上
如果目标顶点U在自己的机器上，就直接把消息放入到与目标顶点U对应的输入消息队列中 如果发现目标顶点U在远程机器上，这个消息就会被暂时缓存到本地，当缓存中的消息数目达到一个事先设定的阈值时，这些缓存消息会被批量异步发送出去，传输到目标顶点所在的Worker上

37 9.5.4 Master Master主要负责协调各个Worker执行任务，每个Worker会借助于名称服务系统定位到Master的位置，并向Master发送自己的注册信息，Master会为每个Worker分配一个唯一的ID Master维护着关于当前处于“有效”状态的所有Worker的各种信息，包括每个Worker的ID和地址信息，以及每个Worker被分配到的分区信息 Master中保存这些信息的数据结构的大小，只与分区的数量有关，而与顶点和边的数量无关

38 9.5.4 Master 一个大规模图计算任务会被Master分解到多个Worker去执行，在每个超步开始时，Master都会向所有处于“有效”状态的Worker发送相同的指令，然后等待这些Worker的回应 如果在指定时间内收不到某个Worker的反馈，Master就认为这个Worker失效 如果参与任务执行的多个Worker中的任意一个发生了故障失效，Master就会进入恢复模式 在每个超步中，图计算的各种工作，比如输入、输出、计算、保存和从检查点中恢复，都会在“路障（barrier）”之前结束

39 9.5.4 Master Master在内部运行了一个HTTP服务器来显示图计算过程的各种信息
用户可以通过网页随时监控图计算执行过程各个细节 图的大小 关于出度分布的柱状图 处于活跃状态的顶点数量 在当前超步的时间信息和消息流量 所有用户自定义Aggregator的值

40 9.5.5 Aggregator 每个用户自定义的Aggregator都会采用聚合函数对一个值集合进行聚合计算得到一个全局值
每个Worker都保存了一个Aggregator的实例集，其中的每个实例都是由类型名称和实例名称来标识的 在执行图计算过程的某个超步S中，每个Worker会利用一个Aggregator对当前本地分区中包含的所有顶点的值进行归约，得到一个本地的局部归约值 在超步S结束时，所有Worker会将所有包含局部归约值的Aggregator的值进行最后的汇总，得到全局值，然后提交给Master 在下一个超步S+1开始时，Master就会将Aggregator的全局值发送给每个Worker

41 9.6 Pregel的应用实例——单源最短路径 Dijkstra算法是解决单源最短路径问题的贪婪算法

42 9.6 Pregel的应用实例——单源最短路径 Pregel非常适合用来解决单源最短路径问题，实现代码如下：
1 class ShortestPathVertex 2 : public Vertex<int, int, int> { 3 void Compute(MessageIterator* msgs) { int mindist = IsSource(vertex_id()) ? 0 : INF; for (; !msgs->Done(); msgs->Next()) mindist = min(mindist, msgs->Value()); if (mindist < GetValue()) { *MutableValue() = mindist; OutEdgeIterator iter = GetOutEdgeIterator(); for (; !iter.Done(); iter.Next()) SendMessageTo(iter.Target(), mindist + iter.GetValue()); 13 } 14 VoteToHalt(); 15 } 16 };

43 9.6 Pregel的应用实例——单源最短路径 每个顶点并行执行Compute()函数 表1 超步0开始时的顶点值 1 2 3 4 INF
1 2 3 4 INF 表2 超步0结束时的顶点值 表3 顶点0向其他顶点发送消息 1 2 3 4 INF 1 2 3 4 100 30 无 10 超步0结束时，所有顶点非活跃

44 9.6 Pregel的应用实例——单源最短路径 超步1： 顶点0：没有收到消息，依然非活跃
顶点1：收到消息100（唯一消息），被显式唤醒，执行计算，mindist变为100，小于顶点值INF，顶点值修改为100，没有出射边，不需要发送消息，最后变为非活跃 顶点2：收到消息30，被显式唤醒，执行计算， mindist变为30，小于顶点值INF，顶点值修改为30，有两条出射边，向顶点3发送消息90（即：30+60），向顶点1发送消息90（即：30+60），最后变为非活跃 顶点3：没有收到消息，依然非活跃 顶点4：收到消息10，被显式唤醒，执行计算， mindist变为10，小于顶点值INF，顶点值修改为10，向顶点3发送消息60（即：10+50），最后变为非活跃 表4 上一步（超步0）中发出的消息 1 2 3 4 100 30 无 10 表5 超步1开始时的顶点值 1 2 3 4 INF 表6 超步1结束时的顶点值 1 2 3 4 100 30 INF 10 剩余超步省略…… 当所有顶点非活跃，并且没有消息传递，就结束

45 9.7 Hama的安装和使用 9.7.1 Hama介绍 9.7.2 安装Hama的基本过程 9.7.3 运行Hama实例PageRank

46 9.7.1 Hama介绍 Hama是Google Pregel的开源实现 与Hadoop适合于分布式大数据处理不同，Hama主要用于分布式的矩阵、graph、网络算法的计算 Hama是在HDFS上实现的BSP(Bulk Synchronous Parallel)计算框架，弥补Hadoop在计算能力上的不足

47 9.7.2 安装Hama的基本过程 本实例中Hama具体运行环境如下： Ubuntu 14.04 Java JDK 1.7 Hadoop 2.6.0

48 export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64
9.7.2 安装Hama的基本过程 Hama （单机）安装步骤如下： （1）安装好合适版本的JDK和Hadoop （2）从官网下载Hama安装文件，比如Hama 0.7.0版本 （3）下载文件后，运用下面命令 sudo tar -zxf ~/下载/hama-dist tar.gz -C /usr/local 解压至 /usr/local/hama ，再运用下面命令 sudo mv ./hama-0.7.0/ ./hama 修改目录名称方便使用 （4）进入hama中的conf文件夹，修改hama-env.sh文件，在其中加入java的home路径，即加入： export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64

49 9.7.2 安装Hama的基本过程 （5）修改 hama-site.xml文件，这是hama配置的核心文件，具体内容如下：
<configuration> <property> <name>bsp.master.address</name> <value>local</value> <description>The address of the bsp master server. Either the literal string "local" or a host:port for distributed mode </description> </property> <name>fs.default.name</name> <description> The name of the default file system. Either the literal string "local" or a host:port for HDFS. </description> </property>

50 9.7.2 安装Hama的基本过程 <property>
<name>hama.zookeeper.quorum</name> <value>localhost</value> <description>Comma separated list of servers in the ZooKeeper Quorum. For example, "host1.mydomain.com,host2.mydomain.com,host3.mydomain.com". By default this is set to localhost for local and pseudo-distributed modes of operation. For a fully-distributed setup, this should be set to a full list of ZooKeeper quorum servers. If HAMA_MANAGES_ZK is set in hama-env.sh this is the list of servers which we will start/stop zookeeper on. </description> </property> </configuration>

51 9.7.3 运行Hama实例PageRank （1）生成 randomgraph，运行如下命令：
./bin/hama jar hama-examples jar gen fastgen -v 100 -e 10 -o randomgraph -t 2 生成的文件位于 /usr/local/hama 下的 randomgraph。它表示100个节点，1000条边的数据，存储在两个文件中（part-00000,part-00001）。

52 9.7.3 运行Hama实例PageRank (2)执行pagerank
./bin/hama jar hama-examples jar pagerank -i randomgraph -o pagerankresult -t 4 运行结果保存在pagerankresult文件中 单机模式下，数据读取都是在本地文件系统，不需要读取HDFS中的文件。

53 本章小结 本章内容介绍了图计算框架Pregel的相关知识。传统的图计算解决方案无法解决大型的图计算问题，包括Pregel在内的各种图计算框架脱颖而出。 Pregel并没有采用远程数据读取或者共享内存的方式，而是采用了纯消息传递模型，来实现不同顶点之间的信息交换。Pregel的计算过程是由一系列被称为“超步”的迭代组成的，每次迭代对应了BSP模型中的一个超步。 Pregel已经预先定义好一个基类——Vertex类，编写Pregel程序时，需要继承Vertex类，并且覆写Vertex类的虚函数Compute()。在Pregel执行计算过程时，在每个超步中都会并行调用每个顶点上定义的Compute()函数。 Pregel是为执行大规模图计算而设计的，通常运行在由多台廉价服务器构成的集群上。一个图计算任务会被分解到多台机器上同时执行，Pregel采用检查点机制来实现容错。 Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、PageRank计算等等。 本章最后通过对PageRank算法在MapReduce和Pregel上执行方式的不同进行比较，说明了Pregel解决图计算问题的优势。

54 附录：主讲教师 主讲教师：林子雨 单位：厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn
个人网页： 数据库实验室网站： 扫一扫访问个人主页 林子雨，男，1978年出生，博士（毕业于北京大学），现为厦门大学计算机科学系助理教授（讲师），曾任厦门大学信息科学与技术学院院长助理、晋江市发展和改革局副局长。中国高校首个“数字教师”提出者和建设者，厦门大学数据库实验室负责人，厦门大学云计算与大数据研究中心主要建设者和骨干成员，2013年度厦门大学奖教金获得者。主要研究方向为数据库、数据仓库、数据挖掘、大数据、云计算和物联网，并以第一作者身份在《软件学报》《计算机学报》和《计算机研究与发展》等国家重点期刊以及国际学术会议上发表多篇学术论文。作为项目负责人主持的科研项目包括1项国家自然科学青年基金项目(No )、1项福建省自然科学青年基金项目(No.2013J05099)和1项中央高校基本科研业务费项目(No )，同时，作为课题负责人完成了国家发改委城市信息化重大课题、国家物联网重大应用示范工程区域试点泉州市工作方案、2015泉州市互联网经济调研等课题。编著出版中国高校第一本系统介绍大数据知识的专业教材《大数据技术原理与应用》并成为畅销书籍，编著并免费网络发布40余万字中国高校第一本闪存数据库研究专著《闪存数据库概念与技术》；主讲厦门大学计算机系本科生课程《数据库系统原理》和研究生课程《分布式数据库》《大数据技术基础》。具有丰富的政府和企业信息化培训经验，曾先后给中国移动通信集团公司、福州马尾区政府、福建省物联网科学研究院、石狮市物流协会、厦门市物流协会、福建龙岩卷烟厂等多家单位和企业开展信息化培训，累计培训人数达2000人以上。

55 附录：大数据学习教材推荐 《大数据技术原理与应用——概念、存储、处理、分析与应用》，由厦门大学计算机科学系林子雨博士编著，是中国高校第一本系统介绍大数据知识的专业教材。 全书共有13章，系统地论述了大数据的基本概念、大数据处理架构Hadoop、分布式文件系统HDFS、分布式数据 库HBase、NoSQL数据库、云数据库、分布式并行编程模型MapReduce、流计算、图计算、数据可视化以及大数据在互联网、生物医学和物流等各个领域的应用。在Hadoop、HDFS、HBase和MapReduce等重要章节，安排了入门级的实践操作，让读者更好地学习和掌握大数据关键技术。 本书可以作为高等院校计算机专业、信息管理等相关专业的大数据课程教材，也可供相关技术人员参考、学习、培训之用。 扫一扫访问教材官网 欢迎访问《大数据技术原理与应用——概念、存储、处理、分析与应用》教材官方网站：

56 附录：中国高校大数据课程公共服务平台 扫一扫访问平台主页 扫一扫观看3分钟FLASH动画宣传片

57 Department of Computer Science, Xiamen University, 2016