（计算机应用技术专业论文）基于gpgpu的mapreduce高性能并行计算模型研究与应用.pdf

桂林理工大学硕士学位论文 摘要 随着硬件技术的迅猛发展带来了图形处理器的革新，这个原本只是用于图形数 据处理的设备现在却变得举足轻重，它拥有高带宽和高度并行计算的能力使得在大 规模数据集运算的应用上，它在性能上有比目前的c p u 更具优势。 而互联网的发展也带来了数据的爆炸式增长，如何在这些海量数据中获取有价 值的信息已经成为每个人都需要面对的问题。g o o g l e 公司在这个方面成为了技术的 引导者，它的开发人员设计并实现了一个仅仅通过普通计算机集群的组合以及在集 群中运行的高性能并行计算平台，拥有这个平台能得到过去只有购买昂贵大型专用 服务器才有的大规模计算能力，这就是m a p r e d u c e 并行计算模型，目前m a p r e d u c e 模型现被应用于天文信息计算处理、病毒库存储、网络检索服务等方面，这个模型 能够解决数据爆炸式增长带来的计算机存储能力和计算能力不足之间的矛盾。 本文结合上面二者的长处，提出研究和实现一个完整的高性能并行计算系统， 它以g p u 为硬件基础并配合基于m a p r e d u c e 并行计算模型平台进行大规模数据处理。 首先我们给出基于m a p r e d u c e 并行计算模型平台的系统架构，该架构为客户端一 管理节点一工作节点三层。客户端通过命令行的方式提交任务；管理节点接收任务并 进行分析，把任务拆分成多块，分配给它所管理的工作节点，然后调用工作节点进 行计算；最后的工作节点是本论文研究和设计的重点，工作节点首先对g p u 设备初 始化并把计算任务分配给c p u 和g p u ，由二者互相配合，共同完成数据的计算，充分 利用系统空闲的资源和获得更多的计算能力。 最后我们在已经部署好的平台上，进行测试系统性能的实验，通过基于c p u 的 m a p r e d u c e 集群方式执行计算和本系统计算的对比实验，获得的结果表明这种基于 g p g p u 的m a p r e d u c e 并行计算模型具有比前者更高的效率。 关键词：m a p r e d u c e ，h a d o o p ，图形处理器，通用图形处理器，c u d a i i 桂林理工大学硕士学位论文 a b s t r a c t t h e r a p i dd e v e l o p m e n to fh a r d w a r em a k e st h eh u g er e g e n e r a t i o no fg p u i to f t e n u s e dt oh a n d l eg r a p h i c sd a t a b u tn o wi th a st h eh u g eb a n d w i d t ha n dp a r a l l e l sc o m p u t i n g a n di th a sg o o dp e r f o r m a n c eo nc o m p u t i n gt h em a s s i v ed a t as e t a l o n gw i t ht h ef a s td e v e l o p m e n to fi n t e r n e t ，t h ed a t ap r o d u c e db yw e bi n c r e a s e s h e a v i l y i ti st h ep r o b l e mt oe v e r y b o d yh o wt og e tt h ev a l u ei n f o r m a t i o n g o o g l ec o m p a n y d e v e l o p e rd e s i g n sa n di m p l e m e n t sah i 曲p e r f o r m a n c ec o m p u t i n gp l a t f o r mb yc o m m o n l y c o m p u t e rc l u s t e r i th a sc o m p u t i n gm a s s i v ed a t as e tb e t t e rt h a nc o s t l yh u g es p e c i a ls e r v e r t h a ti st h em a p r e d u c e p a r a l l e l sc o m p u t i n gm o d e l n o wt h em a p r e d u c em o d e lu s e dt o m a n a g ea s t r o n o m yi n f o r m a t i o na n dt os t o r ev i r u sl i b r a r ya n dt os e a r c hi n t e r n e ts e r v i c e i t c a nr e s o l v et h ep r o b l e mo f s t o r i n ga b i l i t ya n dc o m p u t i n ga b i l i t yb ym a s s i v ed a t as e t w ec o m b i n eg p ua n dt h em a p r e d u c et or e s e a r c ha n di m p l e m e n tt h eh u g e p e r f o r m a n c ec o m p u t i n gs y s t e m i tb a s eo ng p uh a r d w a r ea n du s et h em a p r e d u c e p a r a l l e l sc o m p u t i n gm o d e lo ni t a b o v ea l lw eb r i n gt h es y s t e mp l a t f o r mo ft h em a p r e d u c ep a r a l l e l sc o m p u t i n g m o d e l t h ep l a t f o r mh a st h r e el a y e r s o n ei st h ec l i e n tn o d e t w oi st h em a s t e rn o d e t h e l a s ti st h es l a v en o d e t h ec l i e n tn o d ep u tt h et a s kt ot h em a s t e rn o d eb yc o m m a n dl i n e t h em a s t e rn o d eg e t st h et a s ka n da n a l y s e si t t h e ni ts p l i t st h et a s ka n dd i s t r i b u t e st h e t a s kt ot h es l a v en o d e i nt h ee n di tl e tt h es l a v en o d et or u nt h et a s k f i n a l l y , t h es l a v e n o d ei st h em o s ti m p o r t a n ti no u ra r t i c l e t h es l a v en o d ei n i t i a l i z e sg p ua n ds p l i tt h et a s k f o rc p ua n dg p u t h e yw o r kt o g e t h e ra n df i n i s ht h ec o m p u t i n go ft h et a s k f i n a l l y , w er u nt h es y s t e mt e s to nd e p l o yp l a t f o r m a st h ep a r a l l e l sc o m p u t i n go ft h e m a p r e d u c ep l a t f o r mb a s eo nc p u c o n t r a s tt ob a s eo ng p u i t sr e s u l ts h o w st h ep a r a l l e l s c o m p u t i n ge f f i c i e n c yo ft h em a p r e d u c ep l a t f o r mb a s eo ng p u b e t t e rt h a nt h ec p u k e y w o rd ：m a p r e d u c e ，h a d o o p ，g p u ，g p g p u ，c u d a i i i 桂林理工大学硕士学位论文 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已经发 表或撰写过的研究成果，也不包含为获得其它教育机构的学位或证书而使用过的材 料。对论文的完成提供过帮助的有关人员已在论文中作了明确的说明并表示谢意。 学位论文作者( 签字) ： 签字日期： 学位论文版权使用授权书 本学位论文作者完全了解( 学校) 有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的印刷本和电子版本，允许论文被查阅和借阅。本 人授权( 学校) 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提 供信息服务。( 保密的学位论文在解密后适用本授权书) 导师签字 签字日期： 防日 桂林理工大学硕士学位论文 1 1 研究背景 第1 章引言 近年来在硬件技术推动下，图形处理器( g p u ) 的计算能力和可编程能力得到快速 的发展，具有高度并行化计算的特点使得g p u 不再局限于日常的图形处理任务，开始 涉及更为广泛的高性能通用计算( g p g p u ) 领域n 6 2 3 1 。因为g p u 拥有高性能的多处理器 阵列与高带宽、隐藏延迟的显存系统口4 1 ，这使得在大量重复数据集运算和密集内存存 取的计算应用上，g p u 具有比传统c p u 更具优势。而且常用数据和程序的计算都需要靠 c p u 来完成，对用户而言，如果过多的占用c p u 的时间会使得用户运行大型程序或者进 行比较大的数据计算时感觉计算机很慢，降低系统性能；g p u 在普通用户中主要用于游 戏或图形的计算，空闲时间明显多于c p u ，因此适度使用g p u 会带来良好的效果，即降 低了c p u 的占用时间，又能使处于过度空闲的g p u 得到充分利用眩驯。 同样在高性能并行计算领域得到关注的热点是m a p r e d u c e 海量数据处理框架。，通 过廉价的普通计算机集群我们能得到过去只有昂贵大型服务器才拥有的大规模数据计 算能力，而且在稳定性和扩展性等方面比后者更好。现在m a p r e d u c e 模型现被应用于 天文信息计算处理、海量病例存储分析、病毒库存储、网络检索服务等方面阳引，解 决数据爆炸式增长与计算机存储能力和计算能力不足之间的矛盾。 到目前为止很多对这两方面的研究都局限在某些方面，如针对单台计算机g p u 协 助c p u 对算法和程序进行加速以及由多台计算机g p u 组成的集群来进行分布式计算， 不可否认这些方面都取得相当大的进展，但不足也是存在的。在面对规模越来越大的 游戏和程序时单台计算机g p u 加速并不能带来多么大的改观，数据海量的增长和计算 机的计算能力之间的矛盾不会得到解决；同样普通分布式计算机g p u 集群虽然在计算 能力方面很不错，但是一旦出现节点故障或其他的问题，整个集群的性能会受到很大 的影响：还有m a p r e d u c e 模型进行m a p 和r e d u c e 操作时需要频繁的c p u 进行计算，有 时甚至c p u 占用率为百分之百，因此也非常必要使用g p u 的参与来平衡系统的计算能 力。 桂林理工大学硕士学位论文 1 2 本文的主要内容和工作 如前所述，本文将把g p u 通用计算和m a p r e d u c e 模型二者的优点相结合，研究和 实现一个完整的高性能并行计算系统，以g p u 为硬件基础配合基于m a p r e d u c e 并行计 算模型软件进行大规模数据处理。 本文的创新点在于以下方面： ( 1 ) 实现使用g p u 配合c p u 计算的通用框架，利用纹理表示向量、矩阵等数据结 构，使得数据和并行计算的程序部分在g p u 上存储和运行。该框架在图形硬件和应用 程序之间形成一个抽象层，具有很强的通用型，最大限度减少g p u 和c p u 的通信，提 高系统整体的计算能力和改善系统性能。 ( 2 ) 通过对基于m a p r e d u c e 的分布式计算框架的研究，提出了对基于g p u 的分布 式计算改进，通过这种改进可以利用现有的计算设备来达到更高的并行计算速度。最 后给出了一个改进的原型实现，并给出了相关的实验数据。 ( 3 ) 对g p u 和m a p r e d u c e 模型的发展前景做出了展望。 1 3 论文结构 本论文分为五章： 第一章对课题的研究背景、研究内容和主要的工作进行了简要的说明。 第二章阐述了目前研究热点“云计算技术，并详细介绍“云计算”技术带来的 m a p r e d u c e 海量数据处理模型，最后介绍了m a p r e d u c e 海量数据处理模型的实现h a d o o p 平台。 第三章简单叙述g p u 目前的发展和应用，还介绍了相关概念g p g p u ( g p u 通用计算) ， 最后详细给出了g p u 通用计算的开发工具c u d a 的内容以及如何利用c u d a 对g p u 进行 通用计算开发。 第四章列出了基于g p g p u 的m a p r e d u c e 并行计算模型详细设计思路和实现方式， 并给出了部分相关的代码，最后进行实验和得到最终的结果进行评估。 第五章对本课题研究工作进行总结和展望，指出未来需要进一步改进的方面。 2 桂林理工大学硕士学位论文 第2 章m a p r e d u c e 高性能并行处理模型及其相关技术介绍 m a p r e d u c e 是著名搜索引擎g o o g l e 公司研究人员提出并实现的一种高性能并行数 据处理模型，用来加工、生成和处理海量数据3 。提到m a p r e d u c e 模型不得不解释另一 个概念云计算( c l o u dc o m p u t i n g ) 啪n 4 扪，m a p r e d u c e 模型不仅来源于云计算技 术的提出，而且随着云计算技术的高速发展，m a p r e d u c e 模型被更为广泛的应用。在本 章中，将详细介绍云计算相关理论和m a p r e d u c e 模型的概念。 2 。1 云计算概述 2 1 1 云计算的定义 云计算( c l o u dc o m p u t i n g ) 是一种新兴的商业计算模型，是分布式计算 ( d i s t r i b u t e dc o m p u t i n g ) 、并行计算( p a r a l l e lc o m p u t i n g ) 和网格计算口1 1 3 ( g r i d c o m p u t i n g ) 的发展，同时也是虚拟化1 ( v i r t u a l i z a t i o n ) 、效用计算1 ( u t i l i t y c o m p u t i n g ) 、基础设施即服务n o m l l ( i a a s ) 、平台即服务1 1 1 ( p a a s ) 、软件即服务1 1 m 2 1 ( s a a s ) 等概念混合演进并跃升的结果。 2 1 2 云计算的原理 云计算将计算任务分布在大量计算机构成的资源池上，而非本地的单台计算机或 者单台大型的远程服务器上，使用户终端能够根据自己的需要获取计算能力、存储空 间和各种软件服务。这种资源池是一些可以自我维护和管理的虚拟计算资源，通常包 括计算服务器、存储服务器、宽带资源等。 简单来说就是云计算简化了用户终端的功能，把所有虚拟的计算能力和资源转化 为计算力提供给云计算中每一个用户终端来使用。用户所需的应用程序并不需要运行 在用户的个人电脑、手机等终端设备上，而是运行在互联网的大规模服务器集群中。 用户所处理的数据也并不存储在本地，而是保存在互联网的数据中心里面。用户只需 要一个终端，如一台显示器或一个手机，就可以通过网络所提供的服务来实现用户所 需要的一切功能和操作。 3 桂林理工大学硕士学位论文 2 1 3 云计算的特点 ( 1 ) 超大规模。g o o g l e 云计算已经拥有1 0 0 多万台服务器，a m a z o n 、i b m 、微软、 y a h o o 等的“云”均拥有几十万台服务器b 3 。云计算能赋予用户前所未有的计算能力。 ( 2 ) 虚拟化。云计算支持用户在任意位置、使用各种终端获取应用服务。只需要 一台笔记本或者一个手机，就可以通过网络服务来实现用户需要的一切，甚至包括超 级计算这样的任务。 ， ( 3 ) 高可靠性。“云”使用了数据多备份容错、计算节点同构可互换等措施来保 障服务的高可靠性，使用云计算比使用本地计算机可靠。 ( 4 ) 通用性。云计算不针对特定的应用，在“云的支撑下可以构造出千变万化 的应用，同一个“云”可以同时支撑不同的应用运行。 ( 5 ) 高可扩展性。“云”的规模可以动态伸缩，满足应用和用户规模增长的需要。 ( 6 ) 按需服务。“云 是一个庞大的资源池，你按需购买；云可以象自来水，电， 煤气那样计费。 ( 7 ) 极其廉价。由于“云”的特殊容错措施可以采用极其廉价的节点来构成云， “云”的自动化集中式管理使大量企业无需负担日益高昂的数据中心管理成本，“云 的通用性使资源的利用率较之传统系统大幅提升，因此用户可以充分享受“云”的低 成本优势，经常只要花费几百美元、几天时间就能完成以前需要数力美元、数月时间 才能完成的任务。 2 1 4 云计算的应用类型 目前云计算越来越得到重视和发展，众多公司和厂商都提出了自己的云计算计划， 并投入大量资金来推动云计算的发展，这恰恰为云计算提供了良好的发展机遇。总结 起来，云计算大致有下面七大应用类型： ( 1 ) 软件即服务( s a a s ) s a a s 是s o f t w a r e - a s - a - s e r v i c e ( 软件即服务) 的简称，它是一种通过i n t e r n e t 提供软件的模式，用户不用再购买软件，而改用向提供商租用基于w e b 的软件，来管 理企业经营活动，且无需对软件进行维护，服务提供商会全权管理和维护软件，对于 许多小型企业来说，s m s 是采用先进技术的最好途径，它消除了企业购买、构建和维 4 桂林理工大学硕士学位论文 护基础设施和应用程序的需要，近年来，s a a s 的兴起已经给传统套装软件厂商带来真 实的压力。 ( 2 ) 效用计算( u t i l i t yc o m p u t i n g ) 效用计算是个新概念，具体目标是结合分散各地的服务器、存储系统以及应用程 序来立即提供需求数据的技术，使得用户能够像把灯泡插入灯头一样来使用计算机资 源。为了解决传统计算机资源、网络以及应用程序的使用方法变得越来越复杂，并且 管理成本越来越高的问题，科学家们提出了效用计算这个概念。按需分配的效用计算 模型采用了多种灵活有效的技术，能够对不同的需求提供相应的配置与执行方案。 ( 3 ) 云计算领域的w e b 服务( w e bs e r v i c eo nc l o u dc o m p u t i n g ) 同s a a s 关系密切，网络服务提供者们能够提供a p i 让开发者能够开发更多基于互 联网的应用，而不是提供单机程序。 ( 4 ) 平台即服务( p l a t f o r ma sas e r v i c e ，p a a s ) 平台即服务是软件即服务( s a a s ) 的延伸。s a a s 提供的是定制好的远程软件服务， 比如当你订购一个网络销售系统软件，就可以直接使用，不需要代码开发，但是缺点 是客制化困难。p a a s 也是远程订购服务，但是你购买的是平台模块服务，如计算能力、 数据库、储存和消息传送等。底层的平台已经帮你铺建好，你需要开发自己的上层应 用。 ( 5 ) 管理服务提供商( m s p ) 管理服务( m a n a g e ds e r v i c e ) 是云计算最古老的形式之一，它面向的i t 管理人 员而不是最终用户，例如用于电子邮件的病毒扫描服务，还有应用软件监控服务等。 由i b m 和v e r i z o n 公司提供的管理安全服务就可归为此类，还包括目前被g o o g l e 收购 的以云为基础的反垃圾邮件服务。 ( 6 ) 服务商业平台( s e r v i c ec o m m e r c ep l a t f o r m ) 服务商务平台是一种混合s a a s 以及m s p 的综合平台。这种云式计算服务提供了一 个用户互相交流的服务枢纽。它们在贸易环境中最常见，比如开支管理系统，它允许 用户在一个公共平台上订购旅行或秘书服务，这个公共平台在用户设定的范围内调整 服务的发布和定价。 ( 7 ) 互联网集成 云计算服务的集成仍处于初期阶段。如今，这种云计算互联的情况已经明显减少， 云计算也许可以更精确地描述为”天空中的计算”，i t 用户们必须将彼此独立分散的服 务云连接在一起。 s 桂林理工大学硕士学位论文 2 2m a p r e d u c e 模型的概念 2 2 1m a p r e d u c e 模型的来源 著名搜索引擎g o o g l e 公司于2 0 0 8 年7 月发表文章，称g o o g l e 索引到的惟一性的 网页数目已经超过一万亿，并且互联网上的链接都在以每天数十亿的数目逐同增加。 因此在g o o g l e 公司中，每天有海量的数据需要在有限的时间内进行处理，每个开发人 员都需要进行分布式的程序开发，这其中包括如何分布、调度、监控以及容错等，其 难度之大常人难以想象。 因此g o o g l e 在工作中逐渐提出并实现了m a p r e d u c e 模型用来简化并行计算的编 程，把分布式的业务逻辑从这些复杂的细节中抽象出来，使得没有或者很少并行开发 经验的开发人员也能进行并行应用程序的开发，方便进行海量数据的加工、生成和处 理。 2 2 2m a p r e d u c e 模型的原理 m a p r e d u c e 模型的名字来源于模型中的两项最基本的核心操作：m a p 和r e d u c e 。 m a p 操作是把一组数据一对一的映射为另外的一组数据，其映射的规则由一个用户自定 义的函数来指定。r e d u c e 操作则是对m a p 操作生成的一组数据进行归约，这个归约的 规则同样由用户自定义的函数指定。 因为m a p 操作是独立的对每个元素进行操作，将产生一组全新的数据，而原来的 数据保持不变，因此是高度并行的。r e d u c e 操作虽然不如m a p 操作并行性那么好，但 是它总会得到一个相对简单的结果，大规模运算也相对独立，因此也是比较适合并行 的。 m a p 和r e d u c e 操作过程如下所示： m a p ：瓴，v 1 ) 寸 2 ，v 2 ) r e d u c e ：( k 2 ，屹) 专屹 2 2 3m a p r e d u c e 模型的示例 6 桂林理工大学硕士学位论文 下面的代码示例是使用m a p r e d u c e 模型来统计一个很大的文档中，每一个单词出 现的次数嘲： m a p 操作 m a p ( v o i d , d o c ) 变量d o c 指向一个输入文档 1 ：f o re a c hw o r dwi nd o c 2 ：e m i t i n t e r m e d i a t e ( w ，1 ) ： r e d u c e 操作 r e d u c e ( v o i d * w o r d ，i t e r a t o rv a l u e s ) 1 ：i n tr e s u l t = 0 ： 2 ：f o re a c hvi nv a l u e s 3 ：r e s u l t + = v ： 4 ：e m i t ( w o r d ，r e s u l t ) ： 在上面的例子中，m a p 操作对每一个单词进行匹配，如果相符则把单词对应的计数 器递增1 ，但是并不进行合并，因此会出现许多个重复的单词统计。随后r e d u c e 操作 则把相对应单词的所有出现次数进行合并，得到最终结果。 m a p r e d u c e 模型不仅仅应用于上述方面，m a p r e d u c e 模型也能轻松解决如下问题： ( 1 ) 分布式g r e p ：m a p 操作根据指定的模式匹配到特定的行并将其传递给r e d u c e 操作。r e d u c e 操作将这些中间结果作为最终结果输出。 ( 2 ) u r l 访问频率统计：m a p 操作处理网页请求日志，输出 。r e d u c e 操 作对相同u r l 累加，规约为 对。 ( 3 ) 倒排索引：m a p 操作从每个文档中抽取关键字，生成 对。 r e d u c e 处理给定关键字的所有组，生成 对。输出的集合 形成一个简单的倒排索引。 ( 4 ) 主机词组向量：一个词组向量就是出现在一个或一组文档中最重要的词，以 7 桂林理工大学硕士学位论文 ( w o r d ，f r e q u e n c y ) 对列表的形式表示。m a p 操作通过处理输入文档，输出 对。r e d u c e 操作对具有相同的h o s t 进行规约，它将这些词组向量合并， 去除非常用词，最终输出 对。 ( 5 ) 分布式排序：m a p 操作从每条记录中抽取关键字，并且产生( k e y ，r e c o r d ) 对。r e d u c e 操作原样输出所有的关键字对。 2 2 4m a p r e d u c e 模型的执行过程 m a p 操作调用程序通过把输入数据分割成n 块被分配到多台计算机上，输入的块能 够在不同的计算机上被并行处理。r e d u c e 调用则通过分割函数分割中间键值，从而形 成r 块( 例如，h a s h ( k e y ) m o dr ) ，它们也会被分配到多台计算机上。分割数量r 和分割函数由用户来指定。 分蛲0 遗拶 榴一r 山：每支，牛 分头1 分袭2 分块3 分头4 田 输入 m a p 文绰操作 中闻文件 r e d t u z e 输出 ( 傈存在本地磁盘) 操作 文沣 图2 1m a p r e d u c e 操作的流程图 当用户程序调用m a p r e d u c e 模型时，将同上图整体数据流过程相同，并且图中的 数字编号与下列序号一一对应： ( 1 ) 用户程序中的m a p r e d u c e 函数库首先把输入文件分成n 块，每块大概1 6 m 到 桂林理工大学硕士学位论文 6 4 m ( 可以通过参数决定) 。接着在集群的计算机上执行处理程序。 ( 2 ) 在所有进程中有一个比较特殊，它是管理节点( m a s t e r ) ，其余的执行任务 都是由主控程序分配的。管理节点分别分配了n 个m a p 任务与r 个r e d u c e 任务。主控 程序选择空闲的工作节点( w o r k e r ) 去执行这些任务。 ( 3 ) 一个被委派执行m a p 操作的工作节点接受被切分的文件作输入，经过处理后， 生成键值对集合。集合被传递给用户定义的m a p 操作，m a p 操作产生的中间结果键 值对暂时被缓存起来。 ( 4 ) 这些位于内存的中间结果将被定时保存在本地硬盘中，这些数据通过分区函 数分成r 个区。这些中间结果在本地硬盘的位置信息将被送给管理节点m a s t e r ，然后 m a s t e r 负责把这些位置信息传送给r e d u c e 操作的工作节点。 ( 5 ) 当管理节点通知r e d u c e 操作的工作节点中间结果的位置时，它通过远程调 用从m a p 操作的工作节点所在的本地硬盘上读取中间文件。当r e d u c e 操作的工作节点 读取了所有的中间数据，他就使用中间结果的键进行排序，这样可以使得具有相同键 的对都在一起。通常情况下，会有许多不同键的被映射到相同的r e d u c e 任务，所以， 排序是必要的。如果中间结果集太大了，那么就需要使用外排序。 ( 6 ) r e d u c e 操作的工作节点根据每个唯一的中间键值来遍历所有的排序后的中 间数据，并且相关的中间结果集合传递给用户定义的r e d u c e 操作。对于本r e d u c e 分 块，将输出到一个最终的输出文件。 ( 7 ) 当所有的m a p 操作任务和r e d u c e 操作任务都已经完成了的时候，管理节点 激活用户程序。这时m a p r e d u c e 模型流程返回到用户程序的调用点。 当这些成功结束以后，m a p r e d u c e 模型的结果数据存放在总计r 个输出文件中( 每 个都是由r e d u c e 任务产生的，这些文件名是用户指定的) 。通常，用户不需要合并这r 个输出文件到一个文件，他们通常把这些文件作为输入传递到另一个m a p r e d u c e 调用， 或者用另一个分布式应用来处理这些文件，并且这些分布式应用能处理被分区的输入 数据。 2 2 5m a p r e d u c e 模型的管理节点 管理节点维护了一些数据结构。对于每个m a p 与r e d u c e 任务，会在管理节点上记 录下它们的状态( 分别为空闲、处理中或已完成) ，并且识别不同的节点。 管理节点是由m a p 任务产生的中间文件位置信息传递到r e d u c e 任务的管道。因此， 9 桂林理工大学硕士学位论文 对于每一个完成的m a p 任务，管理节点保存此m a p 任务产生的r 个中间结果文件位置 信息和大小信息。当管理节点接收到m a p 任务完成的消息后，它把中间文件的信息发 送到处于就绪状态的r e d u c e 任务的工作节点上。 m a s t e r 臀l 计算 l + 怿出问题l 图2 2m a p r e d u c e 模型中管理节点m a st e r 和工作节点w o r k e r 交互过程 2 2 6m a p r e d u c e 模型的容错机制 由于m a p r e d u c e 函数库是设计用于在成百上千台计算机上处理海量数据的，所以 这个函数库必须考虑到计算机故障的容错处理。 ( 1 ) 工作节点失效 1 0 桂林理工大学硕士学位论文 管理节点会定期p i n g 每一个工作节点计算机。如果在一定时间内没有工作节点的 响应，管理节点就认为这个节点失效了。所有这台工作节点完成的m a p 任务都被设置 成为他们的初始空闲状态，并且因此可以被其他工作节点重新调度执行。类似的，所 有这个计算机上正在处理的m a p 任务或者r e d u c e 任务都被设置成为空闲状态，可以被 其他工作节点重新执行。 在失效节点上的已经完成的m a p 任务还需要再次重新执行，这是因为中间结果存 放在这个失效的计算机上，导致中间结果无法访问；己经完成的r e d u c e 任务无需再次 执行，因为他们的结果己经保存在全局文件系统中了。 当一个在节点a 上执行的m a p 任务由于a 节点失效，切换到b 节点执行，所有执 行r e d u c e 操作的节点都被告知这一情况。这样的话，那些尚未从节点a 上读取结果的 r e d u c e 节点要从b 上获得数据。 m a p r e d u c e 可以有效地支持很大范围的节点失效的情况。比如，在一次m a p r e d u c e 操作中，网络例行维护可能会导致大约有几十台计算机在几分钟之内不能访问。 m a p r e d u c e 的管理节点简单的把这些不能访问的节点上的工作再执行一次，并且继续调 度进程，最后完成m a p r e d u c e 操作。 ( 2 ) 管理节点失效 通常为管理节点数据结构设置周期性的检查点。这样当管理节点失效的时候，可 以从最后一次检查点重新开始。不过，由于只有一个管理节点在运行，所以如果失效 就比较麻烦。因此当前的实现上，如果管理节点失效了，就终止m a p r e d u c e 执行。客 户端可以检测这种失效并且根据需要重新尝试m a p r e d u c e 操作。 2 2 7m a p r e d u c e 模型的失效处理 当用户自定义的m a p 和r e d u c e 函数对于他们的输入来说是确定性的函数，分布式 的输出就应当和在一个整个程序没有失败的连续执行相同。 依靠对m a p 和r e d u c e 操作的输出进行原子提交来完成这样的可靠性。每一个工作 中的操作把输出写道一个私有的临时文件中。r e d u c e 操作产生一个这样的文件，m a p 操作产生r 个这样的操作。当一个m a p 操作完成的时候，w o r k e r 发送一个消息给 m a s t e r ，并且这个消息中包含了这个r 个临时文件的名字。如果m a s t e r 又收到一个已 经完成的m a p 操作的完成消息，他就忽略这个消息。否则，他就在m a s t e r 数据结构中 记录这个r 文件。 1 1 桂林理工大学硕士学位论文 当一个r e d u c e 操作完成的时候，r e d u c ew o r k e r 自动把临时输出的文件名改为正 式的输出文件。如果再多台计算机上有相同的r e d u c e 操作执行，那么就会有多个针对 最终输出文件的更名动作。依靠文件系统提供的原子重命名操作来保证最终的文件系 统状态中记录的是其中一个r e d u c e 操作的输出。 绝大部分m a p 和r e d u c e 操作都是确定性的，实际上在语义角度，这个m a p 和r e d u c e 并发执行和顺序执行市一样的，这就使得程序员很容易推测程序行为。当m a p 和r e d u c e 操作是非确定性的时候，有稍弱的但是依旧是有道理的错误处理机制。对于非确定性 操作来说，特定r e d u c e 任务r 1 的输出，与，非确定性的顺序执行的程序对r 1 的输出 是等价的。另外，另一个r e d u c e 任务r 2 的输出，是和另一个顺序执行的非确定性程 序对应的r 2 输出相关的。 2 2 8m a p r e d u c e 模型的任务粒度 综合前面所述，把m a p 操作数据拆分到n 小块，并且r e d u c e 操作数据拆分到r 小 块执行。在理想状态下，n 和r 应当比工作节点计算机数量要多得多。每一个工作节点 计算机都通过执行大量的任务来提高动态的负载均衡能力，并且能够加快故障恢复的 速度：这个失效计算机上执行的大量m a p 任务都可以分布到所有其他工作节点计算机 上执行。 但是实现中，实际上对于n 和r 的取值有一定的限制，因为管理节点必须执行0 ( n + r ) 次调度，并且在内存中保存0 ( n 木r ) 个状态。( 对影响内存使用的因素还是比 较小的：0 ( 肿r ) 块状态，大概每对m a p 任务r e d u c e 任务1 个字节就可以了) 进一步来说，用户通常会指定r 的值，因为每一个r e d u c e 任务最终都是一个独立 的输出文件。在实际中，倾向于调整n 的值，使得每一个独立任务都是处理大约1 6 m 到6 4 m 的输入数据，这样本地优化策略会最有效。另外，如果使r 比较小，这样使得r 占用不多的工作节点计算机。通常会用这样的比例来执行m a p r e d u c e ：n ：2 0 0 0 0 0 ， r = 5 0 0 0 ，使用2 0 0 0 台工作节点计算机。 2 3 基于m a p r e d u c e 模型的h a d o o p 并行计算平台 1 2 桂林理工大学硕士学位论文 2 ，3 1h a d o o p 简介 h a d o o p 原来是a p a c h el u c e n e 下的一个子项目，它最初是从n u t c h 项目中分离出 来的专门负责分布式存储以及分布式运算的项目瞳“1 。简单地说来，h a d o o p 是一个 可以更容易开发和运行处理大规模数据的软件平台。h a d o o p 实现了m a p r e d u c e 分布式 计算模型。m a p r e d u c e 将应用程序的工作分解成很多小的工作小块。h d f s 系统为了做 到可靠性创建了多份数据块的复制，并将它们放置在服务器群的计算节点中， m a p r e d u c e 就可以在它们所在的节点上处理这些数据了。 如下图所示： 2 。3 2h a d o o p 特点 图2 3h a d o o p 的分布式存储和并行计算逻辑图 ( 1 ) 扩容能力：能可靠地存储和处理p b 级海量数据。 ( 2 ) 成本低：可以通过普通机器组成的服务器群来分发以及处理数据。这些服务 器群总计可达数干个节点。 ( 3 ) 高效率：通过分发数据，h a d o o p 可以在数据所在的节点上并行地处理它们， 这使得处理非常的快速。 ( 4 ) 可靠性：h a d o o p 能自动地维护数据的多份复制，并且在任务失败后能自动地 重新部署计算任务。 2 3 3h d f s 分布式文件系统 桂林理工大学硕士学位论文 h a d o o p 平台的内部实现了一个分布式文件系统( h a d o o pd i s t r i b u t e df i l e s y s t e m ) ，简称h d f s 系统。h d f s 系统有着高容错性的特点，并且设计用来部署在低廉 的硬件上。而且它提供高传输率来访问应用程序的数据，适合那些有着超大数据集的 应用程序。目前，h d f s 系统有着比大型关系型数据库系统更为优异的性能和特点，具 体如下： ( 1 ) 稳定性 h d f s 系统是部署在低成本计算机集群上的，那么硬件出现的故障是很正常的事情， 整个h d f s 系统将由数百或数千个存储着文件数据片断的普通计算机组成。经常会有一 部分组件出现故障或是无法访问，意味着h d f s 系统里的一些组成部分总是失效的。因 此，如何进行故障的检测与快速恢复是h d f s 系统设计和实现的一个核心问题。 最常见的故障是n a m e n o d e 节点失效、d a t a n o d e 节点失效和网络断开。 每个d a t a n o d e 节点周期性发送心跳给n a m e n o d e 节点，网络故障会造成一些 d a t a n o d e 节点和n a m e n o d e 节点失去联系，n a m e n o d e 节点发现这种情况的根据是没有 了心跳消息。n a m e n o d e 节点标记这些d a t a n o d e 节点失效，就不再将新的i o 请求转发 到这些d a t a n o d e 节点上，而这些节点上的数据将对h d f s 系统不再可用。这将导致一 些块的备份数降低到最低点，因此n a m e n o d e 节点检查所有的需要复制的数据块，并开 始复制它们到其他的d a t a n o d e 节点上。引发重新复制的原因还有：备份被破坏， d a t a n o d e 节点上的磁盘损坏或增加了文件块的备份数。 当文件块从d a t a n o d e 节点读出的时候，有可能被损坏。引发这种情况的原因可能 是存储设备故障，网络故障或软件缺陷，h d f s 系统客户端软件实现了h d f s 系统文件的 内容校验。当一个客户端创建一个h d f s 系统文件，它为每一个文件块计算一个校验码 并存储校验码在同一个n a m e s p a c e 空间中的某个单独的隐藏文件中。当客户端取这个 文件内容时，它再根据这个校验码来验证从d a t a n o d e 节点接受到的数据，如果不对， 客户端可以从另外一个有该块备份的d a t a n o d e 节点重新获取。 ( 2 ) 数据的组织条理性 h d f s 系统是设计成支持大型文件的，程序也是和h d f s 系统一样地处理大数据集。 这些程序写数据仅一次，读数据一次或多次，这就需要一个比较好的流读取速度。h d f s 系统支持对文件的一写多读模式。h d f s 系统典型的块大小是6 4 m 。当一个客户端请求 创建一个文件的时候，并不是立即向n a m e n o d e 节点发请求，h d f s 系统客户端首先在本 地缓存文件数据，应用程序将写操作透明地重定向到临时本地文件。当本地文件堆积 1 4 桂林理工大学硕士学位论文 到大于h d f s 系统块大小的时候，客户端联系n a m e n o d e 节点，n a m e n o d e 节点将文件名 插入到文件系统当中，然后构造一个数据块，n a m e n o d e 节点返回给客户端的响应包括 d a t a n o d e 节点的标识和目标数据块号，客户端再将本地的临时文件刷新到指定位置。 当文件要关闭时，在把未刷入的数据传送完毕后，客户端通知n a m e n o d e 节点此文件已 经关闭，此时，n a m e n o d e 节点提交文件的创建操作到持久化存储。如果客户端直接写 到远程文件系统，而没有本地的缓冲，会对网速和网络吞吐量产生