厦门大学林子雨编著.DOC

1、 厦门大学 林子雨编著 大数据技术原理与应用 教材配套上机练习 图计算框架 Hama 的 基础操作实践 （版本号： 2016 年 1 月 18 日版本） 主讲教师：林子雨 厦门大学数据库实验室 二零一 六 年 一 月 （版权所有，请勿用于商业用途） 目录 目录 1 作业题目 . 1 2 作业目的 . 1 3 作业性质 . 1 4 作业考核方法 . 1 5 作业提交日期与方式 . 1 6 作业准备 . 1 6.1、 Hama 计算框架的安装配置 . 1 6.2、用 Hama 计算模型实现寻找最大独立集问题算法 . 3 7 作业内容 . 9 8 实验报告 . 9 附录 1:任课教师介绍 . 9 附

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

3、根据上机实验报告评定成绩。 5 作业提交日期与方式 图计算 章节内容结束后的下一周周六晚上 9 点之前提交。 6 作业 准备 请阅读厦门大学林子雨编著的大数据专业教材大数据技术原理与应用（官网：http:/ 的 概念与意义 。 6.1、 Hama 计算 框架 的 安装配置 Apache Hama 是 Google Pregel 的开源实现，与 Hadoop 适合于分布式大数据处理不同， Hama 主要用于分布式的矩阵、 graph、网络算法的计算。简单说， Hama 是在 HDFS上实现的 BSP(Bulk Synchronous Parallel)计算框架，弥补 Hadoop 在计算能力上的

4、不足。 （ 1） . 安装好合适版本的 jdk 和 hadoop，并且进行测试，保证他们能用。 （ 2） . 下载 hama 安装文件，从 http:/hama.apache.org/downloads.html 处下载合适的版本，我当时下的是 0.6.4 版本的。 （ 3） . 在用户主目录下创建合适的安装目录文件，我这里是在 下创建了 hama 文件夹作为安装目录，即 /hama 为安装目录。 厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算 框架 Hama 基础 操作实践 主讲教师：林子雨 http:/ 第 2 页 （ 4） . 将下载好的 hama-0.6.4.tar.

5、gz 拷贝到 /hama 中去，并用 tar zvxf hama-0.6.4.tar.gz进行解压。 （ 5） . 进入 hama-0.6.4 中的 conf 文件夹，修改 hama-env.sh 文件，在其中加入 java 的home 路径，即加入： Export JAVA_HOME=/home/wanglianping/java/jdk.1.7.0_91 （ 6） . 修改 hama-site.xml 文件，这时 hama 配置的核心文件，具体内容如下： bsp.master.address 192.168.91.128:40000 The address of the bsp maste

6、r server. Either the literal string “local“ or a host:port for distributed mode fs.default.name hdfs:/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.quorum 192.168.91.128 Comma separated list of servers in the ZooKe

7、eper Quorum. For example, “,,“. 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 st

8、art/stop zookeeper on. 厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算 框架 Hama 基础 操作实践 主讲教师：林子雨 http:/ 第 3 页 hama.zookeeper.property.clientPort 2181 其中 ， bsp.master.address 即 bsp 中的 BSPMaster 的地址和端口。 fs.default.name 这个值要特别注意，是 hadoop 中 nameNode 的地址和端口，因为 hama 要 用到 hadoop 的 hdfs分布式文件系统。剩下的俩个是 zookeeper 的相关配置 。 （ 7）

9、 .另外，在 conf 文件夹下还有一个 groomservers 文件，这个在分布式环境下配置groomserver 的地址，在单机模式下就不用配置了，里面默认值为 localhost。同时，你也可以在 /.bashrc 中添加 hama 的环境变量，这样每次启动就不同转到相应的目录下去了 。 （ 8） . 启动 hadoop，并验证是否启动成功。命令： HADOOP_HOME/bin/start-all.sh，如果启动成功，如下： 启动 hama，命令： HAMA_HOME/bin/start-bspd.sh,结果如下： 出现上述结果，则表明 hama 已经成功启动。 6.2、用 Hama

10、 计算 模型 实现 寻找最大独立集问题 算法 厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算 框架 Hama 基础 操作实践 主讲教师：林子雨 http:/ 第 4 页 （ 1） . 本算法参考 Lubys classic parallel algorithm a simple parallel algorithm for maximal independent set problem，把顶点分为三类： 1) S:The MIS being constructed. Starts empty and grows in iterations. 2) NotInS: Vertic

11、es 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 vertex in S but are not yet in S. （ 2） .Hama 模型 下 MIS（ Maximal Independent Set） 算法描述。 1）初始时 ，把所有顶点的 value 值赋值为自己的 vertexID， 表明初始所有顶点均在 UnKnown 集合中，然后 把自己的 VertexID 发送给

12、邻接顶点 。 2) 若顶点 u 的 VertexID 比自己所有邻接顶点都小，则该顶点进入 S 集合中，并发送neighbor-in-set 消息给所有邻接顶点，通知它们退出 Unknown 集合进入到 NotInS 集合中，并最后把 u 置为 InActive 状态；否则，顶点 u 继续保持 UnKnown 状态。 3) S 集合中顶点的邻接顶点收到 neighbor-in-set 消息，则该顶点进入 NotInS，并且 设置为 Inactive 状态。 返回 继续迭代，直到 UnKnown 集合为空。 （ 3） . 程序中按照顶点 value 取值不同来区分顶点的类别， 具体 如下： 1)

13、 value 等于 vertexID ,表示顶点在 Unknown 集合中； 2) value 等于 -1 ,表示顶点在 S 集合中 3) value 等于 -2 ，表示顶点在 NotInS 集合中。 当所有顶点进入 S 或者 NotInS 集合中，就停止计算，表明已找到一个 MIS。源码如下： package graph.mis; import java.io.IOException; import java.util.Iterator; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.Path

14、; import org.apache.hadoop.io.LongWritable; import org.apache.hadoop.io.NullWritable; import org.apache.hadoop.io.Text; import org.apache.hama.HamaConfiguration; import org.apache.hama.bsp.HashPartitioner; import org.apache.hama.bsp.TextInputFormat; import org.apache.hama.bsp.TextOutputFormat; impor

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

16、public void compute(Iterator messages) throws IOException if (getSuperstepCount() = 0) setValue(getVertexID(); sendMessageToNeighbors(getValue(); else if(getValue().get()=-2) voteToHalt(); else boolean revMsg = false; while (messages.hasNext() revMsg = true; long msg = messages.next().get(); if (msg

17、 = -2) setValue(new LongWritable(-2); voteToHalt(); return; else if (msg Override public boolean parseVertex(LongWritable key, Text value, Vertex vertex) throws Exception String split = value.toString().split(“t“); for (int i = 0; i ( new LongWritable(Long.parseLong(spliti), null); return true; publ

18、ic static void main(String args) throws IOException, InterruptedException, ClassNotFoundException if (args.length “); System.exit(-1); HamaConfiguration conf = new HamaConfiguration(new Configuration(); GraphJob pageJob = new GraphJob(conf, FindMIS.class); pageJob.setJobName(“Find a MIS“); pageJob.s

19、etMaxIteration(30); pageJob.setVertexClass(MISVertex.class); pageJob.setInputPath(new Path(args0); pageJob.setOutputPath(new Path(args1); pageJob.setVertexIDClass(LongWritable.class); pageJob.setVertexValueClass(LongWritable.class); pageJob.setEdgeValueClass(NullWritable.class); pageJob.setInputKeyC

20、lass(LongWritable.class); pageJob.setInputValueClass(Text.class); pageJob.setInputFormat(TextInputFormat.class); pageJob.setVertexInputReaderClass(MISTextReader.class); pageJob.setPartitioner(HashPartitioner.class); pageJob.setOutputFormat(TextOutputFormat.class); pageJob.setOutputKeyClass(Text.clas

21、s); pageJob.setOutputValueClass(LongWritable.class); pageJob.waitForCompletion(true); （ 4） . 运行过程分析。输入为无向图，测试图如下： 厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算 框架 Hama 基础 操作实践 主讲教师：林子雨 http:/ 第 7 页 610 43 52下面分析 S 集合中的顶点 用深 蓝 色标注， NotInS 集合用 网状 图案 标注 ， UnKnown 集合用白 色标注。 S 集合和 NotInS 集合中的顶点均是 InActive 状态， UnKnown

22、 集合中的顶点是Active 状态。 1) 步骤 1：在 SuperStep 0，每个顶点把自己的 VertexID 发送给邻接顶点 ,，如顶点 0 发送消息 0 到顶点 1、 4、 6；顶点 1 发送消息 1 到顶点 0、 3；顶点 6 发送消息 6 到顶点 0、 4、5。其他顶点类似。 2)步骤 2：在 SuperStep 1，每个顶点收到邻接顶点发送的消息，如顶点 0 收到消息 1、 4、6,；顶点 1 收到消息 0、 3；只有顶点 0 比邻接顶点都小，故该 顶点进入 S 集合，用 深 蓝 色标注。其他顶点继续在 UnKnown 集合中。 610 43 523).步骤 3 和步骤 1(步

23、骤 1 属于第二轮 )， 在 SuperStep2 中，顶点 0 的邻接顶 点收到neighbor-in-set 消息（源码中用 -2 表示）进入 NotInS 集合中，即顶点 1、 4、 6 共 3 个顶点进入 NotInS 集合中，变为 InActive 状态。同时顶点 2、 3、 5 依然是 UnKnown 状态， 2、 3、 5 分别向邻接顶点发送消息，顶点 2 向 4、 5 发送消息；顶点 3 向 1、 5 发送消息 ； 顶点 5 向 2、 3、 6 发送 消息。 厦门大学林子雨编著大数据技术原理与应用 教材配套上机练习 图计算 框架 Hama 基础 操作实践 主讲教师：林子雨 ht

24、tp:/ 第 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） . 实验结果