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

基于Hadoop的大规模数据排序算法 网络工程——终期报告 基于Hadoop的大规模数据排序 小组成员： 组长：韩旭红 1091000161 组员：李巍 1091000167 组员：李1091000169 组员： 1091000178 组员：焦天禹 1091000163 目录 一、 前言 4 二、 Hadoop及Mapreduce的相关介绍 4 1. Hadoop 4 （1） Hadoop简介 4 （2） Hadoop架构 5 （3） 分布式计算模型 5 2. Mapreduce 5 （1） map reduce 和hadoop起源 5 （2） mapreduce工作流程 6 （3） 运行环境 7 （4） 输入与输出 7 （5） Map/Reduce - 用户界面 7 三、 大规模数据排序 8 1. 简介 8 2. Nutch 9 四、 算法分析 10 1. Sort算法分析 10 （1） 排序实例 10 （2） 运行排序基准测试 10 （3） 代码分析 10 2. Secondsort算法分析 12 （1） 工作原理 12 （2） 具体步骤 12 （3） SecondarySort.java的部分代码 13 3. Terasort算法分析 15 （1） 概述 15 （2） 算法思想 15 （3） Terasort算法 17 五、 参考资料 19 六、 小组成员个人总结 20 1. 1091000161 韩旭红 20 2. 1091000167 李巍 21 3. 1091000169 李越 21 4. 1091000178 闫悦 21 5. 1091000163 焦天禹 22 前言 我们小组主要对基于[hadoop的大规模数据排序算法、海量数据的生成做了一定的研究。我们首先对于hadoop做了初步了解，其次，mapreduce是hadoop的很重要的算法，我们在第二阶段对mapreduce以及一些代码做了分析。第三阶段，我们安装虚拟机和Linux以及hadoop的软件，配置运行环境。第四阶段，我们对大规模数据排序进行深入的研究，对nutch进行了简单的了解。第五阶段，对一些源代码进行分析，主要是排序算法中的sort.java,secondsort.java,terasort。下面的正文中将作出具体的介绍。 Hadoop及Mapreduce的相关介绍 Hadoop Hadoop简介 Hadoop是一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了一个分布式文件系统，简称HDFS。HDFS有着高容错性的特点，并且设计用来部署在低廉的硬件上。而且它提供高传输率来访问应用程序的数据，适合那些有着超大数据集的应用程序。 H 图表 1 Hadoop 有许多元素构成。其最底部是HDFS，它存储 Hadoop 集群中所有存储节点上的文件。HDFS的上一层是 MapReduce 引擎，该引擎由 JobTrackers 和 TaskTrackers 组成。 分布式计算模型 一个hadoop集群往往有几十台甚至成百上千台low cost的计算机组成，我们运行的每一个任务都要在这些计算机上做任务的分发，执行中间数据排序以及最后的汇总，期间还包含节点发现，任务的重试，故障节点替换等等等等的维护以及异常情况处理。 所以说hadoop就是一个计算模型。一个分布式的计算模型。 M map reduce 和hadoop起源 MapReduce借用了函数式编程的概念，是Google发明的一种数据处理模型。因为Google几乎爬了互联网上的所有网页，要为处理这些网页并为有哪些信誉好的足球投注网站引擎建立索引是一项非常艰巨的任务，必须借助成千上万台机器同时工作（也就是分布式并行处理），才有可能完成建立索引的任务。 所以，Google发明了MapReduce数据处理模型，而且他们还就此发表了相关论文。 后来，Doug Cutting老大就根据这篇论文硬生生的复制了一个MapReduce出来，也就是今天的Hadoop。 MapReduce处理数据过程主要分成2个阶段：map阶段和reduce阶段。先执行map阶段，再执行reduce阶段。 在正式执行map函数前，需要对输入进行“分片”（就是将海量数据分成大概相等的“块”，hadoop的一个分片默认是64M），以便于多个map同时工作，每一个map任务处理一个“分片”。 分片完毕后，多台机器就可以同时进行map工作了。 map函数要做的事情，相当于对数据进行“预处理”，输出所要的“关切”。 map对每条记录的输出以key,value