Fighting bird分享 http://blog.sciencenet.cn/u/tonia

博文

MapReduce

已有 3848 次阅读 2010-5-6 16:21 |系统分类:科研笔记|关键词:parallel,,model| parallel, model

源于Google的并行编程模式。简而言之,就是任务的分解约结果的汇总,这是一种Simplified的哲学。

"面对复杂问题,古人教导我们要“之”,”Divide and Conquer“。Map/Reduce其实就是Divide/Conquer的过程,通过把问题 Divide,使这些Divide后的Map运算高度并行,再将Map后的结果Reduce(根据某一个Key),得到最终的结果。

Googler发现这是问题的核心,其它都是共性问题。因此,他们把MapReduce抽象分离出来。这样,Google的程序员可以只关心应用逻辑,关心根据哪些Key把问题进行分解,哪些操作是Map操作,哪些操作是Reduce操作。其它并行计算中的复杂问题诸如分布、工作调度、容错、机器间通信都交给Map/Reduce Framework去做,很大程度上简化了整个编程模型。

MapReduce的另一个特点是,Map和Reduce的输入和输出都是中间临时文件(MapReduce利 用Google文件系统来管理和访问这些文件),而不是不同进程间或者不同机器间的其它通信方式。我觉得,这是Google一贯的风格,化繁为简,返璞归 真。"

-- 引自 http://www.mengyan.org/blog/archives/2006/11/15/138.html


MapReduce 由两个核心操作组成:

1. Map

Map是把一组数据一对一的映射为另外的一组数据,其映射的规则由一个函数来指定,比如对[1, 2, 3, 4]进行乘2的映射就变成了[2, 4, 6, 8]。
Map操作是独立的对每个元素进行操作,将产生一组全新的数据,而原来的数据保持不变。因此,它是高度并行的。

2. Reduce

Reduce是对一组数据进行归约,这个归约的规则由一个函数指定,比如对[1, 2, 3, 4]进行求和的归约得到结果是10,而对它进行求积的归约结果是24。
Reduce操作虽然不如Map操作并行性那么好,但是它总会得到一 个相对简单的结果,大规模运算也相对独立,因此也是比较适合并行的。

无论是Map还是Reduce都是以另外的函数为参数,在 FP(Functional Programming)中,这样的函数被称为高阶函数(high-order function)。正是因为它们可以同其它函数相结合,所以,我们只要把Map和Reduce这两个高阶函数进行并行化处理,这样便形成了一个以Map和Reduce为基础的框架,具体应用相关代码写在用户代码中,之后与MapReduce结合获得并行处理的能 力。当然,这么做的前提是按照这个框架的要求,把计算归结为Map和Reduce操作。

为什么是Map和Reduce?

在 Map过程中,我们将数据并行,也就是将数据分开,而Reduce则把分开的数据合到了一起,换句话说,Map是一个分的过程,Reduce则对应着合, 这一分一合便在不知不觉中完成了计算。
所以,站在计算的两端来看,与我们通常熟悉的串行计算没有任何差别,所有的复杂性都在中间隐藏了。所有这些并行化能力的获得都与FP有着密不可分的关系。

关于FP:

因为函数式编程的每一个符号都是 final 的,没有函数产生过副作用。因为从未在某个地方修改过值,也没有函数修改过在其作用域之外的量并被其他函数使用(如类成员或全局变量)。这意味着函数求值 的结果只是其返回值,而惟一影响其返回值的就是函数的参数。只需在意其参数,而不必考虑函数调用顺序,不用谨慎地设置外部状态。

函数式程序无需任何修改即可并行执行。不用担心死锁和临界区,因为你从未用锁!函数式程序里没有任何数据被同一线程修改两次,更不用说两个不同的线程了。 这意味着可以不假思索地简单增加线程而不会引发折磨着并行应用程序的传统问题。

即使你的程序本身就是单线程的,那么函数式程序的编译器仍然可以优化它使其运行于多个CPU上。

函数式编程 vs 命令式编程

1. 函数式编程的基本特点是:

丰富的数据类型;

函数是运算元;

在函数内保存数据;

支持闭包和高阶函数(高阶函数能用另一个函数(间接地,用一个表达式) 作为其输入参数,在某些情况下,他甚至返回一个函数作为其输出参数。);

支持懒惰计算(lazy evaluation);

使用递归作为控制流程的机制;

加强了引用透明性;

函数内的运算对函数外无副作用。

函数式编程只描述在程序输入上执行的操作,不必使用临时变量保存中间结果。重点是捕捉"是什么以及为什么",而不是"如何做"。与将重点放在执行连 续命令上的过程性编程相比,函数式编程的重点是函数的定义而不是状态机(State Machine)的实现。是一种强调表达式的计算而非命令的执行的一种编程风格。表达式是用函数结合基本值构成的,它类似于用参数调用函数(函数式的优美 的说明可见《Functional Programming For The Rest of Us》)。

2. 命令式编程

命令式编程是一种用程式状态描述计算的方法。使用这种范型的编程人员用语句改动程式状态。
函数式编程是一种强调表达式的计算而非命令的执行的一种编程风格。表达式是用函数结合基本值构成的,类似于用参数调用函数。  
也就是说,函数式编程主要是函数调用,而不是其他的程式语句。 而命令式编程,是通过程式语句的执行运行的。程式语句的执行,会改动程式中保存的状态。

http://blog.sciencenet.cn/blog-425672-320608.html

上一篇:动态数据挖掘
下一篇:云计算概念解析

0

发表评论 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2020-1-20 23:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部