第六章+大规模数据处理编程模型-20121025

1CloudComputingAutumn,2012Chapter6ProgrammingModelforMassiveDataProcessingXuJungang1202-2月-23CloudComputing,

GUCAS2提纲1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现3数据的爆炸性增长Source:IDC,“TheExpandingDigitalUniverse,”SponsoredbyEMC,updatedonMarch‘082005200620072008200920105年内10倍增长每年复合增长≈60%全球：5年内10倍增长中国：5年内30倍增长4互联网应用飞速发展搜索引擎Google百度必应…SNS网站Facebook人人网Linkedin开心网…...电子商务淘宝京东Amazon…微博Twitter新浪微博腾讯微薄…已经产生和正在产生大规模的海量的数据5云计算应用的迅速开展Google（GAE）Microsoft（WindowsAzure)Amazon（EC2,S3）IBM（BlueCloud）Salesforce(CRM）中国移动（BigCloud)……预期产生规模更大的海量数据6物联网未来应用无处不在流通环保农业工业个人生活……预期产生级数级增长的海量数据7大规模数据的特点V3Volume（量大）Varity（种类多）Velocity（变化快，即数据新增速度快）8大规模数据存储和处理要求和方案存储和管理存储PB级的处理存储多种多样的数据支持分布式处理处理PB级的多种数据低延迟读写速度成本较低的软硬件成本较低的人力成本分布式文件系统NoSQL数据库NoSQL数据库并行编程模型云计算开源软件902-2月-23CloudComputing,

GUCAS9提纲1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现10ParallelcomputingParallelcomputingisaformofcomputationinwhichmanycalculationsarecarriedoutsimultaneously,operatingontheprinciplethatlargeproblemscanoftenbedividedintosmallerones,whicharethensolvedconcurrently("inparallel").Thereareseveraldifferentformsofparallelcomputing:bit-level,instructionlevel,data,andtaskparallelism.11ParallelprogrammingmodelAparallelprogrammingmodelisaconceptthatenablestheexpressionofparallelprogramswhichcanbecompiledandexecuted.Thevalueofaprogrammingmodelisusuallyjudgedonitsgenerality:howwellarangeofdifferentproblemscanbeexpressedandhowwelltheyexecuteonarangeofdifferentarchitectures.Theimplementationofaprogrammingmodelcantakeseveralformssuchaslibrariesinvokedfromtraditionalsequentiallanguages,languageextensions,orcompletenewexecutionmodels.12并行编程的原因加快速度即在更短的时间内解决相同的问题或在相同的时间内解决更多更复杂的问题特别是对一些新出现的巨大的挑战问题，不使用并行计算是根本无法解决的1213并行编程的原因节省投入并行计算可以以较低的投入完成串行计算才能够完成的任务物理极限的约束光速是不可逾越的速度极限，设备和材料也不可能做得无限小，只有通过并行才能够不断提高速度1314并行编程的概念并行编程是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来进行计算。并行编程系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构成的集群。1415并行编程的分类目前最主要的并行编程模型：共享内存线程数据并行消息传递混合模型16共享内存模型在共享内存编程模型中，任务间共享统一的可以异步读写的内存地址空间。一般仅需指定可以并行执行的循环，而不需考虑计算与数据如何划分，以及如何进行任务间通信，编译器会自动完成上述功能。这个模型的优点是对于程序员来说数据没有身份的区分，不需要特别清楚任务间的数据通信。程序开发也相应的得以简化。典型代表是OpenMP编程模型。17线程模型在线程模型中，单个处理器可以有多个并行的执行路径。典型代表是Unix操作系统中基于POSIX接口的编程线程模型的构成如下：1.操作系统调度主程序a.out开始运行，a.out加载所有必要的系统资源和用户资源开始执行。2.a.out完成一些串行工作，然后创建一些可以被操作系统调度的并行任务（线程）去执行。3.每次线程都有自己的数据，而且共享整个a.out的资源。这样就节省了拷贝程序资源给每个线程的开销。这样线程之间可以并行执行子程序。4.线程之间通过全局内存进行通信。这个需要同步构造来确保多个线程不会同时更新同一块全局内存。5.线程执行完了就自动销毁，但是主程序a.out在应用程序完成之前一直存在，维护必要的共享资源。18数据并行编程模型数据并行即将相同的操作同时作用于不同的数据，数据并行编程模型提供给编程者一个全局的地址空间，一般这种形式的语言本身就提供并行执行的语义对于编程者来说，只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了数据并行的编程比如对于数组运算，使得数组B和C的对应元素相加后送给A，则通过语句

A=B+C（或其它的表达方式）

就能够实现上述功能，使并行机对B、C的对应元素并行相加，并将结果并行赋给A。数据并行的表达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行执行的。1819数据并行编程模型20数据并行编程模型数据并行模型有以下特性：并行工作主要是操纵数据集。数据集一般都是像数组一样典型的通用的数据结构。任务集都使用相同的数据结构，但是，每个任务都有自己的数据。每个任务的工作都是相同的。21消息传递并行编程模型消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达的并行算法，都可以用消息传递模型来实现，灵活性和控制手段的多样化，是消息传递并行程序能提供高的执行效率的重要原因。消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部分之间复杂的信息交换和协调、控制的任务交给了编程者，这在一定程度上增加了编程者的负担，这也是消息传递编程模型编程级别低的主要原因。2122消息传递并行编程模型23消息传递并行编程模型消息传递模型有以下三个特征：计算时任务集可以用他们自己的内存。多任务可以在相同的物理处理器上，同时可以访问任意数量的处理器。任务之间通过接收和发送消息来进行数据通信。数据传输通常需要每个处理器协调操作来完成。24消息传递与数据并行的对比2425消息传递与数据并行的对比数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据并行问题消息传递编程模型的编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。数据并行的主要特征是以数据为中心，通过对数据的划分和并行处理来解决问题消息传递当然也可以实现上述功能，但是消息传递在问题的表述上更具体，更低级，可以解决的问题相对于数据并行模型来说也更广泛。在一定程度上，可以把数据并行看作是消息传递的一种特殊形式。26消息传递与数据并行的对比2627混合模型这个模型中，通常是由两个或多个模型组合在一起实现的。当前通用的混合模型的例子就是：由消息传递模型（MPI）和线程模型（POSIX）或者共享内存模型（OpenMP）组成而成。混合模型中其他比较通用的模型是：将数据并行和消息传递组合起来。正如我们上面在数据并行模型部分提到的那样，在分布式体系结构上实现数据并行模型实际上是用消息传递的方法来为任务间传递数据的，对程序员是透明的。28现有主要编程模型OpenMPMPIDryadMapReduce2829OpenMP概述OpenMP应用编程接口API是在共享内存体系结构上的一个编程模型包含编译制导(CompilerDirective)、运行库例程(RuntimeLibrary)和环境变量(EnvironmentVariables)等组件。支持C/C++和Fortan等编程语言已经被大多数计算机硬件和软件厂家所标准化30OpenMP的历史1994年，第一个ANSIX3H5草案提出，被否决1997年，OpenMP标准规范代替原先被否决的ANSIX3H5，被人们认可1997年10月公布了与Fortran语言捆绑的第一个标准规范FORTRANversion1.0

1998年11月9日公布了支持C和C++的标准规范C/C++version1.0

2000年11月推出FORTRANversion2.0

2002年3月推出C/C++version2.0

2005年5月OpenMP2.5将原来的Fortran和C/C++标准规范相结合相关的规范在/drupal/node/view/831OpenMP程序结构基于Fortran语言的OpenMP程序的结构

PROGRAMHELLO

INTEGERVAR1,VAR2,VAR3

!Serialcode

…

!Beginningofparallelsection.Forkateamofthreads.

!Specifyvariablescoping

!$OMPPARALLELPRIVATE(VAR1,VAR2)SHARED(VAR3)

!Parallelsectionexecutedbyallthreads

…

!Allthreadsjoinmasterthreadanddisband

!$OMPENDPARALLEL

!Resumeserialcode

…

END

32OpenMP程序结构基于C/C++语言的OpenMP程序的结构

#include<omp.h> main(){ intvar1,var2,var3;

/*Serialcode*/ … /*Beginningofparallelsection.Forkateamofthreads*/ /*Specifyvariablescoping*/

#pragmaompparallelprivate(var1,var2)shared(var3)

{ /*Parallelsectionexecutedbyallthreads*/ … /*Allthreadsjoinmasterthreadanddisband*/ } /*Resumeserialcode*/ … }33MPIMPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准MPI是一种标准或规范的代表，而不特指某一个对它的具体实现MPI是一个库，而不是一门语言MPI库可以被FORTRAN77/C/Fortran90/C++调用。从语法上说它遵守所有对库函数/过程的调用规则，和一般的函数/过程没有什么区别。最终目的是服务于进程间通信这一目标。目前已经有MPI1和MPI2的标准。3334MPI发展历史3435典型MPI的实现典型的MPI实现包括：开源的MPICH、LAMMPI不开源的INTELMPI36MPICHMPICH是影响最大、用户最多的MPI实现由美国的Argonne国家实验室开发MPICH的特点：开放源码；与MPI标准同步发展；支持多程序多数据（MPMD）编程和异构集群系统；支持C/C++、Fortran77和Fortran90的绑定,支持类Unix和WindowsNT平台；支持环境非常广泛，包括多核、SMP、集群和大规模并行计算系统。37IntelMPI由Intel公司推出的符合MPI-2标准的MPI实现IntelMPI提供了名为DirectAccessProgrammingLibrary（DAPL）的中间层来支持多架构，兼容多种网络硬件及协议，优化网络互联IntelMPI透明地支持TCP/IP、Myrinet、共享内存，并基于DAPL有效支持多种高性能互联系统IntelMPI在通信协议的选择上无需进行额外设置，可自动选择MPI进程间最快的传输协议。38MPI程序的优点用户可以控制并行开发支持数据分布通信实现完全控制39MPI程序的缺点要求程序员显式地处理通信问题,如,消息传递调用的位置,数据移动,数据复制,数据操作,数据的一致性等等.

对大多数科学计算程序来说,消息传递模型的真正困难还在于显式的数据分解无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出来406个基本函数组成的MPI子集#include"mpi.h"/*MPI头函数，提供了MPI函数和数据类型定义*/intmain(intargc,char**argv){intrank,size,tag=1;intsenddata,recvdata;MPI_Statusstatus;MPI_Init(&argc,&argv);/*MPI的初始化函数*/MPI_Comm_rank(MPI_COMM_WORLD,&rank);/*该进程编号*/MPI_Comm_size(MPI_COMM_WORLD,&size);/*总进程数目*/416个基本函数组成的MPI子集if(rank==0){senddata=9999;MPI_Send(&senddata,1,MPI_INT,1,tag,MPI_COMM_WORLD);/*发送数据到进程1*/}if(rank==1)MPI_Recv(&recvdata,1,MPI_INT,0,tag,MPI_COMM_WORLD,&status);/*从进程0接收数据*/MPI_Finalize();/*MPI的结束函数*/return(0);}426个基本函数组成的MPI子集MPI初始化：通过MPI_Init函数进入MPI环境并完成所有的初始化工作。intMPI_Init(int*argc,char***argv)MPI结束：通过MPI_Finalize函数从MPI环境中退出。intMPI_Finalize(void)436个基本函数组成的MPI子集获取进程的编号：调用MPI_Comm_rank函数获得当前进程在指定通信域中的编号，将自身与其他程序区分。intMPI_Comm_rank(MPI_Commcomm,int*rank)获取指定通信域的进程数：调用MPI_Comm_size函数获取指定通信域的进程个数，确定自身完成任务比例。intMPI_Comm_size(MPI_Commcomm,int*size)446个基本函数组成的MPI子集消息发送：MPI_Send函数用于发送一个消息到目标进程。intMPI_Send(void*buf,intcount,MPI_Datatypedataytpe,intdest,inttag,MPI_Commcomm)消息接受:MPI_Recv函数用于从指定进程接收一个消息intMPI_Recv(void*buf,intcount,MPI_Datatypedatatyepe,intsource,inttag,MPI_Commcomm,MPI_Status*status)45MPI消息一个消息好比一封信消息的内容,即信的内容，在MPI中称为消息缓冲(MessageBuffer)消息的接收/发送者,即信的地址，在MPI中称为消息信封(MessageEnvelop)46MPI消息MPI中，消息缓冲由三元组<起始地址，数据个数，数据类型>标识消息信封由三元组<源/目标进程，消息标签，通信域>标识三元组的方式使得MPI可以表达更为丰富的信息，功能更强大47Dryad微软于2010年12月21日发布了分布式并行计算基础平台——Dryad测试版，成为谷歌MapReduce分布式数据计算平台的竞争对手。它可以使开发人员能够在Windows或者.Net平台上编写大规模的并行应用程序模型，并使在单机上所编写的程序很轻易的运行在分布式并行计算平台上程序员可以利用数据中心的服务器集群对数据进行并行处理，当程序开发人员在操作数千台机器时，而无需关心分布式并行处理系统方面的细节。4748Dryad4849DryadDryad同MapReduce一样，它不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Dryad这种编程模型并不仅适用于云计算，在多核和多处理器以及异构机群上同样有良好的性能。Dryad可以对计算机和它们的CPU进行调度，不同的是Dryad被设计为伸缩于各种规模的集群计算平台，无论是单台多核计算机还是到由多台计算机组成的集群，甚至拥有数千台计算机的数据中心，可以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。02-2月-23CloudComputing,

GUCAS4950Dryad02-2月-23CloudComputing,

GUCAS5051Dryad02-2月-23CloudComputing,

GUCAS5152Dryad优缺点优点：DryadLINQ具有声明式编程并将操作的对象封装为.NET类方便数据操作自动序列化和任务图的优化对Join进行了优化，得到了比BigTable+MapReduee更快的Join速率和更易用的数据操作方式

缺点它更适用于批处理任务，而不适用于需要快速响应的任务这个数据模型更适用于处理流式访问，而不是随机访问Dryad还是测试阶段尚未大规模普及，但是微软已经在AdCenter的生产系统中使用Dryad02-2月-23CloudComputing,

GUCAS5253MapReduce02-2月-23CloudComputing,

GUCAS53GoogleMapreduce架构设计师JefferyDeanJefferyDean设计一个新的抽象模型，使我们只要执行简单计算，而将并行化、容错、数据分布、负载均衡等杂乱细节放在一个库里，使并行编程时不必关心它们54MapReduceMapReduce是由Google公司的JeffreyDean和SanjayGhemawat开发的一个针对大规模群组中的海量数据处理的分布式编程模型。Map/Reduce是Hadoop的核心计算模型，它将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个函数，Map和Reduce

02-2月-23CloudComputing,

GUCAS5455MapReduceHistoryofMapReduceandHadoopFeb2003—FirstMapReduceLibrarywrittenatGoogleDec2004—GooglepaperpublishedJuly2005—DougCuttingreportsthatNutchnowusesnewMapReduceimplementationJan2006—DougCuttingjoinsYahoo!Feb2006—HadoopcodemovesoutofNutchintonewLucenesubprojectApr2007—Yahoo!runningHadoopon1000-nodeClusterJan2008—HadoopmadeanApacheTopLevelProjectFeb2008—Yahoo!GenerateproductionsearchindexwithHadoopJuly2008—HadoopWinsTerabyteSortBenchmarkJuly2009—NewHadoopSubprojects02-2月-23CloudComputing,

GUCAS5556MapReduce的应用在Google，MapReduce用在非常广泛的应用程序中，包括“分布排序，web连接图反转，每台机器的词矢量，web访问日志分析，反向索引构建，文档聚类,机器学习，基于统计的机器翻译"等.02-2月-23CloudComputing,

GUCAS5657MapReduce的应用基于Map/Reduce的Hadoop，被用到了facebook、twitter等著名网站中，国内的百度、淘宝、中移动也开展了对其的研究。02-2月-23CloudComputing,

GUCAS575802-2月-23CloudComputing,

GUCAS58提纲1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现59MapReduce02-2月-23CloudComputing,

GUCAS5960MapReduce产生背景据相关统计，每使用一次Google搜索引擎，Google的后台服务器就要进行1011次运算，如果没有好的负载均衡机制，有些服务器的利用率会很低，有些则会负荷太重，有些甚至可能死机，这些都会影响系统对用户的服务质量使用MapReduce这种编程模式，保持了服务器之间的均衡，提高了整体效率.02-2月-23CloudComputing,

GUCAS6061MapReduce产生背景MapReduce这种并行编程模式思想最早是在1995年提出的，当时提出的两个概念“map”和“fold”，与现在Google所使用“Map”和“Reduce”思想是吻合的。与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。通过这个接口，可以把大尺度的计算自动地并发好分布执行，从而使编程变得非常容易02-2月-23CloudComputing,

GUCAS6162MapReduce编程原理利用一个输入key/valuepair集合产生一个输出的key/valuepair集合需用户定义两个函数：Map和ReduceMap函数接受一个输入的Key/valuepair值，产生一个中间key/valuepair值MapReduce库把所有具有相同中间key值的中间value值集合在一起传递给reduce函数02-2月-23CloudComputing,

GUCAS6263MapReduce原理的要点一种简单化的并行编程模型，借用函数式编程中的Map和Reduce函数，将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个阶段数据分割、任务调度、故障处理等细节对程序员透明利用资源无关性的原理，提高处理效率合理的任务力度，优化容错处理和整体效率本地计算：充分利用数据的空间局部性来减少网络传输，节省宽带资源减少中间数据的产生，优化网络传输02-2月-23CloudComputing,

GUCAS6364MapReduce计算模型适合用MapReduce来处理的数据集（或任务）有一个基本要求：待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。MapReduce的计算模型如下：Map：（K1，V2）→list（K2，V2）Reduce：（K2，list（V2））→list（K3，V3）计算模型的核心是Map和Reduce两个函数，这两个函数由用户负责实现，功能是按一定的映射规则将输入的<key,value>对转换成另一个或一批<key,value>对输出02-2月-23CloudComputing,

GUCAS6465MapReduce计算过程MapReduce的计算过程就是将大数据集分解为成百上千的小数据集，每个（或若干个）数据集分别由集群中的一个节点（一般就是一台普通的计算机）进行处理并生成中间结果，然后这些中间结果又由大量的结点进行合并，形成最终结果02-2月-23CloudComputing,

GUCAS6566MapReduce计算过程对于程序员基于MapReduce计算模型编写分布式并行程序非常简单，程序员的主要工作就是实现Map和Reduce函数，其他的并行编程中的种种复杂问题，如分布式存储、工作调度、负载平衡、容错处理、网络通信等，均有MapReduce框架（比如Hadoop）负责处理，程序员完全不用操心。02-2月-23CloudComputing,

GUCAS6667并行编程模型大多数分布式运算可以抽象为任务分解和结果汇总（MapReduce）操作将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个阶段借用了Lisp中相似功能的名称，将这两个阶段分别用Map函数和Reduce函数命名，并将此计算模型命名为MapReduce自动分步到一个由普通机器组成超大集群上并发执行02-2月-23CloudComputing,

GUCAS6768MapReduce并行编程模型02-2月-23CloudComputing,

GUCAS6869MapReduce运行模型02-2月-23CloudComputing,

GUCAS69MapReduce的运行模型下图所示，图中有M个Map操作和R个Reduce操作70MapReduce运行模型02-2月-23CloudComputing,

GUCAS70一个Map函数就是对一部分原始数据进行指定的操作。每个Map操作都针对不同的原始数据，因此Map与Map之间是互相独立的，这就使得它们可以充分并行化。一个Reduce操作就是对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是互不交叉的，所有Reduce产生的最终结果经过简单连接就形成了完整的结果集，因此Reduce也可以在并行环境下执行。

71借用函数式中的Map和Reduce函数02-2月-23CloudComputing,

GUCAS71输入和输出：都是键值对集合用户指定一个映射函数处理一个键/值对来产生中间的键/值对集合，还指定一个缩减函数来合并所有的与同一中间键相关的中间值Map（in_key，in_value）→

list(out_key,intermediate_value)reduce(out_key,list(intermediate_value))→list(out_value)72MapReduce执行流程02-2月-23CloudComputing,

GUCAS7273MapReduce执行流程02-2月-23CloudComputing,

GUCAS73用户程序中的MapReduce函数库首先把输入文件分成M块，每块大概16M～64MB（可以通过参数决定），接着在集群的机器上执行处理程序。74MapReduce执行流程02-2月-23CloudComputing,

GUCAS74总共有M个Map任务和R个Reduce任务需要分派，Master选择空闲的Worker来分配这些Map或者Reduce任务。75MapReduce执行流程02-2月-23CloudComputing,

GUCAS75分配了Map任务的Worker读取并处理相关的输入块。它处理输入的数据并传递给用户定义的Map函数。Map函数产生的中间结果<key,value>对暂时缓冲到内存。76MapReduce执行流程02-2月-23CloudComputing,

GUCAS76缓冲到内存的中间结果将被定时写到MapWorker本地硬盘，这些数据通过分区函数分成R个区。中间结果在本地硬盘的位置信息将被发送回Master，然后Master负责把这些位置信息传送给ReduceWorker。77MapReduce执行流程02-2月-23CloudComputing,

GUCAS77当Master通知Reduce的Worker关于中间结果的位置时，它调用远程过程来从MapWorker的本地硬盘上读取缓冲的中间数据。当ReduceWorker读到所有的中间数据，它将对数据进行排序。78MapReduce执行流程02-2月-23CloudComputing,

GUCAS78ReduceWorker处理排序后的中间数据，并将处理得到的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果输出到一个最终的输出文件。79MapReduce案例：单词计数案例：单词计数问题（Wordcount)给定一个巨大的文本（如1TB），如何计算单词出现的数目?02-2月-23CloudComputing,

GUCAS79输入数据：文件所包含的信息输出数据：单词所出现的频率Hello:3World:2Bye:3Hadoop:4HelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoopMapReduce80MapReduce案例：单词计数使用MapReduce来解决该问题Step1：自动对文本进行分割

对文本分割HelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoopsplitsplitsplitHelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoop(K,V)(K,V)(K,V)81MapReduce案例：单词计数使用MapReduce来解决该问题Step2：在分割之后的每一对<key,value>进行用户定义的Map处理，再生成新的<key,value>对Split输出HelloWoldByeWoldHelloHadoopByeHadoopByeHadoopHelloHadoop<Hello,1><World,1><Bye,1><World,1><Hello,1><Hadoop,1><Bye,1><Hadoop,1><Bye,1><Hadoop,1><Hello,1><Hadoop,1>MapMapMapMap输出82MapReduce案例：单词计数02-2月-23CloudComputing,

GUCAS82使用MapReduce来解决该问题Step3：对输出的结果集排序、归拢（系统自动完成）Map输出<Hello,1><World,1><Bye,1><World,1><Hello,1><Hadoop,1><Bye,1><Hadoop,1><Bye,1><Hadoop,1><Hello,1><Hadoop,1><Hello,1><Hello,1><Hello,1><World,1><World,1><Bye,1><Bye,1><Bye,1><Hadoop,1><Hadoop,1><Hadoop,1><Hadoop,1>FoldFold输出83MapReduce案例：单词计数02-2月-23CloudComputing,

GUCAS83使用MapReduce来解决该问题Step4：对输出的结果集缩减，得出输出结果。Fold输出<Hello,1><Hello,1><Hello,1><World,1><World,1><Bye,1><Bye,1><Bye,1><Hadoop,1><Hadoop,1><Hadoop,1><Hadoop,1><Hello,3><World,2><Bye,3><Hadoop,4>ReduceReduce输出84并行执行02-2月-23CloudComputing,

GUCAS8485数据分割、任务调度、故障处理运行时系统负责：分割输入数据，在一系列机器之间调度程序的执行，处理机器故障，管理机器内部通信没有任何并行和分布式系统经验的程序员也能够容易地利用分布式系统的资源进行计算MapReduce包括三个不同类型的服务器：master、mapservers、reduceserversMaster分配用户给mapservers和reduceservers。它也跟踪任务的状态Mapservers接收用户输入，在它们上面执行映射操作，结果写入中间文件Reduceservers服务器接收由映射服务器产生的中间文件并在它们上面实行化简操作02-2月-23CloudComputing,

GUCAS8586本地计算Master根据数据的位置来分解任务使map任务和相关文件尽可能在同一机器上，或者至少在同一机架上，以减少网络传输Map（）任务的输入被分解为大小64KB的块和GFS的文件块相同，能够保证一个小数据集位于一台计算机上，便于本地计算02-2月-23CloudComputing,

GUCAS8687任务粒度Map任务的个数要远远大于机器的数量好处MinimizestimeforfaultrecoveryBetterdynamicloadbalancingE.g.MapReducecomputationswithMap=200000andReduce=5000,using2000workermachines02-2月-23CloudComputing,

GUCAS8788MapReduce的容错Worker故障Master周期性的ping每个worker。如果master在一个确定的时间范围内没有收到worker返回的信息，master将把这个worker标记为失效将这个worker所执行的Map任务重新分配给其它的worker重新执行该节点未完成的Reduce任务，已完成的不再执行Master故障定期写入检查点数据从检查点回复02-2月-23CloudComputing,

GUCAS8889MapReduce的优化任务备份机制慢的workers会