MapReduce有什么用

80次阅读
没有评论

共计 4093 个字符,预计需要花费 11 分钟才能阅读完成。

本篇内容主要讲解“MapReduce 有什么用”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让丸趣 TV 小编来带大家学习“MapReduce 有什么用”吧!

1. MapReduce 是干啥的

Hadoop 实际上就是谷歌三宝的开源实现,Hadoop MapReduce 对应 Google MapReduce,HBase 对应 BigTable,HDFS 对应 GFS。HDFS(或 GFS)为上层提供高效的非结构化存储服务,HBase(或 BigTable)是提供结构化数据服务的分布式数据库,Hadoop MapReduce(或 Google MapReduce)是一种并行计算的编程模型,用于作业调度。

GFS 和 BigTable 已经为我们提供了高性能、高并发的服务,但是并行编程可不是所有程序员都玩得转的活儿,如果我们的应用本身不能并发,那 GFS、BigTable 也都是没有意义的。MapReduce 的伟大之处就在于让不熟悉并行编程的程序员也能充分发挥分布式系统的威力。

简单概括的说,MapReduce 是将一个大作业拆分为多个小作业的框架(大作业和小作业应该本质是一样的,只是规模不同),用户需要做的就是决定拆成多少份,以及定义作业本身。

下面用一个贯穿全文的例子来解释 MapReduce 是如何工作的。

2. 例子:统计词频

如果我想统计下过去 10 年计算机论文出现最多的几个单词,看看大家都在研究些什么,那我收集好论文后,该怎么办呢?

方法一:我可以写一个小程序,把所有论文按顺序遍历一遍,统计每一个遇到的单词的出现次数,最后就可以知道哪几个单词最热门了。

这种方法在数据集比较小时,是非常有效的,而且实现最简单,用来解决这个问题很合适。

方法二:写一个多线程程序,并发遍历论文。

这个问题理论上是可以高度并发的,因为统计一个文件时不会影响统计另一个文件。当我们的机器是多核或者多处理器,方法二肯定比方法一高效。但是写一个多线程程序要比方法一困难多了,我们必须自己同步共享数据,比如要防止两个线程重复统计文件。

方法三:把作业交给多个计算机去完成。

我们可以使用方法一的程序,部署到 N 台机器上去,然后把论文集分成 N 份,一台机器跑一个作业。这个方法跑得足够快,但是部署起来很麻烦,我们要人工把程序 copy 到别的机器,要人工把论文集分开,最痛苦的是还要把 N 个运行结果进行整合(当然我们也可以再写一个程序)。

方法四:让 MapReduce 来帮帮我们吧!

MapReduce 本质上就是方法三,但是如何拆分文件集,如何 copy 程序,如何整合结果这些都是框架定义好的。我们只要定义好这个任务(用户程序),其它都交给 MapReduce。

在介绍 MapReduce 如何工作之前,先讲讲两个核心函数 map 和 reduce 以及 MapReduce 的伪代码。

3. map 函数和 reduce 函数

map 函数和 reduce 函数是交给用户实现的,这两个函数定义了任务本身。

map 函数:接受一个键值对(key-value pair),产生一组中间键值对。MapReduce 框架会将 map 函数产生的中间键值对里键相同的值传递给一个 reduce 函数。

reduce 函数:接受一个键,以及相关的一组值,将这组值进行合并产生一组规模更小的值(通常只有一个或零个值)。

统计词频的 MapReduce 函数的核心代码非常简短,主要就是实现这两个函数。

[plain] view plain copy

 print?

map(String key, String value): 

 // key: document name 

 // value: document contents 

 for each word w in value: 

 EmitIntermediate(w,  1  

 

reduce(String key, Iterator values): 

 // key: a word 

 // values: a list of counts 

 int result = 0; 

 for each v in values: 

 result += ParseInt(v); 

 Emit(AsString(result)); 

在统计词频的例子里,map 函数接受的键是文件名,值是文件的内容,map 逐个遍历单词,每遇到一个单词 w,就产生一个中间键值对 w, 1,这表示单词 w 咱又找到了一个;MapReduce 将键相同(都是单词 w)的键值对传给 reduce 函数,这样 reduce 函数接受的键就是单词 w,值是一串 1(最基本的实现是这样,但可以优化),个数等于键为 w 的键值对的个数,然后将这些“1”累加就得到单词 w 的出现次数。最后这些单词的出现次数会被写到用户定义的位置,存储在底层的分布式存储系统(GFS 或 HDFS)。

4. MapReduce 是如何工作的

一切都是从最上方的 user program 开始的,user program 链接了 MapReduce 库,实现了最基本的 Map 函数和 Reduce 函数。图中执行的顺序都用数字标记了。

MapReduce 库先把 user program 的输入文件划分为 M 份(M 为用户定义),每一份通常有 16MB 到 64MB,如图左方所示分成了 split0~4;然后使用 fork 将用户进程拷贝到集群内其它机器上。

user program 的副本中有一个称为 master,其余称为 worker,master 是负责调度的,为空闲 worker 分配作业(Map 作业或者 Reduce 作业),worker 的数量也是可以由用户指定的。

被分配了 Map 作业的 worker,开始读取对应分片的输入数据,Map 作业数量是由 M 决定的,和 split 一一对应;Map 作业从输入数据中抽取出键值对,每一个键值对都作为参数传递给 map 函数,map 函数产生的中间键值对被缓存在内存中。

缓存的中间键值对会被定期写入本地磁盘,而且被分为 R 个区,R 的大小是由用户定义的,将来每个区会对应一个 Reduce 作业;这些中间键值对的位置会被通报给 master,master 负责将信息转发给 Reduce worker。

master 通知分配了 Reduce 作业的 worker 它负责的分区在什么位置(肯定不止一个地方,每个 Map 作业产生的中间键值对都可能映射到所有 R 个不同分区),当 Reduce worker 把所有它负责的中间键值对都读过来后,先对它们进行排序,使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个 Reduce 作业(谁让分区少呢),所以排序是必须的。

reduce worker 遍历排序后的中间键值对,对于每个唯一的键,都将键与关联的值传递给 reduce 函数,reduce 函数产生的输出会添加到这个分区的输出文件中。

当所有的 Map 和 Reduce 作业都完成了,master 唤醒正版的 user program,MapReduce 函数调用返回 user program 的代码。

所有执行完毕后,MapReduce 输出放在了 R 个分区的输出文件中(分别对应一个 Reduce 作业)。用户通常并不需要合并这 R 个文件,而是将其作为输入交给另一个 MapReduce 程序处理。整个过程中,输入数据是来自底层分布式文件系统(GFS)的,中间数据是放在本地文件系统的,最终输出数据是写入底层分布式文件系统(GFS)的。而且我们要注意 Map/Reduce 作业和 map/reduce 函数的区别:Map 作业处理一个输入数据的分片,可能需要调用多次 map 函数来处理每个输入键值对;Reduce 作业处理一个分区的中间键值对,期间要对每个不同的键调用一次 reduce 函数,Reduce 作业最终也对应一个输出文件。

我更喜欢把流程分为三个阶段。第一阶段是准备阶段,包括 1、2,主角是 MapReduce 库,完成拆分作业和拷贝用户程序等任务;第二阶段是运行阶段,包括 3、4、5、6,主角是用户定义的 map 和 reduce 函数,每个小作业都独立运行着;第三阶段是扫尾阶段,这时作业已经完成,作业结果被放在输出文件里,就看用户想怎么处理这些输出了。

5. 词频是怎么统计出来的

结合第四节,我们就可以知道第三节的代码是如何工作的了。假设咱们定义 M =5,R=3,并且有 6 台机器,一台 master。

这幅图描述了 MapReduce 如何处理词频统计。由于 map worker 数量不够,首先处理了分片 1、3、4,并产生中间键值对;当所有中间值都准备好了,Reduce 作业就开始读取对应分区,并输出统计结果。

6. 用户的权利

用户最主要的任务是实现 map 和 reduce 接口,但还有一些有用的接口是向用户开放的。

an input reader。这个函数会将输入分为 M 个部分,并且定义了如何从数据中抽取最初的键值对,比如词频的例子中定义文件名和文件内容是键值对。

a partition function。这个函数用于将 map 函数产生的中间键值对映射到一个分区里去,最简单的实现就是将键求哈希再对 R 取模。

a compare function。这个函数用于 Reduce 作业排序,这个函数定义了键的大小关系。

an output writer。负责将结果写入底层分布式文件系统。

a combiner function。实际就是 reduce 函数,这是用于前面提到的优化的,比如统计词频时,如果每个 w, 1 要读一次,因为 reduce 和 map 通常不在一台机器,非常浪费时间,所以可以在 map 执行的地方先运行一次 combiner,这样 reduce 只需要读一次 w, n 了。

map 和 reduce 函数就不多说了。

7. MapReduce 的实现

目前 MapReduce 已经有多种实现,除了谷歌自己的实现外,还有著名的 hadoop,区别是谷歌是 c ++,而 hadoop 是用 java。另外斯坦福大学实现了一个在多核 / 多处理器、共享内存环境内运行的 MapReduce,称为 Phoenix(介绍)。

到此,相信大家对“MapReduce 有什么用”有了更深的了解,不妨来实际操作一番吧!这里是丸趣 TV 网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-16发表,共计4093字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)