Hadoop应用实例基于Hadoop的大规模数据排序算法

基于Hadoop的大规模数据排序算法信息工程学院网络工程——基于Hadoop的大规模数据排序算法第2页(共40页)网络工程——终期报告基于Hadoop的大规模数据排序小组成员：组长：韩旭红1091000161组员：李巍1091000167组员：李越1091000169组员：闫悦1091000178信息工程学院网络工程——基于Hadoop的大规模数据排序算法第3页(共40页)组员：焦天禹1091000163目录一、前言........................................................................................5二、Hadoop及Mapreduce的相关介绍........................................61.Hadoop..................................................................................6（1）Hadoop简介................................................................6（2）Hadoop架构................................................................6（3）分布式计算模型..........................................................72.Mapreduce............................................................................7（1）mapreduce和hadoop起源.......................................7（2）mapreduce工作流程...................................................7（3）运行环境......................................................................9（4）输入与输出..................................................................9（5）Map/Reduce-用户界面..........................................10三、大规模数据排序..................................................................11信息工程学院网络工程——基于Hadoop的大规模数据排序算法第4页(共40页)1.简介.....................................................................................112.Nutch...................................................................................12四、算法分析..............................................................................131.Sort算法分析....................................................................13（1）排序实例....................................................................13（2）运行排序基准测试....................................................14（3）代码分析....................................................................142.Secondsort算法分析........................................................17（1）工作原理....................................................................17（2）具体步骤....................................................................18（3）SecondarySort.java的部分代码................................193.Terasort算法分析............................................................24（1）概述...........................................................................24（2）算法思想....................................................................24（3）Terasort算法..............................................................27五、参考资料..............................................................................32六、小组成员个人总结..............................................................321.1091000161韩旭红...........................................................322.1091000167李巍...............................................................343.1091000169李越...............................................................36信息工程学院网络工程——基于Hadoop的大规模数据排序算法第5页(共40页)4.1091000178闫悦...............................................................375.1091000163焦天禹...........................................................38一、前言我们小组主要对基于[hadoop的大规模数据排序算法、海量数据的生成做了一定的研究。我们首先对于hadoop做了初步了解，其次，mapreduce是hadoop的很重要的算法，我们在第二阶段对mapreduce以及一些代码做了分析。第三阶段，我们安装虚拟机和Linux以及hadoop的软件，配置运行环境。第四阶段，我们对大规模数据排序进行深入的研究，对nutch进行了简单的了解。第五阶段，对一些源代码进行分析，主要是排序算法中的sort.java,secondsort.java,terasort。下面的正文中将作出具体的介绍。信息工程学院网络工程——基于Hadoop的大规模数据排序算法第6页(共40页)二、Hadoop及Mapreduce的相关介绍1.Hadoop（1）Hadoop简介Hadoop是一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了一个分布式文件系统，简称HDFS。HDFS有着高容错性的特点，并且设计用来部署在低廉的硬件上。而且它提供高传输率来访问应用程序的数据，适合那些有着超大数据集的应用程序。（2）Hadoop架构图表1hadoop架构Hadoop有许多元素构成。其最底部是HDFS，它存储Hadoop集群中所有存储节点上的文件。HDFS的上一层是MapReduce引擎，该引擎由JobTrackers和TaskTrackers组成。信息工程学院网络工程——基于Hadoop的大规模数据排序算法第7页(共40页)（3）分布式计算模型一个hadoop集群往往有几十台甚至成百上千台lowcost的计算机组成，我们运行的每一个任务都要在这些计算机上做任务的分发，执行中间数据排序以及最后的汇总，期间还包含节点发现，任务的重试，故障节点替换等等等等的维护以及异常情况处理。所以说hadoop就是一个计算模型。一个分布式的计算模型。2.Mapreduce（1）mapreduce和hadoop起源MapReduce借用了函数式编程的概念，是Google发明的一种数据处理模型。因为Google几乎爬了互联网上的所有网页，要为处理这些网页并为搜索引擎建立索引是一项非常艰巨的任务，必须借助成千上万台机器同时工作（也就是分布式并行处理），才有可能完成建立索引的任务。所以，Google发明了MapReduce数据处理模型，而且他们还就此发表了相关论文。后来，DougCutting老大就根据这篇论文硬生生的复制了一个MapReduce出来，也就是今天的Hadoop。（2）mapreduce工作流程MapReduce处理数据过程主要分成2个阶段：map阶段和reduce阶段。先执行map阶段，再执行reduce阶段。信息工程学院网络工程——基于Hadoop的大规模数据排序算法第8页(共40页)①在正式执行map函数前，需要对输入进行“分片”（就是将海量数据分成大概相等的“块”，hadoop的一个分片默认是64M），以便于多个map同时工作，每一个map任务处理一个“分片”。②分片完毕后，多台机器就可以同时进行map工作了。map函数要做的事情，相当于对数据进行“预处理”，输出所要的“关切”。map对每条记录的输出以key,valuepair的形式输出。③在进入reduce阶段之前，要将各个map中相关的数据（key相同的数据）归结到一起，发往一个reducer。这里面就涉及到多个map的输出“混合地”对应多个reducer的情况，这个过程叫做“洗牌”。④接下来进入reduce阶段。相同的key的map输出会到达同一个reducer。reducer对key相同的多个value进行“reduce操作”，最后一个key的一串value经过reduce函数的作用后，变成了一个value。信息工程学院网络工程——基于Hadoop的大规模数据排序算法第9页(共40页)图表2mapreduce简单工作流程（3）运行环境HadoopStreaming是一种运行作业的实用工具，它允许用户创建和运行任何可执行程序（例如：Shell工具）来做为mapper和reducer。HadoopPipes是一个与SWIG兼容的C++API（没有基于JNITM技术），它也可用于实现Map/Reduce应用程序。（4）输入与输出Map/Reduce框架运转在key,value键值对上，也就是说，框架把作业的输入看为是一组key,value键值对，同样也产出一组key,value键值对做为作业的输出，这两组键值对的类型可能不同。信息工程学院网络工程——基于Hadoop的大规模数据排序算法第10页(共40页)框架需要对key和value的类(class)进行序列化操作，因此，这些类需要实现