【文章內(nèi)容簡介】 ：proposers選擇一個提案并將它的編號設(shè)為n，然后將它發(fā)送給acceptors中的一個多數(shù)派。Acceptors 收到后，如果提案的編號大于它已經(jīng)回復(fù)的所有消息，則acceptors將自己上次的批準(zhǔn)回復(fù)給proposers，并不再批準(zhǔn)小于n的提案。2）批準(zhǔn)階段：當(dāng)proposers接收到acceptors 中的這個多數(shù)派的回復(fù)后，就向回復(fù)請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準(zhǔn)這個請求。為了減少決議發(fā)布過程中的消息量，acceptors將這個通過的決議發(fā)送給learners 的一個子集，然后由這個子集中的learners 去通知所有其他的learners。一般情況下，以上的算法過程就可以成功地解決一致性問題，但是也有特殊情況。根據(jù)算法一個編號更大的提案會終止之前的提案過程，如果兩個proposer在這種情況下都轉(zhuǎn)而提出一個編號更大的提案，那么就可能陷入活鎖。此時需要選舉出一個president，僅允許 president提出提案。以上只是簡要地向大家介紹了Paxos算法的核心內(nèi)容，關(guān)于更多的實現(xiàn)細(xì)節(jié)讀者可以參考Lamport關(guān)于Paxos算法實現(xiàn)的文章。 Chubby系統(tǒng)設(shè)計通常情況下Google的一個數(shù)據(jù)中心僅運行一個Chubby單元[13]（Chubby cell,下面會有詳細(xì)講解），而這個單元需要支持包括GFS、Bigtable在內(nèi)的眾多Google服務(wù)。這種苛刻的服務(wù)要求使得Chubby在設(shè)計之初就要充分考慮到系統(tǒng)需要實現(xiàn)的目標(biāo)以及可能出現(xiàn)的各種問題。Chubby的設(shè)計目標(biāo)主要有以下幾點。1）高可用性和高可靠性。這是系統(tǒng)設(shè)計的首要目標(biāo)，在保證這一目標(biāo)的基礎(chǔ)上再考慮系統(tǒng)的吞吐量和存儲能力。2）高擴展性。將數(shù)據(jù)存儲在價格較為低廉的RAM，支持大規(guī)模用戶訪問文件。3）支持粗粒度的建議性鎖服務(wù)。提供這種服務(wù)的根本目的是提高系統(tǒng)的性能。4）服務(wù)信息的直接存儲。可以直接存儲包括元數(shù)據(jù)、系統(tǒng)參數(shù)在內(nèi)的有關(guān)服務(wù)信息，而不需要再維護另一個服務(wù)。5）支持通報機制。客戶可以及時地了解到事件的發(fā)生。6）支持緩存機制。通過一致性緩存將常用信息保存在客戶端，避免了頻繁地訪問主服務(wù)器。前面提到在分布式系統(tǒng)中保持?jǐn)?shù)據(jù)一致性最常用也最有效的算法是Paxos，很多系統(tǒng)就是將Paxos算法作為其一致性算法的核心。但是Google并沒有直接實現(xiàn)一個包含了Paxos算法的函數(shù)庫，相反，Google設(shè)計了一個全新的鎖服務(wù)Chubby。Google做出這種設(shè)計主要是考慮到以下幾個問題[13]。1）通常情況下開發(fā)者在開發(fā)的初期很少考慮系統(tǒng)的一致性問題，但是隨著開發(fā)的不斷進行，這種問題會變得越來越嚴(yán)重。單獨的鎖服務(wù)可以保證原有系統(tǒng)的架構(gòu)不會發(fā)生改變，而使用函數(shù)庫的話很可能需要對系統(tǒng)的架構(gòu)做出大幅度的改動。2）系統(tǒng)中很多事件的發(fā)生是需要告知其他用戶和服務(wù)器的，使用一個基于文件系統(tǒng)的鎖服務(wù)可以將這些變動寫入文件中。這樣其他需要了解這些變動的用戶和服務(wù)器直接訪問這些文件即可，避免了因大量的系統(tǒng)組件之間的事件通信帶來的系統(tǒng)性能下降。3）基于鎖的開發(fā)接口容易被開發(fā)者接受。雖然在分布式系統(tǒng)中鎖的使用會有很大的不同，但是和一致性算法相比，鎖顯然被更多的開發(fā)者所熟知。一般來說分布式一致性問題通過quorum機制（簡單來說就是根據(jù)少數(shù)服從多數(shù)的選舉原則產(chǎn)生一個決議）做出決策，為了保證系統(tǒng)的高可用性，需要若干臺機器，但是使用單獨的鎖服務(wù)的話一臺機器也能保證這種高可用性。也就是說，Chubby在自身服務(wù)的實現(xiàn)時利用若干臺機器實現(xiàn)了高可用性，而外部用戶利用Chubby則只需一臺機器就可以保證高可用性。正是考慮到以上幾個問題，Google設(shè)計了Chubby，而不是單獨地維護一個函數(shù)庫（實際上，Google有這樣一個獨立于Chubby的函數(shù)庫，不過一般情況下并不會使用）。在設(shè)計的過程中有一些細(xì)節(jié)問題也值得我們關(guān)注，比如在Chubby系統(tǒng)中采用了建議性的鎖而沒有采用強制性的鎖。兩者的根本區(qū)別在于用戶訪問某個被鎖定的文件時，建議性的鎖不會阻止這種行為，而強制性的鎖則會，實際上這是為了便于系統(tǒng)組件之間的信息交互行為。另外Chubby還采用了粗粒度（CoarseGrained）鎖服務(wù)而沒有采用細(xì)粒度（FineGrained）鎖服務(wù)，兩者的差異在于持有鎖的時間。細(xì)粒度的鎖持有時間很短，常常只有幾秒甚至更少，而粗粒度的鎖持有的時間可長達幾天，做出如此選擇的目的是減少頻繁換鎖帶來的系統(tǒng)開銷。當(dāng)然用戶也可以自行實現(xiàn)細(xì)粒度鎖，不過建議還是使用粗粒度 的鎖。圖29[13]就是Chubby的基本架構(gòu)。很明顯，Chubby被劃分成兩個部分：客戶端和服務(wù)器端，客戶端和服務(wù)器端之間通過遠程過程調(diào)用（RPC）來連接。在客戶這一端每個客戶應(yīng)用程序都有一個Chubby程序庫（Chubby Library），客戶端的所有應(yīng)用都是通過調(diào)用這個庫中的相關(guān)函數(shù)來完成的。服務(wù)器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務(wù)器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位。這些副本通過quorum機制選舉產(chǎn)生一個主服務(wù)器（Master），并保證在一定的時間內(nèi)有且僅有一個主服務(wù)器，這個時間就稱為主服務(wù)器租約期（Master Lease）。如果某個服務(wù)器被連續(xù)推舉為主服務(wù)器的話，這個租約期就會不斷地被更新。租續(xù)期內(nèi)所有的客戶請求都是由主服務(wù)器來處理的。客戶端如果需要確定主服務(wù)器的位置，可以向DNS發(fā)送一個主服務(wù)器定位請求，非主服務(wù)器的副本將對該請求做出回應(yīng)，通過這種方式客戶端能夠快速、準(zhǔn)確地對主服務(wù)器做出定位。圖29 Chubby的基本架構(gòu) Chubby文件系統(tǒng)Chubby系統(tǒng)本質(zhì)上就是一個分布式的、存儲大量小文件的文件系統(tǒng)，它所有的操作都是在文件的基礎(chǔ)上完成的。例如在Chubby最常用的鎖服務(wù)中，每一個文件就代表了一個鎖，用戶通過打開、關(guān)閉和讀取文件，獲取共享（Shared）鎖或獨占（Exclusive）鎖。選舉主服務(wù)器的過程中，符合條件的服務(wù)器都同時申請打開某個文件并請求鎖住該文件。成功獲得鎖的服務(wù)器自動成為主服務(wù)器并將其地址寫入這個文件夾，以便其他服務(wù)器和用戶可以獲知主服務(wù)器的地址信息。Chubby的文件系統(tǒng)[13]和UNIX類似。例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統(tǒng)的共有前綴；foo是某個單元的名稱；/wombat/pouch則是foo這個單元上的文件目錄或者文件名。由于Chubby自身的特殊服務(wù)要求，Google對Chubby做了一些與UNIX不同的改變。例如Chubby不支持內(nèi)部文件的移動；不記錄文件的最后訪問時間；另外在Chubby中并沒有符號連接（Symbolic Link，又叫軟連接，類似于Windows系統(tǒng)中的快捷方式）和硬連接（Hard Link，類似于別名）的概念。在具體實現(xiàn)時，文件系統(tǒng)由許多節(jié)點組成，分為永久型和臨時型，每個節(jié)點就是一個文件或目錄。節(jié)點中保存著包括ACL（Access Control List，訪問控制列表，）在內(nèi)的多種系統(tǒng)元數(shù)據(jù)。為了用戶能夠及時了解元數(shù)據(jù)的變動，系統(tǒng)規(guī)定每個節(jié)點的元數(shù)據(jù)都應(yīng)當(dāng)包含以下四種單調(diào)遞增的64位編號[13]。1）實例號（Instance Number）：新節(jié)點實例號必定大于舊節(jié)點的實例號。2）內(nèi)容生成號（Content Generation Number）：文件內(nèi)容修改時該號增加。3）鎖生成號（Lock Generation Number）：鎖被用戶持有時該號增加。4）ACL生成號（ACL Generation Number）：ACL名被覆寫時該號增加。用戶在打開某個節(jié)點時就會獲取一個類似于UNIX中文件描述符（File Descriptor）的句柄[13]（Handles），這個句柄由以下三個部分組成。1）校驗數(shù)位（Check Digit）：防止其他用戶創(chuàng)建或猜測這個句柄。2）序號（Sequence Number）：用來確定句柄是由當(dāng)前還是以前的主服務(wù)器創(chuàng)建的。3）模式信息（Mode Information）：用于新的主服務(wù)器重新創(chuàng)建一個舊的句柄。在實際的執(zhí)行中，為了避免所有的通信都使用序號帶來的系統(tǒng)開銷增長，Chubby引入了sequencer的概念。sequencer實際上就是一個序號，只不過這個序號只能由鎖的持有者在獲取鎖時向系統(tǒng)發(fā)出請求來獲得。這樣一來Chubby系統(tǒng)中只有涉及鎖的操作才需要序號，其他一概不用。在文件操作中，用戶可以將句柄看做一個指向文件系統(tǒng)的指針。這個指針支持一系列的操作，常用的句柄操作函數(shù)如表21所示。表21 常用句柄函數(shù)及其作用函數(shù)名稱作 用Open()打開某個文件或者目錄來創(chuàng)建句柄Close()關(guān)閉打開的句柄，后續(xù)的任何操作都將中止Poison()中止當(dāng)前未完成及后續(xù)的操作，但不關(guān)閉句柄GetContentsAndStat()返回文件內(nèi)容及元數(shù)據(jù)GetStat()只返回文件元數(shù)據(jù)ReadDir()返回子目錄名稱及其元數(shù)據(jù)SetContents()向文件中寫入內(nèi)容SetACL()設(shè)置ACL名稱Delete()如果該節(jié)點沒有子節(jié)點的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進行關(guān)聯(lián)CheckSequencer()檢查某個sequencer是否有效 通信協(xié)議客戶端和主服務(wù)器之間的通信是通過KeepAlive握手協(xié)議來維持的，圖210[13]就是這一通信過程的簡單示意圖。圖210 Chubby客戶端與服務(wù)器端的通信過程圖210中從左到右時間在增加，斜向上的箭頭表示一次KeepAlive請求，斜向下的箭頭則是主服務(wù)器的一次回應(yīng)。MMM3表示不同的主服務(wù)器租約期。CCC3則是客戶端對主服務(wù)器租約期時長做出的一個估計。KeepAlive是周期發(fā)送的一種信息，它主要有兩方面的功能：延遲租約的有效期和攜帶事件信息告訴用戶更新。主要的事件包括文件內(nèi)容被修改、子節(jié)點的增加、刪除和修改、主服務(wù)器出錯、句柄失效等。正常情況下，通過KeepAlive握手協(xié)議租約期會得到延長，事件也會及時地通知給用戶。但是由于系統(tǒng)有一定的失效概率，引入故障處理措施是很有必要的。通常情況下系統(tǒng)可能會出現(xiàn)兩種故障：客戶端租約期過期和主服務(wù)器故障，對于這兩種情況系統(tǒng)有著不同的應(yīng)對方式。1．客戶端租約過期剛開始時，客戶端向主服務(wù)器發(fā)出一個KeepAlive請求（圖210中的1），如果有需要通知的事件時則主服務(wù)器會立刻做出回應(yīng)，否則主服務(wù)器并不立刻對這個請求做出回應(yīng)，而是等到客戶端的租約期C1快結(jié)束的時候才做出回應(yīng)（圖210中的2），并更新主服務(wù)器租約期為M2?？蛻舳嗽诮拥竭@個回應(yīng)后認(rèn)為該主服務(wù)器仍處于活躍狀態(tài)，于是將租約期更新為C2并立刻發(fā)出新的KeepAlive請求（圖210中的3）。同樣的，主服務(wù)器可能不是立刻回應(yīng)而是等待C2接近結(jié)束，但是在這個過程中主服務(wù)器出現(xiàn)故障停止使用。在等待了一段時間后C2到期，由于并沒有收到主服務(wù)器的回應(yīng)，系統(tǒng)向客戶端發(fā)出一個危險（Jeopardy）事件，客戶端清空并暫時停用自己的緩存，從而進入一個稱為寬限期（Grace Period）的危險狀態(tài)。這個寬限期默認(rèn)是45秒。在寬限期內(nèi)，客戶端不會立刻斷開其與服務(wù)器端的聯(lián)系，而是不斷地做探詢。圖210中新的主服務(wù)器很快被重新選出，當(dāng)它接到客戶端的第一個KeepAlive請求（圖210中的4）時會拒絕（圖210中的5），因為這個請求的紀(jì)元號（Epoch Number）錯誤。不同主服務(wù)器的紀(jì)元號不相同，客戶端的每次請求都需要這個號來保證處理的請求是針對當(dāng)前的主服務(wù)器。客戶端在主服務(wù)器拒絕之后會使用新的紀(jì)元號來發(fā)送KeepAlive請求（圖210中的6）。新的主服務(wù)器接受這個請求并立刻做出回應(yīng)（圖210中的7）。如果客戶端接收到這個回應(yīng)的時間仍處于寬限期內(nèi)，則系統(tǒng)會恢復(fù)到安全狀態(tài)，租約期更新為C3。如果在寬限期未接到主服務(wù)器的相關(guān)回應(yīng)，則客戶端終止當(dāng)前的會話。2．主服務(wù)器出錯在客戶端