MapReduce & Hadoop

         MapReduce & Hadoop

 

2.2.1示例

 

考虑这样一个例子，在一个很大的文档集合中，计算每一个单词出现的次数。

可以使用下面的伪代码表示:

 

Map(String key, String value): //key:文档名 //value:文档内容 For each Word w in value: Emitlntermediate(w, ‘1’);

Reduce(String key, Iterator values): //key:一个单词 //value:值列表 For each v in values: Result+=Parselni(v): Emit(AsString(Result));

 

在这个例子中，map函数检查每一个单词，并且对每一个单词增加1到其对应的计数器(在这个例子里就是’1’)。reduce函数把特定单词的所有出现次数进行合并。

此外，还有一些可以用MapReduce轻松表示的问题，如:

1)分布式GreP:Map函数根据指定的模式匹配到特定的行并将其传递给Reduce函数。Reduce函数将这些中间结果作为最终结果输出。

2)URL访问频率统计:Map函数处理网页请求日志，输出<URL, 1>。Reduce函数对相同URL累加，规约为<URL, total_count>对。

3)倒排索引:Map函数从每个文档中抽取关键字，生成<key, document ID>对。Reduce处理给定关键字的所有组，生成<word，list(document ID)>对。输出的集合形成一个简单的倒排索引。

4)主机词组向量:一个词组向量就是出现在一个或一组文档中最重要的词，以<word, frequency>对列表的形式表示。Map函数通过处理输入文档，输出<hostname，term vector>对。Reduce函数对具有相同的host进行规约，它将这些词组向量合并，去除非常用词，最终输出<hostname，term vector>对。

 

2.7开源MapReduce实现-Hadoop

2.7.1概况

Hadoop是大名鼎鼎的Lucene旗下的子项目，它原先是Nutch项目的组成部分，于2006年初从Nutch中分离出来成为一个独立的项目。Hadoop并非一个单纯用于存储的分布式文件系统，而是一个被设计用来在由普通硬件设备组成的大型集群上执行分布式应用的框架。Hadoop包含两个部分:一个分布式文件系统HDFS(Hadoop Distributed File System)，和一个M即Reduce实现。因此，Hadoop的目标是为开发分布式应用提供一个框架，而不是像OpenAFS，Coda那样为存储提供一个分布式文件系统。搜索引擎就是一种典型的分布式程序，Nutch就是基于Hadoop开发的。

 

2.2.2.MapReduce算法

MapReduce不仅是Google的一项重要技术，它更是一个编程模型，用以进行大数据量的计算。对于大数据量的计算，通常采用的处理手法就是并行计算。至少现阶段而言，对许多开发人员来说，并行计算还是一个比较遥远的东西。MapReduce就是一种简化并行计算的编程模型，它让那些没有多少并行计算经验的开发人员也可以开发并行应用。在我看来，这也就是MapReduce的价值所在，通过简化编程模型，降低了开发并行应用的入门门槛。相对于现在普通的开发而言，并行计算需要更多的专业知识，有了MapReduce，并行计算就可以得到更广泛的应用。

MapReduce的名字源于这个模型中的两项核心操作:Map和Reduce。也许熟悉函数式编程(Functional Programming)的人见到这两个词会倍感亲切。简单的说来，Map是把一组数据一对一的映射为另外的一组数据，其映射的规则由一个函数来指定，比如对[l，2，3，4]进行乘2的映射就变成了[2，4，6，8]。Reduce是对一组数据进行归约，这个归约的规则由一个函数指定，比如对[1，2，3，4]进行求和的归约得到结果是10，而对它进行求积的归约结果是24。

Map操作是独立的对每个元素进行操作，在函数式编程中，操作是没有副作用的，换句话说，Map操作将产生一组全新的数据，而原来的数据保持不变。因此，它是高度并行的。Reduce操作虽然不如Map操作并行性那么好，但是它总会得到一个相对简单的结果，大规模运算也相对独立，因此也是比较适合并行的。

无论是Map还是Reduce都是以另外的函数作为参数，在函数式编程中，这样的函数被称为高阶函数(high-order function)。正是因为它们可以同其它函数相结合，所以，我们只要把Map和Reduce这两个高阶函数进行并行化处理，而无需面面俱到的把所有的函数全部考虑到。这样便形成了一个以Map和Reduce为基础的框架，具体应用相关代码写在用户代码中，之后与MapReduce结合获得并行处理的能力。当然，这么做的前提是按照这个框架的要求，把计算归结为Map和Reduce操作。为什么是Map和Reduce?从前面的内容我们可以看出，在Map过程中，我们将数据并行，也就是将数据分开，而Reduce则把分开的数据合到了一起，换句话说，Map是一个分的过程，Reduce则对应着合，这一分一合便在不知不觉中完成了计算。所以，站在计算的两端来看，与我们通常熟悉的串行计算没有任何差别，所有的复杂性都在中间隐藏了。

所有这些并行化能力的获得都与函数式编程有着密不可分的关系。事实上，不仅仅是MapReduce从FP中获得了灵感，其它一些并行编程模型也走上了同样的道路。函数式编程中有很多的好东西，比如自动内存管理，比如动态类型。在遥远的年代里，因为机器性能的原因，它们无法得到广泛应用，当机器性能不再是瓶颈，这些东西便逐渐复活了。

前面提到过，并行计算对于普通开发人员来说，有一个比较高的门槛。从前我们或许可以不理会并行计算，但是随着Intel开始将多核带入人们的日常生活，并行计算将会变得更加平民化，毕竟谁也不希望自己机器里面的多核只有一个在干活。现在的许多操作系统会把多核视为多处理器，但那也得有多任务才能在CPU处多分得一杯羹。对于服务器端应用来说，拥有多任务的能力是一个正常的现象。但对于很多桌面应用来说，一条道跑到黑的情况比较多见。而且，多任务并非为并行计算专门准备的，所以，控制粒度是很大的。如果需要更细粒度的并行计算，至少从表达能力上来说，多任务就有些麻烦了。

并行计算进入日常开发的难度就在于编程模型，太复杂的东西会被人唾弃的，CORBA在这方面已经是个反面教材了。MapReduce已经为我们演示了一种可以接受的编程模型。

 

 

参考文献：   基于MapReduce模型的并行计算平台的设计与实现

基于Hadoop的海量数据处理模型研究和应用