1、 Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxos Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,一種建議性的鎖而不是強(qiáng)制性的鎖；具有更大的靈活性,GFS使用Chubby選取一個GFS主服務(wù)器 Bigtable使用Chubby指定一個主服務(wù)器并發(fā)現(xiàn)、控制與其相關(guān)的子表服務(wù)器 Chubby還可以作為一個穩(wěn)定的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù) Google內(nèi)部還使用Chubby進(jìn)行名字服務(wù)（Name Server）,Chubby Google設(shè)計的提供粗粒度鎖服務(wù)的一個文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題,Paxos算法,Paxos算法 Leslie Lamp

2、ort最先提出的一種基于消息傳遞（Messages Passing）的一致性算法，用于解決分布式系統(tǒng)中的一致性問題,分布式系統(tǒng)一致性問題就是如何保證系統(tǒng)中初始狀態(tài)相同的各個節(jié)點在執(zhí)行相同的操作序列時，看到的指令序列是完全一致的，并且最終得到完全一致的結(jié)果,一個最簡單的方案在分布式系統(tǒng)中設(shè)置一個專門節(jié)點，在每次需要進(jìn)行操作之前，系統(tǒng)的各個部分向它發(fā)出請求，告訴該節(jié)點接下來系統(tǒng)要做什么。該節(jié)點接受第一個到達(dá)的請求內(nèi)容作為接下來的操作，這樣就能夠保證系統(tǒng)只有一個唯一的操作序列,方案存在什么缺陷？,Paxos算法,缺陷專門節(jié)點失效，整個系統(tǒng)就很可能出現(xiàn)不一致。為了避免這種情況，在系統(tǒng)中必然要設(shè)置多個專

3、門節(jié)點，由這些節(jié)點來共同決定操作序列,Paxos算法,proposers提出決議（Value，系統(tǒng)接下來執(zhí)行的指令） acceptors批準(zhǔn)決議 learners獲取并使用已經(jīng)通過的決議,Paxos算法,（1）決議只有被proposers提出后才 能批準(zhǔn),（2）每次只批準(zhǔn)一個決議,（3）只有決議確定被批準(zhǔn)后learners 才能獲取這個決議,保證數(shù)據(jù)的一致性,Paxos算法,P1：每個acceptor只接受它得到的第一個決議,系統(tǒng)約束條件,P1表明一個acceptor可以收到多個決議，為區(qū)分，對每個決議進(jìn)行編號，后到的決議編號大于先到的決議編號 ；約束條件P1不是很完備 ！,P2：一旦某個決議

4、得到通過，之后通過的決議必須和該決議保持一致,P2a：一旦某個決議v得到通過，之后任何acceptor再批準(zhǔn)的決議必須是v,P2a和P1是有矛盾的 !,P2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v,P1和P2b保證條件（2），彼此之間不存在矛盾。但是P2b很難通過一種技術(shù)手段來實現(xiàn)它，因此提出了一個蘊(yùn)涵P2b的約束P2c,P2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準(zhǔn)過編號小于n的任何提案，要么它們進(jìn)行的最近一次批準(zhǔn)具有值v,Paxos算法,決議通過的兩個階段,準(zhǔn)備階段：proposers選擇一個提案并將它的編號設(shè)為n，然后

5、將它發(fā)送給acceptors中的一個“多數(shù)派”。Acceptors 收到后，如果提案的編號大于它已經(jīng)回復(fù)的所有消息，則acceptors將自己上次的批準(zhǔn)回復(fù)給proposers，并不再批準(zhǔn)小于n的提案,批準(zhǔn)階段：當(dāng)proposers接收到acceptors 中的這個“多數(shù)派”的回復(fù)后，就向回復(fù)請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準(zhǔn)這個請求,解決一致性問題算法：為了減少決議發(fā)布過程中的消息量，acceptors將這個通過的決議發(fā)送給learners 的一個子集，然后由這個子集中的learners 去通

6、知所有其他的learners； 特殊情況：如果兩個proposer在這種情況下都轉(zhuǎn)而提出一個編號更大的提案，那么就可能陷入活鎖。此時需要選舉出一個president，僅允許 president提出提案, Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxos Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,系統(tǒng)設(shè)計目標(biāo),Chubby系統(tǒng)設(shè)計,高可用性和高可靠性；首要目標(biāo)，在保證這一目標(biāo)的基礎(chǔ)上再考慮系統(tǒng)的吞吐量和存儲能力,高擴(kuò)展性；將數(shù)據(jù)存儲在價格較為低廉的RAM，支持大規(guī)模用戶訪問文件,支持粗粒度的建議性鎖服務(wù)；提供這種服務(wù)的根本目的是提高系統(tǒng)的性能,服務(wù)信息的直接存儲；可直接存儲包

7、括元數(shù)據(jù)、系統(tǒng)參數(shù)在內(nèi)的有關(guān)服務(wù)信息,支持通報機(jī)制；客戶可以及時地了解到事件發(fā)生,支持緩存機(jī)制；通過一致性緩存將常用信息保存在客戶端，避免了頻繁地訪問主服務(wù)器,Chubby系統(tǒng)設(shè)計,Chubby中還添加了一些新的功能特性；這種設(shè)計主要是考慮到以下幾個問題,03,02,01,開發(fā)者初期很少考慮系統(tǒng)的一致性，但隨著開發(fā)進(jìn)行，問題會變得越來越嚴(yán)重。單獨(dú)的鎖服務(wù)可以保證原有系統(tǒng)架構(gòu)不會發(fā)生改變，而使用函數(shù)庫很可能需要對系統(tǒng)架構(gòu)做出大幅度的改動,系統(tǒng)中很多事件發(fā)生是需要告知其他用戶和服務(wù)器，使用一個基于文件系統(tǒng)的鎖服務(wù)可以將這些變動寫入文件中。有需要的用戶和服務(wù)器直接訪問這些文件即可，避免因大量系統(tǒng)組件

8、之間事件通信帶來系統(tǒng)性能下降,基于鎖的開發(fā)接口容易被開發(fā)者接受。雖然在分布式系統(tǒng)中鎖的使用會有很大的不同，但是和一致性算法相比，鎖顯然被更多的開發(fā)者所熟知,Chubby系統(tǒng)設(shè)計,Paxos算法實現(xiàn)過程中需要一個“多數(shù)派”就某個值達(dá)成一致，本質(zhì)上就是分布式系統(tǒng)中常見的quorum機(jī)制；為保證系統(tǒng)高可用性，需要若干臺機(jī)器，但使用單獨(dú)鎖服務(wù)的話一臺機(jī)器也能保證這種高可用性,Chubby設(shè)計過程中一些細(xì)節(jié)問題值得關(guān)注： 在Chubby系統(tǒng)中采用了建議性的鎖而沒有采用強(qiáng)制性的鎖。兩者的根本區(qū)別在于用戶訪問某個被鎖定的文件時，建議性的鎖不會阻止訪問，而強(qiáng)制性的鎖則會阻止訪問，實際上這是為了方便系統(tǒng)組件之間

9、的信息交互 另外，Chubby還采用了粗粒度（Coarse-Grained）鎖服務(wù)而沒有采用細(xì)粒度（Fine-Grained）鎖服務(wù)，兩者的差異在于持有鎖的時間，細(xì)粒度的鎖持有時間很短,Chubby系統(tǒng)設(shè)計,Chubby基本架構(gòu)：客戶端和服務(wù)器端，兩者通過遠(yuǎn)程過程調(diào)用（RPC）來連接 客戶端每個客戶應(yīng)用程序都有一個Chubby程序庫（Chubby Library），所有應(yīng)用都是通過調(diào)用這個庫中相關(guān)函數(shù)來完成 服務(wù)器一端Chubby單元，一般由五個稱為副本（Replica）服務(wù)器組成，它們配置上完全一致，且系統(tǒng)剛開始時處于對等地位, Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxo

10、s Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,Chubby中的Paxos,單個Chubby副本結(jié)構(gòu),容錯日志對數(shù)據(jù)庫正確性提供重要支持；一致性由Paxos算法保證；副本之間通過特定的Paxos協(xié)議通信，同時本地文件中保存與Chubby中相同的日志數(shù)據(jù),容錯數(shù)據(jù)庫快照（Snapshot）和記錄數(shù)據(jù)庫操作重播日志（Replay-log）；每一次的數(shù)據(jù)庫操作最終都將提交至日志中；本地文件中也保存著一份數(shù)據(jù)庫數(shù)據(jù)副本,Chubby構(gòu)建在這個容錯的數(shù)據(jù)庫之上，Chubby利用這個數(shù)據(jù)庫存儲所有的數(shù)據(jù)。Chubby的客戶端通過特定的Chubby協(xié)議和單個的Chubby副本進(jìn)行通信,Chubby中的Pa

11、xos,容錯日志的API,Content Title,Content Title,Chubby中Paxos算法過程,2、協(xié)調(diào)者從客戶提交的值中選擇一個，accept消息廣播給所有的副本，其他的副本收到廣播后，選擇接受或者拒絕這個值，并將決定結(jié)果反饋,3、協(xié)調(diào)者收到大多數(shù)副本接受信息后，認(rèn)為達(dá)到了一致性，接著向相關(guān)副本發(fā)送一個commit消息,1、選擇一副本為協(xié)調(diào)者（Coordinator）,Chubby中的Paxos,Chubby設(shè)計者借鑒了Paxos的兩種解決機(jī)制：給協(xié)調(diào)者指派序號或限制協(xié)調(diào)者可以選擇的值 指派序號的方法 （1）在一個有n個副本系統(tǒng)中，為每個副本分配一個id ，其中 0irn

12、-1。則副本的序號，其中k的初始值為0 （2）某個副本想成為協(xié)調(diào)者之后，它就根據(jù)規(guī)則生成一個比它以前的序號更大的序號（實際上就是提高k的值），并將這個序號通過propose消息廣播給其他所有的副本 （3）如果接受到廣播的副本發(fā)現(xiàn)該序號比它以前見過的序號都大，則向發(fā)出廣播的副本返回一個promise消息，并且承諾不再接受舊的協(xié)調(diào)者發(fā)送的消息。如果大多數(shù)副本都返回了promise消息，則新的協(xié)調(diào)者就產(chǎn)生了 限制協(xié)調(diào)者可以選擇的值 Paxos強(qiáng)制新的協(xié)調(diào)者必須選擇和前任相同的值,Chubby中的Paxos,Chubby做了一個重要優(yōu)化來提高系統(tǒng)效率在選擇某一個副本作為協(xié)調(diào)者之后就長期不變，此時協(xié)調(diào)者

13、就被稱為主服務(wù)器（Master） 客戶端的數(shù)據(jù)請求由主服務(wù)器完成，Chubby保證在一定時間內(nèi)有且僅有一個主服務(wù)器，這個時間就稱為主服務(wù)器租約期（Master Lease） 客戶端需要確定主服務(wù)器的位置，可向DNS發(fā)送一個主服務(wù)器定位請求，非主服務(wù)器的副本將對該請求做出回應(yīng) Chubby對于Paxos論文中未提及的一些技術(shù)細(xì)節(jié)進(jìn)行了補(bǔ)充，所以Chubby的實現(xiàn)是基于Paxos，但其技術(shù)手段更加的豐富，更具有實踐性, Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxos Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,Chubby文件系統(tǒng),Chubby系統(tǒng)本質(zhì)上就是一個分布式的、存儲大

14、量小文件的文件系統(tǒng)，它所有的操作都是在文件的基礎(chǔ)上完成 Chubby最常用的鎖服務(wù)中，每一個文件就代表一個鎖，用戶通過打開、關(guān)閉和讀取文件，獲取共享（Shared）鎖或獨(dú)占（Exclusive）鎖 選舉主服務(wù)器過程中，符合條件的服務(wù)器都同時申請打開某個文件并請求鎖住該文件 成功獲得鎖的服務(wù)器自動成為主服務(wù)器并將其地址寫入這個文件夾，以便其他服務(wù)器和用戶可以獲知主服務(wù)器的地址信息,Chubby文件系統(tǒng),Chubby的文件系統(tǒng)和UNIX類似 例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統(tǒng)的共有前綴；foo是某個單元的名稱；

15、/wombat/pouch則是foo這個單元上的文件目錄或者文件名 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ù),實例號：新節(jié)點實例號必定大于舊節(jié)點的實例號,元數(shù)據(jù)包含以下四種

16、單調(diào)遞增64位編號,內(nèi)容生成號：文件內(nèi)容修改時該號增加,鎖生成號：鎖被用戶持有時該號增加,ACL生成號：ACL名被覆寫時該號增加,Chubby文件系統(tǒng),Chubby文件系統(tǒng),用戶打開某個節(jié)點的同時會獲取一個類似于UNIX中文件描述符（File Descriptor）的句柄，這個句柄由以下三個部分組成,Chubby文件系統(tǒng),在實際執(zhí)行中，為了避免所有的通信都使用序號帶來系統(tǒng)開銷增長，Chubby引入了sequencer的概念 sequencer實際上就是一個序號，只能由鎖的持有者在獲取鎖時向系統(tǒng)發(fā)出請求來獲得。這樣一來Chubby系統(tǒng)中只有涉及鎖的操作才需要序號，其他一概不用。 在文件操作中，用

17、戶可以將句柄看做一個指向文件系統(tǒng)的指針,常用句柄函數(shù)及其作用, Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxos Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,Chubby客戶端與服務(wù)器端的通信過程,從左到右的水平方向表示時間在增加，斜向上的箭頭表示一次KeepAlive請求，斜向下的箭頭則是主服務(wù)器的一次回應(yīng) M1、M2、M3表示不同的主服務(wù)器租約期；C1、C2、C3則是客戶端對主服務(wù)器租約期時長做出的一個估計 KeepAlive是周期發(fā)送的一種信息，它主要有兩方面的功能：延遲租約的有效期和攜帶事件信息告訴用戶更新,故障處理,客戶端租約過期,客戶端向主服務(wù)器發(fā)出一個KeepA

18、live請求（上圖1） 如果有需要通知的事件時則主服務(wù)器會立刻做出回應(yīng)，否則等到客戶端的租約期C1快結(jié)束的時候才做出回應(yīng)（圖2），并更新主服務(wù)器租約期為M2 客戶端接到回應(yīng)后認(rèn)為該主服務(wù)器仍處于活躍狀態(tài)，于是將租約期更新為C2并立刻發(fā)出新的KeepAlive請求（圖3） 寬限期內(nèi)，客戶端不會立刻斷開其與服務(wù)器端的聯(lián)系，而是不斷地做探詢，當(dāng)它接到客戶端的第一個KeepAlive請求（圖4）時會拒絕（圖5） 客戶端在主服務(wù)器拒絕后使用新紀(jì)元號來發(fā)送KeepAlive請求（圖6） 新的主服務(wù)器接受這個請求并立刻做出回應(yīng)（圖7） 如果客戶端接收到這個回應(yīng)的時間仍處于寬限期內(nèi)，系統(tǒng)會恢復(fù)到安全狀態(tài)，租約

19、期更新為C3。如果在寬限期未接到主服務(wù)器的相關(guān)回應(yīng)，客戶端終止當(dāng)前的會話,故障處理,主服務(wù)器出錯,正常情況下舊的主服務(wù)器出現(xiàn)故障后系統(tǒng)會很快地選舉出新的主服務(wù)器，新選舉需要經(jīng)歷以下九個步驟： （1）產(chǎn)生一個新的紀(jì)元號以便今后客戶端通信時使用，這能保證當(dāng)前的主服務(wù)器不必處理針對舊的主服務(wù)器的請求 （2）只處理主服務(wù)器位置相關(guān)的信息，不處理會話相關(guān)的信息 （3）構(gòu)建處理會話和鎖所需的內(nèi)部數(shù)據(jù)結(jié)構(gòu) （4）允許客戶端發(fā)送KeepAlive請求，不處理其他會話相關(guān)的信息 （5）向每個會話發(fā)送一個故障事件，促使所有的客戶端清空緩存 （6）等待直到所有的會話都收到故障事件或會話終止 （7）開始允許執(zhí)行所有的

20、操作 （8）如果客戶端使用了舊的句柄則需要為其重新構(gòu)建新的句柄 （9）一定時間段后（1分鐘），刪除沒有被打開過的臨時文件夾,如果這一過程在寬限期內(nèi)順利完成，則用戶不會感覺到任何故障的發(fā)生，也就是說新舊主服務(wù)器的替換對于用戶來說是透明的，用戶感覺到的僅僅是一個延遲,系統(tǒng)實現(xiàn)時，Chubby還使用了一致性客戶端緩存（Consistent Client-Side Caching）技術(shù)，這樣做的目的是減少通信壓力，降低通信頻率 在客戶端保存一個和單元上數(shù)據(jù)一致的本地緩存，需要時客戶可以直接從緩存中取出數(shù)據(jù)而不用再和主服務(wù)器通信 當(dāng)某個文件數(shù)據(jù)或者元數(shù)據(jù)需要修改時，主服務(wù)器首先將這個修改阻塞；然后通過查

21、詢主服務(wù)器自身維護(hù)的一個緩存表，向?qū)π薷牡臄?shù)據(jù)進(jìn)行了緩存的所有客戶端發(fā)送一個無效標(biāo)志（Invalidation） 客戶端收到這個無效標(biāo)志后會返回一個確認(rèn)（Acknowledge），主服務(wù)器在收到所有的確認(rèn)后才解除阻塞并完成這次修改,這個過程的執(zhí)行效率非常高，僅僅需要發(fā)送一次無效標(biāo)志即可，因為對于沒有返回確認(rèn)的節(jié)點，主服務(wù)器直接認(rèn)為其是未緩存, Paxos算法 Chubby系統(tǒng)設(shè)計 Chubby中的Paxos Chubby文件系統(tǒng) 通信協(xié)議 正確性與性能,一致性,每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務(wù)器，這種選舉本質(zhì)上就是一個一致性問題。實際執(zhí)行過程中，Chubby使用Paxos算法來解決 主服務(wù)器產(chǎn)生后客戶端的所有讀寫操作都是由主服務(wù)器來完成的 讀操作很簡