（计算机科学与技术专业论文）基于hadoop平台的通信数据分布式查询算法的设计与实现.pdf

摘要 数据是信息的载体，随着信息化的不断发展，数据在现代社会生活中承担着越 来越重要的角色。社会网络分析就是利用图论、数据挖掘等技术手段从社会网络 数据集中寻找有用的信息。由于社会网络分析所处理的数据通常是很庞大的。因 而对数据处理的能力要求很高。 大规模通信社会网络数据分析与可视化系统是一个专门处理通信数据集的社 会网络分析工具。它提供了社会网络分层扩展等一系列数据分析与可视化的基本 操作。对于该系统来说，图的分层扩展涉及到在海量数据中进行查询，因而对数 据查询效率有着很高的要求。采用传统的关系型数据库o r a c l e 或s q ls e r v e r 等虽 然能够满足复杂条件的查询，但在处理t b 级的大规模原始数据集时就显得力不从 心。同时，在网络分层扩展时要用到广度优先搜索算法，需要在海量原始数据中 进行遍历操作，这在关系数据库中的效率是很低的。 以上情况就迫切需要我们解决数据查询和处理中存在的瓶颈。在分析了现有分 布式存储系统与云计算平台的基础上，本文提出了一种基于h a d o o p 平台的分布式 数据存储和查询改进方案。本文重点阐述了通信数据分布式存储与查询在h a d o o p 平台上的实现。据h b a s e 数据库的特色设计了通信社会网络数掘模型。实现了基 于h b a s e 数据库上的条件查询。并对设计好的数据模型进行了优化。最后在h a d o o p 数据服务平台上实现了面向软件客户端的数据访问服务。设计了适合通信社会网 络数据特色的m a p r e d u c e 算法。通过m a p 和r e d u c e 函数实现了数据的并行查询 和处理。在数据查询过程中，还将数据遍历过程放在r e d u c e 函数中，从而使广度 优先搜索算法的层次遍历过程也能够并行运行。这在很大稃度上优化了数据查询 和分层扩展的效率。 通信数据分布式存储与查询方案在h a d o o p 平台上的成功实施具有很重要的意 义。h a d o o p 平台只需要部署在普通的廉价p c 机上即可运行，却能够处理p b 的级 数据。高效却又节约成本，因此具有很高的现实意义与应用价值。 关键词：h a d o o p 平台；m a p r e d u c e 算法；分布式查洵；h b a s e 分类号： a bs t r a c t d a t ai st h ec a r r i e ro fi n f o r m a t i o n w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ， d a t ai nt h em o d e ms o c i a ll if ea s s u m e sa ni n c r e a s i n g l yi m p o r t a n tr o l e s o c i a ln e t w o r k a n a l y s i sd i s t i l su s e f u li n f o r m a t i o nf r o mt h es o c i a ln e t w o r kd a t ab yg r a p ht h e o r y ，d a t a m i n i n gt e c h n i q u e sa n ds oo n u s u a l l yo f t h ed a t as e ti sv e r yl a r g e s ot h ea b i l i t yo fd a t a p r o c e s s i n gs h o u l db ee x c e l l e n t l a r g e s c a l es o c i a ln e t w o r kc o m m u n i c a t i o n sd a t aa n a l y s i sa n dv i s u a l i z a t i o ns y s t e m i sas o c i a ln e t w o r ka n a l y s i st o o l sd e a l i n gs p e c i f i c a l l yw i t hc o m m u n i c a t i o nd a t as e t f o r t h es y s t e m ，e x p a n s i o no ft h eh i e r a r c h i c a ld a t ai n v o l v e sq u e r y i n gi ne x t e n s i v ed a t a s e t a n dt h u si tn e e d sah i g he f f i c i e n c yo fd a t aq u e r yr e q u i r e m e n t s u s i n gt h et r a d i t i o n a l r e l a t i o n a ld a t a b a s es u c ha so r a c l eo rs q ls e r v e rc a nm e e tt h ec o m p l e xc o n d i t i o n s w h i l et h ei n q u i r y ，b u tw h e nd e a l i n gw i t ht b c l a s sl a r g e s c a l ed a t as e t s ，i t su n a b l et od o a sm u c ha sw ew o u l dl i k et o a tt h es a l r l et i m e ，b f sa l g o r i t h m ，w h i c hh a st r a v e r s a l o p e r a t i o n ，i si sv e r yl o wi nr e l a t i o n a ld a t a b a s e s i ns u c hac a s e ，w en e e dt os o l v ed a t aq u e r ya n dp r o c e s s i n gb o t t l e n e c k se x i s t a f t e r a n a l y z i n gt h ee x i s t i n gd i s t r i b u t e ds t o r a g es y s t e m sa n dc l o u dc o m p u t i n gp l a t f o r m ，w e c h o o s eh a d o o pp l a t f o r mf o rd i s t r i b u t e dd a t as t o r a g ea n dq u e r yt oi m p r o v et h ep r o g r a m t h ep a p e r sf o c u so nt h ec o m m u n i c a t i o nd a t ad i s t r i b u t e ds t o r a g ea n dq u e r yb a s e do n h a d o o pp l a t f o r m d e s i g nt h eh b a s e b a s e dc o m m u n i c a t i o n d a t am o d e lo fs o c i a ln e t w o r k d a t a w ei m p l e m e n tt h ec o n d i t i o n sq u e r y d e s i g na n do p t i m i z ed a t am o d e l f i n a l l y , t h e c l i e n t sc a na c c e s ss e r v i c e sf r o mh a d o o pp l a t f o r m d e s i g na n di m p l e m e n tm a p r e d u c e a l g o r i t h mf o rc o m m u n i c a t i o nd a t as e t m a pa n dr e d u c ef u n c t i o n si m p l e m e n tt h ed a t a p a r a l l e lq u e r yp r o c e s s i n g i nt h ed a t aq u e r yp r o c e s s ，t h et r a v e r s ep r o c e s si sp u ti nt h e r e d u c ef u n c t i o n s ot h a tt h eb f sa l g o r i t h mt r a v e r s ec a na l s or u ni np a r a l l e l t h i si si n l a r g em e a s u r et oo p t i m i z et h ed a t aq u e r ya n d t h ee f f i c i e n c yo fs t r a t i f i c a t i o ne x p a n s i o n t h ei m p l e m e n t a t i o no fc o m m u n i c a t i o nd a t ad i s t r i b u t e ds t o r a g ea n dq u e r yb a s e do n h a d o o pp l a t f o r m h a sv e r y i m p o r t a n ts i g n i f i c a n c e h a d o o pp l a t f o r m n e e d st ob e d e p l o y e do n l yi nt h eo r d i n a r y ，c h e a pp ct or u n ，b u ta b l et od e a lw i t ht h ep bd a t a e f f i c i e n tb u tc o s t e f f e c t i v e ，i th a sh i g hv a l u ea n da p p l i c a t i o no fp r a c t i c a ls i g n i f i c a n c e k e y w o r d s ：h a d o o pp l a t f o r m ；m a p r e d u c ea l g o r i t h m ；d i s t r i b u t e dq u e r y ；h b a s e c l a s s n oo 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名吊第签字同期 5 3 年月i 寥日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 躲慨 一期：_ 年 导师签名： 签字熙乃哆年多月猡同 致谢 几经彷徨求索，论文终于得以完成。回顾这一程求学路，记忆罩满是老师的 悉心指导和同学的快乐相伴，在此我要向他们表达最诚挚的感谢。 饮其流时思其源，成吾学时念吾师，在此论文完成之际，谨向我尊敬的导师林 友芳老师致以诚挚的谢意和崇高的敬意。林老师丰富的实践经验、渊博的专业知 识、务实忘我的工作作风、宽以待人的处事态度使我受益匪浅。他精益求精的工 作作风，深深地感染和激励着我。他对学生的理解和宽容常让我心生感动。临别 之际，在此真诚地对林老师表示谢意。 我还要感谢魏名元老师、韩升老师、实验室的其他各位老师，两年来给我最细 心的指导和帮助。各位老师在两年的研究生生活中不仅教给了我很多知识，还给 我营造了一个轻松快乐的学习、研究氛围。 研究生期间朝夕相处的同学也是宝贵的财富，感谢王天宇、陆鹏、武志吴 三位同窗好友让我体会到的真挚友情。感谢我所有师兄弟妹、同学、朋友们，是 你们的情谊和帮助，让我在两年的研究生生活中感到踏实温暖。 同时还要特别感谢我的师兄万怀宇和薛斌同学，在我写论文的过程中给我悉 心的指导，让我掌握了书写论文的技巧，保证了论文能够高质量的完成。 衷心感谢在百忙之中抽出时问审阅本论文的专家教授，感谢答辩委员会的各位 老师和专家们对我的论文提出的宝贵建议，为我今后的学习和研究开拓了思路。 最后感谢我的亲人，焉得谖草，言树之背，养育之恩，无以回报，你们永远健 康快乐是我最大的心愿。 1 引言 1 1课题研究背景 近年来，社会网络分析已经成为了一个热门的研究领域。随着图论、随机网 络等知识不断融入，使得社会网络分析技术有了很大的发展。同时随着通信技术 的r 益普及，通信企业的客户量和业务数据量急剧增加，对通信数据的深层次分 析也随之变得迫切起来。将通信数据与社会网络分析技术结合起来，通过对通信 数据的分析，可以为通信企业执行营销策略提供决策支持。 在数据分析过程中，对数据的可视化描述让我们更直观地获取知识。以图的方 式将社会网络展示给用户是一种非常有效信息展示手段。同时可视化技术提供了 友好的界面，便于用户与数据之间进行交互。 在实施可视化技术的时候，由于通信社会网络数据集非常的庞大。因而要求其 可视化系统具有强大的数据处理能力。也就是说数据处理的效率是本课题研究一 个关键的性能指标。传统的关系型数据在处理大数据集时效率很不理想，尤其是 在图分层拓展方面，由于设计到海量数掘的查询处理，图的每一层扩展都需要等 待很长的时间。这一点就成了系统最大的缺点。所以需求一种更好的数据处理模 式成了亟待解决的事情。本文将研究如何提高数据查询效率 g o o g l e 的m a p r e d u c e 算法模型与b i g t a b l e 技术从一出现，就引起了技术爱 好者的广泛关注。在搜索引擎领域，g o o g l e 以绝对的优势占据领先地位。因此 g o o g l e 的数据处理技术一直备受业内人士关注和推崇。h a d o o p 做为m a p r e d u c e 的一个j a v a 实现。在w e b 文本搜索，w e b 同志分析等方面有了很广泛的应用。 m a p r e d u c e 编程模型对程序员屏蔽了复杂的并行应用程序丌发。程序员只需关心 应用逻辑。同时h a d o o p 平台只需部署在普通的p c 机上，这就大大节约了实施分 布式系统投入的成本。通信社会网络的数据往往是很庞大的，用传统的分向式来 处理这些数据，不仅实施系统复杂度高，投入的成本也随着数据量的增加而大幅 度增加。h a d o o p 平台在数据分布式处理方面的优秀表现就吸引了通信社会网络数 据处理研究组的兴趣。尤其是近些年来h a d o o p 平台技术发展越来越成熟，在数据 的安全性和稳定性方面都有了很大的突破，这就增加了我们将h a d o o p 平台成功实 施剑通信社会网络数据处理系统中的信心。将h a d o o p 平台技术与可视化系统结合 起来是一种很新颖的观点，目前还处于探索阶段，也足本文主要介绍的内容。 1 2 课题研究内容与意义 社会网络分析的很多概念来源于图论，因此在可视化系统中，图的分层扩展是 其他社会网络分析指标研究的基础。在图的扩展算法中，使用广度优先搜索算法 是因为它本身就是基于层的搜索算法。与图的分层扩展方式相吻合。 二二 图1 1 通信数据- - j 视化网络图 f i g u r e 1 1t h ev i s u a ln e t w o r kp i c t u r e 图1 1 就是一个扩展了两层的通信社会网络图。图中节点是手机号码或者飞信 号码。节点之间的边则表示两个号码之间的通信信息。圆形节点是初始化的节点 集。正方形节点是第一层扩展出来的节点。三角形是第二层扩展出来的节点。图 的扩展为社会网络分析提供了更直观，更形象的研究方式。采用传统的关系型数 据来解决图的扩展问题效率及其低下。经过研究和分析，基于h a d o o p 平台的分布 式系统在处理数据方面的优秀表现使其成为了我们解决这一问题的首选。本文主 要研究的内容有以下几个方面： 1 ) 通信社会网络数据采用传统关系型数据库处理数据存在的问题以及解决 这些问题首先需要考虑的各方面因素。 2 ) 通信社会网络数据在h a d o o p 平台的存储与查询实现。基于h a d o o p 平台的 通信数据处理的并行运行。 3 ) h a d o o p 平台搭建，名字节点与数据的节点的配置。h d f s 的数据容错机制， 工作粒度的确定以及基于h a d o o p 平台的通信社会网络分析软件实现与性能优化。 2 4 1m a p r e d u c e 编程模型的基本原理与具体实现，通信社会网络数据查询与遍 历的m a p r e d u c e 算法的设计与实现。 5 ) h b a s e 数据库的体系结构以及数据模型的特色。基于h b a s e 通信社会网络 数据的数据模型的设计以及条件查询的优化。 本文并没有对社会网络分析技术的深层细节进行过多的探讨，重点在于如何通 过分布式系统提高数据存出性能和查询效率。社会网络分析中的很多概念本身就 来自于图论。如果节点、边、有向图等。因此通过图论知识研究通信社会网络分 析技术是最合适不过的。社会网络分析提出了若干定量分析的指标，如最短路径、 中心度、弱相关结构、子群体结构、连通度等。图形扩展对于研究这些指标有这 很重要的意义。 图中节点的扩展算法使用的是广度优先搜索算法。广度优先搜索算法是分层扩 展的。每搜索到一个节点都需要遍历已扩展的节点集合，看其是否存在，因此对 于大规模数据集来说广度优先搜索算法的效率非常低。同时，传统的关系型数据 库中查询扩展节点与扩展边的时候，当数据量达到一定程度时查询效率就会非常 低，甚至会引起程序异常，机器死机等现象。如果h a d o o p 平台能够解决这两个问 题，通信社会网络分层扩展的效率将会有大幅度提高。 h a d o o p 平台做为一项新兴的技术，之所以发展如此迅速是因为它将并行计算 “平民化”。它对程序员屏蔽了并行应用丌发的细节，程序员只需将更多的精力放 在业务逻辑上即可。另外h a d o o p 平台只需要普通p c 机群就可以运行，大大节约 了开发成本。这也让个人实施、研究分布式系统更加容易。h a d o o p 平台自出现以 来就一直在w e b 搜索，w e b 同志分析等方面有着很突出的表现。但是还没有被大 数据处理系统被广泛的使用，主要原因是其处理的数据类型比较单一，数据关联 性弱等特点造成的。解决这些问题，成功地将h a d o o p 平台技术应用到通信社会网 络可视化系统中，是通信社会网络数据可视化系统项目组最终的目标。 总的来说，研究如何将通信社会网络可视化系统成功地实施在h a d o o p 分布式 数据处理平台上有以下几方面的意义： 1 ) 对于通信企业来说，其数据量都是非常庞大。在实施社会网络分析可视化 系统时数据处理效率就成了关键的l 、u j 题。如果h a d o o p 平台解决了这个问题，无疑 会使社会网络分析技术为通信企业的决策做出更大的支持，提高企业的经济效益。 2 ) h a d o o p 平台的只需要普通的p c 集群就可以实施运行，这就大大降低了实 施分钮式系统的成本，大大节约了通信企业丌发可视化系统的硬件投入。 3 ) h a d o o p 平台还没有被广泛地应用于各行各! ，一旦我们在通信社会网络分 析与可视化系统中取得一定得成效，就会埘h a d o o p 技术起到推j 一作用。 1 3 论文结构 本文共分6 章： 第一章主要介绍了论文研究的背景、内容以及意义。为以后的章节打下了一 个基础。 第二章首先介绍了h a d o o p 平台的技术渊源。接下来又详细介绍了h a d o o p 平台的基本原理和架构以及h a d o o p 平台的两个核心组件h d f s 与m a p r e d u c e 算 法。 第三章简单介绍了h b a s e 分布式数据库的体系结构与数据模型。h b a s e 数据 库也是a p a c h e 的一个开源项目。为了更好地在h a d o o p 平台上管理数据，我们选 择h b a s e 来管理可视化系统的数据。接下来主要阐述了可视化系统的h b a s e 数据 模型的设计以及条件查询的改进。 第四章主要介绍了通信社会网络分析数据的m a p r e d u c e 算法模型的实现。 分析了传统关系型数据库存在的不足，讲述了h a d o o p 平台如何优化通信社会网络 系统的设计思想。详细介绍了m a p 和r e d u c e 函数的设计。然后介绍了任务粒度、 容错机制的相关设置以及性能优化，最后又比较了两种系统的性能。 第五章开始介绍了h a d o o p 平台与h b a s e 环境的搭建。然后又给出了实验室 结果。通过对比实验结果做出了详细分析。 第六章主要是总结论文的主要内容，给出了展望。提出了需要进一步解决的 问题。 4 2h a d o o d 平台架构 2 1 h a d o o p 技术背景 2 1 1 lb m 的云计算 2 0 0 7 年底i b m 推出了云计算( b l u ec l o u d ) 。云计算提供一种在虚拟环境中开 发应用程序的方法。由于不需要在自己的系统上安装软件，该环境的计算能力、 带宽、存储、安全和可靠性都不成问题。在虚拟云计算环境中，我们可以开发、 部署和管理应用程序，根据不断变化的业务需求调整应用程序。云计算的定义有 狭义和广义之分。狭义的云计算，指的是厂商通过分布式计算和虚拟化技术搭建 数据中心或超级计算机，以免费或按需租用方式向技术开发者或者企业客户提供 数据存储、分析以及科学计算等服务，比如亚马逊数据仓库外租、微软的s s d s 等。 广义的云计算，则指厂商通过建立网络服务器集群，向各种不同类型客户提供在 线软件服务、硬件租借、数据存储、计算分析等不同类型的服务。显然，广义的 云计算包括了更多的厂商和服务类型，例如以国内用友、金蝶等管理软件厂商推 出的在线财务软件，g o o g l e 发布的g o o g l e 应用程序套装等都属于广义与计算的范 畴。 云计算最重要的概念之一就是可伸缩性，实现它的关键则是虚拟化 ( v i r t u a l i z a t i o n ) 。虚拟化就是在一台共享计算机上聚集多个操作系统和应用程序， 以便更好地利用服务器。虚拟化允许在线迁移，因此，当一个服务器负载超荷时， 可以将其中一个操作系统的一个实例( 以及它的应用程序) 迁移到一个新的、不 相对闲置的服务器上。从外部看，云计算只是将计算和存储资源从企业迁出，并 迁入到云中。用户定义资源需求( 例如计算和广域网、带宽需求) ，云提供者在它 的基础设施中虚拟地装配这些组件。 放弃对自己资源的控制，而让其虚拟地存在于云中最重要的两个原因是成本和 可伸缩性。云计算的目标是使这些资源比自己所能提供和管理的资源更廉价。另 外云计算还拥有很大的灵活性和可伸缩性。云计算提供者可以轻松地扩展虚拟坏 境，通过虚拟基础设施提供更大的带宽或计算资源。 因此云计算可以看成足网格计算与虚拟化技术的结合。利用网格的分布式计算 能力将各种i t 资源筑成一个资源池，然后结合成熟的存储虚拟化和服务虚拟化技 术，让用户实时透明地监控和调配资源。 2 1 2 g o o gie 文件系统g f s g f s 是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据 进行访问的应用。它运行的普通的p c 机上，但可以提供强大的容错功能。它可 以给大量的用户提供总体性能较高的服务。g f s 与以往的文件系统的不同之处在 于： 1 ) 组件错误不是被当作异常，而是将其作为j 下常情况加以处理。因为文件系 统由成大量用于存储的机器构成，而这些机器是由廉价的普通组件组成并被大量 的客户机访问。组件的数量和质量使得一些机器随时都有可能无法工作并且有一 部分还可能无法恢复。所以实时地监控、错误检测、容错、自动恢复是系统必须 拥有的一部分。 2 _ ) 按照以往的标准，g o o g l e 存储的文件都非常大。长度达几个g b 的文件是 很平常的。每个文件通常包含很多应用对象，比如w e b 文档。当经常要处理快速 增长的、包含数以力计的对象、长度达t b 的数据集时，即使底层文件系统提供支 持，很难管理成千上力的k b 规模的文件块。因此，设计时操作的参数、块的大小 必须要重新考虑。对大型的文件的管理一定要能做到高效，对小型的文件也必须 支持，但不必优化。 3 ) 在对g f s 文件处理时，工作量主要由两种读操作构成：对大量数据的流方 式的读操作和对少量数据的随机方式的渎操作。在前一种读操作中，可能要读几 百k b ，通常达1 m b 和更多。来自同一个客户的连续操作通常会读文件的一个连 续的区域。随机的渎操作通常在一个随机的偏移处读几个k b 。性能敏感的应用程 序通常将对少量数据的读操作进行分类并进行批处理以使得读操作稳定地向前推 进，而不要让它来来回回的读。 4 ) g f s 处理数据时包含许多对大量数据进行的、连续的、向文件添加数据的 写操作。所写的数据的规模和读相似。一旦写完，文件很少改动。在随机位置对 少量数据的写操作也支持，但不必非常高效。 一个g f s 集群由一个m a s t e r 和大量的c h u n k s e r v e r 构成，并被许多客户( c l i e n t ) 访问。m a s t e r 和c h u n k s e r v e r 通常是运行用户层服务进程的l i n u x 机器。只要资源 和可靠性允许，c h u n k s e r v e r 和c l i e n t 就呵以运行在同一个机器上。 6 图2 1g f s 体系结构 f i g u r e 2 it h ea r c h i t e c t u r eo fg f s 文件被分成固定大小的块。每个块由一个不变的、全局唯一的6 4 位的c h u n k h a n d l e 标识，c h u n kh a n d l e 是在块创建时由m a s t e r 分配的。c h u n k s e r v e r 将块当 作l i n u x 文件存储在本地磁盘并可以读和写由c h u n kh a n d l e 和位区间指定的数据。 出于可靠性考虑，每一个块被复制到多个c h u n k s e r v e r 上。默认情况下，保存3 个 副本，副本个数可以有用户自己定义。 m a s t e r 维护文件系统所有的元数据，包括名字空间、访问控制信息、从文件到 块的映射以及块的当前位置。它也控制系统的活动，如块租约管理，孤块的垃圾 收集，c h u n k s e r v e r 间的块迁移。m a s t e r 定期通过心跳消息与每一个c h u n k s e r v e r 通信，给c h u n k s e r v e r 传递指令并收集它的状态。 与每个应用相联的g f s 客户代码实现了文件系统的a p i ，并与m a s t e r 和 c h u n k s e r v e r 通信以代表应用程序读和写数据。客户与m a s t e r 的交换只限于对元数 据的操作，所有数据方面的通信都直接和c h u n k s e r v e r 联系。 客户和c h u n k s e r v e r 都不缓存文件数据。因为用户缓存的益处微乎其微，这是 由于数据太多或工作集太大而无法缓存。不缓存数据简化了客户程序和整个系统， 因为不必考虑缓存的一致性问题。但用户缓存元数据( m e t a d a t a ) 。c h u n k s e r v e r 也 不必缓存文件，因为块时作为本地文件存储的。 2 1 3 m a p r e d u c e 算法 m a p r e d u c e 算法模型足g o o g l 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 的名字源于这个模型中的两项核心操作：m a p 和r e d u c e ( 来自于 函数式编程语言l i s p ) 。简单的浼来，m a p 是把用户输入的数据( k e y v a l u e 对) 通过 用户自定义的m a p 函数操作映射为一组临时中间键值对。比如对【2 ，4 ，6 ，8 】进 行平方的映射就变成t 4 ，1 6 ，3 6 ，6 4 】。r e d u c e 是对生成的临时中间键值对进行 归约，这个归约的规则由一个用户自定义r e d u c e 函数操作指定，输出最终结果。 比如对 2 ，4 ，6 ，8 】进行乘积归于最终输出3 8 4 。 在函数式编程中，操作是没有副作用的。m a p 函数在生成新的中间值的过程中， 并不改变原来的数据。所以m a p 函数是高度并行的。r e d u c e 函数没有m a p 函数的 并行性能好，但是它总是计算很简单的规约结果。所以大规模运算的时候也比较 独立。因此也是适合并行的。 m a p 与r e d u c e 函数都是以函数作为参数，在函数式编程中，这类函数被称为 高阶函数。f 是由于可以同其它函数相结合，所以我们只需把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 操作。从i j 面的内容可以看出，在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 ( k l ，v 1 ) 专l i s t ( k 2 ，v 2 ) r e d u c e ( k2 ，l 括t ( v 2 ) ) _ l i s t ( v 2 ) ( 2 1 ) ( 2 2 ) 但是这种关联是m a p r e d u c e 编程模型内部实现的，站在计算的两端来看， m a p r e d u c e 算法实现的分布式系统计算模型与我们通常熟悉的串行计算没有任何 差别，因为这个框架隐藏了中f h j 的复杂性。 这些并行化能力与函数式编程有着密不可分的关系。很多并行编干旱模型都丌 始走函数式编秤的模式。函数式编程有很多优秀的东西，比如自动内存管理，动 态类型。以前山于机器性能的原因，函数编程没有被广泛应用，如今机器性能不 再是瓶颈，于是这些思想逐渐盛行起来。 并行计算的主要开发难点在于编程模型，如果太过复杂必然会遭弃用， c o r b a 就因为不容易上手而成了并行编程模型普及化的反面例子。m a p r e d u c e 给我们提供了一种可以简单的编程模型。 2 2 h a d o o p 平台概述 h a d o o p 是a p a c h e 开源组织的一个分布式计算开源框架，它可以运行在大型 集群的廉价硬件设备上。h a d o o p 为应用程序透明的提供了一组稳定可靠的接口。 本质上h a d o o p 是g o o g l em a p r e d u c e 算法模型的一个j a v a 实现，它让程序自动分 布到一个由普通机器组成的超大集群上并发执行。就如同j a v a 程序员可以不用考 虑内存泄露一样，h a d o o p 的r u n t i m e 系统会解决输入数据的分布细节，跨越机器 集群的程序执行调度，处理机器的失效，并且管理机器之间的通讯请求。h a d o o p 有许多元素构成。最底部是h a d o o pd i s t r i b u t e df i l es y s t e m ( h d f s ) ，它存储 h a d o o p 集群中所有存储节点上的文件。图2 2 是h a d o o p 的运行流程：h d f s ( 对 于本文) 的上一层是m a p r e d u c e 引擎，该引擎由j o b t r a c k e r s 和t a s k t r a c k e r s 组 成。m a p r e d u c e 算法模型和h d f s 是h a d o o p 的两个核心组件。 j o b s u b m i s i o n p r o t o c o l + ： l i n t e r u t t a c k e r p r o t o e o l t a s k m b i l l p r o t o e o l 一；f u 呻l 图2 2h a d o o p 运行流样图 f i g u r e 2 2t h ep r o c e s so fh a d o o p 对于h a d o o p 编码人员来说，需要完成的：t ：作如下： 1 ) 定义m a p p e r ，处理输入的k e y - v a l u e 对，输出中问结果。 2 )定义r e d u c e r ，可选，对中间结果进行规约，输出最终结果。 9 3 ) 定义i n p u t f o r m a t 和o u t p u t f o r m a t ，可选，i n p u t f o r m a t 将每行输入文件的 内容转换为j a v a 类供m a p p e r 函数使用，不定义时默认为s t r i n g 。 4 ) 定义m a i n 函数，在里面定义一个j o b 并运行它。 其余的工作就交给系统自动运行了，当然这罩还涉及到另外一些重要的配置和 调试的细节。h a d o o p 作为一个分布式开发的先进框架，拥有很多优点： 1 ) 扩容能力：能可靠地存储和处理千兆字节( p b ) 数据。 2 ) 成本低：可以通过普通机器组成的服务器群来分发以及处理数据。这些服 务器群总计可达数千个节点。 3 ) 高效率：通过分发数据，h a d o o p 可以在数据所在的节点上并行地( p a r a l l e l ) 处理它们，这使得处理非常的快速。 4 ) 可靠性：h a d o o p 能自动地维护数据的多份复制，并且在任务失败后能自动 地重新部署计算任务。 h a d o o p 的两个核心组件就是h d f s 文件系统和m a p r e d u c e 算法模型。下面 我们分两节详细阐述一下。 分布式文件系统h d f s h a d o o p 文件系统( h d f s ) 是一个运行在普通的硬件上的分布式文件系统， h d f s 是高容错性的，可以部署在低成本的硬件之上，h d f s 大数据集的应用程序。 图2 3 是h d f s 的体系结构： 图2 3h d f s 体系结构 f i g u r e 2 。3t h ea r c h i t e c t u r eo fh d f s 由图2 3 可知，c l i e n t 可以对d a t a n o d e 进行读和写操作，同时在n a m e n o d e l o 上对元数据进行操作。n a m e n o d e 上元数据控制d a t a n o d e 信息。为了更好地理解 h d f s 的工作机制，接下来从各个角度对h d f s 的优缺点进行讨论。 2 3 1假定与目标 1 1 硬件故障 h d f s 认为硬件的故障时很正常的。h d f s 系统由数百或数千个存储着文件数 据片断的服务器组成。早面有非常巨大的组成部分，每一个组成部分都可能频繁 地出现故障，这就意味着h d f s 里的一些组成部分总是处于故障状态，h d f s 可以 快速检测故障并自动恢复。这与前面提到的g f s 是一样的。 2 ) 流式的数据访问 运行在h d f s 之上的应用程序必须流式地访问它们的数据集。h d f s 设计成适 合批量处理而不是交互式的。重点是在数据吞吐量，而不是数据访问的响应时间。 3 ) 大数据集 运行在h d f s 之上的程序一般都要处理海量数据。一般的h d f s 文件都是g b 到t b 的大小，所以，h d f s 可以很好地支持大文件。它应该提供高聚合数据带宽 并且可以在一个集群中支持数百个节点，同时一个h d f s 文件应该可以支持一个 集群中千万的文件。 4 】简单一致性模型 多数h d f s 程序对文件操作需要是“一次写，多次读 模式。一个文件一旦 创建、写入、关闭之后就不再需要修改。这就简化了数据一致性问题因而保证了 高吞吐量的数据访问。m a p r e d u c e 程序和w e b 爬虫程序都好地适应了这个模型。 5 1 移动计算比移动数据更经济 应用程序计算所使用的数据在本地活着附近存储是最理想的状念，尤其是海 量数据。这就消除了网络的拥堵，提高了系统的整体吞吐量。这个假设认为计算 离数据更近优于将文件移动到程序运行的位置。h d f s 提供了让程序将自己移动到 离数据存储的位置更近的一系列接口。 6 ) 轻便的访问异构的软硬件平台 h d f s 应该设计成可以简单轻便地从一个平台迁移到另外一个平台，这样需要 海量数据处理的时候，很多平台都可以选择h d f s 文件系统。 2 3 。2名字节点与数据节点 h d f s 是一个主从结构的体系，一个h d f s 集群由一个名字节点与若干数据节 点组成，名字节点是一个管理文件的命名空间和调节客户端访问文件的主服务器， 集群中只有一个名字节点极大地简单化了系统的体系。名字节点管理所有h d f s 的元数据。系统设计成用户的实际数据不经过名字节点。数据节点是负责存储。 一般一台机器上面部属一个数据节点，有时也会把几个数据节点部属在一台机器 上，但这种情况不是很常见。这些机器一般都是普通的p c 机。p c 机上一般是 g u n l i n u x 操作系统，h d f s 是用j a v a 来写的，任何支持j a v a 的机器都可以运行 名字节点或数据节点，利用j a v a 语言的超轻便型，很容易将h d f s 部署到大范围 的机群上。 2 3 3数据复制 在集群中的大量机器之间h d f s 可以可靠地海量存储文件，各个文件以块序 列的形式存储。除了最后一个块文件其他块大小都是相同的。为了保证故障容错， 文件的块被复制。块的大小和复制因子都可以按照单个文件配置。h d f s 中的文件 都是严格地任何时候只有一个写操作。 名字节点控制所有的块复制操作。它周期性地接受来自集群中数据节点的“心 跳 回应和块报告。收到一个节点的“心跳”回应表示这个数据节点是正常的。 一个块报告包括该数据节点上的所有的块列表。 复制块的放置位置的选择严重影响h d f s 的可靠性和性能。这个特征是h d f s 和其他的分布式文件系统的区别。这个特征需要很多的调节和经验。根据机架的 复制布局目的就是提高数据的可靠性，可用性和网络带宽的利用。 h d f s 通常运行在跨越很多机架的集群机器之上。两个不同机架上的节点通信 是通过交换机进行的，一般来说，处于相同机架上的节点比处于不同机架上的节 点的的网络带宽有优势。 系统启动时每一个数据节点自检它所属的机架，然后在注册的时候告知名字 节点它所属的机架i d 。h d f s 提供了一系列可捅拔模块的a p i 用于挂载检测机架。 一个简单但不是最优的方式就是跨机架进行复制操作，这样可以保证在这个机架 出现故障而不丢失数据，还能在读数据的时候充分利用不同机架的带宽。数据块 均匀地被复制分散在集群中简单地实现了组件实效负载均衡，但是这个方式增加 了写的成本，因为写的时候需要传输文件块到很多的机架。 最常见的情况是复制因子为3 ，此时h d f s 放置方式是将第一个放在本地节点， 将第二个复制放到本地机架上的另外一个节点而将第三个复制放到4 州机架上的 节点。这种方式减少了机架内的写流量，提高了写的性能。山于文件块存在两个 不同的机架，而不是三个。在没有影响数据的可靠性和可用性的前提下，减少了 1 2 读操作的网络聚合带宽。 为了降低全局带宽的消耗和时间的延迟，h d f s 总是试图读取离其最近的复制。 假如在读节点的同一个机架上就有这个复制，就直接读这个，如果h d f s 集群是 跨越多个数据中心，那么本地数据中心的复制是优先于远程的复制。 系统启动的时候，名字节点进入安全模式。安全模式下不发生文件块的复制。 名字节点接受来自数据节点的“心跳”回应和块报告。一个块报告包括当前数据 节点数据块的列表。 每一个块有一个最小复制因子。当名字节点检查