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

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

2、私有云、混合云,网格计算与云计算的比较,云计算的概念模型,云计算技术体系结构,云计算实现机制,Cloud Computing,云计算发展现状,Amazon研发了弹性计算云EC2（Elastic Computing Cloud）和简单存储服务S3（Simple Storage Service）为企业提供计算和存储服务。 诞生两年时间，Amazon上的注册开发人员就多达44万人，其中包括为数众多的企业级用户。,Amazon云计算,1GB数据存放1个月为0.15美元,简单存储服务S3（Simple Storage Service）,桶操作API: CreateBucket DeleteBucket

3、ListBucket 对象操作API: PutObject GetObject DeleteObject GetObjectAccessControlPolicy SetObjectAccessControlPolicy,Amazon云计算,弹性计算云EC2（Elastic Computing Cloud）,每个服务器租用1小时为0.1美元,映像操作API: RegisterImage DescribeImages DeregisterImage 运行实例操作API: RunInstances DescribeInstances TerminateInstances GetConsoleOut

4、put RebootInstances,应用案例：GIGAVOX公司,应用案例：SmugMug公司,应用案例：纽约时报,使用亚马逊云计算服务在不到24个小时的时间里处理了1100万篇文章 累计花费240美元 如果用自己的服务器，需要数月和多得多的费用,云计算发展现状,Google搜索引擎建立在分布在30多个站点、超过200万台服务器构成的云计算设施的支撑之上，这些设施的数量正在迅猛增长。 Google的一系列成功应用，包括Google地球、地图、Gmail、Docs等也同样使用了这些基础设施。 目前，Google已经允许第三方在Google的云计算中通过Google App Engine运行大

5、型并行应用程序。 Hadoop模仿了Google的实现机制。,Google云计算应用的分类,18,Google云计算,Google文件系统(GFS),Google48%,MSN19%,Yahoo33%,客户端,互为备份,管理节点,GFS主节点,GFS主节点,C0,C1,C2,C5,数据结点1,C0,C2,C5,数据结点N,C1,C5,数据结点2,C1,云计算发展现状,微软于2008年10月推出了Windows Azure操作系统。Azure(译为“蓝天”)是继Windows取代DOS之后，微软的又一次颠覆性转型。 Azure的底层是微软全球基础服务系统，由遍布全球的第四代数据中心构成。目前，微

6、软已经配置了220个集装箱式数据中心，包括44万台服务器。,微软云计算,Windows Live,云计算发展现状,IBM在2007年11月推出了“改变游戏规则”的“蓝云”计算平台，为客户带来即买即用的云计算平台。 IBM正在与17个欧洲组织合作开展名为RESERVOIR云计算项目，以“无障碍的资源和服务虚拟化”为口号。欧盟提供了1.7亿欧元作为部分资金。 2008年8月， IBM宣布将投资约4亿美元用于其设在北卡罗来纳州和日本东京的云计算数据中心改造。IBM计划在2009年在10个国家投资3亿美元建13个云计算中心。,开源云计算系统,主要内容,云计算概述 文档的倒排索引 Google搜索引擎系

7、统分析,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.,Core indexing step.,Multiple term entries in a single do

8、cument are merged. Frequency information is added.,The result is split into a Dictionary file and a Postings file.,Where do we pay in storage?,Pointers,Terms,Query processing: AND,Consider processing the query: Brutus AND Caesar Locate Brutus in the Dictionary; Retrieve its postings. Locate Caesar i

9、n the Dictionary; Retrieve its postings. “Merge” the two postings:,128,34,2,4,8,16,32,64,1,2,3,5,8,13,21,Brutus,Caesar,34,The merge,Walk through the two postings simultaneously, in time linear in the total number of postings entries,128,34,2,4,8,16,32,64,1,2,3,5,8,13,21,2,8,If the list lengths are x

10、 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 Page Store Sever Web pages compress

11、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 index. Parse out all the links in

12、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 the documents.Pagerank Generates t

13、he 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 document checksum, and various statistics

14、. 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,Inde