大数据及MapReduce编程模型94

唐卓博士[e-mail]湖南大学信息科学与工程学院2014年8月大数据及其并行编程模型概述2云计算湖南大学信息科学与工程学院主要内容一、大数据概述二、应对大数据的系统思维三、MapReduce并行编程详解2注：本课件前30页PPT来源于国防科大李东升教授：“大数据时代的挑战和探索”3云计算湖南大学信息科学与工程学院互联网应用数据急剧增长互联网用户数量巨大，日益活跃•微博、论坛、电子商务网站等•互联网上的用户生成数据（UserGeneratedContent，UGC）淘宝网每天新增数据40TB以上百度每天处理10PB量级的数据，总数据量达1000PB应用背景注：本课件前30页PPT来源于国防科大李东升教授：“大数据时代的挑战和探索”4云计算湖南大学信息科学与工程学院一、大数据概述•随着信息化的推进，国民经济、国家安全等领域的数据不断增长物联网、移动通信电话、手机短信、语音数据遥感、公共安全、医疗、交通、情报等很多领域•高分辨率卫星（影像）、城市监控摄像头（视频）、…•据报道，武汉监控摄像头已超过25万个，如采用1080P高清摄像头（一天产生数据量40GB以上），整个城市每天新增监控数据10PB以上应用背景5云计算湖南大学信息科学与工程学院•科学实验数据规模巨大，增长迅猛生物工程气候监测高能物理天文观测生态环境….气候研究华大基因测序目前每天产生数据约15TB，一年超过5PB一欧洲CERN对撞机每年产生的数据量超过15PB基因测序应用背景6云计算湖南大学信息科学与工程学院全球数据量•IDC报告预测：未来十年，全球数据量继续迅速增长Amountofdigitalinformationcreatedandreplicatedinayear––––年均增长率超过40%2009年0.8ZB2020年35ZB1ZB~106PB月球容量4GB的DVD光用容量4GB的DVD光盘存储，DVD可从地球排至月球G-T-P-E-Z-Y7云计算湖南大学信息科学与工程学院•维基（Wiki）百科的定义Bigdataisacollectionofdatasetssolargeandcomplexthatitbecomesdifficulttoprocessusingon-handdatabasemanagementtools•IDC的定义Bigdatatechnologiesdescribeanewgenerationoftechnologiesandarchitectures,designedtoeconomicallyextractvaluefromverylargevolumesofawidevarietyofdata,byenablinghigh-velocitycapture,discovery,and/oranalysis.什么是大数据大数据是超大、复杂的数据集，现有的数据库管理技术难以应对大数据技术描述了新一代的技术和架构，通过高速的数据获取、发现和分析技术，以经济的方式从各种超大规模的数据中提取价值8云计算湖南大学信息科学与工程学院一、大数据概述•Volume：规模大从PB级到ZB级1ZB~106*PB•Variety：多样化结构化、非结构化文本、图像、视频等•Velocity：变化快批处理/离线数据、流/实时/在线数据等•Value/Veracity：价值稀疏/数据质量噪音和无用信息很多一、大数据概述大数据的特点9云计算湖南大学信息科学与工程学院•大数据技术对经济社会和科研都在产生重要影响–互联网产业、电子商务推荐、日常生活大数据的影响季节性流感是一个重要的公共卫生问题：WHO估计，全球每年25万至50万人因此死亡及时监测到疾病的传播情况，尽快采取应对措施2008年，Google通过处理网络搜索日志中的几千亿查询数据，训练建立流感疾病监测的数学模型，比美国病控制和预防中心提前1-2周给出流感的传播情况论文发表在Nature(2009.2):DetectingInfluenzaEpidemicsusingSearchEngineQueryData10云计算湖南大学信息科学与工程学院•大数据技术对经济社会和科研都在产生重要影响–科学研究三种科研模式：理论、实验、计算第四模式：数据密集型的科学发现图灵奖获得者JimGray2007年提出专辑：Nature(2008.9):”BigData”,Science(2011.2):”Dealingwithdata”大数据的影响11云计算湖南大学信息科学与工程学院•2012年3月29日，美国政府宣布投资2亿美元启动“大数据研发计划”（BigDataR&DInitiative）美NSF、国防部、能源部、卫生总署等七部委•我国科技部和基金委等部门高度重视2013年973新立项项目：2项“十二五”国家科技计划信息技术领域2013年度备选项目征集指南•国内外学术界的热点课题SIGMOD、VLDB、OSDI、NSDI等著名会议Nature、Science杂志11大数据成为热点课题12云计算湖南大学信息科学与工程学院•传统技术难以应对大数据的规模–数据存储及访问的挑战当前较快硬盘的传输速度6Gbps，线性扫描10PB数据，需约19天而百度、Google等互联网公司每天处理的数据量超过10PB案例源于：北航/爱丁堡樊文飞教授•可扩展是大规模分布式系统面临的基础性问题–JimGray（图灵奖获得者）将可扩展问题列为信息技术领域需解决的16个长远问题之首JimGray.WhatNext?AFewRemainingProblemsinInformationTechnology.ACMTuringAwardLecture(1999).Availableat（1）13云计算湖南大学信息科学与工程学院•很多大数据应用对响应时间要求高–规模大、响应快：对存储和处理提出了很大挑战–2007年前,Facebook使用数据库，总数据量15TB•目前，Facebook每天新增加的数据约70TB–传统并行数据库扩展性受限，节点规模很少超过100，且价格昂贵•2011年，Facebook系统具有2700多个节点，Google单个数据中心在上万个节点集群上存储了约10PB数据•如何设计可扩展、低成本、快速响应的大数据存储和处理系统？大数据存储与处理的可扩展难题14云计算湖南大学信息科学与工程学院数据种类多，需求多样，关联复杂–文本、图像、图形、视频等–在线/流数据、离线/批处理等如何建模、存储、查询、分析和理解多样化的复杂数据，挖掘数据价值？–大数据中垃圾和珍宝并存–大海捞针、去粗取精、去伪存真–需要计算机专家和领域专家的配合….大数据面临的挑战（2）15云计算湖南大学信息科学与工程学院传统算法在大数据时代可能不再有效多项式时间算法O(Nk)，N太大需要计算复杂性和算法设计理论上的变革需要大数据计算思维上的变化例如，从确定性计算到非精确性计算商品在线推荐：只需要计算出前10名相关的结果，有一点不准确也没有关系传统算法结论在大数据时代需要重新评估–简单方法+大数据集可能取得很好的结果大数据面临的挑战（3）16云计算湖南大学信息科学与工程学院•2007年,Google公司的Brants等人研究了机器翻译领域中基于单词训练数据集的语言模型比较了当时最先进的KN算法与其提出的一个简单算法SB研究表明，简单算法在小数据集时效果不佳，但在大数据集时，简单算法却产生了更好的效果T.Brants,A.C.Popat,etal.LargeLanguageModelsinMachineTranslation.ProceedingsoftheJointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning,2007.16传统算法结论需要重新评估17云计算湖南大学信息科学与工程学院•大数据时代的算法新理论–新的计算复杂性和算法设计理论•复杂大数据的建模、表示和可视化–多源异构大数据：由大到小•面向大数据的新型存储和计算系统架构–大规模并行/分布处理•大数据（并行）挖掘算法及应用大数据的研究课题18云计算湖南大学信息科学与工程学院主要内容一、大数据概述二、应对大数据的系统思维三、MapReduce并行编程详解219云计算湖南大学信息科学与工程学院181.数据为中心的计算架构计算和存储唇齿相依2.化繁为简，分而治之可扩展的数据并行处理3.求同存异，聚焦领域放松传统数据处理技术的约束，如一致性等、行式存储-列式存储高可扩展高吞吐率高可靠性……主要内容18二、应对大数据的系统思维20云计算湖南大学信息科学与工程学院1.数据为中心的计算架构过去20年来,计算器件的带宽提升了100–2000倍，而延迟改善只有5-20倍CPU和on-chipL2之间:带宽:增长了2250倍延迟:降低了20倍L3cache和DRAM之间：带宽:增长了125倍延迟:降低了4倍DRAM和disk之间:带宽:增长了150倍延迟:降低了8倍LAN连接的两个节点之间:带宽:增长了100倍延迟:降低了15倍充分利用数据和存储的局部性（缓存、复制、预取）延迟提升滞后于带宽Source：CACM（Patterson)21云计算湖南大学信息科学与工程学院二、应对大数据的系统思维1.数据为中心的计算架构（续）20二、应对大数据的计算思维–数据分布存储在计算附近？–计算尽量利用数据局部性–存储架构、互连网络架构数据密集型计算计算密集型计算SystemData–数据存储与计算相分离–计算之前加载数据–规模挑战：元数据管理+数据传输22云计算湖南大学信息科学与工程学院221.数据为中心的计算架构（续）案例：MicrosoftFlatDatacenterStorage(OSDI2012)MinuteSort新架构+高效互连网络23云计算湖南大学信息科学与工程学院•简化的可扩展数据并行处理：MapReduce框架Map:Key1/Value1（输入数据）Reduce:Key2/Value2（中间数据）Key2/Value2（中间数据）Value（输出数据）数据按照key进行分区：数据并行Google提出（OSDI’04）中间数据输出数据输入数据222.化繁为简，分而治之24云计算湖南大学信息科学与工程学院•特点每个Map/Reduce任务相对独立，执行的任务简单简单，易于扩展（应用无需修改）、容错性好（复算）缺点：Map和Reduce阶段之间需要大量的数据交换•开源实现Hadoop及其变型成功应用于众多著名公司•Facebook,Yahoo!,AOL,EBay,IBM,….•百度，阿里巴巴等MapReduce数据并行框架25云计算湖南大学信息科学与工程学院•MapReduce革新MapReduceOnline(UCBerkeley)、HadoopDB((Yale))Hadoop++(Dittrichetal.:VLDB’2012)Spark（内存Hadoop，UCBerkeley）…•新的数据并行处理框架Pregel，GraphLab:图数据的并行处理框架Dremel：快速交互式数据分析系统，PB/sStorm：流处理数据框架….学术界和工业界不懈努力26云计算湖南大学信息科学与工程学院数据一致性关系数据库：强一致性AtomicityConsistencyIsolationDurability（ACID）写操作完成后，任何后续读操作将得到最新值•分布式环境下，强一致性的代价昂贵，很多应用也无需强一致性弱化数据一致性，提升可扩展性和可靠性3.求同存异，聚焦领域27云计算湖南大学信息科学与工程学院Youcanhaveatmos