【正文】 ACL同樣被保存在文件中，它是節(jié)點(diǎn)元數(shù)據(jù)的一部分，用戶在進(jìn)行相關(guān)操作時(shí)首先需要通過(guò)ACL來(lái)獲取相應(yīng)的授權(quán)。因此，可以看出Paxos算法在分布式一致性問(wèn)題中的作用是巨大的。在實(shí)際的執(zhí)行過(guò)程中，Chubby使用Paxos算法來(lái)解決這個(gè)問(wèn)題。在客戶端保存一個(gè)和單元上數(shù)據(jù)一致的本地緩存，這樣需要時(shí)客戶可以直接從緩存中取出數(shù)據(jù)而不用再和主服務(wù)器通信。9）一定時(shí)間段后（1分鐘），刪除沒(méi)有被打開(kāi)過(guò)的臨時(shí)文件夾。5）向每個(gè)會(huì)話發(fā)送一個(gè)故障事件，促使所有的客戶端清空緩存。1）產(chǎn)生一個(gè)新的紀(jì)元號(hào)以便今后客戶端通信時(shí)使用，這能保證當(dāng)前的主服務(wù)器不必處理針對(duì)舊的主服務(wù)器的請(qǐng)求。如果客戶端接收到這個(gè)回應(yīng)的時(shí)間仍處于寬限期內(nèi)，則系統(tǒng)會(huì)恢復(fù)到安全狀態(tài)，租約期更新為C3。圖210中新的主服務(wù)器很快被重新選出，當(dāng)它接到客戶端的第一個(gè)KeepAlive請(qǐng)求（圖210中的4）時(shí)會(huì)拒絕（圖210中的5），因?yàn)檫@個(gè)請(qǐng)求的紀(jì)元號(hào)（Epoch Number）錯(cuò)誤。同樣的，主服務(wù)器可能不是立刻回應(yīng)而是等待C2接近結(jié)束，但是在這個(gè)過(guò)程中主服務(wù)器出現(xiàn)故障停止使用。但是由于系統(tǒng)有一定的失效概率，引入故障處理措施是很有必要的。CCC3則是客戶端對(duì)主服務(wù)器租約期時(shí)長(zhǎng)做出的一個(gè)估計(jì)。這個(gè)指針支持一系列的操作，常用的句柄操作函數(shù)如表21所示。在實(shí)際的執(zhí)行中，為了避免所有的通信都使用序號(hào)帶來(lái)的系統(tǒng)開(kāi)銷增長(zhǎng)，Chubby引入了sequencer的概念。用戶在打開(kāi)某個(gè)節(jié)點(diǎn)時(shí)就會(huì)獲取一個(gè)類似于UNIX中文件描述符（File Descriptor）的句柄[13]（Handles），這個(gè)句柄由以下三個(gè)部分組成。1）實(shí)例號(hào)（Instance Number）：新節(jié)點(diǎn)實(shí)例號(hào)必定大于舊節(jié)點(diǎn)的實(shí)例號(hào)。例如Chubby不支持內(nèi)部文件的移動(dòng)；不記錄文件的最后訪問(wèn)時(shí)間；另外在Chubby中并沒(méi)有符號(hào)連接（Symbolic Link，又叫軟連接，類似于Windows系統(tǒng)中的快捷方式）和硬連接（Hard Link，類似于別名）的概念。成功獲得鎖的服務(wù)器自動(dòng)成為主服務(wù)器并將其地址寫(xiě)入這個(gè)文件夾，以便其他服務(wù)器和用戶可以獲知主服務(wù)器的地址信息。客戶端如果需要確定主服務(wù)器的位置，可以向DNS發(fā)送一個(gè)主服務(wù)器定位請(qǐng)求，非主服務(wù)器的副本將對(duì)該請(qǐng)求做出回應(yīng)，通過(guò)這種方式客戶端能夠快速、準(zhǔn)確地對(duì)主服務(wù)器做出定位。服務(wù)器一端稱為Chubby單元，一般是由五個(gè)稱為副本（Replica）的服務(wù)器組成的，這五個(gè)副本在配置上完全一致，并且在系統(tǒng)剛開(kāi)始時(shí)處于對(duì)等地位。當(dāng)然用戶也可以自行實(shí)現(xiàn)細(xì)粒度鎖，不過(guò)建議還是使用粗粒度 的鎖。在設(shè)計(jì)的過(guò)程中有一些細(xì)節(jié)問(wèn)題也值得我們關(guān)注，比如在Chubby系統(tǒng)中采用了建議性的鎖而沒(méi)有采用強(qiáng)制性的鎖。雖然在分布式系統(tǒng)中鎖的使用會(huì)有很大的不同，但是和一致性算法相比，鎖顯然被更多的開(kāi)發(fā)者所熟知。單獨(dú)的鎖服務(wù)可以保證原有系統(tǒng)的架構(gòu)不會(huì)發(fā)生改變，而使用函數(shù)庫(kù)的話很可能需要對(duì)系統(tǒng)的架構(gòu)做出大幅度的改動(dòng)。前面提到在分布式系統(tǒng)中保持?jǐn)?shù)據(jù)一致性最常用也最有效的算法是Paxos，很多系統(tǒng)就是將Paxos算法作為其一致性算法的核心。5）支持通報(bào)機(jī)制。3）支持粗粒度的建議性鎖服務(wù)。1）高可用性和高可靠性。以上只是簡(jiǎn)要地向大家介紹了Paxos算法的核心內(nèi)容，關(guān)于更多的實(shí)現(xiàn)細(xì)節(jié)讀者可以參考Lamport關(guān)于Paxos算法實(shí)現(xiàn)的文章。為了減少?zèng)Q議發(fā)布過(guò)程中的消息量，acceptors將這個(gè)通過(guò)的決議發(fā)送給learners 的一個(gè)子集，然后由這個(gè)子集中的learners 去通知所有其他的learners。在這些約束條件的基礎(chǔ)上，可以將一個(gè)決議的通過(guò)分成兩個(gè)階段。2）每次只批準(zhǔn)一個(gè)決議。在Lamport提出的Paxos算法中節(jié)點(diǎn)被分成了三種類型：proposers、acceptors和 learners。 Paxos算法Paxos算法[14][15]是由供職于微軟的Leslie Lamport最先提出的一種基于消息傳遞（Messages Passing）的一致性算法。除了最常用的鎖服務(wù)之外，Chubby還可以作為一個(gè)穩(wěn)定的存儲(chǔ)系統(tǒng)存儲(chǔ)包括元數(shù)據(jù)在類的小數(shù)據(jù)。圖28 Reduce過(guò)程 分布式鎖服務(wù)ChubbyChubby是Google設(shè)計(jì)的提供粗粒度鎖服務(wù)的一個(gè)文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問(wèn)題。這一步由系統(tǒng)自動(dòng)完成。 For each v in V count += v。 案例分析單詞計(jì)數(shù)（Word Count）是一個(gè)經(jīng)典的問(wèn)題，也是能體現(xiàn)MapReduce設(shè)計(jì)思想的最簡(jiǎn)單算法之一。一旦某個(gè)任務(wù)失效了，就可以從最近的一個(gè)檢查點(diǎn)恢復(fù)并重新執(zhí)行。此時(shí)MapReduce返回用戶程序的調(diào)用點(diǎn)。如果中間結(jié)果集過(guò)于龐大，那么就需要使用外排序。中間結(jié)果在本地硬盤(pán)的位置信息將被發(fā)送回Master，然后Master負(fù)責(zé)把這些位置信息傳送給Reduce Worker。圖23 MapReduce執(zhí)行流程圖3）一個(gè)分配了Map任務(wù)的Worker讀取并處理相關(guān)的輸入塊。1）用戶程序中的MapReduce函數(shù)庫(kù)首先把輸入文件分成M塊，每塊大概16M～64MB（可以通過(guò)參數(shù)決定），接著在集群的機(jī)器上執(zhí)行處理程序。例如，假設(shè)我們想用MapReduce來(lái)計(jì)算一個(gè)大型文本文件中各個(gè)單詞出現(xiàn)的次數(shù)，Map的輸入?yún)?shù)指明了需要處理哪部分?jǐn)?shù)據(jù)，以在文本中的起始位置，需要處理的數(shù)據(jù)長(zhǎng)度表示，經(jīng)過(guò)Map處理，形成一批中間結(jié)果單詞，出現(xiàn)次數(shù)。Map的輸出結(jié)果是一組key,value對(duì)，這是經(jīng)過(guò)Map操作后所產(chǎn)生的中間結(jié)果。在編程的時(shí)候，開(kāi)發(fā)者需要編寫(xiě)兩個(gè)主要函數(shù)：Map: (in_key, in_value) 224。圖中有M個(gè)Map操作和R個(gè)Reduce操作。據(jù)相關(guān)統(tǒng)計(jì)，每使用一次Google搜索引擎，Google的后臺(tái)服務(wù)器就要進(jìn)行1011次運(yùn)算。還可以通過(guò)由普通PC構(gòu)成的巨大集群來(lái)達(dá)到極高的性能。正是由于MapReduce有函數(shù)式和矢量編程語(yǔ)言的共性，使得這種編程模式特別適合于非結(jié)構(gòu)化和結(jié)構(gòu)化的海量數(shù)據(jù)的搜索、挖掘、分析與機(jī)器智能學(xué)習(xí)等。4．節(jié)能技術(shù)有關(guān)數(shù)據(jù)表明，服務(wù)器的耗電成本大于當(dāng)初的購(gòu)買(mǎi)成本，因此Google采用了多種機(jī)制來(lái)降低服務(wù)器的能耗，例如對(duì)服務(wù)器主板進(jìn)行修改，采用蓄電池代替昂貴的UPS（不間斷電源系統(tǒng)），提高能量的利用率。那么，迅速地安裝、部署一個(gè)GFS的系統(tǒng)，以及迅速地進(jìn)行節(jié)點(diǎn)的系統(tǒng)升級(jí)等，都需要相應(yīng)的技術(shù)支撐。當(dāng)讀取一個(gè)Chunk副本時(shí)，Chunk Server會(huì)將讀取的數(shù)據(jù)和校驗(yàn)和進(jìn)行比較，如果不匹配，就會(huì)返回錯(cuò)誤，從而使Client選擇其他Chunk Server上的副本。盡管一份數(shù)據(jù)需要存儲(chǔ)三份，好像磁盤(pán)空間的利用率不高，但綜合比較多種因素，加之磁盤(pán)的成本不斷下降，采用副本無(wú)疑是最簡(jiǎn)單、最可靠、最有效，而且實(shí)現(xiàn)的難度也最小的一種方法。每一個(gè)Chunk有多個(gè)存儲(chǔ)副本（默認(rèn)為三個(gè)），分布存儲(chǔ)在不同的Chunk Server上。第三種元數(shù)據(jù)信息則直接保存在各個(gè)Chunk Server上，當(dāng)Master啟動(dòng)或Chunk Server向Master注冊(cè)時(shí)自動(dòng)生成。1）命名空間（Name Space），也就是整個(gè)文件系統(tǒng)的目錄結(jié)構(gòu)。通常與POSIX兼容的接口需要在操作系統(tǒng)內(nèi)核一級(jí)實(shí)現(xiàn)，而GFS是在應(yīng)用層實(shí)現(xiàn)的。GFS在設(shè)計(jì)之初，是完全面向Google的應(yīng)用的，采用了專用的文件系統(tǒng)訪問(wèn)接口。在內(nèi)核態(tài)下，如果不能很好地掌握其特性，效率不但不會(huì)高，甚至還會(huì)影響到整個(gè)系統(tǒng)運(yùn)行的穩(wěn)定性。1）在用戶態(tài)下實(shí)現(xiàn)，直接利用操作系統(tǒng)提供的POSIX編程接口就可以存取數(shù)據(jù)，無(wú)需了解操作系統(tǒng)的內(nèi)部實(shí)現(xiàn)機(jī)制和接口，從而降低了實(shí)現(xiàn)的難度，并提高了通用性。3．在用戶態(tài)下實(shí)現(xiàn)文件系統(tǒng)作為操作系統(tǒng)的重要組成部分，其實(shí)現(xiàn)通常位于操作系統(tǒng)底層。從可行性上講，如何維護(hù)緩存與實(shí)際數(shù)據(jù)之間的一致性是一個(gè)極其復(fù)雜的問(wèn)題，在GFS中各個(gè)Chunk Server的穩(wěn)定性都無(wú)法確保，加之網(wǎng)絡(luò)等多種不確定因素，一致性問(wèn)題尤為復(fù)雜。GFS采用多種機(jī)制來(lái)避免Master成為系統(tǒng)性能和可靠性上的瓶頸，如盡量控制元數(shù)據(jù)的規(guī)模、對(duì)Master進(jìn)行遠(yuǎn)程備份、控制信息和數(shù)據(jù)分流等。如果采用完全對(duì)等的、無(wú)中心的模式，那么如何將Chunk Server的更新信息通知到每一個(gè)Chunk Server，會(huì)是設(shè)計(jì)的一個(gè)難點(diǎn)，而這也將在一定程度上影響系統(tǒng)的擴(kuò)展性。Master管理了分布式文件系統(tǒng)中的所有元數(shù)據(jù)。Client與Chunk Server之間直接傳輸數(shù)據(jù)流，同時(shí)由于文件被分成多個(gè)Chunk進(jìn)行分布式存儲(chǔ)，Client可以同時(shí)訪問(wèn)多個(gè)Chunk Server，從而使得整個(gè)系統(tǒng)I/O高度并行，系統(tǒng)整體性能得到提高。GFS將文件按照固定大小進(jìn)行分塊，默認(rèn)是64MB，每一塊稱為一個(gè)Chunk（數(shù)據(jù)塊），每個(gè)Chunk都有一個(gè)對(duì)應(yīng)的索引號(hào)（Index）。應(yīng)用程序直接調(diào)用這些庫(kù)函數(shù)，并與該庫(kù)鏈接在一起。GFS的精彩在于它采用了多種方法，從多個(gè)角度，使用不同的容錯(cuò)措施來(lái)確保整個(gè)系統(tǒng)的可靠性。創(chuàng)新的價(jià)值，取決于一項(xiàng)創(chuàng)新在新穎、有用和可行性這三個(gè)方面的綜合表現(xiàn)。這些系統(tǒng)通常用于高性能計(jì)算或大型數(shù)據(jù)中心，對(duì)硬件設(shè)施條件要求較高。它為Google云計(jì)算提供海量存儲(chǔ)，并且與Chubby、MapReduce以及Bigtable等技術(shù)結(jié)合十分緊密，處于所有核心技術(shù)的底層。Google云計(jì)算技術(shù)具體包括：Google文件系統(tǒng)GFS、分布式計(jì)算編程模型MapReduce、分布式鎖服務(wù)Chubby和分布式結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)系統(tǒng)Bigtable等。. . . . . Google云計(jì)算原理Google擁有全球最強(qiáng)大的搜索引擎。Google的訣竅在于它發(fā)展出簡(jiǎn)單而又高效的技術(shù)，讓多達(dá)百萬(wàn)臺(tái)的廉價(jià)計(jì)算機(jī)協(xié)同工作，共同完成這些前所未有的任務(wù)，這些技術(shù)是在誕生幾年之后才被命名為Google云計(jì)算技術(shù)。 Google文件系統(tǒng)GFSGoogle文件系統(tǒng)（Google File System，GFS）是一個(gè)大型的分布式文件系統(tǒng)。當(dāng)前主流分布式文件系統(tǒng)有RedHat的GFS[3]（Global File System）、IBM的GPFS[4]、Sun的Lustre[5]等。正如李開(kāi)復(fù)所說(shuō)的那樣，創(chuàng)新固然重要，但有用的創(chuàng)新更重要。由于GFS中服務(wù)器數(shù)目眾多，在GFS中服務(wù)器死機(jī)是經(jīng)常發(fā)生事情，甚至都不應(yīng)當(dāng)將其視為異?，F(xiàn)象，那么如何在頻繁的故障中確保數(shù)據(jù)存儲(chǔ)的安全、保證提供不間斷的數(shù)據(jù)存儲(chǔ)服務(wù)是GFS最核心的問(wèn)題。Client是GFS提供給應(yīng)用程序的訪問(wèn)接口，它是一組專用接口，不遵守POSIX規(guī)范，以庫(kù)文件的形式提供。數(shù)據(jù)以文件的形式存儲(chǔ)在Chunk Server上，Chunk Server的個(gè)數(shù)可以有多個(gè)，它的數(shù)目直接決定了GFS的規(guī)模。Client與Master之間只有控制流，而無(wú)數(shù)據(jù)流，這樣就極大地降低了Master的負(fù)載，使之不成為系統(tǒng)性能的一個(gè)瓶頸。1．采用中心服務(wù)器模式GFS采用中心服務(wù)器模式來(lái)管理整個(gè)文件系統(tǒng)，可以大大簡(jiǎn)化設(shè)計(jì)，從而降低實(shí)現(xiàn)難度。這樣做有許多好處，增加新的Chunk Server是一件十分容易的事情，Chunk Server只需要注冊(cè)到Master上即可，Chunk Server之間無(wú)任何關(guān)系。當(dāng)然，中心服務(wù)器模式也帶來(lái)一些固有的缺點(diǎn)，比如極易成為整個(gè)系統(tǒng)的瓶頸等。從必要性上講，客戶端大部分是流式順序讀寫(xiě)，并不存在大量的重復(fù)讀寫(xiě)，緩存這部分?jǐn)?shù)據(jù)對(duì)系統(tǒng)整體性能的提高作用不大；而對(duì)于Chunk Server，由于GFS的數(shù)據(jù)在Chunk Server上以文件的形式存儲(chǔ)，如果對(duì)某塊數(shù)據(jù)讀取頻繁，本地的文件系統(tǒng)自然會(huì)將其緩存。Master需要對(duì)其元數(shù)據(jù)進(jìn)行頻繁操作，為了提高操作的效率，Master的元數(shù)據(jù)都是直接保存在內(nèi)存中進(jìn)行操作；同時(shí)采用相應(yīng)的壓縮機(jī)制降低元數(shù)據(jù)占用空間的大小，提高內(nèi)存的利用率。然而，GFS卻選擇在用戶態(tài)下實(shí)現(xiàn)，主要基于以下考慮。4）用戶態(tài)下，Master和Chunk Server都以進(jìn)程的方式運(yùn)行，單個(gè)進(jìn)程不會(huì)影響到整個(gè)操作系統(tǒng)，從而可以對(duì)其進(jìn)行充分優(yōu)化。其優(yōu)點(diǎn)是應(yīng)用程序可以通過(guò)操作系統(tǒng)的統(tǒng)一接口來(lái)透明地訪問(wèn)文件系統(tǒng)，而不需要重新編譯程序。1）降低了實(shí)現(xiàn)的難度。 容錯(cuò)機(jī)制1．Master容錯(cuò)具體來(lái)說(shuō)，Maste