4.2MapReduce编程模型在线视频

下面我们来介绍一下

MapReduce的编程模型

MapReduce的想法是数据变形

它另外也是一种非常常见的

算法设计的一种想法

叫分治策略

或者叫()

它的基本想法

是非常非常简单的

它首先经过一个Map的操作

这个MAP操作干什么

它们把数据分割为不同的块

这一块我们行话叫shards

或者叫splits

我们把这些个分成的shards

或者splits

把它们分给不同的工作节点

每一个工作节点

或者叫计算节点

然后来算这个子问题的解

就是说我算这一块里面

我该是数数

或者该做什么运算

我们来只做这一小块

再Reduce的过程中

我们把这些个分块的结果

给它收集起来

把子问题解合并起来

那么就得到了全局的解

这个想法其实在过去的讲

函数式编程

processing里头

经常是这样用的

这个想法早就有

但是MapReduce这个系统

用在大数据里头

是个非常了不起的贡献

是因为这个系统

是非常的容易使用

大家用的时候

根本不用关心各种分布式系统

带来的各种细节问题

而布局分析的人

可以集中的解决

它们数据分析的问题

而不用考虑系统是怎么实现的

刚才我提到了

这些出了错怎么办啊

这些MapReduce系统

都帮你解决好了

它的基本编程模型

就是你实现两个函数

一个叫Map 一个叫Reduce

这个Map函数

系统会不断的调用

你的Map函数

它每次调用的时候

给你传递两个参数

一个是Key 一个是value

它这一个key和一个value

是针对一个对象的

一个输入的记录来做的

比如说它就是一个词

或者是一行

或者是一个很小的单元

我们管它叫一条record

或者一条记录

你针对这条记录

来计算一些东西

那么你可以返回

一个突出的Key

和一组突出的value

记住输入是一个记录

你输入可以是一个list

就是一列记录

一组记录 一个集合

那么Reduce这一版

实际上它输入的是

针对你的Map的时候

输出的这个key

它把这个当成输入的key

传给你Reduce这一步

然后它把所有带有key的值

作为一个集合

一起传给你Reduce

那么怎么传递一个集合

那当然可能传进的是一个

interndiate 对吧

你可以在集合上的叠盖器

或者它给你传一个集合的指针

你可以在集合里来回走

这都是可以的

但是你从道理上

或者从概念上来说

它是把整个的

带有key的所有的值

全部传给你了

这个时候

你这个Reduce的函数

可以做很多运算

可以看看每一个值都是什么

把它们合并起来

一个一个值处理

处理完了之后

你可以输出一个

输出值的集合

这个就是Map Reduce的两步

这节课后边

我们会反反复复的提到这个

大家就会对这两个函数

有一个更深刻的了解

现在我们回到刚才的那个例子

就是词频统计这么一个例子

我们看看

MapReduce的情况下

它应该是怎么做的

还是这个数据

那么第一步Mapreduce

叫做Distrbute或者叫map这一步

我们把这一个数据

我们要切分

切分出来结果

叫（）或者叫（）

每一个（）或者（）

我们交给一个Map的函数

那这个Map函数

它就传进了一个key

像这种词频的问题

它其实是key是无所谓的

它关键是这个value

这个value就是这个值

它一个一个的value传给Map

我如果有的话我就加上1

那怎么加上1

它自个key这个小的表

它可以自个数一下

或者它可以把1输出

这都是两种不同的做法

但是我们比如说这个地方

它就是做了一个

本地的数数的方法

就是说我数了有几个dog

我数了有两个 is是1

它自己算出了一个子问题的解

这是一小块问题

它自己做了一个词频统计

第二步叫Reduce

那么Map会把它子问题的解

传给Reduce

那么怎么传这一个过程

在MapReduce里叫Shuffle

叫洗牌的过程

因为它每一个人都有dog

基本上每一个人dog

这个人没有 对吧

但是它就是零了

它如果有dog的话

那么我们想

把所有的dog放到一起

我要知道它总共有多少个

那么显然我们要把dog

这个东西传到

同一个reduce上

它才能组织一个值

那么所以Map1

会把dog传到这个里头

它会把is比如传到这里头

那么所有的人都要把dog

传到这里头

把is传到里头

把其它几个

它要是时间定好

每一个key

要传到哪一个reduce上来算

所以它等于是洗牌的过程

它把所有的key和value

交换了一下

交换给reduce

那么reduce作为干的事情

它收到的是什么

收到的是一个key

加上一组值

那么它把这个值合并起来

在这个情况下显然合并的方法

就是把这些值加起来

所以在本地就算出来了

到底有多少个cat

有多少个is 有多少个dog

这些东西都加起来

算出来这么一个值

那么最后一步

当然reduce实际上

这个是我们把全局的状态

把全局的答案

分成各个部分了

那么理论上来讲

我们最后的一部分

是应该把它合并在一起

合并在一起是很简单的

是把它appade一起

这个appade在一起

加在后边 对吧

大家就想到了jfs

那么jfs这个东西

本来就是把一个文件

appad在后边

所以它就把appade成一个文件

所以这个时候

我们就得到了

这个全局问题的解

这个是从理论上

Map如何运行的

那么下面我们来看一下

它的程序是怎么写的

这个程序你看起来

是非常非常简洁的

它只有两个函数

一个是Map 一个是reduce

刚才提到Map

它的输入就是一个输入的key

和一个输入的value

然后这个系统

会反反复复调用Map

那么每做一次Map的话

MAP会做这么一个函数

叫做countlocally

它们自己保持了

一个本地的技术

这个本地的技术

只对它这本地的这一个sas

或者一个split

这一小块数据有意义

那么它数了一下这个数

这个数怎么数

可以用一个()table

或者怎么样

这是一个本地的

这是一个in memery的计算

就是在内存里的计算

等它算完了之后

for each count

这个算完了以后它是一个表

它是有几个dog 有几个cat

那么我们对于这每一行

我把这个词 这个word

当成一个key

就是中间结果的key来输出

然后它的值是这个count

回到刚才这一页

就相当于这就是那个key

这个就是那个count 对吧

所以它对每一个

就把这个东西倒出来

这是什么意思

这个Emit就是把它返回给系统

那么系统就相当于

它会把它传给reduce

这个word实际上就是这个word

那调用reduce的时候

它所有相同的词

不管它是在哪个map里生成的

它都会传到reduce这一步

那么这个值

就会变成列表里的一个项

传到reduce这一步

这个它传的是一个Iterator

是一个迭代器 那么显然因为

可以有很多很多的map

有很多很多的count

它不可能把真正的

所有的count

当成一个大数组传给reduce

这时候reduce内存就爆了

所以它传的是一个迭代器

迭代器这个东西就是可以

一个一个的来Iterator

就来迭代在数组里边

把数值一个一个值拿出来看

就像这中 for each v
这种in intemediate values

那么就是我把

一个一个数组里面的值

或者这个集合里的值

一个一个拿出来看

我把这些值加在一起

最后我输出了这个结果

这个结果

结果是一个双元组

那么当然结果也是一样的

是一个词

这个词是它的key

然后它的result

就是它总体的技术

它就输出了这个结果

所以这个玩意

看起来是非常非常简单的

因为它里头根本没有涉及到

任何分布式的内容

你看起来它就是一个map

我们输了一个本地的结果

然后reduce我们把所有的类似的

相同的替代的结果都存在一起

然后把它加起来再输出

非常非常地简洁

那么再次要强调一下

因为这个map和reduce里头

有好几个k好几个value

大家一定要分清楚

这个k和value

到底都指的是什么东西

那么map的k和value

这就是文件输入的数据的键和值

它是本身是input键和值

那么这个key1和key2的类型

可以是不一样的

比如刚才的那个时间就不一样了

刚才那个key1是没有意义的

随便值什么都行

那么key2这是那个词 对吧

这是那个word

那value1是什么

value1刚才是那个word

但是value1和value2值的类型

也是无关的

那么value2它的值就是一个count

这个value1它是原来的那个词

或者是一个文章

可能是整个文章

整个文章可以切分成不同的词

这个它就是一个值 对吧

但是这两个是一个类型的

就是map输出的k2

和reduce输入的k2是一个类型的

那么map的这个value

和reduce的这个value

是一个类型的

但是reduce参数

是一个value的集合

它是所有

有这个key的value的集合

所以这两个东西

大家一定要分清楚

key1和key2它不是一个key

那个key2是你map的时候

你自己根据需要

你自己生成的一个key