摘要

MapReduce是一个编程模型,和处理,产生大数据集的相关实现.用户指定一个map函数处理一个key/value对,从而产生中间的key/value对集.然后再指定一个reduce函数合并所有的具有相同中间key的中间value.下面将列举许多可以用这个模型来表示的现实世界的工作.

以这种方式写的程序能自动的在大规模的普通机器上实现并行化.这个运行时系统关心这些细节:分割输入数据,在机群上的调度,机器的错误处理,管理机器之间必要的通信.这样就可以让那些没有并行分布式处理系统经验的程序员利用大量分布式系统的资源.

我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的机群上,一个典型的MapReduce计算处理几千台机器上的以TB计算的数据.程序员发现这个系统非常好用:已经实现了数以百计的MapReduce程序,每天在Google的机群上都有1000多个MapReduce程序在执行.

1.介绍

在过去的5年里,作者和Google的许多人已经实现了数以百计的为专门目的而写的计算来处理大量的原始数据,比如,爬行的文档,Web请求日志,等等.为了计算各种类型的派生数据,比如,倒排索引,Web文档的图结构的各种表示,每个主机上爬行的页面数量的概要,每天被请求数量最多的集合,等等.很多这样的计算在概念上很容易理解.然而,输入的数据量很大,并且只有计算被分布在成百上千的机器上才能在可以接受的时间内完成.怎样并行计算,分发数据,处理错误,所有这些问题综合在一起,使得原本很简介的计算,因为要大量的复杂代码来处理这些问题,而变得让人难以处理.
作为对这个复杂性的回应,我们设计一个新的抽象模型,它让我们表示我们将要执行的简单计算,而隐藏并行化,容错,数据分布,负载均衡的那些杂乱的细节,在一个库里.我们的抽象模型的灵感来自Lisp和许多其他函数语言的map和reduce的原始表示.我们认识到我们的许多计算都包含这样的操作:在我们输入数据的逻辑记录上应用map操作,来计算出一个中间key/value对集,在所有具有相同key的value上应用reduce操作,来适当的合并派生的数据.功能模型的使用,再结合用户指定的map和reduce操作,让我们可以非常容易的实现大规模并行化计算,和使用再次执行作为初级机制来实现容错.
这个工作的主要贡献是通过简单有力的接口来实现自动的并行化和大规模分布式计算,结合这个接口的实现来在大量普通的PC机上实现高性能计算.
第二部分描述基本的编程模型,并且给一些例子.第三部分描述符合我们的基于集群的计算环境的MapReduce的接口的实现.第四部分描述我们觉得编程模型中一些有用的技巧.第五部分对于各种不同的任务,测量我们实现的性能.第六部分探究在Google内部使用MapReduce作为基础来重写我们的索引系统产品.第七部分讨论相关的,和未来的工作.

2.编程模型

计算利用一个输入key/value对集,来产生一个输出key/value对集.MapReduce库的用户用两个函数表达这个计算:map和reduce.
用户自定义的map函数,接受一个输入对,然后产生一个中间key/value对集.MapReduce库把所有具有相同中间key I的中间value聚合在一起,然后把它们传递给reduce函数.
用户自定义的reduce函数,接受一个中间key I和相关的一个value集.它合并这些value,形成一个比较小的value集.一般的,每次reduce调用只产生0或1个输出value.通过一个迭代器把中间value提供给用户自定义的reduce函数.这样可以使我们根据内存来控制value列表的大小.

2.1 实例

考虑这个问题:计算在一个大的文档集合中每个词出现的次数.用户将写和下面类似的伪代码:
map(String key,String value):
//key:文档的名字
//value:文档的内容
for each word w in value:
    EmitIntermediate(w,"1");

reduce(String key,Iterator values):
//key:一个词
//values:一个计数列表
int result=0;
for each v in values:
   result+=ParseInt(v);
Emit(AsString(resut));
map函数产生每个词和这个词的出现次数(在这个简单的例子里就是1).reduce函数把产生的每一个特定的词的计数加在一起.
另外,用户用输入输出文件的名字和可选的调节参数来填充一个mapreduce规范对象.用户然后调用MapReduce函数,并把规范对象传递给它.用户的代码和MapReduce库链接在一起(用C++实现).附录A包含这个实例的全部文本.

2.2类型

即使前面的伪代码写成了字符串输入和输出的term格式,但是概念上用户写的map和reduce函数有关联的类型:
map(k1,v1) ->list(k2,v2)
reduce(k2,list(v2)) ->list(v2)
例如,输入的key,value和输出的key,value的域不同.此外,中间key,value和输出key,values的域相同.
我们的C++实现传递字符串来和用户自定义的函数交互,并把它留给用户的代码,来在字符串和适当的类型间进行转换.

2.3更多实例

这里有一些让人感兴趣的简单程序,可以容易的用MapReduce计算来表示.
分布式的Grep(UNIX工具程序, 可做文件内的字符串查找):如果输入行匹配给定的样式,map函数就输出这一行.reduce函数就是把中间数据复制到输出.
计算URL访问频率:map函数处理web页面请求的记录,输出(URL,1).reduce函数把相同URL的value都加起来,产生一个(URL,记录总数)的对.
倒转网络链接图:map函数为每个链接输出(目标,源)对,一个URL叫做目标,包含这个URL的页面叫做源.reduce函数根据给定的相关目标URLs连接所有的源URLs形成一个列表,产生(目标,源列表)对.
每个主机的术语向量:一个术语向量用一个(词,频率)列表来概述出现在一个文档或一个文档集中的最重要的一些词.map函数为每一个输入文档产生一个(主机名,术语向量)对(主机名来自文档的URL).reduce函数接收给定主机的所有文档的术语向量.它把这些术语向量加在一起,丢弃低频的术语,然后产生一个最终的(主机名,术语向量)对.
倒排索引:map函数分析每个文档,然后产生一个(词,文档号)对的序列.reduce函数接受一个给定词的所有对,排序相应的文档IDs,并且产生一个(词,文档ID列表)对.所有的输出对集形成一个简单的倒排索引.它可以简单的增加跟踪词位置的计算.
分布式排序:map函数从每个记录提取key,并且产生一个(key,record)对.reduce函数不改变任何的对.这个计算依赖分割工具(在4.1描述)和排序属性(在4.2描述).

3实现

MapReduce接口可能有许多不同的实现.根据环境进行正确的选择.例如,一个实现对一个共享内存较小的机器是合适的,另外的适合一个大NUMA的多处理器的机器,而有的适合一个更大的网络机器的集合.
这部分描述一个在Google广泛使用的计算环境的实现:用交换机连接的普通PC机的大机群.我们的环境是:
1.Linux操作系统,双处理器,2-4GB内存的机器.
2.普通的网络硬件,每个机器的带宽或者是百兆或者千兆,但是平均小于全部带宽的一半.
3.因为一个机群包含成百上千的机器,所有机器会经常出现问题.
4.存储用直接连到每个机器上的廉价IDE硬盘.一个从内部文件系统发展起来的分布式文件系统被用来管理存储在这些磁盘上的数据.文件系统用复制的方式在不可靠的硬件上来保证可靠性和有效性.
5.用户提交工作给调度系统.每个工作包含一个任务集,每个工作被调度者映射到机群中一个可用的机器集上.

3.1执行预览

通过自动分割输入数据成一个有M个split的集,map调用被分布到多台机器上.输入的split能够在不同的机器上被并行处理.通过用分割函数分割中间key,来形成R个片(例如,hash(key) mod R),reduce调用被分布到多台机器上.分割数量(R)和分割函数由用户来指定.
图1显示了我们实现的MapReduce操作的全部流程.当用户的程序调用MapReduce的函数的时候,将发生下面的一系列动作(下面的数字和图1中的数字标签相对应):
1.在用户程序里的MapReduce库首先分割输入文件成M个片,每个片的大小一般从 16到64MB(用户可以通过可选的参数来控制).然后在机群中开始大量的拷贝程序.
2.这些程序拷贝中的一个是master,其他的都是由master分配任务的worker.有M 个map任务和R个reduce任务将被分配.管理者分配一个map任务或reduce任务给一个空闲的worker.
3.一个被分配了map任务的worker读取相关输入split的内容.它从输入数据中分析出key/value对,然后把key/value对传递给用户自定义的map函数.由map函数产生的中间key/value对被缓存在内存中.
4.缓存在内存中的key/value对被周期性的写入到本地磁盘上,通过分割函数把它们写入R个区域.在本地磁盘上的缓存对的位置被传送给master,master负责把这些位置传送给reduce worker.
5.当一个reduce worker得到master的位置通知的时候,它使用远程过程调用来从map worker的磁盘上读取缓存的数据.当reduce worker读取了所有的中间数据后,它通过排序使具有相同key的内容聚合在一起.因为许多不同的key映射到相同的reduce任务,所以排序是必须的.如果中间数据比内存还大,那么还需要一个外部排序.
6.reduce worker迭代排过序的中间数据,对于遇到的每一个唯一的中间key,它把key和相关的中间value集传递给用户自定义的reduce函数.reduce函数的输出被添加到这个reduce分割的最终的输出文件中.
7.当所有的map和reduce任务都完成了,管理者唤醒用户程序.在这个时候,在用户程序里的MapReduce调用返回到用户代码.
在成功完成之后,mapreduce执行的输出存放在R个输出文件中(每一个reduce任务产生一个由用户指定名字的文件).一般,用户不需要合并这R个输出文件成一个文件--他们经常把这些文件当作一个输入传递给其他的MapReduce调用,或者在可以处理多个分割文件的分布式应用中使用他们.

3.2master数据结构

master保持一些数据结构.它为每一个map和reduce任务存储它们的状态(空闲,工作中,完成),和worker机器(非空闲任务的机器)的标识.
master就像一个管道,通过它,中间文件区域的位置从map任务传递到reduce任务.因此,对于每个完成的map任务,master存储由map任务产生的R个中间文件区域的大小和位置.当map任务完成的时候,位置和大小的更新信息被接受.这些信息被逐步增加的传递给那些正在工作的reduce任务.

3.3容错

因为MapReduce库被设计用来使用成百上千的机器来帮助处理非常大规模的数据,所以这个库必须要能很好的处理机器故障.
worker故障
master周期性的ping每个worker.如果master在一个确定的时间段内没有收到worker返回的信息,那么它将把这个worker标记成失效.因为每一个由这个失效的worker完成的map任务被重新设置成它初始的空闲状态,所以它可以被安排给其他的worker.同样的,每一个在失败的worker上正在运行的map或reduce任务,也被重新设置成空闲状态,并且将被重新调度.
在一个失败机器上已经完成的map任务将被再次执行,因为它的输出存储在它的磁盘上,所以不可访问.已经完成的reduce任务将不会再次执行,因为它的输出存储在全局文件系统中.
当一个map任务首先被worker A执行之后,又被B执行了(因为A失效了),重新执行这个情况被通知给所有执行reduce任务的worker.任何还没有从A读数据的reduce任务将从worker B读取数据.
MapReduce可以处理大规模worker失败的情况.例如,在一个MapReduce操作期间,在正在运行的机群上进行网络维护引起80台机器在几分钟内不可访问了,MapReduce master只是简单的再次执行已经被不可访问的worker完成的工作,继续执行,最终完成这个MapReduce操作.
master失败
可以很容易的让管理者周期的写入上面描述的数据结构的checkpoints.如果这个master任务失效了,可以从上次最后一个checkpoint开始启动另一个master进程.然而,因为只有一个master,所以它的失败是比较麻烦的,因此我们现在的实现是,如果master失败,就中止MapReduce计算.客户可以检查这个状态,并且可以根据需要重新执行MapReduce操作.
在错误面前的处理机制
当用户提供的map和reduce操作对它的输出值是确定的函数时,我们的分布式实现产生,和全部程序没有错误的顺序执行一样,相同的输出.
我们依赖对map和reduce任务的输出进行原子提交来完成这个性质.每个工作中的任务把它的输出写到私有临时文件中.一个reduce任务产生一个这样的文件,而一个map任务产生R个这样的文件(一个reduce任务对应一个文件).当一个map任务完成的时候,worker发送一个消息给master,在这个消息中包含这R个临时文件的名字.如果master从一个已经完成的map任务再次收到一个完成的消息,它将忽略这个消息.否则,它在master的数据结构里记录这R个文件的名字.
当一个reduce任务完成的时候,这个reduce worker原子的把临时文件重命名成最终的输出文件.如果相同的reduce任务在多个机器上执行,多个重命名调用将被执行,并产生相同的输出文件.我们依赖由底层文件系统提供的原子重命名操作来保证,最终的文件系统状态仅仅包含一个reduce任务产生的数据.
我们的map和reduce操作大部分都是确定的,并且我们的处理机制等价于一个顺序的执行的这个事实,使得程序员可以很容易的理解程序的行为.当map或/和reduce操作是不确定的时候,我们提供虽然比较弱但是合理的处理机制.当在一个非确定操作的前面,一个reduce任务R1的输出等价于一个非确定顺序程序执行产生的输出.然而,一个不同的reduce任务R2的输出也许符合一个不同的非确定顺序程序执行产生的输出.
考虑map任务M和reduce任务R1,R2的情况.我们设定e(Ri)为已经提交的Ri的执行(有且仅有一个这样的执行).这个比较弱的语义出现,因为e(R1)也许已经读取了由M的执行产生的输出,而e(R2)也许已经读取了由M的不同执行产生的输出.

3.4存储位置

在我们的计算机环境里,网络带宽是一个相当缺乏的资源.我们利用把输入数据(由GFS管理)存储在机器的本地磁盘上来保存网络带宽.GFS把每个文件分成64MB的一些块,然后每个块的几个拷贝存储在不同的机器上(一般是3个拷贝).MapReduce的master考虑输入文件的位置信息,并且努力在一个包含相关输入数据的机器上安排一个map任务.如果这样做失败了,它尝试在那个任务的输入数据的附近安排一个map任务(例如,分配到一个和包含输入数据块在一个switch里的worker机器上执行).当运行巨大的MapReduce操作在一个机群中的一部分机器上的时候,大部分输入数据在本地被读取,从而不消耗网络带宽.

3.5任务粒度

象上面描述的那样,我们细分map阶段成M个片,reduce阶段成R个片.M和R应当比worker机器的数量大许多.每个worker执行许多不同的工作来提高动态负载均衡,也可以加速从一个worker失效中的恢复,这个机器上的许多已经完成的map任务可以被分配到所有其他的worker机器上.
在我们的实现里,M和R的范围是有大小限制的,因为master必须做O(M+R)次调度,并且保存O(M*R)个状态在内存中.(这个因素使用的内存是很少的,在O(M*R)个状态片里,大约每个map任务/reduce任务对使用一个字节的数据).
此外,R经常被用户限制,因为每一个reduce任务最终都是一个独立的输出文件.实际上,我们倾向于选择M,以便每一个单独的任务大概都是16到64MB的输入数据(以便上面描述的位置优化是最有效的),我们把R设置成我们希望使用的worker机器数量的小倍数.我们经常执行MapReduce计算,在M=200000,R=5000,使用2000台工作者机器的情况下.

3.6备用任务

一个落后者是延长MapReduce操作时间的原因之一:一个机器花费一个异乎寻常地的长时间来完成最后的一些map或reduce任务中的一个.有很多原因可能产生落后者.例如,一个有坏磁盘的机器经常发生可以纠正的错误,这样就使读性能从30MB/s降低到3MB/s.机群调度系统也许已经安排其他的任务在这个机器上,由于计算要使用CPU,内存,本地磁盘,网络带宽的原因,引起它执行MapReduce代码很慢.我们最近遇到的一个问题是,一个在机器初始化时的Bug引起处理器缓存的失效:在一个被影响的机器上的计算性能有上百倍的影响.
我们有一个一般的机制来减轻这个落后者的问题.当一个MapReduce操作将要完成的时候,master调度备用进程来执行那些剩下的还在执行的任务.无论是原来的还是备用的执行完成了,工作都被标记成完成.我们已经调整了这个机制,通常只会占用多几个百分点的机器资源.我们发现这可以显著的减少完成大规模MapReduce操作的时间.作为一个例子,将要在5.3描述的排序程序,在关闭掉备用任务的情况下,要比有备用任务的情况下多花44%的时间.

4技巧

尽管简单的map和reduce函数的功能对于大多数需求是足够的了,但是我们开发了一些有用的扩充.这些将在这个部分描述.

4.1分割函数

MapReduce用户指定reduce任务和reduce任务需要的输出文件的数量.在中间key上使用分割函数,使数据分割后通过这些任务.一个缺省的分割函数使用hash方法(例如,hash(key) mod R).这个导致非常平衡的分割.然后,有的时候,使用其他的key分割函数来分割数据有非常有用的.例如,有时候,输出的key是URLs,并且我们希望每个主机的所有条目保持在同一个输出文件中.为了支持像这样的情况,MapReduce库的用户可以提供专门的分割函数.例如,使用"hash(Hostname(urlkey)) mod R"作为分割函数,使所有来自同一个主机的URLs保存在同一个输出文件中.

4.2顺序保证

我们保证在一个给定的分割里面,中间key/value对以key递增的顺序处理.这个顺序保证可以使每个分割产出一个有序的输出文件,当输出文件的格式需要支持有效率的随机访问key的时候,或者对输出数据集再作排序的时候,就很容易.

4.3combiner函数

在某些情况下,允许中间结果key重复会占据相当的比重,并且用户定义的reduce函数
满足结合律和交换律.一个很好的例子就是在2.1部分的词统计程序.因为词频率倾向于一个zipf分布(齐夫分布),每个map任务将产生成百上千个这样的记录<the,1>.所有的这些计数将通过网络被传输到一个单独的reduce任务,然后由reduce函数加在一起产生一个数字.我们允许用户指定一个可选的combiner函数,先在本地进行合并一下,然后再通过网络发送.
在每一个执行map任务的机器上combiner函数被执行.一般的,相同的代码被用在combiner和reduce函数.在combiner和reduce函数之间唯一的区别是MapReduce库怎样控制函数的输出.reduce函数的输出被保存最终输出文件里.combiner函数的输出被写到中间文件里,然后被发送给reduce任务.
部分使用combiner可以显著的提高一些MapReduce操作的速度.附录A包含一个使用combiner函数的例子.

4.4输入输出类型

MapReduce库支持以几种不同的格式读取输入数据.例如,文本模式输入把每一行看作是一个key/value对.key是文件的偏移量,value是那一行的内容.其他普通的支持格式以key的顺序存储key/value对序列.每一个输入类型的实现知道怎样把输入分割成对每个单独的map任务来说是有意义的(例如,文本模式的范围分割确保仅仅在每行的边界进行范围分割).虽然许多用户仅仅使用很少的预定意输入类型的一个,但是用户可以通过提供一个简单的reader接口来支持一个新的输入类型.
一个reader不必要从文件里读数据.例如,我们可以很容易的定义它从数据库里读记录,或从内存中的数据结构读取.

4.5副作用

有的时候,MapReduce的用户发现在map操作或/和reduce操作时产生辅助文件作为一个附加的输出是很方便的.我们依靠应用程序写来使这个副作用成为原子的.一般的,应用程序写一个临时文件,然后一旦这个文件全部产生完,就自动的被重命名.
对于单个任务产生的多个输出文件来说,我们没有提供其上的两阶段提交的原子操作支持.因此,一个产生需要交叉文件连接的多个输出文件的任务,应该使确定性的任务.不过这个限制在实际的工作中并不是一个问题.

4.6跳过错误记录

有的时候因为用户的代码里有bug,导致在某一个记录上map或reduce函数突然crash掉.这样的bug使得MapReduce操作不能完成.虽然一般是修复这个bug,但是有时候这是不现实的;也许这个bug是在源代码不可得到的第三方库里.有的时候也可以忽略一些记录,例如,当在一个大的数据集上进行统计分析.我们提供一个可选的执行模式,在这个模式下,MapReduce库检测那些记录引起的crash,然后跳过那些记录,来继续执行程序.
每个worker程序安装一个信号处理器来获取内存段异常和总线错误.在调用一个用户自定义的map或reduce操作之前,MapReduce库把记录的序列号存储在一个全局变量里.如果用户代码产生一个信号,那个信号处理器就会发送一个包含序号的"last gasp"UDP包给MapReduce的master.当master不止一次看到同一个记录的时候,它就会指出,当相关的map或reduce任务再次执行的时候,这个记录应当被跳过.

4.7本地执行

调试在map或reduce函数中问题是很困难的,因为实际的计算发生在一个分布式的系统中,经常是有一个master动态的分配工作给几千台机器.为了简化调试和测试,我们开发了一个可替换的实现,这个实现在本地执行所有的MapReduce操作.用户可以控制执行,这样计算可以限制到特定的map任务上.用户以一个标志调用他们的程序,然后可以容易的使用他们认为好用的任何调试和测试工具(例如,gdb).

4.8状态信息

master运行一个HTTP服务器,并且可以输出一组状况页来供人们使用.状态页显示计算进度,象多少个任务已经完成,多少个还在运行,输入的字节数,中间数据字节数,输出字节数,处理百分比,等等.这个页也包含到标准错误的链接,和由每个任务产生的标准输出的链接.用户可以根据这些数据预测计算需要花费的时间,和是否需要更多的资源.当计算比预期的要慢很多的时候,这些页面也可以被用来判断是不是这样.
此外,最上面的状态页显示已经有多少个工作者失败了,和当它们失败的时候,那个map和reduce任务正在运行.当试图诊断在用户代码里的bug时,这个信息也是有用的.

4.9计数器

MapReduce库提供一个计数器工具,来计算各种事件的发生次数.例如,用户代码想要计算所有处理的词的个数,或者被索引的德文文档的数量.
为了使用这个工具,用户代码创建一个命名的计数器对象,然后在map或/和reduce函数里适当的增加计数器.例如:
Counter * uppercase;
uppercase=GetCounter("uppercase");
map(String name,String contents):
for each word w in contents:
    if(IsCapitalized(w)):
      uppercase->Increment();
    EmitIntermediate(w,"1");
来自不同worker机器上的计数器值被周期性的传送给master(在ping回应里).master把来自成功的map和reduce任务的计数器值加起来,在MapReduce操作完成的时候,把它返回给用户代码.当前计数器的值也被显示在master状态页里,以便人们可以查看实际的计算进度.当计算计数器值的时候消除重复执行的影响,避免数据的累加.(在备用任务的使用,和由于出错的重新执行,可以产生重复执行)
有些计数器值被MapReduce库自动的维护,比如,被处理的输入key/value对的数量,和被产生的输出key/value对的数量.
用户发现计数器工具对于检查MapReduce操作的完整性很有用.例如,在一些MapReduce操作中,用户代码也许想要确保输出对的数量完全等于输入对的数量,或者处理过的德文文档的数量是在全部被处理的文档数量中属于合理的范围.

5性能

在本节,我们用在一个大型集群上运行的两个计算来衡量MapReduce的性能.一个计算用来在一个大概1TB的数据中查找特定的匹配串.另一个计算排序大概1TB的数据.
这两个程序代表了MapReduce的用户实现的真实的程序的一个大子集.一类是,把数据从一种表示转化到另一种表示.另一类是,从一个大的数据集中提取少量的关心的数据.

5.1机群配置

所有的程序在包含大概1800台机器的机群上执行.机器的配置是:2个2G的Intel Xeon超线程处理器,4GB内存,两个160GB IDE磁盘,一个千兆网卡.这些机器部署在一个由两层的,树形交换网络中,在根节点上大概有100到2000G的带宽.所有这些机器都有相同的部署(对等部署),因此任意两点之间的来回时间小于1毫秒.

在4GB的内存里,大概有1-1.5GB被用来运行在机群中其他的任务.这个程序是在周末的下午开始执行的,这个时候CPU,磁盘,网络基本上是空闲的.

5.2Grep

这个Grep程序扫描大概10^10个,每个100字节的记录,查找比较少的3字符的查找串(这个查找串出现在92337个记录中).输入数据被分割成大概64MB的片(M=15000),全部 的输出存放在一个文件中(R=1).
图2显示计算过程随时间变化的情况.Y轴表示输入数据被扫描的速度.随着更多的机群被分配给这个MapReduce计算,速度在逐步的提高,当有1764个worker的时候这个速度达到最高的30GB/s.当map任务完成的时候,速度开始下降,在计算开始后80秒,输入的速度降到0.这个计算持续的时间大概是150秒.这包括了前面大概一分钟的启动时间.启动时间用来把程序传播到所有的机器上,等待GFS打开1000个输入文件,得到必要的位置优化信息.

5.3排序

这个sort程序排序10^10个记录,每个记录100个字节(大概1TB的数据).这个程序是模仿TeraSort的.
这个排序程序只包含不到50行的用户代码.其中有3行map函数用来从文本行提取10字节的排序key,并且产生一个由这个key和原始文本行组成的中间key/value对.我们使用一个内置的Identity函数作为reduce操作.这个函数直接把中间key/value对作为输出的key/value对.最终的排序输出写到一个2路复制的GFS文件中(也就是,程序的输出会写2TB的数据).
象以前一样,输入数据被分割成64MB的片(M=15000).我们把排序后的输出写到4000个文件中(R=4000).分区函数使用key的原始字节来把数据分区到R个小片中.
我们以这个基准的分割函数,知道key的分布情况.在一般的排序程序中,我们会增加一个预处理的MapReduce操作,这个操作用于采样key的情况,并且用这个采样的key的分布情况来计算对最终排序处理的分割点。
图3(a)显示这个排序程序的正常执行情况.左上图显示输入数据的读取速度.这个速度最高到达13GB/s,并且在不到200秒所有map任务完成之后迅速滑落到0.注意到这个输入速度小于Grep.这是因为这个排序map任务花费大概一半的时间和带宽,来把中间数据写到本地硬盘中.而Grep相关的中间数据可以忽略不计.
左中图显示数据通过网络从map任务传输给reduce任务的速度.当第一个map任务完成后,这个排序过程就开始了.图示上的第一个高峰是启动了第一批大概1700个reduce任务(整个MapReduce任务被分配到1700台机器上,每个机器一次只执行一个reduce任务).大概开始计算后的300秒,第一批reduce任务中的一些完成了,我们开始执行剩下的reduce任务.全部的排序过程持续了大概600秒的时间.
左下图显示排序后的数据被reduce任务写入最终文件的速度.因为机器忙于排序中间数据,所以在第一个排序阶段的结束和写阶段的开始有一个延迟.写的速度大概是2-4GB/s.大概开始计算后的850秒写过程结束.包括前面的启动过程,全部的计算任务持续的891秒.这个和TeraSort benchmark的最高纪录1057秒差不多.
需要注意的事情是:因此位置优化的原因,很多数据都是从本地磁盘读取的而没有通过我们有限带宽的网络,所以输入速度比排序速度和输出速度都要快.排序速度比输出速度快的原因是输出阶段写两个排序后数据的拷贝(我们写两个副本的原因是为了可靠性和可用性).我们写两份的原因是因为底层文件系统的可靠性和可用性的要求.如果底层文件系统用类似容错编码(erasure coding)的方式,而不采用复制写的方式,在写盘阶段可以降低网络带宽的要求。

5.4备用任务的影响

在图3(b)中,显示我们不用备用任务的排序程序的执行情况.除了它有一个很长的几乎没有写动作发生的尾巴外,执行流程和图3(a)相似.在960秒后,只有5个reduce任务没有完成.然而,就是这最后几个落后者知道300秒后才完成.全部的计算任务执行了1283秒,多花了44%的时间.

5.5机器失效

在图3(c)中,显示我们有意的在排序程序计算过程中停止1746台worker中的200台机器上的程序的情况.底层机群调度者在这些机器上马上重新开始新的worker程序(因为仅仅程序被停止,而机器仍然在正常运行).
因为已经完成的map工作丢失了(由于相关的map worker被杀掉了),需要重新再作，所以worker死掉会导致一个负数的输入速率.相关map任务的重新执行很快就重新执行了.整个计算过程在933秒内完成,包括了前边的启动时间(只比正常执行时间多了5%的时间).

6经验

我们在2003年的2月写了MapReduce库的第一个版本,并且在2003年的8月做了显著的增强,包括位置优化,worker机器间任务执行的动态负载均衡,等等.从那个时候起,我们惊奇的发现MapReduce函数库广泛用于我们日常处理的问题.它现在在Google内部各个领域内广泛应用,包括:
大规模机器学习问题
Google News和Froogle产品的机器问题.
提取数据产生一个流行查询的报告(例如,Google Zeitgeist).
为新的试验和产品提取网页的属性(例如,从一个web页的大集合中提取位置信息   用在位置查询).
   大规模的图计算.
图4显示了我们主要的源代码管理系统中,随着时间推移,MapReduce程序的显著增加,从2003年早先时候的0个增长到2004年9月份的差不多900个不同的程序.MapReduce之所以这样的成功,是因为他能够在不到半小时时间内写出一个简单的能够应用于上千台机器的大规模并发程序,并且极大的提高了开发和原形设计的周期效率.并且,他可以让一个完全没有分布式和/或并行系统经验的程序员,能够很容易的利用大量的资源.
在每一个任务结束的时候,MapReduce函数库记录使用的计算资源的统计信息.在图1里,我们列出了2004年8月份在Google运行的一些MapReduce的工作的统计信息.

6.1大规模索引

到目前为止,最成功的MapReduce的应用就是重写了Google web 搜索服务所使用到的index系统.索引系统处理爬虫系统抓回来的超大量的文档集,这些文档集保存在GFS文件里.这些文档的原始内容的大小,超过了20TB.索引程序是通过一系列的,大概5到10次MapReduce操作来建立索引.通过利用MapReduce(替换掉上一个版本的特别设计的分布处理的索引程序版本)有这样一些好处:
索引的代码简单,量少,容易理解,因为容错,分布式,并行处理都隐藏在MapReduce库中了.例如,当使用MapReduce函数库的时候,计算的代码行数从原来的3800行C++代码一下减少到大概700行代码.
MapReduce的函数库的性能已经非常好,所以我们可以把概念上不相关的计算步骤分开处理,而不是混在一起以期减少在数据上的处理.这使得改变索引过程很容易.例如,我们对老索引系统的一个小更改可能要好几个月的时间,但是在新系统内,只需要花几天时间就可以了.
索引系统的操作更容易了,这是因为机器的失效,速度慢的机器,以及网络失效都已经由MapReduce自己解决了,而不需要操作人员的交互.另外,我们可以简单的通过对索引系统增加机器的方式提高处理性能.

7相关工作

很多系统都提供了严格的设计模式,并且通过对编程的严格限制来实现自动的并行计算.例如,一个结合函数可以通过N个元素的数组的前缀在N个处理器上使用并行前缀计算在log N的时间内计算完.MapReduce是基于我们的大型现实计算的经验,对这些模型的一个简化和精炼.并且,我们还提供了基于上千台处理器的容错实现.而大部分并发处理系统都只在小规模的尺度上实现,并且机器的容错还是程序员来控制的.
Bulk Synchronous Programming以及一些MPI primitives提供了更高级别的抽象,可以更容易写出并行处理的程序.这些系统和MapReduce系统的不同之处在,MapReduce利用严格的编程模式自动实现用户程序的并发处理,并且提供了透明的容错处理.
我们本地的优化策略是受active disks等技术的启发,在active disks中,计算任务是尽量推送到靠近本地磁盘的处理单元上,这样就减少了通过I/O子系统或网络的数据量.我们在少量磁盘直接连接到普通处理机运行,来代替直接连接到磁盘控制器的处理机上,但是一般的步骤是相似的.
我们的备用任务的机制和在Charlotte系统上的积极调度机制相似.这个简单的积极调度的一个缺陷是,如果一个任务引起了一个重复性的失败,那个整个计算将无法完成.我们通过在故障情况下跳过故障记录的机制,在某种程度上解决了这个问题.
MapReduce实现依赖一个内置的机群管理系统来在一个大规模共享机器组上分布和运行用户任务.虽然这个不是本论文的重点,但是集群管理系统在理念上和Condor等其他系统是一样的.
在MapReduce库中的排序工具在操作上和NOW-Sort相似.源机器(map worker)分割将要被排序的数据,然后把它发送到R个reduce worker中的一个上.每个reduce worker来本地排序它的数据(如果可能,就在内存中).当然,NOW-Sort没有用户自定义的map和reduce函数,使得我们的库可以广泛的应用.
River提供一个编程模型,在这个模型下,处理进程可以靠在分布式的队列上发送数据进行彼此通讯.和MapReduce一样,River系统尝试提供对不同应用有近似平均的性能,即使在不对等的硬件环境下或者在系统颠簸的情况下也能提供近似平均的性.River是通过精心调度硬盘和网络的通讯,来平衡任务的完成时间.MapReduce不和它不同.利用严格编程模型,MapReduce构架来把问题分割成大量的任务.这些任务被自动的在可用的worker上调度,以便速度快的worker可以处理更多的任务.这个严格编程模型也让我们可以在工作快要结束的时候安排冗余的执行,来在非一致处理的情况减少完成时间(比如,在有慢机或者阻塞的worker的时候).
BAD-FS是一个很MapReduce完全不同的编程模型,它的目标是在一个广阔的网络上执行工作.然而,它们有两个基本原理是相同的.(1)这两个系统使用冗余的执行来从由失效引起的数据丢失中恢复.(2)这两个系统使用本地化调度策略,来减少通过拥挤的网络连接发送的数据数量.
TACC是一个被设计用来简化高有效性网络服务结构的系统.和MapReduce一样,它通过再次执行来实现容错.

8结束语

MapReduce编程模型已经在Google成功的用在不同的目的.我们把这个成功归于以下几个原因:第一,这个模型使用简单,甚至对没有并行和分布式经验的程序员也是如此,因为它隐藏了并行化,容错,位置优化和负载均衡的细节.第二,大量不同的问题可以用MapReduce计算来表达.例如,MapReduce被用来,为Google的产品web搜索服务,排序,数据挖掘,机器学习,和其他许多系统,产生数据.第三,我们已经在一个好几千台计算机的大型集群上开发实现了这个MapReduce.这个实现使得对于这些机器资源的利用非常简单,因此也适用于解决Google遇到的其他很多需要大量计算的问题.
从这个工作中我们也学习到了一些东西.首先,严格的编程模型使得并行化和分布式计算简单,并且也易于构造这样的容错计算环境.第二,网络带宽是系统的瓶颈.因此在我们的系统中大量的优化目标是减少通过网络发送的数据量,本地优化使用我们从本地磁盘读取数据,并且把中间数据写到本地磁盘,以保留网络带宽.第三,冗余的执行可以用来减少速度慢的机器的影响,和控制机器失效和数据丢失.

感谢

Josh Levenberg校定和扩展了用户级别的MapReduce API,并且结合他的适用经验和其他人的改进建议,增加了很多新的功能.MapReduce从GFS中读取和写入数据.我们要感谢Mohit Aron,Howard Gobioff,Markus Gutschke,David Krame,Shun-Tak Leung,和Josh Redstone,他们在开发GFS中的工作.我们还感谢Percy Liang Olcan Sercinoglu 在开发用于MapReduce的集群管理系统得工作.Mike Burrows,Wilson Hsieh,Josh Levenberg,Sharon Perl,RobPike,Debby Wallach为本论文提出了宝贵的意见.OSDI的无名审阅者,以及我们的审核者Eric Brewer,在论文应当如何改进方面给出了有益的意见.最后,我们感谢Google的工程部的所有MapReduce的用户,感谢他们提供了有用的反馈,建议,以及错误报告等等.
A单词频率统计
本节包含了一个完整的程序,用于统计在一组命令行指定的输入文件中,每一个不同的单词出现频率.
#include "mapreduce/mapreduce.h"
//用户map函数
class WordCounter : public Mapper {
public:
    virtual void Map(const MapInput& input) {
      const string& text = input.value();
      const int n = text.size();
      for (int i = 0; i < n; ) {
        //跳过前导空格
        while ((i < n) && isspace(text[i]))
             i++;
         // 查找单词的结束位置
         int start = i;
         while ((i < n) && !isspace(text[i]))
              i++;
         if (start < i)
            Emit(text.substr(start,i-start),"1");
        }

     }

};

REGISTER_MAPPER(WordCounter);
//用户的reduce函数
class Adder : public Reducer {
    virtual void Reduce(ReduceInput* input) {
             //迭代具有相同key的所有条目,并且累加它们的value
              int64 value = 0;
              while (!input->done()) {
                     value += StringToInt(input->value());
                     input->NextValue();
              }
               //提交这个输入key的综合
              Emit(IntToString(value));
       }

};
REGISTER_REDUCER(Adder);
int main(int argc, char** argv) {
       ParseCommandLineFlags(argc, argv);
       MapReduceSpecification spec;
       // 把输入文件列表存入"spec"
       for (int i = 1; i < argc; i++) {
              MapReduceInput* input = spec.add_input();
              input->set_format("text");
              input->set_filepattern(argv[i]);
              input->set_mapper_class("WordCounter");
       }
        //指定输出文件:
       // /gfs/test/freq-00000-of-00100
       // /gfs/test/freq-00001-of-00100
      // ...
       MapReduceOutput* out = spec.output();
       out->set_filebase("/gfs/test/freq");
       out->set_num_tasks(100);
       out->set_format("text");
       out->set_reducer_class("Adder");
       // 可选操作:在map任务中做部分累加工作,以便节省带宽
       out->set_combiner_class("Adder");
       // 调整参数: 使用2000台机器,每个任务100MB内存
       spec.set_machines(2000);
       spec.set_map_megabytes(100);
       spec.set_reduce_megabytes(100);
       // 运行它
       MapReduceResult result;
       if (!MapReduce(spec, &result)) abort();
       // 完成: 'result'结构包含计数,花费时间,和使用机器的信息
       return 0;
}

(1) 老板，你要这么多数据做什么？
假如你是一个商品零售公司的老板。     你的公司很先进，已经实现了业务信息化，每一笔销售单据都保存在数据库中，日积月累，已经保存了十余年的销售数据，上亿条销售记录。      这时如果我问你：“反正三年前的数据留着也白白占地方，耗费存储成本，索性把它们全删掉吧，这样不用买硬盘就能容纳新数据，如何？”      你会从容的接受我这个建议吗？           那么老板，你要这么多数据做什么？      是的，和我一样，你也已经隐约认识到数据的价值，这就是我们割舍不下历史数据的原因，就像任何一个现代化企业，甚至就像任何一个传统的票号，如百年老店般虔诚地保存着古老的数据，因为我们有直觉，我们的直觉告诉我们：这些数据有用！      但这仅仅是一种直觉，到底该怎样把这些占据大量存储空间的数据的价值挖掘出来，让这些数据从成本的消耗者变成利润的促进者？      这中间似乎缺少了某些环节。

(2) Business Intelligence - 连接数据与决策者

BI(Business Intelligence) 是一种运用了数据仓库、在线分析和数据挖掘等技术来处理和分析数据的崭新技术，目的是为企业决策者提供决策支持。      让我们振臂高呼三遍：决策支持，决策支持，决策支持！      BI 是一个工厂：          >> BI 的原材料是海量的数据；          >> BI 的产品是由数据加工而来的信息和知识；          >> BI 将这些产品推送给企业决策者；          >> 企业决策者利用 BI 工厂的产品做出正确的决策，促进企业的发展；      这就是 Business Intelligence，即商业智能——连接数据与决策者，变数据为价值。      BI 应用的两大类别是 信息类应用 和 知识类应用，其特征如下表所示： 信息类 BI 应用      指由原始数据加工而来的数据查询、报表图表、多维分析、数据可视化等应用，这些应用的共同特点是：将数据转换为决策者可接受的信息，展现给决策者。     例如将银行交易数据加工为银行财务报表。      仅负责提供信息，而不会主动去分析数据。      例如，银行财务报表工具没有深入分析客户流失和银行利率之间关系的能力，而只能靠决策者结合信息，通过人的思考，得出知识。 知识类 BI 应用      指通过数据挖掘技术和工具，将数据中隐含的关系发掘出来，利用计算机直接将数据加工为知识，展现给决策者。      会主动去数据中探查数据关联关系，发掘那些决策者人脑无法迅速发掘的隐含知识，并将其以可理解的形式呈现在决策者面前。

(3) BI 初级应用模式概览——数据查询(Querying)
数据查询是最简单的 BI 应用，属于 MIS 系统遗产，虽然出身比较老土，但是目前仍然是决策者获取信息的最直接的方法。     如今，数据查询界面已经彻底摆脱了传统 SQL 命令行，大量的下拉菜单、输入框、列表框等元素甚至是鼠标拖拽界面将后台干苦力的 SQL 语句包装成一个妖艳无比的数据获取系统，而本质仍然没有离开数据查询的几大要素：         >> 查什么     >> 从哪儿查     >> 过滤条件     >> 展示方法          目前国外比较流行的数据查询应用已经完全释放了数据查询的灵活性，如右图所示的是 Cognos ReportNet 的数据查询界面 Query Studio，允许用户通过纯浏览器界面，以鼠标拖拽操作定义数据查询要素，并以报表和图表等多种方式展现数据。

(4) BI 初级应用模式概览——报表(Reporting)

报表是国内最热衷的 BI 应用之一，这与报表在我国企事业单位中的历史地位是分不开的。我国的报表以其格式诡异、数据集中、规则古怪等特征著称于世，曾经让无数国外报表工具和 BI 工具捶胸顿足。     报表的两大要素是数据和格式， 如果没有格式，则报表应用几乎等同于数据查询应用。可以说，报表就是将查询出来的数据按照指定的格式展现。     报表应用包含了报表展现和报表制作两大模块。报表展现就是让决策者看到报表，并允许决策者通过条件定义来选择报表数据，例如选择报表年度、部门、机构等等；报表制作面向报表的开发人员，其格式定义灵活性、数据映射灵活性、计算方法的丰富程度等均影响了 BI 报表应用的质量。     需要澄清一下的是，Microsoft Excel 不算是一个 BI 报表工具，因为 Excel 没有连接数据源的能力，充其量是一个 Spread Sheet。但是 Excel 强大的格式功能让报表制作人员竟折腰，乃至到后来，几乎所有 BI 厂商都提供了面向 Microsoft Excel 的插件，通过插件，Excel 可以连接到 BI 的数据源上，摇身一变为 BI 报表工具，丑小鸭变天鹅。

上图是典型的中国特色的报表，注意其横向表头，各列嵌套层数不一样，行话叫“不均衡报表”。这些报表单元格中的数据是从不同的数据库表的不同的字段中经过不同的计算方法得到的。这种报表当年秒杀了第一批抢滩中国的 BI 软件，乃至后来衍生出诸多售前对策，如用位图画表头然后用数据库存储过程计算表瓤、程序调用 Excel COM 嵌套拼接等等各类江湖招数。

(5) BI 高级应用模式概览——在线分析(OnLine Analytical Processing,OLAP)

OLAP ，即联机分析处理，是 BI 带来的一种全新的数据观察方式，是 BI 的核心技术之一。     我们知道，数据在数据库中是以数据表来存储的，比如某商店的销售数据存储在如下所示的一张数据表中： 销售时间 销售地点 产品 销售数量 销售金额 2004-11-1 北京 肥皂 10 342.00 2004-11-6 广州 桔子 30 123.00 2004-12-3 北京 香蕉 20 12.00 2004-12-13 上海 桔子 50 189.00 2005-1-8 北京 肥皂 10 342.00 2005-1-23 上海 牙刷 30 150.00 2005-2-4 广州 牙刷 20 100.00     决策者希望知道的往往是分布、占比、趋势之类的宏观信息，比如下列问题：         >> 北京地区的销售数量虽时间的变化趋势？         >> 哪种产品在 2005 年销售比 2004 年销售增幅最大？         >> 2004 年各产品销售额的比例分布？ ……     面对这种需求，必须用 SQL 语句进行大量的 SUM 操作，每得出一个问题的结果，就需要 SQL SUM。面对上面的 7 条记录，我们可以很容易的得出结果，但是当我们面对百万级甚至亿级的记录条数时，例如移动公司通话数据，每次 SQL SUM 都需要消耗大量的时间来计算，决策者经常是在第一天提出分析需求，等到第二天才能拿到计算结果，这种分析方式是“脱机分析”，效率很低。     为了提高数据分析效率，OLAP 技术彻底打破以记录为单位的数据浏览方式，而将数据分离为“维度(Dimension)”和“度量(Measure)”：         >> 维度是观察数据的角度，例如上面示例中的“销售时间”、“销售地点”、“产品”；         >> 度量是具体考察的数量值，例如上例中的“销售数量”和“销售金额”；     这样一来，我们就可以将上面这张平版的数据列表转换为一个拥有三个维度的数据立方体( Cube )：     而探查数据的过程，就是在这个立方体中确定一个点，然后观察这个点的度量值：     当然，数据立方体并不局限于三个维度，这里采用三个维度来说明问题，只是因为通过图形可以表现出来的极限就是三个维度。     维度可以划分层次，例如时间上可以从日向上汇总为月和年，产品可以向上汇总为食品和日用品，地点可以向上汇总为华北和华南，用户可以沿着维度的层次任意向下钻取(Drill Down)和向上汇总(Roll Up)：     通过这种方式，我们就可以摆脱 SQL SUM 对速度的制约，快速定位符合不同条件的细节数据，更可以迅速得到某一层次的汇总数据。OLAP 技术为决策者提供了多角度、多层次、高效率的数据探查方式，决策者的思维不再被固定的下拉菜单、查询条件所束缚，而是由决策者的思维带领数据的获取，任意组合分析角度和分析目标，这种打破传统的互动性分析和高效率使 OLAP 成为 BI 系统的核心应用。     下图是 Cognos Powerplay 提供的 OLAP 分析界面，用户仅需把自己感兴趣的维度和度量拖拽到相应位置，就能获得图表和报表：

(*) 第四喷：BI 高级应用模式 —— 数据可视化与数据挖掘

(6) BI 应用模式概览——数据可视化(Visualization)

一图胜千言。     数据可视化应用致力于将信息以尽可能多的形式展现出来，目的是使决策者通过图形这种直观的表现方式迅速获得信息中蕴藏的知识，如趋势、分布、密度等要素。     值得一提的是，以 MapInfo 公司为代表的 GIS 软件商，目前也正在努力结合 BI 应用。MapInfo 率先提出了 Location Intelligence 概念，依托于地理信息系统，展现各地区的属性值，例如人口密度，工业产值，人均医院数量等等，这种可视化应用部分与 BI 数据可视化应用重合，并形成有力补充，有时可以在一个项目中互相搭配。         上图所示的是 Cognos Visualizer 产品， 这家伙用几近哗众取宠的丰富形式展现数据和信息，包含了地图、饼图、瀑布图等近五十种展现图形，并提供了二维和三维两种展现方式。所有的图形元素都是可活动的，例如用户可以通过点击地图上的某一个省，钻取到这个省各个城市的信息，这种可交互性是 BI 与普通图片生成软件的显著差异。

(7) BI 应用模式概览——数据挖掘(Data Mining)
数据挖掘是最高级的 BI 应用，因为它能代替部分人脑功能。     数据挖掘隶属于知识发现(Knowledge Discovery)在结构化数据中的特例。     数据挖掘的目的是通过计算机对大量数据进行分析，找出数据之间潜藏的规律和知识，并以可理解的方式展现给用户。      数据挖掘的三大要素是：          >> 技术和算法：目前常用的数据挖掘技术包括——                  自动类别侦测(Auto Cluster Detection)                  决策树(Decision Trees)                  神经网络(Neural Networks)          >> 数据：由于数据挖掘是一个在已知中挖掘未知的过程，                  因此需要大量数据的积累作为数据源，数据积累                  量越大，数据挖掘工具就会有更多的参考点。          >> 预测模型：也就是将需要进行数据挖掘的业务逻辑由                  计算机模拟出来，这也是数据挖掘的主要任务。     与信息类 BI 应用相比，以数据挖掘为代表的知识类 BI 应用目前还不成熟，但是从另一个角度来看，数据挖掘可发展的空间还很大，是今后 BI 发展的重点方向，SAS，SPSS 等知识类 BI 应用厂商形象逐渐高大，悄悄占据了新的利润增长点。
上图中是著名的 IBM Intelligent Miner 在分析客户的消费行为。它能对大量的客户数据进行分析，然后自动将客户划分为若干群体（自动类别侦测），并将每个群体的消费特征显示出来，这样决策者就能一目了然的针对不同客户的消费习惯，制定促销计划或广告计划。           上述功能如果单靠信息类 BI 应用来实现，则需要决策者根据经验进行大量的 OLAP 分析、数据查询工作，而且还不一定能发现数据中隐藏的规律。例如上述客户分类，对于一个拥有 400 万用户的银行来说，如果没有数据挖掘工具，会把人活活累死的。

(8) BI 底座——数据仓库技术(Data Warehouse)
在开始喷这个主题之前，让我们先看看数据仓库的官方定义：         数据仓库(Data Warehouse)是一个面向主题的(Subject Oriented)、集成的(Integrate)、相对稳定的(Non-Volatile)、反映历史变化(Time Variant)的数据集合，用于支持管理决策。以上是数据仓库的官方定义。     “操作型数据库”如银行里记账系统数据库，每一次业务操作（比如你存了5元钱），都会立刻记录到这个数据库中，长此以往，满肚子积累的都是零碎的数据，这种干脏活累活还不得闲的数据库就叫“操作型数据库”，面向的是业务操作。     “数据仓库”用于决策支持，面向分析型数据处理，不同于操作型数据库；另外，数据仓库是对多个异构的数据源有效集成，集成后按照主题进行了重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。     操作型数据库 、数据仓库与数据库之间的关系，就像 C:、D: 与硬盘之间的关系一样，数据库是硬盘，操作型数据库是 C:，数据仓库是 D:，操作型数据库与数据仓库都存储在数据库里，只不过表结构的设计模式和用途不同。
那么为什么要在操作型数据库和 BI 之间加这么一层“数据仓库”呢？     一是因为操作型数据库日夜奔忙，以快速响应业务为主要目标，根本没精力伺候 BI 这边的数据需求，而且 BI 这边的数据需求通常是汇总型的，一个 select sum(xx) group by xx 就能让操作型数据库耗费大量资源，业务处理跟不上趟，麻烦就大了，比如你存了 5000 元钱，发现十分钟后钱还没到账，作何感想？一定是该银行的领导在看饼图？
二是因为企业中一般存在有多个应用，对应着多个操作型数据库，比如人力资源库、财务库、销售单据库、库存货品库等等，BI 为了提供全景的数据视图，就必须将这些分散的数据综合起来，例如为了实现一个融合销售和库存信息的 OLAP 分析，BI 工具必须能够高效的取得两个数据库中的数据，这时最高效的方法就是将数据先整合到数据仓库中，而 BI 应用统一从数据仓库里取数。
将分散的操作型数据库中的数据整合到数据仓库中是一门大学问，催生了数据整合软件的市场。这种整合并不是简单的将表叠加在一起，而是必须提取出每个操作型数据库的维度，将共同的维度设定为共用维度，然后将包含具体度量值的数据库表按照主题统一成若干张大表（术语“事实表”，Fact Tables），按照维度-度量模型建立数据仓库表结构，然后进行数据抽取转换。后续的抽取一般是在操作性数据库负载比较小的时候（如凌晨），对新数据进行增量抽取，这样数据仓库中的数据就会形成积累。
大多数 BI 应用并不要求获取实时的数据，比如决策者，只需要在每周一看到上周的周报就可以了，95% 的 BI 应用都不要求实时性，允许数据有 1 小时至 1 个月不等的滞后，这是决策支持系统的应用特点，这个滞后区间就是数据抽取工具工作的时间。当然，BI 应用中通常还将包含极少的对实时数据的要求，这时仅需针对这些特殊需求，将 BI Querying 软件直接连接在业务数据库上就可以了，但是必须限制负载，禁止做复杂查询。     目前的数据库产品都对数据仓库提供有专门优化，例如在安装 MySQL 的高版本时，安装成序会询问你是想让数据库实例作为 Transaction-Oriented ，还是 Decision Support ，前者就是操作型数据库，后者就是数据仓库（决策支持么，再振臂高呼一遍），针对这两种形式，数据库将提供针对性的优化。

(9) BI 花边

BI 的相关知识大致就是这样了，写一些花边作为结束语吧。     BI 要害：BI 无法处理非结构化数据，只能处理数字信息，但是在企业中，还存在有大量像文本、流媒体、图片等非结构化的数据，这些数据同样蕴藏有大量价值，但是面对这些数据，目前的 BI 工具无能为力。比较靠谱的是 IBM Intelligent Miner for Text，但是它在处理中文方面似乎十分薄弱。         BI 厂商和产品：让我们认识一下这些大人物！数据仓库方面，有 IBM DB2，Oracle，Sybase IQ，NCR Teradata 等等；BI 应用方面，有 Cognos，Business Objects，MicroStrategy，Hyperion，IBM 等等；数据挖掘方面，有 IBM，SAS，SPSS 等等。巨无霸 Microsoft 也在 BI 领域插了一腿，推出了 SQL Server Analysis Server、Reporting Services 等 BI 相关产品，作抢占山头状。     中国的 BI 市场发展： 时间段 国内 BI 应用情况 2002 年以前     大量 BI 软件被看作是能从多个数据源中抽取数据的报表工作，满眼全是报表。     一开始，公司的销售在推销产品时都向用户介绍：“我们是 BI 领域最强的……”效果不好；后来那些销售终于找到了窍门，上来就说：“我们什么报表都能做！”然后订单不断。 2002-2003     OLAP 的价值终于被某些慧眼发现，一些竞争压力大的企业为了提高竞争力，迫切需要从历史数据中挖掘价值，迅速发现了 OLAP 的优势，这时销售终于不用再说“我们什么报表都能做”了。但是国家机关、垄断型企业，仍旧是报表，并且以为 BI 就是报表。 2004     随着越来越多成功 BI 项目的实施，OLAP 终于得以见天日，这时国内才形成数据查询+报表展示+OLAP分析的合理 BI 应用结构。一些数据可视化的需求也时常被用户提出，在一些竞争激烈、数据量大的企业，已经出现了数据挖掘应用。 2005     信息提供已经无法满足很多企业的要求，特别是银行、通信、证券等竞争激烈、风险密集的行业，大量涌现对数据挖掘的需求，BI 应用终于形成信息+知识的整体。     BI 工具在中国遇到的难题： * 复杂表样：中国是世界上报表最复杂的国家。中国的表样设计思想与西方不同，西方报表倾向于仅用一张报表说明一个问题，而中国的报表倾向于将尽可能多的问题集中在一张报表中，这种思路直接导致了中国报表的复杂格式和诡异风格。 * 大数据量：中国是世界上人口最多的国家。以中国移动公司为例，仅我国一个省的用户数量，就相当于欧洲一个中等国家的人口，是真正的海量数据！国外数据库、数据仓库和 BI 应用软件，都在中国经受着大数据量承载能力的考验。对于美国，可能一个客户分析应用两秒钟就能出结果，但是在中国这样的数据量下，可就不是两秒钟的问题了。 * 数据回写：中国是世界上对 BI 系统要求最奇特的国家。本来 BI 系统是以忠实再现源数据为原则，但这个原则在中国遇到了难题，许多领导都提出了数据修改需求，“报表里数字不好看，就要能改啊，而且有时候也需要调整啊，这样上级领导看着就好嘛！ ”一个领导如是说。目前能满足此要求的 BI 产品，仅有 Microsoft 和 MicroStrategy 两家。微软对中国市场算是吃透了。 原帖地址：http://www.xerdoc.com/blog/archives/142.html ...

1.解释商业智能对企业的重要性
商业智能可以帮助企业的管理层进行快速准确的决策，同时迅速发现企业中的问题，提示管理人员加以解决，商业智能为企业带来的是一种新的管理思维，给整个企业带来的是决策的快速性和准确性、发现问题的及时性以及发现那些对手没有发现的潜在的知识和规律，而这些信息时企业产生经济效益的基础。因为不能快速,准确的指定决策方针等于将市场送给对手, 不能及时发现业务种的潜在信息等于浪费自己的资源。

2.数据仓库、OLAP和数据挖掘在商业智能中的角色
商业智能通常被理解为将企业中现有的数据转化为知识，为了将数据转化为知识，需要利用数据仓库、联机分析处理（OLAP）工具和数据挖掘等技术。
数据仓库：数据仓库负责执行数据的存储和管理，并执行前端展现工具提交的各种查询分析任务。属于商业智能的基础，它直接决定了商业智能应用的响应速度；
OLAP：提供多维数据管理环境，其典型的应用是对商业问题的建模与商业数据分析。使分析人员、管理人员或执行人员能够从多角度对信息进行快速、一致、交互地存取，从而获得对数据的更深入了解
数据挖掘：使用诸如神经网络、规则归纳等技术，用来发现数据之间的关系，做出基于数据的推断，并根据这些推断进行预测和决策，最终完成商业智能的目标；

3.建立和管理数据仓库的主要任务
主要任务是将数据从源系统不断的自动抽取出来，并且按照一定的模型进行建模，这一过程也就是数据的抽取、归并、转换的过程。

4. 简述OLAP支持商业决策的特点和好处
如下：
a. 能即时的快速的提供整合性决策资讯。
b. 经常需要获取大量的历史数据来做趋势分析。
c. 需要对多维度数据进行复杂分析。
d. 经常需要以不同时间维度来比较，比如月、季度、年。
e. 用户需要的数据已经提前计算完成，查询速度很快。

...