大数据存储与处理-第二讲.ppt
大数据的三个关键问题Google的大数据技术Google的业务：PageRank三大法宝,1,第二讲 大数据的关键技术,文件存储,数据分析数据计算数据存储,平台管理,数据集成,数据源,Database Web Log,现代数据处理能力组件,现代数据处理框架,三大关键问题3V,计算存储,容错,三大关键问题,存储计算容错,存储问题,解决大数据存储效率的两方面：,容量,吞吐量,容量,单硬盘容量提升：MB GB TB 系统整体容量提升：DAS、NAS、SAN,吞吐量=传输数据量/传输时间,单硬盘吞吐量提升：转速、接口、缓存等 节点吞吐量提升：RAID、专用数据库机,提升吞吐量,RAID：Redundant Array of Inexpensive Disks，冗余磁盘阵列,把多块独立的硬盘按一定的方式组合起来形成一个硬盘组，从而实现高性,能和高可靠性,RAID0：连续以位或字节为单位分割数据，并行读/写于多个磁盘上，提升,吞吐量,Source:,三大关键问题,存储计算容错,多核技术,Moor定律：当价格不变时，集成电路上可容纳的晶体管数目，约每,隔18个月便会增加一倍，性能也将提升一倍。,采用多核（Multi-core）技术提升IPC，从而突破性能提升瓶颈。,指令数,主频,IPS MF IPC,多处理器技术,多处理器技术的核心：,按处理器之间的关系可以分为两类：,1 F 1 F/N,非对称多处理器架构（ASMP）,不同类型计算任务或进程由不同处理器执行简单，操作系统修改小低效早期过渡性架构,对称多处理器架构（SMP）,所有处理器完全对等计算任务按需分配高效普遍采用,并行模式,独立并行,两个数据操作间没有数据依,赖关系,可以采用独立并行的方式分配给不同的处理器执行例：两个独立数据集的Scan,操作,流水线并行,多个操作间存在依赖关系，且,后一个操作必须等待前一个操,作处理完后方可执行将多个操作分配给不同处理器，但处理器间以流水线方式执行,例：Scan Sort Group,分割并行,数据操作的输入数据可以分解为多个,子集，且子集之间相互独立,分割为若干独立的子操作，每个子操作只处理对应的部分数据，并将这些子操作配到不同的处理器上执行,例：Scan Merge,并行系统架构,共享内存（Shared Memory，SM）,多个处理器，多个磁盘，一个共享,内存，通过数据总线相连,处理器间共享全部磁盘和内存,结构简单，负载均衡数据总线成为瓶颈，可扩展性较差，共享内存单点故障适合处理器较少（8）的小规模并行数据库,共享磁盘（Shared Disk，SD）,多个处理器，每个处理器拥有独立,内存，多个磁盘，处理器与磁盘通,过数据总线相连,处理器间共享全部磁盘容错性提高共享磁盘成为性能瓶颈，需要额外维护内存与磁盘间的数据一致性,无共享（Shared Nothing，SN）,每个处理器拥有独立的内存和若干磁盘，,通过高速网络相连,处理器独立处理所管理的数据,数据传输量小，效率高可扩展性强节点间交换数据开销较大适合处理器数量较大的大规模并行系统后期发展的主流,三大关键问题,存储计算容错,数据容错,RAID单节点数据冗余存储,RAID0：并行磁盘 RAID1：镜像冗余 RAID10：RAID1+RAID0 RAID5：校验冗余Source:,集群多节点数据冗余存储,计算任务容错,计算任务容错的关键问题：,故障监测,计算数据定位与获取 任务迁移,Google是如何解决其大数据处理的三个关键性问题的?我们需要先了解Google的业务特点。,14,Google的大数据技术,1995,1996,1997,1999,2001,2003,2005,2007,2009,2011,.,1998,2000,2002,2004,2006,2008,2010,2012,当佩奇遇见布林,合作开发BackRub搜索引擎,命名Google,Google公司成立,首名专用厨师入职,建立10亿网址的索引,图片搜索+30亿网址索引,商品+新闻+API,开始收购+Google图书,80亿网址索引+上市+学术搜索,地图+Talk+分析,YouTube+GoogleApps,Gmail+街景+Android,Health+iPhone应用,社交网络搜索+实时 地图导航+搜索 收购Moto,手机+投 平板电脑资能源+Google应用商店 眼镜,GoogleGoogle最重要的业务？搜索AdWords Google发展史,Google之前的搜索,目录型搜索：Yahoo!,收集：人工分类 索引：主题,使用：目录结构 优点：准确率高 缺点：覆盖率低,索引型搜索：AltaVista,收集：自动爬取（Scooter）索引：自动标记,使用：输入关键词搜索 优点：覆盖率高 缺点：准确率低,覆盖率 VS.准确率：鱼与熊掌不可兼得？,Google,Google的自我揭秘！核心算法 Lawrence Page,Sergey Brin,et.al.,The PageRank Citation Ranking:Bringing Order to theWeb.Technical Report,Stanford InfoLab,1999.(6881)三大法宝 Sanjay Ghemawat,Howard Gobioff,et.al.,The Google file system,Proceedings of theNineteenth ACM Symposium on Operating Systems Principles,2003.(3911)Jeffrey Dean,Sanjay Ghemawat,MapReduce:Simplified Data Processing on Large Clusters,Sixth Symposium on Operating System Design and Implementation,2004.(9569)Fay Chang,Jeffrey Dean,et.al.,Bigtable:A Distributed Storage System for Structured Data,Seventh Symposium on Operating System Design and Implementation,2006.(2558),灵魂,血肉,搜索结果如何排序！,佩奇（Page），斯坦福,整个互联网就像一张大的图，每个网站就像一个节点，每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做篇博士论文。,算法的图论表述,01/201/20,001/201/2,00010,00001,1/31/31/300,n1,n2,n3 n4 n5,PageRank（9）算法的计算问题,如何计算10亿、100亿个网页？,行列数以亿为单位的矩阵相乘！,Google三大法宝之一：MapReduce,矩阵乘法串行实现1:for i=1;i=N;i+,2:,for j=1;j=N;j+,3:4:5:6:,for k=1;k=N;k+Cij+=Aik*Bkjend forend for,7:end for 算法复杂度：O(N3)以1次乘法需要1个时钟周期，计算10亿维度矩阵为例，使用1G的CPU，需要的计算时间为：t=10亿10亿10亿/10亿=317年！,是否OK？,想办法解决大规模矩阵相乘问题：我拆,Cm=Am B M台服务器并行计算，时间降低为1/M,C,A,B,C1,CmCM,A1,AmAM,=,想办法解决大规模矩阵相乘问题：我再拆,Cm,n=Am Bn M M台服务器并行计算，时间降低为1/M2,C,A,B,A1,AmAM,=,C1,1,Cm,1CM,1,B1,Bn,BM,子任务,子任务,子任务,拆的本质 分而治之 分而治之 Divide and Conquer 一个大的计算任务分解为若干小计算任务 子任务计算结果合并后获得最终结果计算任务Divide,Conquer计算结果,MapReduce的来源,编程模型：,1956年John McCarthy（图灵奖获得者）提出的Lisp语言中的,Map/Reduce方法,Map输入是一个函数和n个列表，输出是一个新的列表，列表中的元素是,将输入函数作用在n个输入列表中每个对应元素获得的计算结果。,Reduce输入是一个函数和一个列表，输出是将函数依次作用于列表的每,个元素后获得的计算结果,(map vector#*#(1 2 3 4 5)#(5 4 3 2 1)-#(5 8 9 8 5),(reduce#+#(5 8 9 8 5)-35,Lisp中的Map和Reduce操作,MapReduce原理,MapReduce机制,主控程序（Master）：将Map和Reduce分配到合适的工作机上 工作机（Worker）：执行Map或Reduce任务,MapReduce不仅仅是编程模型!,让程序员在使用MapReduce时面对以下细节问题？,大数据如何分割为小数据块？,如何调度计算任务并分配和调度map和reduce任务节点？如何在任务节点间交换数据？如何同步任务？,相互依赖的任务是否执行完成？任务节点失效时该如何处理？,Google的MapReduce是一个完整的计算框架,程序员只需要编写少量的程序实现应用层逻辑,程序示例：WordCount,#include mapreduce/mapreduce.hclass WordCounter:public Mapper public:virtual void Map(const MapInput,class Adder:public Reducer virtual void Reduce(ReduceInput*input)int64 value=0;while(!input-done()value+=StringToInt(input-value();input-NextValue();Emit(IntToString(value);REGISTER_REDUCER(Adder);,int main(int argc,char*argv)ParseCommandLineFlags(argc,argv);MapReduceSpecification spec;for(int i=1;i set_format(text);input-set_filepattern(argvi);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);MapReduceResult result;if(!MapReduce(spec,Google三大法宝之二：GFS,GFS简介,GFS Google File System，Google自有的分布式文件,系统,为什么需要GFS？,已有多种分布式文件系统（NFS、AFS、DFS、）Google特有的环境与负载需要,Google特有的数据和计算,Google处理的主要数据,爬取的网页,网站访问日志,其他相对独立的数据,数据计算的期望结果,词频统计 倒排索引,网页文档的链接图 网站页面数量统计,特点,单个计算简单 数量庞大,数据相对独立,GFS支持大容量,用集群方式提升系统整体容量,Google的第一台服务器（1998）,Intel CPU+IDE硬盘,x,GFS支持高吞吐量 Google处理的数据特点 抓取网页并存储：顺序写入，极少发生随机写的情况 分析网页内容：文件写入后，只会发生读的操作，不会再修改 GFS实现高吞吐量的两个关键点：顺序写入，顺序读取，避免随机读写,文件传输效率公式,SEEK _TIMEblock _ size/SPEED SEEK _TIME,1,trans_timetrans_time SEEK _TIME,effect,西数 80G SATA硬盘 随机读,55,8.2 数据以远大于操作系统文件块的基本单元进行存储（64MB vs.512B）,GFS支持容错 问题：大量廉价PC组件构成的集群作为硬件基础，单节点故障率较高,Google的第一台服务器（1998）Intel CPU+IDE硬盘,集群多节点数据冗余存储,GFS系统架构,客户端（Client）,GFS提供给上层应用使用的一组接口库上层应用通过调用接口库中的接口实现GFS系统中的文件管理,适合自身应用的简单接口,主控节点（Master）,管理节点唯一性保存元数据调配块服务器,块服务器（Chunk Server）,存储数据块（Chunk）多个固定块大小（默认64MB）数据库多节点冗余备份,讨论：分析一下，GFS的文件读写流程大致应该是怎么样的？,计算索引：客户端将应用提供的文件名和字节偏移通过固定文件块大小进行计算后获得块索引传递索引：客户端将文件名称和块索引发送给主控节点返回位置：主控节点将用于访问文件块的块句柄和文件块所在的块服务器位置返回给客户端访问数据：客户端将位置信息进行缓存，并访问离自己距离最近的块服务器返回数据：被访问的块服务器将数据返回给客户端,GFS读数据流程,Google三大法宝之三：BigTable,简单搜索框背后的复杂工作,1.Crawler从URL服务器提取地址进行遍历查找2.获取文档docs,建立文档docIDs,进行分析、压缩3.存储到文档数据库4.索引器为docs建立顺排索引和倒排索引5.索引数据存储到集群中,建立索引,响应请求,1.2.3.4.5.,对请求进行预处理，包括拼写检查、附加广告等GWS向索引服务器发送查询关键字索引服务器根据关键字查找匹配文档并向GWS返回docIDsGWS将docIDs传给文档服务器，获得文档GWS将查询结果文档以HTML形式返回给用户,为什么需要BigTable？,GFS的局限性：文件系统，不适合结构化数据的存储和访问,结构化数据？使用DB2、SQLServer、MySQL之类的数据库系统？非也！因为：,存储数据的多样性与复杂性：URL、网页内容、用户数据等 海量的处理请求 成本与控制力,BigTable的目标：,适应各种不同类型的数据和应用,随时增加和减少处理节点的可扩展性和自动平衡能力 PB级数据环境下的高吞吐量和高并发（百万级TPS）连续服务的高可用性和容错性 架构与使用的简洁性,BigTable数据模型,BigTable：是一个经过排序后的分布式的、稀疏的、多维映射表,分布式：数据是分布式存储的,稀疏：列数可能很多，而某一行中可能只有少数列有数据 多维映射表：,数据索引由行关键字（Row Key）、列关键字（Column Key）和时间戳,（Time Stamp）三个维度构成 数据以键/值映射的形式组织,(row:string,column:string,time:int64)string,BigTable示例,网站页面内容及其中超链接的解析,t3、t5、t6三个时间点抓取的网页内容存储在contents列中,有两个网页包含了到网页的链接，分别是位于页面的超链接,文字CNN，和位于my.look.ca页面的超链接文字CNN.com,第43,BigTable表的展开,行数,行关键字,版本,列族：contents,列族：anchor,限定词：,12,“CNN”,“CNN.com”,t2t1t7t6t5t4t3,a2a1d4c3b2,面向列的存储,提高访问少数列的效率,整行扫描 vs.单列读取,提高压缩比,杂 vs.纯,BigTable系统架构,子表（Tablet）,过大的数据表不利于存储和访问效率大表在水平方向上被分为多个子表，每个子表包含表中,若干行的数据,支持数据表的分布式存储和表访问的负载均衡,主控服务器,操作及管理数据表元数据子表分配与监控负载均衡控制,子表服务器,数据服务器的基本单元数据以文件形式存储在GFS文件系统中,
