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

问题导读：
Secondsort的工作原理是什么？
如何实现Secondsort算法？
Terasort算法的流程是什么？
Terasort算法的关键点是什么？

一、前言... 4

二、Hadoop及Mapreduce的相关介绍... 4

三、大规模数据排序... 8

四、算法分析... 10

1.Sort算法分析... 10

2.Secondsort算法分析... 12

3. Terasort算法分析... 15

五、小组成员个人总结.

一、前言

     我们小组主要对基于[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架构

图表 1 hadoop架构

Hadoop 有许多元素构成。其最底部是HDFS，它存储 Hadoop 集群中所有存储节点上的文件。HDFS的上一层是 MapReduce 引擎，该引擎由 JobTrackers 和 TaskTrackers 组成。

（1）分布式计算模型

一个hadoop集群往往有几十台甚至成百上千台low cost的计算机组成，我们运行的每一个任务都要在这些计算机上做任务的分发，执行中间数据排序以及最后的汇总，期间还包含节点发现，任务的重试，故障节点替换等等等等的维护以及异常情况处理。

所以说hadoop就是一个计算模型。一个分布式的计算模型。

1. Mapreduce

（1）mapreduce 和hadoop起源

MapReduce借用了函数式编程的概念，是Google发明的一种数据处理模型。因为Google几乎爬了互联网上的所有网页，要为处理这些网页并为搜索引擎建立索引是一项非常艰巨的任务，必须借助成千上万台机器同时工作（也就是分布式并行处理），才有可能完成建立索引的任务。

所以，Google发明了MapReduce数据处理模型，而且他们还就此发表了相关论文。

后来，Doug Cutting老大就根据这篇论文硬生生的复制了一个MapReduce出来，也就是今天的Hadoop。

（2）mapreduce工作流程

MapReduce处理数据过程主要分成2个阶段：map阶段和reduce阶段。先执行map阶段，再执行reduce阶段。

①      在正式执行map函数前，需要对输入进行“分片”（就是将海量数据分成大概相等的“块”，hadoop的一个分片默认是64M），以便于多个map同时工作，每一个map任务处理一个“分片”。

②      分片完毕后，多台机器就可以同时进行map工作了。

map函数要做的事情，相当于对数据进行“预处理”，输出所要的“关切”。

map对每条记录的输出以<key,value> pair的形式输出。

③      在进入reduce阶段之前，要将各个map中相关的数据（key相同的数据）归结到一起，发往一个reducer。这里面就涉及到多个map的输出“混合地”对应多个reducer的情况，这个过程叫做“洗牌”。

④      接下来进入reduce阶段。相同的key的map输出会到达同一个reducer。reducer对key相同的多个value进行“reduce操作”，最后一个key的一串value经过reduce函数的作用后，变成了一个value。

图表 2   mapreduce简单工作流程

（1）运行环境

• Hadoop Streaming是一种运行作业的实用工具，它允许用户创建和运行任何可执行程序     （例如：Shell工具）来做为mapper和reducer。
• Hadoop Pipes是一个与SWIG兼容的C++ API （没有基于JNITM技术），它也可用于实现Map/Reduce应用程序。
  

（2）输入与输出

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)

（3）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进行排序来作为例子：

如何将数据发给一个指定ID的reduce？hadoop提供了多种分区算法。这些算法根据map输出的数据的key来确定此数据应该发给哪个reduce（reduce的排序也依赖key）。因此，如果需要将数据发给某个reduce，只要在输出数据的同时，提供一个 key（在上面这个例子中就是reduce的ID+url），数据就该去哪儿去哪儿了。

1.        Nutch

Nutch是一个由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/hadoop jar hadoop-*-examples.jar sort [-m <#maps>][-r <#reduces>] <in-dir> <out-dir>

（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.java
b) 下面程序是一段关于Sort算法的源代码：

 * To run: bin/hadoop jar build/hadoop-examples.jar sort 
 *            [-m <i>maps</i>] [-r <i>reduces</i>] 
 *            [-inFormat <i>input format class</i>]  
*            [-outFormat <i>output format class</i>]  
*            [-outKey <i>output key class</i>]  
*            [-outValue <i>output value class</i>]  
*            [-totalOrder <i>pcnt</i> <i>num samples</i> <i>max splits</i>] 
*            <i>in-dir</i> <i>out-dir</i>  
 */  
 public class Sort<K,V> extends Configured implements Tool {  
private RunningJob jobResult = null;  


//input attr:/home/hadoop/rand/part-00000 /home/hadoop/rand-sort   

  public static void main(String[] args) throws Exception {  
     int res = ToolRunner.run(new Configuration(), new Sort(), args);  
System.exit(res);  
}  

/** 
    * Get the last job that was run using this instance. 
* @return the results of the last job that was run 
*/  
public RunningJob getResult() {  
return jobResult;  
}  
}
复制代码

2.Secondsort算法分析


（1）工作原理

在map阶段，使用job.setInputFormatClass定义的InputFormat将输入的数据集分割成小数据块splites，同时InputFormat提供一个RecordReder的实现。本例子中使用的是TextInputFormat，他提供的RecordReder会将文本的一行的行号作为key，这一行的文本作为value。这就是自定义Map的输入是<LongWritable,Text>的原因。然后调用自定义Map的map方法，将一个个<LongWritable, Text>对输入给Map的map方法。注意输出应该符合自定义Map中定义的输出<IntPair, IntWritable>。最终是生成一个List<IntPair,IntWritable>。在map阶段的最后，会先调用job.setPartitionerClass对这个List进行分区，每个分区映射到一个reducer。每个分区内又调用job.setSortComparatorClass设置的key比较函数类排序。可以看到，这本身就是一个二次排序。如果没有通过job.setSortComparatorClass设置key比较函数类，则使用key的实现的compareTo方法。在第一个例子中，使用了IntPair实现的compareTo方法，而在下一个例子中，专门定义了key比较函数类。

在reduce阶段，reducer接收到所有映射到这个reducer的map输出后，也是会调用job.setSortComparatorClass设置的key比较函数类对所有数据对排序。然后开始构造一个key对应的value迭代器。这时就要用到分组，使用jobjob.setGroupingComparatorClass设置的分组函数类。只要这个比较器比较的两个key相同，他们就属于同一个组，它们的value放在一个value迭代器，而这个迭代器的key使用属于同一个组的所有key的第一个key。最后就是进入Reducer的reduce方法，reduce方法的输入是所有的（key和它的value迭代器）。同样注意输入与输出的类型必须与自定义的Reducer中声明的一致。

二次排序就是首先按照第一字段排序，然后再对第一字段相同的行按照第二字段排序，注意不能破坏第一次排序的结果 。

（2）具体步骤

●自定义key。

在mr中，所有的key是需要被比较和排序的，并且是二次，先根据partitione，再根据大小。而本例中也是要比较两次。先按照第一字段排序，然后再对第一字段相同的按照第二字段排序。根据这一点，我们可以构造一个复合类IntPair，他有两个字段，先利用分区对第一字段排序，再利用分区内的比较对第二字段排序。

●由于key是自定义的，所以还需要自定义一下类：  分区函数类；key比较函数类；分组函数类。

（3）SecondarySort.java的部分代码

a)     源码位置

/local/zkl/hadoop/hadoop-0.20.1/hadoop-0.20.1/src/examples/org/apache/hadoop/examples/SecondarySort.java

b)  下面程序是一段关于secondarySort的源代码：

public class SecondarySort {
          //自己定义的key类应该实现WritableComparable接口
          public static class IntPair 
                              implements WritableComparable<IntPair> {
            private int first = 0;
            private int second = 0;
            
            /**
             * Set the left and right values.
             */
            public void set(int left, int right) {
              first = left;
              second = right;
            }
            public int getFirst() {
              return first;
            }
            public int getSecond() {
              return second;
            }
            /
        @Override
        //反序列化，从流中的二进制转换成IntPair
            public void readFields(DataInput in) throws IOException {
              first = in.readInt() + Integer.MIN_VALUE;
              second = in.readInt() + Integer.MIN_VALUE;
            }
        @Override
         //序列化，将IntPair转化成使用流传送的二进制
            public void write(DataOutput out) throws IOException {
              out.writeInt(first - Integer.MIN_VALUE);
              out.writeInt(second - Integer.MIN_VALUE);
        }
        //新定义类应该重写的两个方法
        @Override
        //The hashCode() method is used by the HashPartitioner (the default partitioner in MapReduce)
复制代码

//主函数
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
// 读取hadoop配置
Configuration conf = new Configuration();
String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
if (otherArgs.length != 2) {
System.err.println("Usage: secondarysrot <in> <out>");
System.exit(2);
}
// 实例化一道作业
Job job = new Job(conf, "secondary sort");
job.setJarByClass(SecondarySort.class);
// Mapper类型
job.setMapperClass(MapClass.class);
// Reducer类型
job.setReducerClass(Reduce.class);
// 分区函数
job.setPartitionerClass(FirstPartitioner.class);
// 分组函数
job.setGroupingComparatorClass(FirstGroupingComparator.class);
// map 输出Key的类型
job.setMapOutputKeyClass(IntPair.class);
// map输出Value的类型
job.setMapOutputValueClass(IntWritable.class);
// rduce输出Key的类型 
job.setOutputKeyClass(Text.class);
// rduce输出Value的类型
job.setOutputValueClass(IntWritable.class);
// 输入hdfs路径
FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
// 输出hdfs路径
FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
// 提交job
System.exit(job.waitForCompletion(true) ? 0 : 1);
}

}
复制代码

3.Terasort算法分析

（1）概述

    1TB排序通常用于衡量分布式数据处理框架的数据处理能力。Terasort是Hadoop中的的一个排序作业，在2008年，Hadoop在1TB排序基准评估中赢得第一名，耗时209秒。那么Terasort在Hadoop中是怎样实现的呢？本文主要从算法设计角度分析Terasort作业。

（2）算法思想

    实际上，当我们要把传统的串行排序算法设计成并行的排序算法时，通常会想到分而治之的策略，即：把要排序的数据划成M个数据块（可以用Hash的方法做到），然后每个map task对一个数据块进行局部排序，之后，一个reduce task对所有数据进行全排序。这种设计思路可以保证在map阶段并行度很高，但在reduce阶段完全没有并行。

图表 4  terasort算法简介图




为了提高reduce阶段的并行度，TeraSort作业对以上算法进行改进：在map阶段，每个map task都会将数据划分成R个数据块（R为reduce task个数），其中第i（i>0）个数据块的所有数据都会比第i+1个中的数据大；在reduce阶段，第i个reduce task处理（进行排序）所有map task的第i块，这样第i个reduce task产生的结果均会比第i+1个大，最后将1~R个reduce task的排序结果顺序输出，即为最终的排序结果。




这种设计思路很明显比第一种要高效，但实现难度较大，它需要解决以下两个技术难点：第一，如何确定每个map task数据的R个数据块的范围？ 第二，对于某条数据，如果快速的确定它属于哪个数据块？答案分别为【采样】和【trie树】。

图表 6  trie树

（3）Terasort算法

①Terasort算法流程

    对于Hadoop的Terasort排序算法，主要由3步组成：采样 –>> map task对于数据记录做标记 –>> reduce task进行局部排序。

数据采样在JobClient端进行，首先从输入数据中抽取一部分数据，将这些数据进行排序，然后将它们划分成R个数据块，找出每个数据块的数据上限和下线（称为“分割点”），并将这些分割点保存到分布式缓存中。

在map阶段，每个map task首先从分布式缓存中读取分割点，并对这些分割点建立trie树（两层trie树，树的叶子节点上保存有该节点对应的reduce task编号）。然后正式开始处理数据，对于每条数据，在trie树中查找它属于的reduce task的编号，并保存起来。

在reduce阶段，每个reduce task从每个map task中读取其对应的数据进行局部排序，最后将reduce task处理后结果按reduce task编号依次输出即可。

② 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 = 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，mnk

b)map task对数据记录做标记

每个map task从文件_partition.lst读取分割点，并创建trie树（假设是2-trie，即组织利用前两个字节）。

Map task从split中一条一条读取数据，并通过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/terasort

f)        下面程序是一段关于树节点的源代码：

  * A leaf trie node that does string compares to figure out where the given
             * key belongs between lower..upper.
             */
            static class LeafTrieNode extends TrieNode {
              int lower;
              int upper;
              Text[] splitPoints;
              LeafTrieNode(int level, Text[] splitPoints, int lower, int upper) {
                super(level);
                this.splitPoints = splitPoints;
                this.lower = lower;
                this.upper = upper;
              }
              int findPartition(Text key) {
                for(int i=lower; i<upper; ++i) {
                  if (splitPoints[i].compareTo(key) >= 0) {
                    return i;
                  }
                }
                return upper;
              }
              void print(PrintStream strm) throws IOException {
                for(int i = 0; i < 2*getLevel(); ++i) {
                  strm.print(' ');
                }
                strm.print(lower);
                strm.print(", ");
                strm.println(upper);
              }
            }
复制代码

小组成员个人总结

1. 1091000161 韩旭红

对于网络工程的项目，我们组的题目是：基于hadoop的大规模数据排序算法和海量数据的生成。在徐远超老师的带领下，短短几周的时间里，我学到了很多。从刚开始对云计算仅仅只是听过而已，到后来把关于hadoop的一些代码研究清楚，这个过程虽然很艰辛，中间也遇到了很多困难，但是却让我们感觉很充实,收获了很多，我们真真切切感受到了动手实践的乐趣。

首先接触hadoop时，我感到懵懵懂懂，从网上查了一些资料，翻看了一些相关书籍，慢慢了解了hadoop，了解了这个无处不在，充满诱惑的领域。然后在老师的带领下，我们开始安装hadoop操作平台，虽然这个过程并不顺利，但是经过一些探索，经过老师和同学的帮助之后我们终于成功配置好了hadoop的运行环境。当我们编写的程序在linux系统的eclipse上第一次运行成功时，我们欢呼雀跃，感到非常的兴奋！第三阶段，我们对mapreduce进行了研究，了解了map task 和reduce task的工作原理，mapreduce作为hadoop的一个很重要的算法，在很多方面都用到了，基于hadoop的大规模数据排序算法是从mapreduce进行改进实现的。第四阶段，我们小组对大规模数据排序算法搜索了很多的资料并研读，此外我还研究了nutch的内容，对nutch的网页排序做了一定的了解。然后我们对三个主要算法进行了研究，包括sort.java;secondarysort.java;terasort.java。我主要负责对terasort的研读。从中我了解了terasort的工作原理，对采样和做标记以及trie树的生成都有了深入的了解。虽然我们小组成员都是学C++的，但是我们在这方面下了很多时间和精力，对代码的研读也很细致，不懂不会的从网上查，问学习java的同学，最终拿下了这个难关。第五阶段我们对大规模排序算法在hadoop环境下运行，因为所需内存很大，所以我们对代码进行了相应的修改，在单机上运行程序。

作为这个项目的组长，我要带领大家有绪的进行工作，要统筹安排，更要认真负责，在这个过程中，我收获了很多，锻炼了很多。其实非常感谢徐老师，老师经常教导我们，要学会自学的本领，遇到不懂的问题就自己查。让我们更加自立，更加懂得了独立的思考，和同学们探讨，自己摸索发现。老师谨着认真负责的态度，对我们严格督促，从来不放松，每周都检查我们的工作进度。对我们的成果给予鼓励，对我们的不足提出建设性意见。在我们迷茫不知道怎么做的时候都会给予指导，让我们找到前进的方向。虽然我的工作做得不是那么尽善尽美，但是我们真的在这次的项目中很用心的做了，也很用心的完成了，不仅收获了课本中学不到的知识，还学会了做一个项目要注意的事项，以及怎样学习，怎样探索。我们将带着这次的收获冲向下一个难关，完成更多的工作和任务！

2.1091000167 李巍

在这2011——2012年秋季这学期中，学习了《网络工程》这一门课程。在该课程的课外实践中选择了项目——基于hadoop海量数据的大规模排序算法——进行了研究。在进行该项目的过程中，遇到了一系列的问题，最后都逐一解决，收获颇丰。

首先，进行该项目需要基于linux系统，根据所选题目需要，我们对linux系统的安装的版本进行了选择，最后使用了Ubuntu 10.10版本（装在虚拟机中）。在安装该系统及hadoop平台的过程中，出现了很多问题。其中最主要的是Ubuntu安装中，由于网络原因，总是无法连接网络连接，最后只能接入宽带进行安装。

其次，在linux系统中需要安装Hadoop平台。由于Hadoop是在linux系统中安装的，我们对该系统的命令和使用不太熟悉，请教沈岩，绍严飞，万虎同学帮忙安装。我安装的版本是hadoop-0.20.2。首先安装的javac,然后安装hadoop，最后安装ssh（由于hadoop文件中有ssh,不能直接安装，需要重新下载安装）。联网后，hadoop 和 mapreduce都能正常使用，并在命令行中运行代码成功。

最后，分析代码并运行。我没学过Java语言，从图书馆里借看了本关于java的书，然后开始分析文件中自带的编码。通过上网查询，看书查询，读懂了sort.java 和 secondarysort.java代码的含义，并进一步对terasort.java进行研究。之后，在Hadoop平台上，通过修改部分代码，使其成功运行。

在本项目中，我弄懂了mapreduce的工作原理，以及mapreduce 的适用范围，对于这种海量数据排序来说，mapreduce 无疑是最优的解决方法。

总之，在该项目中，我学到了很多课外的知识，同时又锻炼了自己自学和自行解决问题的能力，为现在及以后的科研项目奠定了坚实的基础。

3. 1091000169 李越

  我们组选择的课题是基于hadoop的大规模数据排序算法。在从开学现在这两个多月里，我们从最开始的不了解，然后一知半解，到最后把这个整个课题做完。我们先对hadoop 和 map reduce 进行了了解。之后安装了虚拟机，Linux，并分析了源代码。我们一个组共同努力，不同分工，在网上查阅了资料，整理资料。在这其中，我负责查阅了map reduce的部分。

    Hadoop是一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。

    MapReduce是一种编程模型，用于大规模数据集的并行运算。概念"Map（映射）"和"Reduce（化简）"，和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。他极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

    通过这次的学习，让我们清楚的了解了hadoop以及相关的算法，同时对LINUX的环境也有了一定的了解。每周的小组开会， 也让我们对其他组的课题，以及同课题的其他同学对所做的课题有了更多的了解，我们学得了更多得到知识，受益匪浅。

4. 1091000178 闫悦

历时十二周的网络工程即将结束，我们组的课题是基于hadoop的大规模数据排序算法。

这将近一学期的学习中，在徐老师的课程中，我们分组进行了基于hadooop的大规模数据排序算法的研究。

我在组中主要负责大规模数据排序的研究。通过这几周的小组学习，我对hadoop的大规模排序有了一定的了解。以下是我学到的内容：

如果云计算是一个系统工程的蓝图，而hadoop就好比是做该工程中某些部件的一个工具，云计算包括很多东西，涉及到方方面面，hadoop专长于数据处理，用这个框架能够使云计算更简便。

Hadoop平台没有提供全局数据排序，而在大规模数据处理中进行数据的全局排序是非常普遍的需求，以及应用hadoop进行大规模数据全局排序的方法。

MapReduce是一种编程模型，用于大规模数据集的并行运算。同时了解了MapReduce的工作流程、运行环境等。

除此之外，我看了terasort与secondstor的源代码，但是由于我学习的是C++，对于基于java的源代码还是不太理解，对于这些算法都认真阅读了，但主要负责大规模数据排序原理方面。

经过这多个星期的项目学习，除了小组上学习外也有很大收获，尤其平时接触不多的云计算方面的内容有了更多的了解，这个小组项目也为我提供了更多的实践基础。虽然历时几个星期，最后成果不甚显著，但是这个项目对我专业学习及实践提供了很大帮助。

5.1091000163 焦天禹

通过学习了解和上网查资料学习关于海量数据和海量数据的管理，让我对海量数据有了一个初步的了解，并让我知道了不少较为专业的知识比如

Bloom Filter

Hash

Bit-Map

堆(Heap)

双层桶划分

数据库索引

倒排索引（Inverted Index）

外排序

Trie树

MapReduce

的概念，和处理的基本手段方法，再比如百度的TopK热门查询问题，某日IP最多访问问题，让我对网络工程有了一个更全面，更为系统的学习和了解。

什么是Bloom Filter，这样的问题也有了较为通俗地了解，包括它的基本要点和原理，适用的范围，Bloom Filter的缺陷不足都有了明了的了解，之后的学习，也让我对其扩张，和实例有了更深更明确掌握，有一种打开了一扇大门的感觉。

之后是对海量数据的管理方面的了解和认识，让我对海量数据的管理的原则有了明确地认识，也从

架构设计上

高频表的存储与优化

编写优良的程序代码

对海量数据进行分区操作

建立广泛的索引

建立缓存机制

分批处理

使用临时表和中间表

优化查询SQL语句

定制强大的清洗规则和出错处理机制

建立视图或者物化视图

使用数据仓库和多维数据库存储

这些方面，有了较为明确的认识认知。对海量数据，和海量数据的管理学习，对我收获很大，让我了解到自我学习的方式方法，这次的学习，关于海量数据和海量数据的管理，让我不仅获得了专业方面的知识，也对我自主学习有很大的提升。