大数据存储与处理-第二讲51

大数据的三个关键问题Google的大数据技术Google的业务：PageRank三大法宝1第二讲大数据的关键技术文件存储数据分析数据计算数据存储平台管理数据集成数据源DatabaseWebLog…现代数据处理能力组件现代数据处理框架三大关键问题3V计算存储｝容错｝｝三大关键问题存储计算容错存储问题解决大数据存储效率的两方面：–容量–吞吐量容量–单硬盘容量提升：MB→GB→TB→┈–系统整体容量提升：DAS、NAS、SAN吞吐量=传输数据量/传输时间–单硬盘吞吐量提升：转速、接口、缓存等–节点吞吐量提升：RAID、专用数据库机提升吞吐量RAID：RedundantArrayofInexpensiveDisks，冗余磁盘阵列–把多块独立的硬盘按一定的方式组合起来形成一个硬盘组，从而实现高性能和高可靠性–RAID0：连续以位或字节为单位分割数据，并行读/写于多个磁盘上，提升吞吐量Source:Moor定律：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。采用多核（Multi-core）技术提升IPC，从而突破性能提升瓶颈。指令数主频IPSMFIPC多处理器技术多处理器技术的核心：按处理器之间的关系可以分为两类：1F1F/N非对称多处理器架构（ASMP）––––不同类型计算任务或进程由不同处理器执行简单，操作系统修改小低效早期过渡性架构对称多处理器架构（SMP）––––所有处理器完全对等计算任务按需分配高效普遍采用并行模式独立并行–两个数据操作间没有数据依赖关系––可以采用独立并行的方式分配给不同的处理器执行例：两个独立数据集的Scan操作流水线并行–多个操作间存在依赖关系，且后一个操作必须等待前一个操–作处理完后方可执行将多个操作分配给不同处理器，但处理器间以流水线方式执行–例：Scan→Sort→Group分割并行–数据操作的输入数据可以分解为多个子集，且子集之间相互独立–分割为若干独立的子操作，每个子操作只处理对应的部分数据，并将这些子操作配到不同的处理器上执行–例：Scan→Merge并行系统架构共享内存（SharedMemory，SM）–多个处理器，多个磁盘，一个共享内存，通过数据总线相连–处理器间共享全部磁盘和内存–––结构简单，负载均衡数据总线成为瓶颈，可扩展性较差，共享内存单点故障适合处理器较少（≤8）的小规模并行数据库共享磁盘（SharedDisk，SD）–多个处理器，每个处理器拥有独立内存，多个磁盘，处理器与磁盘通过数据总线相连–––处理器间共享全部磁盘容错性提高共享磁盘成为性能瓶颈，需要额外维护内存与磁盘间的数据一致性无共享（SharedNothing，SN）–每个处理器拥有独立的内存和若干磁盘，通过高速网络相连–处理器独立处理所管理的数据–––––数据传输量小，效率高可扩展性强节点间交换数据开销较大适合处理器数量较大的大规模并行系统后期发展的主流三大关键问题存储计算容错数据容错RAID单节点数据冗余存储–RAID0：并行磁盘–RAID1：镜像冗余–RAID10：RAID1+RAID0–RAID5：校验冗余Source:集群多节点数据冗余存储计算任务容错计算任务容错的关键问题：–故障监测–计算数据定位与获取–任务迁移Google是如何解决其大数据处理的三个关键性问题的?我们需要先了解Google的业务特点。14Google的大数据技术1995199619971999200120032005200720092011...19982000200220042006200820102012当佩奇遇见布林合作开发BackRub搜索引擎命名GoogleGoogle公司成立首名专用厨师入职建立10亿网址的索引图片搜索+30亿网址索引商品+新闻+API开始收购+Google图书80亿网址索引+上市+学术搜索地图+Talk+分析YouTube+GoogleAppsGmail+街景+AndroidHealth+iPhone应用社交网络搜索+实时地图导航+搜索收购Moto手机+投平板电脑资能源++Google应用商店眼镜GoogleGoogle最重要的业务？搜索AdWordsGoogle发展史Google之前的搜索目录型搜索：Yahoo!–收集：人工分类–索引：主题–使用：目录结构–优点：准确率高–缺点：覆盖率低索引型搜索：AltaVista–收集：自动爬取（Scooter）–索引：自动标记–使用：输入关键词搜索–优点：覆盖率高–缺点：准确率低覆盖率VS.准确率：鱼与熊掌不可兼得？GoogleGoogle的自我揭秘！核心算法–LawrencePage,SergeyBrin,et.al.,ThePageRankCitationRanking:BringingOrdertotheWeb.TechnicalReport,StanfordInfoLab,1999.(6881)三大法宝–SanjayGhemawat,HowardGobioff,et.al.,TheGooglefilesystem,ProceedingsoftheNineteenthACMSymposiumonOperatingSystemsPrinciples,2003.(3911)–JeffreyDean,SanjayGhemawat,MapReduce:SimplifiedDataProcessingonLargeClusters,SixthSymposiumonOperatingSystemDesignandImplementation,2004.(9569)–FayChang,JeffreyDean,et.al.,Bigtable:ADistributedStorageSystemforStructuredData,SeventhSymposiumonOperatingSystemDesignandImplementation,2006.(2558)灵魂血肉搜索结果如何排序！佩奇（Page），斯坦福–整个互联网就像一张大的图，每个网站就像一个节点，每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做篇博士论文。算法的图论表述01/201/20001/201/200010000011/31/31/300n1n2n3n4n5PageRank（9）–算法的计算问题如何计算10亿、100亿个网页？行列数以亿为单位的矩阵相乘！Google三大法宝之一：MapReduce矩阵乘法串行实现1:fori=1;i=N;i++2:forj=1;j=N;j++3:4:5:6:fork=1;k=N;k++C[i][j]+=A[i][k]*B[k][j]endforendfor7:endfor算法复杂度：O(N3)以1次乘法需要1个时钟周期，计算10亿维度矩阵为例，使用1G的CPU，需要的计算时间为：t=10亿×10亿×10亿/10亿=317年！是否OK？想办法解决大规模矩阵相乘问题：我拆Cm=AmⅹBM台服务器并行计算，时间降低为1/MCABC1CmCMA1AmAM=ⅹ想办法解决大规模矩阵相乘问题：我再拆Cm,n=AmⅹBnMⅹM台服务器并行计算，时间降低为1/M2CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM子任务子任务子任务…拆的本质－分而治之分而治之–DivideandConquer–一个大的计算任务分解为若干小计算任务–子任务计算结果合并后获得最终结果计算任务DivideConquer计算结果MapReduce的来源编程模型：–1956年JohnMcCarthy（图灵奖获得者）提出的Lisp语言中的Map/Reduce方法–Map输入是一个函数和n个列表，输出是一个新的列表，列表中的元素是将输入函数作用在n个输入列表中每个对应元素获得的计算结果。–Reduce输入是一个函数和一个列表，输出是将函数依次作用于列表的每个元素后获得的计算结果(map'vector#*#(12345)#(54321)-#(58985)(reduce#'+#(58985))-35Lisp中的Map和Reduce操作MapReduce原理Source：主控程序（Master）：将Map和Reduce分配到合适的工作机上工作机（Worker）：执行Map或Reduce任务MapReduce不仅仅是编程模型!让程序员在使用MapReduce时面对以下细节问题？–大数据如何分割为小数据块？–如何调度计算任务并分配和调度map和reduce任务节点？–如何在任务节点间交换数据？–如何同步任务？–相互依赖的任务是否执行完成？–任务节点失效时该如何处理？Google的MapReduce是一个完整的计算框架–程序员只需要编写少量的程序实现应用层逻辑程序示例：WordCount#includemapreduce/mapreduce.hclassWordCounter:publicMapper{public:virtualvoidMap(constMapInput&input){conststring&text=input.value();constintn=text.size();for(inti=0;in;){while((in)&&isspace(text[i]))i++;intstart=i;while((in)&&!isspace(text[i]))i++;if(starti)Emit(text.substr(start,i-start),1);}}};REGISTER_MAPPER(WordCounter);classAdder:publicReducer{virtualvoidReduce(ReduceInput*input){int64value=0;while(!input-done()){value+=StringToInt(input-value());input-NextValue();}Emit(IntToString(value));}};REGISTER_REDUCER(Adder);intmain(intargc,char**argv){ParseCommandLineFlags(argc,argv);MapReduceSpecificationspec;for(inti=1;iargc;i++){MapReduceInput*input=spec.add_input();input-set_format(text);input-set_filepattern(argv[i]);input-set_mapper_class(WordCounter);}MapReduceOutput*out=spec.output();out-set_filebase(/gfs/test/freq);out-set_num_tasks(100);out-set_format(text);out-set_reducer_class(Adder);out-set_combiner_class(Adder);spec.set_machines(2000);spec.set_map_megabytes(100);spec.set_reduce_megabytes(100);MapReduceResultresult;if(!MapReduce(spec,&result))abort();return0;}Google三大法宝之二：GFSGFS简介GFS–GoogleFileSystem，Google自有的分布式