MapReduce:免费午餐还没结束?

微软著名的C++大师Herb Sutter在2005年初的时候曾经写过一篇重量级的文章:”The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software“,预言OO之后软件开发将要面临的又一次重大变革-并行计算。

摩尔定律统制下的软件开发时代有一个非常有意思的现象:”Andy giveth, and Bill taketh away.”。不管CPU的主频有多快,我们始终有办法来利用它,而我们也陶醉在机器升级带来的程序性能提高中。

我记着我大二的时候曾经做过一个五子棋的程序,当时的算法就是预先设计一些棋型(有优先级),然后扫描棋盘,对形势进行分析,看看当前走哪部对自己最重要。当然下棋还要堵别人,这就需要互换双方的棋型再计算。如果只算一步,很可能被狡猾的对手欺骗,所以为了多想几步,还需要递归和回朔。在当时的机器上,算3步就基本上需要3秒左右的时间了。后来大学毕业收拾东西的时候找到这个程序,试了一下,发现算10步需要的时间也基本上感觉不出来了。

不知道你是否有同样的经历,我们不知不觉的一直在享受着这样的免费午餐。可是,随着摩尔定律的提前终结,免费的午餐终究要还回去。虽然硬件设计师还在努力:Hyper Threading CPU(多出一套寄存器,相当于一个逻辑CPU)使得Pipeline尽可能满负荷,使多个Thread的操作有可能并行,使得多线程程序的性能有5%-15%的提升;增加Cache容量也使得包括Single-Thread和Multi-Thread程序都能受益。也许这些还能帮助你一段时间,但问题是,我们必须做出改变,面对这个即将到来的变革,你准备好了么?

Concurrency Programming != Multi-Thread Programming。很多人都会说MultiThreading谁不会,问题是,你是为什么使用/如何使用多线程的?我从前做过一个类似AcdSee一样的图像查看/处理程序,我通常用它来处理我的数码照片。我在里面用了大量的多线程,不过主要目的是在图像处理的时候不要Block住UI,所以将CPU Intensive的计算部分用后台线程进行处理。而并没有把对图像矩阵的运算并行分开。

我觉得Concurrency Programming真正的挑战在于Programming Model的改变,在程序员的脑子里面要对自己的程序怎样并行化有很清楚的认识,更重要的是,如何去实现(包括架构、容错、实时监控等等)这种并行化,如何去调试,如何去测试。

在Google,每天有海量的数据需要在有限的时间内进行处理(其实每个互联网公司都会碰到这样的问题),每个程序员都需要进行分布式的程序开发,这其中包括如何分布、调度、监控以及容错等等。Google的MapReduce正是把分布式的业务逻辑从这些复杂的细节中抽象出来,使得没有或者很少并行开发经验的程序员也能进行并行应用程序的开发。

MapReduce中最重要的两个词就是Map(映射)和Reduce(规约)。初看Map/Reduce这两个词,熟悉Function Language的人一定感觉很熟悉。FP把这样的函数称为”higher order function”(”High order function”被成为Function Programming的利器之一哦),也就是说,这些函数是编写来被与其它函数相结合(或者说被其它函数调用的)。如果说硬要比的化,可以把它想象成C里面的CallBack函数,或者STL里面的Functor。比如你要对一个STL的容器进行查找,需要制定每两个元素相比较的Functor(Comparator),这个Comparator在遍历容器的时候就会被调用。

拿前面说过图像处理程序来举例,其实大多数的图像处理操作都是对图像矩阵进行某种运算。这里的运算通常有两种,一种是映射,一种是规约。拿两种效果来说,”老照片”效果通常是强化照片的G/B值,然后对每个象素加一些随机的偏移,这些操作在二维矩阵上的每一个元素都是独立的,是Map操作。而”雕刻”效果需要提取图像边缘,就需要元素之间的运算了,是一种Reduce操作。再举个简单的例子,一个一维矩阵(数组)[0,1,2,3,4]可以映射为[0,2,3,6,8](乘2),也可以映射为[1,2,3,4,5](加1)。它可以规约为0(元素求积)也可以规约为10(元素求和)。

面对复杂问题,古人教导我们要“分而治之”,英文中对应的词是”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一贯的风格,化繁为简,返璞归真。

接下来就放下其它,研究一下Map/Reduce操作。(其它比如容错、备份任务也有很经典的经验和实现,论文里面都有详述)

Map的定义:

Map, written by the user, takes an input pair and produces a set of intermediate key/value pairs. The MapReduce library groups together all intermediate values associated with the same intermediate key I and passes them to the Reduce function.

Reduce的定义:

The Reduce function, also written by the user, accepts an intermediate key I and a set of values for that key. It merges together these values to form a possibly smaller set of values. Typically just zero or one output value is produced per Reduce invocation. The intermediate values are supplied to the user’s reduce function via an iterator. This allows us to handle lists of values that are too large to fit in memory.

MapReduce论文中给出了这样一个例子:在一个文档集合中统计每个单词出现的次数。

Map操作的输入是每一篇文档,将输入文档中每一个单词的出现输出到中间文件中去。

map(String key, String value):
    // key: document name
    // value: document contents
    for each word w in value:
        EmitIntermediate(w, “1″);

比如我们有两篇文档,内容分别是

A - “I love programming”

B - “I am a blogger, you are also a blogger”。

B文档经过Map运算后输出的中间文件将会是:

I,1 am,1 a,1 blogger,1 you,1 are,1 a,1 blogger,1

Reduce操作的输入是单词和出现次数的序列。用上面的例子来说,就是 (”I”, [1, 1]), (”love”, [1]), (”programming”, [1]), (”am”, [1]), (”a”, [1,1]) 等。然后根据每个单词,算出总的出现次数。

reduce(String key, Iterator values):
    // key: a word
    // values: a list of counts
    int result = 0;
    for each v in values:
        result += ParseInt(v);
    Emit(AsString(result));

最后输出的最终结果就会是:(”I”, 2″), (”a”, 2″)……

实际的执行顺序是:

MapReduce Library将Input分成M份。这里的Input Splitter也可以是多台机器并行Split。 Master将M份Job分给Idle状态的M个worker来处理; 对于输入中的每一个<key, value> pair 进行Map操作,将中间结果Buffer在Memory里; 定期的(或者根据内存状态),将Buffer中的中间信息Dump到本地磁盘上,并且把文件信息传回给Master(Master需要把这些信息发送给Reduce worker)。这里最重要的一点是,在写磁盘的时候,需要将中间文件做Partition(比如R个)。拿上面的例子来举例,如果把所有的信息存到一个文件,Reduce worker又会变成瓶颈。我们只需要保证相同Key能出现在同一个Partition里面就可以把这个问题分解。 R个Reduce worker开始工作,从不同的Map worker的Partition那里拿到数据(read the buffered data from the local disks of the map workers),用key进行排序(如果内存中放不下需要用到外部排序 - external sort)。很显然,排序(或者说Group)是Reduce函数之前必须做的一步。 这里面很关键的是,每个Reduce worker会去从很多Map worker那里拿到X(0<X<R) Partition的中间结果,这样,所有属于这个Key的信息已经都在这个worker上了。 Reduce worker遍历中间数据,对每一个唯一Key,执行Reduce函数(参数是这个key以及相对应的一系列Value)。 执行完毕后,唤醒用户程序,返回结果(最后应该有R份Output,每个Reduce Worker一个)。

可见,这里的分(Divide)体现在两步,分别是将输入分成M份,以及将Map的中间结果分成R份。将输入分开通常很简单,Map的中间结果通常用”hash(key) mod R”这个结果作为标准,保证相同的Key出现在同一个Partition里面。当然,使用者也可以指定自己的Partition Function,比如,对于Url Key,如果希望同一个Host的URL出现在同一个Partition,可以用”hash(Hostname(urlkey)) mod R”作为Partition Function。

对于上面的例子来说,每个文档中都可能会出现成千上万的 (”the”, 1)这样的中间结果,琐碎的中间文件必然导致传输上的损失。因此,MapReduce还支持用户提供Combiner Function。这个函数通常与Reduce Function有相同的实现,不同点在于Reduce函数的输出是最终结果,而Combiner函数的输出是Reduce函数的某一个输入的中间文件。

Tom White给出了Nutch[2]中另一个很直观的例子,分布式Grep。我一直觉得,Pipe中的很多操作,比如More、Grep、Cat都类似于一种Map操作,而Sort、Uniq、wc等都相当于某种Reduce操作。

加上前两天Google刚刚发布的BigTable论文,现在Google有了自己的集群 - Googel Cluster,分布式文件系统 - GFS,分布式计算环境 - MapReduce,分布式结构化存储 - BigTable,再加上Lock Service。我真的能感觉的到Google著名的免费晚餐之外的对于程序员的另一种免费的晚餐,那个由大量的commodity PC组成的large clusters。我觉得这些才真正是Google的核心价值所在。

呵呵,就像微软老兵Joel Spolsky(你应该看过他的”Joel on Software”吧?)曾经说过,对于微软来说最可怕的是[1],微软还在苦苦追赶Google来完善Search功能的时候,Google已经在部署下一代的超级计算机了。

The very fact that Google invented MapReduce, and Microsoft didn’t, says something about why Microsoft is still playing catch up trying to get basic search features to work, while Google has moved on to the next problem: building Skynet^H^H^H^H^H^H the world’s largest massively parallel supercomputer. I don’t think Microsoft completely understands just how far behind they are on that wave.

注1:其实,微软也有自己的方案 - DryAd。问题是,大公司里,要想重新部署这样一个底层的InfraStructure,无论是技术的原因,还是政治的原因,将是如何的难。

注2:Lucene之父Doug Cutting的又一力作,Project Hadoop - 由Hadoop分布式文件系统和一个Map/Reduce的实现组成,Lucene/Nutch的成产线也够齐全的了

时间: 2024-07-29 05:28:51

MapReduce:免费午餐还没结束?的相关文章

《战锤OL》韩服夭折还没公测就宣布结束服务

继台版<战锤Online>在今(2010)年6 月结束服务后,韩国NHN 公司9月7日也在游戏官网发出沉痛公告,宣布韩版<战锤Online>将在本月底结束服务.<战锤Online>在韩国甚至连公测都还没开始就被放弃了. 战锤OL 为了成功推动韩版<战锤Online>,NHN 甚至在游戏上市前先帮角色变脸 <战锤Online>韩版代理商 NHN 是在当地时间今日下午两点与 EA 共同在官网发表这项消息.NHN 指出,过去为了<战锤Online

iostream-为什么我这个c++程序运行后直接关掉了窗口,就是应该运行出来了,但是还没来得及看结果就被自动关了

问题描述 为什么我这个c++程序运行后直接关掉了窗口,就是应该运行出来了,但是还没来得及看结果就被自动关了 程序代码如下: #include "stdafx.h" #include #include using namespace std; int _tmain(int argc, _TCHAR* argv[]) { double daphne = 100.0; double cleo = 100.0; const double rate_1 = 0.1; const double r

友盟也进来玩一下的话,似乎这个领域的变量还没被终结

现在的第三方推送无疑是个推独大,据说已经砍下90%的市场,但如果友盟也进来玩一下的话,似乎这个领域的变量还没被终结. 早在去年6.7月间,友盟就开始筹划推送产品,去年10月对外发布后进入内测状态.而现在友盟方面向我们表示,该产品已结束灰度测试,正式面向所有友盟账号使用者开放.如果我们留意一下,会看到友盟在各大站点投放的广告已经上线,而友盟主页的消息推送入口已经可用.继个推月初发布带有用户分析能力的2.0版本后,友盟也全面杀入这个市场.这意味着,第三方推送已经由此前的广撒网式推送,正式进入基于用户

分析下这个错误,谢谢,300分了,还没见到答案,thx

问题描述 发生未处理的异常,并已终止进程.ApplicationID:/LM/W3SVC/1/ROOTProcessID:3928Exception:System.ComponentModel.Win32ExceptionMessage:系统找不到指定的文件.StackTrace:在System.Diagnostics.Process.StartWithCreateProcess(ProcessStartInfostartInfo)在System.Diagnostics.Process.Star

java-Ext.ux.IFrame页面还没加载完loadMask已经结束了这是为什么

问题描述 Ext.ux.IFrame页面还没加载完loadMask已经结束了这是为什么 如题,loadMask结束时页面并没有加载完成,还会有一段空白时间,请问怎么设置让loadMask在页面加载完才消失 解决方案 http://www.fengfly.com/plus/view-213235-1.html 解决方案二: iframe加载的内容是不是ajax动态加载的?如果是不好控制,因为一般是window.onload后mask就会隐藏,ajax异步加载不算在onload里面的,自己看下有没有

百度文库改版 网络免费午餐还能吃多久

中介交易 SEO诊断 淘宝客 云主机 技术大厅 一直以来互联网都被网络版权问题困扰着,尤其的百度更是被版权问题牢牢牵制着.最近美国有传来百度的好消息,百度今年7月与环球音乐集团.华纳音乐集团和索尼达成协议,同意向一个社交音乐平台上版权内容的所有人支付版税,这一举动成为百度洗清黑名的最有效证据.受此消息利好,周二百度股价大涨6.24%,报收于118.4美元. 再来看看困扰着百度的另一个与网络版权有关的问题.近日百度文库全新改版页面正式上线,改版后,文学类作品从百度文库中分离出来,"变身"

2010夏季达沃斯论坛热议房价房地产调控还没有结束

房价几乎成了一个"永恒"的热门话题,在昨日召开的2010夏季达沃斯论坛上同样热议.而无论是作为专家的财政部财政科学研究所所长贾康,还是地产业界大佬首创置业董事长刘晓光,都异口同声地表示:"房地产调控还没有结束." 本报记者 徐可奇 财政部财政科学研究所所长 贾康 高端豪宅价格抗跌 "此轮房地产调控还没有结束."财政部财政科学研究所所长贾康昨日率先在2010夏季达沃斯论坛上表示,虽然上海房价在高端的豪宅价格影响下,近期出现反弹并且创出了调控以来的新

供暖改造钱交了 热网咋还没入户

去年供暖期前,位于沈阳市泉园三路67号的新世纪家园小区部分业主,按每平方米120元的价格交了供暖改造费.此前该小区采用煤气分户供暖,改造后将接入热网供热. 没想到的是,至今热网也没入户.交了钱的业主坐不住了,一些心急的业主今夏已将自家的煤气供热设备拆除,今冬可咋取暖? 嫌煤气取暖贵 居民想改热网 昨日,有沈阳新世纪家园业主拨打本报热线称,去年供暖期前交了热网改造费,可今年眼看都要进入供暖期了,热网却还没入户. "我们小区设计就是煤气分户供暖,可煤气1立方米3块3,成本太高. "她说,不

安卓开发中某一个界面还没等你操作呢 自己就没了 哪里出问题了?

问题描述 安卓开发中某一个界面还没等你操作呢 自己就没了 哪里出问题了? 问题如上 好困惑! 解决方案 自己就没了,是返回上一级页面么?还是什么?有可能是AndroidManifest.xml文件里activity配置的问题.. 解决方案二: 出现fatal crash了把,抓下log看看. 解决方案三: 贴出代码,贴出log,才好分析,这样描述太抽象 解决方案四: 看一下log日志,看看错误信息. 解决方案五: 这个问题问的有点抽象能不能再具体些