【正文】 務(wù)器出錯(cuò)在客戶端和主服務(wù)器端進(jìn)行通信時(shí)可能會(huì)遇到主服務(wù)器故障，圖210就出現(xiàn)了這種情況。如果客戶端接收到這個(gè)回應(yīng)的時(shí)間仍處于寬限期內(nèi)，則系統(tǒng)會(huì)恢復(fù)到安全狀態(tài)，租約期更新為C3。客戶端在主服務(wù)器拒絕之后會(huì)使用新的紀(jì)元號(hào)來(lái)發(fā)送KeepAlive請(qǐng)求（圖210中的6）。圖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ò)誤。這個(gè)寬限期默認(rèn)是45秒。同樣的，主服務(wù)器可能不是立刻回應(yīng)而是等待C2接近結(jié)束，但是在這個(gè)過(guò)程中主服務(wù)器出現(xiàn)故障停止使用。1．客戶端租約過(guò)期剛開(kāi)始時(shí)，客戶端向主服務(wù)器發(fā)出一個(gè)KeepAlive請(qǐng)求（圖210中的1），如果有需要通知的事件時(shí)則主服務(wù)器會(huì)立刻做出回應(yīng)，否則主服務(wù)器并不立刻對(duì)這個(gè)請(qǐng)求做出回應(yīng)，而是等到客戶端的租約期C1快結(jié)束的時(shí)候才做出回應(yīng)（圖210中的2），并更新主服務(wù)器租約期為M2。但是由于系統(tǒng)有一定的失效概率，引入故障處理措施是很有必要的。主要的事件包括文件內(nèi)容被修改、子節(jié)點(diǎn)的增加、刪除和修改、主服務(wù)器出錯(cuò)、句柄失效等。CCC3則是客戶端對(duì)主服務(wù)器租約期時(shí)長(zhǎng)做出的一個(gè)估計(jì)。圖210 Chubby客戶端與服務(wù)器端的通信過(guò)程圖210中從左到右時(shí)間在增加，斜向上的箭頭表示一次KeepAlive請(qǐng)求，斜向下的箭頭則是主服務(wù)器的一次回應(yīng)。這個(gè)指針支持一系列的操作，常用的句柄操作函數(shù)如表21所示。這樣一來(lái)Chubby系統(tǒng)中只有涉及鎖的操作才需要序號(hào)，其他一概不用。在實(shí)際的執(zhí)行中，為了避免所有的通信都使用序號(hào)帶來(lái)的系統(tǒng)開(kāi)銷(xiāo)增長(zhǎng)，Chubby引入了sequencer的概念。2）序號(hào)（Sequence Number）：用來(lái)確定句柄是由當(dāng)前還是以前的主服務(wù)器創(chuàng)建的。用戶在打開(kāi)某個(gè)節(jié)點(diǎn)時(shí)就會(huì)獲取一個(gè)類似于UNIX中文件描述符（File Descriptor）的句柄[13]（Handles），這個(gè)句柄由以下三個(gè)部分組成。3）鎖生成號(hào)（Lock Generation Number）：鎖被用戶持有時(shí)該號(hào)增加。1）實(shí)例號(hào)（Instance Number）：新節(jié)點(diǎn)實(shí)例號(hào)必定大于舊節(jié)點(diǎn)的實(shí)例號(hào)。節(jié)點(diǎn)中保存著包括ACL（Access Control List，訪問(wèn)控制列表，）在內(nèi)的多種系統(tǒng)元數(shù)據(jù)。例如Chubby不支持內(nèi)部文件的移動(dòng)；不記錄文件的最后訪問(wèn)時(shí)間；另外在Chubby中并沒(méi)有符號(hào)連接（Symbolic Link，又叫軟連接，類似于Windows系統(tǒng)中的快捷方式）和硬連接（Hard Link，類似于別名）的概念。例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統(tǒng)的共有前綴；foo是某個(gè)單元的名稱；/wombat/pouch則是foo這個(gè)單元上的文件目錄或者文件名。成功獲得鎖的服務(wù)器自動(dòng)成為主服務(wù)器并將其地址寫(xiě)入這個(gè)文件夾，以便其他服務(wù)器和用戶可以獲知主服務(wù)器的地址信息。例如在Chubby最常用的鎖服務(wù)中，每一個(gè)文件就代表了一個(gè)鎖，用戶通過(guò)打開(kāi)、關(guān)閉和讀取文件，獲取共享（Shared）鎖或獨(dú)占（Exclusive）鎖?？蛻舳巳绻枰_定主服務(wù)器的位置，可以向DNS發(fā)送一個(gè)主服務(wù)器定位請(qǐng)求，非主服務(wù)器的副本將對(duì)該請(qǐng)求做出回應(yīng)，通過(guò)這種方式客戶端能夠快速、準(zhǔn)確地對(duì)主服務(wù)器做出定位。如果某個(gè)服務(wù)器被連續(xù)推舉為主服務(wù)器的話，這個(gè)租約期就會(huì)不斷地被更新。服務(wù)器一端稱為Chubby單元，一般是由五個(gè)稱為副本（Replica）的服務(wù)器組成的，這五個(gè)副本在配置上完全一致，并且在系統(tǒng)剛開(kāi)始時(shí)處于對(duì)等地位。很明顯，Chubby被劃分成兩個(gè)部分：客戶端和服務(wù)器端，客戶端和服務(wù)器端之間通過(guò)遠(yuǎn)程過(guò)程調(diào)用（RPC）來(lái)連接。當(dāng)然用戶也可以自行實(shí)現(xiàn)細(xì)粒度鎖，不過(guò)建議還是使用粗粒度 的鎖。另外Chubby還采用了粗粒度（CoarseGrained）鎖服務(wù)而沒(méi)有采用細(xì)粒度（FineGrained）鎖服務(wù)，兩者的差異在于持有鎖的時(shí)間。在設(shè)計(jì)的過(guò)程中有一些細(xì)節(jié)問(wèn)題也值得我們關(guān)注，比如在Chubby系統(tǒng)中采用了建議性的鎖而沒(méi)有采用強(qiáng)制性的鎖。也就是說(shuō)，Chubby在自身服務(wù)的實(shí)現(xiàn)時(shí)利用若干臺(tái)機(jī)器實(shí)現(xiàn)了高可用性，而外部用戶利用Chubby則只需一臺(tái)機(jī)器就可以保證高可用性。雖然在分布式系統(tǒng)中鎖的使用會(huì)有很大的不同，但是和一致性算法相比，鎖顯然被更多的開(kāi)發(fā)者所熟知。這樣其他需要了解這些變動(dòng)的用戶和服務(wù)器直接訪問(wèn)這些文件即可，避免了因大量的系統(tǒng)組件之間的事件通信帶來(lái)的系統(tǒng)性能下降。單獨(dú)的鎖服務(wù)可以保證原有系統(tǒng)的架構(gòu)不會(huì)發(fā)生改變，而使用函數(shù)庫(kù)的話很可能需要對(duì)系統(tǒng)的架構(gòu)做出大幅度的改動(dòng)。Google做出這種設(shè)計(jì)主要是考慮到以下幾個(gè)問(wèn)題[13]。前面提到在分布式系統(tǒng)中保持?jǐn)?shù)據(jù)一致性最常用也最有效的算法是Paxos，很多系統(tǒng)就是將Paxos算法作為其一致性算法的核心。6）支持緩存機(jī)制。5）支持通報(bào)機(jī)制。4）服務(wù)信息的直接存儲(chǔ)。3）支持粗粒度的建議性鎖服務(wù)。2）高擴(kuò)展性。1）高可用性和高可靠性。這種苛刻的服務(wù)要求使得Chubby在設(shè)計(jì)之初就要充分考慮到系統(tǒng)需要實(shí)現(xiàn)的目標(biāo)以及可能出現(xiàn)的各種問(wèn)題。以上只是簡(jiǎn)要地向大家介紹了Paxos算法的核心內(nèi)容，關(guān)于更多的實(shí)現(xiàn)細(xì)節(jié)讀者可以參考Lamport關(guān)于Paxos算法實(shí)現(xiàn)的文章。根據(jù)算法一個(gè)編號(hào)更大的提案會(huì)終止之前的提案過(guò)程，如果兩個(gè)proposer在這種情況下都轉(zhuǎn)而提出一個(gè)編號(hào)更大的提案，那么就可能陷入活鎖。為了減少?zèng)Q議發(fā)布過(guò)程中的消息量，acceptors將這個(gè)通過(guò)的決議發(fā)送給learners 的一個(gè)子集，然后由這個(gè)子集中的learners 去通知所有其他的learners。Acceptors 收到后，如果提案的編號(hào)大于它已經(jīng)回復(fù)的所有消息，則acceptors將自己上次的批準(zhǔn)回復(fù)給proposers，并不再批準(zhǔn)小于n的提案。在這些約束條件的基礎(chǔ)上，可以將一個(gè)決議的通過(guò)分成兩個(gè)階段。Lamport通過(guò)約束條件的不斷加強(qiáng)，最后得到了一個(gè)可以實(shí)際運(yùn)用到算法中的完整約束條件：如果一個(gè)編號(hào)為n的提案具有值v，那么存在一個(gè)多數(shù)派，要么他們中沒(méi)有人批準(zhǔn)過(guò)編號(hào)小于n的任何提案，要么他們進(jìn)行的最近一次批準(zhǔn)具有值 v。2）每次只批準(zhǔn)一個(gè)決議。一個(gè)節(jié)點(diǎn)可以兼有多重類型。在Lamport提出的Paxos算法中節(jié)點(diǎn)被分成了三種類型：proposers、acceptors和 learners。要想了解Paxos算法，我們首先需要知道什么是分布式系統(tǒng)中的一致性問(wèn)題，因?yàn)镻axos算法就是為了解決這個(gè)問(wèn)題而提出的。 Paxos算法Paxos算法[14][15]是由供職于微軟的Leslie Lamport最先提出的一種基于消息傳遞（Messages Passing）的一致性算法。本節(jié)首先簡(jiǎn)要介紹Paxos算法，因?yàn)镃hubby內(nèi)部一致性問(wèn)題的實(shí)現(xiàn)用到了Paxos算法；然后圍繞Chubby系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)展開(kāi)講解。除了最常用的鎖服務(wù)之外，Chubby還可以作為一個(gè)穩(wěn)定的存儲(chǔ)系統(tǒng)存儲(chǔ)包括元數(shù)據(jù)在類的小數(shù)據(jù)。不過(guò)值得注意的是，這種鎖只是一種建議性的鎖（Advisory Lock）而不是強(qiáng)制性的鎖（Mandatory Lock），如此選擇的目的是使系統(tǒng)具有更大的靈活性。圖28 Reduce過(guò)程 分布式鎖服務(wù)ChubbyChubby是Google設(shè)計(jì)的提供粗粒度鎖服務(wù)的一個(gè)文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問(wèn)題。圖26 Map過(guò)程3）Map輸出之后有一個(gè)內(nèi)部的Fold過(guò)程，和第一步一樣，都是由系統(tǒng)自動(dòng)完成的，如圖27所示。這一步由系統(tǒng)自動(dòng)完成。}下面就根據(jù)MapReduce的四個(gè)執(zhí)行步驟對(duì)這一算法進(jìn)行詳細(xì)的介紹。 For each v in V count += v。圖24 單詞計(jì)數(shù)偽代碼如下：Map(K,V){For each word w in V Collect(w , 1)。 案例分析單詞計(jì)數(shù)（Word Count）是一個(gè)經(jīng)典的問(wèn)題，也是能體現(xiàn)MapReduce設(shè)計(jì)思想的最簡(jiǎn)單算法之一。2．Worker失效相對(duì)于Master失效而言，Worker失效算是一種常見(jiàn)的狀態(tài)。一旦某個(gè)任務(wù)失效了，就可以從最近的一個(gè)檢查點(diǎn)恢復(fù)并重新執(zhí)行?？偟恼f(shuō)來(lái)，MapReduce是通過(guò)重新執(zhí)行失效的地方來(lái)實(shí)現(xiàn)容錯(cuò)的。此時(shí)MapReduce返回用戶程序的調(diào)用點(diǎn)。Reduce函數(shù)的結(jié)果輸出到一個(gè)最終的輸出文件。如果中間結(jié)果集過(guò)于龐大，那么就需要使用外排序。當(dāng)Reduce Worker讀到所有的中間數(shù)據(jù)，它就使用中間key進(jìn)行排序，這樣可以使得相同key的值都在一起。中間結(jié)果在本地硬盤(pán)的位置信息將被發(fā)送回Master，然后Master負(fù)責(zé)把這些位置信息傳送給Reduce Worker。Map函數(shù)產(chǎn)生的中間結(jié)果key,value對(duì)暫時(shí)緩沖到內(nèi)存。圖23 MapReduce執(zhí)行流程圖3）一個(gè)分配了Map任務(wù)的Worker讀取并處理相關(guān)的輸入塊。剩下的執(zhí)行程序都是作為Master分派工作的Worker（工作機(jī)）。1）用戶程序中的MapReduce函數(shù)庫(kù)首先把輸入文件分成M塊，每塊大概16M～64MB（可以通過(guò)參數(shù)決定），接著在集群的機(jī)器上執(zhí)行處理程序。 實(shí)現(xiàn)機(jī)制實(shí)現(xiàn)MapReduce操作的執(zhí)行流程圖[7]如圖23所示。例如，假設(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ù)。Reduce的工作是需要對(duì)這些對(duì)應(yīng)相同key的value值進(jìn)行歸并處理，最終形成（key, final_value）的結(jié)果。Map的輸出結(jié)果是一組key,value對(duì)，這是經(jīng)過(guò)Map操作后所產(chǎn)生的中間結(jié)果。 (key, final_value) Map和Reduce的輸入?yún)?shù)和輸出結(jié)果根據(jù)應(yīng)用的不同而有所不同。在編程的時(shí)候，開(kāi)發(fā)者需要編寫(xiě)兩個(gè)主要函數(shù)：Map: (in_key, in_value) 224。每個(gè)Map操作都針對(duì)不同的原始數(shù)據(jù)，因此Map與Map之間是互相獨(dú)立的，這就使得它們可以充分并行化。圖中有M個(gè)Map操作和R個(gè)Reduce操作。而使用MapReduce這種編程模式，就保持了服務(wù)器之間的均衡，提高了整體效率。據(jù)相關(guān)統(tǒng)計(jì)，每使用一次Google搜索引擎，Google的后臺(tái)服務(wù)器就要進(jìn)行1011次運(yùn)算。MapReduce把對(duì)數(shù)據(jù)集的大規(guī)模操作，分發(fā)給一個(gè)主節(jié)點(diǎn)管理下的各分節(jié)點(diǎn)共同完成，通過(guò)這種方式實(shí)現(xiàn)任務(wù)的可靠執(zhí)行與容錯(cuò)機(jī)制。還可以通過(guò)由普通PC構(gòu)成的巨大集群來(lái)達(dá)到極高的性能。與傳統(tǒng)的分布式程序設(shè)計(jì)相比，MapReduce封裝了并行處理、容錯(cuò)處理、本地化計(jì)算、負(fù)載均衡等細(xì)節(jié)，還提供了一個(gè)簡(jiǎn)單而強(qiáng)大的接口。正是由于MapReduce有函數(shù)式和矢量編程語(yǔ)言的共性，使得這種編程模式特別適合于非結(jié)構(gòu)化和結(jié)構(gòu)化的海量數(shù)據(jù)的搜索、挖掘、分析與機(jī)器智能學(xué)習(xí)等。 并行數(shù)據(jù)處理MapReduceMapReduce是Google提出的一個(gè)軟件架構(gòu)，是一種處理海量數(shù)據(jù)的并行編程模式，用于大規(guī)模數(shù)據(jù)集（通常大于1TB）的并行運(yùn)算。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)），提高能量的利用率。3．節(jié)點(diǎn)動(dòng)態(tài)加入技術(shù)當(dāng)有新的Chunk Server加入時(shí)，如果需要事先安裝好系統(tǒng)，那么系統(tǒng)擴(kuò)展將是一件十分煩瑣的事情。那么，迅速地安裝、部署一個(gè)GFS的系統(tǒng)，以及迅速地進(jìn)行節(jié)點(diǎn)的系統(tǒng)升級(jí)等，都需要相應(yīng)的技術(shù)支撐。除了上面提到的GFS的一些關(guān)鍵技術(shù)外，還有相應(yīng)的系統(tǒng)管理技術(shù)來(lái)支持整個(gè)GFS的應(yīng)用，這些技術(shù)可能并不一定為GFS所獨(dú)有。當(dāng)讀取一個(gè)Chunk副本時(shí)，Chunk Server會(huì)將讀取的數(shù)據(jù)和校驗(yàn)和進(jìn)行比較，如果不匹配，就會(huì)返回錯(cuò)誤，從而使Client選擇其他Chunk Server上的副本。Chunk Server存儲(chǔ)的是Chunk的副本，副本以文件的形式進(jìn)行存儲(chǔ)。盡管一份數(shù)據(jù)需要存儲(chǔ)三份，好像磁盤(pán)空間的利用率不高，但綜合比較多種因素，加之磁盤(pán)的成本不斷下降，采用副