MapReduce执行过程在线视频

刚才我们看到MapReduce的程序

是非常简单的

下面我们来看一下

MapReduce是怎么执行的

这个执行步骤

大家可能已经可以想象了

因为输入数据是分割成M块的

或者M个Shard

我们其实针对每一块

就调用这个Map函数就对了

那么大家现在可能想象的是

这每一块 切得我们有多大

那么当然最简单的一种切分

就是说GFS的那个块有多大

我们把每一个GFS的块

都给一个Map就好了

甚至于我们

可以把一个GFS的块

再切成好几小块

一个人读前一半

一个人读后一半

一个人读前四分之一

第二个四分之一

三个四分之一 四个四分之一

所以这个块不宜太小

但是也不宜太大

这个我们待会儿

会详细的讨论一下

块应该切成多少块

输入的数据

那么这些块当然由不同的

服务器处理了

那么有多少台服务器

那么这个MapReduce系统

我准备用多少台服务器

那么他会把这M块

分到小M个服务器上来算

那么中间的结果就是

M这一步的输出

那么我们输出了一个

中间的Key

中间的value这些值

我们也把它当作一种

下一步的输入 是一样

采取一种切分

然后我们把它R块

然后每一块

进行分布式的调用Reduce

这一步还是非常的

有意思的 我们马上会看到

因为这个R块

这些分块的时候你必须要想到

相同的Key必须在同一块

否则的话

他们将来就没办法合并在一起了

所以这一步

还是有一些个小技巧的

我们马上会看到

这些小技巧怎么做

在看到这些个具体的细节之前

我们想想

到底我们应该

把它分成多少块合适

这块应该有多大合适

这个数量

MapReduce系统是不管的

它要让用户来指定

你要告诉它 我想分成多少Map

多少个Reduce

那用户应该怎么选择

我们一般的建议是说

我们要选择这个M

就是Map的数量

要远远大于servers的数量

而Reduce的数量

一般应该大于servers的数量

但是也不应该太多

这是为什么

因为你想一个块和另块

它处理的时间可能是不一样的

比如说 就是最简单的

（02：07）这件事情

那有些个输入

可能它里头输入词多一点

有些文章

可能输入的词少一点

有的可能都是小词它比较难数

有些可能大词 它容易数

或者有些里头中文的多一些

它分词什么的 都比较慢

这个各个情况下都有

所以我们期望呢是

你最好所有的服务器

在所有的时间 它都在跑任务

那你把它切得越小

你就越容易调度

因为有些块跑得块

那我可以多塞给你两块 跑一跑

如果你的块跟那个servers的

数差不多

那你一个servers

跑完了一块儿之后

他闲了但是没有别的块给他跑了

但是有一个人

可能跑得特别慢

那么就得互相等

这就像 好比说

你说我想把一堆石头

然后把它堆成五堆

然后每堆一样高

和我把一堆沙子堆成五堆

每堆一样高

那哪一个更简单

那显然沙子更简单一点

因为它比较碎

你可以把它弄得更平

这就是为什么

我们希望Map的数量

要远远大于servers

这个作为你能够

更有助于它能够做负载均衡

当然了如果服务器坏了的话

你块越小 它也越容易恢复

你重算的东西越少

Reduce当然了

你要想把它切的无穷细

它也可以 它也是一样的理由

但是

Reduce不宜切得太细

是因为每一个Reduce的输出

它都会输出一文件 为什么

因为Reduce

其实我们理论上讲

最后一步是合并的

但是其实并不是

其实像GFS这种东西

它一块一块的

它是（03：33）

它是相当于很多的块

它都是连成一个大的文件

它并没有最后把它在（03：39）

压缩成一个文件

所以在这种情况下

每一个Reduce输出的结果

它都是一个文件

如果每一个Reduce输出太小的话

它实际上占用了

大量的GFS上的块

上节课 我们也讲到

GFS 它不宜有太多的块

否则它的元数据操作会非常地慢

所以这就是为什么Reduce

它不宜做得太大

因为它每一个Reduce

会输出一个文件的

那么MapReduce执行过程

大概其实理解这样的

我们把输入文件

先分成了很多的Map

这里有很多很多的Map 对吧

我们为了做细粒度任务

为了刚才说的负载均衡

为了快速地恢复

我们把Map切成了

远大于机器数量的这么多个Map

然后这些Map会一个一个的

提交给很多很多的机器运行

一个机器会运行

很多个Map的函数

运行完了之后

它会把结果输出

这个结果会存在本地硬盘

待会我们会看到这个细节

然后之后的话

这个操作是MapReduce的

一个非常核心的操作

叫做Group by Key的

这么一个操作

在这个操作中相同的Key

会被组合在一起

这个是怎么组合在一起的

那么我们下一章（04：43）

马上就会看到

但是这个过程

实际上它是一个排序的过程

因为排序实际上把

按照Key排序

那么当然相同的Key

就会排在一起

最后排好序之后

我们会把类似的Key

都交给一个Reduce来做

所以它一个Key

体具有相同Key的Value

那么都在一个Reduce上

这个Reduce

会进行Reduce的运算

最后输出结果

那我们一般来讲 推荐的是

比如说我们有2000个服务器

那我们可能跑

大概20万个Map的任务

大概跑5000个Reduce的任务

因为这样的话 Reduce的任务

还是比服务器的东西多的

以防有一个Reduce很快完成了

其他的还可以替补一下

但是它又不至于输出

同时输出20万的文件

来给GFS造成更多的压力

这是MapReduce简单的执行过程

我们后边会一步一步的

详细的看到里头

具体每一步发生了什么事

但是现在最重要的就是这个

Group by Key的这么一个操作

这个操作

我们马上看一下这个操作

具体是怎么实现的

这个Map函数在最后一步

大家可能记得那个里头

调了一个这样的东西

叫做emit 这个emit函数

干了什么事情

那么我这个emit函数

这是一个中间的Key

中间的Value 对吧

那么这emit函数

首先干了一件事情

它根据这个中间的Key

算出了一个partition的id

或者shard id

那么这个函数

也是用户可以指定的

你可以指定

我怎么样根据这个中间的Key

来算出来我这个Key

应该在第几号Reduce上运行

或者在第几个Shard里来运行

那么一个Shard

实际上就针对了一个Reduce

那么所以比如说

这个Key最简单的算法

就是做一个（06：24）

那么比如说dog它成了1

那么dog就在第一个Shard里

this 它是成了2

那么就在第二个function里头

is成了3 就在第三个function

你可以有很多个Shard

这个number Shards

在这恰好等于

就是到底有多少个Shards

为什么你要设定

这个Reduce的number

它实际上就是Map的时候

看到了有多少个Reduce

那我就把它分成多少个Shards

因为这个（06：50）function

是可以调的

这个哈基函数

意思就是 相当于最后磨个几

它就是相当于几

所以这个数 并不是定死的

所以它在Map结束的时候

调这个emit的时候

他就决定了这一个Key

会跑到哪个Shard里头去

那么接下来的事情就比较简单了

所以这个Map调了emit

把这些Key都存在了Shard里

这个Shard

是放在它自己本地硬盘的

那么它算完了之后

这个Reduce是一个进程

起来之后 它会干什么

Reduce起来之后

它知道它自己是第几号Reduce

比如说Reduce1

它知道 我是1号Reduce

那么我就去会跟每一个Map说

我要你的第一个Shard

你把第一个Shard都给我

那么它就会把每一个Map的

第一个Shard都拿到

它怎么找到这些Map的

那当然是有一个中心控制的

这个master的节点告诉它的

对吧 所以它 这个人告诉它

这些Map都有Shard1了 你去要去

那它就过去 一个一个要

他就会这些东西

从Map的本地硬盘上

传到它自己的本地硬盘上

那相同的Reduce2

也可以做类似的事

Reduce3也会做了类似的事

他们每个人都要

跟他们自己的号码相同的

这个Shard 放到它自己硬盘上

这个过程叫做（08：01）

或者叫做Remote Read

这是（08：03）的一部分

叫Remote Read

这一部分是MapReduce

如果大家仔细想想

这个过程的话

只有这一步是经历了网络通讯

它屈从于（…red）

当然了 我们不考虑

它读GFS的时候的网络通讯

但是从MapReduce自身来说

只有这个Remote Read

这一步是网络通讯

那么Reduce之后

它得到了不同的Shard

它可能有很多个Shard

记得我们 如果我们

有20万个Map的话

那么它就有20万个这种文件

就会有20万个这种Shard

那么它需要把所有的这些个

相同的Key

把这些要Group在一起

然后才能调Reduce的函数

那么这个时候怎么做

那么排序是一个方法

当然为什么不用这个（08：39）

因为它的表可能很大

不是一个内存的算法

所以它外存排序

是一个非常成熟的方法

那么怎么外存排序的

那么就是（08：49）对吧

这个外层排序

我把很多的文件

先把文件自身排好

然后 然后我把

这个文件再归并排序一把

（08：57）算是叫归并排序

所以我们归并排序一把

然后最后得到的就是

一个一个的Key

和带有这个Key的Value

那么每一个Reduce

都并发的进行这种排序

这叫Sort的过程

让排好序的这一串东西

我们就可以把它

传给Reduce的函数了

我们传给它一个Key

加上一个指向这个值的集合的

这么一个指针

或者是一个迭代器

那么它就可以

进行Reduce这一步了

所以整个这一大套东西

就是一个Sort的过程

Sort实际上是MapReaduce系统

最复杂的一步

但是用户一般来讲

除了有些个用户

他有特殊需求

需要指定

这个Partition function之外

大部分用户

是根本不用关心这一步

到底干了什么的

这一步是饰系统帮你自动干的