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

普开数据大数据应用实例：基于Hadoop的大规模数据排序算法基于Hadoop的大规模数据排序目录一、前言4二、Hadoop及Mapreduce的相关介绍41.Hadoop4(1)Hadoop简介4(2)Hadoop架构5(3)分布式计算模型52.Mapreduce5(1)mapreduce和hadoop起源5(2)mapreduce工作流程6(3)运行环境7(4)输入与输出7(5)Map/Reduce‐用户界面7三、大规模数据排序81.简介82.Nutch9四、算法分析101.Sort算法分析10(1)排序实例10(2)运行排序基准测试10(3)代码分析102.Secondsort算法分析12(1)工作原理12(2)具体步骤12(3)SecondarySort.java的部分代码133.Terasort算法分析15(1)概述15(2)算法思想15(3)Terasort算法17五、参考资料19一、前言我们小组主要对基于[hadoop的大规模数据排序算法、海量数据的生成做了一定的研究。我们首先对于hadoop做了初步了解，其次，mapreduce是hadoop的很重要的算法，我们在第二阶段对mapreduce以及一些代码做了分析。第三阶段，我们安装虚拟机和Linux以及hadoop的软件，配置运行环境。第四阶段，我们对大规模数据排序进行深入的研究，对nutch进行了简单的了解。第五阶段，对一些源代码进行分析，主要是排序算法中的sort.java,secondsort.java,terasort。下面的正文中将作出具体的介绍。二、Hadoop及Mapreduce的相关介绍1.Hadoop(1)Hadoop简介Hadoop是一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了一个分布式文件系统，简称HDFS。HDFS有着高容错性的特点，并且设计用来部署在低廉的硬件上。而且它提供高传输率来访问应用程序的数据，适合那些有着超大数据集的应用程序。(2)Hadoop架构图表1hadoop架构Hadoop有许多元素构成。其昀底部是HDFS，它存储Hadoop集群中所有存储节点上的文件。HDFS的上一层是MapReduce引擎，该引擎由JobTrackers和TaskTrackers组成。(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阶段。①在正式执行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。图表2mapreduce简单工作流程(3)运行环境∙HadoopStreaming是一种运行作业的实用工具，它允许用户创建和运行任何可执行程序(例如：Shell工具)来做为mapper和reducer。∙HadoopPipes是一个与SWIG兼容的C++API(没有基于JNITM技术)，它也可用于实现Map/Reduce应用程序。(4)输入与输出Map/Reduce框架运转在KEY,value键值对上，也就是说，框架把作业的输入看为是一组KEY,value键值对，同样也产出一组KEY,value键值对做为作业的输出，这两组键值对的类型可能不同。框架需要对key和value的类(class)进行序列化操作，因此，这些类需要实现Writable接口。另外，为了方便框架执行排序操作，key类必须实现WritableComparable接口。一个Map/Reduce作业的输入和输出类型如下所示：(input)K1,v1‐map‐K2,v2‐combine‐K2,v2‐reduce‐K3,v3(output)(5)Map/Reduce‐用户界面这部分文档为用户将会面临的Map/Reduce框架中的各个环节提供了适当的细节。这应该会帮助用户更细粒度地去实现、配置和调优作业。然而，需要注意每个类/接口的javadoc文档提供昀全面的文档。我们会先看看Mapper和Reducer接口。应用程序通常会通过提供map和reduce方法来实现它们。然后，我们会讨论其他的核心接口，其中包括：JobConf，JobClient，Partitioner，OutputCollector，Reporter，InputFormat，OutputFormat等等。昀后，我们将通过讨论框架中一些有用的功能点(例如：DistributedCache，IsolationRunner等等)来收尾。三、大规模数据排序1.简介使用hadoop进行大量的数据排序排序昀直观的方法是把文件所有内容给map之后，map不做任何处理，直接输出给一个reduce，利用hadoop的自己的shuffle机制，对所有数据进行排序，而后由reduce直接输出。然而这样的方法跟单机毫无差别，完全无法用到多机分布式计算的便利。因此这种方法是不行的。利用hadoop分而治之的计算模型，可以参照快速排序的思想。在这里我们先简单回忆一下快速排序。快速排序基本步骤就是需要现在所有数据中选取一个作为支点。然后将大于这个支点的放在一边，小于这个支点的放在另一边。设想如果我们有N个支点(这里可以称为标尺)，就可以把所有的数据分成N+1个part，将这N+1个part丢给reduce，由hadoop自动排序，昀后输出N+1个内部有序的文件，再把这N+1个文件首尾相连合并成一个文件，收工。由此我们可以归纳出这样一个用hadoop对大量数据排序的步骤：①对待排序数据进行抽样;②对抽样数据进行排序，产生标尺;③Map对输入的每条数据计算其处于哪两个标尺之间;将数据发给对应区间ID的reduce④Reduce将获得数据直接输出。这里使用对一组url进行排序来作为例子：图表3url排序如何将数据发给一个指定ID的reduce?hadoop提供了多种分区算法。这些算法根据map输出的数据的key来确定此数据应该发给哪个reduce(reduce的排序也依赖key)。因此，如果需要将数据发给某个reduce，只要在输出数据的同时，提供一个key(在上面这个例子中就是reduce的ID+url)，数据就该去哪儿去哪儿了。2.NutchNutch是一个由Java实现的，刚刚诞生开放源代码(open‐source)的web搜索引擎。Nutch主要分为爬虫crawler和查询searcher两部分。Crawler主要用于从网络上抓取网页并为这些网页建立索引。Searcher主要利用这些索引检索用户的查找关键词来产生查找结果。两者之间的接口是索引，所以除去索引部分，两者之间的耦合度很低。Crawler的重点在两个方面，Crawler的工作流程和涉及的数据文件的格式和含义。Crawler的工作原理：首先Crawler根据WebDB生成一个待抓取网页的URL集合叫做Fetchlist，接着下载线程Fetcher根据Fetchlist将网页抓取回来，如果下载线程有很多个，那么就生成很多个Fetchlist，也就是一个Fetcher对应一个Fetchlist。然后Crawler用抓取回来的网页更新WebDB，根据更新后的WebDB生成新的Fetchlist，里面是未抓取的或者新发现的URLs，然后下一轮抓取循环重新开始。四、算法分析1.Sort算法分析(1)排序实例排序实例仅仅用map/reduce框架来把输入目录排序放到输出目录。输入和输出必须是顺序文件，键和值是BytesWritable.mapper是预先定义的IdentityMapper，reducer是预先定义的IdentityReducer，两个都是把输入直接的输出。要运行这个例子：bin/hadoopjarhadoop‐*‐examples.jarsort[‐m#maps][‐r#reduces](2)运行排序基准测试为了使得排序例子作为一个基准测试，用RandomWriter产生10GB/node的数据。然后用排序实例来进行排序。这个提供了一个可扩展性依赖于集群的大小的排序基准。默认情况下，排序实例用1.0*capacity作为reduces的数量，依赖于你的集群的大小你可能会在1.75*capacity的情况下得到更好的结果。(3)代码分析在eclipse中设置参数：/home/hadoop/rand/part‐00000/home/hadoop/rand‐sort其中/home/hadoop/rand/part‐00000表示输入路径，/home/hadoop/rand‐sort表示输出路径。数据来源我们这里输入参数中的“/home/hadoop/rand/part‐00000”是通过hadoop实例RandomWriter这个实例得到的。为了节省时间，hadoop实例RandomWriter中得到了两个文件，我们这里指使用了一个文件part‐00000。如果要对两个文件都进行排序操作，那么输入路径只需要是目录即可。Sort算法源代码a)源码位置/local/zkl/hadoop/hadoop‐0.20.1/hadoop‐0.20.1/src/examples/org/apache/hadoop/examples/Sort.javab)下面程序是一段关于Sort算法的源代码：26.*Torun:bin/hadoopjarbuild/hadoop‐examples.jarsort27.*[‐mmaps][‐rreduces]28.*[‐inFormatinputformatclass]29.*[‐outFormatoutputformatclass]30.*[‐outKeyoutputkeyclass]31.*[‐outValueoutputvalueclass]32.*[‐totalOrderpcntnumsamplesmaxsplits]33.*in‐dirout‐dir34.*/35.publicclassSortK,VextendsConfiguredimpleme