云计算技术与大规模数据并行处理

云计算与

大规模数据并行处理技术计算机科学与技术系软件新技术国家重点实验室主要内容第一部分：云计算技术简介简要介绍云计算及其主要特点，云计算发展背景与现状，云计算的关键技术第二部分：MapReduce大规模数据并行处理技术简要介绍Google和HadoopMapReduce大规模数据并行处理技术第三部分：大规模数据并行处理技术研究与应用介绍大规模数据并行处理技术研究，主要讨论大规模数据并行算法研究、大规模数据索引查询技术、以及Hadoop改进和优化技术研究第一部分

云计算技术云计算技术简介什么是云计算？CloudComputing,UtilityComputing,ServiceComputing……通过集中式远程计算资源池，以按需分配方式，为终端用户提供强大而廉价的计算服务能力工业化部署、商业化运作的大规模计算能力一种新的、可商业化的计算和服务模式计算能力像水电煤气一样，按需分配使用资源池物理上对用户透明就像在云端一样云计算的主要特点透明的云端计算服务“无限”多的计算资源，强大的计算能力按需分配，弹性伸缩，取用方便，成本低廉资源共享，降低企业IT基础设施建设维护费用应用部署快速而容易软件/应用功能更新方便快捷节省能源，绿色环保集计算技术之大成，具有很强的技术性、工程型特点云计算的分类按云计算服务层面进行分类SaaS：SoftwareasaService提供各种应用软件服务PaaS：PlatformasaService提供软件支撑平台服务IaaS：InfrastructureasaService提供接近于裸机(物理机或虚拟机)的计算资源

和基础设施服务云计算硬件平台云计算的分类云计算软件支撑平台云计算应用服务软件SaaS如腾讯云词典PaaS如GoogleAppEngIaaS如AmazonEC2云计算应用按云计算服务层面进行分类云计算的分类按云计算系统类型进行分类美国联邦云计算战略报告中，定义了4中云：公用云：提供面向社会大众、公共群体的云计算服务如Amazon云平台，GoogleAppEng

公有云有很多优点，但最大的一个缺点是难以保证数据的私密性私有云：提供面向应用行业/组织内的云计算服务如政府机关、移动通信、学校等内部使用的云平台

私有云可较好地解决数据私密性问题，对移动通信、公安等数据私密性要求特别高的企业或机构，建设私有云将是一个必然的选择云计算的分类按云计算系统类型进行分类社区云：提供面向社团组织内用户使用的云计算平台

如美国航天局(NASA)Nebula云平台为NASA内的研究人员提供快速的IT访问服务混合云：包含以上2种以上云计算类型的混合式云平台云计算发展背景云计算技术的争议反方：云计算是业界的商业性行为正方：云计算是计算技术的重大发展趋势个人认为：云计算技术有其发展的必然性和必要性

云计算发展背景

集中分散集中60-70’s:大型机(mainframe),

集中式、终端用户共享80-90’s:个人计算机,人手一台95-06:互联网/网格/集群

07-现在:云计算“天下大势，合久必分，分久必合”“否定之否定，螺旋式上升”云计算发展背景应用需求背景大粒度应用系统的规模越来越大应用系统数据量越来越大中国移动全国每天的电话短信通联记录数据达到500TB；而中国移动一个流量最大的省每天的通联记录数据可达到65TB阿里巴巴电子商务平台日处理数据量将达到500TB百度存储100-1000PB数据，每日处理10-100PB；存储1千-1万亿网页，索引100-1000亿网页2009年eBays数据仓库，一个有2PB用户数据，另一个6.5PB用户数据包含170TB记录且每天增长150GB个记录Facebook：2.5PB用户数据，每天增加15TB仅2011年，全世界产生1.8ZB（1.8万亿GB）数据，相当于每位美国人每分钟写3条Twitter，不停地写2.7万年YouTube每分钟有13h视频上传，每天数据10TB相当于好莱坞每周发行57000部电影

云计算发展背景应用需求背景大粒度应用系统的规模越来越大超大的计算量和计算复杂度用SGI工作站进行电影渲染时，每帧一般需要1～2小时一部2小时的电影渲染需要：

2小时x3600秒x24帧x(1~2小时)/24小时=20~40年!特殊场景每帧可能需要60个小时(影片“星舰骑兵”中数千只蜘蛛爬行的场面),用横向4096象素分辨率进行渲染时，如果以每帧60个小时的速度，则1秒的放映量（24帧）需要60天的渲染时间,1分钟则需要100年！云计算发展背景应用需求背景小粒度应用系统资源重复、无法共享

企业内大量的小粒度应用系统需要添置独立的硬件资源，但忙闲不均，忙时资源不够，闲时资源空置，资源无法相互调配和共享，造成资源和资金浪费

淘宝网案例：后台设置约15万台服务器，服务于不同的应用系统；而不同应用系统的负载不同，忙闲不均；据淘宝测算，如能在不同应用间合理调配计算资源，大约可省去2/3约10万台服务器，以每台3万元计算，约可节省30亿元！云计算发展背景技术发展背景贯穿整个计算机技术发展历史的两条主线：

计算能力角度：不断追求计算性能提升无论是微处理器还是巨型机，近20年性能提高3千多倍

使用角度：不断追求易用性和灵活性可获得性、易用性、可扩展性和灵活性不断提升Intel微处理器每秒1千8百亿次浮点运算！近20年性能提高3千多倍不断追求计算性能提升巨型机：中国天河一号，2010年底世界TOP500强第1名

每秒2千5百多万亿次浮点运算，近20年性能提高3千多倍亿亿千万亿百万亿十万亿万亿千亿百亿十亿亿TOP500系统体系结构演化向量机=>SMP=>MPP=>ClusterCluster以高获得性、高可扩展性优势成为发展主流

不断追求方便性和灵活性云计算发展背景云计算发展背景技术发展背景

虽然新的计算技术在易用性和灵活性上有不断提高，但仍然存在很大不足：

计算能力仍取决于硬件计算资源，计算能力不够时，需要不断增加硬件资源；空闲时，硬件资源闲置浪费，不能共享；计算能力的获取和使用上仍然存在较大的制约。云计算正是一种解决这一问题的新的计算服务模式，其基本思路是集中计算资源提供巨大的计算能力的同时，提供使用上的方便性和灵活性云计算发展背景技术发展背景云计算是诸多计算技术发展成熟与自然进化的产物计算机虚拟化技术、大规模并行计算、分布式存储、面向服务构架、公用服务计算等诸多技术广泛应用计算机系统规模和处理能力迅速扩大技术发展成熟与自然进化的结果云计算发展背景“Thecomputationandthedataandsoforthareintheservers.…Wecallitcloudcomputing.”(ErickSchmidt,2006)“computationmaysomedaybeorganizedasapublicutility”(JohnMcCarthy,1960)“云计算”的概念在2006年由Google公司正式提出但最初的思想雏形可追溯到更早的时间云计算发展背景云计算发展意义云计算出现的意义，可与20世纪电力工业的变革相比20世纪初电力工业变革的几项关键技术

发电容量大幅提升

交流电的出现(1888)

电表的发明和使用(1894)20世纪初私有电厂向公共电力服务转化过程1900:美国有5万多个私有小型电厂，3千6百个中心电站1907:40%并入了公共电力服务系统

1920:70%并入了公共电力服务系统

1930:80%~90%并入了公共电力服务系统

云计算发展背景云计算发展意义

云计算的一个重要目标是，把计算能力变成像水电等公用服务一样，随用随取，按需使用。故此也有人把云计算称为“UtilityComputing”这里Utility不是效用、实用的意思，在英文里Utility有一个专门的含义，专指类似于水电煤气的公用服务，故UtilityComputing应译为“公用服务计算”云计算发展背景云计算发展意义

2011年2月8日美国奥巴马总统签署了联邦云计算战略报告，制定该报告的目的：TheFederalGovernment’scurrentInformationTechnology(IT)environmentischaracterizedbylowassetutilization,afragmenteddemandforresources,duplicativesystems,environmentswhicharedifficulttomanage,andlongprocurementleadtimes.TheseinefficienciesnegativelyimpacttheFederalGovernment’sabilitytoservetheAmericanpublic.Cloudcomputinghasthepotentialtoplayamajorpartinaddressingtheseinefficienciesandimprovinggovernmentservicedelivery.Thecloudcomputingmodelcansignificantlyhelpagenciesgrapplingwiththeneedtoprovidehighlyreliable,innovativeservicesquicklydespiteresourceconstraints.美国联邦政府部门计划用全部的800亿美元IT预算中的200亿作为云计算平台开发建设的费用。美国联邦云计算战略报告，2011/2/8云计算发展背景云计算发展意义

美国联邦云计算战略报告认为：CloudisafundamentalshiftinITCloudcomputingenablesITsystemstobescalableandelastic.Endusersdonotneedtodeterminetheirexactcomputingresourcerequirementsupfront.Instead,theyprovisioncomputingresourcesasrequired,on-demand.Usingcloudcomputingservices,aFederalagencydoesnotneedtoowndatacenterinfrastructuretolaunchacapabilitythatservesmillionsofusersCloudcomputingcansignificantlyimprovepublicsectorITAnumberofgovernmentagenciesareadoptingcloudtechnologiesandarerealizingconsiderablebenefits.Forinstance,NASANebula,throughacommunitycloud,givesresearchersaccesstoITservicesrelativelyinexpensivelyinminutes.Priortoadoptingthisapproach,itwouldtakeresearchersmonthstoprocureandconfigurecomparableITresourcesandsignificantmanagementoversighttomonitorandupgradesystems.ApplyingcloudtechnologiesacrosstheentireFederalGovernmentcanyieldtremendousbenefitsinefficiency,agility,andinnovation.云计算发展现状与趋势业界云计算技术的发展自2006年Google公司提出云计算技术的概念后，全球IT著名企业纷纷予以极大关注，并投入了巨大力量进行云计算技术的研究开发。GoogleCloudInfrastructureSchedulerChubbyGFSmasterNodeNodeNode…UserGoogleAppEngineSchedulerslaveGFSLinuxNodeMapReduceFrameworkBigTableServerGoogleCloudInfrastructure

(GoogleAppEngine，PaaS型公用云平台)GoogleAppEngine提供了一种PaaS类型的云计算服务平台，用户可租用该平台的计算资源，并使用AppEngine提供的各种应用开发和支撑软件平台开发和部署自己的应用软件S3EBSEC2EBSEC2EBSEC2EBSEC2SimpleDBSQSUserDeveloperAmazonElasticComputingCloud

(AmazonEC2，IaaS型公用云平台)SQS:SimpleQueueServiceEC2:RunningInstanceofVirtualMachinesEBS:ElasticBlockService,ProvidingtheBlockInterface,StoringVirtualMachineImagesS3:SimpleStorageService,SOAP,ObjectInterfaceSimpleDB:SimplifiedDatabaseAmazonEC2提供了一种IaaS类型的云计算服务平台，在该平台上用户可部署自己的系统软件，完成应用软件的开发和发布。28租用案例2007年，美国纽约时报租用Amazon云计算平台，用于将1851-1922年纽约时报的1100万篇报刊文章转换为PDF文件,供读者上网免费访问。共租用了100个EC2节点，运行了24小时，处理了4TB的报刊原始扫描图像，生成了1.5TB的PDF文件。每节点每小时费用为10美分，整个计算任务仅花费了240美元(100节点x24小时x$0.10)！如果用自己的服务器，将需要数月和多得多的费用！

AmazonElasticComputingCloud29MicrosoftCloudServices

(WindowAzure，私有云平台管理和服务软件)

Azure™ServicesPlatformMicrosoftSharePointServicesMicrosoftDynamicsCRMServicesIBM云计算方案

(私有云计算平台管理和服务软件)提供私有云计算资源管理软件平台，主要负责管理和调度虚拟计算资源，完成资源申请、调度和管理等整个生命周期管理2/3/202331其它国内外IT企业云计算研发

除以上几家全球著名的IT企业外，其它著名IT企业如Cisco、HP、EMC、VMWare等，都在大力推进云计算技术和系统研发。国内诸多著名IT企业，如中国移动、中国电信、中国联通、阿里巴巴、腾讯、百度、万网、中兴通信、华为等，也大力推动云计算研发。云计算发展现状与趋势32中国移动BigCloud云计算发展现状目标是建立可为中国移动企业内部进行海量通信数据存储和处理的使用的私有云平台，以及为社会大众和群体使用的公有云平台。大规模低成本数据中心的订制化硬件设计分布式文件系统结构化数据存储非结构化数据存储分布式计算资源管理大规模离线数据处理在线服务综合监控计费系统安全高可靠保障机制云计算编程模型与访问接口商品交易平台软件服务平台数据服务平台企业IT服务统一的资源调度服务阿里巴巴电子交易云计算平台云计算发展现状与趋势云计算发展趋势云计算将提供一种新的计算模式和服务模式。云计算将是计算技术的一次重大变革，作为今后计算发展的潮流将大大改变现有的计算模式，对计算技术领域本身以及各个应用行业都将带来重大的影响，提供更多的发展机遇通过云计算人们能获得前所未有的强大计算能力，并能按需分配，按需付费，提升了本地计算能力但使用成本低廉，而且还能大幅削减不断升级软硬件系统的费用通过云计算平台强大的计算和存储能力，人们将能完成传统系统所无法完成的计算和处理，开发出更强大的应用功能，提供更多智能化应用云计算发展现状与趋势云计算发展趋势通过各种个人终端使用云端的计算能力，将大大扩展现有的移动设备的计算能力，提供各种新的增值应用模式云计算与物联网有重要的关联性，作为未来的人机物计算的重要组成部分，云计算关注的是服务器端技术，物联网关注的客户和终端技术云计算发展现状与趋势云计算发展趋势面向民生工程的政企应用将是云计算的潜在市场，并能带动产业整体发展未来3年，云计算应用将以政府、电信、教育、医疗、金融、石油石化和电力等行业为重点，在中国市场逐步被越来越多的企业和机构采用，市场规模将从2009年的92.23亿元增长到2012年的606.78亿元，年复合增长率达87.4%（来源:赛迪顾问

中国云计算产业发展白皮书）云计算的关键技术主要包括以下关键技术虚拟化技术：虚拟机的安装、设置、调度分配、使用、故障检测与失效恢复等云计算构架技术：研究解决适合于云计算的系统软硬件构架资源调度技术：解决物理或虚拟计算资源的自动化分配、调度、配置、使用、负载均衡、回收等资源管理云计算的关键技术主要包括以下关键技术并行计算技术：针对大规模数据或复杂计算应用，解决数据或计算任务切分和并行计算算法设计问题海量存储技术：解决大规模数据的分布存储、共享访问、数据备份等问题云安全技术：解决云计算系统的访问安全性、数据安全性（包括数据私密性）等问题此外，还有云计算中心的节能和散热等工程技术问题云计算的关键技术怎样才算是云计算？云计算概念很热，各级政府部门、很多行业和应用都想搞云计算。大家很热议的问题是：云计算与传统计算系统有什么区别？系统做成什么样才能称得上是云计算系统？云计算的关键技术怎样才算是云计算？回答这两个问题必须从发展云计算技术的两个根本目的、以及云计算区别于传统计算的特点上来看提高计算能力：集中计算资源，为应用提供强大而廉价的计算能力 =>大规模并行计算能力提高易用性和灵活性：合理调配资源，为应用提供弹性资源分配、资源共享

=>资源虚拟化和弹性调度

云计算的关键技术怎样才算是云计算？因此，个人认为：一个计算系统必须具备以下两个特征才能算是云计算系统（至少具备第一个特征）:资源虚拟化和弹性调度

基于虚拟化和弹性调度，以按需分配方式，为小粒度应用提供计算资源，实现资源共享大规模并行计算服务

基于云端的强大而廉价的计算能力，为大粒度应用提供传统计算系统或用户终端所无法完成的计算服务。这些计算能力包括海量数据存储能力、以及大规模并行计算能力。第二部分

MapReduce

大规模数据并行处理技术大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？大规模数据处理和行业应用需求日益增加和迫切出现越来越多的超大规模数据处理应用需求，传统系统难以提供足够的存储和计算资源进行处理，云计算平台是最理想的解决方案。调查显示：目前，IT专业人员对云计算中诸多关键技术最为关心的是大规模数据并行处理技术大数据并行处理没有通用和现成的解决方案对于应用行业来说，云计算平台软件、虚拟化软件都不需要自己开发，但行业的大规模数据处理应用软件没有通用的软件，需要针对特定的应用需求专门开发，涉及到诸多并行化算法、索引查询优化技术研究、以及系统的设计实现大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？处理数据的能力大幅落后于数据增长速度

磁盘容量增长远远快过存储访问带宽和延迟：80年代中期数十MB到今天1-2TB，增长10万倍，而延迟仅提高2倍，带宽仅提高50倍！海量数据隐含着更准确的事实

研究发现：训练数据集越大,数据分类精度越高；大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果大规模数据并行处理技术的重要性大数据(BigData)应用需求

出现越来越多的大数据应用和行业需求。2008年，在Google成立10周年之际，《Nature》杂志出版一期专刊专门讨论未来的大数据（BigData）处理相关的一系列技术问题和挑战。据预计：未来10年，数据量将从数百EB增长到数百ZB量级！Google大规模数据并行处理技术简介GoogleMapReduceGoogle在2004年提出的一种通用的大规模数据并行计算平台和编程模型和框架MapReduce发明后，Google大量用于各种海量数据处理，目前Google内部有7千以上的程序基于MapReduce实现，包括其搜索引擎

的全部索引处理什么是MapReduce？MapReduce三个层面的含义基于集群的高性能并行计算平台(ClusterInfrastructure)

允许用市场上的普通服务器，构成一个包含数百到数千个节点的分布式并行计算集群并行程序开发与运行框架(SoftwareFramework)提供了一个庞大但设计精良的并行计算软件构架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行子任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算中的很多复杂细节交由系统负责处理，大大减少了软件开发人员的负担并行程序设计模型与方法(ProgrammingModel&Methodology)

借助于函数式语言中的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了完整的并行编程接口，完成大规模数据处理典型的流式大数据处理问题的特征大量数据记录/元素进行重复处理对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息排序和整理中间结果以利后续处理收集整理中间结果产生最终结果输出MapReduce关键思想：借助于Lisp函数式程序设计思想，为大数据处理过程中的两个主要处理操作提供一种抽象机制MapReduce的基本设计思想MapReduce的基本设计思想MapReduce三个层面上的基本设计思想如何对付大数据处理：分而治之

对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略上升到抽象模型：Mapper与Reducer

MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型，程序员只需描述需要“做什么”

(whattodo),不需要关心具体“怎么做”（How

todo)上升到统一构架：为程序员隐藏系统层细节对于具体的“怎么做”的问题，MapReduce提供了一个统一的计算框架，为程序员隐藏了数据存储访问、数据块划分、计算节点调度管理、数据通信、结果收集、容错处理、负载均衡、性能优化等诸多低层细节，交由系统负责处理，因而大大减轻了程序员进行并行编程时的负担MapReduce的基本设计思想大数据任务划分和并行计算模型大数据计算任务子任务子任务子任务子任务……任务划分计算结果结果合并Map和Reduce操作的抽象描述

MapReduce借鉴了函数式程序设计语言Lisp中的思想，定义了如下的Map和Reduce两个抽象的编程接口，由用户去编程实现:map:(k1;v1)[(k2;v2)]输入：键值对(k1;v1)表示的数据处理：文档数据记录(如文本文件中的行，或数据表格中的行)将以“键值对”形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果[(k2;v2)]输出：键值对[(k2;v2)]表示的一组中间数据MapReduce的基本设计思想MapReduce的基本设计思想Map和Reduce操作的抽象描述

reduce:(k2;[v2])

[(k3;v3)]输入：

由map输出的一组键值对[(k2;v2)]将被进行合并处理将同样主键下的不同数值合并到一个列表[v2]中，故reduce的输入为(k2;[v2])处理：对传入的中间结果列表数据进行某种整理或进一步的处理,并产生最终的某种形式的结果输出[(k3;v3)]。输出：最终输出结果[(k3;v3)]MapReduce的基本设计思想基于Map和Reduce的并行计算模型

海量数据存储……数据划分MapMapMapMap初始kv键值对初始kv键值对初始kv键值对初始kv键值对中间结果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)计算结果(K1,val)(K2,val)(K3,val)MapReduce的基本设计思想基于Map和Reduce的并行计算模型各个map函数对所划分的数据并行处理，从不同的输入数据产生不同的中间结果输出各个reduce也各自并行计算，各自负责处理不同的中间结果数据集合进行reduce处理之前,必须等到所有的map函数做完，因此,在进入reduce前需要有一个同步障(barrier);这个阶段也负责对map的中间结果数据进行收集整理(aggregation&shuffle)处理,以便reduce更有效地计算最终结果最终汇总所有reduce的输出结果即可获得最终结果MapReduce并行处理示例文档词频统计WordCount设有4组原始文本数据：Text1:theweatherisgoodText2:todayisgoodText3:goodweatherisgoodText4:today

hasgoodweather传统的串行处理方式(Java)：

String[]text=newString[]{“helloworld”,“helloeveryone”,“sayhellotoeveryoneintheworld”｝;HashTableht=newHashTable();for(i=0;i<3;++i){StringTokenizerst=newStringTokenizer(text[i]);while(st.hasMoreTokens()){Stringword=st.nextToken();if(!ht.containsKey(word)){ht.put(word,newInteger(1));}else{intwc=((Integer)ht.get(word)).intValue()+1;//计数加1ht.put(word,newInteger(wc));}}}for(Iteratoritr=ht.KeySet().iterator();itr.hasNext();){Stringword=(String)itr.next();System.out.print(word+“:”+(Integer)ht.get(word)+“;”);}输出：good:5;has:1;is:3;the:1;today:2;weather:3MapReduce并行处理示例文档词频统计WordCountMap处理示例设使用4个map节点：map节点1:

输入：(text1,“theweatherisgood”)

输出：(the,1),(weather,1),(is,1),(good,1)map节点2:

输入：(text2,“todayisgood”)

输出：(today,1),(is,1),(good,1)map节点3:

输入：(text3,“goodweatherisgood”)

输出：(good,1),(weather,1),(is,1),(good,1)map节点4:

输入：(text3,“todayhasgoodweather”)

输出：(today,1),(has,1),(good,1),(weather,1)Barrier(good,1)(good,1)(good,2)(good,1)PartitionerPartitionerPartitionerPartitioner(is,1)(is,1)(is,1)(has,1)(weather,1)(weather,1)(weather,1)(the,1)(today,1)(today,1)海量数据存储计算结果……数据划分Map初始kv键值对初始kv键值对初始kv键值对初始kv键值对MapMapMap中间结果(the,1)(weather,1)(is,1)(good,1)CombinerCombinerCombinerCombiner(the,1)(weather,1)(is,1)(good,1)(today,1)(is,1)(good,1)(good,1)(weather,1)(is,1)(good,1)(today,1)(has,1)(good,1)(weather,1)(today,1)(is,1)(good,1)(good,2)(weather,1)(is,1)(today,1)(has,1)(good,1)(weather,1)ReduceReduceReduce(good,5)(is,3)(has,1)(weather,3)(the,1)(today,2)完整的MapReduce并行处理模型和过程MapReduce并行处理示例MapReduce并行处理示例文档词频统WordCountReduce处理示例设使用3个Reduce节点:reduce节点1:

输入：(good,1),(good,1),(good,2),(good,1)

输出：(good,5)reduce节点2:

输入：(has,1),(is,1),(is,1),(is,1),

输出：(has,1),(is,3)reduce节点3:

输入：(the,1),(today,1),(today,1)(weather,1),(weather,1),(weather,1)

输出：(the,1),(today,2),(weather,3)输出：good:5is:3has:1the:1today:2weather:3MapReduce并行处理示例文档词频统WordCountMapReduce程序实现MapReduce伪代码(实现Map和Reduce两个函数)：ClassMappermethodmap(Stringinput_key,Stringinput_value):

//input_key:textdocumentname//input_value:documentcontents

foreachwordwininput_value:

EmitIntermediate(w,"1");ClassReducermethodreduce(Stringoutput_key,

Iteratorintermediate_values):

//output_key:aword//output_values:alistofcounts

intresult=0;

foreachvinintermediate_values:result+=ParseInt(v);

Emit(output_key，result);提供统一的计算框架主要需求和目标：实现自动并行化计算为程序员隐藏系统层细节需要考虑的细节技术问题：如何管理和存储数据？如何划分数据？如何调度计算任务并分配map和reduce节点？如果节点间需要共享或交换数据怎么办？如何考虑数据通信和同步？如何掌控节点的执行完成情况？如何收集中间和最终的结果数据？节点失效如何处理？如何恢复数据？如何恢复计算任务？节点扩充后如何保证原有程序仍能正常运行并保证系统性能提升？问题：我们能把这些细节和复杂性都交给系统去负责处理吗？提供统一的计算框架答案：MapReduce之前的并行计算方法都未能做到

但MapReduce做到了！MapReduce提供一个统一的计算框架，可完成：计算任务的划分和调度数据的分布存储和划分处理数据与计算任务的同步结果数据的收集整理(sorting,combining,partitioning,…)系统通信、负载平衡、计算性能优化处理计算和存储节点出错检测和失效恢复MapReduce的主要设计思想与特点

向“外”横向扩展，而非向“上”纵向扩展

（Scale“out”,not“up”）

即MapReduce集群的构筑选用价格便宜、易于扩展的大量低端商用服务器，而非价格昂贵、不易扩展的高端服务器（SMP）低端服务器市场与高容量DesktopPC有重叠的市场，因此，由于相互间价格的竞争、可互换的部件、和规模经济效应，使得低端服务器保持较低的价格基于TPC-C在2007年底的性能评估结果,一个低端服务器平台与高端的共享存储器结构的服务器平台相比,其性价比大约要高4倍;如果把外存价格除外,低端服务器性价比大约提高12倍对于大规模数据处理，由于有大量数据存储需要，显而易见，基于低端服务器的集群远比基于高端服务器的集群优越，这就是为什么MapReduce并行计算集群会基于低端服务器实现*CitefromJimmyLin,University

ofMaryland,Data-IntensiveTextprocessingwithMapReduceMapReduce的主要设计思想与特点

失效被认为是常态（Assumefailuresarecommon）MapReduce集群中使用大量的低端服务器(Google目前在全球共使用百万台以上的服务器节点),因此，节点硬件失效和软件出错是常态，因而：一个良好设计、具有容错性的并行计算系统不能因为节点失效而影响计算服务的质量，任何节点失效都不应当导致结果的不一致或不确定性；任何一个节点失效时，其它节点要能够无缝接管失效节点的计算任务；当失效节点恢复后应能自动无缝加入集群，而不需要管理员人工进行系统配置MapReduce并行计算软件框架使用了多种有效的机制，如节点自动重启技术，使集群和计算框架具有对付节点失效的健壮性，能有效处理失效节点的检测和恢复。

把计算向数据迁移 Movingprocessingtothedata传统高性能计算系统通常有很多处理器节点与一些外存储器节点相连，如用区域存储网络(SAN,StorageAreaNetwork)连接的磁盘阵列，因此，大规模数据处理时外存文件数据I/O访问会成为一个制约系统性能的瓶颈。为了减少大规模数据并行计算系统中的数据通信开销，代之以把数据传送到处理节点(数据向处理器或代码迁移)，应当考虑将处理向数据靠拢和迁移。MapReduce采用了数据/代码互定位的技术方法，计算节点将首先将尽量负责计算其本地存储的数据,以发挥数据本地化特点(locality),仅当节点无法处理本地数据时，再采用就近原则寻找其它可用计算节点，并把数据传送到该可用计算节点。MapReduce的主要设计思想与特点

顺序处理数据、避免随机访问数据 Processdatasequentiallyandavoidrandomaccess大规模数据处理的特点决定了大量的数据记录不可能存放在内存、而只可能放在外存中进行处理。磁盘的顺序访问和随即访问在性能上有巨大的差异

例：100亿(1010)个数据记录(每记录100B,共计1TB)的数据库

更新1%的记录(一定是随机访问)需要1个月时间；

而顺序访问并重写所有数据记录仅需1天时间！MapReduce设计为面向大数据集批处理的并行计算系统，所有计算都被组织成很长的流式操作，以便能利用分布在集群中大量节点上磁盘集合的高传输带宽。MapReduce的主要设计思想与特点

为应用开发者隐藏系统层细节 Hidesystem-leveldetailsfromtheapplicationdeveloper软件工程实践指南中，专业程序员认为之所以写程序困难，是因为程序员需要记住太多的编程细节(从变量名到复杂算法的边界情况处理)，这对大脑记忆是一个巨大的认知负担,需要高度集中注意力而并行程序编写有更多困难，如需要考虑多线程中诸如同步等复杂繁琐的细节，由于并发执行中的不可预测性，程序的调试查错也十分困难；大规模数据处理时程序员需要考虑诸如数据分布存储管理、数据分发、数据通信和同步、计算结果收集等诸多细节问题MapReduce提供了一种抽象机制将程序员与系统层细节隔离开来，程序员仅需描述需要计算什么(whattocompute),而具体怎么去做(howtocompute)就交由系统的执行框架处理，这样程序员可从系统层细节中解放出来，而致力于其应用本身计算问题的算法设计MapReduce的主要设计思想与特点

平滑无缝的可扩展性 Seamlessscalability主要包括两层意义上的扩展性：数据扩展和系统规模扩展理想的软件算法应当能随着数据规模的扩大而表现出持续的有效性，性能上的下降程度应与数据规模扩大的倍数相当在集群规模上，要求算法的计算性能应能随着节点数的增加保持接近线性程度的增长绝大多数现有的单机算法都达不到以上理想的要求；把中间结果数据维护在内存中的单机算法在大规模数据处理时很快失效；从单机到基于大规模集群的并行计算从根本上需要完全不同的算法设计奇妙的是，MapReduce几乎能实现以上理想的扩展性特征。

多项研究发现基于MapReduce的计算性能可随节点数目增长保持近似于线性的增长MapReduce的主要设计思想与特点并行数据处理MapReduceGoogle分布式文件系统GFS(GoogleFileSystem)结构化数据表BigTable分布式锁管理ChubbyMapReduceBigTableGFSChubbyGoogleMapReduce框架和关键技术用市场上的普通服务器，构建了非常可靠的大规模并行计算集群！

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)1.有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序2.系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker)3.主节点为作业程序寻找和配备可用的Map节点，并将程序和数据传送给map节点4.主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点5.主节点启动每个Map节点执行程序，每个map节点尽可能读取本地或本机架的数据进行计算6.每个Map节点处理读取的数据块,并做一些数据整理工作(combining,sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置7.主节点等所有Map节点计算完成后,开始启动Reduce节点运行；Reduce节点从主节点掌握的中间结果数据位置信息读取这些数据8.Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果70GoogleMapReduce的基本工作原理失效检测和恢复处理主节点失效主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费。工作节点失效工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送检测命令，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行

GoogleMapReduce的基本工作原理带宽优化问题

大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销。解决方案每个Map节点处理完成的中间键值队将由Combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值。(good,1)(weather,1)(is,1)(good,1)(good,2)(weather,1)(is,1)combiner

GoogleMapReduce的基本工作原理计算优化问题Reduce节点必须要等到所有Map节点计算计算才能开始执行，因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。解决方案把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果。根据Google的测试，使用了这个冗余Map节点计算方法以后，计算任务性能提高40%多！

GoogleMapReduce的基本工作原理用数据分区解决数据相关性问题问题

一个Reduce节点上的计算数据可能会来自多个Map节点，因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起。解决方案在Map阶段进行了Combine以后，可以根据一定的策略对Map输出的中间结果进行分区(partition)，这样即可解决以上数据相关性问题避免Reduce计算过程中的数据通信。例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果GoogleGFS的基本构架GoogleGFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑；GFS是一个构建在分布节点本地文件系统之上的一个逻辑上文件系统，它将数据存储在物理上分布的每个节点上，但通过GFS将整个数据形成一个逻辑上整体的文件。分布式文件系统GFS工作原理……GoogleGFSGoogleMapReduceMapReduceApplicationsGoogleGFS的基本构架廉价本地磁盘分布存储

各节点本地分布式存储数据，优点是不需要采用价格较贵的集中式磁盘阵列，容量可随节点数增加自动增加多数据自动备份解决可靠性

采用廉价的普通磁盘，把磁盘数据出错视为常态，用自动多数据备份存储解决数据存储可靠性问题为上层的MapReduce计算框架提供支撑GFS作为向上层MapReduce执行框架的底层数据存储支撑，负责处理所有的数据自动存储和容错处理，因而上层框架不需要考虑低层的数据存储和数据容错问题分布式文件系统GFS工作原理GoogleGFS的基本构架和工作原理

分布式文件系统GFS工作原理CitefromGhemawatetal.(SOSP2003)GFSMasterGFSMaster：保存GFS文件系统的三种元数据：命名空间(NameSpace),即整个分布式文件系统的目录结构

Chunk与文件名的映射表Chunk副本的位置信息，每一个Chunk默认有3个副本GFSChunkServer：用来保存大量实际数据的数据服务器；每个数据块缺省划分为64MB在Google发表了文章后，DougCutting，2004年，开源项目Lucene(搜索索引程序库)和Nutch(搜索引擎)的创始人，发现MapReduce正是其所需要的解决大规模分布数据处理的重要技术，因而模仿GoogleMapReduce，基于Java设计出了称为Hadoop的开源MapReduce，该项目成为Apache下最重要项目Hadoop目前最新版本是0.23.0,11/11/2010Yahoo是Hadoop联盟中最大的支持者，目前大量使用了Hadoop集群Yahoo!Hadoop集群(引自Yahoo）开源的HadoopMapReducedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodenamenodenamenodedaemonjobsubmissionnodejobtrackerHadoopMapReduce的基本工作原理数据存储与计算节点构架HadoopMapReduce的基本工作原理对等于GoogleMapReduce中的Master对等于GoogleMapReduce中的WorkerHadoopMapReduce程序执行过程HadoopMapReduce程序执行过程HadoopMapReduce的基本工作原理HDFS基本构架对等于GFS

Master对等于GFS

ChunkServer应用程序HDFS客户端文件名或数据块号数据块号，数据块位置HDFSNameNodeDataNode数据DataNode数据DataNode数据Hadoop的分布式文件系统HDFSGoogle技术培训2009年12月Google在清华大学举办的MapReduce技术培训班大规模数据并行技术培训、教学和平台建设课程建设2009年参加了Google公司MapReduce技术培训班，后与Google公司签约在Google资助下开设了“MapReduce大规模数据并行处理”课程，是目前为止江苏省唯一开设该课程的教师和院系大规模数据并行技术培训、教学和平台建设教材出版2011年7月合著编写《实战Hadoop》，有关Hadoop技术第一本具有原著性质的书籍，456页，9月电子工业出版出版发行。大规模数据并行技术培训、教学和平台建设

《实战Hadoop》大规模数据并行技术培训、教学和平台建设

5.1简介1145.2复合键值对的使用1155.2.1把小的键值对合并成大的键值对1155.2.2巧用复合键让系统完成排序1175.3用户定制数据类型1235.3.1hadoop内置的数据类型1235.3.2用户自定义数据类型的实现1245.4用户定制输入/输出格式1265.4.1hadoop内置的数据输入格式和recordreader1265.4.2用户定制数据输入格式与recordreader1275.4.3hadoop内置的数据输出格式与recordwriter1335.4.4用户定制数据输出格式与recordwriter1345.4.5通过定制数据输出格式实现多集合文件输出1345.5用户定制partitioner和combiner1375.5.1用户定制partitioner1375.5.2用户定制combiner1395.6组合式mapreduce计算作业1415.6.1迭代mapreduce计算任务1415.6.2顺序组合式mapreduce作业的执行1425.6.3具有复杂依赖关系的组合式mapreduce作业的执行1445.6.4mapreduce前处理和后处理步骤的链式执行1455.7多数据源的连接1485.7.1基本问题数据示例1495.7.2用datajoin类实现reduce端连接1505.7.3用全局文件复制方法实现map端连接1585.7.4带map端过滤的reduce端连接1625.7.5多数据源连接解决方法的限制1625.8全局参数/数据文件的传递与使用1635.8.1全局作业参数的传递1635.8.2查询全局mapreduce作业属性1665.8.3全局数据文件的传递1675.9关系数据库的连接与访问1695.9.1从数据库中输入数据1695.9.2向数据库中输出计算结果170第1章神奇的大象—hadoop第2章HDFS—不怕故障的海量存储第3章分久必合—MapReduce第4章一张无限大的表—HBase第5章更上一层楼—MapReduce进阶第6章Hive—飞进数据仓库的小蜜蜂第7章Pig—一头什么都能吃的猪第8章Facebook的女神—cassandra第9章Chukwa—收集数据的大乌龟第10章一统天下—Zookeeper第11章综合实战1—打造一个搜索引擎第12章综合实战2—生物信息学应用第13章综合实战3—移动通信信令监测与查询第14章高枕无忧—Hadoop容错大规模数据并行技术培训、教学和平台建设购建高性能MapReduce并行计算集群

2011年1月和10月共斥资100万建成南京大学第一台专用于科研的高性能MapReduce并行计算集群81台DELL高性能机架式服务器构成其中80台服务器每台包含：2路4核IntelXeon5620,2.4GHz24GB内存4TB硬盘整个集群总计：332个处理器核1000GB内存162TB硬盘存储量千兆以太网交换机,背板带宽184Gbps第三部分

大规模数据并行处理技术

研究与应用大规模数据处理的主要研究问题

数据存储+数据传输+数据处理

具体可包括以下主要技术问题：海量数据存储管理技术海量数据压缩与传输技术大规模数据并行算法海量数据索引和查询技术Hadoop系统改进与优化研究大规模数据并行处理应用

以下主要讨论后3项内容大规模数据处理的主要研究内容大规模数据并行算法基本算法各种全局数据相关性小、能适当划分数据的计算任务，如：分布式排序分布式GREP(文本匹配查找)关系代数操作

如：选择，投影，求交集、并集，连接，成组，聚合…矩阵向量相乘、矩阵相乘词频统计(wordcount)，词频重要性分析(TF-IDF)单词同现关系分析

典型的应用如从生物医学文献中自动挖掘基因交互作用关系文档倒排索引……大规模数据并行算法复杂算法或应用Web搜索引擎

网页爬取、倒排索引、网页排序、搜索算法Web访问日志分析

分析和挖掘用户在Web上的访问、购物行为特征、以定制个性化用户界面或投放用户感兴趣的产品广告数据/文本统计分析

如科技文献引用关系分析和统计、专利文献引用分析和统计图算法

并行化宽度优先搜索(最短路径问题，可克服Dijkstra串行算法的不足)，最小生成树，子树搜索、比对Web链接图分析算法PageRank，垃圾邮件连接分析91大规模数据并行算法复杂算法或应用聚类(clustering)

文档聚类、图聚类、其它数据集聚类相似性比较分析算法

字符序列、文档、图、数据集相似性比较分析基于统计的文本处理

最大期望(EM)统计模型，隐马可夫模型(HMM)，……机器学习

监督学习、无监督学习、分类算法（决策树、SVM…)数据挖掘统计机器翻译生物信息处理

DNA序列分析比对算法Blast：双序列比对、多序列比对生物网络功能模块(Motif)查找和比对广告推送与推荐系统……92

大规模数据并行算法Stanford大学研究小组研究了基于多核构架、自行设计的轻量级MapReduce框架的各种机器学习算法,发现计算性能可随处理器核数增长保持近似于线性的增长Cheng-TaoChuet.al,MapReduceforMachineLearningonMulticore,2006机器学习与数据挖掘算法93中国移动通信数据挖掘ChinaMobilelookstodatawarehousingandminingofthisdatatoextractinsightsforimprovingmarketingoperations,networkoptimization,andserviceoptimization.SometypicalapplicationsincludeAnalyzinguserbehaviorPredictingcustomerchurnAnalyzingserviceassociationAnalyzingnetworkqualityofservice(QOS)AnalyzingsignalingdataFiltering原来使用由著名供应商提供的专用的商业数据挖掘系统，但该系统的单服务器构架严重限制了大数据量挖掘处理。一个分支机构使用了8核、32GB内存、一个磁盘阵列的Unix服务器，但仅能处理1.4百万个用户的行为数据，或者仅仅本分支机构10%的用户数据,而且处理时间很长大规模数据并行算法中国移动通信数据挖掘

然后他们基于Hadoop重新做了一个数据挖掘系统Datanode/TaskTracker—单路4核Xeon2.5GHzCPU,8GBRAM,4x250GBSATAdisksNamenode/JobTracker—双路2核AMDOpteron2.6GHzCPU,16GBRAM,4x146GBSAS价格比较1/5的价格10倍数据时的速度比较一个数量级的性能提升大规模数据并行算法大规模数据并行算法海量数据挖掘算法研究发现：大数据隐含着更准确的事实

信息检索、自然语言理解和机器学习的三个要素：

数据，特征，与算法

2001,BankoandBrill发表了一篇自然语言领域的经典研究论文，探讨训练数据集大小对分类精度的影响，发现数据越大，精度越高；更有趣的发现是，他们发现当数据不断增长时，不同算法的分类精度趋向于相同，使得小数据集时不同算法在精度上的差别基本消失！

结论引起争论：算法不再要紧，数据更重要！不再需要研究复杂算法，找更多数据就行了！大规模数据并行算法海量数据隐含着更准确的事实2001年,一个基于事实的简短问答研究,如提问:WhoshotAbrahamLincoln？在很大的数据集时,只要使用简单的模式匹配方法,找到在“shotAbrahamLincoln”前面的部分即可快速得到准确答案：JohnWilkesBooth2007,Brantsetal.描述了一个基于2万亿个单词训练数据集的语言模型，比较了当时最先进的Kneser-Neysmoothing算法与他们称之为“stupidbackoff“(简单退避)的简单算法,最后发现,后者在小数据集时效果不佳，但在大数据集时，该算法最终居然产生了更好的语言模型！

结论：大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果！

大规模数据并行算法中科院计算所智能信息重点实验室何清教授进行了基于MapReduce的K-Means聚类、分类、和关联规则挖掘等海量数据挖掘并行算法、以及常用的数据统计分析算法的研究；并基于这些算法开发了一个并行分布式数据挖掘工具平台PDMiner，其中大规模数据存储在HDFS上，且通过MapReduce实现各种并行数据预处理和数据挖掘算法。ParallelK-meansclusteringbasedonMapReduce

Zhao,Weizhong(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,ChineseAcademyofSciences,China);Ma,Huifang;He,Qing

Source:

LectureNotesinComputerScience(includingsubseriesLectureNotesinArtificialIntelligenceandLectureNotesinBioinformatics),v5931LNCS,p674-679,2009,CloudComputing-FirstInternationalConference,CloudCom2009,ProceedingsParallelimplementationofclassificationalgorithmsbasedonmapreduce

He,Qing(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China);Zhuang,Fuzhen;Li,Jincheng;Shi,Zh