厦门大学林子雨编着.DOC

1、厦门大学林子雨编著大数据技术原理与应用教材配套上机练习图计算框架 Hama 的基础操作实践（版本号：2016 年 1 月 24 日版本）主讲教师：林子雨厦门大学数据库实验室二零一六年一月（版权所有，请勿用于商业用途）目录目录1 作业题目 .12 作业目的 .13 作业性质 .14 作业考核方法 .15 作业提交日期与方式 .16 作业准备 .16.1、 Hama 计算框架的安装配置 .16.2、用 Hama 计算模型实现寻找最大独立集问题算法 .47 作业内容 .98 实验报告 .9附录 1:任课教师介绍 .9附录 2：课程教材介绍 .10附录 3：中国高校大数据课程公共服务平台介绍 .11厦

2、门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 1 页厦门大学林子雨编著大数据技术原理与应用教材配套上机练习图计算框架 Hama 基础操作实践上机练习说明主讲教师：林子雨E-mail: 个人主页：http:/ Hama 基础操作实践。2作业目的旨在让学生了解 Pregel 图计算模型，并学会用 Pregel 的开源实现 Hama 实现一些基本操作。3作业性质课后作业，必做，作为课堂平时成绩。4作业考核方法提交上机实验报告，任课老师根据上机实验报告评定成绩。5作业提交日期与方式图计算章节内容结束后的下一周周六晚上 9

3、 点之前提交。6作业准备请阅读厦门大学林子雨编著的大数据专业教材大数据技术原理与应用 （官网：http:/ ，了解图计算的概念与意义。6.1、 Hama 计算框架的安装配置Apache Hama 是 Google Pregel 的开源实现，与 Hadoop 适合于分布式大数据处理不同，Hama 主要用于分布式的矩阵、graph、网络算法的计算。简单说，Hama 是在HDFS 上实现的 BSP(Bulk Synchronous Parallel)计算框架，弥补 Hadoop 在计算能力上的不足。（1）. 安装好合适版本的 jdk 和 hadoop，并且进行测试，保证他们能用。（2）. 下载 ha

4、ma 安装文件，从 http:/hama.apache.org/downloads.html 处下载合适的版本，我当时下的是 0.6.4 版本的。厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 2 页（3）. 在用户主目录下创建合适的安装目录文件，我这里是在 下创建了 hama 文件夹作为安装目录，即/hama 为安装目录。（4）. 将下载好的 hama-0.6.4.tar.gz 拷贝到/hama 中去，并用 tar zvxf hama-0.6.4.tar.gz 进行解压。（5）. 进入 hama-0.6.4 中的

5、 conf 文件夹，修改 hama-env.sh 文件，在其中加入 java 的home 路径，即加入：Export JAVA_HOME=/home/wanglianping/java/jdk.1.7.0_91（ 6）. 修改 hama-site.xml 文件，这时 hama 配置的核心文件，具体内容如下：bsp.master.address192.168.91.128:40000The address of the bsp master server. Either theliteral string “local“ or a host:port for distributed modefs

6、.default.namehdfs:/192.168.91.128:9000/The name of the default file system. Either the literal string“local“ or a host:port for HDFS.hama.zookeeper.quorum192.168.91.128Comma separated list of servers in the ZooKeeper Quorum.For example, “,,“.By default this is set to localhost for local and pseudo-d

7、istributed modesof operation. For a fully-distributed setup, this should be set to a fulllist of ZooKeeper quorum servers. If HAMA_MANAGES_ZK is set in hama-env.sh厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 3 页this is the list of servers which we will start/stop zookeeper on.hama

8、.zookeeper.property.clientPort2181其中，bsp.master.address 即 bsp 中的 BSPMaster 的地址和端口。fs.default.name 这个值要特别注意，是 hadoop 中 nameNode 的地址和端口，因为 hama 要用到 hadoop 的hdfs 分布式文件系统。剩下的俩个是 zookeeper 的相关配置。（7）.另外，在 conf 文件夹下还有一个 groomservers 文件，这个在分布式环境下配置groomserver 的地址，在单机模式下就不用配置了，里面默认值为 localhost。同时，你也可以在/.bash

9、rc 中添加 hama 的环境变量，这样每次启动就不同转到相应的目录下去了。（8）. 启动 hadoop，并验证是否启动成功。命令：HADOOP_HOME/bin/start-all.sh，如果启动成功，如下：启动 hama，命令：HAMA_HOME/bin/start-bspd.sh,结果如下：厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 4 页出现上述结果，则表明 hama 已经成功启动。6.2、用 Hama 计算模型实现寻找最大独立集问题算法 （1）. 本算法参考 Lubys classic paralle

10、l algorithma simple parallel algorithm for maximal independent set problem，把顶点分为三类：1) S:The MIS being constructed. Starts empty and grows in iterations.2) NotInS: Vertices that have at least one edge to a vertex in S and as a result cannot be in S.3) Unknown: Vertices that do not have an edge to any

11、 vertex in S but are not yet in S.（2）.Hama 模型下 MIS（Maximal Independent Set）算法描述。1）初始时，把所有顶点的 value 值赋值为自己的 vertexID，表明初始所有顶点均在 UnKnown 集合中，然后把自己的 VertexID 发送给邻接顶点。2) 若顶点 u 的 VertexID 比自己所有邻接顶点都小，则该顶点进入 S 集合中，并发送neighbor-in-set 消息给所有邻接顶点，通知它们退出 Unknown 集合进入到 NotInS 集合中，并最后把 u 置为 InActive 状态；否则，顶点 u 继

12、续保持 UnKnown 状态。3) S 集合中顶点的邻接顶点收到 neighbor-in-set 消息，则该顶点进入 NotInS，并且设置为 Inactive 状态。返回继续迭代，直到 UnKnown 集合为空。（3）. 程序中按照顶点 value 取值不同来区分顶点的类别，具体如下：1) value 等于 vertexID ,表示顶点在 Unknown 集合中；2) value 等于 -1 ,表示顶点在 S 集合中3) value 等于 -2 ，表示顶点在 NotInS 集合中。当所有顶点进入 S 或者 NotInS 集合中，就停止计算，表明已找到一个 MIS。源码如下：package g

13、raph.mis;import java.io.IOException;import java.util.Iterator;import org.apache.hadoop.conf.Configuration;import org.apache.hadoop.fs.Path;import org.apache.hadoop.io.LongWritable;import org.apache.hadoop.io.NullWritable;import org.apache.hadoop.io.Text;import org.apache.hama.HamaConfiguration;impor

14、t org.apache.hama.bsp.HashPartitioner;import org.apache.hama.bsp.TextInputFormat;import org.apache.hama.bsp.TextOutputFormat;厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 5 页import org.apache.hama.graph.Edge;import org.apache.hama.graph.GraphJob;import org.apache.hama.graph.Vertex;

15、import org.apache.hama.graph.VertexInputReader;public class FindMIS public static class MISVertex extendsVertex Overridepublic void compute(Iterator messages) throws IOException if (getSuperstepCount() = 0) setValue(getVertexID();sendMessageToNeighbors(getValue(); else if(getValue().get()=-2) voteTo

16、Halt(); else boolean revMsg = false; while (messages.hasNext() revMsg = true;long msg = messages.next().get();if (msg = -2) setValue(new LongWritable(-2);voteToHalt();return; else if (msg Overridepublic boolean parseVertex(LongWritable key, Text value,Vertex vertex)厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架

17、 Hama 基础操作实践主讲教师：林子雨 http:/ 第 6 页throws Exception String split = value.toString().split(“t“);for (int i = 0; i (new LongWritable(Long.parseLong(spliti), null);return true;public static void main(String args) throws IOException,InterruptedException, ClassNotFoundException if (args.length “);System.ex

18、it(-1);HamaConfiguration conf = new HamaConfiguration(new Configuration();GraphJob pageJob = new GraphJob(conf, FindMIS.class);pageJob.setJobName(“Find a MIS“);pageJob.setMaxIteration(30);pageJob.setVertexClass(MISVertex.class);pageJob.setInputPath(new Path(args0);pageJob.setOutputPath(new Path(args

19、1);pageJob.setVertexIDClass(LongWritable.class);pageJob.setVertexValueClass(LongWritable.class);pageJob.setEdgeValueClass(NullWritable.class);pageJob.setInputKeyClass(LongWritable.class);pageJob.setInputValueClass(Text.class);pageJob.setInputFormat(TextInputFormat.class);pageJob.setVertexInputReader

20、Class(MISTextReader.class);pageJob.setPartitioner(HashPartitioner.class);pageJob.setOutputFormat(TextOutputFormat.class);pageJob.setOutputKeyClass(Text.class);pageJob.setOutputValueClass(LongWritable.class);pageJob.waitForCompletion(true);厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/

21、 第 7 页（4）. 运行过程分析。输入为无向图，测试图如下：610 43 52下面分析 S 集合中的顶点用深蓝色标注， NotInS 集合用网状图案标注，UnKnown 集合用白色标注。S 集合和 NotInS 集合中的顶点均是 InActive 状态，UnKnown 集合中的顶点是Active 状态。1) 步骤 1：在 SuperStep 0，每个顶点把自己的 VertexID 发送给邻接顶点,，如顶点 0 发送消息 0 到顶点 1、4 、6；顶点 1 发送消息 1 到顶点 0、3；顶点 6 发送消息 6 到顶点0、4、5。其他顶点类似。2)步骤 2：在 SuperStep 1，每个顶点收

22、到邻接顶点发送的消息，如顶点 0 收到消息1、4、6,；顶点 1 收到消息 0、3；只有顶点 0 比邻接顶点都小，故该顶点进入 S 集合，用深蓝色标注。其他顶点继续在 UnKnown 集合中。610 43 523).步骤 3 和步骤 1(步骤 1 属于第二轮) ， 在 SuperStep2 中，顶点 0 的邻接顶点收到neighbor-in-set 消息（源码中用-2 表示）进入 NotInS 集合中，即顶点 1、4、6 共 3个顶点进入 NotInS 集合中，变为 InActive 状态。同时顶点 2、3、5 依然是 UnKnown状态，2、3、5 分别向邻接顶点发送消息，顶点 2 向 4、

23、5 发送消息；顶点 3 向 1、5发送消息；顶点 5 向 2、3 、 6 发送消息。厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 基础操作实践主讲教师：林子雨 http:/ 第 8 页610 43 524) .步骤 2（第二轮）：在 SuperStep 3 中，NotInS 集合中的顶点 1、6 和 4 收到消息后被系统自动激活变为 Active 状态，所以程序中对此情况有所处理，把顶点 1、6、4直接置为 Inactive 状态，不做后续处理。顶点 2、3 收到消息 5 比自身大，则 2、3 进入 S 集合中，而顶点 5 则相反继续在 UnKnown 集合中。顶点 2、3 向邻接顶点1、4、5 发送 neighbor-in-set 消息。610 43 525) 步骤 3（第二轮）：在 SuperStep 4 中，顶点 1 和顶点 4 同（4）步处理相同。顶点 5 收到 neighbor-in-set 消息后进入 NotInS 集合中。由于 UnKnown 集合中已没有顶点，不会再向外发送消息。610 43 526) SuperStep 5 中，发现已没有活跃顶点且没有消息在传递，故结束计算。（5）. 实验结果