《云计算与数据挖掘.ppt》由会员分享，可在线阅读，更多相关《云计算与数据挖掘.ppt（116页珍藏版）》请在三一办公上搜索。
1、云计算与数据挖掘,刘鹏 中国云计算：http:/中国网格：http:/,内 容 提 纲,云计算概念与现状,云计算的起源,云计算发展的驱动因素,云计算的定义,云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务。,云计算技术体系结构,Google云计算关键技术,Google文件系统GFS(Google File System)并行数据处理MapReduce结构化数据表BigTable分布式锁管理Chubby,微软的节能措施,Google云计算原理,分布式文件系统GFSGoogle File System,12,Google
2、需要一个支持海量存储的文件系统购置昂贵的分布式文件系统与硬件？,Google设计GFS的动机,是否可以在一堆廉价且不可靠的硬件上构建可靠的分布式文件系统？,13,为什么不使用当时现存的文件系统？Google所面临的问题与众不同不同的工作负载，不同的设计优先级（廉价、不可靠的硬件）需要设计与Google应用和负载相符的文件系统,Google设计GFS的动机,14,GFS的假设与目标,硬件出错是正常而非异常系统应当由大量廉价、易损的硬件组成必须保持文件系统整体的可靠性主要负载是流数据读写主要用于程序处理批量数据，而非与用户的交互或随机读写数据写主要是“追加写”，“插入写”非常少需要存储大尺寸的文件
3、存储的文件尺寸可能是GB或TB量级，而且应当能支持存储成千上万的大尺寸文件,15,将文件划分为若干块（Chunk）存储每个块固定大小（64M）通过冗余来提高可靠性每个数据块至少在3个数据块服务器上冗余数据块损坏概率？通过单个master来协调数据访问、元数据存储结构简单，容易保持元数据一致性无缓存Why?,GFS的设计思路,16,单一Master,若干ChunkServer,GFS的架构,GFS的架构有什么问题吗？,17,18,分布式系统设计告诉我们：这是单点故障这是性能瓶颈GFS的解决办法单点故障问题,单一Master问题,采用多个（如3个）影子Master节点进行热备，一旦主节点损坏，立刻
4、选举一个新的主节点服务,19,GFS的解决办法性能瓶颈问题,单一Master问题,尽可能减少数据存取中Master的参与程度,不使用Master读取数据，仅用于保存元数据,客户端缓存元数据,采用大尺寸的数据块（64M）,数据修改顺序交由Primary Chunk Server完成,Simple,and good enough!,20,存储元数据文件系统目录管理与加锁与ChunkServer进行周期性通信发送指令，搜集状态，跟踪数据块的完好性数据块创建、复制及负载均衡对ChunkServer的空间使用和访问速度进行负载均衡，平滑数据存储和访问请求的负载对数据块进行复制、分散到ChunkServe
5、r上一旦数据块冗余数小于最低数，就发起复制操作,Master节点的任务,21,垃圾回收在日志中记录删除操作，并将文件改名隐藏缓慢地回收隐藏文件与传统文件删除相比更简单、更安全陈旧数据块删除探测陈旧的数据块，并删除,Master节点的任务,22,采用中心服务器模式可以方便地增加Chunk ServerMaster掌握系统内所有Chunk Server的情况，方便进行负载均衡不存在元数据的一致性问题,GFS架构的特点,23,不缓存数据GFS的文件操作大部分是流式读写，不存在大量的重复读写，使用Cache对性能提高不大Chunk Server上的数据存取使用本地文件系统，如果某个Chunk读取频繁，
6、文件系统具有Cache从可行性看，Cache与实际数据的一致性维护也极其复杂,GFS架构的特点,?,24,在用户态下实现直接利用Chunk Server的文件系统存取Chunk，实现简单用户态应用调试较为简单，利于开发用户态的GFS不会影响Chunk Server的稳定性提供专用的访问接口未提供标准的POSIX访问接口降低GFS的实现复杂度,GFS架构的特点,25,GFS的容错方法,GFS的容错机制Chunk Server容错每个Chunk有多个存储副本（通常是3个），分别存储于不通的服务器上每个Chunk又划分为若干Block（64KB），每个Block对应一个32bit的校验码，保证数据正
7、确（若某个Block错误，则转移至其他Chunk副本）,26,GFS的性能,27,Google云计算原理,并行数据处理模型MapReduce,摩尔定律集成电路芯片上所集成的电路的数目，每隔18个月就翻一番，同时性能也提升一倍,并行计算基础,Gordon Moore,“免费的性能大餐”？Andy given,and Bill taken away软件算法、数据结构似乎不再重要，因为处理器性能不断提升,并行计算基础,免费的午餐已经结束！,Intel,Microsoft,摩尔定律正在走向终结单芯片容纳晶体管的增加，对制造工艺提出要求CPU制造18nm技术，电子泄漏问题CPU主频已达3GHz时代，难以
8、继续提高散热问题（发热太大，且难以驱散）功耗太高,并行计算基础,未来的发展：多核,在多核时代生存，必须考虑并发问题不存在解决多核编程问题的银弹，不存在可以简单地将并发编程问题化解掉的工具，开发高性能的并行程序必须要求开发者从根本上改变其编程方法从某种意义上来说，这不仅仅是要改变50年来顺序程序设计的工艺传统，而且是要改变数百万年来人类顺序化思考问题的习惯,并行计算基础,Herb Sutter,串行编程早期的计算里，程序一般是被串行执行的程序是指令的序列，在单处理器的机器里，程序从开始到结束，这些指令一条接一条的执行并行编程一道处理可以被划分为几部分,然后它们可以并发地执行各部分的指令分别在不同
9、的CPU上同时运行，这些CPU可以存在于单台机器中,也可以存在于多台机器上,它们通过连接起来共同运作,并行计算基础,什么样的问题适合并行计算？斐波那契序列(Fibonacci)的计算？,并行计算基础,什么样的问题适合并行计算？如果有大量结构一致的数据要处理，且数据可以分解成相同大小的部分，那我们就可以设法使这道处理变成并行,并行计算基础,计算问题简单，但求解困难待处理数据量巨大（PB级），只有分布在成百上千个节点上并行计算才能在可接受的时间内完成如何进行并行分布式计算？如何分发待处理数据？如何处理分布式计算中的错误？,为什么需要MapReduce？,简单的问题，计算并不简单！,为什么需要Map
10、Reduce？,Google MapReduce架构设计师Jeffrey Dean,Jeffery Dean设计一个新的抽象模型，使我们只要执行的简单计算，而将并行化、容错、数据分布、负载均衡的等杂乱细节放在一个库里，使并行编程时不必关心它们这就是MapReduce,一个软件架构，是一种处理海量数据的并行编程模式用于大规模数据集（通常大于1TB）的并行运算MapReduce实现了Map和Reduce两个功能Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集Reduce对结果集进行分类和归纳Map()和 Reduce()两个函数可能会并行运行，即使不是在同一的系统的同一时刻
11、,MapReduce,MapReduce示例：单词计数,案例：单词记数问题(Word Count)给定一个巨大的文本（如1TB），如何计算单词出现的数目？,MapReduce示例：单词计数,使用MapReduce求解该问题定义Map和Reduce函数,MapReduce示例：单词计数,使用MapReduce求解该问题Step 1:自动对文本进行分割，形成初始的对,MapReduce示例：单词计数,使用MapReduce求解该问题Step 2:在分割之后的每一对进行用户定义的Map进行处理，再生成新的对,MapReduce示例：单词计数,使用MapReduce求解该问题Step 3:对输出的结果
12、集归拢、排序(系统自动完成）,MapReduce示例：单词计数,使用MapReduce求解该问题Step 4:通过Reduce操作生成最后结果,Google MapReduce执行流程,源文件：GFSMap处理结果：本地存储Reduce处理结果：GFS日志：GFS,文件存储位置,思考,Google MapReduce计算架构有什么问题？,Worker故障Master 周期性的ping每个worker。如果master在一个确定的时间段内没有收到worker返回的信息，那么它将把这个worker标记成失效重新执行该节点上已经执行或尚未执行的Map任务重新执行该节点上未完成的Reduce任务，已完
13、成的不再执行Master故障定期写入检查点数据从检查点恢复,MapReduce的容错,WHY？,任务备份机制慢的workers 会严重地拖延整个执行完成的时间 由于其他的任务占用了资源 磁盘损坏解决方案:在临近结束的时候，启动多个进程来执行尚未完成的任务谁先完成，就算谁可以十分显著地提高执行效率,MapReduce的优化,本地处理Master 调度策略:向GFS询问获得输入文件blocks副本的位置信息Map tasks 的输入数据通常按 64MB来划分(GFS block 大小)按照blocks所在的机器或机器所在机架的范围进行调度效果绝大部分机器从本地读取文件作为输入，节省大量带宽,Map
14、Reduce的优化,跳过有问题的记录一些特定的输入数据常导致Map/Reduce无法运行最好的解决方法是调试或者修改不一定可行 可能需要第三方库或源码在每个worker里运行一个信号处理程序，捕获map或reduce任务崩溃时发出的信号，一旦捕获，就会向master报告，同时报告输入记录的编号信息。如果master看到一条记录有两次崩溃信息，那么就会对该记录进行标记，下次运行的时候，跳过该记录,MapReduce的优化,“实践是检验真理的唯一标准”,实践证明，MapReduce是出色的分布式计算模型Google宣布，其对分布于1000台计算机上的1TB数据进行排序仅仅需要68s对4000台计算
15、机上的1PB数据进行排序处理仅需要6小时2分钟（每次测试至少会损坏1块硬盘）在08年1月份，Google MapReduce平均每天的数据处理量是20PB，相当于美国国会图书馆当年5月份存档网络数据的240倍,Goolge的云计算,分布式数据表BigTable,53,BigTable,为什么需要设计BigTable？Google需要存储的数据种类繁多网页，地图数据，邮件如何使用统一的方式存储各类数据？海量的服务请求如何快速地从海量信息中寻找需要的数据？BigTable：基于GFS和Chubby的分布式存储系统对数据进行结构化存储和管理与GFS的联系,54,数据存储可靠性高速数据检索与读取存储海
16、量的记录（若干TB）可以保存记录的多个版本,Google的需求,55,与写操作相比，数据记录读操作占绝大多数工作负载单个节点故障损坏是常见的磁盘是廉价的可以不提供标准接口Google既能控制数据库设计，又能进行应用系统设计,假设,56,具有广泛的适应性支持Google系列产品的存储需求具有很强的可扩展性根据需要随时加入或撤销服务器应对不断增多的访问请求高可用性单个节点易损，但要确保几乎所有的情况下系统都可用简单性简单的底层系统可减少系统出错概率，为上层开发带来便利,设计目标,57,总体上，与关系数据库中的表类似,逻辑视图,58,关系数据库中的表是什么样的？有什么特征？关系数据库中的表设计需要遵
17、循什么原则？,行每行数据有一个可排序的关键字和任意列项字符串、整数、二进制串甚至可串行化的结构都可以作为行键表按照行键的“逐字节排序”顺序对行进行有序化处理表内数据非常稀疏，不同的行的列的数完全目可以大不相同URL是较为常见的行键，存储时需要倒排统一地址域的网页连续存储，便于查找、分析和压缩,数据模型,59,列特定含义的数据的集合，如图片、链接等可将多个列归并为一组，称为族（family）采用 族:限定词 的语法规则进行定义fileattr:owning_group”,“fileattr:owning_user”,etc同一个族的数据被压缩在一起保存族是必须的，是BigTable中访问控制的基
18、本单元,数据模型,60,时间戳保存不同时期的数据，如“网页快照”“A big table”表中的列可以不受限制地增长表中的数据几乎可以无限地增加,数据模型,通过(row,col,timestamp)查询通过(row,col,MOST_RECENT)查询,61,无数据校验每行都可存储任意数目的列BigTable不对列的最少数目进行约束任意类型的数据均可存储BigTable将所有数据均看作为字符串数据的有效性校验由构建于其上的应用系统完成一致性针对同一行的多个操作可以分组合并不支持对多行进行修改的操作符,数据模型,62,物理视图,63,逻辑上的“表”被划分为若干子表（Tablet）每个Tablet
19、由多个SSTable文件组成SSTable文件存储在GFS之上每个子表存储了table的一部分行元数据：起始行键、终止行键如果子表体积超过了阈值（如200M），则进行分割,物理视图,64,体系结构,65,为每个子表服务器分配子表，对外提供服务与GFS垃圾回收进行交互，收回废弃的SSTable探测子表服务器的故障与恢复负载均衡,主节点的职责,有效缓解单点故障,66,BigTable小结,67,Google云计算架构中GFS、MapReduce和BigTable中是否存在集群节点复用的情况？如何复用？节点复用的好处有哪些？Google云计算架构的设计对你有哪些启发？有哪些收获？,综合讨论,中移动大
20、云平台Big Cloud,BC-PDM分布式数据挖掘系统,2007年3月，确定了大云(Big Cloud)计划，即中国移动研究院为打造中国移动云计算基础设施而实施的关键技术研究及原型系统开发计划。2007年7月，利用闲置的15台PC服务器，基于开源软件搭建了海量数据处理试验平台，并成功运行搜索引擎软件。2008年10月，建立256节点的大规模运算实验室，并运行数据挖掘工具和相关应用。2009年9月，Big Cloud 0.5版本在中国移动研究院内部发布试用。2009年12月，试验平台进一步扩容，达到1000台服务器、5000个CPU、3000TB的存储规模。,“大云”研发大事记,并行数据挖掘工
21、具(BC-PDM)是一套高性能、低成本、高可靠性、高可伸缩性的海量数据处理、分析和挖掘系统。该工具提供海量数据并行ETL和并行挖掘能力，支持企业的BI应用和精准营销;提供业务逻辑复杂的SQL 能力，支持海量数据的清洗、转换、关联、汇总等操作，支持生成企业报表、KPI、挖掘等应用;提供基于Web的SaaS服务模式，降低企业IT系统投资。,大云数据挖掘系统(BC-PDM),登录后界面,工作流画布（Knowledge Flow Layout）,job监控框(Job monitor),数据查看与管理,预览数据,创建工作流,配置工作流,运行工作流,查看工作流结果,文本,ROC图,Lift图,工作流调度情
22、况,BC-PDM的数据装载和导出,数据加载是将分布式文件系统（DFS）上的没有元数据文件的数据生成元数据文件，或对数据进行断行、空行等初步处理，或作为工作流运行的起始组件。数据导出是将处理后的数据文件转换成指定的格式或分隔符，数据仍然保存在DFS上。,数据加载（导入）,数据加载（导入）,导入头文件,头文件举例,start_time,date,开始时间imsi,VARCHAR(10),IMSIcalling,VARCHAR(10),用户号码user_ip,VARCHAR(10),用户IP地址APN,VARCHAR(10),访问方式IMEI,VARCHAR(10),终端标识号rat,int,2G/
23、3G网络标识App_type,int,应用类型LAC,VARCHAR(10),xmCell_ID,VARCHAR(10),xmsource_ip,VARCHAR(10),源IP地址dest_ip,VARCHAR(10),目的地址,数据导出,并行数据处理(ETL),ETL操作可以分为普通ETL和链式ETL。,普通ETL和链式ETL分别又细分为：清洗类、转换类、集成类、计算类、抽样类、集合类、更新类、及其它类8大类。,清洗类-数据类型检查,根据元数据中各个字段的数据类型，对输入文件逐条记录地检查每个字段的数据是否与元数据中的类型相符合，支持多种日期类型。对发现不满足数据类型的记录，应用异常数据处理
24、规则。并在有效性验证后提供一个验证报告，包括丢弃了多少数据、对数据进行了什么处理等信息。,转换类-caseWhen,根据用户输入的条件，将指定字段的值进行转换，类似SQL的case when。用户指定转换的字段与转换规则。支持对多字段进行转换，支持对某个字段多个转换规则，支持default规则。可以配置转换生成列的元数据信息。,1 并行分类算法Classifiers4MR分类功能应以用户提供的历史消费清单作为训练数据，这些数据中有一个属性作为分类属性，且每条记录已标明分类属性的值。分类算法应提供两方面基本功能：（1）学习分类模型：从训练集数据中发现潜在的分类模型，并以特定方式表达（2）预测：对
25、用户新提供的数据集，依据分类模型预测出所属类别并行分类算法包括：EmptyClassifier4M、C45决策树、CBC分类、CBR分类、K近邻、朴素贝叶斯、层次C45决策树、线性回归分类、神经网络算法。,BC-PDM挖掘算法,神经网络算法,把整个神经网络的神经元划分成不同层次，对同层次内的不同神经元进行并行参数计算，并通过统一调度和精度控制对神经元进行快速的并行化训练。训练完毕后，对于每一个输入，通过并行化神经网络快速地得到输出,2 并行聚类算法Clusterers4MR 聚类算法应对用户提供的全体数据集，按照一定的聚类原则，自动聚成几簇。每个簇内的数据应具有很高的相似性。应提供的功能包括：
26、（1）自动聚类：将数据集形成簇模型；（2）预测：依据形成的簇模型，对新数据判定所属的簇。并行聚类规则算法包括：k均值算法、Clara聚类算法、DBScan聚类算法。,3 并行关联规则算法Associations4MR关联规则挖掘工具以选定的客户消费记录全集作为输入，分析消费记录中各消费项间依赖关系，产生规则描述各消费项之间同时出现的规律。关联规则算法包括：并行PApriori算法、并行PFPgrowth算法、并行PAwfits算、时序关联规则。,时序关联规则挖掘算法主要可以用于发现交易序列中的频繁模式。因为交易序列具有时间性，因此各数据项集之间存在时间上的先后关系，“买A又买B的顾客往往还会买C”的规则转变成了“买A后又买B的顾客往往会接下来再买C”或者“买B后又买A的顾客往往会接下来再买C”，在时序关联规则算法中，这后两者是不同的两个关联规则。,时序关联规则算法,聚类算法结果展示,PKmeas算法处理dm_call数据后结果,决策树算法结果展示,进一步了解云计算,http:/,谢 谢！,刘鹏 中国云计算：http:/中国网格：http:/,
