厦门大学-林子雨-大数据技术原理与应用-上机练习-图计算框架Hama的基础操作实践

厦门大学林子雨编著《大数据技术原理与应用》教材配套上机练习图计算框架Hama的基础操作实践（版本号：2016年1月18日版本）主讲教师：林子雨厦门大学数据库实验室二零一六年一月（版权所有，请勿用于商业用途）目录目录1作业题目...................................................................................................................................12作业目的...................................................................................................................................13作业性质...................................................................................................................................14作业考核方法...........................................................................................................................15作业提交日期与方式...............................................................................................................16作业准备...................................................................................................................................16.1、Hama计算框架的安装配置........................................................................................16.2、用Hama计算模型实现寻找最大独立集问题算法.....................................................37作业内容...................................................................................................................................98实验报告...................................................................................................................................9附录1:任课教师介绍.......................................................................................................................9附录2：课程教材介绍..................................................................................................................10厦门大学林子雨编著《大数据技术原理与应用》教材配套上机练习图计算框架Hama基础操作实践主讲教师：林子雨第1页《大数据技术原理与应用》图计算框架Hama基础操作实践上机练习说明主讲教师：林子雨E-mail:[e-mail]个人主页：作业题目图计算框架Hama基础操作实践。2作业目的旨在让学生了解Pregel图计算模型，并学会用Pregel的开源实现Hama实现一些基本操作。3作业性质课后作业，必做，作为课堂平时成绩。4作业考核方法提交上机实验报告，任课老师根据上机实验报告评定成绩。5作业提交日期与方式图计算章节内容结束后的下一周周六晚上9点之前提交。6作业准备请阅读厦门大学林子雨编著的大数据专业教材《大数据技术原理与应用》（官网：），了解图计算的概念与意义。6.1、Hama计算框架的安装配置ApacheHama是GooglePregel的开源实现，与Hadoop适合于分布式大数据处理不同，Hama主要用于分布式的矩阵、graph、网络算法的计算。简单说，Hama是在HDFS上实现的BSP(BulkSynchronousParallel)计算框架，弥补Hadoop在计算能力上的不足。（1）.安装好合适版本的jdk和hadoop，并且进行测试，保证他们能用。（2）.下载hama安装文件，从处下载合适的版本，我当时下的是0.6.4版本的。（3）.在用户主目录下创建合适的安装目录文件，我这里是在~下创建了hama文件夹作为安装目录，即~/hama为安装目录。厦门大学林子雨编著《大数据技术原理与应用》教材配套上机练习图计算框架Hama基础操作实践主讲教师：林子雨第2页（4）.将下载好的hama-0.6.4.tar.gz拷贝到~/hama中去，并用tarzvxfhama-0.6.4.tar.gz进行解压。（5）.进入hama-0.6.4中的conf文件夹，修改hama-env.sh文件，在其中加入java的home路径，即加入：ExportJAVA_HOME=/home/wanglianping/java/jdk.1.7.0_91（6）.修改hama-site.xml文件，这时hama配置的核心文件，具体内容如下：configurationpropertynamebsp.master.address/namevalue192.168.91.128:40000/valuedescriptionTheaddressofthebspmasterserver.Eithertheliteralstringlocalorahost:portfordistributedmode/description/propertypropertynamefs.default.name/namevaluehdfs://192.168.91.128:9000//valuedescriptionThenameofthedefaultfilesystem.Eithertheliteralstringlocalorahost:portforHDFS./description/propertypropertynamehama.zookeeper.quorum/namevalue192.168.91.128/valuedescriptionCommaseparatedlistofserversintheZooKeeperQuorum.Forexample,host1.mydomain.com,host2.mydomain.com,host3.mydomain.com.Bydefaultthisissettolocalhostforlocalandpseudo-distributedmodesofoperation.Forafully-distributedsetup,thisshouldbesettoafulllistofZooKeeperquorumservers.IfHAMA_MANAGES_ZKissetinhama-env.shthisisthelistofserverswhichwewillstart/stopzookeeperon./description厦门大学林子雨编著《大数据技术原理与应用》教材配套上机练习图计算框架Hama基础操作实践主讲教师：林子雨第3页/propertypropertynamehama.zookeeper.property.clientPort/namevalue2181/value/property/configuration其中，bsp.master.address即bsp中的BSPMaster的地址和端口。fs.default.name这个值要特别注意，是hadoop中nameNode的地址和端口，因为hama要用到hadoop的hdfs分布式文件系统。剩下的俩个是zookeeper的相关配置。（7）.另外，在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计算模型实现寻找最大独立集问题算法厦门大学林子雨编著《大数据技术原理与应用》教材配套上机练习图计算框架Hama基础操作实践主讲教师：林子雨第4页（1）.本算法参考Luby'sclassicparallelalgorithm《asimpleparallelalgorithmformaximalindependentsetproblem》，把顶点分为三类：1)S:TheMISbeingconstructed.Startsemptyandgrowsiniterations.2)NotInS:VerticesthathaveatleastoneedgetoavertexinSandasaresultcannotbeinS.3)Unknown:VerticesthatdonothaveanedgetoanyvertexinSbutarenotyetinS.（2）.Hama模型下MIS（MaximalIndependentSet）算法描述。1）初始时，把所有顶点的value值赋值为自己的vertexID，表明初始所有顶点均在UnKnown集合中，然后把自己的VertexID发送给邻接顶点。2)若顶点u的VertexID比自己所有邻接顶点都小，则该顶点进入S集合中，并发送neighbor-in-set消息给所有邻接顶点，通知它们退出Unknown集合进入到NotInS集合中，并最后把u置为InActive状态；否则，顶点u继续保持UnKnown状态。3)S集合中顶点的邻接顶点收到neighbor-in-set消息，则该顶点进入NotInS，并且设置为Inactive状态。返回继续迭代，直到UnKnown集合为空。（3）.程序中按照顶点value取值不同来区分顶点的类别，具体如下：1)value等于ver