大规模数据处理编程模型.ppt

1,Cloud Computing,Autumn,2011,Chapter 6Programming Model for Massive Data ProcessingXu Jungang,1,2023/11/1,Cloud Computing,GUCAS,2,提纲,1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现,数据的爆炸性增长,Source:IDC,“The Expanding Digital Universe,”Sponsored by EMC,updated on March 08,全球：5年内10倍增长中国：5年内30倍增长,互联网应用飞速发展,搜索引擎Google百度必应SNS网站Facebook人人网Linkedin开心网.,电子商务淘宝京东Amazon微博Twitter新浪微博腾讯微薄,已经产生和正在产生大规模的海量的数据,云计算应用的迅速开展,Google（GAE）Microsoft（Windows Azure)Amazon（EC2,S3）IBM（BlueCloud）Salesforce(CRM）中国移动（BigCloud),预期产生规模更大的海量数据,物联网未来应用无处不在,流通环保农业工业个人生活,预期产生级数级增长的海量数据,大规模数据的特点,V3Volume（量大）Varity（种类多）Velocity（变化快，即数据新增速度快）,大规模数据存储和处理要求和方案,存储和管理存储PB级的处理存储多种多样的数据支持分布式处理处理PB级的多种数据低延迟读写速度成本较低的软硬件成本较低的人力成本,分布式文件系统NoSQL数据库,NoSQL数据库并行编程模型,云计算开源软件,2023/11/1,Cloud Computing,GUCAS,9,提纲,1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现,Parallel computing,Parallel computing is a form of computation in which many calculations are carried out simultaneously,operating on the principle that large problems can often be divided into smaller ones,which are then solved concurrently(in parallel).There are several different forms of parallel computing:bit-level,instruction level,data,and task parallelism.,Parallel programming model,A parallel programming model is a concept that enables the expression of parallel programs which can be compiled and executed.The value of a programming model is usually judged on its generality:how well a range of different problems can be expressed and how well they execute on a range of different architectures.The implementation of a programming model can take several forms such as libraries invoked from traditional sequential languages,language extensions,or complete new execution models.,并行编程的原因,加快速度即在更短的时间内解决相同的问题或在相同的时间内解决更多更复杂的问题特别是对一些新出现的巨大的挑战问题，不使用并行计算是根本无法解决的,12,并行编程的原因,节省投入并行计算可以以较低的投入完成串行计算才能够完成的任务物理极限的约束光速是不可逾越的速度极限，设备和材料也不可能做得无限小，只有通过并行才能够不断提高速度,13,并行编程的概念,并行编程是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来进行计算。并行编程系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构成的集群。,14,并行编程的分类,目前最主要的并行编程模型：共享内存线程数据并行消息传递混合模型,共享内存模型,在共享内存编程模型中，任务间共享统一的可以异步读写的内存地址空间。一般仅需指定可以并行执行的循环，而不需考虑计算与数据如何划分，以及如何进行任务间通信，编译器会自动完成上述功能。这个模型的优点是对于程序员来说数据没有身份的区分，不需要特别清楚任务间的数据通信。程序开发也相应的得以简化。典型代表是OpenMP编程模型。,线程模型,在线程模型中，单个处理器可以有多个并行的执行路径。典型代表是Unix操作系统中基于POSIX接口的编程,线程模型的构成如下：1.操作系统调度主程序a.out开始运行，a.out加载所有必要的系统资源和用户资源开始执行。完成一些串行工作，然后创建一些可以被操作系统调度的并行任务（线程）去执行。3.每次线程都有自己的数据，而且共享整个a.out的资源。这样就节省了拷贝程序资源给每个线程的开销。这样线程之间可以并行执行子程序。4.线程之间通过全局内存进行通信。这个需要同步构造来确保多个线程不会同时更新同一块全局内存。5.线程执行完了就自动销毁，但是主程序a.out在应用程序完成之前一直存在，维护必要的共享资源。,数据并行编程模型,数据并行即将相同的操作同时作用于不同的数据，数据并行编程模型提供给编程者一个全局的地址空间，一般这种形式的语言本身就提供并行执行的语义对于编程者来说，只需要简单地指明执行什么样的并行操作和并行操作的对象，就实现了数据并行的编程比如对于数组运算，使得数组B和C的对应元素相加后送给A，则通过语句A=B+C（或其它的表达方式）就能够实现上述功能，使并行机对B、C的对应元素并行相加，并将结果并行赋给A。数据并行的表达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行执行的。,18,数据并行编程模型,数据并行编程模型,数据并行模型有以下特性：并行工作主要是操纵数据集。数据集一般都是像数组一样典型的通用的数据结构。任务集都使用相同的数据结构，但是，每个任务都有自己的数据。每个任务的工作都是相同的。,消息传递并行编程模型,消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达的并行算法，都可以用消息传递模型来实现，灵活性和控制手段的多样化，是消息传递并行程序能提供高的执行效率的重要原因。消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部分之间复杂的信息交换和协调、控制的任务交给了编程者，这在一定程度上增加了编程者的负担，这也是消息传递编程模型编程级别低的主要原因。,21,消息传递并行编程模型,消息传递并行编程模型,消息传递模型有以下三个特征：计算时任务集可以用他们自己的内存。多任务可以在相同的物理处理器上，同时可以访问任意数量的处理器。任务之间通过接收和发送消息来进行数据通信。数据传输通常需要每个处理器协调操作来完成。,消息传递与数据并行的对比,24,消息传递与数据并行的对比,数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据并行问题消息传递编程模型的编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。数据并行的主要特征是以数据为中心，通过对数据的划分和并行处理来解决问题消息传递当然也可以实现上述功能，但是消息传递在问题的表述上更具体，更低级，可以解决的问题相对于数据并行模型来说也更广泛。在一定程度上，可以把数据并行看作是消息传递的一种特殊形式。,消息传递与数据并行的对比,26,混合模型,这个模型中，通常是由两个或多个模型组合在一起实现的。当前通用的混合模型的例子就是：由消息传递模型（MPI）和线程模型（POSIX）或者共享内存模型（OpenMP）组成而成。混合模型中其他比较通用的模型是：将数据并行和消息传递组合起来。正如我们上面在数据并行模型部分提到的那样，在分布式体系结构上实现数据并行模型实际上是用消息传递的方法来为任务间传递数据的，对程序员是透明的。,现有主要编程模型,OpenMPMPIDryad MapReduce,28,OpenMP概述,OpenMP应用编程接口API是在共享内存体系结构上的一个编程模型包含编译制导(Compiler Directive)、运行库例程(Runtime Library)和环境变量(Environment Variables)等组件。支持C/C+和Fortan等编程语言已经被大多数计算机硬件和软件厂家所标准化,OpenMP的历史,1994年，第一个ANSI X3H5草案提出，被否决 1997年，OpenMP标准规范代替原先被否决的ANSI X3H5，被人们认可1997年10月公布了与Fortran语言捆绑的第一个标准规范 FORTRAN version 1.0 1998年11月9日公布了支持C和C+的标准规范C/C+version 1.0 2000年11月推出FORTRAN version 2.0 2002年3月推出C/C+version 2.0 2005年5月OpenMP 2.5将原来的Fortran和C/C+标准规范相结合相关的规范在,OpenMP程序结构,基于Fortran语言的OpenMP程序的结构PROGRAM HELLOINTEGER VAR1,VAR2,VAR3!Serial code!Beginning of parallel section.Fork a team of threads.!Specify variable scoping!$OMP PARALLEL PRIVATE(VAR1,VAR2)SHARED(VAR3)!Parallel section executed by all threads!All threads join master thread and disband!$OMP END PARALLEL!Resume serial codeEND,OpenMP程序结构,基于C/C+语言的OpenMP程序的结构#include main()int var1,var2,var3;/*Serial code*/*Beginning of parallel section.Fork a team of threads*/*Specify variable scoping*/#pragma omp parallel private(var1,var2)shared(var3)/*Parallel section executed by all threads*/*All threads join master thread and disband*/*Resume serial code*/,MPI,MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准MPI是一种标准或规范的代表，而不特指某一个对它的具体实现MPI是一个库，而不是一门语言MPI库可以被FORTRAN77/C/Fortran90/C+调用。从语法上说它遵守所有对库函数/过程的调用规则，和一般的函数/过程没有什么区别。最终目的是服务于进程间通信这一目标。目前已经有MPI1和MPI2的标准。,33,MPI发展历史,34,典型MPI的实现,典型的MPI实现包括：,开源的MPICH、LAM MPI,不开源的INTEL MPI,MPICH,MPICH是影响最大、用户最多的MPI实现 由美国的Argonne国家实验室开发 MPICH的特点：开放源码；与MPI标准同步发展；支持多程序多数据（MPMD）编程和异构集群系统；支持C/C+、Fortran 77 和Fortran 90的绑定,支持类Unix和Windows NT平台；支持环境非常广泛，包括多核、SMP、集群和大规模并行计算系统。,Intel MPI,由Intel公司推出的符合MPI-2标准的MPI实现 Intel MPI提供了名为Direct Access Programming Library（DAPL）的中间层来支持多架构，兼容多种网络硬件及协议，优化网络互联Intel MPI透明地支持TCP/IP、Myrinet、共享内存，并基于DAPL有效支持多种高性能互联系统Intel MPI在通信协议的选择上无需进行额外设置，可自动选择MPI进程间最快的传输协议。,MPI程序的优点,用户可以控制并行开发支持数据分布通信实现完全控制,MPI程序的缺点,要求程序员显式地处理通信问题,如,消息传递调用的位置,数据移动,数据复制,数据操作,数据的一致性等等.对大多数科学计算程序来说,消息传递模型的真正困难还在于显式的数据分解无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出来,6个基本函数组成的MPI子集,#include mpi.h/*MPI头函数，提供了MPI函数和数据类型定义*/int main(int argc,char*argv)int rank,size,tag=1;int senddata,recvdata;MPI_Status status;MPI_Init(/*总进程数目*/,6个基本函数组成的MPI子集,if(rank=0)senddata=9999;MPI_Send(,6个基本函数组成的MPI子集,MPI初始化：通过MPI_Init函数进入MPI环境并完成所有的初始化工作。int MPI_Init(int*argc,char*argv)MPI结束：通过MPI_Finalize函数从MPI环境中退出。int MPI_Finalize(void),6个基本函数组成的MPI子集,获取进程的编号：调用MPI_Comm_rank函数获得当前进程在指定通信域中的编号，将自身与其他程序区分。int MPI_Comm_rank(MPI_Comm comm,int*rank)获取指定通信域的进程数：调用MPI_Comm_size函数获取指定通信域的进程个数，确定自身完成任务比例。int MPI_Comm_size(MPI_Comm comm,int*size),6个基本函数组成的MPI子集,消息发送：MPI_Send函数用于发送一个消息到目标进程。int MPI_Send(void*buf,int count,MPI_Datatype dataytpe,int dest,int tag,MPI_Comm comm)消息接受:MPI_Recv函数用于从指定进程接收一个消息int MPI_Recv(void*buf,int count,MPI_Datatype datatyepe,int source,int tag,MPI_Comm comm,MPI_Status*status),MPI消息,一个消息好比一封信消息的内容,即信的内容，在MPI中称为消息缓冲(Message Buffer)消息的接收/发送者,即信的地址，在MPI中称为消息信封(Message Envelop),MPI消息,MPI中，消息缓冲由三元组标识消息信封由三元组标识 三元组的方式使得MPI可以表达更为丰富的信息，功能更强大,Dryad,微软于2010年12月21日发布了分布式并行计算基础平台Dryad测试版，成为谷歌MapReduce分布式数据计算平台的竞争对手。它可以使开发人员能够在Windows或者.Net平台上编写大规模的并行应用程序模型，并使在单机上所编写的程序很轻易的运行在分布式并行计算平台上程序员可以利用数据中心的服务器集群对数据进行并行处理，当程序开发人员在操作数千台机器时，而无需关心分布式并行处理系统方面的细节。,47,Dryad,48,Dryad,Dryad同MapReduce一样，它不仅仅是一种编程模型，同时也是一种高效的任务调度模型。Dryad这种编程模型并不仅适用于云计算，在多核和多处理器以及异构机群上同样有良好的性能。Dryad可以对计算机和它们的CPU进行调度，不同的是Dryad被设计为伸缩于各种规模的集群计算平台，无论是单台多核计 算机还是到由多台计算机组成的集群，甚至拥有数千台计算机的数据中心，可以从任务队列中创建的策略建模来实现分布式并行计算的编程框架。,2023/11/1,Cloud Computing,GUCAS,49,Dryad,2023/11/1,Cloud Computing,GUCAS,50,Dryad,2023/11/1,Cloud Computing,GUCAS,51,Dryad优缺点,优点：DryadLINQ具有声明式编程并将操作的对象封装为.NET类方便数据操作 自动序列化和任务图的优化对Join进行了优化，得到了比BigTable+MapReduee更快的Join速率和更易用的数据操作方式 缺点它更适用于批处理任务，而不适用于需要快速响应的任务 这个数据模型更适用于处理流式访问，而不是随机访问 Dryad还是测试阶段尚未大规模普及，但是微软已经在AdCenter的生产系统中使用Dryad,2023/11/1,Cloud Computing,GUCAS,52,MapReduce,2023/11/1,Cloud Computing,GUCAS,53,Google Mapreduce架构设计师 Jeffery Dean,Jeffery Dean设计一个新的抽象模型，使我们只要执行简单计算，而将并行化、容错、数据分布、负载均衡等杂乱细节放在一个库里，使并行编程时不必关心它们,MapReduce,MapReduce 是由Google公司的Jeffrey Dean 和 Sanjay Ghemawat 开发的一个针对大规模群组中的海量数据处理的分布式编程模型。Map/Reduce 是 Hadoop的核心计算模型，它将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个函数，Map 和 Reduce,2023/11/1,Cloud Computing,GUCAS,54,MapReduce,History of MapReduce and HadoopFeb 2003First MapReduce Library written at GoogleDec 2004Google paper publishedJuly 2005Doug Cutting reports that Nutch now uses new MapReduce implementationJan 2006DougCutting joins Yahoo!Feb 2006Hadoop code moves out of Nutch into new Lucene subproject Apr 2007Yahoo!running Hadoop on 1000-node ClusterJan 2008Hadoop made an Apache Top Level ProjectFeb 2008Yahoo!Generate production search index with HadoopJuly 2008Hadoop Wins Terabyte Sort BenchmarkJuly 2009New Hadoop Subprojects,2023/11/1,Cloud Computing,GUCAS,55,MapReduce的应用,在Google，MapReduce用在非常广泛的应用程序中，包括“分布排序，web连接图反转，每台机器的词矢量，web访问日志分析，反向索引构建，文档聚类,机器学习，基于统计的机器翻译等.,2023/11/1,Cloud Computing,GUCAS,56,MapReduce的应用,基于Map/Reduce 的Hadoop，被用到了facebook、twitter等著名网站中，国内的百度、淘宝、中移动也开展了对其的研究。,2023/11/1,Cloud Computing,GUCAS,57,2023/11/1,Cloud Computing,GUCAS,58,提纲,1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现,MapReduce,2023/11/1,Cloud Computing,GUCAS,59,MapReduce产生背景,据相关统计，每使用一次Google搜索引擎，Google的后台服务器就要进行1011次运算，如果没有好的负载均衡机制，有些服务器的利用率会很低，有些则会负荷太重，有些甚至可能死机，这些都会影响系统对用户的服务质量使用MapReduce这种编程模式，保持了服务器之间的均衡，提高了整体效率.,2023/11/1,Cloud Computing,GUCAS,60,MapReduce产生背景,MapReduce这种并行编程模式思想最早是在1995年提出的，当时提出的两个概念“map”和“fold”，与现在Google所使用“Map”和“Reduce”思想是吻合的。与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。通过这个接口，可以把大尺度的计算自动地并发好分布执行，从而使编程变得非常容易,2023/11/1,Cloud Computing,GUCAS,61,MapReduce编程原理,利用一个输入key/value pair集合产生一个输出的key/value pair集合需用户定义两个函数：Map和ReduceMap函数接受一个输入的Key/value pair值，产生一个中间key/value pair值MapReduce库把所有具有相同中间key值的中间value值集合在一起传递给reduce函数,2023/11/1,Cloud Computing,GUCAS,62,MapReduce原理的要点,一种简单化的并行编程模型，借用函数式编程中的Map和Reduce函数，将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个阶段数据分割、任务调度、故障处理等细节对程序员透明利用资源无关性的原理，提高处理效率合理的任务力度，优化容错处理和整体效率本地计算：充分利用数据的空间局部性来减少网络传输，节省宽带资源减少中间数据的产生，优化网络传输,2023/11/1,Cloud Computing,GUCAS,63,MapReduce计算模型,适合用MapReduce来处理的数据集（或任务）有一个基本要求：待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。MapReduce的计算模型如下：Map：（K1，V2）list（K2，V2）Reduce：（K2，list（V2）list（K3，V3）计算模型的核心是Map和Reduce两个函数，这两个函数由用户负责实现，功能是按一定的映射规则将输入的对转换成另一个或一批对输出,2023/11/1,Cloud Computing,GUCAS,64,MapReduce计算过程,MapReduce的计算过程就是将大数据集分解为成百上千的小数据集，每个（或若干个）数据集分别由集群中的一个节点（一般就是一台普通的计算机）进行处理并生成中间结果，然后这些中间结果又由大量的结点进行合并，形成最终结果,2023/11/1,Cloud Computing,GUCAS,65,MapReduce计算过程,对于程序员基于MapReduce计算模型编写分布式并行程序非常简单，程序员的主要工作就是实现Map和Reduce函数，其他的并行编程中的种种复杂问题，如分布式存储、工作调度、负载平衡、容错处理、网络通信等，均有MapReduce框架（比如Hadoop）负责处理，程序员完全不用操心。,2023/11/1,Cloud Computing,GUCAS,66,并行编程模型,大多数分布式运算可以抽象为任务分解和结果汇总（MapReduce）操作将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个阶段借用了Lisp中相似功能的名称，将这两个阶段分别用Map函数和Reduce函数命名，并将此计算模型命名为MapReduce自动分步到一个由普通机器组成超大集群上并发执行,2023/11/1,Cloud Computing,GUCAS,67,MapReduce并行编程模型,2023/11/1,Cloud Computing,GUCAS,68,MapReduce运行模型,2023/11/1,Cloud Computing,GUCAS,69,MapReduce的运行模型下图所示，图中有M个Map操作和R个Reduce操作,MapReduce运行模型,2023/11/1,Cloud Computing,GUCAS,70,一个Map函数就是对一部分原始数据进行指定的操作。每个Map操作都针对不同的原始数据，因此Map与Map之间是互相独立的，这就使得它们可以充分并行化。一个Reduce操作就是对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是互不交叉的，所有Reduce产生的最终结果经过简单连接就形成了完整的结果集，因此Reduce也可以在并行环境下执行。,借用函数式中的Map和Reduce函数,2023/11/1,Cloud Computing,GUCAS,71,输入和输出：都是键值对集合用户指定一个映射函数处理一个键/值对来产生中间的键/值对集合，还指定一个缩减函数来合并所有的与同一中间键相关的中间值Map（in_key，in_value）list(out_key,intermediate_value)reduce(out_key,list(intermediate_value)list(out_value),MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,72,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,73,用户程序中的MapReduce 函数库首先把输入文件分成M 块，每块大概16M64MB（可以通过参数决定），接着在集群的机器上执行处理程序。,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,74,总共有M 个Map 任务和R 个Reduce任务需要分派，Master 选择空闲的Worker 来分配这些Map 或者Reduce 任务。,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,75,分配了Map任务的Worker读取并处理相关的输入块。它处理输入的数据并传递给用户定义的Map函数。Map函数产生的中间结果对暂时缓冲到内存。,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,76,缓冲到内存的中间结果将被定时写到Map Worker本地硬盘，这些数据通过分区函数分成R个区。中间结果在本地硬盘的位置信息将被发送回Master，然后Master负责把这些位置信息传送给Reduce Worker。,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,77,当Master通知Reduce的Worker关于中间结果的位置时，它调用远程过程来从Map Worker的本地硬盘上读取缓冲的中间数据。当Reduce Worker读到所有的中间数据，它将对数据进行排序。,MapReduce执行流程,2023/11/1,Cloud Computing,GUCAS,78,Reduce Worker处理排序后的中间数据，并将处理得到的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果输出到一个最终的输出文件。,MapReduce案例：单词计数,案例：单词计数问题（Word count)给定一个巨大的文本（如1TB），如何计算单词出现的数目?,2023/11/1,Cloud Computing,GUCAS,79,输入数据：文件所包含的信息,输出数据：单词所出现的频率,Hello:3World:2Bye:3Hadoop:4,Hello World Bye WorldHello Hadoop Bye HadoopBye Hadoop Hello Hadoop,MapReduce,MapReduce案例：单词计数,使用MapReduce来解决该问题,Step 1：自动对文本进行分割,对文本分割,Hello World Bye WorldHello Hadoop Bye HadoopBye Hadoop Hello Hadoop,split,split,split,Hello World Bye World,Hello Hadoop Bye Hadoop,Bye Hadoop Hello Hadoop,(K,V),(K,V),(K,V),MapReduce案例：单词计数,使用MapReduce来解决该问题Step 2：在分割之后的每一对进行用户定义的Map处理，再生成新的对,Split输出,Hello Wold Bye Wold,Hello Hadoop ByeHadoop,Bye Hadoop Hello Hadoop,Map,Map,Map,Map输出,MapReduce案例：单词计数,2023/11/1,Cloud Computing,GUCAS,82,使用MapReduce来解决该问题Step 3：对输出的结果集排序、归拢（系统自动完成）,Map输出,Fold,Fold输出,MapReduce案例：单词计数,2023/11/1,Cloud Computing,GUCAS,83,使用MapReduce来解决该问题Step 4：对输出的结果集缩减，得出输出结果。,Fold输出,Reduce,Reduce输出,并行执行,2023/11/1,Cloud Computing,GUCAS,84,数据分割、任务调度、故障处理,运行时系统负责：分割输入数据，在一系列机器之间调度程序的执行，处理机器故障，管理机器内部通信没有任何并行和分布式系统经验的程序员也能够容易地利用分布式系统的资源进行计算MapReduce包括三个不同类型的服务器：master、mapservers、reduceserversMaster分配用户给mapservers和reduceservers。它也跟踪任务的状态Mapservers接收用户输入，在它们上面执行映射操作，结果写入中间文件Reduceservers服务器接收由映射服务器产生的中间文件并在它们上面实行化简操作,2023/11/1,Cloud Computing,GUCAS,85,本地计算,Master根据数据的位置来分解任务使map任务和相关文件尽可能在同一机器上，或者至少在同一机架上，以减少网络传输Map（）任务的输入被分解为大小64KB的块和GFS的文件块相同，能够保证一个小数据集位于一台计算机上，便于本地计算,2023/11/1,Cloud Computing,GUCAS,86,任务粒度,Map任务的个数要远远大于机器的数量好处Minimizes time for fault recoveryBetter dynamic load balancing computations with Map=200000 and Reduce=5000,using 2000 worker machines,2023/11/1,Cloud Computing,GUCAS,87,MapReduce的容错,Worker故障Master周期性的ping每个worker。如果master在一个确定的时间范围内没有收到worker返回的信息，master将把这个worker标记为失效将这个worker所执行的Map任务重新分配给其它的worker重新执行该节点未完成的Reduce任务，已完成的不再执行Master故障定期写入检查点数据从检查点回复,2023/11/1,Cloud Computing,GUCAS,88,MapReduce的优化,任务备份机制慢的workers会严重地拖延整个执行完成的时间由于其他的任务占用了资源磁盘损坏解决方案：在临近结束的时候，启动多个进程执行尚未完成的任务谁先完成，就算谁可以十分显著地提高效率,2023/11/1,Cloud Computing,GUCAS,89,MapReduce的实现,Google公司提出了基于GFS的C+版本的MapReduce实现，但是该实现属于Google公司的保密技术，未开源开源MapReduce实现：HadoopQizmtPhoenix,2023/11/1,Cloud Computing,GUCAS,90,2023/11/1,Cloud Computing,GUCAS,91,提纲,1.大规模数据处理2.并行编程3.MapReduce基本原理4.MapReduce的实现,Hadoop,Hadoop实现了Google的MapReduce编程模型，提供了简单易用的编程接口，也提供了它自己的分布式文件系统HDFS与Google不同的是，Hadoop是开源的，任何人都可以使用这个框架来进行并行编程。,2023/11/1,Cloud Computing,GUCAS,92,Hadoop中的MapReduce,Hadoop JobHadoop中所有MapReduce程序以Job形式提交给集群运行。一个MapReduce Job被划分为若干个Map Task和Reduce Task并行执行。一个Job的提交包括数据和程序(Jar文件)的提交。,2023/11/1,Cloud Computing,GUCAS,93,Hadoop中的MapReduce,Combine(连接）对Map任务的结果，先进行连接，将中间结果中有相同key和value的进行合并，与reduce类似。可以减少生成对的数目。Partion(分区）Combine之后，把产生的中间结果按key的范围划分成R份，划分时通常采用Hash函数来完成：hash(key)%R,Hadoop中的MapReduce,读取中间结果Map任务的中间结果在做完Combine和Partion后，以文件形式存于本地磁盘。中间结果文件的位置会通知主控JobTracker，JobTracker再通知Reduce任务到哪一个DataNode上去取中间结果。每个Reduce需要向多个Map任务取数据。,Hadoop中的MapReduce,2023/11/1,Cloud Computing,GUCAS,96,Job运行时控制流和数据流,Hadoop中的MapReduce,2023/11/1,Cloud Computing,GUCAS,97,Job 执行流程,Qizmt,Qizmt是MySpace的开源MapReduce框架，可用于在大规模Windows集群上开发或运行分布式计算程序Qizmt是以Windows平台的C#开发，.NET的开发人员可以利用已有的技术编写MapReduce功能,2023/11/1,Cloud