云计算中的MapReduce并行编程模式研究_吴贵鑫.docx

《云计算中的MapReduce并行编程模式研究_吴贵鑫.docx》由会员分享，可在线阅读，更多相关《云计算中的MapReduce并行编程模式研究_吴贵鑫.docx（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 1 绪论 1. 1云计算研究现状 云计算 1是并行计算、分布式计算和网格计算的发展，是虚拟化、效用计 算、将基础设施作为服务 IaaS、 将平台作为服务 PaaS和将软件作为服务 SaaS 等概念混合演变和升华的结果。云计算是多种计算技术混合演变的结果，其在 技术性方面有较高的成熟度，而且又有大公司的积极推动，所以云计算一经提 出，发展就极为迅速。 Google、 亚马逊、 IBM、 微软和 Yahoo等公司是云计算 技术的领先者和引导者。云计算领域的众多成功公司还包括 VMware、 Salesforce、 Facebook、 YouTube、 MySpace 等。 Google是最大的

2、云计算技术的使用者。 Google搜索引擎就是使用分布在 200多个站点、超过 100万台的服务器的支撑之上建立起来的，而且其服务器 设施的数量还在迅速的增加。 Google公司的一系列成功应用的系统平台，包括 Google地球、地图、 Gmail、 Docs等也同样使用了这些云计算设备。用户采用 Google Docs之类的应用平台，其数据信息会存放在互联网上的某个位置，且用 户可以使用任何一个与互联网相连的终端设备，非常方便地访问和共享这些数 据信息。目前 ， Google已经向第三方开放其云计算设施，用户可以通过使用 Google Engine2来运行大型地并行应用。 Google不保守

3、的特点是最值得称 颂的，它早在 2004年就以发表学术论文 3的形式公开其云计算的三大法宝： GFS、 MapReduce和 Bigtable， 并在美国、中国等高校开设如何进行云计算编程 的课程。随之而来，就会产生很多模仿者，其中最受关注的开源项目就是 Hadoop 亚马逊为了向企业提供计算和存储服务，开发了弹性计算云 EC2 (Elastic Computing Cloud)和简单存储服务 S3 (Simple Storage Service)。 其提供包括存 储空间、带宽、 CPU资源以及月租费等收费的服务项目。月租费与我们平常使 用的电话月租费类似；存储空间、带宽按容 量收费，用户可以

4、通过亚马逊提供 的服务接口将任意类型的文件临时或者永久地存储在 S3服务器上； CPU资源 的使用则是根据运算时长收费。 IBM在 2007年 11月推出了 “ 改变游戏规则 ” 的 “ 蓝云 ” 计算平台 4，目 的是为广大客户带来 “ 即买即用 ” 的云计算平台。它是由一系列自我管理和自2 我修复的虚拟化云计算软件来组成的，世界上不同地域的用户都能够很方便地 使用这些分布式的大型服务器计算节点，在数据中心的计算应用就好像运行在 互联网环境中。IBM与欧洲 17个组织开展合作，提出一个 RESERVOIR云计算 项目，以实现 “ 无障碍的资源和服务虚拟化 ” ，欧盟为该项目提供了 1.7亿欧

5、元 的资金。 2008年 8月， IBM宣布将投资约 4亿美元来改造其设在北卡罗来纳州 和日本东京的云计算数据中心，并计划 2009年在 10个国家投资 3亿美元建设 13个云计算中心。 微软是以发展终端产品为主的，在云计算时代软件免费的商业模式迅速发 展时期，微软也在 2008年 10推出了一个名叫 Windows Azure的云计算系统。 Azure (译为 “ 蓝天 ” ）是以互联网架构为基础打造的新型云计算操作平台，这 是继 Windows取代 DOS之后微软的一次重要的战略性产品 。 Windows Azure云 计算平台的底层是由分布在全球的第四代数据中心组成的微软全球基础性服务

6、系统 。 Windows Azure云计算平台提供了能够通过互联网访问的基础设施，包 括处理器、存储设备和服务等，用户和企业也在微软云计算平台上运行自己的 应用程序和存储数据。目前，微软己经配置了 220个集装箱式数据中心，其中 包括 44万台服务器。 在我国，云计算的发展也非常迅速。 2008年， IBM先后在无锡和北京建立 了两个云计算中心；世纪互联推出了 CloudEx产品线，提供 互联网主机服务、 在线存储虚拟化服务等；中国移动研究院已经建立起 1024个 CPU的云计算试 验中心。作为云计算技术的一个分支，云安全技术通过大量客户端的参与和大 量服务器端的统计分析来识别病毒和木马，取得

7、了巨大成功。瑞星、江民、金 山、 360安全卫士等均推出了云安全解决方案。值得一提的是，云安全的核心 思想，与早在 2003年就提出的反垃圾邮件网格非常接近 5。 2008年 11月 25日，中国电子学会专门成立了云计算专家委员会。已经成 立的中国电子学会云计算专家委员会充分发挥专家资源，跟踪国内外云计算相 关技 术的最新发展，加强云计算领域的交流与合作，推动国内云计算技术的研 究开发与应用，为政府和行业主管部门提供准确及时的决策建议。 2009年 5月 22日，中国电子学会隆重举办首届中国云计算大会。 2009年 11月 2日，中国 互联网大会专门召开了 “2009 云计算产业峰会 ” 。

8、2009年 12月，中国电子学会 举办了中国首届云计算学术会议， 2010年 5月，中国电子学会接着举办了第二 届中国云计算大会，极大地促进了国内云计算技术的发展。 3 1. 2 MapReduce产生背景及意义 MapReduce是 Google提出的一个基于云计算体系的编程架构，是一种处理 海量数据的并行编程模式，用于大规模数据集（通常大于 1TB)的并行计算。 “Map (映射 ） ” 、“Reduce (化简 ） ” 的概念和主要思想，都来源于函数式编程语言和 矢量编程语言 3 。正是因为 MapReduce有着函数式和矢量编程语言的共同特点， 使得这种编程模式特别适合于非结构化和结构

9、化的海量数据的搜索、挖掘、分 析与机器智能学习等应用，极大的简化了并行程序设计的难度。 实际上， MapReduce这种并行编程模式思想最早是在 1995年由 John Darlington6等提出的 ， John Darlington 首次提出了 “ map” 和 “ fold” 的概 念，与现在 Google所使用的 “ Map” 和 “ Reduce” 思想是类似的。 Google绝大部分的计算应用在概念上都是很简单的，不过每个应用所输入 的数据量通常是非常庞大的，并且为了使计算能在合理的时间内执行完毕，每 个应用的数据计算必须分发到上百个或者上千个计算节点上去执行。如何并发 地执行计算

10、，如何为每个计算任务分配数据，如何处理计算任务失败等等相关 问题联系在一起，为了解决这些问题往往会造成使用很复杂 的代码才能解决原 本很简单的计算问题。 Google为了降低这种复杂度，设计了一种新的能够方便处理这类简单计算 的模式 MapReduce。 有些计算问题原本是很简单的，但是我们要处理并发细 节，容错机制，以及数据分布策略，负载均衡等等细节问题导致了程序的代码 非常复杂，难于编写。所以可以把这些所有计算应用都存在的问题封装到一个 库中，由一个系统整体来负责。而将对数据的计算任务抽象为 map和 reduce两 个概念，这种抽象的来源是基于 Lisp以及其它多种函数式语言的 map和

11、 reduce 概念。很多对数据的计算任务都和 map相关，这些 map负责处理输入数据中的 每个逻辑 “ record” ， 并且产生一组中间的 key/value键值对，接着对所有具 有相同 key的中间结果上执行 reduce操作，对 map操作所产生的中间结果进行 合并，从而生成最终计算结果。 fcpReduce对于大规模数据集的计算操作，是由一个主节点管理和控制的， 具体的计算任务由主节点来分发到各子节点共同完成，通过这种方式 MapReduce 实现并行任务的可靠执行与容错机制。在每个时间周期，主节点都会对各个子 节点的工作状态进行 标记，一旦子节点状态标记为死亡状态，则这个节点的

12、所 4 有任务都将分配给其他的子节点重新执行。 与传统的分布式程序设计模式相比， MapReduce对并行处理、容错处理、 本地化计算、负载均衡等细节进行了封装，还提供了一个简单而功能强大的接 口。通过这个接口，可以把大数据量的计算任务自动的并发和分布执行，运行 时系统会解决输入数据的分配问题，跨越集群节点的程序执行和调度，处理节 点的失效，并且管理节点之间的通讯信息。从而使并行程序的编写变得非常容 易，程序员不需要有什么并发处理或者分布式编程的经验，就可以使用超 大的 分布式系统的资源。而且还可以通过由一般 PC组成的高性能集群来达到极高的 性能，具有很好的经济性。并且， MapReduce

13、也具有很好的通用性，许多不同 类型的计算应用都可以简单地通过 fcpReduce编程模型来解决。 根据相关统计，每使用一次 Google搜索引擎， Google的后台服务器就要 进行 1011次运算。对于这么庞大的运算量，如果没有较好的负载均衡机制，有 些服务器的利用率会很低，有些服务器则会负荷过重，有些甚至可能会死机， 这些都会影响用户的使用质量。而 MapReduce这种编程模式的使用，就 使服务 器保持了很好的均衡，提高了整体的执行效率。 MapReduce编程模型已经在 Google的多个领域成功的应用。对于这种成功 的原因我们归结为几个方面：首先，由于 MapReduce封装了并行处

14、理、容错处 理、数据本地化优化、负载均衡等等技术难点的细节，这使得即便对于完全没 有并行或者分布式系统开发经验的程序员来说， MapReduce也较易于使用；其 次，大量不同类型的问题都可以通过 MapReduce简单的解决。例如 ， MapReduce 用于生成 Google的网络搜索服务所需要的数据、用来排序、用来数据挖掘、用 于机器学习，以及很多其它的系统；第三，可以实现一个在数千台计算机组成 的大型集群上灵活部署运行 fcpReduce。 这个实现使得有效利用这些丰富的计 算资源变得非常简单，因此用来解决 Google遇到的其他很多需要大量计算的问 题也是很适合的。 我们从 MapRe

15、duce的程序开发过程中可以看出：首先，约束编程模式使得 并行和分布式计算变得非常容易，也易于建立容错机制；其次，网络带宽是比 较稀有的资源。许多对于并行计算的优化都是针对减少网络传输数据为目的的， 本地数据计算的优化使得大量的数据信息无需通过网络来传送，而直接从本地 磁盘读取，中间文件写入本地磁盘，并且只写一份中间文件也节约了网络带宽； 第三，多次执行类似或相同的作业可以减少低速节点带来的负面影响，同时解 5 决了由于节点失效所造成的数据丢失问题。 1. 3本文主要研究内容 本文首先介绍了云计算的概念、基本理论，阐述了并行编程模式的原理和 发展。并与传统并行编程模式 MPI进行比较，研究两者

16、的区别与各自优势。分 析了 fcpReduce解决问题的原理、具体步骤和方法。 最后，介绍了 MapReduce在异构环境下的性能差异，分析了异构环境对 MapReduce性能的影响。提出一种新的数据分配机制，以提高 MapReduce在异 构环境下的性能。 1. 4论文结构 第一章为绪论部分，简要地阐述了云计算的研究现状，概括了 MapReduce 并行编程模式产生的背景，介绍了本文的主要研究内容，最后说明了本文的组 织结构。 第二章为并行程序设计理论的分析。本章首先简要介绍了传统的并行程序 开发环境，包括消息传递模式 MPI、 共享存储编程模型 OpenMP和混合编程模 式，阐明了三者的特

17、点及其原理。接着介绍了 Google云计算的原理，并对实现 MapReduce并行编程模型的 Hadoop开源分布式计算架构做了简要的阐述。最后 我们比较了 MPI和 MapReduce这两种流行的并行编程模式，对这两种并行程序 开发模型进行详细地研究，分析了两者的区别和联系。 第三章为 MapReduce并行编程模式研究。本章首先简要地介绍了 MapReduce并行编程思想，阐述了 MapReduce的编程模型，分析了 MapReduce 模型的实现机制。接着介绍了 MapReduce的工作原理，对 MapReduce作业的提 交，初始化，任务 的分配与执行，作业的进度和状态的更新等进行了详

18、细的阐 述。最后分析了在 Hadoop集群中 MapReduce作业的调度方式。 第四章为异构环境下的数据分配机制研究。简要介绍了 Hadoop分布式文件 系统HDFS。 分析了异构环境下集群中数据存储的特点，阐述了异构环境对 MapReduce性能的影响。提出一种数据分配机制的改进策略 HDDM， 阐明如何利 用数据的分配来改进 MapReduce的执行性能，从而提高整个异构集群的效率。 第五章是用实例来测试数据分配机制，从而验证该策略的有效性。 第六章总结了本论文的主要研究内容和主要成果，并对今后的工作进进行 6 了进一步的阐述。 1. 5本章小结 本章首先简要地阐述了国内外云计算的研究现

19、状，接着又分析了 MapReduce 并行编程模式的产生背景及意义，最后介绍了本文的主要研究内容。7 2并行程序设计相关理论 2. 1传统的并行程序开发环境 在传统的并行编程模型中比较流行的是消息传递模型 MPI， 共享存储模型 OpenMP以及 MPI和 OpenMP混合编程三种开发模式。 2. 1. 1消息传递机制 MPI MPI (Message Passing Interface)是一种目前广泛应用的消息传递编程 模型 31，用于开发基于消息传递的并行程序，它为用户提供一个实际可用的、 可移植的、高效的和灵活的消息传递接口库。它定义了一个实现消息传递模型 标准的程序库，而不是一门语言，

20、它提供的接口可以方便使用 C/C+和 FORTRAN 语言调用。 MPICH是一种最重要的 MPI实现，其版本与 MPI规范制定同步，是 MPI-2的完全实现。 MPICH除包含 MPI函数库之外，还包含了一套程序设计以及 运行环境。 MPI作为一种可以被广泛使用的编写消息传递程序的并行编程标准， 要求将任务分解成多个子任务，启动多个进程对每个任务并行执行，每个进程 不能直接访问其它进程中的数据，各进程之间的数据交换操作通过消息传递来 实现。 使用 MPI的并行程序可以不做修改的运行在 PC机、工作站、机群系统和 MPP系统上，无论这些机器使用何种操作系统，这也是它能够广泛流行的原因。 MPI

21、已在 IBMPC机上、 Windows上、所有主要的 Unix工作站上和所有主流的并 行机上得到实现。 基于消息传递的 MPI:并行程序执行模式主要有以下两种： 1) SPMD (单程序多数据流）模式： SPMD是将同一程序复制到各个处理器 上，而不同的数据分布在不同的处理器上。在系统中各个处理器上运行 着相同的程序，而处理的对象是不同的数据，如图 2-1所示。 2) MPMD (多程序多数据流）模式： MPMD是指每个处理器执行不同的程序 代码，独自完成对不同数据的运算。在如事务处理的应用中，由于各个 子功能自身的异构性，以及在异构网络中，各个计算资源存在差异性， 使用 MPMD结构进行程序

22、设计是很合适的。 8 MPI并行程序是由多个进程组成的，程序在初始化的过程中生成一定数目 的进程。各进程都包含于通信域之内。通信域由通信组、通信上下文等组成。 通信域中的所有进程组合在一起就形成了进程组，进程组中的每个进程通过相 互发送和接收消息来进行通信。通常情况下， MPI程序需要六个基本的函数， 分别用来完成 MPI程序的初始化和结束、获取 a前进程及指定通信域的进程数 目、完成消息的发送和接收等功能。图2-2反应了使用 MPI进行并行程序设计 时的流程。图 2_1 SPMD执行模式 Fig.2-1 SPMD execution mode 9 图 2-2 MPI程序设计流程图 Fig.2

23、-2 MPI programming flow chart 2. 1. 2 OpenMP并行编程模型 10 图 2-3 Fork-Join并行执行模型 Fig.2-3 Fork-Join parallel execution model OpenMP标准是共享存储体系结构上一个比较典型的编程模型。它是基于编 译制导的，具有简单、移植性好和可扩展等优点，是共享存储系统并行编程的 一个工业标准。实际上， OpenMP并不是一种新的语言，它是对基本语言（如 Fortran99、 C、 C+等）的扩展。 OpenMP规范中定义的一系列的编译制导指令、 运行库和环境变量，用于与编译器和运行使系统进行交互

24、，能够使用户在保证 程序的可移植性的前提下，按照标准将已有的串行程序逐步并行化。 OpenMP是基于线程的并行编程模型，一个共享存储的进程由多个线程组成。 OpenMP使用 Fork-Join并行执行模型，如图 2-3所不。 mm mm OpenMP在开始执行时一般有一个主线程在工作，在程序执行过程中主线程 会在进入并行域时才会进行并行执行，接下来执行过程如下： 1) FORK过程：创建 FORK子线程，每个子线程并行执行并行域中的代码， 并行域中的代码在不同的线程中并行执行。 2) JI0N过程：当离开并行域时，所有子线程都会被同步或者被中断，只 有主线程继续执行。 一般我们是在 C/C+或

25、 Fortran程序代码中嵌入编译制导语句来实现 OpenMP程序的并行化。而且还可以在别的并行结构中嵌入 OpenMP应用编程接 口 （ API)的并行结构。对于不同的并行域 （ Parallel Region)应用编程接口 可以根据需要动态地改变线程数。2. 1. 3混合编程 11 随着多核技术的发展，高性能计算集群的结构也越来越复杂。集群中多个 CPU或者多个核之间使用高速总线或者交叉开关连接起来，并通过它们访问共 享的内存区域和 I/O设备等。集群中的各个节点之间通过通信网络（例如 Infiniband、 以太网 ）连接起来，并且节点间通过传递消息进行通信。在这种情 况下，单一的使用一

26、种并行编程模式很难同时发挥集群中多核多处理的优势， 使用多种并行编程模式的混合编程能够很好的解决这一问题。 目前比较流行的混合编程是 MPI+OpenMP， 在一个并行应用程序开发中同时 使用MPI和 OpenMP两种模式。融合了消息传递和共享内存编程模型的各自优点， 适合于开发基于 SMP并行体系结构的并行应用程序，充分发挥这种体系结构的 长处，提高并行体系结构的使用效率，加速了应用程序的运行性能。对于 MPI+OpenMP的混合编程模式来说，使用 MPI能够提高节点间的并行性，同时使 用 OpenMP来提升节点内的并行性。也就是说首先使用 MPI程序在各计算节点上 产生进程，再由 Open

27、MP在节点内部产生线程。使用 MPI为主程序框架，对于每 个 MPI进程内部可以并行化的区域可采用 OpenMP来对其进行编译制导的并行 化。使用 MPI+OpenMP混合编程模式的模型结构图如图 2-4所示。 MPI并行位于 上层，用来表示节点间的并行； OpenMP位于底层，用来表示节点内的并行。进 行并行编程时首先对问题进行 MPI分解，各个 MPI进程被分配到一个 SMP节点 上，进程间通过消息传递机制交换信息；然后在每个 MPI进程中，使用 OpenMP 制导指令创建一组线程，并分发到 SMP节点的不同处理器上并行地运行。 图 2-4混合编程模式的结构 Fig.2-4 The str

28、ucture of hybrid programming model 12 混合编程模型可以充分发挥两种编程模式的优点， MPI能够很好的解决多 处理器间的粗粒度通信问题，而 OpenMP提供轻量级的线程能够解决每个多处理 器计算机内各个处理器之间的交互工作。与 MPI模式相比， MPI+ OpenMP混合 编程使用快速的共享内存访问机制来代替节点内的消息传递，降低了节点内通 信的开销。另外，当 MPI进程的数目增加到一定程度时，并行程序的性能通常 也会下降。而在混合编程模型中由于 MPI的进程数等于集群节点的个数而不是 MPI模式中的处理器数量。这样，使得在保持并行程序运行的处理器数量不变

29、的前提下进程数目大大地降低。因此，混合编程模型有一定的可扩展性优势。 2. 2云计算技术 云 （ Cloud)是网络的象征，因此云计算 （ Cloud Computing)， 最广义的解 释就是“ 网络计算 ” 。云计算 7是一种商业化的计算模型，它将计算任务分布在 大量计算机构成的资源池上，使用户能够按照需求来获取计算能力、存储空间 和信息服务。这种资源池称为 “ 云 ” 。它们是一些可以自我维护和管理的虚拟计 算资源，通常表现为一些大型的服务器集群，包括计算集群、存储服务器等。 云计算将这些计算资源集中起来，使用专门软件实现自动化管理，无需人为的 参与。用户可以随时申请计算资源，支持各种应

30、用程序的运行，无需再为烦琐 的细节而困惑，使用户可以更专注的实现自己的工作。 云计算技术方兴未艾， Google、 亚马逊、 IBM、 微软和 Yahoo等信息巨头 都在努力打造自己的云计算系统，积极推行云计算的发展。值得注意的是，随 着云计算技术的深入发展，不同的云计算实现方案之间想到相互融合，同一种 项目内往往存在两种以上的类型。例如 ，亚马逊是以 IaaS发展的，但它所提出 的弹性 MapReduce服务就是参照和模仿了 Google公司的 MapReduce。 2. 2. 1 Google云计算原理 Google的整个云计算体系主要包括分布式文件系统 GFS、 面向并行计算的 编程模式

31、 MapReduce和结构化的 BigTable存储系统三大部分。 GFS (Google File System) 8是一个可扩展、结构化、具有日志功能的分 布式文件系统，能够进行大数据量、分布式的读写操作。对于 Google系统中上 层的分布式应用程序来说， GFS赋予上层很高的灵活性和可操作性，对于操作 系统甚至是硬件层的操作权力，开发者能够轻易的获得，可以根据特定的需求 13 来控制文件在不同磁盘空间的读写操作。 GFS通常包括一个控制中心 （ Master)、 多个数据服务器 （ Chunkserver) 以及客户机 （ Client)， 运行在 GFS上的所有应用程序都是在普通 L

32、inux系统的 用户态进程中运行的。在 GFS系统中，每个文件被分隔成固定大小的数据块 (Chunk),存储在数据服务器 （ Chunkserver)中，通过増加数据块一定程度的 冗余保证数据的可靠性。在进行数据块读写操作时，系统使用系统所赋予的全 局唯一的 ID标识来识别数据块。 Master负责管理 GFS文件系统中所有的元数 据信息，包括文件的命名空间、访问控制信息等内容。另一方面， fcstei 还管 理着 Chunkserver与 Client之间的数据传输，并且负责整个系统的负载均衡、 数据块的分配和定位以及数据服务器状态的监控等。 Client是所有应用获取 GFS数据服务的入口

33、。应用程序通过 Client与 Master和 Chunkserver通信， 并使用 GFS的 API来读写数据。 建立在大型数据存储能力基础之上的处理操作，必须要赋予程序员分布式 的应用程序开发能力。 MapReduce模型的出现将开发者所关注的逻辑问题与分 布式编程所涉及的繁琐问题隔离开来，通过 MapReduce提供的编程模型屏蔽底 层实现细节来完成并行应用程序的开发，从而服务于 Google绝大多数的数据处 理工作。 在并行计算实现环节上，首先， MapReduce提供的编程模型会跨越大量数 据节点将任务分割，并将输入数据划分后分配给下层计算节点，在计算节点上 开发者定义 Map函数来

34、处理 “ 键 /值 ” 对，并生成 “ 键 /值 ” 对集 合形式的中间 结果，之后根据开发者定义的 Reduce函数将所有中间结果进行合并，完成任务 的处理。并行应用在执行过程中，输入数据的划分、节点业务执行调度、容错 处理以及节点间信息交换等细节都将由 MapReduce提供的编程模型来实现。通 过 MapReduce提供的编程模型，可以将许多真实世界的计算任务抽象后使用分 治规约的方法实现。基于 MapReduce模式编写的并行程序可能仅仅很短的代码 就能够完成复杂的分布式计算任务。 BigTable是一个分布式的结构化数据存储系统， Google的很多项目使用 Bigtable 存储数

35、据，包括 Web 索引 、 Google Earth、 Google Finance。 BigTable 是一个分布式的、稀疏的、有序的多维度 Map， 在设计上具备很好的伸缩性以 及高可用性的特点。每个 Table都是一个由行和列组成的多维稀疏图，并且每 个存储单元对应有一个时间戳。Table的索引从行关键字、列关键字和时间戳 14 三个维度建立，每个索引值都使用一个字符数组进行存放。 2. 2. 2 Hadoop云计算系统 最流行的云计算开源系统 Hadoop9模仿了 Google云计算的主要技术。 Hadoop的三大核心设计是 HDFS、 MapReduce和 HBase,它们分别是 G

36、oogle云计 算最核心技术 GFS、 MapReduce和 BigTable的开源实现。 Hadoop是 Apache开 源组织的一个分布式计算架构，能够在大量廉价的硬件设备组成的集群系统上 运行分布式程序，为应用程序提供了一组高效可靠的接口，旨在建立一个具有 高效率、可靠性高和良好扩展性的分布式系统。随着云计算的迅速流行 ， Hadoop 项目也被越来越多的个人和企业用户 2)所运用，本文也是在Hadoop集群的基础 上来对 MapReduce编程模式进行研究的。 Hadoop源自于两个开源项目 Lucene和 Nutch， 它们之间是一脉相承的。 Lucene是一个用 Java语言开发的

37、高性能全文检索工具包，它并不是一个完整 的应用程序，而是一套简单易用的 API库。它可以很方便地嵌入到各种实际的 应用程序中，实现搜索和索引功能。 Nutch是第一个开源的 Web搜索引擎，它 是在 Lucene的基础上増加了网络爬虫、与 Web相关的一些功能以及一些解析各 类文档格式的插件等，还包含一个分布式文件系统来存储数据。从 NutchO. 8.0 开始，将其中实现分布式文件系统和 MapReduce算法的代码独立出来，形成了 一个新的开源项目 Hadoop。 HDFS 是 Hadoop 分布式文件系统 1Q (Hadoop Distibuted File System)的 缩写，是分

38、布式计算的存储结构。 HDFS具有高容错性的特点，它能够部署在大 量廉价的硬件设备上，适合那些具有海量数据集的应用，并且为数据读写操作 提供了较高的吞吐率。 HDFS能够对数据进行可扩展的访问，通过简单地往集群 中增加节点就能够解决大量用户同时访问的问题。 HDFS支持传统的层 次文件组 织结构，与现有的一些文件系统操作相似，可以对文件进行创建、删除、重命 名等操作。 MapReduce是一种并行编程模式，能够在大型集群上执行分布式应用，具 有简单性和高可用性特点。 Hadoop开源实现了 Google的 fcpReduce模型，该 部分和 Google相同。MapReduce是一种简化的并行

39、计算模型，主要由 Map和 Reduce两部分组成，分别进行对任务的分解和对中间结果的汇总。基于这个计 算模型，并行程序的编写将变得非常简单，用户甚至不需要具有并行程序的开 15 发经验，就可以很方便地编 写出分布式的并行程序，完成对大量数据的计算。 冊 &3611也是此 (1 (项目的一个重要组成部分，它是一个开源的、支持结 构化数据存储的、基于列存储模型的分布式数据库。 Hadoop除了开源之外，还具有可扩展、经济性、高可靠性、高效率等优点。 计算和的存储可扩展性都是 Hadoop的设计根本。 Hadoop集群可以由廉价的普 通 PC来组成，具有很高的经济性。 HDFS的高容错性特点又保证

40、了分布式计算 的可靠性。 分布式文件系统 HDFS以及 MapReduce编程模型相结合，实现 Local Data 处理的模式，实现了对数据信息的高效处理。这是 Hadoop实现分布式计算的最 大优势。集群中每台计算机对存储在本地磁盘的数据进行计算，这种本地计算 的模式减少了数据信息在网络上的传输量，降低对网络带宽的需求。在现有的 大型分布式并行计算系统中，进行分布计算应用时由于大量的数据需要频繁地 在不同的计算机之间传输，往往极大的占用网络带宽，成为制约分布计算性能 的瓶颈。而 Hadoop的 “ 本地计算 ” 方式就成为了一种有效节约网络带宽的机 制，人们把这喻为 “ 移动计算比移动数据

41、更经济 ” 。 2. 3 MapReduce 与 MPI 的联系 MPI是并行计算时代标准的程序设计方法，广泛地应用中各种大规模并行 处理机上。MPI擅长于编写计算密集型应用程序，现在的大量数值计算程序都 是采用 MPI编写的。即使在网格计算时代，也有专门的 MPI标准实现一一 MPICH-G212， 能够在网格环境下方便地为计算密集型应用编写 MPI程序，对于 在网格环境下 MPI的使用在文献 12中有详细介绍。用 MPI在程序设计上有较大 的自由度， MPI有着良好的并行程序执行效率，我们甚至可以用 MPI来实现 Hadoop中的 Map和 Reduce的功能 19。在 MPI中就存在对各

42、节点数据的归约 (Reduce)操作，能够很方便地完成多个节点向主节点的归约，并提供了相应 的函数支持，如 MPI_Reduce函数。 归约函数说明： int MPI_Reduce (void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_0p op, int root, MPI_Comm comm) 并行编程模式 MapReduce则是云计算时代的关键核心技术。云计算时代最 显著的特征就是对大规模数据的处理， 因此 MapRedcue模式对数值密集型应用16 能够进行很好的处理。事实上在 Hadoop中我们也能找

43、到很多 MPI的影子，如 Hadoop中的分布式文件系统 HDFS和 MapReduce处理是主从结构的，而主从结 构也是 MPI并行程序的一种重要设计方法。 下面着重分析 MapReduce与 MPI之间的差异。 1) MPI没有分布式文件系统支持 MPI是一种基于消息传递机制的并行编程标准，为并行程序开发者提供了 功能强大的通信函数，在 MPI中关于点对点的通信或组级通信都有相应的函数， 对于 MapReduce的标志性处理 - 归约 （ Reduce)也有相应的函数调用。 然而 MPI虽然能提供强大的并行计算能力，但它没有一个分布式文件系统 在底层对其进行支持。对于计算密集型应用 MPI

44、尚能较好的处理，然而在处理 数据密集型应用时，由于在 MPI中计算与数据的存储是分开的，因此在各个节 点之间存在大量的数据交换。子节点往往只负责计算工作，所有的数据都需要 从主节点通过网络传向子节点，这样在程序执行时存在着严重的网络延迟，影 响并行程序的执行效率。如果有分布式文件系统36支持的情况下，将计算和存 储在同一个节点上进行，子节点就能够从本地 磁盘直接读取数据信息。我们认 为 MPI在应用于数据密集或数据和计算同时密集的任务时由于没有分布式文件 系统的支持将面临很大的困难，所以 MPI现在主要应用在科学计算领域。 2) MapReduce能够处理节点的失效 MPI在设计之初是面向高性

45、能服务器的，从设计理念上假设了服务器是不 会失效的，所有节点和网络通信在计算过程是可以保证正常的，因而如果 MPI 在运行过程中出现节点失效及网络通信中断，则只有返回并退出， MPI没有提 供一套机制处理节点失效后的备份处理方案问题。所以如果中途出现问题所有 的计算将重新开始 ，这是非常耗费时间的。从根本上分析， MPI无法应用节点 失效的问题原因还是没有分布式文件系统的支持，特别是带有数据块备份能力 的分布式文件系统。如果 MPI是运行在一个具有数据块备份策略的分布式文件 系统上的，那么 MPI在某节点失效后会在该数据块的备份节点上重启这部分计 算而不会使整个程序全部退出，但是如果没有这一文

46、件系统的支持，则节点失 效后该主节点将无法找到一个新的节点来接着执行当前的任务，只能全部退出。 从云计算发展的趋势和 Google成功的经验来看，今后不可信 服务器节点的 采用将会成为一个重要的方向，在集群系统中不可信服务器是一个廉价的节点， 服务器失效会成为一种常态化的现象，我们通常会容忍不可信节点以一种相对 17 高的概率出现故障，特别是在集群规模很大的时候，集群出现失效节点的概率 将会相当高，因此从系统设计上我们必须保证在节点失效后系统能够继续正常 运行下去。MapReduce编程模式内部封装了容错处理机制，能够很好的应对集 群中各种节点的失效情况，适宜于在云计算环境下编写各种分布式应用

47、程序。 3)在数据处理方式上的不同 MPI与 fcpReduce在数据处理上的差异主要体现在数据存储与数据处理在 系统中的位置不同，如图 2-5所示。 MPI是计算与存储分离， MapReduce是计算 向存储迁移。 在 MPI中数据存储的节点和数据处理的节点往往是不同的，一般在每次计 算开始时 MPI需要从数据存储节点读取需要处理的数据分配给各个计算节点对 数据进行处理，因此 MPI中数据存储和数据处理是分离的。对于计算密集型的 应用 MPI能有较好的性能表现，但对于处理 TB级数据的数据密集型应用由于网 络数据传输速度很慢， MPI的性能会大大降低，甚至会到无法忍受的地步，所 以对构建在

48、MPI上的并行计算系统网络通信速度一直是一个重要的性能指标， 用 “ 计算换通信 ” 也是 MPI并行程序设计中的基本原则。 在 Hadoop中 MapReduce由于有 HDFS文件系统的支持，数据是分布式存储 在各个节点的，计算时各节点读取存储在自己节点的数据进行处理，从而避免 了大量数据在网络上的传递，实现 “ 计算向存储的迁移 ” 。处理 TB级的海量数 据这种方式有很大的优势，这也是为何 Hadoop在搜索引擎系统中能很好运行的 原因，因为搜索引擎系统是最典型的数据密集型应用，需要对惊人数量的网页 数据进行管理和处理。 图 2-5 MPI与 MapReduce在数据处理上的差异 Fig.2-5 Differences between MPI and MapReduc