走在架构师的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技术,软件架构,领域建模,IT 项目管理 Dict.CN 在线词典, 英语学习, 在线翻译

BlogJava 首页 新随笔 联系 聚合 管理
  195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks
是啊!!
有N条1000M光纤,N个服务器级的硬盘组成阵列!

1.1 前互联网搜索时代

在互联网发展初期,网站相对较少,信息查找比较容易。然而伴随互联网爆炸性的发展,普通网络用户想找到所需的资料简直如同大海捞针,这时为满足大众信息检索需求的专业搜索网站便应运而生了。

所有搜索引擎的祖先,是1990年由Montreal的McGill University学生Alan Emtage、Peter Deutsch、Bill Wheelan发明的Archie(Archie FAQ)。当时World Wide Web还未出现。Archie是第一个自动索引互联网上匿名FTP网站文件的程序,但它还不是真正的搜索引擎。Archie是一个可搜索的FTP文件名列表,用户必须输入精确的文件名搜索,然后Archie会告诉用户哪一个FTP地址可以下载该文件。

Archie工作原理与现在的搜索引擎已经很接近,它依靠脚本程序自动搜索网上的文件,然后对有关信息进行索引,供使用者以一定的表达式查询。由于Archie深受用户欢迎,受其启发,美国内华达System Computing Services大学于1993年开发了另一个与之非常相似的搜索工具,不过此时的搜索工具除了索引文件外,已能检索网页。

当时,“机器人”一词在编程者中十分流行。电脑“机器人”(Computer Robot)是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的“机器人”程序象蜘蛛一样在网络间爬来爬去,因此,搜索引擎的“机器人”程序就被称为“蜘蛛”程序。由于专门用于检索信息的Robot程序象蜘蛛(spider)一样在网络间爬来爬去,因此,搜索引擎的Robot程序被称为spider(SpiderFAQ)程序。世界上第一个Spider程序,是MIT Matthew Gray的World wide Web Wanderer,用于追踪互联网发展规模。刚开始它只用来统计互联网上的服务器数量,后来则发展为也能够捕获网址(URL)。

世界上第一个用于监测互联网发展规模的“机器人”程序是Matthew Gray开发的World wide Web Wanderer。刚开始它只用来统计互联网上的服务器数量,后来则发展为能够检索网站域名。

与Wanderer相对应,1993年10月Martijn Koster创建了ALIWEB(Martijn Koster Annouces the Availability of Aliweb),它相当于Archie的HTTP版本。ALIWEB不使用网络搜寻Robot,如果网站主管们希望自己的网页被ALIWEB收录,需要自己提交每一个网页的简介索引信息,类似于后来大家熟知的Yahoo。
1993年底,一些基于此原理的搜索引擎开始纷纷涌现,其中最负盛名的三个是:Scotland的JumpStation、Colorado大学Oliver McBryan的The World Wide Web Worm(First Mention of McBryan's World Wide Web Worm)、NASA的Repository-Based Software Engineering(RBSE)spider。随着互联网的迅速发展,使得检索所有新出现的网页变得越来越困难,因此,在Matthew Gray的Wanderer基础上,一些编程者将传统的“蜘蛛”程序工作原理作了些改进。其设想是,既然所有网页都可能有连向其他网站的链接,那么从跟踪一个网站的链接开始,就有可能检索整个互联网。然而Jump Station和WWW Worm只是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果,因此毫无信息关联度可言。而RBSE是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。

1993年2月,6个Stanford(斯坦福)大学生的想法是分析字词关系,以对互联网上的大量信息作更有效的检索。这就是Excite。后来曾以概念搜索闻名,2002年5月,被Infospace收购的Excite停止自己的搜索引擎,改用元搜索引擎Dogpile

1994年1月,第一个既可搜索又可浏览的分类目录EINetGalaxy(Tradewave Galaxy)上线。除了网站搜索,它还支持Gopher和Telnet搜索。

1994年4月,Stanford两名博士生,美籍华人Jerry Yang(杨致远)和David Filo共同创办了Yahoo。随着访问量和收录链接数的增长,Yahoo目录开始支持简单的数据库搜索。因为Yahoo!的数据是手工输入的,所以不能真正被归为搜索引擎,事实上只是一个可搜索的目录。搜索效率明显提高。(Yahoo以后陆续使用Altavista、Inktomi、Google提供搜索引擎服务)

1994年初,Washington大学CS学生Brian Pinkerton开始了他的小项目Web Crawler(Brian Pinkerton Announces the Availability of Webcrawler)。1994年4月20日,Web Crawler正式亮相时仅包含来自6000个服务器的内容。Web Crawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎,在它之前,用户只能通过URL和摘要搜索,摘要一般来自人工评论或程序自动取正文的前100个字。(后来web crawler陆续被AOL和Excite收购,现在和excite一样改用元搜索引擎Dogpile)

1.2 互联网搜索时代

最早现代意义上的搜索引擎出现于1994年7月。当时Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中,创建了大家现在熟知的Lycos。同年4月,斯坦福(Stanford)大学的两名博士生,David Filo和美籍华人杨致远(Gerry Yang)共同创办了超级目录索引Yahoo,并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前,互联网上有名有姓的搜索引擎已达数百家,其检索的信息量也与从前不可同日而语。比如最近风头正劲的Google,其数据库中存放的网页已达30亿之巨!

随着互联网规模的急剧膨胀,一家搜索引擎光靠自己单打独斗已无法适应目前的市场状况,因此现在搜索引擎之间开始出现了分工协作,并有了专业的搜索引擎技术和搜索数据库服务提供商。象国外的Inktomi,它本身并不是直接面向用户的搜索引擎,但向包括Overture(原GoTo)、LookSmart、MSN、HotBot等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类,搜狐和新浪用的就是它的技术。因此从这个意义上说,它们是搜索引擎的搜索引擎。

Lycos(Carnegie Mellon University Center for Machine Translation Announces Lycos)是搜索引擎史上又一个重要的进步。Carnegie Mellon University的Michael Mauldin将John Leavitt的spider程序接入到其索引程序中,创建了Lycos。1994年7月20日,数据量为54,000的Lycos正式发布。除了相关性排序外,Lycos还提供了前缀匹配和字符相近限制,Lycos第一个在搜索结果中使用了网页自动摘要,而最大的优势还是它远胜过其它搜索引擎的数据量:1994年8月--394,000 documents;1995年1月--1.5 million documents;1996年11月--over 60 million documents。(注:1999年4月,Lycos停止自己的Spider,改由Fast提供搜索引擎服务)

Infoseek(Steve Kirsch Announces Free Demos Of the Infoseek Search Engine)是另一个重要的搜索引擎,虽然公司声称1994年1月已创立,但直到年底它的搜索引擎才与公众见面。起初,Infoseek只是一个不起眼的搜索引擎,它沿袭Yahoo!和Lycos的概念,并没有什么独特的革新。但是它的发展史和后来受到的众口称赞证明,起初第一个登台并不总是很重要。Infoseek友善的用户界面、大量附加服务(such as UPStracking,News,adirectory,and the like)使它声望日隆。而1995年12月与Netscape的战略性协议,使它成为一个强势搜索引擎:当用户点击Netscape浏览器上的搜索按钮时,弹出Infoseek的搜索服务,而此前由Yahoo!提供该服务。(注:Infoseek后来曾以相关性闻名,2001年2月,Infoseek停止了自己的搜索引擎,开始改用Overture的搜索结果)
1995年,一种新的搜索引擎形式出现了——元搜索引擎(A Meta Search Engine Roundup)。用户只需提交一次搜索请求,由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎,并将从各独立搜索引擎返回的所有查询结果,集中起来处理后再返回给用户。第一个元搜索引擎,是Washington大学硕士生Eric Selberg和Oren Etzioni的Metacrawler。元搜索引擎概念上好听,但搜索效果始终不理想,所以没有哪个元搜索引擎有过强势地位。

DEC的AltaVista(2001年夏季起部分网友需通过p-roxy访问,无p-roxy可用qbseach单选altavista搜索,只能显示第一页搜索结果)是一个迟到者,1995年12月才登场亮相(AltaVista Public Beta Press Release)。但是,大量的创新功能使它迅速到达当时搜索引擎的顶峰。Altavista最突出的优势是它的速度。而Altavista的另一些新功能,则永远改变了搜索引擎的定义。AltaVista是第一个支持自然语言搜索的搜索引擎,AltaVista是第一个实现高级搜索语法的搜索引擎(如AND,OR,NOT等)。用户可以用AltaVista搜索Newsgroups(新闻组)的内容并从互联网上获得文章,还可以搜索图片名称中的文字、搜索Titles、搜索Java applets、搜索ActiveXobjects。AltaVista也声称是第一个支持用户自己向网页索引库提交或删除URL的搜索引擎,并能在24小时内上线。AltaVista最有趣的新功能之一,是搜索有链接指向某个URL的所有网站。在面向用户的界面上,AltaVista也作了大量革新。它在搜索框区域下放了“tips”以帮助用户更好的表达搜索式,这些小tip经常更新,这样,在搜索过几次以后,用户会看到很多他们可能从来不知道的的有趣功能。这系列功能,逐渐被其它搜索引擎广泛采用。

1997年,AltaVista发布了一个图形演示系统LiveTopics,帮助用户从成千上万的搜索结果中找到想要的。

然后到来的是HotBot。1995年9月26日,加州伯克利分校CS助教EricBrewer、博士生PaulGauthier创立了Inktomi(UCBerkeley Announces Inktomi),1996年5月20日,Inktomi公司成立,强大的HotBot出现在世人面前。声称每天能抓取索引1千万页以上,所以有远超过其它搜索引擎的新内容。HotBot也大量运用cookie储存用户的个人搜索喜好设置。(Hotbot曾是随后几年最受欢迎的搜索引擎之一,后被Lycos收购)

Northernlight公司于1995年9月成立于马萨诸塞州剑桥,1997年8月,Northernlight搜索引擎正式现身。它曾是拥有最大数据库的搜索引擎之一,它没有Stop Words,它有出色的Current News、7,100多出版物组成的Special Collection、良好的高级搜索语法,第一个支持对搜索结果进行简单的自动分类。(2002年1月16日,Northernlight公共搜索引擎关闭,随后被divine收购,但在Nlresearch,选中"World Wide Web only",仍可使用Northernlight搜索引擎)

1998年10月之前,Google只是Stanford大学的一个小项目BackRub。1995年博士生LarryPage开始学习搜索引擎设计,于1997年9月15日注册了google.com的域名,1997年底,在Sergey Brin和Scott Hassan、Alan Steremberg的共同参与下,Bach Rub开始提供Demo。1999年2月,Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日。

Google在Pagerank、动态摘要、网页快照、Daily Refresh、多文档格式支持、地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新,象Altavista一样,再一次永远改变了搜索引擎的定义。

在2000年中以前,Google虽然以搜索准确性备受赞誉,但因为数据库不如其它搜索引擎大,缺乏高级搜索语法,所以使用价值不是很高,推广并不快。直到2000年中数据库升级后,又借被Yahoo选作搜索引擎的东风,才一飞冲天。

Fast(Alltheweb)公司创立于1997年,是挪威科技大学(NTNU)学术研究的副产品。1999年5月,发布了自己的搜索引擎AllTheWeb。Fast创立的目标是做世界上最大和最快的搜索引擎,几年来庶几近之。Fast(Alltheweb)的网页搜索可利用ODP自动分类,支持Flash和pdf搜索,支持多语言搜索,还提供新闻搜索、图像搜索、视频、MP3、和FTP搜索,拥有极其强大的高级搜索功能。

Teoma起源于1998年Rutgers大学的一个项目。Apostolos Gerasoulis教授带领华裔TaoYang教授等人创立Teoma于新泽西Piscataway,2001年春初次登场,2001年9月被提问式搜索引擎Ask Jeeves收购,2002年4月再次发布。Teoma的数据库目前仍偏小,但有两个出彩的功能:支持类似自动分类的Refine;同时提供专业链接目录的Resources。

Wisenut由韩裔Yeogirl Yun创立。2001年春季发布Beta版,2001年9月5日发布正式版,2002年4月被分类目录提供商looksmart收购。wisenut也有两个出彩的功能:包含类似自动分类和相关检索词的Wise Guide;预览搜索结果的Sneak-a-Peek。

Gigablast由前Infoseek工程师Matt Wells创立,2002年3月展示pre-beta版,2002年7月21日发布Beta版。Gigablast的数据库目前仍偏小,但也提供网页快照,一个特色功能是即时索引网页,你的网页刚提交它就能搜索(注:这个spammers的肉包子功能暂已关闭)。

Openfind创立于1998年1月,其技术源自台湾中正大学吴升教授所领导的GAIS实验室。Openfind起先只做中文搜索引擎,曾经是最好的中文搜索引擎,鼎盛时期同时为三大著名门户新浪、奇摩、雅虎提供中文搜索引擎,但2000年后市场逐渐被Baidu和Google瓜分。2002年6月,Openfind重新发布基于GAIS30Project的Openfind搜索引擎Beta版,推出多元排序(PolyRankTM),宣布累计抓取网页35亿,开始进入英文搜索领域,此后技术升级明显加快。

北大天网是国家"九五"重点科技攻关项目"中文编码和分布式中英文信息发现"的研究成果,由北大计算机系网络与分布式系统研究室开发,于1997年10月29日正式在CERNET上提供服务。2000年初成立天网搜索引擎新课题组,由国家973重点基础研究发展规划项目基金资助开发,收录网页约6000万,利用教育网优势,有强大的ftp搜索功能。

2000年1月,超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇(加州伯克利分校博士)在北京中关村创立了百度(Baidu)公司。2001年8月发布Baidu.com搜索引擎Beta版(此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎),2001年10月22日正式发布Baidu搜索引擎。Baidu虽然只提供中文搜索,但目前收录中文网页超过9000万,可能是最大的的中文数据库。Baidu搜索引擎的其它特色包括:网页快照、网页预览/预览全部网页、相关搜索词、错别字纠正提示、新闻搜索、Flash搜索、信息快递搜索。2002年3月闪电计划(Blitzen Project)开始后,技术升级明显加快。
1.3 搜索引擎大事记

1990年, McGill University学生Alan Emtage、Peter Deutsch、Bill Wheelan发明Archie(Archie FAQ)。

1993年,美国内华达System Computing Services大学开发了另一个与Archie非常相似的搜索工具,不过此时的搜索工具除了索引文件外,已能检索网页。

1993年,Matthew Gray开发的World wide Web Wanderer,是世界上第一个用于监测互联网发展规模的“机器人”程序。

1993年10月,Martin Koster创建了ALIWEB,它是Archie的HTTP版本。
1993年底,一些基于此原理的搜索引擎开始纷纷涌现,其中以Jump Station、The World Wide Web Worm和Repository-Based Software Engineering(RBSE)spider最负盛名。

1994年1月,第一个既可搜索又可浏览的分类目录EINetGalaxy(Tradewave Galaxy)上线。除了网站搜索,它还支持Gopher和Telnet搜索。

1994年初,Washington大学CS学生Brian Pinkerton开始了他的小项目Web Crawler(Brian Pinkerton Announces the Availability of Webcrawler)。1994年4月20日,Web Crawler正式亮相。

1994年4月,Stanford两名博士生,美籍华人Jerry Yang(杨致远)和David Filo共同创办了Yahoo。随着访问量和收录链接数的增长,Yahoo目录开始支持简单的数据库搜索。因为Yahoo!的数据是手工输入的,所以不能真正被归为搜索引擎,事实上只是一个可搜索的目录。

1994年7月,Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中,创建了大家现在熟知的Lycos。1996年底,美国在线收购了Excite20%的股份,美国在线搜索引擎也自然由Excite提供。

1995年,一种新的搜索引擎形式出现了——元搜索引擎(A Meta Search Engine Roundup)。第一个元搜索引擎,是Washington大学硕士生Eric Selberg和Oren Etzioni的Metacrawler。

1995年9月26日,加州伯克利分校CS助教EricBrewer、博士生PaulGauthier创立了Inktomi(UCBerkeley Announces Inktomi),1996年5月20日,Inktomi公司成立,强大的HotBot出现在世人面前。

1995年9月,Northernlight公司于成立于马萨诸塞州剑桥,1997年8月,Northernlight搜索引擎正式现身。它曾是拥有最大数据库的搜索引擎之一,它没有Stop Words,它有出色的Current News、7,100多出版物组成的Special Collection、良好的高级搜索语法,第一个支持对搜索结果进行简单的自动分类。

1995年博士生LarryPage开始学习搜索引擎设计,于1997年9月15日注册了google.com的域名,1997年底,在Sergey Brin和Scott Hassan、Alan Steremberg的共同参与下,Bach Rub开始提供Demo。1999年2月,Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日。

1997年,Fast(Alltheweb)公司创立于,是挪威科技大学(NTNU)学术研究的副产品。1999年5月,发布了自己的搜索引擎AllTheWeb。

1998年,Rutgers大学的Apostolos Gerasoulis教授带领华裔TaoYang教授等人创立Teoma于新泽西Piscataway,2001年春初次登场,2001年9月被提问式搜索引擎Ask Jeeves收购,2002年4月再次发布。

1998年1月,Openfind创立,其技术源自台湾中正大学吴升教授所领导的GAIS实验室,2002年6月,Openfind重新发布基于GAIS30Project的Openfind搜索引擎Beta版。

1997年10月29日,北大天网作为国家"九五"重点科技攻关项目"中文编码和分布式中英文信息发现"的研究成果,由北大计算机系网络与分布式系统研究室开发,正式在CERNET上提供服务。2000年初成立天网搜索引擎新课题组,由国家973重点基础研究发展规划项目基金资助开发,收录网页约6000万,利用教育网优势,有强大的ftp搜索功能。

2000年1月,超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇(加州伯克利分校博士)在北京中关村创立了百度(Baidu)公司。2001年8月发布Baidu.com搜索引擎Beta版(此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎),2001年10月22日正式发布Baidu搜索引擎。

2001年春季韩裔Yeogirl Yun创立Wisenut,发布Beta版,2001年9月5日发布正式版,2002年4月被分类目录提供商looksmart收购。

2002年5月1日,网络帝国美国在线(AOL)与Google签约,全面采用Google的搜索引擎并显示Google所有卖出的网站排名结果。

2002年12月24日,雅虎称公司同意以大约2.35亿美元的价格收购搜索软件公司Inktomi。

2003年1月18日,Google收购博客网站Blogger.com开发团队——网上出版软件开发商PyraLabs。

2003年2月19日,Overture服务公司表示,计划以1.4亿美元现金加股票从CMGI公司手中收购门户网站AtaVista。

2003年2月26日,Overture同意以1亿美元收购位于挪威的FastSearchandTransfer公司的网络搜索部门。

2003年4月15日,新浪与中国搜索联盟结成战略同盟,至此,中国已有数百家网站结成搜索联盟,以迎接国际巨头Google挺进国内市场后的巨大压力。

2003年4月21日,第二大互联网搜索引擎提供商AskJeeves公司宣布对其Ask.com网站进行升级。AskJeeves是仅次于Google的第二大搜索引擎,也是互联网上第五大搜索基地(Google、雅虎、微软、AOL、Askjeeves)。

2003年6月18日,微软公司表示其正在加大研发新型互联网搜索引擎技术的力度,包括对一款功能更先进的技术原型进行测试。

2003年7月13日,百度推出图象搜索,新闻搜索两大搜索功能,以此来带动搜索流量。同时,辅以百度的搜索风云榜,使得百度的信息搜索及信息评估的作用更加突出

2003年7月15日,全球最大的互联网公司雅虎宣布,以16.3亿美元收购在网络搜索服务上的竞争对手—Overture公司,以期在同Google的竞争中取得优势。


Google背后的分布式计算架构策略
Google是与众不同的。它的独特不仅仅表现于革新的思维和充满创意的应用 (比如那个大堂里的地球模型),更在于其有别常规的IT策略……
  加利福尼亚州山景城(Mountain View)Google公司(Google,下称Google)总部有一个43号大楼,该建筑的中央大屏幕上显示着一个与Google地球(Google Earth)相仿的世界地图,一个转动的地球上不停地闪动着五颜六色的光点,恍如罗马宫廷的千万烛灯,每一次闪动标志着地球的这个角落一名Google用 户发起了一次新的搜索。
  这同时意味着Google又一次满足了人们对未知信息的好奇与渴望。
  Google是与众不同的。它的独特不仅仅表现于革新的思维和充满创意的应用 (比如那个大堂里的地球模型),更在于其有别常规的IT策略。从人们的常理来看,简单的硬件商品和免费软件是无法构建出一个帝国的,但是Google做到 了。在性能调整后,Google把它们变成一个无可比拟的分布式计算平台,该平台能够支持大规模的搜索和不断涌现的新兴应用。我们原本认为这些应用都是个 人消费级别的,但是Google改变了这一切。现在商业世界也在使用它们,这就令这家搜索公司显得那么与众不同。
  GoogleWeb 服务背后的IT架构对无数使用搜索引擎的用户来说也许并不是非常重要,但它是Google几百位致力于把全球信息组织起来,实现“随处可达,随时可用”目 标的工程师们的最核心工作。这就需要一个在覆盖范围和野心上都与Google的商业愿景完全相符的IT蓝图作为支撑。
  Google 的经理们一直对公司的IT策略话题保持沉默,他们厌恶谈及特定的厂商或者产品,当被问到他们的服务器和数据中心时,他们总是闭口不谈。但与几位 Google的IT领导一起呆了一天后,我们最终得以揭示该公司的IT是如何运作的,那可不仅仅是一个运行在无数服务器集群上的、表面看来非常简单的搜索 引擎。在其简单的外表下,蕴涵着许多内部研发软件、定制硬件、人工智能,以及对性能的执着追求和打破常规的人力管理模式。
  IT理念方面,Google对同行有一条建议:尽量避免那些人人都在使用的系统和软件,以自己的方式做事会更有独特的竞争优势。
  “企业文化决定了你的做事方式。”道格拉斯"美林(Douglas Merrill),这位Google工程副总裁和事实上的首席信息官(CIO) 指出,“到了我们这样的发展阶段,企业观念和文化非常与众不同,这也反过来鞭策我们必须要采用与众不同的方式来运行那些他人看来很常规的系统。”
  Google 最大的IT优势在于它能建造出既富于性价比(并非廉价)又能承受极高负载的高性能系统。因此IT顾问史蒂芬"阿诺德(Stephen Arnold)指出,Google与竞争对手,如亚马逊网站(Amazon)、电子港湾公司(eBay)、微软公司(Microsoft,下称微软)和雅 虎公司 (Yahoo,下称雅虎)等公司相比,具有更大的成本优势。Google程序员的效率比其他Web公司同行们高出50%~100%,原因是Google已 经开发出了一整套专用于支持大规模并行系统编程的定制软件库。据他估算,其他竞争公司可能要花上四倍的时间才能获得同等的效果。
  打造服务器
  Google 究竟是怎样做到这点的呢?其中一个手段,美林认为,“是因为我们自己动手打造硬件。”Google并不制造计算机系统,但它根据自己的参数定制硬件,然后 像MTV的节目“靓车打造”(Pimp My Ride)那样自己安装和调整硬件系统。开源程序经理克里斯"迪博纳(Chris DiBona)评论道:“我们很善于购买商业服务器,并且改造他们为我们所用,最后把性能压榨和发挥到极致,以致有时候他们热得像要融化了似的。”
  这种亲手打造的方式,来源于Google从车库诞生时与生俱来的节俭风格,更与Google那超大型的系统规模息息相关,良好的习惯一直延续至 今。据说 Google在65个数据中心拥有20万~45万台服务器—这个数目会有偏差(取决于你如何定义服务器和由谁来做这项统计)。但是,不变的是持续上升的趋 势。
  Google不会去讨论这些资产,因为它认为保密也是一种竞争优势。事实上,Google之所以喜欢开源软件也是因为它的私密性。“如果我们购 买了软件许可或代码许可,人们只要对号入座,就可以猜出Google的IT基础架构。”迪博纳分析说, “使用开源软件,就使我们多了一条把握自己命运的途径。”
  Google喜欢规模化的服务器运行方式。当有成百上千台机器时,定制服务器的优势也会成倍增加,效果也会更趋明显。Google正在俄勒冈州 哥伦比亚河边的达勒斯市建造一个占地30亩的数据中心,在那儿它可以获得运算和降温需要的低价水力电力能源(参见边栏《Google数据中心自有一套》)。
  Google以“单元”(Cell)的形式组织这些运行 Linux操作系统的服务器,迪博纳把这种形式比喻成互联网服务的“磁盘驱动器”(但别和一直谣传的Google存储服务Gdrive混淆了,“并没有 Gdrive这回事。”一位Google女发言人明确表示。),公司的软件程序都驻扎在这些并不昂贵的电脑机箱里,由程序员决定它们的冗余工作量。这种由 很多单元组成的文件系统代替了商业存储设备;迪博纳表示Google这些单元设备更易于建造和维护,他还暗示他们能处理更大规模的数据。
  Google 不会漏过对任何技术细节的关注。多年来,公司的工程师就在研究微处理器的内部工作机制,随着Google规模的持续壮大,必然会用到特别定制和调节过的芯 片。知名工程师路易斯"巴罗索(Luiz Barroso)去年在一篇发表在工业杂志上的论文中证实,近年来Google的主要负荷都由单核设计的系统承担着。但许多服务器端的应用,如 Google搜索索引服务,所需的并行计算在单核芯片的指令级别上执行得并不好。
  曾在数据设备公司(Digital Equipment)和康柏公司(Compaq)当过芯片设计师的巴罗索认为,随着AMD公司、英特尔公司(Intel)、太阳计算机系统公司(Sun)开始制造多核芯片,必将会出现越来越多芯片级别的并行计算。
  Google 也曾考虑过自己制造计算机芯片,但从业界潮流来看,这个冒险的举动似乎不是很必要。“微处理器的设计非常复杂而且成本昂贵,”运营高级副总裁乌尔斯"霍尔 茨勒(Urs Holzle)表示。Google宁愿与芯片制造商合作,让他们去理解自己的应用并设计适合的芯片。这是一种客户建议式的设计,其关注点在于总体吞吐量、 效能,以及耗电比,而不是看单线程的峰值性能。霍尔茨勒表示,“这也是最近多核CPU的设计潮流与未来方向。”
裁缝般地定制软件
  为了能尽量压榨硬件性能,Google开发了相当数量的定制软件。创新产品主要包括用于简化处理和创建大规模数据集的编程模型 MapReduce;用于存储和管理大规模数据的系统BigTable;分析分布式运算环境中大规模数据集的解释编程语言Sawzall;用于数据密集型 应用的分布式文件系统的 “Google文件系统”(Google File System);还有为处理分布式系统队列分组和任务调度的“Google工作队列”(Google Workqueue)。
  正是从Sawzall这些工具里体现出Google对计算效率的执著关注。并不是每家公司都能从底层去解决效率问题,但是对Google来说, 为常规关系型数据库无法容纳的大规模数据集专门设计一种编程语言是完全合理的。即使其他编程工具可以解决问题,Google的工程师们仍然会为了追求效率 而另外开发一套定制方案。Google工程师认为,Sawzall能与C++中的MapReduce相媲美,而且它更容易编写一些。
  Google 对效率的关注使它不可能对标准Linux内核感到满意;Google会根据自己的需要运行修改过的内核版本。通过调整Linux的底层性能,Google 工程师们在提高了整体系统可靠性的基础上,还一并解决了数据损坏和数据瓶颈等一系列棘手问题。对内核的修改也使Google的计算机集群系统因为通信效率 的提高而运行得更快。
  当然,Google偶尔也会出现系统故障,情况一旦发生,无数的用户就会受到影响了。三年前一次持续30分钟的系统故障使20%的搜索流量受到影响。
  Google 开发了自己的网站服务器却没有使用开源的Apache服务器,尽管它在网站服务器的市场占有率超过60%。迪博纳认为,Google的网站服务器可以运行 在更多数量的主机上,对Google站点上内容庞大又彼此互相依赖的应用程序来说,这种服务器的负载均衡能力远比Apache的能力更高。同时,在用标准 公共网关接口(CGI)访问数据库动态网页方面,Google服务器的编程难度要比 Apache更高,但是最终运行速度却更快。“如果我们能够压榨出10%~20%的性能,我们就可以节省出更多系统资源、电量和人力了。”迪博纳在总结中 指出。
  Google还设计了自己的客户关系管理(CRM)系统用于支持自己基于竞价和点击的互联网广告收费业务。但对是否需要设计自己的工具,Google的态度也不是一成不变的。比如在财会软件上,它就使用了甲骨文公司(Oracle)的Financials软件。
  美林拿着一只叉子举例说明现成的产品也可以带来价值。但在有些场合现成的软件产品就不一定适用了。“我们的文化在各个层面对我们的运作都有深远影响,”他表示,“所以我们不想让购买所得的工具改变我们的工作方式和文化层面。”
Google's BigTable 原理 (翻译)
题记:google 的成功除了一个个出色的创意外,还因为有 Jeff Dean 这样的软件架构天才。
------ 编者
官方的 Google Reader blog 中有对BigTable 的解释。这是Google 内部开发的一个用来处理大数据量的系统。这种系统适合处理半结构化的数据比如 RSS 数据源。 以下发言 是 Andrew Hitchcock 在 2005 年10月18号 基于: Google 的工程师 Jeff Dean 在华盛顿大学的一次谈话 (Creative Commons License).
首先,BigTable 从 2004 年初就开始研发了,到现在为止已经用了将近8个月。(2005年2月)目前大概有100个左右的服务使用BigTable,比如: Print,Search History,Maps和 Orkut。根据Google的一贯做法,内部开发的BigTable是为跑在廉价的PC机上设计的。BigTable 让Google在提供新服务时的运行成本降低,最大限度地利用了计算能力。BigTable 是建立在 GFS ,Scheduler ,Lock Service 和 MapReduce 之上的。
每个Table都是一个多维的稀疏图 sparse map。Table 由行和列组成,并且每个存储单元 cell 都有一个时间戳。在不同的时间对同一个存储单元cell有多份拷贝,这样就可以记录数据的变动情况。在他的例子中,行是URLs ,列可以定义一个名字,比如:contents。Contents 字段就可以存储文件的数据。或者列名是:”language”,可以存储一个“EN”的语言代码字符串。
为了管理巨大的Table,把Table根据行分割,这些分割后的数据统称为:Tablets。每 个Tablets大概有 100-200 MB,每个机器存储100个左右的 Tablets。底层的架构是:GFS。由于GFS是一种分布式的文件系统,采用Tablets的机制后,可以获得很好的负载均衡。比如:可以把经常响应 的表移动到其他空闲机器上,然后快速重建。
Tablets在系统中的存储方式是不可修改的 immutable 的SSTables,一台机器一个日志文件。当系统的内存满后,系统会压缩一些Tablets。由于Jeff在论述这点的时候说的很快,所以我没有时间把听到的都记录下来,因此下面是一个大概的说明:
压缩分为:主要和次要的两部分。次要的压缩仅仅包括几个Tablets,而主要的压缩时关于整个系统的压缩。主压缩有回收硬盘空间的功能。Tablets的位置实际上是存储在几个特殊的BigTable的存储单元cell中。看起来这是一个三层的系统。
客户端有一个指向METAO的Tablets的指针。如果METAO的Tablets被频繁使用,那个这台机器就会放弃其他的tablets专门支持 METAO这个Tablets。METAO tablets 保持着所有的META1的tablets的记录。这些tablets中包含着查找tablets的实际位置。(老实说翻译到这里,我也不太明白。)在这个系统中不存在大的瓶颈,因为被频繁调用的数据已经被提前获得并进行了缓存。
现在我们返回到对列的说明:列是类似下面的形式: family:optional_qualifier。在他的例子中,行:www.search-analysis.com 也许有列:”contents:其中包含html页面的代码。 “ anchor:cnn.com/news” 中包含着 相对应的url,”anchor:www.search-analysis.com/” 包含着链接的文字部分。列中包含着类型信息。
(翻译到这里我要插一句,以前我看过一个关于万能数据库的文章,当时很激动,就联系了作者,现在回想起来,或许google的 bigtable 才是更好的方案,切不说分布式的特性,就是这种建华的表结构就很有用处。)
注意这里说的是列信息,而不是列类型。列的信息是如下信息,一般是:属性/规则。 比如:保存n份数据的拷贝或者保存数据n天长等等。当 tablets 重新建立的时候,就运用上面的规则,剔出不符合条件的记录。由于设计上的原因,列本身的创建是很容易的,但是跟列相关的功能确实非常复杂的,比如上文提到 的 类型和规则信息等。为了优化读取速度,列的功能被分割然后以组的方式存储在所建索引的机器上。这些被分割后的组作用于 列 ,然后被分割成不同的 SSTables。这种方式可以提高系统的性能,因为小的,频繁读取的列可以被单独存储,和那些大的不经常访问的列隔离开来。
在一台机器上的所有的 tablets 共享一个log,在一个包含1亿的tablets的集群中,这将会导致非常多的文件被打开和写操作。新的log块经常被创建,一般是64M大小,这个GFS的块大小相等。当一个机器down掉后,控制机器就会重新发布他的log块到其他机器上继续进行处理。这台机器重建tablets然后询问控制机器处理结构的存储位置,然后直接对重建后的数据进行处理。
这个系统中有很多冗余数据,因此在系统中大量使用了压缩技术。
Dean 对压缩的部分说的很快,我没有完全记下来,所以我还是说个大概吧:压缩前先寻找相似的 \行,列,和时间数据。
他们使用不同版本的: BMDiff 和 Zippy 技术。
BMDiff 提供给他们非常快的写速度: 100MB/s – 1000MB/s 。Zippy 是和 LZW 类似的。Zippy 并不像 LZW 或者 gzip 那样压缩比高,但是他处理速度非常快。
Dean 还给了一个关于压缩 web 蜘蛛数据的例子。这个例子的蜘蛛 包含 2.1B 的页面,行按照以下的方式命名:“com.cnn.www/index.html:http”.在未压缩前的web page 页面大小是:45.1 TB ,压缩后的大小是:4.2 TB , 只是原来的 9.2%。Links 数据压缩到原来的 13.9% , 链接文本数据压缩到原来的 12.7%。
Google 还有很多没有添加但是已经考虑的功能。
1. 数据操作表达式,这样可以把脚本发送到客户端来提供修改数据的功能。
2. 多行数据的事物支持。
3. 提高大数据存储单元的效率。
4. BigTable 作为服务运行。
好像:每个服务比如: maps 和 search history 历史搜索记录都有他们自己的集群运行 BigTable。
他们还考虑运行一个全局的 BigTable 系统,但这需要比较公平的分割资源和计算时间。
大表(Bigtable):结构化数据的分布存储系统
http://labs.google.com/papers/bigtable-osdi06.pdf
{中是译者评论,程序除外}
{本文的翻译可能有不准确的地方,详细资料请参考原文.}
摘要
bigtable是设计来分布存储大规模结构化数据的,从设计上它可以扩展到上2^50字节,分布存储在几千个普通服务器上.google的很多项目使用 bt来存储数据,包括网页查询,google earth和google金融.这些应用程序对bt的要求各不相同:数据大小(从URL到网页到卫星图象)不同,反应速度不同(从后端的大批处理到实时数 据服务).对于不同的要求,bt都成功的提供了灵活高效的服务.在本文中,我们将描述bt的数据模型.这个数据模型让用户动态的控制数据的分布和结构.我 们还将描述BT的设计和实现.
1.介绍
在过去两年半里,我们设计,实现并部署了BT.BT是用来分布存储和管理结构化数据的.BT的设计使它能够管理2^50 bytes(petabytes)数据,并可以部署到上千台机器上.BT完成了以下目标:应用广泛,可扩展,高性能和高可用性(high availability). 包括google analytics, google finance, orkut, personalized search, writely和google earth在内的60多个项目都使用BT.这些应用对BT的要求各不相同,有的需要高吞吐量的批处理,有的需要快速反应给用户数据.它们使用的BT集群也各不相同,有的只有几台机器,有的有上千台,能够存储2^40字节(terabytes)数据.
BT在很多地方和数据库很类似:它使用了很多数据库的实现策略.并行数据库[14]和内存数据库[13]有可扩展性和高性能,但是BT的界面不同.BT不支持完全的关系数据模型;而是为客户提供了简单的数据模型,让客户来动态控制数据的分布和格式{就是只存储字串,格式由客户来解释},并允许客户推断底层存储数据的局部性{以提高访问速度}.数据下标是行和列的名字,数据本身可以是任何字串.BT的数据是字串,没有解释{类型等}.客户会在把各种结构或者半结构化的数据串行化{比如说日期串}到数据中.通过仔细选择数据表示,客户可以控制数据的局部化.最后,可以使用BT模式来控制数据是放在内存里还是在硬盘上.{就是说用模式,你可以把数据放在离应用最近的地方.毕竟程序在一个时间只用到一块数据.在体系结构里,就是:locality, locality, locality}
第二节描述数据模型细节.第三节关于客户API概述.第四节简介BT依赖的google框架.第五节描述BT的实现关键部分.第6节叙述提高BT性 能的一些调整.第7节提供BT性能的数据.在第8节,我们提供BT的几个使用例子,第9节是经验教训.在第10节,我们列出相关研究.最后是我们的结论.
2.数据模型
BT是一个稀疏的,长期存储的{存在硬盘上},多维度的,排序的映射表.这张表的索引是行关键字,列关键字和时间戳.每个值是一个不解释的字符数组.{数据都是字符串,没类型,客户要解释就自力更生吧}.
(row:string, column:string,time:int64)->string {能编程序的都能读懂,不翻译了}
我们仔细查看过好些类似bigtable的系统之后定下了这个数据模型。举一个具体例子(它促使我们做出某些设计决定), 比如我们想要存储大量网页及相关信息,以用于很多不同的项目;我们姑且叫它Webtable。在Webtable里,我们将用URL作为行关键字,用网页 的某些属性作为列名,把网页内容存在contents:列中并用获取该网页的时间戳作为标识,如图一所示。

图一:一个存储Web网页的范例列表片断。行名是一个反向URL{即com.cnn.www}。contents列族{原文用 family,译为族,详见列族} 存放网页内容,anchor列族存放引用该网页的锚链接文本。CNN的主页被Sports Illustrater{即所谓SI,CNN的王牌体育节目}和MY-look的主页引用,因此该行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本{由时间戳标识,如t9,t8};而contents列则有三个版本,分别由时间 戳t3,t5,和t6标识。

表中的行关键字可以是任意字符串(目前支持最多64KB,多数情况下10-100字节足够了)。在一个行关键字下的每一个读写操作都是原子操作(不管读写这一行里多少个不同列),这是一个设计决定,这样在对同一行进行并发操作时,用户对于系统行为更容易理解和掌控。
Bigtable通过行关键字的字典序来维护数据。一张表可以动态划分成多个连续行。连续行在这里叫做“子表”{tablet},是数据分布和负载 均衡的单位。这样一来,读较少的连续行就比较有效率,通常只需要较少机器之间的通信即可。用户可以利用这个属性来选择行关键字,从而达到较好数据访问地域 性{locality}。举例来说,在Webtable里,通过反转URL中主机名的方式,可以把同一个域名下的网页组织成连续行。具体来说,可以把 maps.google.com/index.html中的数据存放在关键字com.google.maps/index.html下。按照相同或属性相 近的域名来存放网页可以让基于主机和基于域名的分析更加有效。
列族
一组列关键字组成了“列族”,这是访问控制的基本单位。同一列族下存放的所有数据通常都是同一类型(同一列族下的数据可压缩在一起)。列族必须先创 建,然后在能在其中的列关键字下存放数据;列族创建后,族中任何一个列关键字均可使用。我们希望,一张表中的不同列族不能太多(最多几百个),并且列族在 运作中绝少改变。作为对比,一张表可以有无限列。
列关键字用如下语法命名:列族:限定词。 列族名必须是看得懂{printable}的字串,而限定词可以是任意字符串。比如,Webtable可以有个列族叫language,存放撰写网页的语 言。我们在language列族中只用一个列关键字,用来存放每个网页的语言标识符。该表的另一个有用的列族是anchor;给列族的每一个列关键字代表 一个锚链接,如图一所示。而这里的限定词则是引用该网页的站点名;表中一个表项存放的是链接文本。
访问控制,磁盘使用统计,内存使用统计,均可在列族这个层面进行。在Webtable举例中,我们可以用这些控制来管理不同应用:有的应用添加新的基本数据,有的读取基本数据并创建引申的列族,有的则只能浏览数据(甚至可能因为隐私权原因不能浏览所有数据)。
时间戳
Bigtable表中每一个表项都可以包含同一数据的多个版本,由时间戳来索引。Bigtable的时间戳是64位整型。可以由Bigtable来 赋值,表示准确到毫秒的“实时”;或者由用户应用程序来赋值。需要避免冲突的应用程序必须自己产生具有唯一性的时间戳。不同版本的表项内容按时间戳倒序排 列,即最新的排在前面。
为了简化对于不同数据版本的数据的管理,我们对每一个列族支持两个设定,以便于Bigtable对表项的版本自动进行垃圾清除。用户可以指明只保留表项的最后n个版本,或者只保留足够新的版本(比如,只保留最近7天的内容)。
在Webtable举例中,我们在contents:列中存放确切爬行一个网页的时间戳。如上所述的垃圾清除机制可以让我们只保留每个网页的最近三个版本。
3.API
BT的API提供了建立和删除表和列族的函数.还提供了函数来修改集群,表和列族的元数据,比如说访问权限.
// Open the table
Table *T = OpenOrDie(”/bigtable/web/webtable”);
// Write a new anchor and delete an old anchor
RowMutation r1(T, “com.cnn.www”);
r1.Set(”anchor:www.c-span.org”, “CNN”);
r1.Delete(”anchor:www.abc.com”);
Operation op;
Apply(&op, &r1);
图 2: 写入Bigtable.
在BT中,客户应用可以写或者删除值,从每个行中找值,或者遍历一个表中的数据子集.图2的c++代码是使用RowMutation抽象表示来进行一系列的更新(为保证代码精简,没有包括无关的细节).调用Apply函数,就对Webtable进行了一个原子修改:它为http://www.cnn.com/增加了一个锚点,并删除了另外一个锚点.
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily(”anchor”);
stream->SetReturnAllVersions();
scanner.Lookup(”com.cnn.www”);
for (; !stream->Done(); stream->Next()) {
printf(”%s %s %lld %s\n”,
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
图3: 从Bigtable读数据.
图3的C++代码是使用Scanner抽象来遍历一个行内的所有锚点.客户可以遍历多个列族.有很多方法可以限制一次扫描中产生的行,列和时间戳. 例如,我们可以限制上面的扫描,让它只找到那些匹配正则表达式*.cnn.com的锚点,或者那些时间戳在当前时间前10天的锚点.
BT还支持其他一些更复杂的处理数据的功能.首先,BT支持单行处理.这个功能可以用来对存储在一个行关键字下的数据进行原子的读-修改-写操作. BT目前不支持跨行关键字的处理,但是它有一个界面,可以用来让客户进行批量的跨行关键字处理操作.其次,BT允许把每个表项用做整数记数器.最后,BT 支持在服务器的地址空间内执行客户端提供的脚本程序.脚本程序的语言是google开发的Sawzall[28]数据处理语言.目前,我们基于的 Sawzall的API还不允许客户脚本程序向BT内写数据,但是它允许多种形式的数据变换,基于任何表达式的过滤和通过多种操作符的摘要.
BT可以和MapReduce[12]一起使用.MapReduce是google开发的大规模并行计算框架.我们为编写了一套外层程序,使BT可以作为MapReduce处理的数据源头和输出结果.
4.建立BT的基本单元
BT是建立在其他数个google框架单元上的.BT使用google分布式文件系统(GFS)[17]来存储日志和数据文件{yeah, right, what else can it use, FAT32?}.一个BT集群通常在一个共享的机器池中工作,池中的机器还运行其他的分布式应用{虽然机器便宜的跟白菜似的,可是一样要运行多个程序,命苦的象小白菜},BT和其他程序共享机器{BT的瓶颈是IO/内存,可以和CPU要求高的程序并存}.BT依赖集群管理系统来安排工作,在共享的机器上管理资源,处理失效机器并监视机器状态{典型的server farm结构,BT是上面的应用之一}.
BT内部存储数据的格式是google SSTable格式.一个SSTable提供一个从关键字到值的映射,关键字和值都可以是任意字符串.映射是排序的,存储的{不会因为掉电而丢失},不可改写的.可以进行以下操作:查询和一个关键字相关的值;或者根据给出的关键字范围遍历所有的关键字和值.在内部,每个SSTable包含一列数据块(通常每个块的大小是64KB,但是大小是可以配置的{索引大小是16 bits,应该是比较好的一个数}).块索引(存储在SSTable的最后)用来定位数据块;当打开SSTable的时候,索引被读入内存{性能}.每次查找都可以用一个硬盘搜索完成{根据索引算出数据在哪个道上,一个块应该不会跨两个道,没必要省那么点空间}:首先在内存中的索引里进行二分查找找到数据块的位置,然后再从硬盘读去数据块.最佳情况是:整个SSTable可以被放在内存里,这样一来就不必访问硬盘了.{想的美,前面是谁口口声声说要跟别人共享机器来着?你把内存占满了别人上哪睡去?}
BT还依赖一个高度可用的,存储的分布式数据锁服务Chubby[8]{看你怎么把这个high performance给说圆喽}.一个Chubby服务由5个活的备份{机器}构成,其中一个被这些备份选成主备份,并且处理请求.这个服务只有在大多数备份都活着并且互相通信的时候才是活的{绕口令?去看原文吧,是在有出错的前提下的冗余算法}.当有机器失效的时候,Chubby使用Paxos算法[9,23]来保证备份的一致性{这个问题还是比较复杂的,建议去看引文了解一下问题本身}.Chubby提供了一个名字空间,里面包括了目录和小文件{万变不离其宗}.每个目录或者文件可以当成一个锁来用,读写文件操作都是原子化的.Chubby客户端的程序库提供了对Chubby文件的一致性缓存{究竟是提高性能还是降低性能?如果访问是分布的,就是提高性能}.每个Chubby客户维护一个和Chubby服务的会话.如果一个客户不能在一定时间内更新它的会话,这个会话就过期失效了{还是针对大server farm里机器失效的频率设计的}.当一个会话失效时,其拥有的锁和打开的文件句柄都失效{根本设计原则:失效时回到安全状态}.Chubby客户可以在文件和目录上登记回调函数,以获得改变或者会话过期的通知.{翻到这里,有没有人闻到java的味道了?}
BT使用Chubby来做以下几个任务:保证任何时间最多只有一个活跃的主备份;来存储BT数据的启动位置(参考5.1节);发现小表 (tablet)服务器,并完成tablet服务器消亡的善后(5.2节);存储BT数据的模式信息(每张表的列信息);以及存储访问权限列表.如果有相当长的时间Chubby不能访问,BT就也不能访问了{任何系统都有其弱点}.最近我们在使用11个Chubby服务实例的14个BT集群中度量了这个效果,由于Chubby不能访问而导致BT中部分数据不能访问的平均百分比是0.0047%,这里Chubby不能访问的原因是Chubby本身失效或者网络问题.单个集群里,受影响最大的百分比是0.0326%{基于文件系统的Chubby还是很稳定的}.

GFS是一个可扩展的分布式文件系统,用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上,但可以提供容错功能。它可以给大量的用户提供总体性能较高的服务。
出处:http://labs.google.com/papers/gfs.html
1、设计概览
(1)设计想定
GFS与过去的分布式文件系统有很多相同的目标,但GFS的设计受到了当前及预期的应用方面的工作量及技术环境的驱动,这反映了它与早期的文件系统明显不同的设想。这就需要对传统的选择进行重新检验并进行完全不同的设计观点的探索。
GFS与以往的文件系统的不同的观点如下:
1、部件错误不再被当作异常,而是将其作为常见的情况加以处理。因为文件系统由成百上千个用于存储的机器构成,而这 些机器是由廉价的普通部件组成并被大量的客户机访问。部件的数量和质量使得一些机器随时都有可能无法工作并且有一部分还可能无法恢复。所以实时地监控、错 误检测、容错、自动恢复对系统来说必不可少。
2、按照传统的标准,文件都非常大。长度达几个GB的文件是很平常的。每个文件通常包含很多应用对象。当经常要处理 快速增长的、包含数以万计的对象、长度达TB的数据集时,我们很难管理成千上万的KB规模的文件块,即使底层文件系统提供支持。因此,设计中操作的参数、 块的大小必须要重新考虑。对大型的文件的管理一定要能做到高效,对小型的文件也必须支持,但不必优化。

3、大部分文件的更新是通过添加 新数据完成的,而不是改变已存在的数据。在一个文件中随机的操作在实践中几乎不存在。一旦写完,文件就只可读,很多数据都有这些特性。一些数据可能组成一 个大仓库以供数据分析程序扫描。有些是运行中的程序连续产生的数据流。有些是档案性质的数据,有些是在某个机器上产生、在另外一个机器上处理的中间数据。 由于这些对大型文件的访问方式,添加操作成为性能优化和原子性保证的焦点。而在客户机中缓存数据块则失去了吸引力。
4、工作量主要由两种读操作构成:对大量数据的流方式的读操作和对少量数据的随机方式的读操作。在前一种读操作中, 可能要读几百KB,通常达 1MB和更多。来自同一个客户的连续操作通常会读文件的一个连续的区域。随机的读操作通常在一个随机的偏移处读几个KB。性能敏感的应用程序通常将对少量 数据的读操作进行分类并进行批处理以使得读操作稳定地向前推进,而不要让它来来回回的读。
5、工作量还包含许多对大量数据进行的、连续的、向文件添加数据的写操作。所写的数据的规模和读相似。一旦写完,文件很少改动。在随机位置对少量数据的写操作也支持,但不必非常高效。
6、系统必须高效地实现定义完好的大量客户同时向同一个文件的添加操作的语义。
(2)系统接口
GFS提供了一个相似地文件系统界面,虽然它没有向POSIX那样实现标准的API。文件在目录中按层次组织起来并由路径名标识。
(3)体系结构:
一个GFS集群由一个master和大量的chunkserver构成,并被许多客户(Client)访问。如图1 所示。Master和 chunkserver通常是运行用户层服务进程的Linux机器。只要资源和可靠性允许,chunkserver和client可以运行在同一个机器 上。
文件被分成固定大小的块。每个块由一个不变的、全局唯一的64位的chunk-handle标识,chunk- handle是在块创建时由 master分配的。ChunkServer将块当作Linux文件存储在本地磁盘并可以读和写由chunk-handle和位区间指定的数据。出于可靠 性考虑,每一个块被复制到多个chunkserver上。默认情况下,保存3个副本,但这可以由用户指定。
Master维护文件系统所以的元数据(metadata),包括名字空间、访问控制信息、从文件到块的映射以及块 的当前位置。它也控制系统范围的活动,如块租约(lease)管理,孤儿块的垃圾收集,chunkserver间的块迁移。Master定期通过 HeartBeat消息与每一个 chunkserver通信,给chunkserver传递指令并收集它的状态。
与每个应用相联的GFS客户代码实现了文件系统的API并与master和chunkserver通信以代表应用程序读和写数据。客户与master的交换只限于对元数据(metadata)的操作,所有数据方面的通信都直接和chunkserver联系。
客户和chunkserver都不缓存文件数据。因为用户缓存的益处微乎其微,这是由于数据太多或工作集太大而无法 缓存。不缓存数据简化了客户程序和整个系统,因为不必考虑缓存的一致性问题。但用户缓存元数据(metadata)。Chunkserver也不必缓存文 件,因为块时作为本地文件存储的。
(4)单master。
只有一个master也极大的简化了设计并使得master可以根据全局情况作出先进的块放置和复制决定。但是我们 必须要将master对读和写的参与减至最少,这样它才不会成为系统的瓶颈。Client从来不会从master读和写文件数据。Client只是询问 master它应该和哪个 chunkserver联系。Client在一段限定的时间内将这些信息缓存,在后续的操作中Client直接和chunkserver交互。
以图1解释一下一个简单的读操作的交互。
1、client使用固定的块大小将应用程序指定的文件名和字节偏移转换成文件的一个块索引(chunk index)。

2、给master发送一个包含文件名和块索引的请求。
3、master回应对应的chunk handle和副本的位置(多个副本)。
4、client以文件名和块索引为键缓存这些信息。(handle和副本的位置)。
5、Client 向其中一个副本发送一个请求,很可能是最近的一个副本。请求指定了chunk handle(chunkserver以chunk handle标识chunk)和块内的一个字节区间。
6、除非缓存的信息不再有效(cache for a limited time)或文件被重新打开,否则以后对同一个块的读操作不再需要client和master间的交互。
通常Client可以在一个请求中询问多个chunk的地址,而master也可以很快回应这些请求。
(5)块规模:
块规模是设计中的一个关键参数。我们选择的是64MB,这比一般的文件系统的块规模要大的多。每个块的副本作为一个普通的Linux文件存储,在需要的时候可以扩展。
块规模较大的好处有:
1、减少client和master之间的交互。因为读写同一个块只是要在开始时向master请求块位置信息。对于读写大型文件这种减少尤为重要。即使对于访问少量数据的随机读操作也可以很方便的为一个规模达几个TB的工作集缓缓存块位置信息。
2、Client在一个给定的块上很可能执行多个操作,和一个chunkserver保持较长时间的TCP连接可以减少网络负载。
3、这减少了master上保存的元数据(metadata)的规模,从而使得可以将metadata放在内存中。这又会带来一些别的好处。
不利的一面:
一个小文件可能只包含一个块,如果很多Client访问改文件的话,存储这些块的chunkserver将成为访问的热点。但在实际应用中,应用程序通常顺序地读包含多个块的文件,所以这不是一个主要问题。
(6)元数据(metadata):
master存储了三中类型的metadata:文件的名字空间和块的名字空间,从文件到块的映射,块的副本的位 置。所有的metadata都放在内存中。前两种类型的metadata通过向操作日志登记修改而保持不变,操作日志存储在master的本地磁盘并在几 个远程机器上留有副本。使用日志使得我们可以很简单地、可靠地更新master的状态,即使在master崩溃的情况下也不会有不一致的问题。相反, mater在每次启动以及当有 chuankserver加入的时候询问每个chunkserver的所拥有的块的情况。
A、内存数据结构:
因为metadata存储在内存中,所以master的操作很快。进一步,master可以轻易而且高效地定期在后台扫描它的整个状态。这种定期地扫描被用于实现块垃圾收集、chunkserver出现故障时的副本复制、为平衡负载和磁盘空间而进行的块迁移。
这种方法的一个潜在的问题就是块的数量也即整个系统的容量是否受限与master的内存。实际上,这并不是一个严重 的问题。Master为每个 64MB的块维护的metadata不足64个字节。除了最后一块,文件所有的块都是满的。类似的,每个文件的名字空间数据也不足64个字节,因为文件名 是以一种事先确定的压缩方式存储的.如果要支持更大的文件系统,那么增加一些内存的方法对于我们将元数据(metadata)保存在内存种所获得的简单 性、可靠性、高性能和灵活性来说,这只是一个很小的代价。
B、块位置:

master并不为chunkserver所拥有的块的副本的保存一个不变的记录。它在启动时通过简单的查询来获得这些信息。Master可以保持这些信息的更新,因为它控制所有块的放置并通过HeartBeat消息来监控chunkserver的状态。
这样做的好处:因为chunkserver可能加入或离开集群、改变路径名、崩溃、重启等,一个集群重有成百个server,这些事件经常发生,这种方法就排除了master与chunkserver之间的同步问题。
另一个原因是:只有chunkserver才能确定它自己到底有哪些块,由于错误,chunkserver中的一些块可能会很自然的消失,这样在master中就没有必要为此保存一个不变的记录。
C、操作日志:
操作日志包含了对metadata所作的修改的历史记录。它作为逻辑时间线定义了并发操作的执行顺序。文件、块以及它们的版本号都由它们被创建时的逻辑时间而唯一地、永久地被标识。
操作日志是如此的重要,我们必须要将它可靠地保存起来,并且只有在metadata的改变固定下来之后才将变化呈现给用户。所以我们将操作日志复制到数个远程的机器上,并且只有在将相应的日志记录写到本地和远程的磁盘上之后才回答用户的请求。
Master可以用操作日志来恢复它的文件系统的状态。为了将启动时间减至最小,日志就必须要比较小。每当日志的长度增长到超过一定的规模后,master就要检查它的状态,它可以从本地磁盘装入最近的检查点来恢复状态。
创建一个检查点比较费时,master的内部状态是以一种在创建一个检查点时并不耽误即将到来的修改操作的方式来组 织的。Master切换到一个新的日子文件并在一个单独的线程中创建检查点。这个新的检查点记录了切换前所有的修改。在一个有数十万文件的集群中用一分钟 左右就能完成。创建完后,将它写入本地和远程的磁盘。
(7)数据完整性
名字空间的修改必须是原子性的,它们只能有master处理:名字空间锁保证了操作的原子性和正确性,而master的操作日志在全局范围内定义了这些操作的顺序。

文 件区间的状态在修改之后依赖于修改的类型,不论操作成功还是失败,也不论是不是并发操作。如果不论从哪个副本上读,所有的客户都看到同样的数据,那么文件 的这个区域就是一致的。如果文件的区域是一致的并且用户可以看到修改操作所写的数据,那么它就是已定义的。如果修改是在没有并发写操作的影响下完成的,那 么受影响的区域是已定义的,所有的client都能看到写的内容。成功的并发写操作是未定义但却是一致的。失败的修改将使区间处于不一致的状态。
Write操作在应用程序指定的偏移处写入数据,而record append操作使得数据(记录)即使在有并发修改操作的情况下也至少原子性的被加到GFS指定的偏移处,偏移地址被返回给用户。

在一系列成功的修改操作后,最后的修改操作保证文件区域是已定义的。GFS通过对所有的副本执行同样顺序的修改操作并且使用块版本号检测过时的副本(由于chunkserver退出而导致丢失修改)来做到这一点。
因为用户缓存了会位置信息,所以在更新缓存之前有可能从一个过时的副本中读取数据。但这有缓存的截止时间和文件的重新打开而受到限制。
在修改操作成功后,部件故障仍可以是数据受到破坏。GFS通过master和chunkserver间定期的handshake,借助校验和来检测对数据的破坏。一旦检测到,就从一个有效的副本尽快重新存储。只有在GFS检测前,所有的副本都失效,这个块才会丢失。
2、系统交互
(1)租约(lease)和修改顺序
(2)数据流
我们的目标是充分利用每个机器的网络带宽,避免网络瓶颈和延迟
为了有效的利用网络,我们将数据流和控制流分离。数据是以流水线的方式在选定的chunkerserver链上线性的传递的。每个机器的整个对外带宽都被用作传递数据。为避免瓶颈,每个机器在收到数据后,将它收到数据尽快传递给离它最近的机器。

(3)原子性的record Append:
GFS提供了一个原子性的添加操作:record append。在传统的写操作中,client指定被写数据的偏移位置,向同一个区间的并发的写操作是不连续的:区间有可能包含来自多个client的数 据碎片。在record append中, client只是指定数据。GFS在其选定的偏移出将数据至少原子性的加入文件一次,并将偏移返回给client。
在分布式的应用中,不同机器上的许多client可能会同时向一个文件执行添加操作,添加操作被频繁使用。如果用传 统的write操作,可能需要额外的、复杂的、开销较大的同步,例如通过分布式锁管理。在我们的工作量中,这些文件通常以多个生产者单个消费者队列的方式 或包含从多个不同 client的综合结果。
Record append和前面讲的write操作的控制流差不多,只是在primary上多了一些逻辑判断。首先,client将数据发送到文件最后一块的所有副本 上。然后向primary发送请求。Primary检查添加操作是否会导致该块超过最大的规模(64M)。如果这样,它将该块扩充到最大规模,并告诉其它 副本做同样的事,同时通知client该操作需要在下一个块上重新尝试。如果记录满足最大规模的要求,primary就会将数据添加到它的副本上,并告诉 其它的副本在在同样的偏移处写数据,最后primary向client报告写操作成功。如果在任何一个副本上record append操作失败,client将重新尝试该操作。这时候,同一个块的副本可能包含不同的数据,因为有的可能复制了全部的数据,有的可能只复制了部 分。GFS不能保证所有的副本每个字节都是一样的。它只保证每个数据作为一个原子单元被写过至少一次。这个是这样得出的:操作要是成功,数据必须在所有的 副本上的同样的偏移处被写过。进一步,从这以后,所有的副本至少和记录一样长,所以后续的记录将被指定到更高的偏移处或者一个不同的块上,即使另一个副本 成了primary。根据一致性保证,成功的record append操作的区间是已定义的。而受到干扰的区间是不一致的。
(4)快照(snapshot)
快照操作几乎在瞬间构造一个文件和目录树的副本,同时将正在进行的其他修改操作对它的影响减至最小。
我们使用copy-on-write技术来实现snapshot。当master受到一个snapshot请求时, 它首先将要snapshot的文件上块上的lease。这使得任何一个向这些块写数据的操作都必须和master交互以找到拥有lease的副本。这就给 master一个创建这个块的副本的机会。
副本被撤销或终止后,master在磁盘上登记执行的操作,然后复制源文件或目录树的metadata以对它的内存状态实施登记的操作。这个新创建的snapshot文件和源文件(其metadata)指向相同的块(chunk)。
Snapshot之后,客户第一次向chunk c写的时候,它发一个请求给master以找到拥有lease的副本。Master注意到chunk c的引用记数比1大,它延迟对用户的响应,选择一个chunk handle C’,然后要求每一有chunk c的副本的chunkserver创建一个块C’。每个chunkserver在本地创建chunk C’避免了网络开销。从这以后和对别的块的操作没有什么区别。
3、MASTER操作
MASTER执行所有名字空间的操作,除此之外,他还在系统范围管理数据块的复制:决定数据块的放置方案,产生新数据块并将其备份,和其他系统范围的操作协同来确保数据备份的完整性,在所有的数据块服务器之间平衡负载并收回没有使用的存储空间。
3.1 名字空间管理和加锁
与传统文件系统不同的是,GFS没有与每个目录相关的能列出其所有文件的数据结构,它也不支持别名(unix中的硬连接或符号连接),不管是对文件或是目录。GFS的名字空间逻辑上是从文件元数据到路径名映射的一个查用表。
MASTER在执行某个操作前都要获得一系列锁,例如,它要对/d1/d2…/dn/leaf执行操作,则它必须获 得/d1,/d1/d2,…, /d1/d2/…/dn的读锁,/d1/d2…/dn/leaf的读锁或写锁(其中leaf可以使文件也可以是目录)。MASTER操作的并行性和数据的 一致性就是通过这些锁来实现的。
3.2 备份存储放置策略
一个GFS集群文件系统可能是多层分布的。一般情况下是成千上万个文件块服务器分布于不同的机架上,而这些文件块服 务器又被分布于不同机架上的客户来访问。因此,不同机架上的两台机器之间的通信可能通过一个或多个交换机。数据块冗余配置策略要达到连个目的:最大的数据 可靠性和可用性,最大的网络带宽利用率。因此,如果仅仅把数据的拷贝置于不同的机器上很难满足这两个要求,必须在不同的机架上进行数据备份。这样即使整个 机架被毁或是掉线,也能确保数据的正常使用。这也使数据传输,尤其是读数据,可以充分利用带宽,访问到多个机架,而写操作,则不得不涉及到更多的机架。
3.3 产生、重复制、重平衡数据块
当MASTER产生新的数据块时,如何放置新数据块,要考虑如下几个因素:(1)尽量放置在磁盘利用率低的数据块服 务器上,这样,慢慢地各服务器的磁盘利用率就会达到平衡。(2)尽量控制在一个服务器上的“新创建”的次数。(3)由于上一小节讨论的原因,我们需要把数 据块放置于不同的机架上。
MASTER在可用的数据块备份低于用户设定的数目时需要进行重复制。这种情况源于多种原因:服务器不可用,数据被 破坏,磁盘被破坏,或者备份数目被修改。每个被需要重复制的数据块的优先级根据以下几项确定:第一是现在的数目距目标的距离,对于能阻塞用户程序的数据 块,我们也提高它的优先级。最后, MASTER按照产生数据块的原则复制数据块,并把它们放到不同的机架内的服务器上。
MASTER周期性的平衡各服务器上的负载:它检查chunk分布和负载平衡,通过这种方式来填充一个新的服务器而 不是把其他的内容统统放置到它上面带来大量的写数据。数据块放置的原则与上面讨论的相同,此外,MASTER还决定那些数据块要被移除,原则上他会清除那 些空闲空间低于平均值的那些服务器。
3.4 垃圾收集
在一个文件被删除之后,GFS并不立即收回磁盘空间,而是等到垃圾收集程序在文件和数据块级的的检查中收回。
当一个文件被应用程序删除之后,MASTER会立即记录下这些变化,但文件所占用的资源却不会被立即收回,而是重新 给文件命了一个隐藏的名字,并附上了删除的时间戳。在MASTER定期检查名字空间时,它删除超过三天(可以设定)的隐藏的文件。在此之前,可以以一个新 的名字来读文件,还可以以前的名字恢复。当隐藏的文件在名字空间中被删除以后,它在内存中的元数据即被擦除,这就有效地切断了他和所有数据块的联系。
在一个相似的定期的名字空间检查中,MASTER确认孤儿数据块(不属于任何文件)并擦除他的元数据,在和MASTER的心跳信息交换中,每个服务器报告他所拥有的数据块,MASTER返回元数据不在内存的数据块,服务器即可以删除这些数据块。
3.5 过时数据的探测
在数据更新时如果服务器停机了,那么他所保存的数据备份就会过时。对每个数据块,MASTER设置了一个版本号来区别更新过的数据块和过时的数据块。
当MASTER授权一个新的lease时,他会增加数据块的版本号并会通知更新数据备份。MASTER和备份都会记 录下当前的版本号,如果一个备份当时不可用,那么他的版本号不可能提高,当ChunkServer重新启动并向MASTER报告他的数据块集时, MASTER就会发现过时的数据。
MASTER在定期的垃圾收集程序中清除过时的备份,在此以前,处于效率考虑,在各客户及英大使,他会认为根本不存 在过时的数据。作为另一个安全措施, MASTER在给客户及关于数据块的应答或是另外一个读取数据的服务器数据是都会带上版本信息,在操作前客户机和服务器会验证版本信息以确保得到的是最新 的数据。
4、容错和诊断
4.1 高可靠性
4.1.1 快速恢复
不管如何终止服务,MASTER和数据块服务器都会在几秒钟内恢复状态和运行。实际上,我们不对正常终止和不正常终止进行区分,服务器进程都会被切断而终止。客户机和其他的服务器会经历一个小小的中断,然后它们的特定请求超时,重新连接重启的服务器,重新请求。
4.1.2 数据块备份
如上文所讨论的,每个数据块都会被备份到放到不同机架上的不同服务器上。对不同的名字空间,用户可以设置不同的备份级别。在数据块服务器掉线或是数据被破坏时,MASTER会按照需要来复制数据块。
4.1.3 MASTER备份
为确保可靠性,MASTER的状态、操作记录和检查点都在多台机器上进行了备份。一个操作只有在数据块服务器硬盘上 刷新并被记录在MASTER和其备份的上之后才算是成功的。如果MASTER或是硬盘失败,系统监视器会发现并通过改变域名启动它的一个备份机,而客户机 则仅仅是使用规范的名称来访问,并不会发现MASTER的改变。
4.2 数据完整性
每个数据块服务器都利用校验和来检验存储数据的完整性。原因:每个服务器随时都有发生崩溃的可能性,并且在两个服务器间比较数据块也是不现实的,同时,在两台服务器间拷贝数据并不能保证数据的一致性。
每个Chunk按64kB的大小分成块,每个块有32位的校验和,校验和和日志存储在一起,和用户数据分开。
在读数据时,服务器首先检查与被读内容相关部分的校验和,因此,服务器不会传播错误的数据。如果所检查的内容和校验 和不符,服务器就会给数据请求者返回一个错误的信息,并把这个情况报告给MASTER。客户机就会读其他的服务器来获取数据,而MASTER则会从其他的 拷贝来复制数据,等到一个新的拷贝完成时,MASTER就会通知报告错误的服务器删除出错的数据块。
附加写数据时的校验和计算优化了,因为这是主要的写操作。我们只是更新增加部分的校验和,即使末尾部分的校验和数据已被损坏而我们没有检查出来,新的校验和与数据会不相符,这种冲突在下次使用时将会被检查出来。
相反,如果是覆盖现有数据的写,在写以前,我们必须检查第一和最后一个数据块,然后才能执行写操作,最后计算和记录校验和。如果我们在覆盖以前不先检查首位数据块,计算出的校验和则会因为没被覆盖的数据而产生错误。

在空闲时间,服务器会检查不活跃的数据块的校验和,这样可以检查出不经常读的数据的错误。一旦错误被检查出来,服务器会拷贝一个正确的数据块来代替错误的。

4.3 诊断工具
广泛而细致的诊断日志以微小的代价换取了在问题隔离、诊断、性能分析方面起到了重大的作用。GFS服务器用日志来记 录显著的事件(例如服务器停机和启动)和远程的应答。远程日志记录机器之间的请求和应答,通过收集不同机器上的日志记录,并对它们进行分析恢复,我们可以 完整地重现活动的场景,并用此来进行错误分析。
5 测量
5.1 测试环境
一台主控机,两台主控机备份,16台数据块服务器,16台客户机。
每台机器:2块PIII1.4G处理器,2G内存,2块80G5400rpm的硬盘,1块100Mbps全双工网卡
19台服务器连接到一个HP2524交换机上,16台客户机俩接到领外一台交换机上,两台交换机通过1G的链路相连。




本博客为学习交流用,凡未注明引用的均为本人作品,转载请注明出处,如有版权问题请及时通知。由于博客时间仓促,错误之处敬请谅解,有任何意见可给我留言,愿共同学习进步。
posted on 2008-03-09 17:41 Jack.Wang 阅读(5876) 评论(1)  编辑  收藏 所属分类: 开发技术架构师篇

Feedback

# re: Google的搜索速度为什么这么快? 2008-03-28 17:05 net
google搜索为什么这么快?  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: