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