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