您现在的位置 >> Hadoop教程 >> Hadoop实战 >> hadoop专题  
 

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

【作者:Hadoop实战专家】【关键词:云计算 海量数据 】 【点击:93805次】【2013-03-3】
三、大规模数据排序. 实际上,当我们要把传统的串行排序算法设计成并行的排序算法时,通常会想到分而治之的策略,即:把要排序的数据划成M个数据块(可以用Hash的方法做到),然后每个map task对一个数据块进行局部排序,之后,一个reduce task对所有数据进行全排序。  

相关热门搜索:云计算 大数据技术 hadoop云计算实战 云计算技术

大数据标签:hadoop hdfs mapreduce bigdata

问题导读:
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.png (10.2 KB, 下载次数: 1)

  

2014-7-12 17:33 上传

图表 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对每条记录的输出以 pair的形式输出。

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

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

2.png (74.26 KB, 下载次数: 1)

  

2014-7-12 17:34 上传

图表 2   mapreduce简单工作流程

(1)运行环境

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

(2)输入与输出

Map/Reduce框架运转在 键值对上,也就是说, 框架把作业的输入看为是一组 键值对,同样也产出一组  键值对做为作业的输出,这两组键值对的类型可能不同。

框架需要对key和value的类(class)进行序列化操作, 因此,这些类需要实现 Writable接口。 另外,为了方便框架执行排序操作,key类必须实现 WritableComparable接口。

一个Map/Reduce 作业的输入和输出类型如下所示:

(input)  -> map -> -> combine ->  -> reduce ->  (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进行排序来作为例子:

3.png (16.02 KB, 下载次数: 1)

  

2014-7-12 17:40 上传

如何将数据发给一个指定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>]  

(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算法的源代码:

1. * To run: bin/hadoop jar build/hadoop-examples.jar sort

2. *            [-m maps] [-r reduces]

3. *            [-inFormat input format class]

4. *            [-outFormat output format class]

5. *            [-outKey output key class]

6. *            [-outValue output value class]

7. *            [-totalOrder pcnt num samples max splits]

8. *            in-dir out-dir

9. */

10. public class Sort extends Configured implements Tool {

11. private RunningJob jobResult = null;

12.

13.

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

15.

16.   public static void main(String[] args) throws Exception {

17.      int res = ToolRunner.run(new Configuration(), new Sort(), args);

18. System.exit(res);

19. }

20.

21. /**

22.     * Get the last job that was run using this instance.

23. * @return the results of the last job that was run

24. */

25. public RunningJob getResult() {

26. return jobResult;

27. }

28. }

29.

复制代码

2.Secondsort算法分析

(1)工作原理

在map阶段,使用job.setInputFormatClass定义的InputFormat将输入的数据集分割成小数据块splites,同时InputFormat提供一个RecordReder的实现。本例子中使用的是TextInputFormat,他提供的RecordReder会将文本的一行的行号作为key,这一行的文本作为value。这就是自定义Map的输入是的原因。然后调用自定义Map的map方法,将一个个对输入给Map的map方法。注意输出应该符合自定义Map中定义的输出。最终是生成一个List。在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的源代码:

1. public class SecondarySort {

2.           //自己定义的key类应该实现WritableComparable接口

3.           public static class IntPair

4.                               implements WritableComparable {

5.             private int first = 0;

6.             private int second = 0;

7.

8.             /**

9.              * Set the left and right values.

10.              */

11.             public void set(int left, int right) {

12.               first = left;

13.               second = right;

14.             }

15.             public int getFirst() {

16.               return first;

17.             }

18.             public int getSecond() {

19.               return second;

20.             }

21.             /

22.         @Override

23.         //反序列化,从流中的二进制转换成IntPair

24.             public void readFields(DataInput in) throws IOException {

25.               first = in.readInt() + Integer.MIN_VALUE;

26.               second = in.readInt() + Integer.MIN_VALUE;

27.             }

28.         @Override

29.          //序列化,将IntPair转化成使用流传送的二进制

30.             public void write(DataOutput out) throws IOException {

31.               out.writeInt(first - Integer.MIN_VALUE);

32.               out.writeInt(second - Integer.MIN_VALUE);

33.         }

34.         //新定义类应该重写的两个方法

35.         @Override

36.         //The hashCode() method is used by the HashPartitioner (the default partitioner in MapReduce)

复制代码

1. //主函数

2. public static void main(String[] args) throws Exception {

3. // TODO Auto-generated method stub

4. // 读取hadoop配置

5. Configuration conf = new Configuration();

6. String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();

7. if (otherArgs.length != 2) {

8. System.err.println("Usage: secondarysrot  ");

9. System.exit(2);

10. }

11. // 实例化一道作业

12. Job job = new Job(conf, "secondary sort");

13. job.setJarByClass(SecondarySort.class);

14. // Mapper类型

15. job.setMapperClass(MapClass.class);

16. // Reducer类型

17. job.setReducerClass(Reduce.class);

18. // 分区函数

19. job.setPartitionerClass(FirstPartitioner.class);

20. // 分组函数

21. job.setGroupingComparatorClass(FirstGroupingComparator.class);

22. // map 输出Key的类型

23. job.setMapOutputKeyClass(IntPair.class);

24. // map输出Value的类型

25. job.setMapOutputValueClass(IntWritable.class);

26. // rduce输出Key的类型

27. job.setOutputKeyClass(Text.class);

28. // rduce输出Value的类型

29. job.setOutputValueClass(IntWritable.class);

30. // 输入hdfs路径

31. FileInputFormat.addInputPath(job, new Path(otherArgs[0]));

32. // 输出hdfs路径

33. FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));

34. // 提交job

35. System.exit(job.waitForCompletion(true) ? 0 : 1);

36. }

37.

38. }

复制代码

3.Terasort算法分析

(1)概述

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

(2)算法思想

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

4.png (60.58 KB, 下载次数: 1)

  

2014-7-12 17:53 上传

图表 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的排序结果顺序输出,即为最终的排序结果。

5.png (54.77 KB, 下载次数: 1)

  

2014-7-12 17:54 上传

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

6.png (7.2 KB, 下载次数: 1)

  

2014-7-12 17:55 上传

图表 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.png (28.24 KB, 下载次数: 1)

  

2014-7-12 17:57 上传

图表 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)        下面程序是一段关于树节点的源代码:

1.   * A leaf trie node that does string compares to figure out where the given

2.              * key belongs between lower..upper.

3.              */

4.             static class LeafTrieNode extends TrieNode {

5.               int lower;

6.               int upper;

7.               Text[] splitPoints;

8.               LeafTrieNode(int level, Text[] splitPoints, int lower, int upper) {

9.                 super(level);

10.                 this.splitPoints = splitPoints;

11.                 this.lower = lower;

12.                 this.upper = upper;

13.               }

14.               int findPartition(Text key) {

15.                 for(int i=lower; i= 0) {

17.                     return i;

18.                   }

19.                 }

20.                 return upper;

21.               }

22.               void print(PrintStream strm) throws IOException {

23.                 for(int i = 0; i < 2*getLevel(); ++i) {

24.                   strm.print(' ');

25.                 }

26.                 strm.print(lower);

27.                 strm.print(", ");

28.                 strm.println(upper);

29.               }

30.             }

复制代码

小组成员个人总结

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语句

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

建立视图或者物化视图

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

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

大数据系列hadoop相关文章:

最新评论
尖儿2014-09-09 10:31:52
有什么好的建议吗?
小宾2014-09-09 06:18:24
【小Vi在现场】硬蛋i未来硬件大赛北京赛区初赛,VICO李昂及团队为能有此机会与前辈切磋而感激,感激嘉宾和主办方的鼓励。我们仍将尽全力以赴,以期提供全方位的直观的人车互动。@hadoop向磊 @数据科学家联盟 @科通芯城网 @3W咖啡
-Hello_World2014-09-08 03:13:51
Process identifier=hconnection-0x12a3793 connecting to ZooKeeper ensemble=h0:2181
砖头2014-09-08 12:00:29
@小川 你好~我有个疑问呢,之前导入hdfs的数据在/user/hadoop/的路径下,当我把它映射到hive当中,数据路径就到/hive/warehouse/下了,这些路径代表什么呢??
玲玲2014-09-06 11:50:53
【SAP的托管HANA价格低廉 但内藏玄机】SAP的托管内存分析软件的定价与大数据其他同类软件的价钱似乎不差上下,但在大多数情况下SAP的售价低廉。最大的问题是,廉价是不是物有所值。Cowen分析师在一份研究报告中比较了HANA售价和Hadoop替代品售价。 http://t.cn/8ssYunD
paul2014-09-06 07:10:39
度娘出来了
帅哥2014-09-06 01:52:02
【惠普5000万美元战略投资大数据平台Hortonworks】据美国科技博客Re/code报道,惠普将在今天宣布,该公司将与2011年从雅虎分拆出来的Hadoop创业公司Hortonworks达成战略性合作关系,对后者投资5000万美元。详情点击:http://t.cn/RPbkfae
BZDDSM2014-09-05 11:49:38
9.12-14号、9.19-21号、9.26-28号上海、深圳、北京举办《决胜大数据时代:Hadoop、Yarn、Spark企业级最佳实践》公开课
雨中晴天2014-09-04 05:00:02
hadoop是中国云计算的先锋,但也有老外有不同的看法 http://t.cn/z8QUcRf http://t.cn/z884i6q
奥九马2014-09-03 08:36:33
#OSTC2014#腾讯大数据平台TDW项目技术负责人赵伟介绍了目前腾讯使用的TDW,分布式数据仓库。目前TDW部署最大集群点达到5000+台。构建TDW的开源软件有Hive、Hadoop、PostgreSQL。TDW项目是腾讯第一期开源项目,相关采访:http://t.cn/8sIfCsf
 
  • Hadoop生态系统资料推荐