Google Linux Cluster
1. 前言 Google公司于1998年由Stanford大學(xué)計算機系的兩個(gè)博士研究生Sergey Brin和Larry Page創(chuàng )立[1]；2000年被《Internet Life
》雜志評為“互聯(lián)網(wǎng)上最好的搜索引擎”[1],今年被世界品牌實(shí)驗室評為2005年世界品牌500強中的第三名[2]。與曾經(jīng)最有影響的搜索引擎Yahoo相比，Google在創(chuàng )立之初在技術(shù)和經(jīng)濟資源方面并不具備太多優(yōu)勢，是什么原因導致網(wǎng)絡(luò )用戶(hù)放棄Yahoo、接受Google,我認為對搜索結果質(zhì)量評價(jià)的正確觀(guān)點(diǎn)可能是最主要的原因。1998年期間，網(wǎng)絡(luò )中的Web頁(yè)面數量較小，可以采用手工方法對每一個(gè)頁(yè)面進(jìn)行人工分類(lèi)。對一個(gè)用戶(hù)查詢(xún)請求，可以查全所有的Web頁(yè)面，然后反饋所有相關(guān)頁(yè)面鏈接。然而在1998年，Sergey Brin和Larry Page在《Computer Networks》雜志上合作發(fā)表論文[3]卻提出了不同的觀(guān)點(diǎn)，他們指出：Google追求的高質(zhì)量網(wǎng)絡(luò )搜索不是擁有盡可能高的查全率，而是反饋給用戶(hù)的前幾十條鏈接必須具有很高的精確率。基于該理念，Sergey Brin 和Larry Page在Google搜索引擎中采用了根據鏈接數量來(lái)判定頁(yè)面質(zhì)量的PageRank算法，該算法后來(lái)成為網(wǎng)頁(yè)評價(jià)研究中的一個(gè)很著(zhù)名的算法。由于PageRank算法的分析和1Technical Report, April 2005 Google Linux Cluster 的系統結構分析 改進(jìn)工作已有很多相關(guān)研究和評論，本文不對此進(jìn)行討論。本文只關(guān)注Google服務(wù)器 技術(shù)。 1998年Google創(chuàng )立之初，該公司的數據中心放置在Larry在Stanford大學(xué)的宿舍內，且公司的第一筆資金只有100萬(wàn)美元[1]。從當時(shí)的服務(wù)器、大型機價(jià)格來(lái)看，100萬(wàn)美元即使全部用來(lái)購買(mǎi)服務(wù)器，也不可能購買(mǎi)十分先進(jìn)、高檔的服務(wù)器或大型機。數據中心放置在學(xué)生宿舍，受房間面積限制，大型機及附屬設備所需占地面積也不可能得到滿(mǎn)足。同時(shí)大型機對降溫要求很高，一般學(xué)生宿舍也很難得到保障。關(guān)于大型機所需供電、降溫需求，以及普通房屋供電負荷相關(guān)參數可參考文獻[4]。因此根據以上信息，可判斷1998年Google不太可能采用、也很難有條件采用傳統的大型機
作為搜索引擎的服務(wù)器。 1998年以后互聯(lián)網(wǎng)發(fā)展速度越來(lái)越快，無(wú)論是Web頁(yè)面數量，還是用戶(hù)提交的搜索請求數量都在短短幾年內增長(cháng)了數十倍甚至上百倍。Google搜索引擎卻沒(méi)有因為計算量和存儲量高速增長(cháng)而變得不堪重負，相反它一直爭取在0.5秒時(shí)間內處理完成用戶(hù)請求。如今Google完成查詢(xún)請求后，還把查詢(xún)所耗費的時(shí)間反饋給用戶(hù)。以2005年4月21日上午10時(shí)51分在華中科技大學(xué)校園網(wǎng)內輸入“華中科技大學(xué)”一詞進(jìn)行檢索為例，Google反饋了917,000個(gè)查詢(xún)結果，查詢(xún)時(shí)間卻僅為0.22秒。對同一個(gè)檢索詞在不同時(shí)間段進(jìn)行檢索，搜索引擎消耗的時(shí)間不盡相同，因為處理一個(gè)請求所需時(shí)間不僅受搜索引擎中待檢索頁(yè)面的數量、大小限制，也與整個(gè)系統當前的繁忙程度有關(guān)。在0.5秒內完成數據檢索，Google服務(wù)器應該是高性能計算的一個(gè)成功典范。作為面向全球用戶(hù)的商業(yè)搜索引擎，由于全球存在時(shí)差，Google必須保證每天24小時(shí)都能正常運行，這對Google服務(wù)器的可用性提出了巨大的挑戰。 Google本是數學(xué)中的一個(gè)名詞，它表示一個(gè)十分巨大的數：1后面跟100個(gè)0（即10100）[3]。Sergey Brin 和Larry Page使用Google作為自己的搜索引擎和公司名的主要原因是希望自己設計的Web搜索引擎將來(lái)能夠支持十分巨大的Web頁(yè)面檢索[3]。至2005年4月21為止，Google中所收集的Web頁(yè)面數量已經(jīng)達到8,058,044,651張（見(jiàn)Google頁(yè)面）。雖然該值與Google所描述數量還相差甚遠，但它成為如今世界上收集Web頁(yè)面最多的搜索引擎。 本文內容結構安排如下：
第二部分介紹Google集群（機群）的邏輯結構和物理結構；
第三部分討論Google的文件系統；
第四部分介紹Google的存儲系統和存儲策略；
第五部分討論Google的高可用性和可靠性；
第六部分討論Google集群在計算和存儲中的高并行性。
最后根據Google集群的成功經(jīng)驗對大型機或大型集群開(kāi)發(fā)提出一些思考。
2、Google集群的邏輯結構和物理結構 為Google搜索引擎提供硬件支持的不是傳統的大型機和服務(wù)器，而是技術(shù)含量低、廉價(jià)的集群技術(shù)。至2003年4月，Google集群已集成15,000臺PC機，成為當時(shí)世界上最大的PC機集群系統[4]。文獻[5]中指出預計到2004年底，Google集群中的PC機臺數會(huì )超過(guò)18,000臺，外存儲器容量達到5PB。在2000年，Google集群中的CPU個(gè)數（每臺PC機中僅有一個(gè)CPU）只有4,000個(gè)，2003年初它便增加到30,000（每臺PC機中有兩個(gè)CPU），因此有理由判斷如今Google集群中的CPU個(gè)數可能達到或者超過(guò)40,000個(gè)。為了獲得Google集群的最新信息，在本文寫(xiě)作過(guò)程中，我曾通過(guò)電子郵件向oogle Fellow Urs H?lzle博士（文獻[4]的通信作者）詢(xún)問(wèn)Google集群當前的PC機數目、PC機具體配置等問(wèn)題，但沒(méi)有得到回復。以往向國外學(xué)者詢(xún)問(wèn)論文所涉及的問(wèn)題，一般都能很快得到詳細答復。本文寫(xiě)作過(guò)程中，我曾在IEEE, ACM, ScienceDirect等專(zhuān)業(yè)科研論文數據庫中進(jìn)行多次檢索，以及在Yahoo, Google等通用Web搜索引擎中進(jìn)行搜索，還查看了Google Lab主頁(yè)中列出的論文清單，但獲得的最新報道僅僅是2004年4月發(fā)表的文獻[5]。因此，不妨可猜測：Google集群中的PC機數量、PC機具體配置信息可能是搜索引擎公司的重要商業(yè)秘密，不便公開(kāi)。 文獻[3]早在1998年就介紹了Google搜索引擎的邏輯結構如圖1所示。文獻[3]是至今
2Technical Report, April 2005 Google Linux Cluster 的系統結構分析關(guān)于Google搜索引擎邏輯結構描述最為清晰的一篇論文，并且該文獻中作者明確表示這也是他們閱讀范圍內第一篇詳細描述Web搜索引擎結構的論文。由于圖1僅是Google搜索引擎的邏輯結構圖，我們根據圖1判斷服務(wù)器采到底是采用SMP構架的服務(wù)器，或者是MPP構架的服務(wù)器，還是集群服務(wù)器。圖1對理解搜索引擎的邏輯功能模塊和檢索操作流程很有幫助，對我們在后面分析系統的并行性有幫助。 圖1中同一個(gè)功能模塊如果出現多次，如crawlers，則表示該模塊存在多個(gè)并行的實(shí)例。多個(gè)并行實(shí)例既可以理解為一臺機器中的多個(gè)進(jìn)程或線(xiàn)程，也可以理解成在多臺PC機上執行的進(jìn)程。以crawlers為例，在Google原型系統設計之初，可能就是同一臺機器上多個(gè)線(xiàn)程，而在2000年以后可能就是多臺PC機上都在運行crawlers程序。文獻[3]中對每個(gè)功能模塊都進(jìn)行詳細說(shuō)明，感興趣者可直接閱讀文獻[3]。 圖1、Google的邏輯結構圖 圖2是最新的關(guān)于Google服務(wù)器系統結構的介紹[4],該文通信作者Urs H?lzle博士由于對Google公司的發(fā)展作出了突出貢獻，被授予Google Fellow榮譽(yù)稱(chēng)號。文獻[4]是我們收集到的資料中唯一專(zhuān)門(mén)討論Goolge集群的系統結構的論文。從1998年到2003年，時(shí)間相隔五年，但比較圖1和圖2卻發(fā)現二者并沒(méi)有本質(zhì)區別。圖1中的系統結構五年后依然在更復雜、數據和計算更密集的應用環(huán)境中繼續使用，這驗證了圖1中的Web搜索引擎邏輯功能結構具有很好的可擴展性。 圖2 Google的邏輯結構圖 關(guān)于Google集群的物理
結構最早的全面介紹可能是2001年出版的計算機系統結構經(jīng)典3Technical Report, April 2005 Google Linux Cluster 的系統結構分析
教材《Computer Architecture: A Quantitative Approach》一書(shū)[6]。文獻[6]中專(zhuān)門(mén)把Google集群作為大型集群的綜合性實(shí)例，從PC機內部配置，PC機在機柜中的布局、集群系統的能耗和散熱處理、網(wǎng)絡(luò )交換設備、存儲設備等多個(gè)方面進(jìn)行介紹。由于文獻[6]在計算機系統結構教科書(shū)中的權威地位，它的出版使Google集群得到了大家的廣泛關(guān)注。由于文獻[4]發(fā)表時(shí)間比文獻[5]晚兩年，以下用文獻[4]中公布的PC機配置信息來(lái)估算Google集群的計算性能，以及它在TOP500中的排名位置。 浮點(diǎn)數峰值速率是大型機設計、開(kāi)發(fā)和評價(jià)的一個(gè)重要指標。TOP500在對大型機進(jìn)行性能排名時(shí)有兩個(gè)重要指標，一個(gè)是系統的理論浮點(diǎn)數運算速率，另一個(gè)是實(shí)際的Linpack測試浮點(diǎn)數運算速率[7]。文獻[6]中指出每臺PC機中只有一個(gè)奔騰800MHZ的CPU，文獻[3]中報道在2002年底一臺PC機中有兩個(gè)2G Intel Xeon的處理器。15,000臺PC機則意味著(zhù)Google集群中有30,000個(gè)并行的CPU。從因特網(wǎng)上不難查到2GHZ Xero處理器每個(gè)時(shí)鐘周期內可完成兩次浮點(diǎn)數運算，因此可得到2002年底Google集群的理論浮點(diǎn)數運算速率為2G×2×30,000=120,000Gflops=120TFlops。對比2002年11月份的全球TOP500排名列表[7]，發(fā)現其中排名第一的地球模擬器的峰值速率是40,960Gflops，Google集群的峰值速率是地球模擬器的近三倍。由于地球模擬器采用向量計算機技術(shù)，我們不放把Google集群與TOP500中排名第二的ASCI Q作比較。 ASCI Q是NASA(National Aeronautics and Space Administration)第五臺高性能計算機，在參加2002年11月份的TOP500測試時(shí)它的基本配置是4096個(gè)1.25GHZ處理器，Linpack測試速度7727GFlops，峰值速率為10240Gflops [9]。ASCI Q在2002年沒(méi)有還沒(méi)有完全開(kāi)發(fā)完畢，它計劃在未來(lái)達到11,968個(gè)處理器、12TB內存以及600TB的磁盤(pán)容量的規模。比較2002年底的Google集群與ASCI Q,發(fā)現Google集群的處理器個(gè)數幾乎是ASCI Q的八倍，且每個(gè)CPU的主頻較高，理論峰值速率Google集群是ASCI Q的十二倍。 鑒于Google集群是Google公司自己搭建，且沒(méi)有采用如MyriNet價(jià)格昂貴通信效率高的大型機專(zhuān)用高速通信網(wǎng)絡(luò )設備互連。由于無(wú)法收集到Google集群作Linpack測試的數據，但可以基本肯定的是它作Linpack測試的可實(shí)際運用速率與峰值速率之比要低于地球模擬器和ASCI Q。因此在Google集群上作Linpack測試的實(shí)際速率不一定比ASCI Q高，但由于它的理論峰值太高，即使可利用率低至0.5%（觀(guān)察TOP500中的記錄，可知該數值一般都大于30%），它依然在TOP500的前一百名之內（因為第100名機器是558GFlops）。 本文寫(xiě)作過(guò)程中，我查閱了2000年以來(lái)TOP500的十次排名記錄，都沒(méi)有發(fā)現Google集群。參與TOP500排名的機器是遵循自愿原則（可以在網(wǎng)上填表），可以推測Google有進(jìn)入前100名的實(shí)力，卻沒(méi)有上榜，其最大可能就是沒(méi)有參與TOP500排名。Google集群不愿意公布性能數據，從很難檢索到關(guān)于它系統結構分析的論文也是一個(gè)反映。 因此盡管在TOP500中沒(méi)有發(fā)現Google集群，但無(wú)需質(zhì)疑的是它無(wú)論是在浮點(diǎn)數計算能力還存儲容量方面都是世界上最頂級的計算機之一。某些大型機有很高的性能，且有很高的技術(shù)含量，卻沒(méi)有出現在TOP500名單中的情況其實(shí)在我國也有。如眾所周知的神威巨型計算機，它不僅具備很高的峰值速率，也具有良好的實(shí)際性能，至少在國內它與曙光公司、聯(lián)想公司開(kāi)發(fā)的巨型機具有相當的性能，然而在TOP500上一直沒(méi)有出現它的名字。 國外關(guān)于利用集群技術(shù)開(kāi)發(fā)大型機的Beowulf論壇中已有人提出：設計大型機，并注重它能否進(jìn)入TOP500以及在TOP500中的名次只是學(xué)術(shù)界的一個(gè)游戲而已[9]。利用集群構架開(kāi)發(fā)的大型機，進(jìn)入TOP500其實(shí)不能代表太高的技術(shù)水平，這應該是近年來(lái)關(guān)于大型機開(kāi)發(fā)的一個(gè)共識。如今國內的大型機開(kāi)發(fā)技術(shù)已經(jīng)達到較高的水平，未來(lái)幾年無(wú)需再把能否進(jìn)入TOP500前十名當作十分重要的目標。因為我們過(guò)去設計的一些大型機由于應用效率不高，已經(jīng)造成了不少資源閑置現象，關(guān)于該類(lèi)報道在互聯(lián)網(wǎng)上比較多。 Google集群完全能進(jìn)TOP500，但它卻不參加排名。Google集群能否進(jìn)入OP500，絲毫4Technical Report, April 2005 Google Linux Cluster 的系統結構分析不影響大家對它高性能、高可用性和高可擴展性的懷疑。作為集群系統的典型例子進(jìn)入教科書(shū)，就是對Google集群的極大肯定。文獻[3]中作者再三強調Google集群是由Google公司自行開(kāi)發(fā)的集群系統，并不采用最先進(jìn)的技術(shù)（一般最先進(jìn)的技術(shù)都比較昂貴）。Google集群設計和維護中無(wú)處不體現強烈的追求最大性?xún)r(jià)比、實(shí)用的特點(diǎn)。Google集群的設計者不一次性購買(mǎi)很多資源，而是不夠時(shí)再投入?？傊?，Google集群構建和維護過(guò)程中始終堅持的實(shí)用主義特點(diǎn)，值得我們在大型機設計和購買(mǎi)過(guò)程中學(xué)習。 3、Google的文件系統 作為一個(gè)巨大的數據檢索系統，Google并沒(méi)有采用常見(jiàn)的數據庫管理系統來(lái)管理Web文件及相關(guān)數據。Google集群如今收集了80多億個(gè)Web文檔，平均每天執行兩億多次用戶(hù)查詢(xún)請求。文件數目太多，則檢索速度慢；且每個(gè)文件大小相差甚遠，容易導致硬盤(pán)文件存儲管理費用巨大。文獻[3]中介紹，Google把多個(gè)Web文件匯集到一個(gè)巨大的文件中進(jìn)行存儲、管理，當然對一個(gè)大文檔有相關(guān)記錄信息。關(guān)于大文件說(shuō)明信息的格式如圖3所示[3]。另外因為Web文件數量太多，所占存儲區間太大，Google采用ZLIB壓縮算法先對原始Web頁(yè)面信息進(jìn)行壓縮，然后只存儲壓縮后的結果。ZLIB壓縮算法對WEB文檔的壓縮比為3：1，因此一個(gè)64MB的大文件，實(shí)際上包含192MB的原始Web文檔。 圖3 Web文件的描述信息 Google集群中的硬盤(pán)是普通的IDE接口的PC機硬盤(pán)，雖然便宜但可靠性較低。Google集群維護人員在工作中發(fā)現，存儲器出現故障在Google集群中并不是少見(jiàn)的異?，F象，而是頻繁發(fā)生。
三萬(wàn)個(gè)硬盤(pán)(15,000臺PC機，每臺機器中有兩個(gè)硬盤(pán))同時(shí)工作，都不出現故障，用概率計算的方法一算就知道幾乎是不可能事件。Google集群總在頻繁的執行文件讀操作，硬盤(pán)出現故障的可能性就更大。硬盤(pán)常出故障的現實(shí)環(huán)境與傳統分布式文件系統設計的基本假設有沖突。Google集群應該設計具備持續監視、錯誤檢測、容錯和自動(dòng)恢復功能的分布式文件系統。 Google集群運行過(guò)程中還發(fā)現了許多來(lái)自應用、操作系統、用戶(hù)、存儲器、網(wǎng)絡(luò )等多方面存在的軟件故障。Google集群中的文件操作有一個(gè)特性：每個(gè)文件基本上是只執行一次寫(xiě)入操作，以后都是頻繁執行只讀操作，隨機寫(xiě)操作幾乎不發(fā)生。當crawlers從網(wǎng)絡(luò )中采集到一個(gè)Web文件，在內存中完成相關(guān)處理后，就寫(xiě)入到一個(gè)大文件中，以后每次查詢(xún)只是執行一次數據讀取操作。銀行、電子商務(wù)等常見(jiàn)的大型數據管理系統中則沒(méi)有這個(gè)特性。針對來(lái)自應用領(lǐng)域的特征，Google公司的研發(fā)人員在分布式文件系統開(kāi)發(fā)中采用了不同于傳統分布式文件系統I/O操作的假設。 Google開(kāi)發(fā)了公司內部的分布式文件系統Google File System（GFS），該文件系統的系統結構如圖4所示。GFS中包括單一的GFS Master，多個(gè)GFS chunkserver。文獻[3]和文獻[10]發(fā)表時(shí)間相差五年，但不難判斷文獻[3]中的大文件就是文獻[
10]中的chunk。圖4表示GFS不是完全在操作系統層設計的分布式文件系統，而是在已有的Linux文件系統之后再封裝的分布式文件系統，因此它依賴(lài)傳統的Linux文件系統。GFS master中存儲了三種重要的元數據：文件和chunk的命名空間、文件到chunk的映射表以及chunk及其備份的位
5Technical Report, April 2005 Google Linux Cluster 的系統結構分析置信息（為了提高文件存儲的可靠性，GFS中對同一份數據一般存儲在三臺不同的主
機上。對一個(gè)chunk而言，它就有兩個(gè)分布在其它PC機上的備份）。GFS chunkserver中每個(gè)chunk大小為64MB，關(guān)于每個(gè)chunk大小的具體數值選擇并不是隨意的，而是很有技巧。關(guān)于64MB大小的chunk設置的優(yōu)點(diǎn)和缺點(diǎn)在文獻[9]中有很詳細的討論。 圖4 Google文件系統的結構 GFS中執行一個(gè)簡(jiǎn)單的讀數據操作工作流程如下：首先，應用客戶(hù)端把文件名和文件在一個(gè)chunk中的偏移量轉換成一個(gè)包含該文件數據的chunk索引；然后，客戶(hù)端向GFS master發(fā)送請求，請求中包括所需要的文件名以及chunk索引。當GFS master收到請求并通過(guò)chunk映射表映射后，它向客戶(hù)端作出響應，反饋給客戶(hù)端相應的chunk句柄以及該chunk備份的位置?？蛻?hù)端收到反饋信息后，將以文件名和chunk索引為關(guān)鍵詞進(jìn)行緩存。有了所需文件chunk索引和位置信息，客戶(hù)端一般從多個(gè)chunk服務(wù)器中選擇一個(gè)離自己最鄰近的chunkserver發(fā)出數據訪(fǎng)問(wèn)請求。一般數據訪(fǎng)問(wèn)存在空間局部性，以后如果該應用客戶(hù)端需要訪(fǎng)問(wèn)同一chunkserver中的數據，它不再向GFS server發(fā)送請求，而是直接向chunk服務(wù)器發(fā)送數據讀取請求。關(guān)于GFS更詳細的討論在此不再進(jìn)行更深入討論，如果希望進(jìn)一步了解可以參考文獻[9]。
4、Google的存儲系統 Google集群收集到的Web頁(yè)面就已達到80多億張，另外它還有十億多張圖片。文獻[5]中報道Google集群中的數據容量在2004年就達到了5PB。作為一個(gè)容量巨大且訪(fǎng)問(wèn)頻繁的存儲系統，Google卻沒(méi)有采用流行的網(wǎng)絡(luò )存儲技術(shù)和附網(wǎng)存儲技術(shù)，甚至就連比較廉價(jià)的磁盤(pán)陣列也沒(méi)使用。Google采用的存儲方法是用最常見(jiàn)、最普通的一個(gè)PC機中帶兩個(gè)硬盤(pán)的存儲方式。Google放棄主流的并行海量數據存儲技術(shù)，采用健壯性較低的PC機帶硬盤(pán)存儲的方式最主要的原因是希望降低成本。雖然這種存儲方式不太可靠，但通過(guò)GFS可實(shí)現高效、可靠存儲，已被實(shí)踐檢驗是有效的海量存儲解決方法。 2003年市場(chǎng)上最常見(jiàn)的PC機硬盤(pán)存儲容量是80G。根據文獻[4]中報道，每臺PC機中配有兩個(gè)80G的硬盤(pán)，不難計算出Google集群的總容量是80G×15,000×2＝2,400,000G＝2.4PB。由于可靠性和可用性對Google十分重要，不是所有的存儲區間都用來(lái)存儲有效數據。為了提高可用性，有一半的硬盤(pán)是作鏡像存儲。當一個(gè)硬盤(pán)出現故障，或者數據讀寫(xiě)錯誤時(shí)，可用另一個(gè)硬盤(pán)啟動(dòng)系統或訪(fǎng)問(wèn)其中的數據。集群中的每臺PC機都存儲了一份獨立完整的操作系統，又有一部分存儲區域去存放系統軟件，因此實(shí)際有效存儲空間比1.2PB還小。同樣出于價(jià)格成本因素考慮，Google集群中沒(méi)有使用SCSI接口的硬盤(pán)。使用SCSI接口的硬盤(pán)，不僅硬盤(pán)自身價(jià)格高，且還需轉接卡。為了提高數據讀取速度，Google集群中的硬盤(pán)轉速比較高，從而降低旋轉等待時(shí)間。
6
Technical Report, April 2005 Google Linux Cluster 的系統結構分析2003年底，Google中每臺PC機中竟然配置了高達2GB的內存。由于每個(gè)chunk高達64MB，使用大內存對提高系統的性能有良好效果。曾對存儲器容量對系統性能的影響進(jìn)行測試，發(fā)現存儲器系統不是整個(gè)系統性能的瓶頸。 5、Google的可靠性和可用性 可靠性是指系統正常運行時(shí)間，可用性是系統正常運行時(shí)間與正常運行時(shí)間以及故障維修時(shí)間之和的比率[11]，高可用性是評價(jià)超級計算機和服務(wù)器系統的關(guān)鍵指標之一。作為商業(yè)網(wǎng)站，Google集群必須能保證每周7天、每天24小時(shí)都正常工作。即使是在系統維護操作時(shí)，也不能讓整個(gè)系統停機。一萬(wàn)多臺PC機，總會(huì )存在各種各樣的故障和異常，幾乎所有故障都會(huì )降低系統的可用性。即使系統不出故障，Google集群中的PC機每?jì)赡暌矔?huì )更新一次。PC機更新是在硬件上徹底更換，更新的過(guò)程必定會(huì )終止一部分機器服務(wù)。設備更新比較耗時(shí)，15,000臺機器同時(shí)更新顯然不是兩個(gè)小時(shí)內可以完成。以下分析Google集群提高系統可用性的方法。 首先，Google是Web搜索引擎，可用性要求比較弱。搜索引擎的可用性需求與銀行、電信業(yè)務(wù)中的可用性存在區別，這些區別導致了不同的可用性維護策略。對銀行業(yè)務(wù)連續執行同樣的請求，得到的響應必須一致。但對Web搜索引擎，用戶(hù)期望的可用性是只要能訪(fǎng)問(wèn)Google的入口，鍵入檢索詞，幾秒鐘后能得到檢索結果即可。2004年4月17日,我輸入“華中科技大學(xué)”一詞進(jìn)行檢索，得到了1,170,000個(gè)檢索結果；而在4月21日執行同樣的檢索，我只得到了917,000條結果。顯然兩次檢索結果差異巨大，但實(shí)際上普通用戶(hù)很難發(fā)現這種差異，甚至根本就沒(méi)考慮過(guò)這種現象。 Google中對Index和Web頁(yè)面數據都采用分布式存儲。每臺PC機都可能出故障，出現故障后需要一定的故障維修周期。在維修周期內，該機器中所存儲的數據可能就不能正常訪(fǎng)問(wèn)，因此導致反饋給用戶(hù)的檢索結果減
少。因此，連續多次執行同樣的檢索請求，但檢索結果不一致現象就能得到合理解釋
。這種非嚴格的可用性，給Google的維護以及技術(shù)方案選擇提供了寬松的環(huán)境。相反
，銀行則不得不采用昂貴的硬件設備來(lái)維持系統的嚴格可用性。 其次，Google通過(guò)
分布在不同地區的多個(gè)鏡像站點(diǎn)來(lái)提供系統的可用性。Google集群耗電量巨大，占地
面積大，停電是導致系統可用性降低的致命因素。Google公司位于加州，加州近年來(lái)
出現了能源短缺、電力供應緊張現象，近年來(lái)加州曾多次出現大面積停電現象[12]。
單機或服務(wù)器保證電力供應方法是采用UPS電源，而Google集群由于功耗太大，估計
采用UPS的可能性比較小，公司自備發(fā)電機發(fā)電可能是更可行的方法。Google僅是一
個(gè)Web搜索引擎，即使是公司內部有備用電源，也不能保證當地區停電時(shí)網(wǎng)站正常提
供網(wǎng)絡(luò )服務(wù)功能。原因是Google與外界連接的通信網(wǎng)絡(luò )也因停電而終止工作，因此無(wú)
論Google集群的可用性有多高，只要通信網(wǎng)絡(luò )具有單一性，它依然無(wú)法保證高可用性
。 另外，地震、恐怖襲擊等其它災難性事故也將導致單一Google集群無(wú)法保證高可
用性。加州是太平洋板塊和美洲板塊的交界處，地震活動(dòng)比較頻繁。2005年4月16日
12時(shí)18分在加州WSW of Mettler發(fā)生了5.1級的地震[13]；2003年12月23日在加州發(fā)
生了里氏6.5級的地址，導致多人死亡。運行在地震頻繁地區的大型機有必要考慮地
震對整個(gè)系統可用性的影響，實(shí)際上Google公司的研究人員也考慮了該問(wèn)題，并采取
了相關(guān)對策。 2001年Google有三個(gè)鏡像站點(diǎn)，兩個(gè)分布在加州的硅谷，另一個(gè)在美
國東海岸的弗吉尼亞。每個(gè)Google站點(diǎn)都采用OC48 (2488Mbit/sec)的帶寬連接到因
特網(wǎng)，硅谷中的兩個(gè)臨近站點(diǎn)還用一根OC12的光纖互連，以便緊急情況下或網(wǎng)絡(luò )故障
時(shí)兩個(gè)鏡像站點(diǎn)可共享一根OC48光纖連接互聯(lián)網(wǎng)。弗吉尼亞州的那個(gè)站點(diǎn)在2003年也
有了自己的鏡像，其連接方法就和硅谷中兩個(gè)鏡像站點(diǎn)的互連方法一致。從一個(gè)站點(diǎn)
變成地理位置上分離的四個(gè)站點(diǎn)，軟硬件設備的成本就增加了三倍，但可用性幾乎達
到了100%。中國用戶(hù)訪(fǎng)問(wèn)Google經(jīng)常不通，
7
Technical Report, April 2005 Google Linux Cluster 的系統結構分析
估計是通信網(wǎng)絡(luò )故障原因較多。這些來(lái)自網(wǎng)絡(luò )中的技術(shù)的與非技術(shù)處理是Google公司
無(wú)法解決的。 高度冗余提高了Google的可用性，但Google公司對鏡像站點(diǎn)的投資并
不是真正的冗余投資。服務(wù)器常見(jiàn)的冗余方式是雙機備份，當一臺機器出現故障時(shí)另
一臺機器立即接管故障機器上的任務(wù)。簡(jiǎn)而言之，就是兩臺服務(wù)器實(shí)際上只具備一臺
服務(wù)器的工作效率。如果服務(wù)器工作穩定，有一半投資是冗余。由于搜索引擎對可用
性要求不是很?chē)栏?，且每個(gè)Google站點(diǎn)自身有很高的可用性，Google的鏡像站點(diǎn)不是
另一個(gè)站點(diǎn)的熱備份。通過(guò)基于DNS的負載均衡方法，DNS服務(wù)器把域名地址www.google
.com解析成不同的IP地址，把查詢(xún)請求分配到四個(gè)鏡像站點(diǎn)?；贒NS的負載均衡方
法并不是Google首創(chuàng )，它是計算機網(wǎng)絡(luò )技術(shù)中的一個(gè)常見(jiàn)技巧，簡(jiǎn)單高效。如DNS服
務(wù)器收到一個(gè)來(lái)自中國大陸地區的搜索請求，只要加州的兩個(gè)服務(wù)器不是特別繁忙，
它就把域名地址解析成加州兩個(gè)站點(diǎn)中較為空閑的一臺。請求在加州處理，降低了網(wǎng)
絡(luò )通信中的線(xiàn)路傳輸延時(shí)，對降低響應時(shí)間有好處。同理，來(lái)自歐洲用戶(hù)的請求則解
析到弗吉尼亞的鏡像站點(diǎn)。四個(gè)站點(diǎn)中的某個(gè)站點(diǎn)出現故障或過(guò)于繁忙，DNS服務(wù)器
可以暫時(shí)不把請求分配到該站點(diǎn)，而是轉移到其它的三個(gè)站點(diǎn)，因此Google看來(lái)是利
用冗余的方法來(lái)提高系統的可用性,但建立鏡像站點(diǎn)實(shí)際上幾乎算不上冗余投資。這
從一貫堅持節省投資成本的Google而言，無(wú)疑是一個(gè)很好的設計方案。 第三、Google
堅持采用軟件方案來(lái)提高可用性，而不是使用硬件技術(shù)。服務(wù)器和大型機中的冗余一
般是用硬件，硬件方式意味著(zhù)更多投資。Google公司的維護人員可以開(kāi)發(fā)軟件，如GFS
，采用軟件方法可達到提高可用性的效果。Google是最大的Linux用戶(hù)，它可把應用
需求直接向Red Hat公司提出，讓對方的設計人員開(kāi)發(fā)面向Google的操作系統[14]。
6、Google如何實(shí)現高并行性 如何提供系統的并行性是大型機設計和開(kāi)發(fā)的關(guān)鍵問(wèn)
題，并行性高則意味著(zhù)系統的加速比大，有利于系統的可擴展性。系統的加速比與實(shí)
際應用自身的特性緊密相關(guān)，如果應用中計算部分所占比例小，而多處理器之間的通
信、同步操作多，則并行性難以提高。Google集群的設計者在多篇論文中都表明Google
集群的處理能力與PC機數量呈線(xiàn)形關(guān)系[4]，顯然這是并行計算中所期望的理想狀態(tài)
。本文認為Google集群提高并行性的技術(shù)可歸納為宏觀(guān)意義上的多發(fā)射、多流水。
圖5 請求處理流程 圖1示出Google的三大功能模塊：負責Web頁(yè)面收集的crawlers、
負責Index檢索的Index server、以及負責文檔檢索的Doc Server。Crawlers只負責
從網(wǎng)絡(luò )中不斷的采集網(wǎng)頁(yè)，它與用戶(hù)的檢索請求沒(méi)有直接聯(lián)系；Index以及頁(yè)面檢索
是直接為用戶(hù)的請求服務(wù)。三者之間通信和同步操作少，適合并行工作。Crawlers以
固定周期去發(fā)現和采集網(wǎng)絡(luò )中的Web
8
Technical Report, April 2005 Google Linux Cluster 的系統結構分析
頁(yè)面，1998年、2000年、2001年以及2003年的文獻關(guān)于采集周期的報道都是每一個(gè)月
更新一次。每個(gè)crawler所采集頁(yè)面的地址是由系統分配的，因為分配的地址不同，
多臺執行crawler程序的PC機可以并行操作。只要Google集群連接到網(wǎng)絡(luò )的帶寬不存
在瓶頸，則數據采集信息處理能力與PC的數量成正比增長(cháng)。 一個(gè)請求在Google中的
處理過(guò)程如圖2和圖5所示[15]。步驟1是用戶(hù)通過(guò)Web頁(yè)面將檢索詞發(fā)送到Google Web
Server。步驟2是WWW服務(wù)器將查詢(xún)發(fā)送到索引服務(wù)器。目前在步驟2執行之前，Google
做了一些小處理，如：判斷檢索詞的英文拼寫(xiě)是否正確，如果出錯向用戶(hù)給出提示信
息。Google盈利的主要來(lái)源之一是廣告業(yè)務(wù)，因此在步驟2執行之前，還有一些關(guān)于
附加廣告操作。 Google Web Server對每個(gè)請求所作處理較少，一般不是系統的瓶頸
。Index檢索與Doc檢索之間存在嚴格的時(shí)序關(guān)系，即對同一個(gè)請求只有在Index server
處理完成后，才能去訪(fǎng)問(wèn)Doc Server。把一個(gè)請求分成兩次查詢(xún)主要是從效率角度考
慮，因為原始Web頁(yè)面有80多億張,直接檢索則范圍太多，檢索時(shí)間長(cháng)。Google先對容
量大小為數TB甚至是幾個(gè)PB的原始數據建立高達數MB的索引描述信息，根據Index檢
索結果，只對部分Web頁(yè)面進(jìn)行搜索。Index檢索完成后，Index服務(wù)器不再處理該請
求，而是直接去處理下一個(gè)請求。當Index服務(wù)器在為第n個(gè)請求作檢索的時(shí)候，Doc
服務(wù)器可能是在為第n-1個(gè)請求進(jìn)行搜索。Index服務(wù)器和Doc服務(wù)器在同一時(shí)刻并不
處理同一個(gè)請求，二者可并行為用戶(hù)服務(wù)。若把每一個(gè)宏觀(guān)檢索類(lèi)比為流水線(xiàn)中的功
能部件，那么Index服務(wù)器和Doc服務(wù)器是流水線(xiàn)執行。 多個(gè)Doc服務(wù)器可以得到數以
百萬(wàn)計的檢索結果，如本文中描述的對“華中科技大學(xué)”檢索。多個(gè)結果在反饋給用
戶(hù)之前，必須進(jìn)行一次信息匯總和結果評價(jià)排序操作，最后將最好的結果在前幾十條
記錄中反饋給用戶(hù)。 多發(fā)射技術(shù)在Google中也有應用。從站點(diǎn)層次來(lái)看，Google有
多個(gè)鏡像站點(diǎn)，每個(gè)鏡像站點(diǎn)之間可以并行為用戶(hù)服務(wù)。位于美國東海岸的鏡像站點(diǎn)
為美國東部和歐洲用戶(hù)服務(wù)，而加州的鏡像站點(diǎn)并行的為亞洲及美國西部用戶(hù)服務(wù)。
從站點(diǎn)內部來(lái)看，Google Web Server并非是一臺PC機，它肯定有多臺PC機負責該操
作?？傊?，在同一時(shí)刻Google Web Server可以接受多個(gè)用戶(hù)請求，并可以向Index發(fā)
出多條查詢(xún)任務(wù)。類(lèi)比單個(gè)芯片內部存在多條流水線(xiàn)的現代CPU系統，我們可以認為
Google集群中有多條流水線(xiàn)，是一個(gè)多發(fā)射系統。 表3 每秒Google處理的請求數和
Google中的頁(yè)面數量 時(shí)間 Web頁(yè)面數 每天處理的請求數(百萬(wàn)) 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] 互聯(lián)網(wǎng)的普及導致Google在單位時(shí)間內處理的請求越來(lái)越多
。表1示出了自1998年以來(lái)，Google平均每天處理的檢索請求數目增長(cháng)情況。表1中的
數據來(lái)自Google公司提供的介紹信息[15]。關(guān)于2005年4月份平均每天處理的用戶(hù)請
求數是超過(guò)2億，即大于200M。 9
Technical Report, April 2005 Google Linux Cluster 的系統結構分析
7. 結束語(yǔ) Google是世界上最成功的網(wǎng)絡(luò )搜索引擎，它在創(chuàng )辦之初就發(fā)現并堅持了一
個(gè)十分正確的搜索結果評價(jià)標準:精確率高于查全率，并設計了比較科學(xué)的網(wǎng)頁(yè)評價(jià)
算法。在Google最具原創(chuàng )性的兩篇論文中，對來(lái)自硬件領(lǐng)域的可擴展性、可靠性、可
用性根本都未曾涉及。Google公司創(chuàng )始人在攻讀博士期間發(fā)表的論文主要是講述Google
的軟件體系、數據結構和頁(yè)面評價(jià)算法，由此可判斷他倆擅長(cháng)軟件設計，而不是偏向
硬件的計算機系統結構。 隨著(zhù)Belwolf的成功，集群技術(shù)成為今年來(lái)國際上大型機和
高性能計算領(lǐng)域的主流技術(shù)。Google集群的設計者在多年前就巧妙的利用集群技術(shù)，
無(wú)疑是一個(gè)十分正確的技術(shù)選擇。因為沒(méi)有哪臺大型機能以如此低的價(jià)格，提供如此
強的可擴展性。 Google是世界上應用效率最高的集群系統之一，但對集群技術(shù)自身
的發(fā)展它并沒(méi)有作出太多貢獻。Google集群在某種程度上來(lái)看，也許不能成為嚴格的
集群服務(wù)器，甚至更像一個(gè)巨大的計算或存儲局域網(wǎng)。因為集群系統研究中最關(guān)鍵的
技術(shù)是單一系統映象,而所有關(guān)于Google集群的介紹中都沒(méi)有涉及。估計Google集群
是通過(guò)網(wǎng)絡(luò )的方式來(lái)進(jìn)行負載均衡和數據訪(fǎng)問(wèn)，不具有嚴格的集群定義。隨著(zhù)人們對
集群定義的逐步放松，特別是Patterson教授和Hennessy教授的《計算機系統結構：
一種量化的研究方法》中用很大篇幅詳細介紹Google集群之后，它就變成了大型集群
成功應用的典范。Hennessy教授既是Stanford大學(xué)的校長(cháng)，又是Google公司的董事。
作為計算機系統結構領(lǐng)域的國際著(zhù)名學(xué)者，他有可能直接參與并指導了Google集群的
設計和開(kāi)發(fā)，在目前所有關(guān)于Google集群的文獻中，文獻[6]是最全面和細致的一篇
。Google集群能否稱(chēng)得上嚴格意義上的集群，在國外也有爭議。但無(wú)論是否是集群，
對Google而言沒(méi)有太多意義。因為它已成功的解決了一個(gè)大計算量、大存儲量、高實(shí)
時(shí)性的應用需求，并且多年來(lái)工作得很好。 總之,從計算機系統結構角度來(lái)看，我最
推崇Google集群研究者和維護者的觀(guān)點(diǎn)：用最少的錢(qián)、用最成熟的技術(shù)去構建穩定、
高性能、高可用性的系統。目前國內也有很多耗費巨資購買(mǎi)的服務(wù)器或者大型機，而
真正得到高效應用較少。有些計算或存儲服務(wù)需求比Google要寬松得多，為什么我們
不改變思路，用成熟的技術(shù)去構建一個(gè)自己的大型計算機系統？本文對Google集群的
評價(jià)是：用成熟、廉價(jià)的技術(shù)去構建了一個(gè)先進(jìn)、卓越的計算機系統。這種實(shí)用主義
的態(tài)度，值得我們未來(lái)在計算機硬件系統設計和軟件系統開(kāi)發(fā)中學(xué)習。 致謝 本文是
華中科技大學(xué)計算機學(xué)院謝長(cháng)生教授講授的《高等計算機系統結構專(zhuān)題》課程的課程
論文，感謝他提供了Google集群系統結構分析這個(gè)有趣的問(wèn)題、并深入淺出的講授了
計算機系統結構領(lǐng)域的技術(shù)進(jìn)展及思維方法。 參考文獻 [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 10
Technical Report, April 2005 Google Linux Cluster 的系統結構分析
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
.
