走在架構(gòu)師的大道上 Jack.Wang's home

Google背后的分布式計(jì)算架構(gòu)策略
Google是與眾不同的。它的獨(dú)特不僅僅表現(xiàn)于革新的思維和充滿(mǎn)創(chuàng)意的應(yīng)用 (比如那個(gè)大堂里的地球模型)，更在于其有別常規(guī)的IT策略……
　　加利福尼亞州山景城(Mountain View)Google公司(Google，下稱(chēng)Google)總部有一個(gè)43號(hào)大樓，該建筑的中央大屏幕上顯示著一個(gè)與Google地球(Google Earth)相仿的世界地圖，一個(gè)轉(zhuǎn)動(dòng)的地球上不停地閃動(dòng)著五顏六色的光點(diǎn)，恍如羅馬宮廷的千萬(wàn)燭燈，每一次閃動(dòng)標(biāo)志著地球的這個(gè)角落一名Google用 戶(hù)發(fā)起了一次新的搜索。
　　這同時(shí)意味著Google又一次滿(mǎn)足了人們對(duì)未知信息的好奇與渴望。
　　Google是與眾不同的。它的獨(dú)特不僅僅表現(xiàn)于革新的思維和充滿(mǎn)創(chuàng)意的應(yīng)用 (比如那個(gè)大堂里的地球模型)，更在于其有別常規(guī)的IT策略。從人們的常理來(lái)看，簡(jiǎn)單的硬件商品和免費(fèi)軟件是無(wú)法構(gòu)建出一個(gè)帝國(guó)的，但是Google做到 了。在性能調(diào)整后，Google把它們變成一個(gè)無(wú)可比擬的分布式計(jì)算平臺(tái)，該平臺(tái)能夠支持大規(guī)模的搜索和不斷涌現(xiàn)的新興應(yīng)用。我們?cè)菊J(rèn)為這些應(yīng)用都是個(gè) 人消費(fèi)級(jí)別的，但是Google改變了這一切。現(xiàn)在商業(yè)世界也在使用它們，這就令這家搜索公司顯得那么與眾不同。
　　GoogleWeb 服務(wù)背后的IT架構(gòu)對(duì)無(wú)數(shù)使用搜索引擎的用戶(hù)來(lái)說(shuō)也許并不是非常重要，但它是Google幾百位致力于把全球信息組織起來(lái)，實(shí)現(xiàn)“隨處可達(dá)，隨時(shí)可用”目 標(biāo)的工程師們的最核心工作。這就需要一個(gè)在覆蓋范圍和野心上都與Google的商業(yè)愿景完全相符的IT藍(lán)圖作為支撐。
　　Google 的經(jīng)理們一直對(duì)公司的IT策略話(huà)題保持沉默，他們厭惡談及特定的廠(chǎng)商或者產(chǎn)品，當(dāng)被問(wèn)到他們的服務(wù)器和數(shù)據(jù)中心時(shí)，他們總是閉口不談。但與幾位 Google的IT領(lǐng)導(dǎo)一起呆了一天后，我們最終得以揭示該公司的IT是如何運(yùn)作的，那可不僅僅是一個(gè)運(yùn)行在無(wú)數(shù)服務(wù)器集群上的、表面看來(lái)非常簡(jiǎn)單的搜索 引擎。在其簡(jiǎn)單的外表下，蘊(yùn)涵著許多內(nèi)部研發(fā)軟件、定制硬件、人工智能，以及對(duì)性能的執(zhí)著追求和打破常規(guī)的人力管理模式。
　　IT理念方面，Google對(duì)同行有一條建議：盡量避免那些人人都在使用的系統(tǒng)和軟件，以自己的方式做事會(huì)更有獨(dú)特的競(jìng)爭(zhēng)優(yōu)勢(shì)。
　　“企業(yè)文化決定了你的做事方式。”道格拉斯"美林(Douglas Merrill)，這位Google工程副總裁和事實(shí)上的首席信息官(CIO) 指出，“到了我們這樣的發(fā)展階段，企業(yè)觀(guān)念和文化非常與眾不同，這也反過(guò)來(lái)鞭策我們必須要采用與眾不同的方式來(lái)運(yùn)行那些他人看來(lái)很常規(guī)的系統(tǒng)。”
　　Google 最大的IT優(yōu)勢(shì)在于它能建造出既富于性?xún)r(jià)比(并非廉價(jià))又能承受極高負(fù)載的高性能系統(tǒng)。因此IT顧問(wèn)史蒂芬"阿諾德(Stephen Arnold)指出，Google與競(jìng)爭(zhēng)對(duì)手，如亞馬遜網(wǎng)站(Amazon)、電子港灣公司(eBay)、微軟公司(Microsoft，下稱(chēng)微軟)和雅 虎公司 (Yahoo，下稱(chēng)雅虎)等公司相比，具有更大的成本優(yōu)勢(shì)。Google程序員的效率比其他Web公司同行們高出50%～100%，原因是Google已 經(jīng)開(kāi)發(fā)出了一整套專(zhuān)用于支持大規(guī)模并行系統(tǒng)編程的定制軟件庫(kù)。據(jù)他估算，其他競(jìng)爭(zhēng)公司可能要花上四倍的時(shí)間才能獲得同等的效果。
　　打造服務(wù)器
　　Google 究竟是怎樣做到這點(diǎn)的呢?其中一個(gè)手段，美林認(rèn)為，“是因?yàn)槲覀冏约簞?dòng)手打造硬件。”Google并不制造計(jì)算機(jī)系統(tǒng)，但它根據(jù)自己的參數(shù)定制硬件，然后 像MTV的節(jié)目“靚車(chē)打造”(Pimp My Ride)那樣自己安裝和調(diào)整硬件系統(tǒng)。開(kāi)源程序經(jīng)理克里斯"迪博納(Chris DiBona)評(píng)論道：“我們很善于購(gòu)買(mǎi)商業(yè)服務(wù)器，并且改造他們?yōu)槲覀兯茫詈蟀研阅軌赫ズ桶l(fā)揮到極致，以致有時(shí)候他們熱得像要融化了似的。”
　　這種親手打造的方式，來(lái)源于Google從車(chē)庫(kù)誕生時(shí)與生俱來(lái)的節(jié)儉風(fēng)格，更與Google那超大型的系統(tǒng)規(guī)模息息相關(guān)，良好的習(xí)慣一直延續(xù)至 今。據(jù)說(shuō) Google在65個(gè)數(shù)據(jù)中心擁有20萬(wàn)～45萬(wàn)臺(tái)服務(wù)器—這個(gè)數(shù)目會(huì)有偏差(取決于你如何定義服務(wù)器和由誰(shuí)來(lái)做這項(xiàng)統(tǒng)計(jì))。但是，不變的是持續(xù)上升的趨 勢(shì)。
　　Google不會(huì)去討論這些資產(chǎn)，因?yàn)樗J(rèn)為保密也是一種競(jìng)爭(zhēng)優(yōu)勢(shì)。事實(shí)上，Google之所以喜歡開(kāi)源軟件也是因?yàn)樗乃矫苄浴?#8220;如果我們購(gòu) 買(mǎi)了軟件許可或代碼許可，人們只要對(duì)號(hào)入座，就可以猜出Google的IT基礎(chǔ)架構(gòu)。”迪博納分析說(shuō)， “使用開(kāi)源軟件，就使我們多了一條把握自己命運(yùn)的途徑。”
　　Google喜歡規(guī)模化的服務(wù)器運(yùn)行方式。當(dāng)有成百上千臺(tái)機(jī)器時(shí)，定制服務(wù)器的優(yōu)勢(shì)也會(huì)成倍增加，效果也會(huì)更趨明顯。Google正在俄勒岡州 哥倫比亞河邊的達(dá)勒斯市建造一個(gè)占地30畝的數(shù)據(jù)中心，在那兒它可以獲得運(yùn)算和降溫需要的低價(jià)水力電力能源(參見(jiàn)邊欄《Google數(shù)據(jù)中心自有一套》)。
　　Google以“單元”(Cell)的形式組織這些運(yùn)行 Linux操作系統(tǒng)的服務(wù)器，迪博納把這種形式比喻成互聯(lián)網(wǎng)服務(wù)的“磁盤(pán)驅(qū)動(dòng)器”(但別和一直謠傳的Google存儲(chǔ)服務(wù)Gdrive混淆了，“并沒(méi)有 Gdrive這回事。”一位Google女發(fā)言人明確表示。)，公司的軟件程序都駐扎在這些并不昂貴的電腦機(jī)箱里，由程序員決定它們的冗余工作量。這種由 很多單元組成的文件系統(tǒng)代替了商業(yè)存儲(chǔ)設(shè)備;迪博納表示Google這些單元設(shè)備更易于建造和維護(hù)，他還暗示他們能處理更大規(guī)模的數(shù)據(jù)。
　　Google 不會(huì)漏過(guò)對(duì)任何技術(shù)細(xì)節(jié)的關(guān)注。多年來(lái)，公司的工程師就在研究微處理器的內(nèi)部工作機(jī)制，隨著Google規(guī)模的持續(xù)壯大，必然會(huì)用到特別定制和調(diào)節(jié)過(guò)的芯 片。知名工程師路易斯"巴羅索(Luiz Barroso)去年在一篇發(fā)表在工業(yè)雜志上的論文中證實(shí)，近年來(lái)Google的主要負(fù)荷都由單核設(shè)計(jì)的系統(tǒng)承擔(dān)著。但許多服務(wù)器端的應(yīng)用，如 Google搜索索引服務(wù)，所需的并行計(jì)算在單核芯片的指令級(jí)別上執(zhí)行得并不好。
　　曾在數(shù)據(jù)設(shè)備公司(Digital Equipment)和康柏公司(Compaq)當(dāng)過(guò)芯片設(shè)計(jì)師的巴羅索認(rèn)為，隨著AMD公司、英特爾公司(Intel)、太陽(yáng)計(jì)算機(jī)系統(tǒng)公司(Sun)開(kāi)始制造多核芯片，必將會(huì)出現(xiàn)越來(lái)越多芯片級(jí)別的并行計(jì)算。
　　Google 也曾考慮過(guò)自己制造計(jì)算機(jī)芯片，但從業(yè)界潮流來(lái)看，這個(gè)冒險(xiǎn)的舉動(dòng)似乎不是很必要。“微處理器的設(shè)計(jì)非常復(fù)雜而且成本昂貴，”運(yùn)營(yíng)高級(jí)副總裁烏爾斯"霍爾 茨勒(Urs Holzle)表示。Google寧愿與芯片制造商合作，讓他們?nèi)ダ斫庾约旱膽?yīng)用并設(shè)計(jì)適合的芯片。這是一種客戶(hù)建議式的設(shè)計(jì)，其關(guān)注點(diǎn)在于總體吞吐量、 效能，以及耗電比，而不是看單線(xiàn)程的峰值性能。霍爾茨勒表示，“這也是最近多核CPU的設(shè)計(jì)潮流與未來(lái)方向。”
裁縫般地定制軟件
　　為了能盡量壓榨硬件性能，Google開(kāi)發(fā)了相當(dāng)數(shù)量的定制軟件。創(chuàng)新產(chǎn)品主要包括用于簡(jiǎn)化處理和創(chuàng)建大規(guī)模數(shù)據(jù)集的編程模型 MapReduce;用于存儲(chǔ)和管理大規(guī)模數(shù)據(jù)的系統(tǒng)BigTable;分析分布式運(yùn)算環(huán)境中大規(guī)模數(shù)據(jù)集的解釋編程語(yǔ)言Sawzall;用于數(shù)據(jù)密集型 應(yīng)用的分布式文件系統(tǒng)的 “Google文件系統(tǒng)”(Google File System);還有為處理分布式系統(tǒng)隊(duì)列分組和任務(wù)調(diào)度的“Google工作隊(duì)列”(Google Workqueue)。
　　正是從Sawzall這些工具里體現(xiàn)出Google對(duì)計(jì)算效率的執(zhí)著關(guān)注。并不是每家公司都能從底層去解決效率問(wèn)題，但是對(duì)Google來(lái)說(shuō)， 為常規(guī)關(guān)系型數(shù)據(jù)庫(kù)無(wú)法容納的大規(guī)模數(shù)據(jù)集專(zhuān)門(mén)設(shè)計(jì)一種編程語(yǔ)言是完全合理的。即使其他編程工具可以解決問(wèn)題，Google的工程師們?nèi)匀粫?huì)為了追求效率 而另外開(kāi)發(fā)一套定制方案。Google工程師認(rèn)為，Sawzall能與C++中的MapReduce相媲美，而且它更容易編寫(xiě)一些。
　　Google 對(duì)效率的關(guān)注使它不可能對(duì)標(biāo)準(zhǔn)Linux內(nèi)核感到滿(mǎn)意;Google會(huì)根據(jù)自己的需要運(yùn)行修改過(guò)的內(nèi)核版本。通過(guò)調(diào)整Linux的底層性能，Google 工程師們?cè)谔岣吡苏w系統(tǒng)可靠性的基礎(chǔ)上，還一并解決了數(shù)據(jù)損壞和數(shù)據(jù)瓶頸等一系列棘手問(wèn)題。對(duì)內(nèi)核的修改也使Google的計(jì)算機(jī)集群系統(tǒng)因?yàn)橥ㄐ判?的提高而運(yùn)行得更快。
　　當(dāng)然，Google偶爾也會(huì)出現(xiàn)系統(tǒng)故障，情況一旦發(fā)生，無(wú)數(shù)的用戶(hù)就會(huì)受到影響了。三年前一次持續(xù)30分鐘的系統(tǒng)故障使20%的搜索流量受到影響。
　　Google 開(kāi)發(fā)了自己的網(wǎng)站服務(wù)器卻沒(méi)有使用開(kāi)源的Apache服務(wù)器，盡管它在網(wǎng)站服務(wù)器的市場(chǎng)占有率超過(guò)60%。迪博納認(rèn)為，Google的網(wǎng)站服務(wù)器可以運(yùn)行 在更多數(shù)量的主機(jī)上，對(duì)Google站點(diǎn)上內(nèi)容龐大又彼此互相依賴(lài)的應(yīng)用程序來(lái)說(shuō)，這種服務(wù)器的負(fù)載均衡能力遠(yuǎn)比Apache的能力更高。同時(shí)，在用標(biāo)準(zhǔn) 公共網(wǎng)關(guān)接口(CGI)訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)動(dòng)態(tài)網(wǎng)頁(yè)方面，Google服務(wù)器的編程難度要比 Apache更高，但是最終運(yùn)行速度卻更快。“如果我們能夠壓榨出10%～20%的性能，我們就可以節(jié)省出更多系統(tǒng)資源、電量和人力了。”迪博納在總結(jié)中 指出。
　　Google還設(shè)計(jì)了自己的客戶(hù)關(guān)系管理(CRM)系統(tǒng)用于支持自己基于競(jìng)價(jià)和點(diǎn)擊的互聯(lián)網(wǎng)廣告收費(fèi)業(yè)務(wù)。但對(duì)是否需要設(shè)計(jì)自己的工具，Google的態(tài)度也不是一成不變的。比如在財(cái)會(huì)軟件上，它就使用了甲骨文公司(Oracle)的Financials軟件。
　　美林拿著一只叉子舉例說(shuō)明現(xiàn)成的產(chǎn)品也可以帶來(lái)價(jià)值。但在有些場(chǎng)合現(xiàn)成的軟件產(chǎn)品就不一定適用了。“我們的文化在各個(gè)層面對(duì)我們的運(yùn)作都有深遠(yuǎn)影響，”他表示，“所以我們不想讓購(gòu)買(mǎi)所得的工具改變我們的工作方式和文化層面。”
Google's BigTable 原理 （翻譯）
題記：google 的成功除了一個(gè)個(gè)出色的創(chuàng)意外，還因?yàn)橛?Jeff Dean 這樣的軟件架構(gòu)天才。
------ 編者
官方的 Google Reader blog 中有對(duì)BigTable 的解釋。這是Google 內(nèi)部開(kāi)發(fā)的一個(gè)用來(lái)處理大數(shù)據(jù)量的系統(tǒng)。這種系統(tǒng)適合處理半結(jié)構(gòu)化的數(shù)據(jù)比如 RSS 數(shù)據(jù)源。 以下發(fā)言 是 Andrew Hitchcock 在 2005 年10月18號(hào) 基于： Google 的工程師 Jeff Dean 在華盛頓大學(xué)的一次談話(huà) (Creative Commons License).
首先，BigTable 從 2004 年初就開(kāi)始研發(fā)了，到現(xiàn)在為止已經(jīng)用了將近8個(gè)月。（2005年2月）目前大概有100個(gè)左右的服務(wù)使用BigTable，比如： Print,Search History,Maps和 Orkut。根據(jù)Google的一貫做法，內(nèi)部開(kāi)發(fā)的BigTable是為跑在廉價(jià)的PC機(jī)上設(shè)計(jì)的。BigTable 讓Google在提供新服務(wù)時(shí)的運(yùn)行成本降低，最大限度地利用了計(jì)算能力。BigTable 是建立在 GFS ，Scheduler ，Lock Service 和 MapReduce 之上的。
每個(gè)Table都是一個(gè)多維的稀疏圖 sparse map。Table 由行和列組成，并且每個(gè)存儲(chǔ)單元 cell 都有一個(gè)時(shí)間戳。在不同的時(shí)間對(duì)同一個(gè)存儲(chǔ)單元cell有多份拷貝，這樣就可以記錄數(shù)據(jù)的變動(dòng)情況。在他的例子中，行是URLs ，列可以定義一個(gè)名字，比如：contents。Contents 字段就可以存儲(chǔ)文件的數(shù)據(jù)。或者列名是：”language”，可以存儲(chǔ)一個(gè)“EN”的語(yǔ)言代碼字符串。
為了管理巨大的Table，把Table根據(jù)行分割，這些分割后的數(shù)據(jù)統(tǒng)稱(chēng)為：Tablets。每 個(gè)Tablets大概有 100-200 MB，每個(gè)機(jī)器存儲(chǔ)100個(gè)左右的 Tablets。底層的架構(gòu)是：GFS。由于GFS是一種分布式的文件系統(tǒng)，采用Tablets的機(jī)制后，可以獲得很好的負(fù)載均衡。比如：可以把經(jīng)常響應(yīng) 的表移動(dòng)到其他空閑機(jī)器上，然后快速重建。
Tablets在系統(tǒng)中的存儲(chǔ)方式是不可修改的 immutable 的SSTables，一臺(tái)機(jī)器一個(gè)日志文件。當(dāng)系統(tǒng)的內(nèi)存滿(mǎn)后，系統(tǒng)會(huì)壓縮一些Tablets。由于Jeff在論述這點(diǎn)的時(shí)候說(shuō)的很快，所以我沒(méi)有時(shí)間把聽(tīng)到的都記錄下來(lái)，因此下面是一個(gè)大概的說(shuō)明：
壓縮分為：主要和次要的兩部分。次要的壓縮僅僅包括幾個(gè)Tablets，而主要的壓縮時(shí)關(guān)于整個(gè)系統(tǒng)的壓縮。主壓縮有回收硬盤(pán)空間的功能。Tablets的位置實(shí)際上是存儲(chǔ)在幾個(gè)特殊的BigTable的存儲(chǔ)單元cell中。看起來(lái)這是一個(gè)三層的系統(tǒng)。
客戶(hù)端有一個(gè)指向METAO的Tablets的指針。如果METAO的Tablets被頻繁使用，那個(gè)這臺(tái)機(jī)器就會(huì)放棄其他的tablets專(zhuān)門(mén)支持 METAO這個(gè)Tablets。METAO tablets 保持著所有的META1的tablets的記錄。這些tablets中包含著查找tablets的實(shí)際位置。（老實(shí)說(shuō)翻譯到這里，我也不太明白。）在這個(gè)系統(tǒng)中不存在大的瓶頸，因?yàn)楸活l繁調(diào)用的數(shù)據(jù)已經(jīng)被提前獲得并進(jìn)行了緩存。
現(xiàn)在我們返回到對(duì)列的說(shuō)明：列是類(lèi)似下面的形式： family:optional_qualifier。在他的例子中，行：www.search-analysis.com 也許有列：”contents:其中包含html頁(yè)面的代碼。 “ anchor:cnn.com/news” 中包含著 相對(duì)應(yīng)的url，”anchor:www.search-analysis.com/” 包含著鏈接的文字部分。列中包含著類(lèi)型信息。
(翻譯到這里我要插一句，以前我看過(guò)一個(gè)關(guān)于萬(wàn)能數(shù)據(jù)庫(kù)的文章，當(dāng)時(shí)很激動(dòng)，就聯(lián)系了作者，現(xiàn)在回想起來(lái)，或許google的 bigtable 才是更好的方案，切不說(shuō)分布式的特性，就是這種建華的表結(jié)構(gòu)就很有用處。)
注意這里說(shuō)的是列信息，而不是列類(lèi)型。列的信息是如下信息，一般是：屬性/規(guī)則。 比如：保存n份數(shù)據(jù)的拷貝或者保存數(shù)據(jù)n天長(zhǎng)等等。當(dāng) tablets 重新建立的時(shí)候，就運(yùn)用上面的規(guī)則，剔出不符合條件的記錄。由于設(shè)計(jì)上的原因，列本身的創(chuàng)建是很容易的，但是跟列相關(guān)的功能確實(shí)非常復(fù)雜的，比如上文提到 的 類(lèi)型和規(guī)則信息等。為了優(yōu)化讀取速度，列的功能被分割然后以組的方式存儲(chǔ)在所建索引的機(jī)器上。這些被分割后的組作用于 列 ,然后被分割成不同的 SSTables。這種方式可以提高系統(tǒng)的性能，因?yàn)樾〉模l繁讀取的列可以被單獨(dú)存儲(chǔ)，和那些大的不經(jīng)常訪(fǎng)問(wèn)的列隔離開(kāi)來(lái)。
在一臺(tái)機(jī)器上的所有的 tablets 共享一個(gè)log，在一個(gè)包含1億的tablets的集群中，這將會(huì)導(dǎo)致非常多的文件被打開(kāi)和寫(xiě)操作。新的log塊經(jīng)常被創(chuàng)建，一般是64M大小，這個(gè)GFS的塊大小相等。當(dāng)一個(gè)機(jī)器down掉后，控制機(jī)器就會(huì)重新發(fā)布他的log塊到其他機(jī)器上繼續(xù)進(jìn)行處理。這臺(tái)機(jī)器重建tablets然后詢(xún)問(wèn)控制機(jī)器處理結(jié)構(gòu)的存儲(chǔ)位置，然后直接對(duì)重建后的數(shù)據(jù)進(jìn)行處理。
這個(gè)系統(tǒng)中有很多冗余數(shù)據(jù)，因此在系統(tǒng)中大量使用了壓縮技術(shù)。
Dean 對(duì)壓縮的部分說(shuō)的很快，我沒(méi)有完全記下來(lái)，所以我還是說(shuō)個(gè)大概吧：壓縮前先尋找相似的 \行，列，和時(shí)間數(shù)據(jù)。
他們使用不同版本的： BMDiff 和 Zippy 技術(shù)。
BMDiff 提供給他們非常快的寫(xiě)速度： 100MB/s – 1000MB/s 。Zippy 是和 LZW 類(lèi)似的。Zippy 并不像 LZW 或者 gzip 那樣壓縮比高，但是他處理速度非常快。
Dean 還給了一個(gè)關(guān)于壓縮 web 蜘蛛數(shù)據(jù)的例子。這個(gè)例子的蜘蛛 包含 2.1B 的頁(yè)面，行按照以下的方式命名：“com.cnn.www/index.html:http”.在未壓縮前的web page 頁(yè)面大小是：45.1 TB ，壓縮后的大小是：4.2 TB ， 只是原來(lái)的 9.2%。Links 數(shù)據(jù)壓縮到原來(lái)的 13.9% , 鏈接文本數(shù)據(jù)壓縮到原來(lái)的 12.7%。
Google 還有很多沒(méi)有添加但是已經(jīng)考慮的功能。
1. 數(shù)據(jù)操作表達(dá)式，這樣可以把腳本發(fā)送到客戶(hù)端來(lái)提供修改數(shù)據(jù)的功能。
2. 多行數(shù)據(jù)的事物支持。
3. 提高大數(shù)據(jù)存儲(chǔ)單元的效率。
4. BigTable 作為服務(wù)運(yùn)行。
好像：每個(gè)服務(wù)比如： maps 和 search history 歷史搜索記錄都有他們自己的集群運(yùn)行 BigTable。
他們還考慮運(yùn)行一個(gè)全局的 BigTable 系統(tǒng)，但這需要比較公平的分割資源和計(jì)算時(shí)間。
大表(Bigtable):結(jié)構(gòu)化數(shù)據(jù)的分布存儲(chǔ)系統(tǒng)
http://labs.google.com/papers/bigtable-osdi06.pdf
｛中是譯者評(píng)論,程序除外｝
{本文的翻譯可能有不準(zhǔn)確的地方,詳細(xì)資料請(qǐng)參考原文.}
摘要
bigtable是設(shè)計(jì)來(lái)分布存儲(chǔ)大規(guī)模結(jié)構(gòu)化數(shù)據(jù)的，從設(shè)計(jì)上它可以擴(kuò)展到上２^50字節(jié)，分布存儲(chǔ)在幾千個(gè)普通服務(wù)器上．google的很多項(xiàng)目使用 bt來(lái)存儲(chǔ)數(shù)據(jù)，包括網(wǎng)頁(yè)查詢(xún)，google earth和google金融．這些應(yīng)用程序?qū)t的要求各不相同：數(shù)據(jù)大小（從URL到網(wǎng)頁(yè)到衛(wèi)星圖象）不同，反應(yīng)速度不同（從后端的大批處理到實(shí)時(shí)數(shù) 據(jù)服務(wù)）．對(duì)于不同的要求，bt都成功的提供了靈活高效的服務(wù)．在本文中，我們將描述bt的數(shù)據(jù)模型．這個(gè)數(shù)據(jù)模型讓用戶(hù)動(dòng)態(tài)的控制數(shù)據(jù)的分布和結(jié)構(gòu)．我 們還將描述BT的設(shè)計(jì)和實(shí)現(xiàn)．
１．介紹
在過(guò)去兩年半里，我們?cè)O(shè)計(jì)，實(shí)現(xiàn)并部署了BT．BT是用來(lái)分布存儲(chǔ)和管理結(jié)構(gòu)化數(shù)據(jù)的．BT的設(shè)計(jì)使它能夠管理2^50 bytes(petabytes)數(shù)據(jù)，并可以部署到上千臺(tái)機(jī)器上．BT完成了以下目標(biāo)：應(yīng)用廣泛，可擴(kuò)展，高性能和高可用性（high availability）. 包括google analytics, google finance, orkut, personalized search, writely和google earth在內(nèi)的60多個(gè)項(xiàng)目都使用BT.這些應(yīng)用對(duì)BT的要求各不相同，有的需要高吞吐量的批處理，有的需要快速反應(yīng)給用戶(hù)數(shù)據(jù)．它們使用的BT集群也各不相同，有的只有幾臺(tái)機(jī)器，有的有上千臺(tái)，能夠存儲(chǔ)2^40字節(jié)(terabytes)數(shù)據(jù)．
BT在很多地方和數(shù)據(jù)庫(kù)很類(lèi)似：它使用了很多數(shù)據(jù)庫(kù)的實(shí)現(xiàn)策略．并行數(shù)據(jù)庫(kù)[14]和內(nèi)存數(shù)據(jù)庫(kù)[13]有可擴(kuò)展性和高性能，但是BT的界面不同．BT不支持完全的關(guān)系數(shù)據(jù)模型；而是為客戶(hù)提供了簡(jiǎn)單的數(shù)據(jù)模型，讓客戶(hù)來(lái)動(dòng)態(tài)控制數(shù)據(jù)的分布和格式{就是只存儲(chǔ)字串，格式由客戶(hù)來(lái)解釋}，并允許客戶(hù)推斷底層存儲(chǔ)數(shù)據(jù)的局部性｛以提高訪(fǎng)問(wèn)速度｝．?dāng)?shù)據(jù)下標(biāo)是行和列的名字，數(shù)據(jù)本身可以是任何字串．BT的數(shù)據(jù)是字串，沒(méi)有解釋?zhuān)?lèi)型等｝．客戶(hù)會(huì)在把各種結(jié)構(gòu)或者半結(jié)構(gòu)化的數(shù)據(jù)串行化｛比如說(shuō)日期串｝到數(shù)據(jù)中．通過(guò)仔細(xì)選擇數(shù)據(jù)表示，客戶(hù)可以控制數(shù)據(jù)的局部化．最后，可以使用BT模式來(lái)控制數(shù)據(jù)是放在內(nèi)存里還是在硬盤(pán)上．｛就是說(shuō)用模式，你可以把數(shù)據(jù)放在離應(yīng)用最近的地方．畢竟程序在一個(gè)時(shí)間只用到一塊數(shù)據(jù)．在體系結(jié)構(gòu)里，就是：locality, locality, locality｝
第二節(jié)描述數(shù)據(jù)模型細(xì)節(jié)．第三節(jié)關(guān)于客戶(hù)API概述．第四節(jié)簡(jiǎn)介BT依賴(lài)的google框架．第五節(jié)描述BT的實(shí)現(xiàn)關(guān)鍵部分．第6節(jié)敘述提高BT性 能的一些調(diào)整．第7節(jié)提供BT性能的數(shù)據(jù)．在第8節(jié)，我們提供BT的幾個(gè)使用例子，第9節(jié)是經(jīng)驗(yàn)教訓(xùn)．在第10節(jié)，我們列出相關(guān)研究．最后是我們的結(jié)論．
２．?dāng)?shù)據(jù)模型
BT是一個(gè)稀疏的，長(zhǎng)期存儲(chǔ)的｛存在硬盤(pán)上｝，多維度的，排序的映射表．這張表的索引是行關(guān)鍵字，列關(guān)鍵字和時(shí)間戳．每個(gè)值是一個(gè)不解釋的字符數(shù)組．｛數(shù)據(jù)都是字符串，沒(méi)類(lèi)型，客戶(hù)要解釋就自力更生吧｝．
(row:string, column:string,time:int64)->string {能編程序的都能讀懂，不翻譯了}
我們仔細(xì)查看過(guò)好些類(lèi)似bigtable的系統(tǒng)之后定下了這個(gè)數(shù)據(jù)模型。舉一個(gè)具體例子（它促使我們做出某些設(shè)計(jì)決定）， 比如我們想要存儲(chǔ)大量網(wǎng)頁(yè)及相關(guān)信息，以用于很多不同的項(xiàng)目；我們姑且叫它Webtable。在Webtable里，我們將用URL作為行關(guān)鍵字，用網(wǎng)頁(yè) 的某些屬性作為列名，把網(wǎng)頁(yè)內(nèi)容存在contents:列中并用獲取該網(wǎng)頁(yè)的時(shí)間戳作為標(biāo)識(shí)，如圖一所示。

圖一：一個(gè)存儲(chǔ)Web網(wǎng)頁(yè)的范例列表片斷。行名是一個(gè)反向URL｛即com.cnn.www｝。contents列族｛原文用 family，譯為族，詳見(jiàn)列族｝ 存放網(wǎng)頁(yè)內(nèi)容，anchor列族存放引用該網(wǎng)頁(yè)的錨鏈接文本。CNN的主頁(yè)被Sports Illustrater｛即所謂SI，CNN的王牌體育節(jié)目｝和MY-look的主頁(yè)引用，因此該行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每個(gè)錨鏈接只有一個(gè)版本｛由時(shí)間戳標(biāo)識(shí)，如t9，t8｝；而contents列則有三個(gè)版本，分別由時(shí)間 戳t3，t5，和t6標(biāo)識(shí)。
行
表中的行關(guān)鍵字可以是任意字符串（目前支持最多64KB，多數(shù)情況下10－100字節(jié)足夠了）。在一個(gè)行關(guān)鍵字下的每一個(gè)讀寫(xiě)操作都是原子操作（不管讀寫(xiě)這一行里多少個(gè)不同列），這是一個(gè)設(shè)計(jì)決定，這樣在對(duì)同一行進(jìn)行并發(fā)操作時(shí)，用戶(hù)對(duì)于系統(tǒng)行為更容易理解和掌控。
Bigtable通過(guò)行關(guān)鍵字的字典序來(lái)維護(hù)數(shù)據(jù)。一張表可以動(dòng)態(tài)劃分成多個(gè)連續(xù)行。連續(xù)行在這里叫做“子表”｛tablet｝，是數(shù)據(jù)分布和負(fù)載 均衡的單位。這樣一來(lái)，讀較少的連續(xù)行就比較有效率，通常只需要較少機(jī)器之間的通信即可。用戶(hù)可以利用這個(gè)屬性來(lái)選擇行關(guān)鍵字，從而達(dá)到較好數(shù)據(jù)訪(fǎng)問(wèn)地域 性｛locality｝。舉例來(lái)說(shuō)，在Webtable里，通過(guò)反轉(zhuǎn)URL中主機(jī)名的方式，可以把同一個(gè)域名下的網(wǎng)頁(yè)組織成連續(xù)行。具體來(lái)說(shuō)，可以把 maps.google.com/index.html中的數(shù)據(jù)存放在關(guān)鍵字com.google.maps/index.html下。按照相同或?qū)傩韵?近的域名來(lái)存放網(wǎng)頁(yè)可以讓基于主機(jī)和基于域名的分析更加有效。
列族
一組列關(guān)鍵字組成了“列族”，這是訪(fǎng)問(wèn)控制的基本單位。同一列族下存放的所有數(shù)據(jù)通常都是同一類(lèi)型（同一列族下的數(shù)據(jù)可壓縮在一起）。列族必須先創(chuàng) 建，然后在能在其中的列關(guān)鍵字下存放數(shù)據(jù)；列族創(chuàng)建后，族中任何一個(gè)列關(guān)鍵字均可使用。我們希望，一張表中的不同列族不能太多（最多幾百個(gè)），并且列族在 運(yùn)作中絕少改變。作為對(duì)比，一張表可以有無(wú)限列。
列關(guān)鍵字用如下語(yǔ)法命名：列族：限定詞。 列族名必須是看得懂｛printable｝的字串，而限定詞可以是任意字符串。比如，Webtable可以有個(gè)列族叫l(wèi)anguage，存放撰寫(xiě)網(wǎng)頁(yè)的語(yǔ) 言。我們?cè)趌anguage列族中只用一個(gè)列關(guān)鍵字，用來(lái)存放每個(gè)網(wǎng)頁(yè)的語(yǔ)言標(biāo)識(shí)符。該表的另一個(gè)有用的列族是anchor；給列族的每一個(gè)列關(guān)鍵字代表 一個(gè)錨鏈接，如圖一所示。而這里的限定詞則是引用該網(wǎng)頁(yè)的站點(diǎn)名；表中一個(gè)表項(xiàng)存放的是鏈接文本。
訪(fǎng)問(wèn)控制，磁盤(pán)使用統(tǒng)計(jì)，內(nèi)存使用統(tǒng)計(jì)，均可在列族這個(gè)層面進(jìn)行。在Webtable舉例中，我們可以用這些控制來(lái)管理不同應(yīng)用：有的應(yīng)用添加新的基本數(shù)據(jù)，有的讀取基本數(shù)據(jù)并創(chuàng)建引申的列族，有的則只能瀏覽數(shù)據(jù)（甚至可能因?yàn)殡[私權(quán)原因不能瀏覽所有數(shù)據(jù)）。
時(shí)間戳
Bigtable表中每一個(gè)表項(xiàng)都可以包含同一數(shù)據(jù)的多個(gè)版本，由時(shí)間戳來(lái)索引。Bigtable的時(shí)間戳是64位整型。可以由Bigtable來(lái) 賦值，表示準(zhǔn)確到毫秒的“實(shí)時(shí)”；或者由用戶(hù)應(yīng)用程序來(lái)賦值。需要避免沖突的應(yīng)用程序必須自己產(chǎn)生具有唯一性的時(shí)間戳。不同版本的表項(xiàng)內(nèi)容按時(shí)間戳倒序排 列，即最新的排在前面。
為了簡(jiǎn)化對(duì)于不同數(shù)據(jù)版本的數(shù)據(jù)的管理，我們對(duì)每一個(gè)列族支持兩個(gè)設(shè)定，以便于Bigtable對(duì)表項(xiàng)的版本自動(dòng)進(jìn)行垃圾清除。用戶(hù)可以指明只保留表項(xiàng)的最后n個(gè)版本，或者只保留足夠新的版本（比如，只保留最近7天的內(nèi)容）。
在Webtable舉例中，我們?cè)赾ontents:列中存放確切爬行一個(gè)網(wǎng)頁(yè)的時(shí)間戳。如上所述的垃圾清除機(jī)制可以讓我們只保留每個(gè)網(wǎng)頁(yè)的最近三個(gè)版本。
3.API
BT的API提供了建立和刪除表和列族的函數(shù)．還提供了函數(shù)來(lái)修改集群，表和列族的元數(shù)據(jù)，比如說(shuō)訪(fǎng)問(wèn)權(quán)限．
// 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: 寫(xiě)入Bigtable.
在BT中，客戶(hù)應(yīng)用可以寫(xiě)或者刪除值，從每個(gè)行中找值，或者遍歷一個(gè)表中的數(shù)據(jù)子集．圖2的c++代碼是使用RowMutation抽象表示來(lái)進(jìn)行一系列的更新（為保證代碼精簡(jiǎn)，沒(méi)有包括無(wú)關(guān)的細(xì)節(jié)）．調(diào)用Apply函數(shù)，就對(duì)Ｗebtable進(jìn)行了一個(gè)原子修改：它為http://www.cnn.com/增加了一個(gè)錨點(diǎn)，并刪除了另外一個(gè)錨點(diǎn)．
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讀數(shù)據(jù).
圖3的C++代碼是使用Scanner抽象來(lái)遍歷一個(gè)行內(nèi)的所有錨點(diǎn)．客戶(hù)可以遍歷多個(gè)列族．有很多方法可以限制一次掃描中產(chǎn)生的行，列和時(shí)間戳． 例如，我們可以限制上面的掃描，讓它只找到那些匹配正則表達(dá)式*.cnn.com的錨點(diǎn)，或者那些時(shí)間戳在當(dāng)前時(shí)間前10天的錨點(diǎn)．
BT還支持其他一些更復(fù)雜的處理數(shù)據(jù)的功能．首先，BT支持單行處理．這個(gè)功能可以用來(lái)對(duì)存儲(chǔ)在一個(gè)行關(guān)鍵字下的數(shù)據(jù)進(jìn)行原子的讀-修改-寫(xiě)操作． BT目前不支持跨行關(guān)鍵字的處理，但是它有一個(gè)界面，可以用來(lái)讓客戶(hù)進(jìn)行批量的跨行關(guān)鍵字處理操作．其次，BT允許把每個(gè)表項(xiàng)用做整數(shù)記數(shù)器．最后，BT 支持在服務(wù)器的地址空間內(nèi)執(zhí)行客戶(hù)端提供的腳本程序．腳本程序的語(yǔ)言是google開(kāi)發(fā)的Sawzall[28]數(shù)據(jù)處理語(yǔ)言．目前，我們基于的 Sawzall的API還不允許客戶(hù)腳本程序向BT內(nèi)寫(xiě)數(shù)據(jù)，但是它允許多種形式的數(shù)據(jù)變換，基于任何表達(dá)式的過(guò)濾和通過(guò)多種操作符的摘要．
BT可以和MapReduce[12]一起使用．MapReduce是google開(kāi)發(fā)的大規(guī)模并行計(jì)算框架．我們?yōu)榫帉?xiě)了一套外層程序，使BT可以作為MapReduce處理的數(shù)據(jù)源頭和輸出結(jié)果．
4.建立BT的基本單元
BT是建立在其他數(shù)個(gè)google框架單元上的．BT使用google分布式文件系統(tǒng)(GFS)[17]來(lái)存儲(chǔ)日志和數(shù)據(jù)文件{yeah, right, what else can it use, FAT32?}．一個(gè)BT集群通常在一個(gè)共享的機(jī)器池中工作，池中的機(jī)器還運(yùn)行其他的分布式應(yīng)用{雖然機(jī)器便宜的跟白菜似的，可是一樣要運(yùn)行多個(gè)程序，命苦的象小白菜}，BT和其他程序共享機(jī)器｛BT的瓶頸是ＩＯ/內(nèi)存，可以和CPU要求高的程序并存｝．BT依賴(lài)集群管理系統(tǒng)來(lái)安排工作，在共享的機(jī)器上管理資源，處理失效機(jī)器并監(jiān)視機(jī)器狀態(tài)｛典型的server farm結(jié)構(gòu)，BT是上面的應(yīng)用之一｝．
BT內(nèi)部存儲(chǔ)數(shù)據(jù)的格式是google SSTable格式．一個(gè)SSTable提供一個(gè)從關(guān)鍵字到值的映射，關(guān)鍵字和值都可以是任意字符串．映射是排序的，存儲(chǔ)的｛不會(huì)因?yàn)榈綦姸鴣G失｝，不可改寫(xiě)的．可以進(jìn)行以下操作：查詢(xún)和一個(gè)關(guān)鍵字相關(guān)的值；或者根據(jù)給出的關(guān)鍵字范圍遍歷所有的關(guān)鍵字和值．在內(nèi)部，每個(gè)SSTable包含一列數(shù)據(jù)塊（通常每個(gè)塊的大小是64KB,但是大小是可以配置的｛索引大小是16 bits，應(yīng)該是比較好的一個(gè)數(shù)｝）．塊索引（存儲(chǔ)在SSTable的最后）用來(lái)定位數(shù)據(jù)塊；當(dāng)打開(kāi)SSTable的時(shí)候，索引被讀入內(nèi)存｛性能｝．每次查找都可以用一個(gè)硬盤(pán)搜索完成｛根據(jù)索引算出數(shù)據(jù)在哪個(gè)道上，一個(gè)塊應(yīng)該不會(huì)跨兩個(gè)道，沒(méi)必要省那么點(diǎn)空間｝：首先在內(nèi)存中的索引里進(jìn)行二分查找找到數(shù)據(jù)塊的位置，然后再?gòu)挠脖P(pán)讀去數(shù)據(jù)塊．最佳情況是：整個(gè)SSTable可以被放在內(nèi)存里，這樣一來(lái)就不必訪(fǎng)問(wèn)硬盤(pán)了．｛想的美，前面是誰(shuí)口口聲聲說(shuō)要跟別人共享機(jī)器來(lái)著？你把內(nèi)存占滿(mǎn)了別人上哪睡去？｝
BT還依賴(lài)一個(gè)高度可用的，存儲(chǔ)的分布式數(shù)據(jù)鎖服務(wù)Chubby[8]｛看你怎么把這個(gè)high performance給說(shuō)圓嘍｝．一個(gè)Chubby服務(wù)由5個(gè)活的備份｛機(jī)器｝構(gòu)成，其中一個(gè)被這些備份選成主備份，并且處理請(qǐng)求．這個(gè)服務(wù)只有在大多數(shù)備份都活著并且互相通信的時(shí)候才是活的｛繞口令？去看原文吧，是在有出錯(cuò)的前提下的冗余算法｝．當(dāng)有機(jī)器失效的時(shí)候，Chubby使用Paxos算法[9,23]來(lái)保證備份的一致性｛這個(gè)問(wèn)題還是比較復(fù)雜的，建議去看引文了解一下問(wèn)題本身｝．Chubby提供了一個(gè)名字空間，里面包括了目錄和小文件｛萬(wàn)變不離其宗｝．每個(gè)目錄或者文件可以當(dāng)成一個(gè)鎖來(lái)用，讀寫(xiě)文件操作都是原子化的．Chubby客戶(hù)端的程序庫(kù)提供了對(duì)Chubby文件的一致性緩存｛究竟是提高性能還是降低性能？如果訪(fǎng)問(wèn)是分布的，就是提高性能｝．每個(gè)Chubby客戶(hù)維護(hù)一個(gè)和Chubby服務(wù)的會(huì)話(huà)．如果一個(gè)客戶(hù)不能在一定時(shí)間內(nèi)更新它的會(huì)話(huà)，這個(gè)會(huì)話(huà)就過(guò)期失效了｛還是針對(duì)大server farm里機(jī)器失效的頻率設(shè)計(jì)的｝．當(dāng)一個(gè)會(huì)話(huà)失效時(shí)，其擁有的鎖和打開(kāi)的文件句柄都失效｛根本設(shè)計(jì)原則：失效時(shí)回到安全狀態(tài)｝．Chubby客戶(hù)可以在文件和目錄上登記回調(diào)函數(shù)，以獲得改變或者會(huì)話(huà)過(guò)期的通知．｛翻到這里，有沒(méi)有人聞到j(luò)ava的味道了？｝
BT使用Chubby來(lái)做以下幾個(gè)任務(wù)：保證任何時(shí)間最多只有一個(gè)活躍的主備份；來(lái)存儲(chǔ)BT數(shù)據(jù)的啟動(dòng)位置（參考5.1節(jié)）；發(fā)現(xiàn)小表 （tablet）服務(wù)器，并完成tablet服務(wù)器消亡的善后（5.2節(jié)）；存儲(chǔ)BT數(shù)據(jù)的模式信息（每張表的列信息）；以及存儲(chǔ)訪(fǎng)問(wèn)權(quán)限列表．如果有相當(dāng)長(zhǎng)的時(shí)間Chubby不能訪(fǎng)問(wèn)，BT就也不能訪(fǎng)問(wèn)了｛任何系統(tǒng)都有其弱點(diǎn)｝．最近我們?cè)谑褂?1個(gè)Chubby服務(wù)實(shí)例的14個(gè)BT集群中度量了這個(gè)效果，由于Chubby不能訪(fǎng)問(wèn)而導(dǎo)致BT中部分?jǐn)?shù)據(jù)不能訪(fǎng)問(wèn)的平均百分比是0.0047%,這里Chubby不能訪(fǎng)問(wèn)的原因是Chubby本身失效或者網(wǎng)絡(luò)問(wèn)題．單個(gè)集群里，受影響最大的百分比是0.0326%｛基于文件系統(tǒng)的Chubby還是很穩(wěn)定的｝.

GFS是一個(gè)可擴(kuò)展的分布式文件系統(tǒng)，用于大型的、分布式的、對(duì)大量數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)的應(yīng)用。它運(yùn)行于廉價(jià)的普通硬件上，但可以提供容錯(cuò)功能。它可以給大量的用戶(hù)提供總體性能較高的服務(wù)。
出處：http://labs.google.com/papers/gfs.html
1、設(shè)計(jì)概覽
（1）設(shè)計(jì)想定
GFS與過(guò)去的分布式文件系統(tǒng)有很多相同的目標(biāo)，但GFS的設(shè)計(jì)受到了當(dāng)前及預(yù)期的應(yīng)用方面的工作量及技術(shù)環(huán)境的驅(qū)動(dòng)，這反映了它與早期的文件系統(tǒng)明顯不同的設(shè)想。這就需要對(duì)傳統(tǒng)的選擇進(jìn)行重新檢驗(yàn)并進(jìn)行完全不同的設(shè)計(jì)觀(guān)點(diǎn)的探索。
GFS與以往的文件系統(tǒng)的不同的觀(guān)點(diǎn)如下：
1、部件錯(cuò)誤不再被當(dāng)作異常，而是將其作為常見(jiàn)的情況加以處理。因?yàn)槲募到y(tǒng)由成百上千個(gè)用于存儲(chǔ)的機(jī)器構(gòu)成，而這 些機(jī)器是由廉價(jià)的普通部件組成并被大量的客戶(hù)機(jī)訪(fǎng)問(wèn)。部件的數(shù)量和質(zhì)量使得一些機(jī)器隨時(shí)都有可能無(wú)法工作并且有一部分還可能無(wú)法恢復(fù)。所以實(shí)時(shí)地監(jiān)控、錯(cuò) 誤檢測(cè)、容錯(cuò)、自動(dòng)恢復(fù)對(duì)系統(tǒng)來(lái)說(shuō)必不可少。
2、按照傳統(tǒng)的標(biāo)準(zhǔn)，文件都非常大。長(zhǎng)度達(dá)幾個(gè)GB的文件是很平常的。每個(gè)文件通常包含很多應(yīng)用對(duì)象。當(dāng)經(jīng)常要處理 快速增長(zhǎng)的、包含數(shù)以萬(wàn)計(jì)的對(duì)象、長(zhǎng)度達(dá)TB的數(shù)據(jù)集時(shí)，我們很難管理成千上萬(wàn)的KB規(guī)模的文件塊，即使底層文件系統(tǒng)提供支持。因此，設(shè)計(jì)中操作的參數(shù)、 塊的大小必須要重新考慮。對(duì)大型的文件的管理一定要能做到高效，對(duì)小型的文件也必須支持，但不必優(yōu)化。

3、大部分文件的更新是通過(guò)添加 新數(shù)據(jù)完成的，而不是改變已存在的數(shù)據(jù)。在一個(gè)文件中隨機(jī)的操作在實(shí)踐中幾乎不存在。一旦寫(xiě)完，文件就只可讀，很多數(shù)據(jù)都有這些特性。一些數(shù)據(jù)可能組成一 個(gè)大倉(cāng)庫(kù)以供數(shù)據(jù)分析程序掃描。有些是運(yùn)行中的程序連續(xù)產(chǎn)生的數(shù)據(jù)流。有些是檔案性質(zhì)的數(shù)據(jù)，有些是在某個(gè)機(jī)器上產(chǎn)生、在另外一個(gè)機(jī)器上處理的中間數(shù)據(jù)。 由于這些對(duì)大型文件的訪(fǎng)問(wèn)方式，添加操作成為性能優(yōu)化和原子性保證的焦點(diǎn)。而在客戶(hù)機(jī)中緩存數(shù)據(jù)塊則失去了吸引力。
4、工作量主要由兩種讀操作構(gòu)成：對(duì)大量數(shù)據(jù)的流方式的讀操作和對(duì)少量數(shù)據(jù)的隨機(jī)方式的讀操作。在前一種讀操作中， 可能要讀幾百KB，通常達(dá) 1MB和更多。來(lái)自同一個(gè)客戶(hù)的連續(xù)操作通常會(huì)讀文件的一個(gè)連續(xù)的區(qū)域。隨機(jī)的讀操作通常在一個(gè)隨機(jī)的偏移處讀幾個(gè)KB。性能敏感的應(yīng)用程序通常將對(duì)少量 數(shù)據(jù)的讀操作進(jìn)行分類(lèi)并進(jìn)行批處理以使得讀操作穩(wěn)定地向前推進(jìn)，而不要讓它來(lái)來(lái)回回的讀。
5、工作量還包含許多對(duì)大量數(shù)據(jù)進(jìn)行的、連續(xù)的、向文件添加數(shù)據(jù)的寫(xiě)操作。所寫(xiě)的數(shù)據(jù)的規(guī)模和讀相似。一旦寫(xiě)完，文件很少改動(dòng)。在隨機(jī)位置對(duì)少量數(shù)據(jù)的寫(xiě)操作也支持，但不必非常高效。
6、系統(tǒng)必須高效地實(shí)現(xiàn)定義完好的大量客戶(hù)同時(shí)向同一個(gè)文件的添加操作的語(yǔ)義。
（2）系統(tǒng)接口
GFS提供了一個(gè)相似地文件系統(tǒng)界面，雖然它沒(méi)有向POSIX那樣實(shí)現(xiàn)標(biāo)準(zhǔn)的API。文件在目錄中按層次組織起來(lái)并由路徑名標(biāo)識(shí)。
（3）體系結(jié)構(gòu)：
一個(gè)GFS集群由一個(gè)master和大量的chunkserver構(gòu)成，并被許多客戶(hù)（Client）訪(fǎng)問(wèn)。如圖1 所示。Master和 chunkserver通常是運(yùn)行用戶(hù)層服務(wù)進(jìn)程的Linux機(jī)器。只要資源和可靠性允許，chunkserver和client可以運(yùn)行在同一個(gè)機(jī)器 上。
文件被分成固定大小的塊。每個(gè)塊由一個(gè)不變的、全局唯一的64位的chunk－h(huán)andle標(biāo)識(shí)，chunk－ handle是在塊創(chuàng)建時(shí)由 master分配的。ChunkServer將塊當(dāng)作Linux文件存儲(chǔ)在本地磁盤(pán)并可以讀和寫(xiě)由chunk－h(huán)andle和位區(qū)間指定的數(shù)據(jù)。出于可靠 性考慮，每一個(gè)塊被復(fù)制到多個(gè)chunkserver上。默認(rèn)情況下，保存3個(gè)副本，但這可以由用戶(hù)指定。
Master維護(hù)文件系統(tǒng)所以的元數(shù)據(jù)（metadata），包括名字空間、訪(fǎng)問(wèn)控制信息、從文件到塊的映射以及塊 的當(dāng)前位置。它也控制系統(tǒng)范圍的活動(dòng)，如塊租約（lease）管理，孤兒塊的垃圾收集，chunkserver間的塊遷移。Master定期通過(guò) HeartBeat消息與每一個(gè) chunkserver通信，給chunkserver傳遞指令并收集它的狀態(tài)。
與每個(gè)應(yīng)用相聯(lián)的GFS客戶(hù)代碼實(shí)現(xiàn)了文件系統(tǒng)的API并與master和chunkserver通信以代表應(yīng)用程序讀和寫(xiě)數(shù)據(jù)。客戶(hù)與master的交換只限于對(duì)元數(shù)據(jù)（metadata）的操作，所有數(shù)據(jù)方面的通信都直接和chunkserver聯(lián)系。
客戶(hù)和chunkserver都不緩存文件數(shù)據(jù)。因?yàn)橛脩?hù)緩存的益處微乎其微，這是由于數(shù)據(jù)太多或工作集太大而無(wú)法 緩存。不緩存數(shù)據(jù)簡(jiǎn)化了客戶(hù)程序和整個(gè)系統(tǒng)，因?yàn)椴槐乜紤]緩存的一致性問(wèn)題。但用戶(hù)緩存元數(shù)據(jù)（metadata）。Chunkserver也不必緩存文 件，因?yàn)閴K時(shí)作為本地文件存儲(chǔ)的。
（4）單master。
只有一個(gè)master也極大的簡(jiǎn)化了設(shè)計(jì)并使得master可以根據(jù)全局情況作出先進(jìn)的塊放置和復(fù)制決定。但是我們 必須要將master對(duì)讀和寫(xiě)的參與減至最少，這樣它才不會(huì)成為系統(tǒng)的瓶頸。Client從來(lái)不會(huì)從master讀和寫(xiě)文件數(shù)據(jù)。Client只是詢(xún)問(wèn) master它應(yīng)該和哪個(gè) chunkserver聯(lián)系。Client在一段限定的時(shí)間內(nèi)將這些信息緩存，在后續(xù)的操作中Client直接和chunkserver交互。
以圖1解釋一下一個(gè)簡(jiǎn)單的讀操作的交互。
1、client使用固定的塊大小將應(yīng)用程序指定的文件名和字節(jié)偏移轉(zhuǎn)換成文件的一個(gè)塊索引（chunk index）。

2、給master發(fā)送一個(gè)包含文件名和塊索引的請(qǐng)求。
3、master回應(yīng)對(duì)應(yīng)的chunk handle和副本的位置（多個(gè)副本）。
4、client以文件名和塊索引為鍵緩存這些信息。（handle和副本的位置）。
5、Client 向其中一個(gè)副本發(fā)送一個(gè)請(qǐng)求，很可能是最近的一個(gè)副本。請(qǐng)求指定了chunk handle（chunkserver以chunk handle標(biāo)識(shí)chunk）和塊內(nèi)的一個(gè)字節(jié)區(qū)間。
6、除非緩存的信息不再有效（cache for a limited time）或文件被重新打開(kāi)，否則以后對(duì)同一個(gè)塊的讀操作不再需要client和master間的交互。
通常Client可以在一個(gè)請(qǐng)求中詢(xún)問(wèn)多個(gè)chunk的地址，而master也可以很快回應(yīng)這些請(qǐng)求。
（5）塊規(guī)模：
塊規(guī)模是設(shè)計(jì)中的一個(gè)關(guān)鍵參數(shù)。我們選擇的是64MB，這比一般的文件系統(tǒng)的塊規(guī)模要大的多。每個(gè)塊的副本作為一個(gè)普通的Linux文件存儲(chǔ)，在需要的時(shí)候可以擴(kuò)展。
塊規(guī)模較大的好處有：
1、減少client和master之間的交互。因?yàn)樽x寫(xiě)同一個(gè)塊只是要在開(kāi)始時(shí)向master請(qǐng)求塊位置信息。對(duì)于讀寫(xiě)大型文件這種減少尤為重要。即使對(duì)于訪(fǎng)問(wèn)少量數(shù)據(jù)的隨機(jī)讀操作也可以很方便的為一個(gè)規(guī)模達(dá)幾個(gè)TB的工作集緩緩存塊位置信息。
2、Client在一個(gè)給定的塊上很可能執(zhí)行多個(gè)操作，和一個(gè)chunkserver保持較長(zhǎng)時(shí)間的TCP連接可以減少網(wǎng)絡(luò)負(fù)載。
3、這減少了master上保存的元數(shù)據(jù)（metadata）的規(guī)模，從而使得可以將metadata放在內(nèi)存中。這又會(huì)帶來(lái)一些別的好處。
不利的一面：
一個(gè)小文件可能只包含一個(gè)塊，如果很多Client訪(fǎng)問(wèn)改文件的話(huà)，存儲(chǔ)這些塊的chunkserver將成為訪(fǎng)問(wèn)的熱點(diǎn)。但在實(shí)際應(yīng)用中，應(yīng)用程序通常順序地讀包含多個(gè)塊的文件，所以這不是一個(gè)主要問(wèn)題。
（6）元數(shù)據(jù)（metadata）：
master存儲(chǔ)了三中類(lèi)型的metadata：文件的名字空間和塊的名字空間，從文件到塊的映射，塊的副本的位 置。所有的metadata都放在內(nèi)存中。前兩種類(lèi)型的metadata通過(guò)向操作日志登記修改而保持不變，操作日志存儲(chǔ)在master的本地磁盤(pán)并在幾 個(gè)遠(yuǎn)程機(jī)器上留有副本。使用日志使得我們可以很簡(jiǎn)單地、可靠地更新master的狀態(tài)，即使在master崩潰的情況下也不會(huì)有不一致的問(wèn)題。相反， mater在每次啟動(dòng)以及當(dāng)有 chuankserver加入的時(shí)候詢(xún)問(wèn)每個(gè)chunkserver的所擁有的塊的情況。
A、內(nèi)存數(shù)據(jù)結(jié)構(gòu)：
因?yàn)閙etadata存儲(chǔ)在內(nèi)存中，所以master的操作很快。進(jìn)一步，master可以輕易而且高效地定期在后臺(tái)掃描它的整個(gè)狀態(tài)。這種定期地掃描被用于實(shí)現(xiàn)塊垃圾收集、chunkserver出現(xiàn)故障時(shí)的副本復(fù)制、為平衡負(fù)載和磁盤(pán)空間而進(jìn)行的塊遷移。
這種方法的一個(gè)潛在的問(wèn)題就是塊的數(shù)量也即整個(gè)系統(tǒng)的容量是否受限與master的內(nèi)存。實(shí)際上，這并不是一個(gè)嚴(yán)重 的問(wèn)題。Master為每個(gè) 64MB的塊維護(hù)的metadata不足64個(gè)字節(jié)。除了最后一塊，文件所有的塊都是滿(mǎn)的。類(lèi)似的，每個(gè)文件的名字空間數(shù)據(jù)也不足64個(gè)字節(jié)，因?yàn)槲募?是以一種事先確定的壓縮方式存儲(chǔ)的.如果要支持更大的文件系統(tǒng)，那么增加一些內(nèi)存的方法對(duì)于我們將元數(shù)據(jù)（metadata）保存在內(nèi)存種所獲得的簡(jiǎn)單 性、可靠性、高性能和靈活性來(lái)說(shuō)，這只是一個(gè)很小的代價(jià)。
B、塊位置：

master并不為chunkserver所擁有的塊的副本的保存一個(gè)不變的記錄。它在啟動(dòng)時(shí)通過(guò)簡(jiǎn)單的查詢(xún)來(lái)獲得這些信息。Master可以保持這些信息的更新，因?yàn)樗刂扑袎K的放置并通過(guò)HeartBeat消息來(lái)監(jiān)控chunkserver的狀態(tài)。
這樣做的好處：因?yàn)閏hunkserver可能加入或離開(kāi)集群、改變路徑名、崩潰、重啟等，一個(gè)集群重有成百個(gè)server，這些事件經(jīng)常發(fā)生，這種方法就排除了master與chunkserver之間的同步問(wèn)題。
另一個(gè)原因是：只有chunkserver才能確定它自己到底有哪些塊，由于錯(cuò)誤，chunkserver中的一些塊可能會(huì)很自然的消失，這樣在master中就沒(méi)有必要為此保存一個(gè)不變的記錄。
C、操作日志：
操作日志包含了對(duì)metadata所作的修改的歷史記錄。它作為邏輯時(shí)間線(xiàn)定義了并發(fā)操作的執(zhí)行順序。文件、塊以及它們的版本號(hào)都由它們被創(chuàng)建時(shí)的邏輯時(shí)間而唯一地、永久地被標(biāo)識(shí)。
操作日志是如此的重要，我們必須要將它可靠地保存起來(lái)，并且只有在metadata的改變固定下來(lái)之后才將變化呈現(xiàn)給用戶(hù)。所以我們將操作日志復(fù)制到數(shù)個(gè)遠(yuǎn)程的機(jī)器上，并且只有在將相應(yīng)的日志記錄寫(xiě)到本地和遠(yuǎn)程的磁盤(pán)上之后才回答用戶(hù)的請(qǐng)求。
Master可以用操作日志來(lái)恢復(fù)它的文件系統(tǒng)的狀態(tài)。為了將啟動(dòng)時(shí)間減至最小，日志就必須要比較小。每當(dāng)日志的長(zhǎng)度增長(zhǎng)到超過(guò)一定的規(guī)模后，master就要檢查它的狀態(tài)，它可以從本地磁盤(pán)裝入最近的檢查點(diǎn)來(lái)恢復(fù)狀態(tài)。
創(chuàng)建一個(gè)檢查點(diǎn)比較費(fèi)時(shí)，master的內(nèi)部狀態(tài)是以一種在創(chuàng)建一個(gè)檢查點(diǎn)時(shí)并不耽誤即將到來(lái)的修改操作的方式來(lái)組 織的。Master切換到一個(gè)新的日子文件并在一個(gè)單獨(dú)的線(xiàn)程中創(chuàng)建檢查點(diǎn)。這個(gè)新的檢查點(diǎn)記錄了切換前所有的修改。在一個(gè)有數(shù)十萬(wàn)文件的集群中用一分鐘 左右就能完成。創(chuàng)建完后，將它寫(xiě)入本地和遠(yuǎn)程的磁盤(pán)。
（7）數(shù)據(jù)完整性
名字空間的修改必須是原子性的，它們只能有master處理：名字空間鎖保證了操作的原子性和正確性，而master的操作日志在全局范圍內(nèi)定義了這些操作的順序。

文 件區(qū)間的狀態(tài)在修改之后依賴(lài)于修改的類(lèi)型，不論操作成功還是失敗，也不論是不是并發(fā)操作。如果不論從哪個(gè)副本上讀，所有的客戶(hù)都看到同樣的數(shù)據(jù)，那么文件 的這個(gè)區(qū)域就是一致的。如果文件的區(qū)域是一致的并且用戶(hù)可以看到修改操作所寫(xiě)的數(shù)據(jù)，那么它就是已定義的。如果修改是在沒(méi)有并發(fā)寫(xiě)操作的影響下完成的，那 么受影響的區(qū)域是已定義的，所有的client都能看到寫(xiě)的內(nèi)容。成功的并發(fā)寫(xiě)操作是未定義但卻是一致的。失敗的修改將使區(qū)間處于不一致的狀態(tài)。
Write操作在應(yīng)用程序指定的偏移處寫(xiě)入數(shù)據(jù)，而record append操作使得數(shù)據(jù)（記錄）即使在有并發(fā)修改操作的情況下也至少原子性的被加到GFS指定的偏移處，偏移地址被返回給用戶(hù)。

在一系列成功的修改操作后，最后的修改操作保證文件區(qū)域是已定義的。GFS通過(guò)對(duì)所有的副本執(zhí)行同樣順序的修改操作并且使用塊版本號(hào)檢測(cè)過(guò)時(shí)的副本（由于chunkserver退出而導(dǎo)致丟失修改）來(lái)做到這一點(diǎn)。
因?yàn)橛脩?hù)緩存了會(huì)位置信息，所以在更新緩存之前有可能從一個(gè)過(guò)時(shí)的副本中讀取數(shù)據(jù)。但這有緩存的截止時(shí)間和文件的重新打開(kāi)而受到限制。
在修改操作成功后，部件故障仍可以是數(shù)據(jù)受到破壞。GFS通過(guò)master和chunkserver間定期的handshake，借助校驗(yàn)和來(lái)檢測(cè)對(duì)數(shù)據(jù)的破壞。一旦檢測(cè)到，就從一個(gè)有效的副本盡快重新存儲(chǔ)。只有在GFS檢測(cè)前，所有的副本都失效，這個(gè)塊才會(huì)丟失。
2、系統(tǒng)交互
（1）租約（lease）和修改順序
（2）數(shù)據(jù)流
我們的目標(biāo)是充分利用每個(gè)機(jī)器的網(wǎng)絡(luò)帶寬，避免網(wǎng)絡(luò)瓶頸和延遲
為了有效的利用網(wǎng)絡(luò)，我們將數(shù)據(jù)流和控制流分離。數(shù)據(jù)是以流水線(xiàn)的方式在選定的chunkerserver鏈上線(xiàn)性的傳遞的。每個(gè)機(jī)器的整個(gè)對(duì)外帶寬都被用作傳遞數(shù)據(jù)。為避免瓶頸，每個(gè)機(jī)器在收到數(shù)據(jù)后，將它收到數(shù)據(jù)盡快傳遞給離它最近的機(jī)器。

（3）原子性的record Append：
GFS提供了一個(gè)原子性的添加操作：record append。在傳統(tǒng)的寫(xiě)操作中，client指定被寫(xiě)數(shù)據(jù)的偏移位置，向同一個(gè)區(qū)間的并發(fā)的寫(xiě)操作是不連續(xù)的：區(qū)間有可能包含來(lái)自多個(gè)client的數(shù) 據(jù)碎片。在record append中， client只是指定數(shù)據(jù)。GFS在其選定的偏移出將數(shù)據(jù)至少原子性的加入文件一次，并將偏移返回給client。
在分布式的應(yīng)用中，不同機(jī)器上的許多client可能會(huì)同時(shí)向一個(gè)文件執(zhí)行添加操作，添加操作被頻繁使用。如果用傳 統(tǒng)的write操作，可能需要額外的、復(fù)雜的、開(kāi)銷(xiāo)較大的同步，例如通過(guò)分布式鎖管理。在我們的工作量中，這些文件通常以多個(gè)生產(chǎn)者單個(gè)消費(fèi)者隊(duì)列的方式 或包含從多個(gè)不同 client的綜合結(jié)果。
Record append和前面講的write操作的控制流差不多，只是在primary上多了一些邏輯判斷。首先，client將數(shù)據(jù)發(fā)送到文件最后一塊的所有副本 上。然后向primary發(fā)送請(qǐng)求。Primary檢查添加操作是否會(huì)導(dǎo)致該塊超過(guò)最大的規(guī)模（64M）。如果這樣，它將該塊擴(kuò)充到最大規(guī)模，并告訴其它 副本做同樣的事，同時(shí)通知client該操作需要在下一個(gè)塊上重新嘗試。如果記錄滿(mǎn)足最大規(guī)模的要求，primary就會(huì)將數(shù)據(jù)添加到它的副本上，并告訴 其它的副本在在同樣的偏移處寫(xiě)數(shù)據(jù)，最后primary向client報(bào)告寫(xiě)操作成功。如果在任何一個(gè)副本上record append操作失敗，client將重新嘗試該操作。這時(shí)候，同一個(gè)塊的副本可能包含不同的數(shù)據(jù)，因?yàn)橛械目赡軓?fù)制了全部的數(shù)據(jù)，有的可能只復(fù)制了部 分。GFS不能保證所有的副本每個(gè)字節(jié)都是一樣的。它只保證每個(gè)數(shù)據(jù)作為一個(gè)原子單元被寫(xiě)過(guò)至少一次。這個(gè)是這樣得出的：操作要是成功，數(shù)據(jù)必須在所有的 副本上的同樣的偏移處被寫(xiě)過(guò)。進(jìn)一步，從這以后，所有的副本至少和記錄一樣長(zhǎng)，所以后續(xù)的記錄將被指定到更高的偏移處或者一個(gè)不同的塊上，即使另一個(gè)副本 成了primary。根據(jù)一致性保證，成功的record append操作的區(qū)間是已定義的。而受到干擾的區(qū)間是不一致的。
（4）快照（snapshot）
快照操作幾乎在瞬間構(gòu)造一個(gè)文件和目錄樹(shù)的副本，同時(shí)將正在進(jìn)行的其他修改操作對(duì)它的影響減至最小。
我們使用copy-on-write技術(shù)來(lái)實(shí)現(xiàn)snapshot。當(dāng)master受到一個(gè)snapshot請(qǐng)求時(shí)， 它首先將要snapshot的文件上塊上的lease。這使得任何一個(gè)向這些塊寫(xiě)數(shù)據(jù)的操作都必須和master交互以找到擁有l(wèi)ease的副本。這就給 master一個(gè)創(chuàng)建這個(gè)塊的副本的機(jī)會(huì)。
副本被撤銷(xiāo)或終止后，master在磁盤(pán)上登記執(zhí)行的操作，然后復(fù)制源文件或目錄樹(shù)的metadata以對(duì)它的內(nèi)存狀態(tài)實(shí)施登記的操作。這個(gè)新創(chuàng)建的snapshot文件和源文件（其metadata）指向相同的塊（chunk）。
Snapshot之后，客戶(hù)第一次向chunk c寫(xiě)的時(shí)候，它發(fā)一個(gè)請(qǐng)求給master以找到擁有l(wèi)ease的副本。Master注意到chunk c的引用記數(shù)比1大，它延遲對(duì)用戶(hù)的響應(yīng)，選擇一個(gè)chunk handle C’,然后要求每一有chunk c的副本的chunkserver創(chuàng)建一個(gè)塊C’。每個(gè)chunkserver在本地創(chuàng)建chunk C’避免了網(wǎng)絡(luò)開(kāi)銷(xiāo)。從這以后和對(duì)別的塊的操作沒(méi)有什么區(qū)別。
3、MASTER操作
MASTER執(zhí)行所有名字空間的操作，除此之外，他還在系統(tǒng)范圍管理數(shù)據(jù)塊的復(fù)制：決定數(shù)據(jù)塊的放置方案，產(chǎn)生新數(shù)據(jù)塊并將其備份，和其他系統(tǒng)范圍的操作協(xié)同來(lái)確保數(shù)據(jù)備份的完整性，在所有的數(shù)據(jù)塊服務(wù)器之間平衡負(fù)載并收回沒(méi)有使用的存儲(chǔ)空間。
3.1 名字空間管理和加鎖
與傳統(tǒng)文件系統(tǒng)不同的是，GFS沒(méi)有與每個(gè)目錄相關(guān)的能列出其所有文件的數(shù)據(jù)結(jié)構(gòu)，它也不支持別名（unix中的硬連接或符號(hào)連接），不管是對(duì)文件或是目錄。GFS的名字空間邏輯上是從文件元數(shù)據(jù)到路徑名映射的一個(gè)查用表。
MASTER在執(zhí)行某個(gè)操作前都要獲得一系列鎖，例如，它要對(duì)/d1/d2…/dn/leaf執(zhí)行操作，則它必須獲 得/d1，/d1/d2，…， /d1/d2/…/dn的讀鎖，/d1/d2…/dn/leaf的讀鎖或?qū)戞i（其中l(wèi)eaf可以使文件也可以是目錄）。MASTER操作的并行性和數(shù)據(jù)的 一致性就是通過(guò)這些鎖來(lái)實(shí)現(xiàn)的。
3.2 備份存儲(chǔ)放置策略
一個(gè)GFS集群文件系統(tǒng)可能是多層分布的。一般情況下是成千上萬(wàn)個(gè)文件塊服務(wù)器分布于不同的機(jī)架上，而這些文件塊服 務(wù)器又被分布于不同機(jī)架上的客戶(hù)來(lái)訪(fǎng)問(wèn)。因此，不同機(jī)架上的兩臺(tái)機(jī)器之間的通信可能通過(guò)一個(gè)或多個(gè)交換機(jī)。數(shù)據(jù)塊冗余配置策略要達(dá)到連個(gè)目的：最大的數(shù)據(jù) 可靠性和可用性，最大的網(wǎng)絡(luò)帶寬利用率。因此，如果僅僅把數(shù)據(jù)的拷貝置于不同的機(jī)器上很難滿(mǎn)足這兩個(gè)要求，必須在不同的機(jī)架上進(jìn)行數(shù)據(jù)備份。這樣即使整個(gè) 機(jī)架被毀或是掉線(xiàn)，也能確保數(shù)據(jù)的正常使用。這也使數(shù)據(jù)傳輸，尤其是讀數(shù)據(jù)，可以充分利用帶寬，訪(fǎng)問(wèn)到多個(gè)機(jī)架，而寫(xiě)操作，則不得不涉及到更多的機(jī)架。
3.3 產(chǎn)生、重復(fù)制、重平衡數(shù)據(jù)塊
當(dāng)MASTER產(chǎn)生新的數(shù)據(jù)塊時(shí)，如何放置新數(shù)據(jù)塊，要考慮如下幾個(gè)因素：（1）盡量放置在磁盤(pán)利用率低的數(shù)據(jù)塊服 務(wù)器上，這樣，慢慢地各服務(wù)器的磁盤(pán)利用率就會(huì)達(dá)到平衡。（2）盡量控制在一個(gè)服務(wù)器上的“新創(chuàng)建”的次數(shù)。（3）由于上一小節(jié)討論的原因，我們需要把數(shù) 據(jù)塊放置于不同的機(jī)架上。
MASTER在可用的數(shù)據(jù)塊備份低于用戶(hù)設(shè)定的數(shù)目時(shí)需要進(jìn)行重復(fù)制。這種情況源于多種原因：服務(wù)器不可用，數(shù)據(jù)被 破壞，磁盤(pán)被破壞，或者備份數(shù)目被修改。每個(gè)被需要重復(fù)制的數(shù)據(jù)塊的優(yōu)先級(jí)根據(jù)以下幾項(xiàng)確定：第一是現(xiàn)在的數(shù)目距目標(biāo)的距離，對(duì)于能阻塞用戶(hù)程序的數(shù)據(jù) 塊，我們也提高它的優(yōu)先級(jí)。最后， MASTER按照產(chǎn)生數(shù)據(jù)塊的原則復(fù)制數(shù)據(jù)塊，并把它們放到不同的機(jī)架內(nèi)的服務(wù)器上。
MASTER周期性的平衡各服務(wù)器上的負(fù)載：它檢查chunk分布和負(fù)載平衡，通過(guò)這種方式來(lái)填充一個(gè)新的服務(wù)器而 不是把其他的內(nèi)容統(tǒng)統(tǒng)放置到它上面帶來(lái)大量的寫(xiě)數(shù)據(jù)。數(shù)據(jù)塊放置的原則與上面討論的相同，此外，MASTER還決定那些數(shù)據(jù)塊要被移除，原則上他會(huì)清除那 些空閑空間低于平均值的那些服務(wù)器。
3.4 垃圾收集
在一個(gè)文件被刪除之后，GFS并不立即收回磁盤(pán)空間，而是等到垃圾收集程序在文件和數(shù)據(jù)塊級(jí)的的檢查中收回。
當(dāng)一個(gè)文件被應(yīng)用程序刪除之后，MASTER會(huì)立即記錄下這些變化，但文件所占用的資源卻不會(huì)被立即收回，而是重新 給文件命了一個(gè)隱藏的名字，并附上了刪除的時(shí)間戳。在MASTER定期檢查名字空間時(shí)，它刪除超過(guò)三天（可以設(shè)定）的隱藏的文件。在此之前，可以以一個(gè)新 的名字來(lái)讀文件，還可以以前的名字恢復(fù)。當(dāng)隱藏的文件在名字空間中被刪除以后，它在內(nèi)存中的元數(shù)據(jù)即被擦除，這就有效地切斷了他和所有數(shù)據(jù)塊的聯(lián)系。
在一個(gè)相似的定期的名字空間檢查中，MASTER確認(rèn)孤兒數(shù)據(jù)塊（不屬于任何文件）并擦除他的元數(shù)據(jù)，在和MASTER的心跳信息交換中，每個(gè)服務(wù)器報(bào)告他所擁有的數(shù)據(jù)塊，MASTER返回元數(shù)據(jù)不在內(nèi)存的數(shù)據(jù)塊，服務(wù)器即可以刪除這些數(shù)據(jù)塊。
3.5 過(guò)時(shí)數(shù)據(jù)的探測(cè)
在數(shù)據(jù)更新時(shí)如果服務(wù)器停機(jī)了，那么他所保存的數(shù)據(jù)備份就會(huì)過(guò)時(shí)。對(duì)每個(gè)數(shù)據(jù)塊，MASTER設(shè)置了一個(gè)版本號(hào)來(lái)區(qū)別更新過(guò)的數(shù)據(jù)塊和過(guò)時(shí)的數(shù)據(jù)塊。
當(dāng)MASTER授權(quán)一個(gè)新的lease時(shí)，他會(huì)增加數(shù)據(jù)塊的版本號(hào)并會(huì)通知更新數(shù)據(jù)備份。MASTER和備份都會(huì)記 錄下當(dāng)前的版本號(hào)，如果一個(gè)備份當(dāng)時(shí)不可用，那么他的版本號(hào)不可能提高，當(dāng)ChunkServer重新啟動(dòng)并向MASTER報(bào)告他的數(shù)據(jù)塊集時(shí)， MASTER就會(huì)發(fā)現(xiàn)過(guò)時(shí)的數(shù)據(jù)。
MASTER在定期的垃圾收集程序中清除過(guò)時(shí)的備份，在此以前，處于效率考慮，在各客戶(hù)及英大使，他會(huì)認(rèn)為根本不存 在過(guò)時(shí)的數(shù)據(jù)。作為另一個(gè)安全措施， MASTER在給客戶(hù)及關(guān)于數(shù)據(jù)塊的應(yīng)答或是另外一個(gè)讀取數(shù)據(jù)的服務(wù)器數(shù)據(jù)是都會(huì)帶上版本信息，在操作前客戶(hù)機(jī)和服務(wù)器會(huì)驗(yàn)證版本信息以確保得到的是最新 的數(shù)據(jù)。
4、容錯(cuò)和診斷
4.1 高可靠性
4.1.1 快速恢復(fù)
不管如何終止服務(wù)，MASTER和數(shù)據(jù)塊服務(wù)器都會(huì)在幾秒鐘內(nèi)恢復(fù)狀態(tài)和運(yùn)行。實(shí)際上，我們不對(duì)正常終止和不正常終止進(jìn)行區(qū)分，服務(wù)器進(jìn)程都會(huì)被切斷而終止。客戶(hù)機(jī)和其他的服務(wù)器會(huì)經(jīng)歷一個(gè)小小的中斷，然后它們的特定請(qǐng)求超時(shí)，重新連接重啟的服務(wù)器，重新請(qǐng)求。
4.1.2 數(shù)據(jù)塊備份
如上文所討論的，每個(gè)數(shù)據(jù)塊都會(huì)被備份到放到不同機(jī)架上的不同服務(wù)器上。對(duì)不同的名字空間，用戶(hù)可以設(shè)置不同的備份級(jí)別。在數(shù)據(jù)塊服務(wù)器掉線(xiàn)或是數(shù)據(jù)被破壞時(shí)，MASTER會(huì)按照需要來(lái)復(fù)制數(shù)據(jù)塊。
4.1.3 MASTER備份
為確保可靠性，MASTER的狀態(tài)、操作記錄和檢查點(diǎn)都在多臺(tái)機(jī)器上進(jìn)行了備份。一個(gè)操作只有在數(shù)據(jù)塊服務(wù)器硬盤(pán)上 刷新并被記錄在MASTER和其備份的上之后才算是成功的。如果MASTER或是硬盤(pán)失敗，系統(tǒng)監(jiān)視器會(huì)發(fā)現(xiàn)并通過(guò)改變域名啟動(dòng)它的一個(gè)備份機(jī)，而客戶(hù)機(jī) 則僅僅是使用規(guī)范的名稱(chēng)來(lái)訪(fǎng)問(wèn)，并不會(huì)發(fā)現(xiàn)MASTER的改變。
4.2 數(shù)據(jù)完整性
每個(gè)數(shù)據(jù)塊服務(wù)器都利用校驗(yàn)和來(lái)檢驗(yàn)存儲(chǔ)數(shù)據(jù)的完整性。原因：每個(gè)服務(wù)器隨時(shí)都有發(fā)生崩潰的可能性，并且在兩個(gè)服務(wù)器間比較數(shù)據(jù)塊也是不現(xiàn)實(shí)的，同時(shí)，在兩臺(tái)服務(wù)器間拷貝數(shù)據(jù)并不能保證數(shù)據(jù)的一致性。
每個(gè)Chunk按64kB的大小分成塊，每個(gè)塊有32位的校驗(yàn)和，校驗(yàn)和和日志存儲(chǔ)在一起，和用戶(hù)數(shù)據(jù)分開(kāi)。
在讀數(shù)據(jù)時(shí)，服務(wù)器首先檢查與被讀內(nèi)容相關(guān)部分的校驗(yàn)和，因此，服務(wù)器不會(huì)傳播錯(cuò)誤的數(shù)據(jù)。如果所檢查的內(nèi)容和校驗(yàn) 和不符，服務(wù)器就會(huì)給數(shù)據(jù)請(qǐng)求者返回一個(gè)錯(cuò)誤的信息，并把這個(gè)情況報(bào)告給MASTER。客戶(hù)機(jī)就會(huì)讀其他的服務(wù)器來(lái)獲取數(shù)據(jù)，而MASTER則會(huì)從其他的 拷貝來(lái)復(fù)制數(shù)據(jù)，等到一個(gè)新的拷貝完成時(shí)，MASTER就會(huì)通知報(bào)告錯(cuò)誤的服務(wù)器刪除出錯(cuò)的數(shù)據(jù)塊。
附加寫(xiě)數(shù)據(jù)時(shí)的校驗(yàn)和計(jì)算優(yōu)化了，因?yàn)檫@是主要的寫(xiě)操作。我們只是更新增加部分的校驗(yàn)和，即使末尾部分的校驗(yàn)和數(shù)據(jù)已被損壞而我們沒(méi)有檢查出來(lái)，新的校驗(yàn)和與數(shù)據(jù)會(huì)不相符，這種沖突在下次使用時(shí)將會(huì)被檢查出來(lái)。
相反，如果是覆蓋現(xiàn)有數(shù)據(jù)的寫(xiě)，在寫(xiě)以前，我們必須檢查第一和最后一個(gè)數(shù)據(jù)塊，然后才能執(zhí)行寫(xiě)操作，最后計(jì)算和記錄校驗(yàn)和。如果我們?cè)诟采w以前不先檢查首位數(shù)據(jù)塊，計(jì)算出的校驗(yàn)和則會(huì)因?yàn)闆](méi)被覆蓋的數(shù)據(jù)而產(chǎn)生錯(cuò)誤。

在空閑時(shí)間，服務(wù)器會(huì)檢查不活躍的數(shù)據(jù)塊的校驗(yàn)和，這樣可以檢查出不經(jīng)常讀的數(shù)據(jù)的錯(cuò)誤。一旦錯(cuò)誤被檢查出來(lái)，服務(wù)器會(huì)拷貝一個(gè)正確的數(shù)據(jù)塊來(lái)代替錯(cuò)誤的。

4.3 診斷工具
廣泛而細(xì)致的診斷日志以微小的代價(jià)換取了在問(wèn)題隔離、診斷、性能分析方面起到了重大的作用。GFS服務(wù)器用日志來(lái)記 錄顯著的事件（例如服務(wù)器停機(jī)和啟動(dòng)）和遠(yuǎn)程的應(yīng)答。遠(yuǎn)程日志記錄機(jī)器之間的請(qǐng)求和應(yīng)答，通過(guò)收集不同機(jī)器上的日志記錄，并對(duì)它們進(jìn)行分析恢復(fù)，我們可以 完整地重現(xiàn)活動(dòng)的場(chǎng)景，并用此來(lái)進(jìn)行錯(cuò)誤分析。
5 測(cè)量
5.1 測(cè)試環(huán)境
一臺(tái)主控機(jī)，兩臺(tái)主控機(jī)備份，16臺(tái)數(shù)據(jù)塊服務(wù)器，16臺(tái)客戶(hù)機(jī)。
每臺(tái)機(jī)器：2塊PIII1.4G處理器，2G內(nèi)存，2塊80G5400rpm的硬盤(pán)，1塊100Mbps全雙工網(wǎng)卡
19臺(tái)服務(wù)器連接到一個(gè)HP2524交換機(jī)上，16臺(tái)客戶(hù)機(jī)倆接到領(lǐng)外一臺(tái)交換機(jī)上，兩臺(tái)交換機(jī)通過(guò)1G的鏈路相連。