大数据的关键技术(51p)课件.ppt

1讲大数据的关键技术第1页，共52页文件存文件存储储数据分析数据分析数据数据计计算算数据存数据存储储平平台台管管理理数据集成数据集成数据源数据源Database Web Log现现代数据代数据处处理理能力能力组组件件现代数据处理框架 三大关键问题3V计算存储容错第2页，共52页三大关键问题存储计算容错第3页，共52页存储问题 解决大数据存储效率的两方面：容量 吞吐量 容量 单硬盘容量提升：MB GB TB 系统整体容量提升：DAS、NAS、SAN 吞吐量=传输数据量/传输时间 单硬盘吞吐量提升：转速、接口、缓存等 节点吞吐量提升：RAID、专用数据库机第4页，共52页提升吞吐量 RAID：Redundant Array of Inexpensive Disks，冗余磁盘阵列 把多块独立的硬盘按一定的方式组合起来形成一个硬盘组，从而实现高性能和高可靠性 RAID0：连续以位或字节为单位分割数据，并行读/写于多个磁盘上，提升吞吐量Source:http:/ Moor定律：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍采用多核（Multi-core）技术提升IPC，从而突破性能提升瓶颈。

指令数主频第7页，共52页IPS MF IPC 多处理器技术 多处理器技术的核心：按处理器之间的关系可以分为两类：1 F 1 F/N 非对称多处理器架构（ASMP）不同类型计算任务或进程由不同处理器执行简单，操作系统修改小低效早期过渡性架构对称多处理器架构（SMP）所有处理器完全对等计算任务按需分配高效普遍采用第8页，共52页并行模式独立并行两个数据操作间没有数据依赖关系可以采用独立并行的方式分配给不同的处理器执行例：两个独立数据集的Scan操作流水线并行多个操作间存在依赖关系，且后一个操作必须等待前一个操作处理完后方可执行将多个操作分配给不同处理器，但处理器间以流水线方式执行例：Scan Sort Group分割并行数据操作的输入数据可以分解为多个子集，且子集之间相互独立分割为若干独立的子操作，每个子操作只处理对应的部分数据，并将这些子操作配到不同的处理器上执行例：Scan Merge第9页，共52页并行系统架构共享内存（Shared Memory，SM）多个处理器，多个磁盘，一个共享内存，通过数据总线相连处理器间共享全部磁盘和内存结构简单，负载均衡数据总线成为瓶颈，可扩展性较差，共享内存单点故障适合处理器较少（8）的小规模并行数据库共享磁盘（Shared Disk，SD）多个处理器，每个处理器拥有独立内存，多个磁盘，处理器与磁盘通过数据总线相连处理器间共享全部磁盘容错性提高共享磁盘成为性能瓶颈，需要额外维护内存与磁盘间的数据一致性无共享（Shared Nothing，SN）每个处理器拥有独立的内存和若干磁盘，通过高速网络相连处理器独立处理所管理的数据数据传输量小，效率高可扩展性强节点间交换数据开销较大适合处理器数量较大的大规模并行系统后期发展的主流第10页，共52页。

三大关键问题存储计算容错第11页，共52页数据容错 RAID单节点数据冗余存储 RAID0：并行磁盘 RAID1：镜像冗余 RAID10：RAID1+RAID0 RAID5：校验冗余Source:http:/ 计算任务容错的关键问题：故障监测 计算数据定位与获取 任务迁移第13页，共52页Google是如何解决其大数据处理的三个关键性问题的?我们需要先了解Google的业务特点14Google的大数据技术第14页，共52页1995199619971999200120032005200720092011.19982000200220042006200820102012当佩奇遇见布林合作开发BackRub搜索引擎命名GoogleGoogle公司成立首名专用厨师入职建立10亿网址的索引图片搜索+30亿网址索引商品+新闻+API开始收购+Google图书80亿网址索引+上市+学术搜索地图+Talk+分析YouTube+GoogleAppsGmail+街景+AndroidHealth+iPhone应用社交网络搜索+实时 地图导航+搜索 收购Moto+投 平板电脑资能源+Google应用商店 眼镜GoogleGoogle最重要的业务？搜索AdWords Google发展史第15页，共52页。

Google之前的搜索 目录型搜索：Yahoo!收集：人工分类 索引：主题 使用：目录结构 优点：准确率高 缺点：覆盖率低 索引型搜索：AltaVista 收集：自动爬取（Scooter）索引：自动标记 使用：输入关键词搜索 优点：覆盖率高 缺点：准确率低 覆盖率 VS.准确率：鱼与熊掌不可兼得？第16页，共52页Google第17页，共52页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)灵魂血肉第18页，共52页。

第19页，共52页搜索结果如何排序！第20页，共52页第21页，共52页佩奇（Page），斯坦福 整个互联网就像一张大的图，每个网站就像一个节点，每个网页的链接就像一个弧我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做篇博士论文第22页，共52页算法的图论表述第23页，共52页01/201/20001/201/200010000011/31/31/300n1n2n3 n4 n5第24页，共52页PageRank（9）算法的计算问题如何计算10亿、100亿个网页？行列数以亿为单位的矩阵相乘！第25页，共52页Google三大法宝之一：MapReduce第26页，共52页矩阵乘法串行实现1:for i=1;i=N;i+2:for j=1;j=N;j+3:4:5:6:for k=1;k#(5 8 9 8 5)(reduce#+#(5 8 9 8 5)-35Lisp中的Map和Reduce操作第31页，共52页MapReduce原理Source：http:/www.infosun.fim.uni-passau.de/cl/MapReduceFoundation/第32页，共52页MapReduce机制 主控程序（Master）：将Map和Reduce分配到合适的工作机上 工作机（Worker）：执行Map或Reduce任务第33页，共52页。

MapReduce不仅仅是编程模型!让程序员在使用MapReduce时面对以下细节问题？大数据如何分割为小数据块？如何调度计算任务并分配和调度map和reduce任务节点？如何在任务节点间交换数据？如何同步任务？相互依赖的任务是否执行完成？任务节点失效时该如何处理？Google的MapReduce是一个完整的计算框架 程序员只需要编写少量的程序实现应用层逻辑第34页，共52页程序示例：WordCount#include mapreduce/mapreduce.hclass WordCounter:public Mapper public:virtual void Map(const MapInput&input)const string&text=input.value();const int n=text.size();for(int i=0;i n;)while(i n)&isspace(texti)i+;int start=i;while(i n)&!isspace(texti)i+;if(start 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,&result)abort();return 0;第35页，共52页。

Google三大法宝之二：GFS第36页，共52页GFS简介 GFS Google File System，Google自有的分布式文件系统 为什么需要GFS？已有多种分布式文件系统（NFS、AFS、DFS、）Google特有的环境与负载需要第37页，共52页Google特有的数据和计算 Google处理的主要数据 爬取的网页 网站访问日志 其他相对独立的数据 数据计算的期望结果 词频统计 倒排索引 网页文档的链接图 网站页面数量统计 特点 单个计算简单 数量庞大 数据相对独立第38页，共52页GFS支持大容量 用集群方式提升系统整体容量Google的第一台服务器（1998）Intel CPU+IDE硬盘x第39页，共52页GFS支持高吞吐量 Google处理的数据特点 抓取网页并存储：顺序写入，极少发生随机写的情况 分析网页内容：文件写入后，只会发生读的操作，不会再修改 GFS实现高吞吐量的两个关键点：顺序写入，顺序读取，避免随机读写文件传输效率公式SEEK _TIMEblock _ size/SPEED SEEK _TIME 1 trans_timetrans_time SEEK _TIMEeffect 西数 80G SATA硬盘 随机读558.2 数据以远大于操作系统文件块的基本单元进行存储（64MB vs.512B）第40页，共52页。

GFS支持容错 问题：大量廉价PC组件构成的集群作为硬件基础，单节点故障率较高Google的第一台服务器（1998）Intel CPU+IDE硬盘集群多节点数据冗余存储第41页，共52页GFS系。