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

1、大数据的三个关键问题Google的大数据技术Google的业务：PageRank三大法宝1第二讲 大数据的关键技术文件存储储数据分析析数据计算算数据存储储平台管理数据集成成数据源DatabaseWebLog现代数据据处理能力组件件现代数据据处理框框架三大关键键问题3V计算存储容错三大关键键问题存储计算容错存储问题题解决大数据存储效率的两方面面：容量吞吐量容量单硬盘容容量提升升：MBGBTB系统整体体容量提提升：DAS、NAS、SAN吞吐量=传输数据据量/传输时间间单硬盘吞吞吐量提提升：转转速、接接口、缓缓存等节点吞吐吐量提升升：RAID、专用数数据库机机提升吞吐吐量RAID：Redundant

2、ArrayofInexpensiveDisks，冗冗余磁盘盘阵列把多块独独立的硬硬盘按一一定的方方式组合合起来形形成一个个硬盘组组，从而而实现高高性能和高可可靠性RAID0：连连续以位位或字节节为单位位分割数数据，并并行读/写于多多个磁盘盘上，提提升吞吐量三大关键键问题存储计算容错多核技术术Moor定律：当价格格不变时时，集成成电路上上可容纳纳的晶体体管数目目，约每每隔18个个月便会会增加一一倍，性性能也将将提升一一倍。采用多核核（Multi-core）技术提提升IPC，从从而突破破性能提提升瓶颈颈。指令数主频IPSMFIPC 多处理器器技术多处理器器技术的的核心：按处理器器之间的的关系可可以

3、分为为两类：1F1F/N非对称多多处理器器架构（ASMP）不同类型型计算任任务或进进程由不不同处理理器执行行简单，操操作系统统修改小小低效早期过渡渡性架构构对称多处处理器架架构（SMP）所有处理理器完全全对等计算任务务按需分分配高效普遍采用用并行模式式独立并行行两个数据据操作间间没有数数据依赖关系可以采用用独立并并行的方方式分配给不同同的处理理器执行行例：两个个独立数数据集的的Scan操作流水线并并行多个操作作间存在在依赖关关系，且且后一个操操作必须须等待前前一个操操作处理完完后方可可执行将多个操操作分配配给不同同处理器器，但处理器器间以流流水线方方式执行行例：ScanSortGroup分割并

4、行行数据操作作的输入入数据可可以分解解为多个个子集，且且子集之之间相互互独立分割为若若干独立立的子操操作，每每个子操操作只处理理对应的的部分数数据，并并将这些些子操作配配到不同同的处理理器上执执行例：ScanMerge并行系统统架构共享内存存（SharedMemory，SM）多个处理理器，多多个磁盘盘，一个个共享内存，通通过数据据总线相相连处理器间间共享全全部磁盘盘和内存存结构简单单，负载载均衡数据总线线成为瓶瓶颈，可可扩展性性较差，共享内存存单点故故障适合处理理器较少少（8）的小小规模并并行数据库库共享磁盘盘（SharedDisk，SD）多个处理理器，每每个处理理器拥有有独立内存，多多个磁盘

5、盘，处理理器与磁磁盘通过数据总总线相连连处理器间间共享全全部磁盘盘容错性提提高共享磁盘盘成为性性能瓶颈颈，需要要额外维护内存存与磁盘盘间的数数据一致致性无共享（SharedNothing，SN）每个处理理器拥有有独立的的内存和和若干磁磁盘，通过高速速网络相相连处理器独独立处理理所管理理的数据据数据传输输量小，效率高高可扩展性性强节点间交交换数据据开销较较大适合处理理器数量量较大的的大规模模并行系系统后期发展展的主流流三大关键键问题存储计算容错数据容错RAID单节点点数据冗冗余存储储集群多节节点数据据冗余存存储计算任务务容错计算任务务容错的的关键问问题：故障监测测计算数据据定位与与获取任务迁移移

6、Google是是如何解解决其大数据处理理的三个个关键性性问题的的?我们需要要先了解解Google的业务特特点。14Google的大数据据技术1995199619971999200120032005200720092011.19982000200220042006200820102012当佩奇遇遇见布林合作开发发BackRub搜索引擎擎命名GoogleGoogle公司成立立首名专用用厨师入职职建立10亿网址的索索引图片搜索索+30亿亿网址索引商品+新新闻+API开始收购购+Google图书80亿网网址索引+上上市+学术搜搜索地图+Talk+分析YouTube+GoogleAppsGmail+街景

7、+AndroidHealth+iPhone应用社交网络络搜索+实实时地图导航航+搜索收购Moto手机+投投平板电脑脑资能源+Google应用商店店眼镜GoogleGoogle最最重要的的业务？搜索AdWordsGoogle发发展史Google之之前的搜搜索目录型搜搜索：Yahoo!收集：人人工分类类索引：主主题使用：目目录结构构优点：准准确率高高缺点：覆覆盖率低低索引型搜搜索：AltaVista收集：自自动爬取取（Scooter）索引：自自动标记记使用：输输入关键键词搜索索优点：覆覆盖率高高缺点：准准确率低低覆盖率VS.准确率：鱼与熊熊掌不可可兼得？GoogleGoogle的的自我揭揭秘！核心

8、算法法LawrencePage,SergeyBrin,et.al.,ThePageRankCitationRanking:BringingOrdertotheWeb.TechnicalReport,StanfordInfoLab,1999.(6881)三大法宝宝SanjayGhemawat,HowardGobioff,et.al.,TheGooglefilesystem,ProceedingsoftheNineteenthACMSymposiumonOperatingSystemsPrinciples,2003.(3911)JeffreyDean,SanjayGhemawat,MapReduc

9、e:SimplifiedDataProcessingonLargeClusters,SixthSymposiumonOperatingSystemDesignandImplementation,2004.(9569)FayChang,JeffreyDean,et.al.,Bigtable:ADistributedStorageSystemforStructuredData,SeventhSymposiumonOperatingSystemDesignandImplementation,2006.(2558)灵魂血肉搜索结果果如何排排序！佩奇（Page），斯斯坦福整个互联联网就像像一张大大的图，

10、每个网网站就像像一个节节点，每个网页页的链接接就像一一个弧。我想，互联网网可以用用一个图或者矩矩阵描述述，我也也许可以以用这个个发现做做篇博士士论文。算法的图图论表述述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#(58985)(reduce#+#(58985)-35Li

11、sp中的Map和和Reduce操作MapReduce原原理MapReduce机机制主控程序序（Master）：将Map和Reduce分分配到合合适的工工作机上上工作机（Worker）：执执行Map或Reduce任任务MapReduce不不仅仅是是编程模模型!让程序员员在使用用MapReduce时面对对以下细细节问题题？大数据如如何分割割为小数数据块？如何调度度计算任任务并分分配和调调度map和reduce任任务节点点？如何在任任务节点点间交换换数据？如何同步步任务？相互依赖赖的任务务是否执执行完成成？任务节点点失效时时该如何何处理？Google的的MapReduce是一个个完整的的计算框框架程

12、序员只只需要编编写少量量的程序序实现应应用层逻逻辑程序示例例：WordCount#includemapreduce/mapreduce.hclassWordCounter:publicMapperpublic:virtualvoidMap(constMapInput&input)conststring&text=input.value();constintn=text.size();for(inti=0;in;)while(in)&isspace(texti)i+;intstart=i;while(in)&!isspace(texti)i+;if(startdone()value+=Strin

13、gToInt(input-value();input-NextValue();Emit(IntToString(value);REGISTER_REDUCER(Adder);intmain(intargc,char*argv)ParseCommandLineFlags(argc,argv);MapReduceSpecificationspec;for(inti=1;iset_format(text);input-set_filepattern(argvi);input-set_mapper_class(WordCounter);MapReduceOutput*out=spec.output()

14、;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三三大法宝宝之二：

15、GFSGFS简简介GFSGoogleFileSystem，Google自有的的分布式式文件系统为什么需需要GFS？已有多种种分布式式文件系系统（NFS、AFS、DFS、）Google特特有的环环境与负负载需要要Google特特有的数数据和计计算Google处处理的主主要数据据爬取的网网页网站访问问日志其他相对对独立的的数据数据计算算的期望望结果词频统计计倒排索引引网页文档档的链接接图网站页面面数量统统计特点单个计算算简单数量庞大大数据相对对独立GFS支支持大容容量用集群方方式提升升系统整整体容量量Google的的第一台台服务器器（1998）IntelCPU+IDE硬硬盘xGFS支支持高吞吞吐量

16、Google处处理的数数据特点点抓取网页页并存储储：顺序序写入，极少发发生随机机写的情情况分析网页页内容：文件写写入后，只会发发生读的的操作，不会再再修改GFS实实现高吞吞吐量的的两个关关键点：顺序写入入，顺序序读取，避免随随机读写写文件传输输效率公公式SEEK_TIMEblock_size/SPEEDSEEK_TIME1trans_timetrans_timeSEEK_TIMEeffect西数80GSATA硬盘随机读558.2数据以远远大于操操作系统统文件块块的基本本单元进进行存储储（64MBvs.512B）GFS支支持容错错问题：大大量廉价价PC组组件构成成的集群群作为硬硬件基础础，单节节

17、点故障障率较高高Google的的第一台台服务器器（1998）IntelCPU+IDE硬硬盘集群多节节点数据据冗余存存储GFS系系统架构构客户端（Client）GFS提提供给上上层应用用使用的的一组接口库库上层应用用通过调调用接口口库中的接口实实现GFS系统统中的文文件管理适合自身身应用的的简单接接口主控节点点（Master）管理节点点唯一性保存元数数据调配块服服务器块服务器器（ChunkServer）存储数据据块（Chunk）多个固定块大大小（默默认64MB）数据库多多节点冗冗余备份份讨论：分分析一下下，GFS的文件读读写流程程大致应应该是怎怎么样的的？计算索引引：客户户端将应应用提供供的文件

18、件名和字字节偏移移通过固固定文件件块大小小进行计计算后获获得块索索引传递索引引：客户户端将文文件名称称和块索索引发送送给主控控节点返回位置置：主控控节点将将用于访访问文件件块的块块句柄和和文件块块所在的的块服务务器位置置返回给给客户端端访问数据据：客户户端将位位置信息息进行缓缓存，并并访问离离自己距距离最近近的块服服务器返回数据据：被访访问的块块服务器器将数据据返回给给客户端端GFS读读数据流流程Google三三大法宝宝之三：BigTable简单搜索索框背后后的复杂杂工作1.Crawler从URL服务务器提取取地址进进行遍历历查找2.获取文档档docs,建立文文档docIDs,进行分分析、压压

19、缩3.存储到文文档数据据库4.索引器为为docs建立立顺排索索引和倒倒排索引引5.索引数据据存储到到集群中中建立索引引响应请求求1.2.3.4.5.对请求进进行预处处理，包包括拼写写检查、附加广广告等GWS向向索引服服务器发发送查询询关键字字索引服务务器根据据关键字字查找匹匹配文档档并向GWS返返回docIDsGWS将将docIDs传给文文档服务务器，获获得文档档GWS将将查询结结果文档档以HTML形形式返回回给用户户为什么需需要BigTable？GFS的的局限性性：文件件系统，不适合合结构化化数据的的存储和和访问结构化数数据？使使用DB2、SQLServer、MySQL之之类的数数据库系系统？非也！因因为：存储数据据的多样样性与复复杂性：URL、网页内内容、用用户数据据等海量的处处理请求求成本与控控制力BigTable的目目标：适应各种种不同类类型的数数据和应应用随时增加加和减少少处理节节点的可可扩展性性和自动动平衡能能力PB级数数据环境境下的高高吞吐量量和高并并发（百百万级TPS）连续服务务的高可可用性和和容错性