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

1、基于Hadoop的大规模数据排序算法网络项目最终报告基于Hadoop的大规模数据排序小组成员：组长：韩组员：李伟团队成员：李越组员：严月组员：焦天宇目录一.导言4二。Hadoop和Mapreduce 4简介1.Hadoop4(1)Hadoop简介4(2)Hadoop体系结构5(3)分布式计算模型52.Mapreduce5(1)地图简化和hadoop起源5(2)mapreduce工作流6(3)运行环境7(4)输入和输出7(5)地图/缩小-用户界面7三、大规模数据排序81.导言82.螺母9四.算法分析101.排序算法分析10(1)订购示例10(2)运行排名基准测试10(3)代码分析102.分析2。

2、第二排序算法12(1)工作原理12(2)具体步骤12(3)SecondarySort.java 13的一些代码3.万亿排序算法分析15(1)概述15(2)算法思想15(3)太排序算法17V.参考文献19Vi .小组成员的个人总结201.韩20李伟213.李越4.颜悦215.焦天宇22一、导言我们团队主要研究了基于hadoop的大规模数据排序算法和海量数据的生成。首先，我们对hadoop有了初步的了解。其次，mapreduce是hadoop的一个非常重要的算法。我们在第二阶段分析了mapreduce和一些代码。在第三阶段，我们安装了虚拟机、Linux和hadoop软件，并配置了操作环境。在第四阶

3、段，我们对大规模数据分类进行了深入研究，对nutch做了简单的了解。在第五阶段，分析了一些源代码，主要是SORT。Java，SECOND SORT。排序算法中的Java和TERASORT。下面的文字将给出一个具体的介绍。二。Hadoop和Mapreduce简介1.Hadoop(Hadoop简介Hadoop是由阿帕奇基金会开发的分布式系统基础设施。用户可以在不知道分布式底层细节的情况下开发分布式程序。充分利用集群的能力进行高速计算和存储。Hadoop实现了一个分布式文件系统，简称HDFS。HDFS具有很高的容错能力，并且被设计为部署在廉价的硬件上。此外，它还提供了访问应用程序数据的高传输速率，适

4、用于具有大数据集的应用程序。(2) Hadoop架构图表1 hadoop架构Hadoop有许多元素。底部是HDFS，它将文件存储在Hadoop群集中的所有存储节点上。在HDFS之上的是MapReduce引擎，它由作业跟踪器和任务跟踪器组成。(3)分布式计算模型hadoop集群通常由数十台甚至数百台低成本计算机组成。我们运行的每个任务都必须在这些计算机上进行任务分配、中间数据排序和最终总结。该阶段还包括节点发现、任务重试、故障节点替换等的维护和异常处理。所以hadoop是一种计算模型。分布式计算模型。2.Mapreduce(1)地图归约和hadoop原点MapReduce借用了函数式编程的概念，

5、是谷歌发明的一种数据处理模型。因为谷歌已经抓取了互联网上几乎所有的网页，所以处理这些网页并为搜索引擎建立索引是一项非常困难的任务。只有当数千台机器同时工作时(即分布式并行处理)，索引任务才能完成。因此，谷歌发明了MapReduce数据处理模型，并发表了相关论文。后来，根据这篇文章，老板道格切割突然复制了一个地图减少，这是今天的Hadoop。(2) mapreduce工作流数据处理的Mapreduce过程主要分为两个阶段：Map阶段和reduce阶段。映射阶段在减少阶段之前执行。(1)在正式执行地图功能之前，需要对输入进行“切片”(即，将海量数据分成大致相等的“块”，一个hadoop切片默认为6

6、4M)，以便多个地图可以同时工作，每个地图任务处理一个“切片”。(2)切片后，多台机器可以同时在地图上工作。地图功能需要做的相当于“预处理”数据并输出所需的“关注点”。每条记录的映射输出以成对的形式输出。(3)在进入归约阶段之前，应将每张地图中的相关数据(关键相同数据)汇总并发送至归约器。在这种情况下，涉及到用多个缩减器“混合”的多个地图的输出，并且这个过程被称为“洗牌”。(4)接下来，进入缩减阶段。相同键的映射输出将到达相同的减压器。Reducer用同一个键“减少”多个值，最后一个键的一串值在reduce函数后变成一个值。图表2映射简化简单工作流(3)运行环境Hadoop Streaming

7、是一个用于运行作业的实用工具，它允许用户创建和运行任何可执行程序(例如，外壳工具)作为映射器和缩减器。Hadoop管道是一个与SWIG兼容的C API(不是基于JNITM技术)，它也可以用来实现映射/简化应用程序。(4)输入和输出映射/简化框架对键值对进行操作，也就是说，该框架将作业的输入视为一组键值对，并生成一组键值对作为作业的输出。两组键值对的类型可能不同。框架需要序列化键和值的类，因此这些类需要实现可写接口。此外，为了便于框架执行排序操作，键类必须实现可写可比较接口。映射/简化作业的输入和输出类型如下：(输入)-映射-合并-减少-(输出)(5)地图/简化用户界面文档的这一部分为用户将面临

8、的地图/简化框架中的每个链接提供了适当的细节。这将有助于用户以更精细的粒度实现、配置和调整作业。然而，重要的是要注意每个类/接口的javadoc文档提供了最全面的文档。我们将首先研究映射器和缩减器接口。应用程序通常通过提供映射和简化方法来实现它们。然后，我们将讨论其他核心接口，包括：作业配置、作业客户端、分区器、输出收集器、报告器、输入格式、输出格式等。最后，我们将通过讨论框架中一些有用的功能点来结束本文(例如分布式缓存、隔离运行器等)。)。第三，大规模数据排序1.介绍使用hadoop对大量数据进行排序的最直观方式是使用hadoop自身的洗牌机制对所有数据进行排序，在所有文件的内容都被赋予ma

9、p后，map不做任何处理而直接输出到reduce，然后所有数据都被reduce直接输出。然而，这种方法与单个计算机没有什么不同，并且不能用于多计算机分布式计算的便利性。因此，这种方法是不可行的。使用hadoop的分而治之计算模型，我们可以参考快速排序的思想。这里，让我们简单回顾一下快速排序。快速排序的基本步骤是选择所有数据中的一个作为支点。然后把比这个支点大的放在一边，把比这个支点小的放在另一边。想象一下，如果我们有N个支点(这里可以称之为标尺)，我们可以将所有的数据分成N 1个部分，将这些N 1个部分进行简化，通过hadoop自动排序，最后输出N 1个内部排序的文件，然后将这些N 1个文件首

10、尾相连地合并成一个文件，并完成工作。由此，我们可以总结出用hadoop对大量数据进行排序的步骤：(1)采样待分类数据；(2)对采样数据进行排序以生成标尺；(3)地图计算每条输入数据在哪两个比例之间；发送数据以减少对应的间隔标识减少将直接输出获得的数据。这里我们用排序一组网址作为例子：图表3网址排序如何使用指定的标识发送数据进行缩减？Hadoop提供了多种分区算法。这些算法根据地图输出数据的关键点(减少的顺序也取决于关键点)来确定应该将数据发送到哪个减少点。因此，如果您需要将数据发送到reduce，只要您在输出数据时提供一个键(在上面的示例中，就是reduce的ID url)，数据应该放在哪里？

11、2.NutchNutch是一个Java实现的网络搜索引擎，刚刚诞生于开源。Nutch主要分为爬虫和搜索器。爬虫主要用于从网络上抓取网页并建立索引。搜索者主要使用这些索引来检索用户的搜索关键词以生成搜索结果。两者之间的接口是索引，因此除了索引部分之外，两者之间的耦合度很低。爬虫关注两个方面：爬虫的工作流程和所涉及的数据文件的格式和含义。爬虫的工作原理是：首先，爬虫根据网络数据库生成一个待抓取网页的网址集，称为抓取列表，然后抓取器根据抓取列表抓取网页。如果有许多下载线程，则生成许多fetchlist，即一个Fetcher对应一个fetchlist。然后，爬虫用检索到的网页更新网络数据库，根据更新后

12、的网络数据库生成一个新的抓取列表，其中包含未抓取或新发现的网址，然后下一个抓取周期再次开始。第四，算法分析1.排序算法分析(1)整理实例排序实例只使用map/reduce框架将输入目录排序到输出目录。输入和输出必须是顺序文件，键和值是字节可写的。映射器是预定义的标识符映射器，缩减器是预定义的标识符缩减器，两者都是输入的直接输出。运行此示例：bin/Hadoop jarhadoop-*-examples . jarsort-m # maps-r # reduction(2)运行排序基准测试为了将排序示例用作基准测试，使用随机写入器生成10GB/节点数据。然后使用排序实例进行排序。这提供了一个排序

13、基准，其可伸缩性取决于集群的大小。默认情况下，排序实例使用1.0 *容量作为缩减数量，根据您的群集大小，1.75 *容量的缩减可能会更好。(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实例Rando

14、mWriter得到了两个文件，我们在这里使用了一个文件部分-00000。如果要对两个文件进行排序，输入路径只需是一个目录。排序算法源代码a)源代码位置/local/zkl/Hadoop/Hadoop-0 . 20 . 1/Hadoop-0 . 20 . 1/src/examples/org/Apache/Hadoop/examples/Sort . Java以下程序是排序算法的源代码：26.* torun : bin/Hadoop jar build/Hadoop-示例. jarsort27.*-mmap-r减少28.*-InformationInputFormatClass29.*-outFormatoutputformatclass30.*-outKeyoutputkeyclass31.*-outValueoutputvalueclass32.*-TotalOrderPcntNumSampleSmaxsplits