支撑技术的教案

支撑技术的教案第1页/共88页数据库技术的演化网状数据库和层次数据库关系数据库和结构化查询语言面向对象数据库决策支持系统和数据仓库NoSQL技术非关系型的数据库。随着互联网web2.0网站的兴起，传统的关系数据库在应付web2.0网站，特别是超大规模和高并发类型的web2.0纯动态网站已经显得力不从心.每秒的访问量可能是上万次(10K):传统的关系型数据库mysqloracle每秒进行10K次数据查询还可以勉强应付，但是如果是每秒10K次读写数据库，因为数据库的数据都是卸载磁盘中，所以磁盘IO也是支撑不住每秒10K的读写。对关系型数据库进行升级和扩展，往往要进行停机维护7.1数据库系统第2页/共88页数据管理和后键盘时代第3页/共88页数据库的研究者和制造商们，已经看到这些事实变化，正在不断地丰富、完善现有数据库的功能和性能。海量：全球的数据量正以指数趋势迅猛增长，据保守估计，目前全球每年至少产生15亿TB的新数据。共享：互联网和通讯设备的普及，使得人们能够享受他人提供数据所带来的好处，因此，数据库之间也建立起越来越密切的联系。多样化：现在，数据已不再是关系模型下纯粹的结构化文本数据，图片、音频、视频乃至非结构化的文档，都涌入到应用中。第4页/共88页数据洪水和全球性的数据爆炸

据保守估计，目前全球每年至少将产生几十亿TB的新数据。但是，在数据管理中，却有一样东西是基本维持不变的，那就是人的注意力和人能够用在计算方面的时间。每个人总的寿命以及每一天用在工作中的时间，在近千年中几乎没有太大的改变。

第5页/共88页NoSQL系统NoSQL是采用key/value的结构来存储数据，而且大多数的NoSQL采用内存来存储数据，一段时间后把数据同步到磁盘中；由于使用内存保存数据很好地解决了高并发读写的问题；其次NoSQL提供了根据key值进行横向分表(比如：用户id，每2000w数据放到一台数据库服务器中的一张用户表中)；同时实现了主从数据库互备，这样可以让数据库的动态迁移变得简单，让数据库服务器的横向扩展变得容易了。第6页/共88页物联网中主要数据管理问题数据质量控制数据融合与数据集成数据查询复杂事件处理数据存储和数据压缩数据访问控制和数据隐私保护第7页/共88页7.2海量存储技术7.2.1存储系统的发展概况计算与存储，是计算机的两大主题。对此，IBM、EMC、SUN和Veritas等IT企业给出了三条理由：数据呈爆炸式增长。我们所处的时代，是一个知识爆炸、信息爆炸的时代。随着Internet及各种新的应用如电子商务、电子政务等的发展，信息量不断增加，使得数据存储的需求急剧增长。调查显示，全球每年存储设备（对应于不同的应用环境）增长约1～10倍，成为计算机硬件系统购买成本中比例最大的部分。网络时代的数据太多，需要海量存储系统。数据极端重要。数据就是业务，就是生命线。例如，对银行来说，数据是最大的资产，关系到它的命脉。服务器坏了可以进行更换，数据丢失则是无可挽回的灾难。网络需求快速增加。媒体资源需要转换成数字形式后才能通过网络共享，这些数字资源不仅占用了大量存储空间，也增加了管理费用（每TB存储的管理成本，是购置成本的7～10倍）。应用成本，已经成为新的存储瓶颈，解决这一问题的最好办法，就是把存储系统从服务器中独立出来，建立新的网络存储系统和使用模式第8页/共88页存储系统的演化直接附加存储(Direct-AttachedStorage,DAS)将存储系统通过缆线直接与服务器或工作站相连一般包括多个硬盘驱动器，与主机总线适配器通过电缆或光纤在存储设备和主机总线适配器之间不存在其他网络设备实现了计算机内存储到存储子系统的跨越第9页/共88页网络附加存储(NetworkAttachedStorage,NAS)文件级的计算机数据存储架构计算机连接到一个仅为其它设备提供基于文件级数据存储服务的网络第10页/共88页NAS与DAS的区别DAS是对已有服务器的简单扩展，并没有真正实现网络互联。NAS则是将网络作为存储实体，更容易实现文件级别的共享。NAS性能上比DAS有所增强第11页/共88页存储区域网络(StorageAreaNetwork,SAN)通过网络方式连接存储设备和应用服务器的存储架构由服务器、存储设备和SAN连接设备组成SAN的特点存储共享支持服务器从SAN直接启动第12页/共88页存储系统的演化：DAS（左）、NAS（中）和SAN（右）

DAS管理容易，结构简单；集中式体系结构，不能满足大规模数据访问的需求；存储资源利用率低，资源共享能力差，造成“信息孤岛”。NAS网络的存储实体，容易实现文件级别共享；性能严重依赖于网络流量，用户数过多，读写过频繁时性能受限。SAN存储管理简化，存储容量利用率提高；无直接文件级别的访问能力，但可在SAN基础上建立文件系统。第13页/共88页三种网络存储结构的比较第14页/共88页物联网的三个层次

第15页/共88页物联网+互联网+云计算

第16页/共88页物联网中数据的特点将物联网所连接的物体或实体，统一看作物理节点，按照连接的物理节点的多少，可将物联网划分成4种类型：小规模系统（100个节点左右）。例如，一套智能住宅内，相互连接的照明、空调、炊具等家用电器和设备；一套身体传感器网络内，连接在一起的心电监护仪、血压监护仪、呼吸监护仪、体温监护仪和位置监护仪等。中规模系统（上万个节点左右）。如一栋智能建筑，建筑物内的各种照明、消防和防盗系统；一个生态环境监控区域内的空气质量监测仪、水质监测仪，以及被观察的植物和动物状态等。大规模系统（上百万个节点左右）。如一个城市的智能交通系统，涉及到交通控制系统、公路监测系统、桥梁监测系统、隧道监测系统、以及铁路和民航系统等；智能电网系统，包括发电系统、输电系统、配电系统和最终用电设备。超大规模系统（百万个节点以上）。如一个大型的智能城市，甚至全国性、全球性系统，包括全球流行病监测网、地球观测系统和全球性物流系统等。第17页/共88页海量运算--CPS系统CPS(CyberPhysicalSystems)是一个综合计算、网络和物理环境的多维复杂系统，通过3C（Computation、Communication、Control）技术的有机融合与深度协作，实现大型工程系统的实时感知、动态控制和信息服务。CPS实现计算、通信与物理系统的一体化设计，可使系统更加可靠、高效、实时协同，具有重要而广泛的应用前景。CPS将来无处不在的环境感知、嵌入式计算、网络通信和网络控制等系统工程，使物理系统具有计算、通信、精确控制、远程协作和自治功能。它注重计算资源与物理资源的紧密结合与协调，主要用于一些智能系统上如机器人，智能导航等。第18页/共88页数据中心的起源与发展大型机微型机大规模数据中心(MegaDataCenter)第19页/共88页数据中心的起源与发展大规模数据中心已经得到推广第20页/共88页数据中心资源管理的基本要求。这些建议，来自于IT和服务行业中许多数据中心的设计、操作经验：使普通用户满意：数据中心的设计，应该至少为广大用户提供30年的优质服务。可控的信息流：信息流应该可以流水线化，持续的服务和高可用性，是主要目标。多用户管理：系统必须能够支持数据中心的所有功能，包括流量、数据库更新和服务器维护。适应数据库增长的可扩展性：随着负载增加，系统也随之扩充，存储、处理、I/O、电源和冷却子系统等，也应具有可扩展性。虚拟化基础设施的可靠性：故障切换、容错和虚拟机实时迁移应该结合起来，使得关键应用可以从故障、灾难中尽快恢复。用户和提供商的低成本：减低建构在数据中心之上的云系统的用户和提供商的成本，包括操作成本。安全防范和数据保护：必须部署数据隐私和安全防范机制，来保护数据中心不受网络攻击和系统中断的影响，在用户误用或网络攻击中，还能保持数据的一致性。绿色信息技术：在设计与操作当前和未来数据中心时，非常需要节约能耗与提升效能。第21页/共88页什么是数据中心？维基百科：“数据中心是一整套复杂的设施。它不仅仅包括计算机系统和其它与之配套的设备（例如通信和存储系统），还包含冗余的数据通信连接、环境控制设备、监控设备以及各种安全装置。”Google：“多功能的建筑物，能容纳多个服务器以及通信设备。这些设备被放置在一起是因为它们具有相同的对环境的要求以及物理安全上的需求，并且这样放置便于维护。”第22页/共88页数据中心标准数据中心建设者面对的难题如何规划一个新的数据中心？怎样对数据中心进行升级？数据中心的标准对相关经验进行了总结ANSI/TIA/EIA-942（简称TIA-942）：数据中心标准电信产业协会（TIA）提出美国国家标准学会（ANSI）批准第23页/共88页数据中心标准：TIA-942选址：需要考虑多方面因素建设和运营成本应用需求政策优惠…布局：按功能区域划分功能区域组成第24页/共88页数据中心标准：TIA-942（续）TIA-942还对缆线系统，可靠性分级，能源系统和降温系统等做了规定。缆线系统规格如何放置缆线能源系统外部电力供应电池组发电机降温系统降温设备架空地板冷通道与热通道第25页/共88页典型数据中心：Google数据中心简介全球共建有近40个大规模数据中心单个数据中心需要至少50兆瓦功率，约等于一个小型城市所有家庭的用电量独特的硬件设备：定制的以太网交换机、能源系统等自行研发的软件技术：GoogleFileSystem、MapReduce、BigTable等谷歌在俄勒冈州数据中心第26页/共88页GoogleFileSystemGFS的设计观念组件失效不再被认为是意外，而是被看做正常的现象GFS的文件非常巨大对文件的操作具有特定的模式应用程序和文件系统API的协同设计提高了整个系统的灵活性第27页/共88页GoogleFileSystemGFS的设计架构一个GFS集群包含一个主服务器和多个块服务器，并被多个客户端访问。文件分成固定大小的“块”。每个块在创建时都由主服务器分配一个固定不变的64位句柄唯一标识。块服务器把块作为Linux文件存储在本地磁盘上，并根据指定的块句柄和字节范围对数据块进行读写操作。第28页/共88页GoogleFileSystemGFS的设计架构（续）主服务器维护所有文件系统的元数据，包括名字空间、访问控制信息、文件到块的映射信息以及块当前的位置。此外，主服务器还控制其它系统级的活动。主服务器周期性地与块服务器通信，以下达指令和收集状态。GFS客户端代码被嵌入到每个应用中。它实现了文件系统API，实现主服务器与块服务器的通信从而代表应用实现读写操作。客户端与服务器交互从而实现元数据操作，但所有的数据操作都通过直接与块服务器交互而完成。第29页/共88页MapReduceMapReduce是一种针对超大规模数据集的编程模型和系统用MapReduce开发出的程序可在大量商用计算机集群上并行执行、处理计算机的失效以及调度计算机间的通信MapReduce的基本思想用户写的两个程序：Map和Reduce一个在计算机集群上执行多个程序实例的框架MapReduce程序的执行过程第30页/共88页MapReduce框架第31页/共88页BigTableBigTable是一种用来在海量数据规模下（例如包含以PB为单位的数据量和数千台廉价计算机的应用）管理结构化数据的分布式存储系统。应用Google地球网页索引RSS阅读器每个BigTable都是一个稀疏的、分布式的多维有序图，按行键值、列键值和时间戳建立索引第32页/共88页Bigtable基本架构第33页/共88页典型数据中心：Hadoop什么是Hadoop？Apache开源组织的一个分布式计算开源框架用于在大型集群的廉价服务器设备上运行数据密集型分布式应用程序在早期实际上是Google文件系统与MapReduce分布式计算框架及相关IT基础服务的开源实现Hadoop包括多个子项目HDFS、MapReduce、HBase、Chukwa、Pig、ZooKeeper等Hadoop的最核心的设计：HDFS和MapReduce.HDFS为海量的数据提供了存储，则MapReduce为海量的数据提供了计算第34页/共88页HDFSHadoopDistributedFileSystem第35页/共88页数据中心的研究热点2006年Google在数据中心项目上的花费为19亿美元，而2007年该项支出增加到24亿美元。Google在俄勒冈州的数据中心有近100兆瓦的功率，满负荷运行时消耗的电力基本上和纽卡斯尔（Newcastle）一个城市所有家庭的用电量加起来一样多。研究热点：如何在保证服务质量的前提下降低成本？第36页/共88页数据中心的成本构成基础设施部分包括能源系统、降温系统、各种防火设备、安保设备等。降低这一部分成本往往涉及到机械设备制造技术或政策优惠等因素，与计算机学科的关联程度相对较低。我们分别从服务器，网络设备，能源三个方面对造成高成本的原因和目前的解决方法进行简要介绍。第37页/共88页服务器成本服务器的实际利用效率较低分配到各服务器的应用不能完全利用某些组件对应用需求的预测比较难，无法做到按需分配为了提高系统的可靠性，一般都留有冗余设备提高服务器利用率的关键在于及时应对需求的动态变化第38页/共88页网络设备成本主要来源交换机、路由器、负载均衡设备传统的数据中心使用树形结构，核心交换机和路由器构成流量瓶颈，且造价昂贵研究热点：新的数据中心网络结构以交换机为中心的多层树形结构：例如Fat-Tree以服务器为中心的互联结构：例如DCell第39页/共88页能源成本研究热点降低服务器工作能耗降低同等性能设备能耗提高同等能耗设备性能可调整负载的服务器减少降温系统能耗精细、精准的温度控制集装箱式模块化数据中心数据中心能耗构成第40页/共88页7.3搜索引擎技术7.3.1搜索引擎概述Web搜索引擎一个能够在合理响应时间内，根据用户的查询关键词，返回一个包含相关信息的结果列表（hitslist）服务的综合体。传统的Web搜索引擎是基于查询关键词的，对于相同的关键词，会得到相同的查询结果。第41页/共88页搜索引擎类型

搜索引擎与全文检索形成了三个不同的类型：全文检索搜索引擎。全文搜索引擎是名副其实的搜索引擎，国外具代表性的有谷歌、雅虎、AllTheweb等，国内著名的有百度、中搜。它们都是通过从互联网上提取的各个网站的信息（以网页文字为主）而建立的数据库，检索与用户查询条件匹配的相关记录，然后，按一定的排列顺序将结果返回给用户，也是目前常规意义上的搜索引擎。目录搜索引擎。目录索引虽然有搜索功能，但严格意义上，算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而己。用户完全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。国外比较著名的目录索引搜索引擎，有雅虎OpenDirectoryProject（DMOZ）、LookSmart等。国内的搜狐、新浪、网易搜索，也都具有这一类功能。元搜索引擎。元搜索引擎在接受用户查询请求时，同时在其它多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎，有Dogpile、Vivisimo等，国内元搜索引擎中具代表性的，有搜星搜索引擎，优客搜索。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile；有的则按自定的规则将结果重新排列组合，如Vivisimo。其他的像新浪、网易、A9等搜索引擎，都是调用其它全文检索搜索引擎，或者在其搜索结果的基础上做了二次开发。第42页/共88页网络爬虫模块：主要功能是通过对Web页面的解析，根据Web页面之间的连接关系抓取这些页面，并储存页面信息交给索引模块处理。索引模块：主要完成对于抓取的数据进行预处理建立关键字索引以便搜索模块输出。搜索模块：对于用户的关键词，根据数据库的索引知识给出合理的搜索结果。Web搜索引擎的结构第43页/共88页Web搜索引擎的工作模式第44页/共88页Web搜索引擎的3个重要问题响应时间：一般来说合理的响应时间在秒这个数量级关键词搜索：得到合理的匹配结果搜索结果排序：如何对海量的结果数据排序搜索引擎的体系结构信息采集索引技术搜索服务第45页/共88页体系结构：信息采集Web搜索引擎的信息采集模块主要功能：Web上收集页面信息，即Web机器人（爬虫）程序基于超文本传输协议（HypertextTransferProtocol,简称HTTP）第46页/共88页体系结构：信息采集典型的基于超文本传输协议的网络应答第47页/共88页网络爬虫程序的工作模式网络爬虫程序根据HTTP协议，发送请求，并通过TCP连接接受服务器的应答。由于Web搜索引擎需要抓取数以亿计的页面，所以建立快速分布式的网络爬虫程序才能满足搜索引擎对性能和服务的要求，其物理实现可能是一组终端。第48页/共88页网络爬虫程序的工作模式爬虫程序物理设备架构图第49页/共88页网络爬虫程序的基础结构首先网络爬虫程序从URL链接库读取一个或多个URL作为初始输入并进行域名解析然后根据域名解析结果（IP）访问Web服务器，建立TCP连接，发送请求，接受应答，储存接受数据，并分析提取链接信息（URL）放入URL连接库里。爬虫程序递归执行该过程直到URL链接库为空。第50页/共88页信息采集优化网络连接优化策略持久性连接

多进程并发设计域名系统的缓存策略：由于网络爬虫程序会频繁调用域名系统，域名系统缓存可提高爬虫程序性能。LRU（LeastRecentlyUsed）算法LFU（LeaseFrequentlyUsed）算法FIFO（First-In,First-Out）算法第51页/共88页网页抓取算法深度优先算法在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接深度抓取页面，直到搜索结束（没有新的URL）。广度优先算法在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接广度抓取页面，抓取下一层的URL直到这一层的URL完全被抓取，直到搜索结束时返回。第52页/共88页网页抓取算法（续）基于内容算法根据关键字、主题文档的相似度和链接文本（Linkedtexts）估计链接值，并确定相应搜索策略的算法。链接文本是包含对URL链接解释说明和内容摘要的文字信息。基于HITS的算法主要思想：在抓取Web页面时，采用Authority/Hub抓取策略。Authority表示该页面被其他页面所引用的次数（页面入度值，in-degreevalue）。Hub表示其他页面引用该页面的次数（页面出度值，out-degreevalue）。第53页/共88页网页抓取算法（续2）PageRank（Google的传奇技术）定义PageRank：我们假设有T1…Tn个页面指向页面A（即引用）。参数d是一个阻尼因子，其取值区间属于(0,1)，我们通常取值为0.85。C(A)定义为指向页面A的其他页面的连接数，页面A的PageRank或PR(A)值可以通过下面的公式得到：注意：PageRank值是Web页面的概率分布表示，所以所有Web页面的PageRank值的和是1。第54页/共88页体系结构：索引技术Web爬虫抓取回来的页面信息，需要放入索引数据库里。索引建立的好坏对于搜索引擎有很大的影响，优秀的索引能够显著的提高搜索引擎系统运行的效率及检索结果的品质。文本分析技术是建立数据索引信息的支撑技术。第55页/共88页索引建立：预处理当Web搜索引擎获得数据信息以后，首先需要对数据进行预处理，如将句子切分成有意义的词汇。由于中文的特殊性在切分句子时会产生二义性，如何合理的切分词汇是一个技术难题。中文分词完全不同于英文分词，英文行文中，单词间以空格分隔；而中文只有字/句/段有明显分隔符，唯独词没有形式上的分隔符存在。第56页/共88页索引建立：倒排文件模型倒排文件（invertedfile），是指一个词汇集合W和一个文档集合D之间对应关系的数据结构。建立倒排文件索引是建立索引数据库的核心工作。索引模块架构第57页/共88页体系结构：搜索服务搜索服务是Web搜索引擎工作流程的最后一步，根据用户提交的查询关键字展开搜索，将匹配结果返回给用户。搜索服务的好坏直接影响Web搜索引擎的用户满意程度。第58页/共88页搜索服务：结果显示接受用户的输入，提交用户搜索请求。根据搜索结果列表合理的展示给用户。在保护隐私的前提下，记录用户使用行为的详细信息，以便提高下次服务的满意度。第59页/共88页搜索服务：网页快照Web上的数据每时每刻都在变化着，所以随时存在着检索到的页面信息已经不存在的可能。Web搜索引擎为了提高服务质量，需要对搜索到的页面信息进行快照，以便在原来页面信息失效的情况下，保证用户能够通过快照功能查看页面。第60页/共88页类GoogleWeb搜索引擎的实例分析*类Google搜索引擎的架构URL服务器Web页面抓取器存储服务器URL解释器排序器PageRank搜索器第61页/共88页类GoogleWeb搜索引擎的实例分析*Google数据仓库的结构第62页/共88页类GoogleWeb搜索引擎的实例分析*查询评估流程解析查询（Query）把单词转化成wordID从每个单词的短桶文档列表开始查找扫描文档列表直到有一个文档匹配了所有的搜索词语计算这个文档对应的查询的评分如果到达短桶的文档列表结尾，从每个单词的全桶(fullbarrel)文档列表开始查找，跳到第4步如果没有到达任何文档列表的结尾，跳到第4步根据评分对匹配的文档排序，然后返回评分最高的k个第63页/共88页7.3.3搜索引擎面临的挑战第64页/共88页7.3.4搜索引擎应对策略多元化搜索质量提高搜索能力加强其他方面个性化搜索与用户需求

第65页/共88页7.4大数据挖掘7.4.1大数据产生背景第66页/共88页大数据

大数据技术的战略意义，不在于掌握庞大的数据信息，而在于对这些含有意义的数据进行专业化处理。如果，把大数据比作一种产业，那么这种产业实现盈利的关键，在于提高对数据的“加工能力”，通过“加工”实现数据的“增值”。中国物联网校企联盟认为，物联网的发展离不开大数据，依靠大数据提供足够有利的资源。第67页/共88页7.4.2大数据的关键问题第68页/共88页大数据全景图

第69页/共88页7.4.3大数据处理技术数据并行处理增量处理技术第70页/共88页7.4.4复杂数据智能分析技术图匹配查询社会网络数据分析第71页/共88页7.4.5数据质量基础理论与关键技术统一的逻辑框架半结构化数据数据质量分布式数据清洗第72页/共88页7.4.6数据挖掘的进展及挑战什么是数据挖掘数据挖掘的进展和趋向物联网数据特性对挖掘的挑战第73页/共88页数据挖掘的著名案例：啤酒尿布

20世纪90年代的美国，沃尔玛的超市管理人员分析销售数据时发现了一个令人难于理解的现象：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中，这种独特的销售现象引起了管理人员的注意，经过后续调查发现，这种现象出现在年轻的父亲身上。父亲在购买尿布的同时，往往会顺便为自己购买啤酒，如果这个年轻的父亲在卖场只能买到两件商品之一，则他很有可能会放弃购物而到另一家商店，直到可以一次同时买到啤酒与尿布为止。沃尔玛开始在卖场尝试将啤酒与尿布摆放在相同的区域，让年轻的父亲可以同时找到这两件商品，并很快地完成购物；而沃尔玛超市也可以让这些客户一次购买两件商品、而不是一件，从而获得了很好的商品销售收入。第74页/共88页数据挖掘视为知识发现过程的一个步骤

第75页/共88页典型的数据挖掘系统结构

第76页/共88页美国TeraGridTeraGrid项目为开放的科学研究建立和部署世界上最大、最全面的分布式基础设施。该项目的开发已持续多年，TeraGrid拥有在9个站点上20万亿次(1015)的计算速度、能够管理和存储1PB(1015字节)数据的数据管理机制、高解析度的可视化环境和网格计算工具包。所有资源将通过迄今为止最快的研究网络带宽——40Gbps的专用网络完整地连接起来。第77页/共88页网格应用虚拟天文台第78页/共88页第79页/共88页第80页/共88页P817.5云计算1.云计算基础云计算（CloudComputing）是分布式处理（DistributedComputing）、并行处理（ParallelComputing）和网格计算（GridComputing）的发展，或者说是这些计算机科学概念的商业实现。云计算是一种新型的计算模