妩媚人生--云计算技术与大规模数据并行处理

云云 计计 算算 与与大规模数据并行处理技术大规模数据并行处理技术黄黄 宜宜 华华南南 京京 大大 学学计算机科学与技术系计算机科学与技术系软件新技术国家重点实验室软件新技术国家重点实验室妩媚人生 主 要 内 容第一局部：云计算技术简介简要介绍云计算及其主要特点，云计算开展背景与现状，云计算的关键技术第二局部：MapReduce大规模数据并行处理技术简要介绍Google和Hadoop MapReduce大规模数据并行处理技术第三局部：大规模数据并行处理技术研究与应用介绍大规模数据并行处理技术研究，主要讨论大规模数据并行算法研究、大规模数据索引查询技术、以及Hadoop改进和优化技术研究妩媚人生 第 一 部 分云计算技术云计算技术妩媚人生 云计算技术简介什么是云计算？什么是云计算？Cloud Computing,Utility Computing,Service Cloud Computing,Utility Computing,Service ComputingComputing通过集中式远程计算资源池，以按需分配方式，为终通过集中式远程计算资源池，以按需分配方式，为终端用户提供强大而廉价的计算效劳能力端用户提供强大而廉价的计算效劳能力工业化部署、商业化运作的大规模计算能力工业化部署、商业化运作的大规模计算能力一种新的、可商业化的计算和效劳模式一种新的、可商业化的计算和效劳模式计算能力像水电煤气一样，按需分配使用计算能力像水电煤气一样，按需分配使用资源池物理上对用户透明就像在云端一样资源池物理上对用户透明就像在云端一样妩媚人生 云计算的主要特点云计算的主要特点l透明的云端计算效劳l“无限多的计算资源，强大的计算能力l按需分配，弹性伸缩，取用方便，本钱低廉l资源共享，降低企业IT根底设施建设维护费用l应用部署快速而容易l软件/应用功能更新方便快捷l节省能源，绿色环保l集计算技术之大成，具有很强的技术性、工程型特点妩媚人生 云计算的分类按云计算效劳层面进行分类按云计算效劳层面进行分类SaaSSaaS：Software as a ServiceSoftware as a Service 提供各种应用软件效劳提供各种应用软件效劳PaaSPaaS：Platform as a ServicePlatform as a Service 提供软件支撑平台效劳提供软件支撑平台效劳IaaSIaaS：Infrastructure as a ServiceInfrastructure as a Service 提供接近于裸机提供接近于裸机(物理机或虚拟机物理机或虚拟机)的计算资的计算资源源 和根底设施效劳和根底设施效劳妩媚人生 云计算硬件平台云计算的分类云计算软件支撑平台云计算应用效劳软件SaaS如腾讯云词典PaaS如GoogleAppEngIaaS如AmazonEC2云计算应用按云计算效劳层面进行分类按云计算效劳层面进行分类妩媚人生 云计算的分类按云计算系统类型进行分类按云计算系统类型进行分类美国联邦云计算战略报告中，定义了美国联邦云计算战略报告中，定义了4 4中云：中云：公用云：提供面向社会群众、公共群体的云计算效公用云：提供面向社会群众、公共群体的云计算效劳劳 如如AmazonAmazon云平台，云平台，Google AppEngGoogle AppEng 公有云有很多优点，但最大的一个缺点是难以保公有云有很多优点，但最大的一个缺点是难以保证数据的私密性证数据的私密性私有云：提供面向应用行业私有云：提供面向应用行业/组织内的云计算效劳组织内的云计算效劳 如政府机关、移动通信、学校等内部使用的云平如政府机关、移动通信、学校等内部使用的云平台台 私有云可较好地解决数据私密性问题，对移动通私有云可较好地解决数据私密性问题，对移动通信、公安等数据私密性要求特别高的企业或机构，信、公安等数据私密性要求特别高的企业或机构，建设私有云将是一个必然的选择建设私有云将是一个必然的选择云计算的分类按云计算系统类型进行分类按云计算系统类型进行分类社区云：提供面向社团组织内用户使用的云计算平社区云：提供面向社团组织内用户使用的云计算平台台 如美国航天局如美国航天局(NASA)Nebula(NASA)Nebula云平台为云平台为NASANASA内内的研究人员提供快速的的研究人员提供快速的ITIT访问效劳访问效劳混合云：包含以上混合云：包含以上2 2种以上云计算类型的混合式云平种以上云计算类型的混合式云平台台妩媚人生 云计算开展背景云计算技术的争议云计算技术的争议反方：云计算是业界的商业性行为反方：云计算是业界的商业性行为正方：云计算是计算技术的重大开展趋势正方：云计算是计算技术的重大开展趋势个人认为：云计算技术有其开展的必然性和必要个人认为：云计算技术有其开展的必然性和必要性性妩媚人生 云计算开展背景集中分散集中60-70s:大型机(mainframe),集中式、终端用户共享80-90s:个人计算机,人手一台95-06:互联网/网格/集群 07-现在:云计算“天下大势，合久必分，分久必合天下大势，合久必分，分久必合“否认之否认，螺旋式上升否认之否认，螺旋式上升云计算开展背景应用需求背景应用需求背景 大粒度应用系统的规模越来越大大粒度应用系统的规模越来越大应用系统数据量越来越大应用系统数据量越来越大中国移动全国每天的中国移动全国每天的 短信通联记录数短信通联记录数据到达据到达500TB500TB；而中国移动一个流量最；而中国移动一个流量最大的省每天的通联记录数据可到达大的省每天的通联记录数据可到达65TB65TB阿里巴巴电子商务平台日处理数据量将阿里巴巴电子商务平台日处理数据量将到达到达500TB500TB百度存储百度存储100-1000PB100-1000PB数据，每日处理数据，每日处理10-10-100PB100PB；存储；存储1 1千千-1-1万亿网页，索引万亿网页，索引100-100-10001000亿网页亿网页20212021年年eBayseBays数据仓库，一个有数据仓库，一个有2PB2PB用户用户数据，另一个数据，另一个6.5PB6.5PB用户数据包含用户数据包含170TB170TB记录且每天增长记录且每天增长150GB150GB个记录个记录FacebookFacebook：2.5PB2.5PB用户数据，每天增加用户数据，每天增加15TB15TB仅仅20212021年，全世界产生年，全世界产生1.8ZB1.8ZB1.81.8万亿万亿GBGB数据，相当于每位美国人每分钟写数据，相当于每位美国人每分钟写3 3条条TwitterTwitter，不停地写，不停地写2.72.7万年万年YouTubeYouTube每分钟有每分钟有13h13h视频上传，每天数视频上传，每天数据据10TB10TB相当于好莱坞每周发行相当于好莱坞每周发行5700057000部部电影电影云计算开展背景应用需求背景应用需求背景 大粒度应用系统的规模越来越大大粒度应用系统的规模越来越大超大的计算量和计算复杂度超大的计算量和计算复杂度用用SGISGI工作站进行电影渲染时，每帧一般需要工作站进行电影渲染时，每帧一般需要1 12 2小小时时一部一部2 2小时的电影渲染需要：小时的电影渲染需要：2 2小时小时x3600 x3600秒秒x24x24帧帧x(12x(12小时小时)/24)/24小时小时=2040=2040年年!特殊场景每帧可能需要特殊场景每帧可能需要6060个小时个小时(影片影片“星舰骑兵星舰骑兵中数千只蜘蛛爬行的场面中数千只蜘蛛爬行的场面),),用横向用横向40964096象素分辨率象素分辨率进行渲染时，如果以每帧进行渲染时，如果以每帧6060个小时的速度，那么个小时的速度，那么1 1秒的放映量秒的放映量2424帧需要帧需要6060天的渲染时间天的渲染时间,1,1分钟那分钟那么需要么需要100100年！年！云计算开展背景应用需求背景应用需求背景小粒度应用系统资源重复、无法共享小粒度应用系统资源重复、无法共享 企业内大量的小粒度应用系统需要添置独立的硬件企业内大量的小粒度应用系统需要添置独立的硬件资源，但忙闲不均，忙时资源不够，闲时资源空置，资源，但忙闲不均，忙时资源不够，闲时资源空置，资源无法相互调配和共享，造成资源和资金浪费资源无法相互调配和共享，造成资源和资金浪费 淘宝网案例：后台设置约淘宝网案例：后台设置约1515万台效劳器，效劳于万台效劳器，效劳于不同的应用系统；而不同应用系统的负载不同，忙不同的应用系统；而不同应用系统的负载不同，忙闲不均；据淘宝测算，如能在不同应用间合理调配闲不均；据淘宝测算，如能在不同应用间合理调配计算资源，大约可省去计算资源，大约可省去2/32/3约约1010万台效劳器，以每万台效劳器，以每台台3 3万元计算，约可节省万元计算，约可节省3030亿元！亿元！云计算开展背景技术开展背景技术开展背景 贯穿整个计算机技术开展历史的两条主线：贯穿整个计算机技术开展历史的两条主线：计算能力角度：不断追求计算性能提升计算能力角度：不断追求计算性能提升 无论是微处理器还是巨型机，近无论是微处理器还是巨型机，近20年性能提高年性能提高3千多千多倍倍 使用角度：不断追求易用性和灵活性使用角度：不断追求易用性和灵活性 可获得性、易用性、可扩展性和灵活性不断提升可获得性、易用性、可扩展性和灵活性不断提升妩媚人生 Intel微处理器每秒1千8百亿次浮点运算！近20年性能提高3千多倍不断追求计算性能提升巨型机：中国天河一号，2021年底世界TOP500强第1名每秒2千5百多万亿次浮点运算，近20年性能提高3千多倍亿亿千万亿百万亿十万亿万亿千亿百亿十亿亿TOP500系统体系结构演化向量机=SMP=MPP=ClusterCluster以高获得性、高可扩展性优势成为开展主流 不断追求方便性和灵活性云计算开展背景云计算开展背景云计算开展背景技术开展背景技术开展背景 虽然新的计算技术在易用性和灵活性上有不断提虽然新的计算技术在易用性和灵活性上有不断提高，但仍然存在很大缺乏：高，但仍然存在很大缺乏：计算能力仍取决于硬件计算资源，计算能力不计算能力仍取决于硬件计算资源，计算能力不够时，需要不断增加硬件资源；空闲时，硬件资够时，需要不断增加硬件资源；空闲时，硬件资源闲置浪费，不能共享；计算能力的获取和使用源闲置浪费，不能共享；计算能力的获取和使用上仍然存在较大的制约。上仍然存在较大的制约。云计算正是一种解决这一问题的新的计算效劳模云计算正是一种解决这一问题的新的计算效劳模式，其根本思路是集中计算资源提供巨大的计算式，其根本思路是集中计算资源提供巨大的计算能力的同时，提供使用上的方便性和灵活性能力的同时，提供使用上的方便性和灵活性妩媚人生 云计算开展背景技术开展背景技术开展背景 云计算是诸多计算技术开展成熟与自然进化的产云计算是诸多计算技术开展成熟与自然进化的产物物计算机虚拟化技术、大规模并行计算、分布式存储、计算机虚拟化技术、大规模并行计算、分布式存储、面向效劳构架、公用效劳计算等诸多技术广泛应面向效劳构架、公用效劳计算等诸多技术广泛应用用计算机系统规模和处理能力迅速扩大计算机系统规模和处理能力迅速扩大技术开展成熟与自然进化的结果技术开展成熟与自然进化的结果妩媚人生 云计算开展背景“Thecomputationandthedataandsoforthareintheservers.Wecallitcloudcomputing.”(ErickSchmidt,2006)“computationmaysomedaybeorganizedasapublicutility”(JohnMcCarthy,1960)“云计算的概念在云计算的概念在2006年年由由Google公司正式提出公司正式提出但最初的思想雏形但最初的思想雏形可追溯到更早的时间可追溯到更早的时间妩媚人生 云计算开展背景云计算开展意义云计算开展意义云计算出现的意义，可与云计算出现的意义，可与2020世纪电力工业的变革相世纪电力工业的变革相比比20世纪初电力工业变革的几项关键技术 发电容量大幅提升 交流电的出现(1888)电表的创造和使用(1894)20世纪初私有电厂向公共电力效劳转化过程 1900:美国有5万多个私有小型电厂，3千6百个中心电站 1907:40%并入了公共电力效劳系统 1920:70%并入了公共电力效劳系统 1930:80%90%并入了公共电力效劳系统 妩媚人生 云计算开展背景云计算开展意义云计算开展意义 云计算的一个重要目标是，把计算能力变成像水云计算的一个重要目标是，把计算能力变成像水电等公用效劳一样，随用随取，按需使用。故此电等公用效劳一样，随用随取，按需使用。故此也有人把云计算称为也有人把云计算称为“Utility Computing“Utility Computing 这里这里UtilityUtility不是效用、实用的意思，在英文里不是效用、实用的意思，在英文里UtilityUtility有一个专门的含义，专指类似于水电煤气有一个专门的含义，专指类似于水电煤气的公用效劳，故的公用效劳，故Utility ComputingUtility Computing应译为应译为“公用公用效劳计算效劳计算妩媚人生 云计算开展背景云计算开展意义云计算开展意义 2021 2021年年2 2月月8 8日美国奥巴马总统签署了联日美国奥巴马总统签署了联邦云计算战略报告，制定该报告的目的：邦云计算战略报告，制定该报告的目的：The Federal Governments current The Federal Governments current Information Technology(IT)Information Technology(IT)environment is characterized by low environment is characterized by low asset utilization,a fragmented asset utilization,a fragmented demand for resources,duplicative demand for resources,duplicative systems,environments which are systems,environments which are difficult to manage,and long difficult to manage,and long procurement lead times.These procurement lead times.These inefficiencies negatively impact the inefficiencies negatively impact the Federal Governments ability to Federal Governments ability to serve the American public.serve the American public.Cloud computing has the potential to Cloud computing has the potential to play a major part in addressing these play a major part in addressing these inefficiencies and improving inefficiencies and improving government service delivery.The government service delivery.The cloud computing model can cloud computing model can significantly help agencies grappling significantly help agencies grappling with the need to provide highly with the need to provide highly reliable,innovative services quickly reliable,innovative services quickly despite resource constraints.despite resource constraints.美国联邦政府部门方案用全部的美国联邦政府部门方案用全部的800800亿美亿美元元ITIT预算中的预算中的200200亿作为云计算平台开发建亿作为云计算平台开发建设的费用。设的费用。美国联邦云计算战略报告，美国联邦云计算战略报告，2021/2/82021/2/8云计算开展背景云计算开展意义云计算开展意义 美国联邦云计算战略报告认为：美国联邦云计算战略报告认为：Cloud is a fundamental shift in ITCloud is a fundamental shift in IT Cloud computing enables IT systems to be Cloud computing enables IT systems to be scalable and elastic.End users do not need scalable and elastic.End users do not need to determine their exact computing resource to determine their exact computing resource requirements upfront.I nstead,they provision requirements upfront.I nstead,they provision computing resources as required,on-computing resources as required,on-demand.Using cloud computing services,a demand.Using cloud computing services,a Federal agency does not need to own data Federal agency does not need to own data center infrastructure to launch a capability center infrastructure to launch a capability that serves millions of usersthat serves millions of usersCloud computing can significantly improve Cloud computing can significantly improve public sector ITpublic sector IT A number of government agencies are A number of government agencies are adopting cloud technologies and are realizing adopting cloud technologies and are realizing considerable benefits.For instance,NASA considerable benefits.For instance,NASA Nebula,through a community cloud,gives Nebula,through a community cloud,gives researchers access to IT services relatively researchers access to IT services relatively inexpensively in minutes.Prior to adopting inexpensively in minutes.Prior to adopting this approach,it would take researchers this approach,it would take researchers months to procure and configure comparable IT months to procure and configure comparable IT resources and significant management resources and significant management oversight to monitor and upgrade systems.oversight to monitor and upgrade systems.Applying cloud technologies across the entire Applying cloud technologies across the entire Federal Government can yield tremendous Federal Government can yield tremendous benefits in efficiency,agility,and benefits in efficiency,agility,and innovation.innovation.妩媚人生 云计算开展现状与趋势业界云计算技术的开展业界云计算技术的开展 自自2006年年Google公司提出云计算技术的概念后，公司提出云计算技术的概念后，全球全球IT著名企业纷纷予以极大关注，并投入了巨著名企业纷纷予以极大关注，并投入了巨大力量进行云计算技术的研究开发。大力量进行云计算技术的研究开发。妩媚人生 GoogleCloudInfrastructureSchedulerChubbyGFSmasterNodeNodeNodeUserGoogleAppEngineSchedulerslaveGFSLinuxNodeMapReduceFrameworkBigTableServerGoogleCloudInfrastructure(GoogleAppEngine，PaaS型公用云平台)Google AppEngine提供了一种PaaS类型的云计算效劳平台，用户可租用该平台的计算资源，并使用AppEngine提供的各种应用开发和支撑软件平台开发和部署自己的应用软件S3EBSEC2EBSEC2EBSEC2EBSEC2SimpleDBSQSUserDeveloperAmazonElasticComputingCloud(AmazonEC2，IaaS型公用云平台)SQS:Simple Queue ServiceEC2:Running Instance of Virtual MachinesEBS:Elastic Block Service,Providing the Block Interface,Storing Virtual Machine ImagesS3:Simple Storage Service,SOAP,Object InterfaceSimpleDB:Simplified DatabaseAmazon EC2提供了一种IaaS类型的云计算效劳平台，在该平台上用户可部署自己的系统软件，完成应用软件的开发和发布。租用案例2007年，美国纽约时报租用Amazon云计算平台，用于将1851-1922年纽约时报的1100万篇报刊文章转换为PDF文件,供读者上网免费访问。共租用了100个EC2节点，运行了24小时，处理了4TB的报刊原始扫描图像，生成了1.5TB的PDF文件。每节点每小时费用为10美分，整个计算任务仅花费了240美元(100节点 x 24小时 x$0.10)！如果用自己的效劳器，将需要数月和多得多的费用！Amazon Elastic Computing Cloud妩媚人生 MicrosoftCloudServices(WindowAzure，私有云平台管理和效劳软件)Azure Services PlatformMicrosoft SharePoint ServicesMicrosoft Dynamics CRM ServicesIBM 云计算方案(私有云计算平台管理和效劳软件)提供私有云计算资源管理软件平台，主要负责管理和调度虚拟计算资源，完成资源申请、调度和管理等整个生命周期管理其它国内外IT企业云计算研发 除以上几家全球著名的IT企业外，其它著名IT企业如Cisco、HP、EMC、VMWare等，都在大力推进云计算技术和系统研发。国内诸多著名IT企业，如中国移动、中国电信、中国联通、阿里巴巴、腾讯、百度、万网、中兴通信、华为等，也大力推动云计算研发。云计算开展现状与趋势妩媚人生 中国移动中国移动Big CloudBig Cloud云计算开展现状云计算开展现状目标是建立可为中国移动企业内部进行海量通信数据存储和处理的使用的私有云平台，以及为社会群众和群体使用的公有云平台。大规模低本钱数据中心的订制化硬件设计分布式文件系统结构化数据存储非结构化数据存储分布式计算资源管理大规模离线数据处理在线效劳综合监控计费系统平安高可靠保障机制云计算编程模型与访问接口商品交易平台软件效劳平台数据效劳平台企业IT效劳统一的资源调度效劳阿里巴巴电子交易云计算平台阿里巴巴电子交易云计算平台云计算开展现状与趋势云计算开展趋势云计算开展趋势云计算将提供一种新的计算模式和效劳模式。云计算云计算将提供一种新的计算模式和效劳模式。云计算将是计算技术的一次重大变革，作为今后计算开展将是计算技术的一次重大变革，作为今后计算开展的潮流将大大改变现有的计算模式，对计算技术领的潮流将大大改变现有的计算模式，对计算技术领域本身以及各个应用行业都将带来重大的影响，提域本身以及各个应用行业都将带来重大的影响，提供更多的开展机遇供更多的开展机遇 通过云计算人们能获得前所未有的强大计算能力，通过云计算人们能获得前所未有的强大计算能力，并能按需分配，按需付费，提升了本地计算能力但并能按需分配，按需付费，提升了本地计算能力但使用本钱低廉，而且还能大幅削减不断升级软硬件使用本钱低廉，而且还能大幅削减不断升级软硬件系统的费用系统的费用通过云计算平台强大的计算和存储能力，人们将能完通过云计算平台强大的计算和存储能力，人们将能完成传统系统所无法完成的计算和处理，开发出更强成传统系统所无法完成的计算和处理，开发出更强大的应用功能，提供更多智能化应用大的应用功能，提供更多智能化应用 云计算开展现状与趋势云计算开展趋势云计算开展趋势通过各种个人终端使用云端的计算能力，将大大扩展通过各种个人终端使用云端的计算能力，将大大扩展现有的移动设备的计算能力，提供各种新的增值应现有的移动设备的计算能力，提供各种新的增值应用模式用模式云计算与物联网有重要的关联性，作为未来的人机物云计算与物联网有重要的关联性，作为未来的人机物计算的重要组成局部，云计算关注的是效劳器端技计算的重要组成局部，云计算关注的是效劳器端技术，物联网关注的客户和终端技术术，物联网关注的客户和终端技术妩媚人生 云计算开展现状与趋势云计算开展趋势云计算开展趋势l面向民生工程的政企应用将是云计算的潜在市场，并能带动产业整体开展l未来3年，云计算应用将以政府、电信、教育、医疗、金融、石油石化和电力等行业为重点，在中国市场逐步被越来越多的企业和机构采用，市场规模将从2021年的92.23亿元增长到2021年的606.78亿元，年复合增长率达87.4%l 来源:赛迪参谋 中国云计算产业开展白皮书妩媚人生 云计算的关键技术主要包括以下关键技术主要包括以下关键技术l虚拟化技术：虚拟机的安装、设置、调度分配、使用、故障检测与失效恢复等l云计算构架技术：研究解决适合于云计算的系统软硬件构架l资源调度技术：解决物理或虚拟计算资源的自动化分配、调度、配置、使用、负载均衡、回收等资源管理妩媚人生 云计算的关键技术主要包括以下关键技术主要包括以下关键技术并行计算技术：针对大规模数据或复杂计算应用，并行计算技术：针对大规模数据或复杂计算应用，解决数据或计算任务切分和并行计算算法设计问解决数据或计算任务切分和并行计算算法设计问题题海量存储技术：解决大规模数据的分布存储、共享海量存储技术：解决大规模数据的分布存储、共享访问、数据备份等问题访问、数据备份等问题云平安技术：解决云计算系统的访问平安性、数据云平安技术：解决云计算系统的访问平安性、数据平安性包括数据私密性等问题平安性包括数据私密性等问题此外，还有云计算中心的节能和散热等工程技术问此外，还有云计算中心的节能和散热等工程技术问题题云计算的关键技术怎样才算是云计算？云计算概念很热，各级政府部门、很多行业和应用都想搞云计算。大家很热议的问题是：l云计算与传统计算系统有什么区别？l系统做成什么样才能称得上是云计算系统？妩媚人生 云计算的关键技术怎样才算是云计算？答复这两个问题必须从开展云计算技术的两个根本目的、以及云计算区别于传统计算的特点上来看提高计算能力：集中计算资源，为应用提供强大而廉价的计算能力=大规模并行计算能力提高易用性和灵活性：合理调配资源，为应用提供弹性资源分配、资源共享 =资源虚拟化和弹性调度 云计算的关键技术怎样才算是云计算？因此，个人认为：一个计算系统必须具备以下两个特征才能算是云计算系统至少具备第一个特征:资源虚拟化和弹性调度 基于虚拟化和弹性调度，以按需分配方式，为小粒度应用提供计算资源，实现资源共享大规模并行计算效劳 基于云端的强大而廉价的计算能力，为大粒度应用提供传统计算系统或用户终端所无法完成的计算效劳。这些计算能力包括海量数据存储能力、以及大规模并行计算能力。第 二 部 分MapReduceMapReduce大规模数据并行处理技术大规模数据并行处理技术妩媚人生 大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？大规模数据处理和行业应用需求日益增加和迫切出现越来越多的超大规模数据处理应用需求，传统系统难以提供足够的存储和计算资源进行处理，云计算平台是最理想的解决方案。调查显示：目前，IT专业人员对云计算中诸多关键技术最为关心的是大规模数据并行处理技术大数据并行处理没有通用和现成的解决方案对于应用行业来说，云计算平台软件、虚拟化软件都不需要自己开发，但行业的大规模数据处理应用软件没有通用的软件，需要针对特定的应用需求专门开发，涉及到诸多并行化算法、索引查询优化技术研究、以及系统的设计实现大规模数据并行处理技术的重要性为什么大规模数据并行处理是云计算核心技术之一？处理数据的能力大幅落后于数据增长速度磁盘容量增长远远快过存储访问带宽和延迟：80年代中期数十MB到今天1-2TB，增长10万倍，而延迟仅提高2倍，带宽仅提高50倍！海量数据隐含着更准确的事实研究发现：训练数据集越大,数据分类精度越高；大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果妩媚人生 大规模数据并行处理技术的重要性大数据大数据(Big Data)(Big Data)应用需求应用需求 出现越来越多的大数据应用和行业需求。出现越来越多的大数据应用和行业需求。20212021年，在年，在GoogleGoogle成立成立1010周年之际，周年之际，?Nature?Nature?杂志出版一期专刊专门讨论未来杂志出版一期专刊专门讨论未来的大数据的大数据Big DataBig Data处理相关的一系列处理相关的一系列技术问题和挑战。技术问题和挑战。据预计：未来10年，数据量将从数百EB增长到数百ZB量级！Google大规模数据并行处理技术简介Google MapReduceGoogle在在2004年提出的一种通用的大规模数据并行计算年提出的一种通用的大规模数据并行计算平台和编程模型和框架平台和编程模型和框架MapReduce创造后，创造后，Google大量用于各种海量数据处大量用于各种海量数据处理，目前理，目前Google内部有内部有7千以上的程序基于千以上的程序基于MapReduce实现，包括其搜索引擎实现，包括其搜索引擎 的全部索引处理的全部索引处理什么是MapReduce？MapReduceMapReduce三个层面的含义三个层面的含义基于集群的高性能并行计算平台基于集群的高性能并行计算平台(Cluster(Cluster Infrastructure)Infrastructure)允许用市场上的普通效劳器，构成一个包含数百到数千允许用市场上的普通效劳器，构成一个包含数百到数千个节点的分布式并行计算集群个节点的分布式并行计算集群并行程序开发与运行框架并行程序开发与运行框架(Software Framework)(Software Framework)提供了一个庞大但设计精良的并行计算软件构架，能自提供了一个庞大但设计精良的并行计算软件构架，能自动完成计算任务的并行化处理，自动划分计算数据和计动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行子任务以及收集算任务，在集群节点上自动分配和执行子任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并计算结果，将数据分布存储、数据通信、容错处理等并行计算中的很多复杂细节交由系统负责处理，大大减少行计算中的很多复杂细节交由系统负责处理，大大减少了软件开发人员的负担了软件开发人员的负担并行程序设计模型与方法并行程序设计模型与方法(Programming Model&(Programming Model&Methodology)Methodology)借助于函数式语言中的设计思想，提供了一种简便的并借助于函数式语言中的设计思想，提供了一种简便的并行程序设计方法，用行程序设计方法，用MapMap和和ReduceReduce两个函数编程实现根两个函数编程实现根本的并行计算任务，提供了完整的并行编程接口，完成本的并行计算任务，提供了完整的并行编程接口，完成大规模数据处理大规模数据处理典型的流式大数据处理问题的特征典型的流式大数据处理问题的特征大量数据记录/元素进行重复处理对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息排序和整理中间结果以利后续处理收集整理中间结果产生最终结果输出MapReduce关键思想：借助于Lisp函数式程序设计思想，为大数据处理过程中的两个主要处理操作提供一种抽象机制MapReduce的根本设计思想MapReduce的根本设计思想MapReduce三个层面上的根本设计思想如何对付大数据处理：分而治之对相互间不具有计算依赖关系的大数据，实现并行最自然的方法就是采取分而治之的策略上升到抽象模型：Mapper与ReducerMapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型，程序员只需描述需要“做什么(what to do),不需要关心具体“怎么做How to do)上升到统一构架：为程序员隐藏系统层细节对于具体的“怎么做的问题，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：Aggregation and ShuffleReduceReduceReduce(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组原始文本数据：Text 1:the weather is good Text 2:today is good Text 3:good weather is good Text 4:today has good weather传统的串行处理方式(Java)：String text=new String “hello world,“hello every one,“say hello to everyone in the world;HashTable ht=new HashTable();for(i=0;i3;+i)StringTokenizer st=new StringTokenizer(texti);while(st.hasMoreTokens()String word=st.nextToken();if(!ht.containsKey(word)ht.put(word,new Integer(1);else int wc=(Integer)ht.get(word).intValue()+1;/计数加1 ht.put(word,new Integer(wc);for(Iterator itr=ht.KeySet().iterator();itr.hasNext();)String word=(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,“the weather is good)输出：(the,1),(weather,1),(is,1),(good,1)map节点2:输入：(text2,“today is good)输出：(today,1),(is,1),(good,1)map节点3:输入：(text3,“good weather is good)输出：(good,1),(weather,1),(is,1),(good,1)map节点4:输入：(text3,“today has good weather)输出：(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并行处理例如文档词频统文档词频统WordCountWordCountReduceReduce处理例如处理例如设使用设使用3 3个个ReduceReduce节点节点:reducereduce节点节点1:1:输入：输入：(good,1),(good,1),(good,2),(good,(good,1),(good,1),(good,2),(good,1)1)输出：输出：(good,5)(good,5)reducereduce节点节点2:2:输入：输入：(has,1),(is,1),(is,1),(is,1),(has,1),(is,1),(is,1),(is,1),输出：输出：(has,1),(is,3)(has,1),(is,3)reducereduce节点节点3:3:输入：输入：(the,1),(today,1),(today,1)(the,1),(today,1),(today,1)(weather,1),(weather,1),(weather,1),(weather,1),(weather,1)(weather,1)输出：输出：(the,1),(today,2),(weather,3)(the,1),(today,2),(weather,3)输出：good:5is:3has:1the:1today:2weather:3MapReduce并行处理例如文档词频统WordCountMapReduce程序实现MapReduce伪代码(实现Map和Reduce两个函数)：Class Mapper method map(String input_key,String input_value):/input_key:text document name /input_value:document contents for each word w in input_value:EmitIntermediate(w,1);Class Reducer method reduce(String output_key,Iterator intermediate_values):/output_key:a word /output_values:a list of counts int result=0;for each v in intermediate_values:result+=ParseInt(v);Emit(output_key，result);提供统一的计算框架主要需求和目标：实现自动并行化计算为程序员隐藏系统层细节需要考虑的细节技术问题：如何管理和存储数据？如何划分数据？如何调度计算任务并分配map和reduce节点？如果节点间需要共享或交换数据怎么办？如何考虑数据通信和同步？如何掌控节点的执行完成情况？如何收集中间和最终的结果数据？节点失效如何处理？如何恢复数据？如何恢复计算任务？节点扩充后如何保证原有程序仍能正常运行并保证系统性能提升？问题：我们能把这些细节和复杂性都交给系统去负责处理吗？提供统一的计算框架答案：MapReduce之前的并行计算方法都未能做到但MapReduce做到了！MapReduce提供一个统一的计算框架，可完成：计算任务的划分和调度数据的分布存储和划分处理数据与计算任务的同步结果数据的收集整理(sorting,combining,partitioning,)系统通信、负载平衡、计算性能优化处理计算和存储节点出错检测和失效恢复妩媚人生 MapReduce的主要设计思想与特点 向向“外横向扩展，而非向外横向扩展，而非向“上纵向扩展上纵向扩展 Scale“out,not“up 即即MapReduce集群的构筑选用价格廉价、易集群的构筑选用价格廉价、易于扩展的大量低端商用效劳器，而非价格于扩展的大量低端商用效劳器，而非价格昂贵、不易扩展的高端效劳器昂贵、不易扩展的高端效劳器SMP低端效劳器市场与高容量低端效劳器市场与高容量Desktop PC有重叠有重叠的市场，因此，由于相互间价格的竞争、的市场，因此，由于相互间价格的竞争、可互换的部件、和规模经济效应，使得低可互换的部件、和规模经济效应，使得低端效劳器保持较低的价格端效劳器保持较低的价格基于基于TPC-C在在2007年底的性能评估结果年底的性能评估结果,一个一个低端效劳器平台与高端的共享存储器结构低端效劳器平台与高端的共享存储器结构的效劳器平台相比的效劳器平台相比,其性价比大约要高其性价比大约要高4倍倍;如果把外存价格除外如果把外存价格除外,低端效劳器性价比大低端效劳器性价比大约提高约提高12倍倍对于大规模数据处理，由于有大量数据存储对于大规模数据处理，由于有大量数据存储需要，显而易见，基于低端效劳器的集群需要，显而易见，基于低端效劳器的集群远比基于高端效劳器的集群优越，这就是远比基于高端效劳器的集群优越，这就是为什么为什么MapReduce并行计算集群会基于低并行计算集群会基于低端效劳器实现端效劳器实现*Cite from Jimmy Lin,University of Maryland,Data-Intensive Text processing with MapReduceMapReduce的主要设计思想与特点 失效被认为是常态失效被认为是常态Assume failures are common MapReduce集群中使用大量的低端效劳器集群中使用大量的低端效劳器(Google目目前在全球共使用百万台以上的效劳器节点前在全球共使用百万台以上的效劳器节点),因此，因此，节点硬件失效和软件出错是常态，因而：节点硬件失效和软件出错是常态，因而：一个良好设计、具有容错性的并行计算系统不能因为一个良好设计、具有容错性