存档

文章标签 ‘mapreduce’

Mapreduce简介

2011年4月21日 sigma 6 条评论 10,034 views

今天在Opps里和grapeot,Ouyang等人扯到了mapreduce,感觉这东西还是挺有意思的,并且和分布式系统等体系结构领域有关,我于是花了点时间去看了下(主要是看wiki以及google员工在MIT讲课的课件),在这里对mapreduce做个简要介绍。

Mapreduce是google提出的一种编程模型,该模型最早在OSDI(一个操作系统领域顶级会议) 2004上提出。其主要是用于大规模数据并行处理(如排序,索引),不过现在貌似机器学习(machine learning,ML)上用的也挺多的。其主要有两个步骤,一个是Map(可译为分发,映射),一个是reduce(可译为化简,回收,合并等),这两个概念都是从函数式语言借来的。Map和reduce的两个步骤主要工作如下:

"Map" step: The master node takes the input, partitions it up into smaller sub-problems, and distributes those to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes that smaller problem, and passes the answer back to its master node.

Map阶段主要是主节点把输入划分成一些子问题,并且分发给工作节点。而工作节点有可能继续重复这一工作,直到划分够细,子问题能在规定的时间内有一个工作节点完成为止,形成一个树状结构。下一层的工作节点会将完成的计算结果传输给上一层的(主)节点。

"Reduce" step: The master node then takes the answers to all the sub-problems and combines them in some way to get the output — the answer to the problem it was originally trying to solve.

Reduce阶段把所有的问题,所有的答案按一定的方式组合化简归并,最终形成最初问题的答案并输出。

在这两个阶段中,Map阶段分配后的并行度是很高的,因此很适合一些数据处理的应用,比如说对大量网页文件进行建立索引,因为这时候可以直接把数以亿计的网页直接按数G分给各个工作节点处理(貌似google一般是以64M为单位的)。而reduce阶段的并行度相对不高,但是由于可以层层的reduce,并行度其实也很可观。

为了提高可靠性,每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔,主节点(类同Google File System中的主服务器)记录下这个节点状态为死亡,并把分配给这个节点的数据发到别的节点。

另外,可以看出,其实这个并行模型和分治法非常像,基本思想几乎一致,感觉是一个基本思想(分治)在大规模数据处理中的一个应用和具体化。

也许也正因为这个原因,mapreduce从技术上没有任何先进之处,感觉其火起来很大一部分是由于云计算泡沫的原因,因此一些传统的数据库领域的人甚至认为其是一种倒退,因为:

  1. 在大规模的数据密集应用的编程领域,它是一个巨大的倒退
  2. 它是一个非最优的实现,使用了蛮力而非索引
  3. 它一点也不新颖——代表了一种25年前已经开发得非常完善的技术
  4. 它缺乏当前DBMS基本都拥有的大多数特性
  5. 它和DBMS用户已经依赖的所有工具都不兼容  

顺便说件大傻帽grapeot碰到的傻帽事:

    求一个图的连通片个数,7M个节点70M条边,在Amazon Elastic EC2上开了16个small instance跑了4个半小时就跑完了。然后我写了个串行的版本,在自己的笔记本上跑。。。90秒。。

    这件事说明,任何事物都具有适用性,反过来说,任何事物都有存在的理由。想用万能的通用结构或者模型高效解决任何问题是不可能的,因此,多样性结构是高效的必要条件,因为应用是多样的。

不过,相对与传统的牛叉的各种数据库技术,mapreduce能活的这么好,主要原因是:传统的数据库太难用了,传统的并行编程模型也太难用了,而mapreduce简单,因此简单的,易用的往往是最好的,这也是windows能够打败linux的原因之一。而历史上,野蛮的蒙古人就用简单的暴力几乎整个地球上所谓的文明人!

最后,附一张来自google在MIT的课件上的图,来形象的描述mapreduce:

mapreduce示意图

参考:

维基:http://en.wikipedia.org/wiki/MapReduce

google lab:http://labs.google.com/papers/mapreduce.html

MIT MapReduce course:http://sites.google.com/site/mriap2008/home

另附:MapReduce: 一个巨大的倒退的链接(点前面标题)

无觅相关文章插件,快速提升流量