• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

map_reduce原理

bigdata admin 3年前 (2017-05-25) 1161次浏览 0个评论 扫描二维码

进入大数据领域经常接触到的词汇就是 map /reduce,其实在这个在 python 中经常用到,比如处理一个 list 时,如果你要对每个元素进行相应的函数操作,就可以通过 map 的方式,当然你也可以通过生成烈表式来做,在大数据中区别还是在于分布式操作。

转载一篇白话原理 http://blog.csdn.net/lifuxiangcaohui/article/details/22675437

1.什么是 Map/Reduce,看下面的各种解释:

(1)MapReduce 是 hadoop 的核心组件之一,hadoop 要分布式包括两部分,一是分布式文件系统 hdfs,一部是分布式计算框,就是 mapreduce,缺一不可,也就是说,可以通过 mapreduce 很容易在 hadoop 平台上进行分布式的计算编程。

(2)Mapreduce 是一种编程模型,是一种编程方法,抽象理论。

(3)下面是一个关于一个程序员是如何个妻子讲解什么是 MapReduce?文章很长请耐心的看。

我问妻子:“你真的想要弄懂什么是 MapReduce?” 她很坚定的回答说“是的”。 因此我问道:

我: 你是如何准备洋葱辣椒酱的?(以下并非准确食谱,请勿在家尝试)

妻子: 我会取一个洋葱,把它切碎,然后拌入盐和水,最后放进混合研磨机里研磨。这样就能得到洋葱辣椒酱了。

妻子: 但这和 MapReduce 有什么关系?

我: 你等一下。让我来编一个完整的情节,这样你肯定可以在 15 分钟内弄懂 MapReduce.

妻子: 好吧。

我:现在,假设你想用薄荷、洋葱、番茄、辣椒、大蒜弄一瓶混合辣椒酱。你会怎么做呢?

妻子: 我会取薄荷叶一撮,洋葱一个,番茄一个,辣椒一根,大蒜一根,切碎后加入适量的盐和水,再放入混合研磨机里研磨,这样你就可以得到一瓶混合辣椒酱了。

我: 没错,让我们把 MapReduce 的概念应用到食谱上。Map 和 Reduce 其实是两种操作,我来给你详细讲解下。
Map(映射): 把洋葱、番茄、辣椒和大蒜切碎,是各自作用在这些物体上的一个 Map 操作。所以你给 Map 一个洋葱,Map 就会把洋葱切碎。 同样的,你把辣椒,大蒜和番茄一一地拿给 Map,你也会得到各种碎块。 所以,当你在切像洋葱这样的蔬菜时,你执行就是一个 Map 操作。 Map 操作适用于每一种蔬菜,它会相应地生产出一种或多种碎块,在我们的例子中生产的是蔬菜块。在 Map 操作中可能会出现有个洋葱坏掉了的情况,你只要把坏洋葱丢了就行了。所以,如果出现坏洋葱了,Map 操作就会过滤掉坏洋葱而不会生产出任何的坏洋葱块。

Reduce(化简):在这一阶段,你将各种蔬菜碎都放入研磨机里进行研磨,你就可以得到一瓶辣椒酱了。这意味要制成一瓶辣椒酱,你得研磨所有的原料。因此,研磨机通常将 map 操作的蔬菜碎聚集在了一起。

妻子: 所以,这就是 MapReduce?

我: 你可以说是,也可以说不是。 其实这只是 MapReduce 的一部分,MapReduce 的强大在于分布式计算。

妻子: 分布式计算? 那是什么?请给我解释下吧。

我: 没问题。

我: 假设你参加了一个辣椒酱比赛并且你的食谱赢得了最佳辣椒酱奖。得奖之后,辣椒酱食谱大受欢迎,于是你想要开始出售自制品牌的辣椒酱。假设你每天需要生产 10000 瓶辣椒酱,你会怎么办呢?

妻子: 我会找一个能为我大量提供原料的供应商。

我:是的..就是那样的。那你能否独自完成制作呢?也就是说,独自将原料都切碎? 仅仅一部研磨机又是否能满足需要?而且现在,我们还需要供应不同种类的辣椒酱,像洋葱辣椒酱、青椒辣椒酱、番茄辣椒酱等等。

妻子: 当然不能了,我会雇佣更多的工人来切蔬菜。我还需要更多的研磨机,这样我就可以更快地生产辣椒酱了。
我:没错,所以现在你就不得不分配工作了,你将需要几个人一起切蔬菜。每个人都要处理满满一袋的蔬菜,而每一个人都相当于在执行一个简单的 Map 操作。每一个人都将不断的从袋子里拿出蔬菜来,并且每次只对一种蔬菜进行处理,也就是将它们切碎,直到袋子空了为止。
这样,当所有的工人都切完以后,工作台(每个人工作的地方)上就有了洋葱块、番茄块、和蒜蓉等等。

妻子:但是我怎么会制造出不同种类的番茄酱呢?

我:现在你会看到 MapReduce 遗漏的阶段—搅拌阶段。MapReduce 将所有输出的蔬菜碎都搅拌在了一起,这些蔬菜碎都是在以 key 为基础的 map 操作下产生的。搅拌将自动完成,你可以假设 key 是一种原料的名字,就像洋葱一样。 所以全部的洋葱 keys 都会搅拌在一起,并转移到研磨洋葱的研磨器里。这样,你就能得到洋葱辣椒酱了。同样地,所有的番茄也会被转移到标记着番茄的研磨器里,并制造出番茄辣椒酱。

(4)上面都是从理论上来说明什么是 MapReduce,那么咱们在 MapReduce 产生的过程和代码的角度来理解这个问题。
如果想统计下过去 10 年计算机论文出现最多的几个单词,看看大家都在研究些什么,那收集好论文后,该怎么办呢?

方法一:
我可以写一个小程序,把所有论文按顺序遍历一遍,统计每一个遇到的单词的出现次数,最后就可以知道哪几个单词最热门了。 这种方法在数据集比较小时,是非常有效的,而且实现最简单,用来解决这个问题很合适。

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

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

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

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

map 函数和 reduce 函数

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

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

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

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

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)。

工作原理

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

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

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

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

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

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

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

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

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

总结:

通过以上你是否了解什么是 MapReduce 了那,什么是 key,怎么过滤有效数据,怎么得到自己想要的数据。
MapReduce 是一种编程思想,可以使用 java 来实现,C++来实现。Map 的作用是过滤一些原始数据,Reduce 则是处理这些数据,得到我们想要的结果,比如你想造出番茄辣椒酱。也就是我们使用 hadoop,比方来进行日志处理之后,得到我们想要的关心的数据


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明map_reduce 原理
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!