Video在线视频

大家好我们刚刚说到了这个

什么是MapReduce

以及MapReduce数据处理模式

以及它简单的

这种系统调度的策略有哪一些

那么下面我们

就想来帮大家回答一个很重要的问题

MapReduce到底有什么用

我们讲了很多大家也看到

好像MapReduce能做一些简单的事情

比如说从文章里面

查到每个单词出现的这样一个频率

但是这些任务看起来太过于简单了

好像在真实的这样一个世界

当中不能起到什么样的作用

那么我们在这一小节里面就会去介绍

MapReduce它到底能够做一些什么样的

这种实际的工业

或者说实际的数据处理里面的任务

那我们来看MapReduce中的

算法到底有哪一些典型的这种模式

那在这里面实际上

我们会介绍几个非常简单的这种

但是非常实用的这个MapReduce

就是能够做的这种算法的过程

那么通过这些过程

希望大家能够大致的了解

用MapReduce

怎么样去处理大规模的数据

以及大家在后面通过对这些算法

或者说其他的MapReduce

就是这种算法进行组合

能够完成你们比较复杂的

这种数据处理的一个需求

那第一个例子

是怎么样用MapReduce来做search

实际上这也是google和google公司

它的搜索引擎非常匹配的一个专题

它们能够用MapReduce

对网页进行一个排序

然后让用户能够对关键词进行搜索

那么我们就来做这样的

一个非常简单的版本

怎么样来对关键词进行一个搜索

那么我们来看它的输入是什么

输入是这个原始的行号

和行的这样一个记录

那么输出是什么

我们希望给定它一个pattern

也就是一个匹配的模式

然后把所有包含了

这样一个模式的行给输出出来

那这是我们的一个算法的一个需求

那我们来看这个过程我们怎么去做

那在我们手里面

我们有两个工具

一个是map一个是reduce

我们可以在map里面填充一些功能

可以reduce里面填充一些功能

让它们按照我们的方式

我们的要求去处理这样的一些数据

我们来看

为了达到这样的一个搜索的一个目标

我们做一些什么样的事情

那么在这个例子

当中我们用了这样一个Python的

伪代码进行描述

我们来看在map里面

我们做了些什么样的事情

那在map里面有一个if语句

那这个if给出当行匹配上

这个pattern的时候我们就输出这一行

那这是map

那么在reduce阶段

reduce阶段是一个identify function

也就是说把map

给到它的这样一个结果

直接输出到HDFS

什么都不做

不做任何操作

也就是no reduce

好

那我们来看这个过程是怎么样进行的

那么当我们有一系列的line number

和这个line的时候

实际上

整个过程会去匹配每一行

出现的这样一个单词

当匹配到的时候

行就会被输出到中间结果上

那么这一行就会通过中间结果

直接通过网络传输到reduce的节点

那么reduce会把这些数据直接匹配

直接输出到了这个分布式文件系统里面

那这是完成了一个搜索这样的操作

那么有了搜索之后实际上

我们已经可以做很多的事情

我们可以在有的数据集里面去查找关键词

我们可以去查找

具有某一些模式的图片或者是视频

那么都可以在成百上千的

这样一个服务器上来

完成我们需要的任务

那第二个任务也是非常常用

而且非常重要非常核心的一个算法

叫做排序sort

我们来看由MapReduce

怎么样来达到sort的一个任务

听起来好像有点难

因为在map和reduce两阶段里面

我们从来没有

说过有什么地方可以做sort

可以把数据做这样的一个关联

那我们来看MapReduce

怎么解决这样一个问题

那么我们来看看这个问题的描述

我们输入同样

是Key和value一个数据集

我们的输出是排序好的结果

那这个结果是按照它的Key

进行了这样一个排序

我们来看看MapReduce分别做了什么事情

map阶段我们发现

它是一个identify function

我们刚刚说到这个function是什么都不做的

也就是说把读入到的数据

直接写入到中间结果

然后交给了reducer

reducer我们发现也是什么都不做

直接把结果输出到了分布式文件系统

那两个东西我们好像什么都没有做

那它为什么

会完成一个排序的这样一个功能

那么它的一个trick它的这样一个技巧

就在于我们实际上要选择一个很好的

这个partition的函数

这个partition的函数

帮我们完成了这样一个排序的过程

我们刚刚说到partition

实际上做了什么事情

就是说决定了中间结果具有的Key

会最终被哪一个reducer去处理

那么我们通过精心的

选择这样一个Key

使它具有一个什么样的特性呢

也就是我们在PPT里面

写到的这样一个特性

当K1小于K2的时候

我们让它的哈希K1 HK1

也小于K2的哈希HK2

那有了这样一个特性之后

我们就能够保证我们的数据

能够是它的这个

根据它的中间结果被有顺序的

分配给不同的reducer去处理

而reducer在输出的时候

又会按照这样一个顺序

把结果输出到最终的文件

大家可以回想一下我们最终输出的文件

也是一个key value这样的一个形式

所以由于我们在隐含的利用了这样一个

partition的一个函数

实际上我们即使使用了

两个什么都不做的

map和reduce的一个功能

我们最终也可以让它输出这样一个

我们想要的排序好了的一个结果

那么在这张图中我们可以看到这个例子

实际上在reducer阶段

所有的单词都按照之前

partition函数要求的

按照了它们的Key的

这样一个顺序排好了序

然后输出到了分布式文件系统

好 刚刚我们说到了

我们可以进行搜索我们可以进行排序

那我们来看看我们还能做一些什么样的事情

第3个例子是一个叫做inverted index

就是倒排表这样一个过程

那么倒排表它是一个什么样的意思

我们通过例子来看

当我们的输入是文件名

和文本这样的一个记录的时候

我们要输出什么

我们输出的是这些文件的列表

那么文件的列表它具体

是什么样的文件列表

就是说它包含了某一个每个单词的文件列表

那么建立这样一张表有什么样的好处

当我们去看某一个单词的时候

我们就可以很直接的

查到哪些文件包含了这个单词

在某一些搜索的任务或者是某些排序任务

实际上它需要这样的一个倒排表的一个结构

那么我们来看看咱们MapReduce里面

我们要构建这样一个inverted index

到底是怎么做的

我们看map

map实际上它做了一个for循环

在for循环中它会去遍历

每一个输入的文件

它的文本的这个单词

我们可以看到text和speed

是它的每个单词

那么对于每个单词

我们输出的中间Key和中间结果

就是这个单词

和这个单词出现的这个文件名

word filename这样的一个记录

那我们看看在reduce里面

我们做了些什么事情

reduce我们做了一个输出

那么这个输出是单词

和文件名的这样一个排序

那么我们把文件名

排好让它把这个单词输出

那我们再来看看

在MapReduce之间的这个combine

我们做了一些什么事情

大家可以回想一下combine

实际上是在这个map之后

对中间结果进行一个优化处理

进行一个整理的一个过程

我们发现它是把一些重复的

文件名给去掉

也就是说留下唯一的

这些文件名的这样一个过程

那有了这样一个过程之后

实际上我们就可以生成

我们需要的这样一个倒排表

那么我们来看这两个文件

那么在最上面一行

给出了两个文件的文件名

那么在下面给出的是文件里面

它的这个数据也就是

它包含的单词

我们来看map之后

得到什么样的结果

map把每个单词给输出了出来

同时把它的这个文件名

对应的文件名给输出了出来

那么形成一个中间的key和中间的value

那么在这个map之后

我们进行了一个combine

我们把重复的单词和重复的

这样一个文件名给合并了一下

那么使得每个key

和每个这个中间的这个单词

和每个这个文件名

它都独立的出现唯一的出现

那么reduce阶段

我们做了一些什么事情

我们把这个单词给放到前面

而把它的这个文件名

进行了一个排序

那么要知道在reduce的阶段实际上

我们已经把相同的单词

对应的各种不一样的

这个文件名给汇聚到了一起

它只是做了一个文件名上的

一个按名称的排序

那么最终我们输出了右边的这样一个结果

那么在这样的一个结果的基础上

我们下一步可以做各种各样复杂的事情

比如说把某一个单词

对应的所有的文件的列表打印出来

那么就变成了一个可行的一个事情

那么下一个例子实际上

是一个最流行的单词的一个输出

这也是在自然语言处理

或者是数据挖掘里面

用到比较多的这样一个操作

我们来看它的一个要求是什么

输入文件名和文件的内容

和刚刚的那样一个例子是一致的

那么输出是把在这些文件

里面出现最多的

1000个单词给输出出来

大家可以想一想这个例子

实际上可能和你的科研上的很多任务

或者是工作中的很多任务

实际上是能够对应的上的

我们经常需要找出现最多的这些成员

这些元素是什么

这就是我们在这里面

需要去处理的一个任务

我们来看这个事情我们怎么做

那在这里面实际上

我们用到了一个这个模块化的

一个概念来做它

也就是说我们会有两个MapReduce的任务

来处理这样一件事情

我们来看第一个job我们是怎么去做的

第一个job实际上我们建立一张倒排表

那么我们说过倒排表

我们在刚刚已经可以通过一个

MapReduce任务一步来做到

那么倒排表就会给出单词和文件列表

那么第二个job我们会做一件事情

我们就是把单词

和这个文件列表把它直接在map阶段

变成了单词的数量和这个单词是什么

变成了count和word这样一个东西

那么在它的reduce里面

job 2的reduce里面

我们去做的一件事情

就是做我们刚刚做了这个排序

在reduce里面实际上我们什么都不做

对吧

我们依然使用partition

它本身具有的排序的功能

来对count进行排序

那么有了这样一步之后

我们就可以把前100个

最常出现的单词给输出出来

那这就是我们通过组合了

两个MapReduce的任务

来把一个相对比较复杂的任务给完成

但实际的工作当中

或者研究当中各位实际上

可以使用更加复杂的组合

比如说不是两个

而是5个甚至10个MapReduce

进行一个串联来达到

某一个数据处理的这样一个要求

但是现在我们回过头来看看这一个操作

我们是不是还有优化的一个空间

我们为什么一定要有

两个MapReduce的任务去做呢

如果我们用一个能不能做得到

那我们来看用一个去怎么做

那么当我们想一个MapReduce

来实现这样一个任务的时候

首先我们会在map阶段

不是去输出它的文件名

而是去输出word和1

有点像我们再作词频统计的例子里面

用到的这样一个方法

在reduce里面

我们统计这个文件的数量的时候

实际上我们现在就变成了

统计这个word对应的

这个出现的文件的次数

也就是做一个叠加

有了这个次数之后

实际上我们直接

就能够进行一个排序

然后使得它的输出变成了

我们想要的这样一个词频

然后这个词频最终可以作为

我们挑选前100个单词的依据

同时在这里面

我们还有一些其他的优化的一个操作

比如在我们的具体的例子中

我们想要挑选出现最多的100个单词

那么对于明显不可能是这些单词的这些数据

我们就可以在一个比较早期的阶段

比如说在reduce写入到HDFS阶段

把它从整个数据中扔掉

那么可以节省一定的数据写入的开销

那这是我们用MapReduce

来处理最流行单词的这样一个算法

它是怎么去操作的

那么在大家的实际的任务当中

可能会需要更加复杂的

一些这种基本单元

那么大家在后续的研究当中

或者学习当中可以去积累

这样的一些MapReduce典型的这种模块

并且通过对他们进行组合进行连接

然后来形成比较复杂的

这种数据处理的这样一个流程

那么讲完这一部分之后

实际上我们对MapReduce的

介绍就基本上告一段落

在后面的这个课程当中

我们会去进一步介绍MapReduce的

优化以及MapReduce它的不足

以及我们怎么样能够对MapReduce

进行一个补充和调整

以及在工业界中实际的进行应用