MapReuduce编程模型（主讲人：吴威）在线视频

我们来看一个比较经典的

分布式编程模型MapReduce

首先需要解释的是

这个模型的输入数据

也就是编程处理的格式

可以是关系型数据

也可以是其它格式的数据

MapReduce对输入格式的

要求比较灵活

在本系列课程前面的

分布式调度课程上

老师已经给你们介绍过

MapReduce的基本概念

在这里

我会着重从编程语言的角度

来阐述这个新的模型

其实MapReduce的编程思想

来自于函数式编程

对于函数式编程

我一会儿还会再介绍一下

所谓MapReduce其实是

函数式编程里的两个函数

分别是Map和Reduce

它们组合在一起

这个模型就叫做MapReduce

所谓Map函数

就是将一个key-value队

映射到一组新的key-value队

可以是一对一的映射

也可以是一对多的映射

甚至是一对零的映射

比如将一个单词转换成

全部大写的格式

就是一对一的映射

比如将一句英文句子

转换为一个个英文单词

就是一对多的映射

还有我们可以用Map函数

做过滤操作

过滤条件是在一行句子里

如果出现了特定的单词

则输出这个句子

如果没有出现这个单词

则什么都不做 直接返回

后一种情况就是

一对零的映射

而所谓的Reduce函数

是将同一个key

以及它对应的一组value

映射到一组新的key和value

比如想计算知道

某位同学的考试总分

用Reduce函数来说

输入的key是学生的学号

value列表是各门课程的分数

比如物理 化学 数学

等课程的分数

Reduce的输出就是

学号和总分的key-value队

在Reduce函数里

需要将各门课程的分数加起来

大家看这两个函数接口

还是比较简单的

所以MapReduce模型

至少满足了接口简单这一需求

说起MapReduce

肯定绕不过函数式编程

所以我们先来了解一下

什么是函数式编程

它有如下特点

在面向对象语言里

万物皆对象

所以class是一等公民

但是函数式编程语言里

函数才是一等公民

而且

这里的函数是比较纯粹的函数

比如

每个函数都需要有输入和输出

而且函数的输出值

依赖于输入的参数

不依赖于外部变量或者状态

而函数的返回

新的输出值

并不会改变外边的状态

也就是说

程序在任意时刻执行的一个函数

如果输入是固定的

那么输出也是固定的

这个特性非常重要

比如当程序发生异常时

需要重新启动执行

如果函数调用的结果是一致的

那第二次执行的结果

也是固定的

这个特性对程序做容错处理

非常有用

在函数式编程语言里

还有高阶函数的概念

高阶函数可以将一个

或多个函数作为输入

或者它的输出是另外一个函数

在MapReduce编程模型里

Map和Reduce都是来自

函数式编程语言里的高阶函数

它们的输入

是另外一个

做数据变换的函数

我这里就不列举那些

更加有名的函数式编程语言

比如LISP Haskell等

我们来看更加常见的语言

比如C++

在C++标准模板库里

可以看到一个类似于Map的方法

比如for_each就是一个高阶函数

它的输入参数

包括一个列表的起始位置

和终止位置

还包括一个叫incr的函数

incr函数把每一个输入的值

加上1之后返回

所以这句代码的最终结果

是把列表中

所有的数字都加上了1

我们再看一个Python的例子

首先定义了一个upper函数

它把输入的字符串

转换为全大写的字符串

另外

可以使用一个Map函数

这里的Map也是一个高阶函数

输入同样是列表

和另外一个函数

就是upper函数

这个语句的结果

就是把列表中所有的单词

都转换成全部大写的

以上两个例子都非常简单

但用几句简单的代码

实现了其他编程方法

比较复杂的操作

这就是函数式编程的优势

我们回到MapReduce编程模型

这里介绍一个

最有名的MapReduce程序

wordcount

每个学分布式编程的人

都绕不过这个程序

它就相当于

分布式编程界的HelloWorld程序

当然比HelloWorld要复杂很多

大家需要认真研究

和体会这个程序

当你读懂这个程序时

MapReduce的基本原理

也了解的差不多了

首先来看看Map

和Reduce的函数是怎么写的

这里的代码以

Hadoop MapReduce为例

Map函数有四个参数

除了最核心的Key和Value

两个参数外

还有专门用来

搜集输出结果的output参数

还有一个阻住（05:51）参数Reporter

用来记录程序的进度

或者其他信息

这里的key和value的数据类型

是可以自己定义的

比如这里输入的value

是text类型

每一个value是一行文本数据

输入的key在wordcount中

没有什么意义

我们直接忽略它

我们首先把value转换成字符串

然后再把String

用tokenizer的方法

切分成单词

然后用一个while循环

把单词及数字1

作为key和value输出

数据1的意思是

单词在这个行里只出现过一次

再来看Reduce函数

同样是四个参数

输入的key是刚才map输出的key

输入的value列表是用迭代器

这里的Iterator来表示

Reduce的输入参数

表示一个key对应了多个value

编程框架已经帮我们聚合好了

编程人员不要知道

聚合是怎么发生的

函数内部的逻辑比较简单

依次读入value的值

并把它们加起来

得到一个总数

最后把原始的key

和计算得到的总数

作为value输出

这里的动画展示了用MapReduce

实现的WordCount程序

内部运行原理

大家可以照着动画进行理解

在分布式编程的领域里

MapReduce有非常好的功能

和特点

为我们解决底层系统的复杂度

我们来看它是怎么解决的

首先是并发性

整个MapReduce程序

可以多线程

或者多进程并发执行

并且需要跨多台机器

MapReduce框架

帮我们把数据做了自动切分

切分基本上是根据数据量来做的

可以很好地做到负载均衡

Map任务依赖于输入数据

Reduce任务只依赖于

前面的Map任务的输出

各个任务之间相互没有影响

所以任何一个Map

或者Reduce函数

都可以独立运行

然后是容错性

因为分布式文件系统的数据

都有副本

一台机器的问题

只影响部分任务的执行

而不影响任务输入数据的完整性

所以每个任务都可以重新启动

并且根据函数式编程的特点

重新计算任务并不影响结果

另外

MapReduce框架的master结点

可以监控到任务的失败

自动帮我们在另外的机器上

重新运行失败的任务

在分布式领域有一句话

移动计算比移动数据更划算

说的就是数据本地化的事情

利用之前课程中提到的

伏羲的调度功能

MapReduce框架把任务启动到

输入数据所在的机器上

帮我们解决了这个问题

MapReduce模型的应用场景

也非常广泛

比如

可以用在网站日志分析

和流量统计上

从传统的web服务器

比如Apache的日志分析

到广告日志点击

和搜索日志的分析

再到更深层次的访问来源分析

广告点击消耗的实时计费等

还有其他商业性的数据分析

比如

各类商品的成交量统计

销售额占比分析等等

除了做简单的分析

MapReduce模型

还被用在做机器学习

和数据挖掘上

比如 关联推荐算法

协同过滤算法等等

有兴趣的同学可以自行搜索

相关的内容

当然

MapReduce最早的应用

其实是Google内部

构建网络索引用的

所以在分布式索引的构建上

MapReduce也是一把利器

刚才大家看到了

传统的MapReduce任务

一般是很规整的

Map加Reduce的形式

如果你的分析程序

或者算法比较复杂

那可能需要多道

MapReduce程序

也就是Map加Reduce

接着Map加Reduce
再接着Map加Reduce

如果用户想突破这个限制

比如

他们想让多个Map连接在一起

或者Reduce后面还有Reduce

做起来还是比较复杂的

我们在开源软件Hadoop里

可以找到Train the map

和Train the reduce的两个类

帮助用户考虑了这个问题

但是因为Hadoop

MapReduce框架的限制

Train the Map

只能在一个Map后面

再跟另外一个Map

或者在Reduce的前面

加上一个或者多个Map

而做不到

Reduce后面直接跟一个Reduce

但是ODPS的MapReduce框架

可以做到多个Reduce运算符

串联的操作

这和ODPS MapReduce底层

伏羲的DAG调度模型有关

有兴趣的同学可以思考一下

如何来实现这个功能