Linux Cluster案例分析之 Google的Linux集群解决方案(2)

82c7q4264i

　　原文地址 http://www.opendigest.org/article.php/538

 
4、Google的存储系统
Google集群收集到的Web页面就已达到80多亿张，另外它还有十亿多张图片。文献[5]中报道Google集群中的数据容量在2004年就达到了5PB。作为一个容量巨大且访问频繁的存储系统，Google却没有采用流行的网络存储技术和附网存储技术，甚至就连比较廉价的磁盘阵列也没使用。Google采用的存储方法是用最常见、最普通的一个PC机中带两个硬盘的存储方式。Google放弃主流的并行海量数据存储技术，采用健壮性较低的PC机带硬盘存储的方式最主要的原因是希望降低成本。虽然这种存储方式不太可靠，但通过GFS可实现高效、可靠存储，已被实践检验是有效的海量存储解决方法。
2003年市场上最常见的PC机硬盘存储容量是80G。根据文献[4]中报道，每台PC机中配有两个80G的硬盘，不难计算出Google集群的总容量是80G×15,000×2＝2,400,000G＝2.4PB。由于可靠性和可用性对Google十分重要，不是所有的存储区间都用来存储有效数据。为了提高可用性，有一半的硬盘是作镜像存储。当一个硬盘出现故障，或者数据读写错误时，可用另一个硬盘启动系统或访问其中的数据。集群中的每台PC机都存储了一份独立完整的操作系统，又有一部分存储区域去存放系统软件，因此实际有效存储空间比1.2PB还小。同样出于价格成本因素考虑，Google集群中没有使用SCSI接口的硬盘。使用SCSI接口的硬盘，不仅硬盘自身价格高，且还需转接卡。为了提高数据读取速度，Google集群中的硬盘转速比较高，从而降低旋转等待时间。
2003年底，Google中每台PC机中竟然配置了高达2GB的内存。由于每个chunk高达64MB，使用大内存对提高系统的性能有良好效果。曾对存储器容量对系统性能的影响进行测试，发现存储器系统不是整个系统性能的瓶颈。
 
5、Google的可靠性和可用性
可靠性是指系统正常运行时间，可用性是系统正常运行时间与正常运行时间以及故障维修时间之和的比率[11]，高可用性是评价超级计算机和服务器系统的关键指标之一。作为商业网站，Google集群必须能保证每周7天、每天24小时都正常工作。即使是在系统维护操作时，也不能让整个系统停机。一万多台PC机，总会存在各种各样的故障和异常，几乎所有故障都会降低系统的可用性。即使系统不出故障，Google集群中的PC机每两年也会更新一次。PC机更新是在硬件上彻底更换，更新的过程必定会终止一部分机器服务。设备更新比较耗时，15,000台机器同时更新显然不是两个小时内可以完成。以下分析Google集群提高系统可用性的方法。
首先，Google是Web搜索引擎，可用性要求比较弱。搜索引擎的可用性需求与银行、电信业务中的可用性存在区别，这些区别导致了不同的可用性维护策略。对银行业务连续执行同样的请求，得到的响应必须一致。但对Web搜索引擎，用户期望的可用性是只要能访问Google的入口，键入检索词，几秒钟后能得到检索结果即可。2004年4月17日,我输入“华中科技大学”一词进行检索，得到了1,170,000个检索结果；而在4月21日执行同样的检索，我只得到了917,000条结果。显然两次检索结果差异巨大，但实际上普通用户很难发现这种差异，甚至根本就没考虑过这种现象。
Google中对Index和Web页面数据都采用分布式存储。每台PC机都可能出故障，出现故障后需要一定的故障维修周期。在维修周期内，该机器中所存储的数据可能就不能正常访问，因此导致反馈给用户的检索结果减少。因此，连续多次执行同样的检索请求，但检索结果不一致现象就能得到合理解释。这种非严格的可用性，给Google的维护以及技术方案选择提供了宽松的环境。相反，银行则不得不采用昂贵的硬件设备来维持系统的严格可用性。
其次，Google通过分布在不同地区的多个镜像站点来提供系统的可用性。Google集群耗电量巨大，占地面积大，停电是导致系统可用性降低的致命因素。Google公司位于加州，加州近年来出现了能源短缺、电力供应紧张现象，近年来加州曾多次出现大面积停电现象[12]。单机或服务器保证电力供应方法是采用UPS电源，而Google集群由于功耗太大，估计采用UPS的可能性比较小，公司自备发电机发电可能是更可行的方法。Google仅是一个Web搜索引擎，即使是公司内部有备用电源，也不能保证当地区停电时网站正常提供网络服务功能。原因是Google与外界连接的通信网络也因停电而终止工作，因此无论Google集群的可用性有多高，只要通信网络具有单一性，它依然无法保证高可用性。
另外，地震、恐怖袭击等其它灾难性事故也将导致单一Google集群无法保证高可用性。加州是太平洋板块和美洲板块的交界处，地震活动比较频繁。2005年4月16日12时18分在加州WSW of Mettler发生了5.1级的地震[13]；2003年12月23日在加州发生了里氏6.5级的地址，导致多人死亡。运行在地震频繁地区的大型机有必要考虑地震对整个系统可用性的影响，实际上Google公司的研究人员也考虑了该问题，并采取了相关对策。
2001年Google有三个镜像站点，两个分布在加州的硅谷，另一个在美国东海岸的弗吉尼亚。每个Google站点都采用OC48 (2488Mbit/sec)的带宽连接到因特网，硅谷中的两个临近站点还用一根OC12的光纤互连，以便紧急情况下或网络故障时两个镜像站点可共享一根OC48光纤连接互联网。弗吉尼亚州的那个站点在2003年也有了自己的镜像，其连接方法就和硅谷中两个镜像站点的互连方法一致。从一个站点变成地理位置上分离的四个站点，软硬件设备的成本就增加了三倍，但可用性几乎达到了100%。中国用户访问Google经常不通，估计是通信网络故障原因较多。这些来自网络中的技术的与非技术处理是Google公司无法解决的。
高度冗余提高了Google的可用性，但Google公司对镜像站点的投资并不是真正的冗余投资。服务器常见的冗余方式是双机备份，当一台机器出现故障时另一台机器立即接管故障机器上的任务。简而言之，就是两台服务器实际上只具备一台服务器的工作效率。如果服务器工作稳定，有一半投资是冗余。由于搜索引擎对可用性要求不是很严格，且每个Google站点自身有很高的可用性，Google的镜像站点不是另一个站点的热备份。通过基于DNS的负载均衡方法，DNS服务器把域名地址www.google.com解析成不同的IP地址，把查询请求分配到四个镜像站点。基于DNS的负载均衡方法并不是Google首创，它是计算机网络技术中的一个常见技巧，简单高效。如DNS服务器收到一个来自中国大陆地区的搜索请求，只要加州的两个服务器不是特别繁忙，它就把域名地址解析成加州两个站点中较为空闲的一台。请求在加州处理，降低了网络通信中的线路传输延时，对降低响应时间有好处。同理，来自欧洲用户的请求则解析到弗吉尼亚的镜像站点。四个站点中的某个站点出现故障或过于繁忙，DNS服务器可以暂时不把请求分配到该站点，而是转移到其它的三个站点，因此Google看来是利用冗余的方法来提高系统的可用性,但建立镜像站点实际上几乎算不上冗余投资。这从一贯坚持节省投资成本的Google而言，无疑是一个很好的设计方案。
第三、Google坚持采用软件方案来提高可用性，而不是使用硬件技术。服务器和大型机中的冗余一般是用硬件，硬件方式意味着更多投资。Google公司的维护人员可以开发软件，如GFS，采用软件方法可达到提高可用性的效果。Google是最大的Linux用户，它可把应用需求直接向Red Hat公司提出，让对方的设计人员开发面向Google的操作系统[14]。
 
6、Google如何实现高并行性
如何提供系统的并行性是大型机设计和开发的关键问题，并行性高则意味着系统的加速比大，有利于系统的可扩展性。系统的加速比与实际应用自身的特性紧密相关，如果应用中计算部分所占比例小，而多处理器之间的通信、同步操作多，则并行性难以提高。Google集群的设计者在多篇论文中都表明Google集群的处理能力与PC机数量呈线形关系[4]，显然这是并行计算中所期望的理想状态。本文认为Google集群提高并行性的技术可归纳为宏观意义上的多发射、多流水。

 

图5 请求处理流程

图1示出Google的三大功能模块：负责Web页面收集的crawlers、负责Index检索的Index server、以及负责文档检索的Doc Server。Crawlers只负责从网络中不断的采集网页，它与用户的检索请求没有直接联系；Index以及页面检索是直接为用户的请求服务。三者之间通信和同步操作少，适合并行工作。Crawlers以固定周期去发现和采集网络中的Web页面，1998年、2000年、2001年以及2003年的文献关于采集周期的报道都是每一个月更新一次。每个crawler所采集页面的地址是由系统分配的，因为分配的地址不同，多台执行crawler程序的PC机可以并行操作。只要Google集群连接到网络的带宽不存在瓶颈，则数据采集信息处理能力与PC的数量成正比增长。
一个请求在Google中的处理过程如图2和图5所示[15]。步骤1是用户通过Web页面将检索词发送到Google Web Server。步骤2是WWW服务器将查询发送到索引服务器。目前在步骤2执行之前，Google做了一些小处理，如：判断检索词的英文拼写是否正确，如果出错向用户给出提示信息。Google盈利的主要来源之一是广告业务，因此在步骤2执行之前，还有一些关于附加广告操作。
Google Web Server对每个请求所作处理较少，一般不是系统的瓶颈。Index检索与Doc检索之间存在严格的时序关系，即对同一个请求只有在Index server处理完成后，才能去访问Doc Server。把一个请求分成两次查询主要是从效率角度考虑，因为原始Web页面有80多亿张,直接检索则范围太多，检索时间长。Google先对容量大小为数TB甚至是几个PB的原始数据建立高达数MB的索引描述信息，根据Index检索结果，只对部分Web页面进行搜索。Index检索完成后，Index服务器不再处理该请求，而是直接去处理下一个请求。当Index服务器在为第n个请求作检索的时候，Doc服务器可能是在为第n-1个请求进行搜索。Index服务器和Doc服务器在同一时刻并不处理同一个请求，二者可并行为用户服务。若把每一个宏观检索类比为流水线中的功能部件，那么Index服务器和Doc服务器是流水线执行。
多个Doc服务器可以得到数以百万计的检索结果，如本文中描述的对“华中科技大学”检索。多个结果在反馈给用户之前，必须进行一次信息汇总和结果评价排序操作，最后将最好的结果在前几十条记录中反馈给用户。
多发射技术在Google中也有应用。从站点层次来看，Google有多个镜像站点，每个镜像站点之间可以并行为用户服务。位于美国东海岸的镜像站点为美国东部和欧洲用户服务，而加州的镜像站点并行的为亚洲及美国西部用户服务。从站点内部来看，Google Web Server并非是一台PC机，它肯定有多台PC机负责该操作。总之，在同一时刻Google Web Server可以接受多个用户请求，并可以向Index发出多条查询任务。类比单个芯片内部存在多条流水线的现代CPU系统，我们可以认为Google集群中有多条流水线，是一个多发射系统。

表3 每秒Google处理的请求数和Google中的页面数量

时间	Web页面数	每天处理的请求数(百万)
1998年		0.01
1999年1月-6月		0.5
1999年8月-11月		3
2000年5月-6月		18
2000年11-12月	1.3Billion	60
2001年1月-2月		100
2001年11月-12月	3Billion
2002年7月-8月	2.4Billion
2002年11月-12月	4Billion
2004年1月-2月	4.28Billion
2004年11月-12月	8Billion
2005年4月	8Billion	200[2]

 
互联网的普及导致Google在单位时间内处理的请求越来越多。表1示出了自1998年以来，Google平均每天处理的检索请求数目增长情况。表1中的数据来自Google公司提供的介绍信息[15]。关于2005年4月份平均每天处理的用户请求数是超过2亿，即大于200M。
7. 结束语
Google是世界上最成功的网络搜索引擎，它在创办之初就发现并坚持了一个十分正确的搜索结果评价标准:精确率高于查全率，并设计了比较科学的网页评价算法。在Google最具原创性的两篇论文中，对来自硬件领域的可扩展性、可靠性、可用性根本都未曾涉及。Google公司创始人在攻读博士期间发表的论文主要是讲述Google的软件体系、数据结构和页面评价算法，由此可判断他俩擅长软件设计，而不是偏向硬件的计算机系统结构。
随着Belwolf的成功，集群技术成为今年来国际上大型机和高性能计算领域的主流技术。Google集群的设计者在多年前就巧妙的利用集群技术，无疑是一个十分正确的技术选择。因为没有哪台大型机能以如此低的价格，提供如此强的可扩展性。
Google是世界上应用效率最高的集群系统之一，但对集群技术自身的发展它并没有作出太多贡献。Google集群在某种程度上来看，也许不能成为严格的集群服务器，甚至更像一个巨大的计算或存储局域网。因为集群系统研究中最关键的技术是单一系统映象,而所有关于Google集群的介绍中都没有涉及。估计Google集群是通过网络的方式来进行负载均衡和数据访问，不具有严格的集群定义。随着人们对集群定义的逐步放松，特别是Patterson教授和Hennessy教授的《计算机系统结构：一种量化的研究方法》中用很大篇幅详细介绍Google集群之后，它就变成了大型集群成功应用的典范。Hennessy教授既是Stanford大学的校长，又是Google公司的董事。作为计算机系统结构领域的国际著名学者，他有可能直接参与并指导了Google集群的设计和开发，在目前所有关于Google集群的文献中，文献[6]是最全面和细致的一篇。Google集群能否称得上严格意义上的集群，在国外也有争议。但无论是否是集群，对Google而言没有太多意义。因为它已成功的解决了一个大计算量、大存储量、高实时性的应用需求，并且多年来工作得很好。
总之,从计算机系统结构角度来看，我最推崇Google集群研究者和维护者的观点：用最少的钱、用最成熟的技术去构建稳定、高性能、高可用性的系统。目前国内也有很多耗费巨资购买的服务器或者大型机，而真正得到高效应用较少。有些计算或存储服务需求比Google要宽松得多，为什么我们不改变思路，用成熟的技术去构建一个自己的大型计算机系统？本文对Google集群的评价是：用成熟、廉价的技术去构建了一个先进、卓越的计算机系统。这种实用主义的态度，值得我们未来在计算机硬件系统设计和软件系统开发中学习。
 
 
致谢
本文是华中科技大学计算机学院谢长生教授讲授的《高等计算机系统结构专题》课程的课程论文，感谢他提供了Google集群系统结构分析这个有趣的问题、并深入浅出的讲授了计算机系统结构领域的技术进展及思维方法。
 
 
参考文献
[1] The Google Timeline, http://www.google.com/corporate/timeline.html.
[2] The World’s 500 Most Influential Brands, http://brand.icxo.com/brand500/top500_1.htm.
[3]Sergey Brin and Lawence Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine,” Computer Networks, Vol. No. 1998, pp. 107-117.
[4]Luiz André Barroso, Jeffrey Dean, and Urs Hölzle, “Web Search for a Planet: The Google Cluster Architecture,” IEEE Micro, Vol. 23, No.2, March 2003, pp.22-28.
[5] Chris Mellor, Google’s Storage Strategy, http://www.techworld.com.
[6]John L. Hennessy, David A. Patterson, “Computer System Architecture: A Quantitative Approach, (3rd edition)”, Morgan Kaufmann, May 15, 2002.
[7] TOP500 supercomputer, http://www.top500.org.
[8] List of November 2002, http://www.top500.org/list/2002/11/
[9] Google's cluster, http://www.beowulf.org.
[10]Sanjay Ghemawat, Howard Gobioff and Shun-Tak Leung, “The Google File System,” Proceedings of the nineteenth ACM symposium on Operating systems principles, October 2003.
[11] Kai Hwang and Zhiwei Xu, “Scalable parallel Computing, Technology, architecture, programming,” WCB/McGraw-Hill, 1998.
[12] http://tech.sina.com.cn/i/w/65936.shtml.
[13] Recent Earthquakes in California and Nevada, http://quake.usgs.gov/recenteqs/index.html.
[14] Red Hat Linux Powers Google’s Award-Winning Search Engine, Business Wire, May 30, 2000.
[15] Press Center of Google, http://www.google.com/press/descriptions.html.