3大数据存储关键技术

海量数据处理中的存储系统案例.Google核心存储技术如何计算10亿、100亿个网页？行列数以亿为单位的矩阵相乘！第2页Google三大法宝之一：MapReduce第3页MapReduce（1）–从矩阵相乘基础开始

第4页MapReduce（2）–矩阵乘法串行实现

第5页1:fori=1;i<=N;i++2:forj=1;j<=N;j++3:fork=1;k<=N;k++4:C[i][j]+=A[i][k]*B[k][j]5:endfor6:endfor7:endfor是否OK？MapReduce（3）–想想办法：我拆Cm=AmⅹBM台服务器并行计算，时间降低为1/M第6页CABC1CMCmA1AmAM=ⅹMapReduce（4）–想想办法：我再拆Cm,n=AmⅹBnMⅹM台服务器并行计算，时间降低为1/M2第7页CABCm,1A1AmAM=ⅹC1,1CM,1B1BmBMMapReduce（5）–分而治之分而治之DivideandConquer一个大的计算任务分解为若干小计算任务子任务计算结果合并后获得最终结果第8页计算任务子任务子任务子任务…计算结果DivideConquerMapReduce（6）–MapReduce来源编程模型：1956年JohnMcCarthy（图灵奖获得者）提出的Lisp语言中的Map/Reduce方法Map输入是一个函数和n个列表，输出是一个新的列表，列表中的元素是将输入函数作用在n个输入列表中每个对应元素获得的计算结果。Reduce输入是一个函数和一个列表，输出是将函数依次作用于列表的每个元素后获得的计算结果第9页(map'vector#*#(12345)#(54321)->#(58985)(reduce#'+#(58985))->35Lisp中的Map和Reduce操作MapReduce（7）–原理第10页Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/MapReduce（8）–运行机制主控程序（Master）：将Map和Reduce分配到合适的工作机上工作机（Worker）：执行Map或Reduce任务第11页MapReduce（9）–不仅是编程模型让程序员在使用MapReduce时面对以下细节问题？大数据如何分割为小数据块？如何调度计算任务并分配和调度map和reduce任务节点？如何在任务节点间交换数据？如何同步任务？相互依赖的任务是否执行完成？任务节点失效时该如何处理？NO!Google的MapReduce是一个完整的计算框架程序员只需要编写少量的程序实现应用层逻辑第12页MapReduce（10）–WordCount#include"mapreduce/mapreduce.h"classWordCounter:publicMapper{public:virtualvoidMap(constMapInput&input){conststring&text=input.value();constintn=text.size();for(inti=0;i<n;){while((i<n)&&isspace(text[i]))i++;intstart=i;while((i<n)&&!isspace(text[i]))i++;if(start<i)Emit(text.substr(start,i-start),"1");}}};REGISTER_MAPPER(WordCounter);第13页classAdder:publicReducer{virtualvoidReduce(ReduceInput*input){int64value=0;while(!input->done()){value+=StringToInt(input->value());input->NextValue();}Emit(IntToString(value));}};REGISTER_REDUCER(Adder);intmain(intargc,char**argv){ParseCommandLineFlags(argc,argv);MapReduceSpecificationspec;for(inti=1;i<argc;i++){MapReduceInput*input=spec.add_input();input->set_format("text");input->set_filepattern(argv[i]);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);MapReduceResultresult;if(!MapReduce(spec,&result))abort();return0;}Google三大法宝之二：GFS第14页GFS（1）–简介GFS–GoogleFileSystem，Google自有的分布式文件系统为什么需要GFS？已有多种分布式文件系统（NFS、AFS、DFS、…）Google特有的环境与负载需要第15页GFS（2）–Google的数据和计算Google处理的主要数据爬取的网页网站访问日志其他相对独立的数据数据计算的期望结果词频统计倒排索引网页文档的链接图网站页面数量统计特点单个计算简单数量庞大数据相对独立第16页GFS（3）–回顾海量数据的文件存储所需要解决的关键性问题：大容量高吞吐量容错计算第17页GFS（4）–大容量用集群方式提升系统整体容量第18页Google的第一台服务器（1998）IntelCPU+IDE硬盘xGFS（5）–高吞吐量Google处理的数据特点抓取网页并存储：顺序写入，极少发生随机写的情况分析网页内容：文件写入后，只会发生读的操作，不会再修改GFS实现高吞吐量的两个关键点：顺序写入，顺序读取，避免随机读写数据以远大于操作系统文件块的基本单元进行存储（64MBvs.512B）文件传输效率公式第19页西数80GSATA硬盘随机读558.2GFS（6）–容错大量廉价PC组件构成的集群作为硬件基础，单节点故障率较高第20页Google的第一台服务器（1998）IntelCPU+IDE硬盘集群多节点数据冗余存储xGFS（7）–计算数据靠近计算存储节点与工作机尽量处于同一节点机架感知：尽量选择最近的数据存储节点读取数据第21页GFS（8）–系统架构第22页客户端（Client）GFS提供给上层应用使用的一组接口库上层应用通过调用接口库中的接口实现GFS系统中的文件管理适合自身应用的简单接口主控节点（Master）管理节点唯一性保存元数据调配块服务器块服务器（ChunkServer）存储数据块（Chunk）多个固定块大小（默认64MB）数据库多节点冗余备份GFS（9）–读数据流程第23页计算索引：客户端将应用提供的文件名和字节偏移通过固定文件块大小进行计算后获得块索引传递索引：客户端将文件名称和块索引发送给主控节点返回位置：主控节点将用于访问文件块的块句柄和文件块所在的块服务器位置返回给客户端访问数据：客户端将位置信息进行缓存，并访问离自己距离最近的块服务器返回数据：被访问的块服务器将数据返回给客户端①②③④⑤Google三大法宝之三：BigTable第24页BigTable（1）–简单搜索框背后的复杂工作Crawler从URL服务器提取地址进行遍历查找获取文档docs,建立文档docIDs,进行分析、压缩存储到文档数据库索引器为docs建立顺排索引和倒排索引索引数据存储到集群中第25页建立索引响应请求对请求进行预处理，包括拼写检查、附加广告等GWS向索引服务器发送查询关键字索引服务器根据关键字查找匹配文档并向GWS返回docIDsGWS将docIDs传给文档服务器，获得文档GWS将查询结果文档以HTML形式返回给用户网页链接关系等结构化信息，要从页面中提取出来进行存储，用于计算BigTable（2）–RDBMS？GFS的局限性：文件系统，不适合结构化数据的存储和访问结构化数据？使用DB2、SQLServer、MySQL之类的数据库系统？非也！因为：存储数据的多样性与复杂性：URL、网页内容、用户数据等海量的处理请求成本与控制力BigTable的目标：适应各种不同类型的数据和应用随时增加和减少处理节点的可扩展性和自动平衡能力PB级数据环境下的高吞吐量和高并发（百万级TPS）连续服务的高可用性和容错性架构与使用的简洁性第26页BigTable（3）–数据模型BigTable：是一个经过排序后的分布式的、稀疏的、多维映射表分布式：数据是分布式存储的稀疏：一个表里不同的行，列可能差异很大多维映射表：数据索引由行关键字（RowKey）、列关键字（ColumnKey）和时间戳（TimeStamp）三个维度构成数据以键/值映射的形式组织第27页(row:string,column:string,time:int64)→stringBigTable（4）–示例网站页面内容及其中超链接的解析t3、t5、t6三个时间点抓取的网页内容存储在contents列中有两个网页包含了到网页的链接，分别是位于页面的超链接文字CNN，和位于my.look.ca页面的超链接文字CNN.com第28页BigTable（5）–展开表第29页行数行关键字版本列族：contents列族：anchor限定词：限定词：my.look.ca1com.bbc.wwwt2

t1<html>a1</html>

2n.wwwt7

“CNN”t6

“CNN.com”t5<html>d4</html>

t4<html>c3</html>

t3<html>b2</html>

BigTable（6）–面向列的存