基于Hadoop的大规模数据排序算法

1、信息工程学院 网络工程基于hadoop的大规模数据排序算法 基于hadoop的大规模数据排序算法 网络工程终期报告 基于hadoop的大规模数据排序小组成员：组长：韩旭红 1091000161组员：李巍 1091000167组员：李越 1091000169组员：闫悦 1091000178组员：焦天禹 1091000163目录一、前言4二、hadoop及mapreduce的相关介绍41.hadoop4（1）hadoop简介4（2）hadoop架构5（3）分布式计算模型52.mapreduce5（1）map reduce 和hadoop起源5（2）mapreduce工作流程6（3）运行环境7（4）

2、输入与输出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六、小组成员个人总结201.1091000161 韩旭红202.1091000167 李巍213.1091000169 李越214.1091000178 闫悦2

3、15.1091000163 焦天禹22一、 前言 我们小组主要对基于hadoop的大规模数据排序算法、海量数据的生成做了一定的研究。我们首先对于hadoop做了初步了解，其次，mapreduce是hadoop的很重要的算法，我们在第二阶段对mapreduce以及一些代码做了分析。第三阶段，我们安装虚拟机和linux以及hadoop的软件，配置运行环境。第四阶段，我们对大规模数据排序进行深入的研究，对nutch进行了简单的了解。第五阶段，对一些源代码进行分析，主要是排序算法中的sort.java,secondsort.java,terasort。下面的正文中将作出具体的介绍。二、 hadoop及

4、mapreduce的相关介绍1. hadoop（1） hadoop简介 hadoop是一个分布式系统基础架构，由apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。hadoop实现了一个分布式文件系统，简称hdfs。hdfs有着高容错性的特点，并且设计用来部署在低廉的硬件上。而且它提供高传输率来访问应用程序的数据，适合那些有着超大数据集的应用程序。（2） hadoop架构图表 1 hadoop架构hadoop 有许多元素构成。其最底部是hdfs，它存储 hadoop 集群中所有存储节点上的文件。hdfs的上一层是 mapreduce

5、 引擎，该引擎由 jobtrackers 和 tasktrackers 组成。（3） 分布式计算模型一个hadoop集群往往有几十台甚至成百上千台low cost的计算机组成，我们运行的每一个任务都要在这些计算机上做任务的分发，执行中间数据排序以及最后的汇总，期间还包含节点发现，任务的重试，故障节点替换等等等等的维护以及异常情况处理。所以说hadoop就是一个计算模型。一个分布式的计算模型。2. mapreduce（1） map reduce 和hadoop起源mapreduce借用了函数式编程的概念，是google发明的一种数据处理模型。因为google几乎爬了互联网上的所有网页，要为处理这

6、些网页并为搜索引擎建立索引是一项非常艰巨的任务，必须借助成千上万台机器同时工作（也就是分布式并行处理），才有可能完成建立索引的任务。所以，google发明了mapreduce数据处理模型，而且他们还就此发表了相关论文。 后来，doug cutting老大就根据这篇论文硬生生的复制了一个mapreduce出来，也就是今天的hadoop。（2） mapreduce工作流程mapreduce处理数据过程主要分成2个阶段：map阶段和reduce阶段。先执行map阶段，再执行reduce阶段。 在正式执行map函数前，需要对输入进行“分片”（就是将海量数据分成大概相等的“块”，hadoop的一个分片默

7、认是64m），以便于多个map同时工作，每一个map任务处理一个“分片”。 分片完毕后，多台机器就可以同时进行map工作了。 map函数要做的事情，相当于对数据进行“预处理”，输出所要的“关切”。 map对每条记录的输出以 pair的形式输出。 在进入reduce阶段之前，要将各个map中相关的数据（key相同的数据）归结到一起，发往一个reducer。这里面就涉及到多个map的输出“混合地”对应多个reducer的情况，这个过程叫做“洗牌”。 接下来进入reduce阶段。相同的key的map输出会到达同一个reducer。reducer对key相同的多个value进行“reduce操作”，最

8、后一个key的一串value经过reduce函数的作用后，变成了一个value。图表 2 mapreduce简单工作流程（3） 运行环境 hadoop streaming是一种运行作业的实用工具，它允许用户创建和运行任何可执行程序 （例如：shell工具）来做为mapper和reducer。 hadoop pipes是一个与swig兼容的c+ api （没有基于jnitm技术），它也可用于实现map/reduce应用程序。（4） 输入与输出map/reduce框架运转在 键值对上，也就是说， 框架把作业的输入看为是一组 键值对，同样也产出一组 键值对做为作业的输出，这两组键值对的类型可能不同。

9、框架需要对key和value的类(class)进行序列化操作， 因此，这些类需要实现 writable接口。 另外，为了方便框架执行排序操作，key类必须实现 writablecomparable接口。 一个map/reduce 作业的输入和输出类型如下所示：(input) - map - - combine - - reduce - (output) （5） map/reduce - 用户界面这部分文档为用户将会面临的map/reduce框架中的各个环节提供了适当的细节。这应该会帮助用户更细粒度地去实现、配置和调优作业。然而，需要注意每个类/接口的javadoc文档提供最全面的文档。 我们会

10、先看看mapper和reducer接口。应用程序通常会通过提供map和reduce方法来实现它们。 然后，我们会讨论其他的核心接口，其中包括： jobconf，jobclient，partitioner， outputcollector，reporter， inputformat，outputformat等等。最后，我们将通过讨论框架中一些有用的功能点（例如：distributedcache， isolationrunner等等）来收尾。三、 大规模数据排序1. 简介使用hadoop进行大量的数据排序排序最直观的方法是把文件所有内容给map之后，map不做任何处理，直接输出给一个reduce，

11、利用hadoop的自己的shuffle机制，对所有数据进行排序，而后由reduce直接输出。然而这样的方法跟单机毫无差别，完全无法用到多机分布式计算的便利。因此这种方法是不行的。利用hadoop分而治之的计算模型，可以参照快速排序的思想。在这里我们先简单回忆一下快速排序。快速排序基本步骤就是需要现在所有数据中选取一个作为支点。然后将大于这个支点的放在一边，小于这个支点的放在另一边。设想如果我们有n个支点（这里可以称为标尺），就可以把所有的数据分成n+1个part，将这n+1个part丢给reduce，由hadoop自动排序，最后输出n+1个内部有序的文件，再把这n+1个文件首尾相连合并成一个文

12、件，收工。由此我们可以归纳出这样一个用hadoop对大量数据排序的步骤：对待排序数据进行抽样；对抽样数据进行排序，产生标尺；map对输入的每条数据计算其处于哪两个标尺之间；将数据发给对应区间id的reduce reduce将获得数据直接输出。这里使用对一组url进行排序来作为例子：图表 3 url排序如何将数据发给一个指定id的reduce？hadoop提供了多种分区算法。这些算法根据map输出的数据的key来确定此数据应该发给哪个reduce（reduce的排序也依赖key）。因此，如果需要将数据发给某个reduce，只要在输出数据的同时，提供一个 key（在上面这个例子中就是reduce的

13、id+url），数据就该去哪儿去哪儿了。2. nutchnutch是一个由java实现的，刚刚诞生开放源代码(open-source)的web搜索引擎。nutch主要分为爬虫crawler和查询searcher两部分。crawler主要用于从网络上抓取网页并为这些网页建立索引。searcher主要利用这些索引检索用户的查找关键词来产生查找结果。两者之间的接口是索引，所以除去索引部分，两者之间的耦合度很低。crawler的重点在两个方面，crawler的工作流程和涉及的数据文件的格式和含义。crawler的工作原理：首先crawler根据webdb生成一个待抓取网页的url集合叫做fetchli

14、st，接着下载线程fetcher根据fetchlist将网页抓取回来，如果下载线程有很多个，那么就生成很多个fetchlist，也就是一个fetcher对应一个fetchlist。然后crawler用抓取回来的网页更新webdb，根据更新后的webdb生成新的fetchlist，里面是未抓取的或者新发现的urls，然后下一轮抓取循环重新开始。四、 算法分析1. sort算法分析（1） 排序实例 排序实例仅仅用 map/reduce框架来把输入目录排序放到输出目录。输入和输出必须是顺序文件，键和值是byteswritable. mapper是预先定义的identitymapper，reducer

15、 是预先定义的 identityreducer， 两个都是把输入直接的输出。要运行这个例 子：bin/hadoop jar hadoop-*-examples.jar sort -m -r （2） 运行排序基准测试 为了使得排序例子作为一个 基准测试，用 randomwriter产 生10gb/node 的数据。然后用排序实例来进行排序。这个提供了一个可扩展性依赖于集群的大小的排序基准。默认情况下，排序实例用1.0*capacity作为 reduces的数量，依赖于你的集群的大小你可能会在1.75*capacity的情况下得到更好的结果。（3） 代码分析在eclipse中设置参数：/home/

16、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) 源码位置 /loc

17、al/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-rreduces28. *-informatinputformatclass29. *-outformatoutputformatclass30. *-outkeyoutputkeyclass31. *-outvalueoutputvalue

18、class32. *-totalorderpcntnumsamplesmaxsplits33. *in-dirout-dir34. */35. publicclasssortextendsconfiguredimplementstool36. privaterunningjobjobresult=null;37. 166. /inputattr:/home/hadoop/rand/part-00000/home/hadoop/rand-sort 167. 168. publicstaticvoidmain(stringargs)throwsexception169. intres=toolru

19、nner.run(newconfiguration(),newsort(),args);170. system.exit(res);171. 172. 173. /*174. *getthelastjobthatwasrunusingthisinstance.175. *returntheresultsofthelastjobthatwasrun176. */177. publicrunningjobgetresult()178. returnjobresult;179. 180. 2. secondsort算法分析（1） 工作原理在map阶段，使用job.setinputformatclas

20、s定义的inputformat将输入的数据集分割成小数据块splites，同时inputformat提供一个recordreder的实现。本例子中使用的是textinputformat，他提供的recordreder会将文本的一行的行号作为key，这一行的文本作为value。这就是自定义map的输入是的原因。然后调用自定义map的map方法，将一个个对输入给map的map方法。注意输出应该符合自定义map中定义的输出。最终是生成一个list。在map阶段的最后，会先调用job.setpartitionerclass对这个list进行分区，每个分区映射到一个reducer。每个分区内又调用job

21、.setsortcomparatorclass设置的key比较函数类排序。可以看到，这本身就是一个二次排序。如果没有通过job.setsortcomparatorclass设置key比较函数类，则使用key的实现的compareto方法。在第一个例子中，使用了intpair实现的compareto方法，而在下一个例子中，专门定义了key比较函数类。 在reduce阶段，reducer接收到所有映射到这个reducer的map输出后，也是会调用job.setsortcomparatorclass设置的key比较函数类对所有数据对排序。然后开始构造一个key对应的value迭代器。这时就要用到分组

22、，使用jobjob.setgroupingcomparatorclass设置的分组函数类。只要这个比较器比较的两个key相同，他们就属于同一个组，它们的value放在一个value迭代器，而这个迭代器的key使用属于同一个组的所有key的第一个key。最后就是进入reducer的reduce方法，reduce方法的输入是所有的（key和它的value迭代器）。同样注意输入与输出的类型必须与自定义的reducer中声明的一致。 二次排序就是首先按照第一字段排序，然后再对第一字段相同的行按照第二字段排序，注意不能破坏第一次排序的结果 。（2） 具体步骤自定义key。 在mr中，所有的key是需要被

23、比较和排序的，并且是二次，先根据partitione，再根据大小。而本例中也是要比较两次。先按照第一字段排序，然后再对第一字段相同的按照第二字段排序。根据这一点，我们可以构造一个复合类intpair，他有两个字段，先利用分区对第一字段排序，再利用分区内的比较对第二字段排序。由于key是自定义的，所以还需要自定义一下类： 分区函数类；key比较函数类；分组函数类。（3） secondarysort.java的部分代码c) 源码位置 /local/zkl/hadoop/hadoop-0.20.1/hadoop-0.20.1/src/examples/org/apache/hadoop/exampl

24、es/secondarysort.javad) 下面程序是一段关于secondarysort的源代码：33. public class secondarysort 34. /自己定义的key类应该实现writablecomparable接口35. public static class intpair 36. implements writablecomparable 37. private int first = 0;38. private int second = 0;39. 40. /*41. * set the left and right values.42. */43. publi

25、c void set(int left, int right) 44. first = left;45. second = right;46. 47. public int getfirst() 48. return first;49. 50. public int getsecond() 51. return second;52. 53. /54. override55. /反序列化，从流中的二进制转换成intpair56. public void readfields(datainput in) throws ioexception 57. first = in.readint() + i

26、nteger.min_value;58. second = in.readint() + integer.min_value;59. 60. override61. /序列化，将intpair转化成使用流传送的二进制62. public void write(dataoutput out) throws ioexception 63. out.writeint(first - integer.min_value);64. out.writeint(second - integer.min_value);65. 66. /新定义类应该重写的两个方法67. override68. /thehash

27、code()methodisusedbythehashpartitioner(thedefaultpartitionerinmapreduce)185. /主函数186. public static void main(string args) throws exception 187. /todoauto-generatedmethodstub188. /读取hadoop配置189. configuration conf = new configuration();190. string otherargs = new genericoptionsparser(conf, args).get

28、remainingargs();191. if (otherargs.length != 2) 192. system.err.println(usage: secondarysrot );193. system.exit(2);194. 195. /实例化一道作业196. job job = new job(conf, secondary sort);197. job.setjarbyclass(secondarysort.class);198. /mapper类型199. job.setmapperclass(mapclass.class);200. /reducer类型201. job.

29、setreducerclass(reduce.class);202. /分区函数203. job.setpartitionerclass(firstpartitioner.class);204. /分组函数205. job.setgroupingcomparatorclass(firstgroupingcomparator.class);206. /map输出key的类型207. job.setmapoutputkeyclass(intpair.class);208. /map输出value的类型209. job.setmapoutputvalueclass(intwritable.class

30、);210. /rduce输出key的类型 211. job.setoutputkeyclass(text.class);212. /rduce输出value的类型213. job.setoutputvalueclass(intwritable.class);214. /输入hdfs路径215. fileinputformat.addinputpath(job, new path(otherargs0);216. /输出hdfs路径217. fileoutputformat.setoutputpath(job, new path(otherargs1);218. /提交job219. syst

31、em.exit(job.waitforcompletion(true) ? 0 : 1);220. 221.222. 3. terasort算法分析（1） 概述 1tb排序通常用于衡量分布式数据处理框架的数据处理能力。terasort是hadoop中的的一个排序作业，在2008年，hadoop在1tb排序基准评估中赢得第一名，耗时209秒。那么terasort在hadoop中是怎样实现的呢？本文主要从算法设计角度分析terasort作业。（2） 算法思想 实际上，当我们要把传统的串行排序算法设计成并行的排序算法时，通常会想到分而治之的策略，即：把要排序的数据划成m个数据块（可以用hash的方法

32、做到），然后每个map task对一个数据块进行局部排序，之后，一个reduce task对所有数据进行全排序。这种设计思路可以保证在map阶段并行度很高，但在reduce阶段完全没有并行。图表 4 terasort算法简介图为了提高reduce阶段的并行度，terasort作业对以上算法进行改进：在map阶段，每个map task都会将数据划分成r个数据块（r为reduce task个数），其中第i（i0）个数据块的所有数据都会比第i+1个中的数据大；在reduce阶段，第i个reduce task处理（进行排序）所有map task的第i块，这样第i个reduce task产生的结果均会比

33、第i+1个大，最后将1r个reduce task的排序结果顺序输出，即为最终的排序结果。图表 5 terasort算法图 这种设计思路很明显比第一种要高效，但实现难度较大，它需要解决以下两个技术难点：第一，如何确定每个map task数据的r个数据块的范围？ 第二，对于某条数据，如果快速的确定它属于哪个数据块？答案分别为【采样】和【trie树】。图表 6 trie树（3） terasort算法 terasort算法流程 对于hadoop的terasort排序算法，主要由3步组成：采样 map task对于数据记录做标记 reduce task进行局部排序。数据采样在jobclient端进行，首

34、先从输入数据中抽取一部分数据，将这些数据进行排序，然后将它们划分成r个数据块，找出每个数据块的数据上限和下线（称为“分割点”），并将这些分割点保存到分布式缓存中。在map阶段，每个map task首先从分布式缓存中读取分割点，并对这些分割点建立trie树（两层trie树，树的叶子节点上保存有该节点对应的reduce task编号）。然后正式开始处理数据，对于每条数据，在trie树中查找它属于的reduce task的编号，并保存起来。在reduce阶段，每个reduce task从每个map task中读取其对应的数据进行局部排序，最后将reduce task处理后结果按reduce task

35、编号依次输出即可。 terasort算法关键点a) 采样hadoop自带了很多数据采样工具，包括intercalsmapler，randomsampler，splitsampler等（具体见org.apache.hadoop.mapred.lib）。采样数据条数：samplesize = conf.getlong(“terasort.partitions.sample”, 100000);选取的split个数：samples = math.min(10, splits.length); splits是所有split组成的数组。每个split提取的数据条数：recordspersample =

36、samplesize / samples;对采样的数据进行全排序，将获取的“分割点”写到文件_partition.lst中，并将它存放到分布式缓存区中。举例说明：比如采样数据为b，abc，abd，bcd，abcd，efg，hii，afd，rrr，mnk经排序后，得到：abc，abcd，abd，afd，b，bcd，efg，hii，mnk，rrr如果reduce task个数为4，则分割点为：abd，bcd，mnkb) map task对数据记录做标记每个map task从文件_partition.lst读取分割点，并创建trie树（假设是2-trie，即组织利用前两个字节）。map task从s

37、plit中一条一条读取数据，并通过trie树查找每条记录所对应的reduce task编号。比如：abg对应第二个reduce task， mnz对应第四个reduce task。图表 7 数据采样和作标记图解c) reduce task进行局部排序每个reduce task进行局部排序，依次输出结果即可。 terasort源代码e) 源码位置 /local/zkl/hadoop/hadoop-0.20.1/hadoop-0.20.1/src/examples/org/apache/hadoop/examples/terasortf) 下面程序是一段关于树节点的源代码：111. * a lea

38、f trie node that does string compares to figure out where the given112. * key belongs between lower.upper.113. */114. static class leaftrienode extends trienode 115. int lower;116. int upper;117. text splitpoints;118. leaftrienode(int level, text splitpoints, int lower, int upper) 119. super(level);

39、120. this.splitpoints = splitpoints;121. this.lower = lower;122. this.upper = upper;123. 124. int findpartition(text key) 125. for(int i=lower; i= 0) 127. return i;128. 129. 130. return upper;131. 132. void print(printstream strm) throws ioexception 133. for(int i = 0; i 2*getlevel(); +i) 134. strm.

40、print( );135. 136. strm.print(lower);137. strm.print(, );138. strm.println(upper);139. 140. 五、 参考资料(1) hadoop的1tb排序terasort： (2) hadoop-0.20.2代码: / (3) hadoop中terasort算法分析(4) 实战hadoop(5) hadoop权威指南(6) hadoop中terasort算法分析: /mapreduce/hadoop-terasort-analyse

41、/(7) hadoop简介：(8) 你不可不知的“云计算”(9) a practical guide to cloud computing(10) ubantu linux从入门到精通（版本9）(11) 基于hadoop的大规模数据排序算法：六、 小组成员个人总结1. 1091000161 韩旭红 对于网络工程的项目，我们组的题目是：基于hadoop的大规模数据排序算法和海量数据的生成。在徐远超老师的带领下，短短几周的时间里，我学到了很多。从刚开始对云计算仅仅只是听过而已，到后来把关于hadoop的一些代码研究清楚，这个过程虽然很艰辛，中间也遇到了很多困难，但是却让我们感觉很充实,收获了很多，

42、我们真真切切感受到了动手实践的乐趣。首先接触hadoop时，我感到懵懵懂懂，从网上查了一些资料，翻看了一些相关书籍，慢慢了解了hadoop，了解了这个无处不在，充满诱惑的领域。然后在老师的带领下，我们开始安装hadoop操作平台，虽然这个过程并不顺利，但是经过一些探索，经过老师和同学的帮助之后我们终于成功配置好了hadoop的运行环境。当我们编写的程序在linux系统的eclipse上第一次运行成功时，我们欢呼雀跃，感到非常的兴奋！第三阶段，我们对mapreduce进行了研究，了解了map task 和reduce task的工作原理，mapreduce作为hadoop的一个很重要的算法，在很

43、多方面都用到了，基于hadoop的大规模数据排序算法是从mapreduce进行改进实现的。第四阶段，我们小组对大规模数据排序算法搜索了很多的资料并研读，此外我还研究了nutch的内容，对nutch的网页排序做了一定的了解。然后我们对三个主要算法进行了研究，包括sort.java;secondarysort.java;terasort.java。我主要负责对terasort的研读。从中我了解了terasort的工作原理，对采样和做标记以及trie树的生成都有了深入的了解。虽然我们小组成员都是学c+的，但是我们在这方面下了很多时间和精力，对代码的研读也很细致，不懂不会的从网上查，问学习java的同

44、学，最终拿下了这个难关。第五阶段我们对大规模排序算法在hadoop环境下运行，因为所需内存很大，所以我们对代码进行了相应的修改，在单机上运行程序。作为这个项目的组长，我要带领大家有绪的进行工作，要统筹安排，更要认真负责，在这个过程中，我收获了很多，锻炼了很多。其实非常感谢徐老师，老师经常教导我们，要学会自学的本领，遇到不懂的问题就自己查。让我们更加自立，更加懂得了独立的思考，和同学们探讨，自己摸索发现。老师谨着认真负责的态度，对我们严格督促，从来不放松，每周都检查我们的工作进度。对我们的成果给予鼓励，对我们的不足提出建设性意见。在我们迷茫不知道怎么做的时候都会给予指导，让我们找到前进的方向。虽

45、然我的工作做得不是那么尽善尽美，但是我们真的在这次的项目中很用心的做了，也很用心的完成了，不仅收获了课本中学不到的知识，还学会了做一个项目要注意的事项，以及怎样学习，怎样探索。我们将带着这次的收获冲向下一个难关，完成更多的工作和任务！2. 1091000167 李巍在这20112012年秋季这学期中，学习了网络工程这一门课程。在该课程的课外实践中选择了项目基于hadoop海量数据的大规模排序算法进行了研究。在进行该项目的过程中，遇到了一系列的问题，最后都逐一解决，收获颇丰。首先，进行该项目需要基于linux系统，根据所选题目需要，我们对linux系统的安装的版本进行了选择，最后使用了ubunt

46、u 10.10版本（装在虚拟机中）。在安装该系统及hadoop平台的过程中，出现了很多问题。其中最主要的是ubuntu安装中，由于网络原因，总是无法连接网络连接，最后只能接入宽带进行安装。其次，在linux系统中需要安装hadoop平台。由于hadoop是在linux系统中安装的，我们对该系统的命令和使用不太熟悉，请教沈岩，绍严飞，万虎同学帮忙安装。我安装的版本是hadoop-0.20.2。首先安装的javac,然后安装hadoop，最后安装ssh（由于hadoop文件中有ssh,不能直接安装，需要重新下载安装）。联网后，hadoop 和 mapreduce都能正常使用，并在命令行中运行代码成

47、功。最后，分析代码并运行。我没学过java语言，从图书馆里借看了本关于java的书，然后开始分析文件中自带的编码。通过上网查询，看书查询，读懂了sort.java 和 secondarysort.java代码的含义，并进一步对terasort.java进行研究。之后，在hadoop平台上，通过修改部分代码，使其成功运行。在本项目中，我弄懂了mapreduce的工作原理，以及mapreduce 的适用范围，对于这种海量数据排序来说，mapreduce 无疑是最优的解决方法。总之，在该项目中，我学到了很多课外的知识，同时又锻炼了自己自学和自行解决问题的能力，为现在及以后的科研项目奠定了坚实的基础。3. 1091000169 李越 我们组选择的课题是基于hadoop的大规模数据排序算法。在从开学现在这两个多月里，我们从最开始的不了解，然后一知半解，到最后把这个整个课题做完。我们先对hadoop 和 map reduce 进行了了解。之后安装了虚拟机，linux，并分析了源代码。我们一个组共同努力，不同分工，在网上查阅了资料，整理资料。在这其中，我负责查阅了map reduce的部分。 hadoop是一个分布式系统基础架