《大数据的关键技术》由会员分享，可在线阅读，更多相关《大数据的关键技术（51页珍藏版）》请在金锄头文库上搜索。
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 , ,多处理器技术, 多处理器技术的
3、核心：, 按处理器之间的关系可以分为两类：, 1 F 1 F/ N ,非对称多处理器架构（ASMP）, ,不同类型计算任务或进程由不同处理器执行 简单，操作系统修改小 低效 早期过渡性架构,对称多处理器架构（SMP）, ,所有处理器完全对等 计算任务按需分配 高效 普遍采用,并行模式,独立并行,两个数据操作间没有数据依,赖关系, ,可以采用独立并行的方式分 配给不同的处理器执行 例：两个独立数据集的Scan,操作,流水线并行,多个操作间存在依赖关系，且,后一个操作必须等待前一个操,作处理完后方可执行 将多个操作分配给不同处理器， 但处理器间以流水线方式执行,例：Scan Sort Group,
4、分割并行,数据操作的输入数据可以分解为多个,子集，且子集之间相互独立,分割为若干独立的子操作，每个子操 作只处理对应的部分数据，并将这些 子操作配到不同的处理器上执行,例： Scan Merge,并行系统架构,共享内存（Shared Memory，SM）,多个处理器，多个磁盘，一个共享,内存，通过数据总线相连,处理器间共享全部磁盘和内存, ,结构简单，负载均衡 数据总线成为瓶颈，可扩展性较差， 共享内存单点故障 适合处理器较少（8）的小规模并 行数据库,共享磁盘（Shared Disk，SD）,多个处理器，每个处理器拥有独立,内存，多个磁盘，处理器与磁盘通,过数据总线相连, ,处理器间共享全部
5、磁盘 容错性提高 共享磁盘成为性能瓶颈，需要额外 维护内存与磁盘间的数据一致性,无共享（Shared Nothing，SN）,每个处理器拥有独立的内存和若干磁盘，,通过高速网络相连,处理器独立处理所管理的数据, ,数据传输量小，效率高 可扩展性强 节点间交换数据开销较大 适合处理器数量较大的大规模并行系统 后期发展的主流,三大关键问题,存储 计算 容错,数据容错, RAID单节点数据冗余存储, RAID0：并行磁盘 RAID1：镜像冗余 RAID10：RAID1+RAID0 RAID5：校验冗余 Source: http:/ 集群多节点数据冗余存储,计算任务容错, 计算任务容错的关键问题：,
6、故障监测, 计算数据定位与获取 任务迁移,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亿网址 索引+
7、上市 +学术搜索,地图 +Talk+ 分析,YouTube +Google Apps,Gmail+ 街景 +Android,Health+ iPhone 应用,社交网络 搜索+实时 地图导航+ 搜索 收购Moto,手机+投 平板电脑 资能源+ +Google 应用商店 眼镜,Google Google最重要的业务？ 搜索 AdWords Google发展史,Google之前的搜索, 目录型搜索：Yahoo!, 收集：人工分类 索引：主题, 使用：目录结构 优点：准确率高 缺点：覆盖率低, 索引型搜索：AltaVista, 收集：自动爬取（Scooter） 索引：自动标记, 使用：输入关键词搜索
8、 优点：覆盖率高 缺点：准确率低, 覆盖率 VS. 准确率：鱼与熊掌不可兼得？,Google,Google的自我揭秘！ 核心算法 Lawrence Page, Sergey Brin, et. al., The PageRank Citation Ranking: Bringing Order to the Web. Technical Report, Stanford InfoLab, 1999. (6881) 三大法宝 Sanjay Ghemawat, Howard Gobioff, et. al., The Google file system, Proceedings of the N
9、ineteenth 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
10、 System for Structured Data, Seventh Symposium on Operating System Design and Implementation, 2006. (2558),灵 魂,血 肉, 搜索结果如何排序！, 佩奇（Page），斯坦福, 整个互联网就像一张大的图，每个网站就像一个节点， 每个网页的链接就像一个弧。我想，互联网可以用一个 图或者矩阵描述，我也许可以用这个发现做篇博士论文。,算法的图论表述,0 1/2 0 1/2 0,0 0 1/2 0 1/2,0 0 0 1 0,0 0 0 0 1,1/3 1/3 1/3 0 0,n1,n2,n3 n4
11、 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*Bkj end for end for,7: end for 算法复杂度：O(N3) 以1次乘法需要1个时钟周期，计算10亿维度矩阵为 例，使用1G的CPU，需要的计算时间为： t = 10亿10亿10亿 / 10亿 = 317年！,是否OK？,想办法解决大规模矩阵相乘问题：
12、我拆, Cm = Am B M台服务器并行计算，时间降低为1/M,C,A,B,C1,Cm CM,A1,Am AM,=,想办法解决大规模矩阵相乘问题：我再拆, Cm,n = Am Bn M M台服务器并行计算，时间降低为1/M2,C,A,B,A1,Am AM,=,C1,1,Cm,1 CM,1,B1,Bn,BM,子任务,子任务,子任务,拆的本质 分而治之 分而治之 Divide and Conquer 一个大的计算任务分解为若干小计算任务 子任务计算结果合并后获得最终结果 计算任务 Divide,Conquer 计算结果,MapReduce的来源, 编程模型：, 1956年John McCarth
13、y（图灵奖获得者）提出的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原理,Source：http:/www.infosun.fim.uni-pass
14、au.de/cl/MapReduceFoundation/,MapReduce机制, 主控程序（Master）：将Map和Reduce分配到合适的工作机上 工作机（Worker）：执行Map或Reduce任务,MapReduce不仅仅是编程模型!, 让程序员在使用MapReduce时面对以下细节问题？, 大数据如何分割为小数据块？, 如何调度计算任务并分配和调度map和reduce任务节点？ 如何在任务节点间交换数据？ 如何同步任务？, 相互依赖的任务是否执行完成？ 任务节点失效时该如何处理？, Google的MapReduce是一个完整的计算框架, 程序员只需要编写少量的程序实现应用层逻辑,
15、程序示例：WordCount,#include “mapreduce/mapreduce.h“ class 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) ParseComma
