云计算概述及Google搜索引擎系统结构解析

1、云计算概述及 Google搜索引擎解 析 主要内容 云计算概述 文档的倒排索引 Google搜索引擎系统分析 云计算的定义 维基百科的定义：云计算是一种能够将动态伸缩 的虚拟化资源通过互联网以服务的方式提供给用 户的计算模式，用户不需要知道如何管理那些支 持云计算的基础设施。 云计算的特征 硬件和软件都是资源，通过互联网以服务的形式 提供给用户 这些资源都可以根据需要进行动态扩展和配置 这些资源在物理上以分布式的共享方式存在，但 最终在逻辑上以单一整体的形式呈现。 用户按需使用云中的资源，按实际使用量付费， 而不需要管理他们。 云计算的分类 按服务类型： 按服务方式：公有云、私有云、混合云 网

2、格计算与云计算的比较 网格计算 异构资源异构资源 不同机构不同机构 虚拟组织虚拟组织 科学计算为主科学计算为主 高性能计算机高性能计算机 紧耦合问题紧耦合问题 免费免费 标准化标准化 科学界科学界 云计算 同构资源同构资源 单一机构单一机构 虚拟机虚拟机 数据处理为主数据处理为主 服务器服务器/PC/PC 松耦合问题松耦合问题 按量计费按量计费 尚无标准尚无标准 商业社会商业社会 云计算的概念模型 云计算技术体系结构云计算技术体系结构 云计算实现机制云计算实现机制 Cloud Computing 云计算发展现状 Amazon研发了弹性计算云EC2（Elastic Computing Cloud

3、）和简单存储 服务S3（Simple Storage Service）为企业提供计算和存储服务。 诞生两年时间，Amazon上的注册开发人员就多达44万人，其中包括为数 众多的企业级用户。 Amazon云计算 1GB数据存放1个 月为0.15美元 简单存储服务S3（Simple Storage Service） 桶操作桶操作API: CreateBucket DeleteBucket ListBucket 对象操作对象操作API: PutObject GetObject DeleteObject GetObjectAccessControlPolicy SetObjectAccessContr

4、olPolicy Amazon云计算 弹性计算云EC2（Elastic Computing Cloud） 每个服务器租用 1小时为0.1美元 映像操作映像操作API: RegisterImage DescribeImages DeregisterImage 运行实例操作运行实例操作API: RunInstances DescribeInstances TerminateInstances GetConsoleOutput RebootInstances 应用案例：GIGAVOX公司 应用案例：SmugMug公司 应用案例：纽约时报 使用亚马逊云计算服务在不到24 个小时的时间里处理了1100万

5、篇 文章 累计花费240美元 如果用自己的服务器，需要数月 和多得多的费用 云计算发展现状 Google搜索引擎建立在分布在30多个站点、超过200万台服务器构成的云计 算设施的支撑之上，这些设施的数量正在迅猛增长。 Google的一系列成功应用，包括Google地球、地图、Gmail、Docs等也同样 使用了这些基础设施。 目前，Google已经允许第三方在Google的云计算中通过Google App Engine 运行大型并行应用程序。 Hadoop模仿了Google的实现机制。 SaaS Google Docs Google Maps Gmail Google Calendar Goo

6、gle Wave PaaS Google App Engine Google云计算应用的分类 1 8 Google云计算 Google文件系统(GFS) Google 48% MSN 19% Yahoo 33% 客户端 客户端客户端 互为备份 管理节点 GFS主节点 GFS主节点 C0C1 C2C5 数据结点1 C0 C2 C5 数据结点N C1 C5 数据结点2 客户端客户端 客户端客户端 客户端客户端 C1 云计算发展现状 微软于2008年10月推出了Windows Azure操作系统。Azure(译为“蓝 天”)是继Windows取代DOS之后，微软的又一次颠覆性转型。 Azure的底层

7、是微软全球基础服务系统，由遍布全球的第四代数据中 心构成。目前，微软已经配置了220个集装箱式数据中心，包括44万台 服务器。 微软云计算微软云计算 Windows LiveWindows Live 云计算发展现状 IBM在2007年11月推出了“改变游戏规则”的“蓝云”计算平台，为客户带 来即买即用的云计算平台。 IBM正在与17个欧洲组织合作开展名为RESERVOIR云计算项目，以“无障碍 的资源和服务虚拟化”为口号。欧盟提供了1.7亿欧元作为部分资金。 2008年8月， IBM宣布将投资约4亿美元用于其设在北卡罗来纳州和日本东 京的云计算数据中心改造。IBM计划在2009年在10个国家投

8、资3亿美元建13 个云计算中心。 开源云计算系统开源云计算系统 开源云计算系统开源云计算系统对应的商用云计算系统对应的商用云计算系统 Hadoop HDFSGoogle GFS Hadoop MapReduceGoogle MapReduce Hadoop HBaseGoogle Bigtable Hadoop ZooKeeperGoogle Chubby Eucalyptus、Enomaly ECP、 Nimbus Amazon EC2 EucalyptusAmazon S3 Sector and Sphere无直接对应系统 abiquo无直接对应系统 MongoDB无直接对应系统 主要内容

9、 云计算概述 文档的倒排索引 Google搜索引擎系统分析 Sequence of (Modified token, Document ID) pairs. I did enact Julius Caesar I was killed i the Capitol; Brutus killed me. Doc 1 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious Doc 2 Indexer steps Sort by terms. TermDoc # I1 did1 enact 1 juli

10、us1 caesar1 I1 was1 killed1 i1 the1 capitol1 brutus1 killed1 me1 so2 let2 it2 be2 with2 caesar2 the2 noble 2 brutus2 hath 2 told 2 you2 caesar 2 was2 ambitious2 Core indexing step. Multiple term entries in a single document are merged. Frequency information is added. The result is split into a Dicti

11、onary file and a Postings file. Doc #Freq 21 21 11 21 11 11 22 11 11 21 12 11 21 11 12 21 11 21 21 11 21 21 21 11 21 21 TermDoc #Freq ambitious21 be21 brutus 11 brutus 21 capitol11 caesar11 caesar22 did11 enact11 hath21 I12 i11 it21 julius11 killed12 let21 me11 noble21 so21 the11 the 21 told21 you21

12、 was11 was21 with21 Where do we pay in storage? Doc #Freq 21 21 11 21 11 11 22 11 11 21 12 11 21 11 12 21 11 21 21 11 21 21 21 11 21 21 Pointers Terms Query processing: AND Consider processing the query: Brutus AND Caesar Locate Brutus in the Dictionary; Retrieve its postings. Locate Caesar in the D

13、ictionary; Retrieve its postings. “Merge” the two postings: 128 34 248163264 123581321 BrutusBrutus CaesarCaesar 34 34 128248163264 123581321 The merge Walk through the two postings simultaneously, in time linear in the total number of postings entries 128 34 248163264 123581321 BrutusBrutus CaesarC

14、aesar 28 If the list lengths are x and y, the merge takes O(x+y) operations. Crucial: postings sorted by docID. 主要内容 云计算概述 文档的倒排索引 Google搜索引擎系统分析 Google Architecture Overview Google Architecture Overview URL Server URLserver sends lists of URLs to be fetched to the crawlers. Crawler Downloads Web Pa

15、ge Store Sever Web pages compress and stores into a repository Repository Stores the compressed web pages Google Architecture Overview Indexer(docID) Reads the repository, uncompresses the documents, and parses them. Converts each document into a set of word and Store them in barrels.Create forward

16、index. Parse out all the links in every web page and store in an anchors file. URL Resorlver reads the anchors file and converts relative URLs Into absolute URLs and in turn into docIDs. generates a database of links which are pairs of docIDs. The links database is used to compute PageRanks for all

17、the documents.Pagerank Generates the Doc Index Google Architecture Overview Doc index keeps information about each document. It is a fixed width ISAM (Index sequential access mode) index, ordered by docID. The information includes the current document status, a pointer into the repository, a documen

18、t checksum, and various statistics. the document has been crawled, a pointer called docinfo which contains its URL and title. Otherwise the pointer contains just the URL. Sorter(wordID) Takes the barrels and resorts them by wordID to generate the inverted index generates a new lexicon to be used by the searcher Repository Doc Index Links 软件学院 清华大学 . - - 清华大学 - - - . Lexicon Indexer结果 Sorter结果 Forward and Rev