一、前言
在上一篇理解了Paxos算法的理論基礎(chǔ)后，接下來看看Paxos算法在工程中的應(yīng)用。
二、Chubby
Chubby是一個面向松耦合分布式系統(tǒng)的鎖服務(wù)，GFS（Google File System）和Big Table等大型系統(tǒng)都是用它來解決分布式協(xié)作、元數(shù)據(jù)存儲和Master選舉等一些列與分布式鎖服務(wù)相關(guān)的問題。Chubby的底層一致性實現(xiàn)就是以Paxos算法為基礎(chǔ)，Chubby提供了粗粒度的分布式鎖服務(wù)，開發(fā)人員直接調(diào)用Chubby的鎖服務(wù)接口即可實現(xiàn)分布式系統(tǒng)中多個進程之間粗粒度的同控制，從而保證分布式數(shù)據(jù)的一致性。
2.1 設(shè)計目標
Chubby被設(shè)計成為一個需要訪問中心化的分布式鎖服務(wù)。
① 對上層應(yīng)用程序的侵入性更小，使用一個分布式鎖服務(wù)的接口方式對上層應(yīng)用程序的侵入性更小，應(yīng)用程序只需調(diào)用相應(yīng)的接口即可使用分布式一致性特性，并且更易于保持系統(tǒng)已有的程序結(jié)構(gòu)和網(wǎng)絡(luò)通信模式。
② 便于提供數(shù)據(jù)的發(fā)布與訂閱，在Chubby進行Master選舉時，需要使用一種廣播結(jié)果的機制來向所有客戶端公布當前Master服務(wù)器，這意味著Chubby應(yīng)該允許其客戶端在服務(wù)器上進行少量數(shù)據(jù)的存儲和讀?。ù鎯χ鱉aster地址等信息），也就是對小文件的讀寫操作。數(shù)據(jù)的發(fā)布與訂閱功能和鎖服務(wù)在分布式一致性特性上是相通的。
③ 開發(fā)人員對基于鎖的接口更為熟悉，Chubby提供了一套近乎和單機鎖機制一直的分布式鎖服務(wù)接口。
④ 更便捷地構(gòu)建更可靠的服務(wù)，Chubby中通常使用5臺服務(wù)器來組成一個集群單元（Cell），根據(jù)Quorum機制（在一個由若干個機器組成的集群中，在一個數(shù)據(jù)項值的選定過程中，要求集群中過半的機器達成一致），只要整個集群中有3臺服務(wù)器是正常運行的，那么整個集群就可以對外提供正常的服務(wù)。
⑤ 提供一個完整的、獨立的分布式鎖服務(wù)，Chubby對于上層應(yīng)用程序的侵入性特別低，對于Master選舉同時將Master信息等級并廣播的場景，應(yīng)用程序只需要向Chubby請求一個鎖，并且在獲得鎖之后向相應(yīng)的鎖文件寫入Master信息即可，其余的客戶端就可以通過讀取這個鎖文件來獲取Master信息。
⑥ 提供粗粒度的鎖服務(wù)，Chubby針對的應(yīng)用場景是客戶端獲得鎖之后會進行長時間持有（數(shù)小時或數(shù)天），而非用于短暫獲取鎖的場景。當鎖服務(wù)短暫失效時（服務(wù)器宕機），Chubby需要保持所有鎖的持有狀態(tài)，以避免持有鎖的客戶端出現(xiàn)問題。而細粒度鎖通常設(shè)計為為鎖服務(wù)一旦失效就釋放所有鎖，因為其持有時間很短，所以其放棄鎖帶來的代價較小。
⑦ 高可用、高可靠，對于一個由5太機器組成的集群而言，只要保證3臺正常運行的機器，整個集群對外服務(wù)就能保持可用，另外，由于Chubby支持通過小文件讀寫服務(wù)的方式來進行Master選舉結(jié)果的發(fā)布與訂閱，因此在Chubby的實際應(yīng)用中，必須能夠支撐成百上千個Chubby客戶端對同一個文件進行監(jiān)控和讀取。
⑧ 提供時間通知機制，Chubby客戶端需要實時地感知到Master的變化情況，這可以通過讓你客戶端反復(fù)輪詢來實現(xiàn)，但是在客戶端規(guī)模不斷增大的情況下，客戶端主動輪詢的實時性效果并不理想，且對服務(wù)器性能和網(wǎng)絡(luò)帶寬壓力都非常大，因此，Chubby需要有能力將服務(wù)端的數(shù)據(jù)變化情況以時間的形式通知到所有訂閱的客戶端。
2.2 技術(shù)架構(gòu)
Chubby的整個系統(tǒng)結(jié)構(gòu)主要由服務(wù)端和客戶端兩部分組成，客戶端通過RPC調(diào)用和服務(wù)端進行通信，如下圖所示。
一個典型的Chubby集群（Chubby Cell），通常由5臺服務(wù)器組成，這些副本服務(wù)器采用Paxos協(xié)議，通過投票的方式來選舉產(chǎn)生一個獲得過半投票的服務(wù)器作為Master，一旦成為Master，Chubby就會保證在一段時間內(nèi)不會再有其他服務(wù)器成為Master，這段時期稱為Master租期（Master Lease），在運行過程中，Master服務(wù)器會通過不斷續(xù)租的方式來延長Master租期，而如果Master服務(wù)器出現(xiàn)故障，那么余下的服務(wù)器會進行新一輪的Master選舉，最終產(chǎn)生新的Master服務(wù)器，開始新的Master租期。
集群中的每個服務(wù)器都維護著一份服務(wù)端數(shù)據(jù)庫的副本，但在實際運行過程中，只有Master服務(wù)器才能對數(shù)據(jù)庫進行寫操作，而其他服務(wù)器都是使用Paxos協(xié)議從Master服務(wù)器上同步數(shù)據(jù)庫數(shù)據(jù)的更新。
Chubby客戶端通過向記錄有Chubby服務(wù)端機器列表的DNS來請求獲取所有的Chubby服務(wù)器列表，然后逐一發(fā)起請求詢問該服務(wù)器是否是Master，在這個詢問過程中，那些非Master的服務(wù)器，則會將當前Master所在的服務(wù)器標志反饋給客戶端，這樣客戶端就能很快速的定位到Master服務(wù)器了。
只要該Master服務(wù)器正常運行，那么客戶端就會將所有的請求都發(fā)送到該Master服務(wù)器上，針對寫請求，Master會采用一致性協(xié)議將其廣播給集群中所有的副本服務(wù)器，并且在過半的服務(wù)器接受了該寫請求后，再響應(yīng)給客戶端正確的應(yīng)答，而對于讀請求，則不需要在集群內(nèi)部進行廣播處理，直接由Master服務(wù)器單獨處理即可。
若該Master服務(wù)器發(fā)生故障，那么集群中的其他服務(wù)器會在Master租期到期后，重新開啟新的一輪Master選舉，通常一次Master選舉大概花費幾秒鐘的時間，而如果其他副本服務(wù)器崩潰，那么整個集群繼續(xù)工作，該崩潰的服務(wù)器會在恢復(fù)之后自動加入到Chubby集群中去，新加入的服務(wù)器首先需要同步Chubby最新的數(shù)據(jù)庫數(shù)據(jù)，完成數(shù)據(jù)庫同步之后，新的服務(wù)器就可以加入到正常的Paxos運作流程中與其他服務(wù)器副本一起協(xié)同工作。若崩潰后幾小時后仍無法恢復(fù)工作，那么需要加入新的機器，同時更新DNS列表（新IP代替舊IP），Master服務(wù)器會周期性地輪詢DNS列表，因此會很快感知服務(wù)器地址的變更，然后Master就會將集群數(shù)據(jù)庫中的地址列表做相應(yīng)的變更，集群內(nèi)部的其他副本服務(wù)器通過復(fù)制方式就可以獲取到最新的服務(wù)器地址列表了。
2.3 目錄與文件
Chubby對外提供了一套與Unix文件系統(tǒng)非常相近但是更簡單的訪問接口。Chubby的數(shù)據(jù)結(jié)構(gòu)可以看作是一個由文件和目錄組成的樹，其中每一個節(jié)點都可以表示為一個使用斜杠分割的字符串，典型的節(jié)點路徑表示如下：
/ls/foo/wombat/pouch
其中，ls是所有Chubby節(jié)點所共有的前綴，代表著鎖服務(wù)，是Lock Service的縮寫；foo則指定了Chubby集群的名字，從DNS可以查詢到由一個或多個服務(wù)器組成該Chubby集群；剩余部分的路徑/wombat/pouch則是一個真正包含業(yè)務(wù)含義的節(jié)點名字，由Chubby服務(wù)器內(nèi)部解析并定位到數(shù)據(jù)節(jié)點。
Chubby的命名空間，包括文件和目錄，我們稱之為節(jié)點（Nodes，我們以數(shù)據(jù)節(jié)點來泛指Chubby的文件或目錄）。在同一個Chubby集群數(shù)據(jù)庫中，每一個節(jié)點都是全局唯一的。和Unix系統(tǒng)一樣，每個目錄都可以包含一系列的子文件和子目錄列表，而每個文件中則會包含文件內(nèi)容。Chubby沒有符號鏈接和硬連接的概念。
Chubby上的每個數(shù)據(jù)節(jié)點都分為持久節(jié)點和臨時節(jié)點兩大類，其中持久節(jié)點需要顯式地調(diào)用接口API來進行刪除，而臨時節(jié)點則會在其對應(yīng)的客戶端會話失效后被自動刪除。也就是說，臨時節(jié)點的生命周期和客戶端會話綁定，如果該臨時節(jié)點對應(yīng)的文件沒有被任何客戶端打開的話，那么它就會被刪除掉。因此，臨時節(jié)點通?？梢杂脕磉M行客戶端會話有效性的判斷依據(jù)。
Chubby的每個數(shù)據(jù)節(jié)點都包含了少量的元數(shù)據(jù)信息，其中包括用于權(quán)限控制的訪問控制列表（ACL）信息，同時每個節(jié)點的元數(shù)據(jù)還包括4個單調(diào)遞增的64位標號：
① 實例標號，用于標識創(chuàng)建該數(shù)據(jù)節(jié)點的順序，節(jié)點的創(chuàng)建順序不同，其實例編號也不相同，可以通過實例編號來識別兩個名字相同的數(shù)據(jù)節(jié)點是否是同一個數(shù)據(jù)節(jié)點，因為創(chuàng)建時間晚的數(shù)據(jù)節(jié)點，其實例編號必定大于任意先前創(chuàng)建的同名節(jié)點。
② 文件內(nèi)容編號（針對文件），用于標識文件內(nèi)容的變化情況，該編號會在文件內(nèi)容被寫入時增加。
③ 鎖編號，用于標識節(jié)點鎖狀態(tài)的變更情況，該編號會在節(jié)點鎖從自由狀態(tài)轉(zhuǎn)化到被持有狀態(tài)時增加。
④ ACL編號，用于標識節(jié)點的ACL信息變更情況，該編號會在節(jié)點的ACL配置信息被寫入時增加。
2.4 鎖和鎖序列器
分布式環(huán)境中鎖機制十分復(fù)雜，消息的延遲或是亂序都有可能引起鎖的失效，如客戶端C1獲得互斥鎖L后發(fā)出請求R，但請求R遲遲沒有到達服務(wù)端（網(wǎng)絡(luò)延遲或消息重發(fā)等），這時應(yīng)用程序會認為該客戶端進程已經(jīng)失敗，于是為另一個客戶端C2分配鎖L，然后在發(fā)送請求R，并成功應(yīng)用到了服務(wù)器上。然而，之前的請求R經(jīng)過一波三折后也到達了服務(wù)器端，此時，它可能不瘦任何鎖控制的情況下被服務(wù)端處理，而覆蓋了客戶端C2的操作，也是導(dǎo)致了數(shù)據(jù)不一致問題。
在Chubby中，任意一個數(shù)據(jù)節(jié)點均可被當做一個讀寫鎖來使用：一種是單個客戶端排他（寫）模式持有這個鎖，另一種則是任意數(shù)目的客戶端以共享（讀）模式持有這個鎖，Chubby放棄了嚴格的強制鎖，客戶端可以在沒有獲取任何鎖的情況下訪問Chubby的文件。
Chubby采用了鎖延遲和鎖序列器兩種策略來解決上述由于消息延遲和重排序引起的分布式鎖問題，對于鎖延遲而言，如果一個客戶端以正常的方式主動釋放了一個鎖，那么Chubby服務(wù)端將會允許其他客戶端能夠立即獲取到該鎖；如果鎖是以異常情況被釋放的話，那么Chubby服務(wù)器會為該鎖保留一定的時間，這稱之為鎖延遲，這段時間內(nèi)，其他客戶端無法獲取該鎖，其可以很好的防止一些客戶端由于網(wǎng)絡(luò)閃斷的原因而與服務(wù)器暫時斷開的場景。對于鎖序列器而言，其需要Chubby的上層應(yīng)用配合在代碼中加入相應(yīng)的修改邏輯，任何時候，鎖的持有者都可以向Chubby請求一個鎖序列器，其包括鎖的名字、鎖模式（排他或共享）、鎖序號，當客戶端應(yīng)用程序在進行一些需要鎖機制保護的操作時，可以將該鎖序列器一并發(fā)送給服務(wù)端，服務(wù)端收到該請求后，會首先檢測該序列器是否有效，以及檢查客戶端是否處于恰當?shù)逆i模式，如果沒有通過檢查，那么服務(wù)端就會拒絕該客戶端的請求。
2.5 事件通知機制
為了避免大量客戶端輪詢Chubby服務(wù)端狀態(tài)所帶來的壓力，Chubby提供了事件通知機制，客戶端可以向服務(wù)端注冊事件通知，當觸發(fā)這些事件時，服務(wù)端就會向客戶端發(fā)送對應(yīng)的時間通知，消息通知都是通過異步的方式發(fā)送給客戶端的。常見的事件如下
① 文件內(nèi)容變更 ② 節(jié)點刪除 ③ 子節(jié)點新增、刪除 ④ Master服務(wù)器轉(zhuǎn)移
2.6 緩存
其是為了減少客戶端與服務(wù)端之間的頻繁的讀請求對服務(wù)端的壓力設(shè)計的，會在客戶端對文件內(nèi)容和元數(shù)據(jù)信息進行緩存，雖然緩存提高了系統(tǒng)的整體性能，但是其也帶來了一定復(fù)雜性，如如何保證緩存的一致性。其通過租期機制來保證緩存的一致性。
緩存的生命周期和Master租期機制緊密相關(guān)，Master會維護每個客戶端的數(shù)據(jù)緩存情況，并通過向客戶端發(fā)送過期信息的方式來保證客戶端數(shù)據(jù)的一致性，在此機制下，Chubby能夠保證客戶端要么能夠從緩存中訪問到一致的數(shù)據(jù)，要么訪問出錯，而一定不會訪問到不一致的數(shù)據(jù)。具體的講，每個客戶端的緩存都有一個租期，一旦該租期到期，客戶端就需要向服務(wù)端續(xù)訂租期以繼續(xù)維持緩存的有效性，當文件數(shù)據(jù)或元數(shù)據(jù)被修改時，Chubby服務(wù)端首先會阻塞該修改操作，然后由Master向所有可能緩存了該數(shù)據(jù)的客戶端發(fā)送緩存過期信號，使其緩存失效，等到Master在接收到所有相關(guān)客戶端針對該過期信號的應(yīng)答（客戶端明確要求更新緩存或客戶端允許緩存租期過期）后，再進行之前的修改操作。
2.7 會話
Chubby客戶端和服務(wù)端之間通過創(chuàng)建一個TCP連接來進行所有的網(wǎng)絡(luò)通信操作，這稱之為會話，會話存在生命周期，存在超時時間，在超時時間內(nèi)，客戶端和服務(wù)端之間可以通過心跳檢測來保持會話的活性，以使會話周期得到延續(xù)，這個過程稱為KeepAlive（會話激活），如果能夠成功地通過KeepAlive過程將Chubby會話一直延續(xù)下去，那么客戶端創(chuàng)建的句柄、鎖、緩存數(shù)據(jù)等將仍然有效。
2.8 KeepAlive請求
Master服務(wù)端在收到客戶端的KeepAlive請求時，首先會將該請求阻塞住，并等到該客戶端的當前會話租期即將過期時，才為其續(xù)租該客戶端的會話租期，之后再向客戶端響應(yīng)這個KeepAlive請求，并同時將最新的會話租期超時時間反饋給客戶端，在正常情況下，每個客戶端總是會有一個KeepAlive請求阻塞在Master服務(wù)器上。
2.9 會話超時
客戶端也會維持一個和Master端近似相同（由于KeepAlive響應(yīng)在網(wǎng)絡(luò)傳輸過程中會花費一定的時間、Master服務(wù)端和客戶端存在時鐘不一致的現(xiàn)象）的會話租期?？蛻舳嗽谶\行過程中，按照本地的會話租期超時時間，檢測到其會話租期已經(jīng)過期卻尚未收到Master的KeepAlive響應(yīng)，此時，它將無法確定Master服務(wù)端是否已經(jīng)中止了當前會話，這個時候客戶端處于危險狀態(tài)，此時，客戶端會清空其本地緩存并將其標記為不可用，同時客戶端還會等待一個被稱作寬限期的時間周期，默認為45秒，若在寬限期到期前，客戶端與服務(wù)端之間成功地進行了KeepAlive，那么客戶端就會再次開啟本地緩存，否則，客戶端就會認為當前會話已經(jīng)過期了，從而終止本次會話。
在客戶端進入危險狀態(tài)時，客戶端會通過一個“jeopardy”事件來通知上層應(yīng)用程序，如果恢復(fù)正常，客戶端同樣會以一個“safe”事件來通知應(yīng)用程序可以繼續(xù)正常運行，但如果客戶端最終沒能從危險狀態(tài)中恢復(fù)過來，那么客戶端會以一個“expired”事件來通知應(yīng)用程序當前Chubby會話已經(jīng)超時。
2.10 Master故障恢復(fù)
Master服務(wù)端會運行著會話租期計時器，用來管理所有的會話的生命周期，如果Master在運行過程中出現(xiàn)故障，那么該計時器就會停止，直到新的Master選舉產(chǎn)生后，計時器才會繼續(xù)計時，即從舊的Master崩潰到新的Master選舉產(chǎn)生所花費的時間將不計入會話超時的計算中，這就等價于延長了客戶端的會話租期，如果Master在短時間內(nèi)就選舉產(chǎn)生了，那么客戶端就可以在本地會話租期過期前與其創(chuàng)建連接，而如果Master的選舉花費了較長的時間，就會導(dǎo)致客戶端只能清空本地的緩存而進入寬限期進行等待，由于寬限期的存在，使得會話能夠很好地在服務(wù)端Master轉(zhuǎn)化的過程中得到維持，整個Master的故障恢復(fù)過程中服務(wù)端和客戶端的交互情況如下
如上圖所示，一開始在舊的Master服務(wù)器上維持了一個會話租期lease M1，在客戶端上維持對應(yīng)的lease C1，同時客戶端的KeepAlive請求1一直被Master服務(wù)器阻塞著。一段時間后，Master向客戶端反饋了KeepAlive響應(yīng)2，同時開始了新的會話租期lease M2，而客戶端在接收到該KeepAlive響應(yīng)后，立即發(fā)送了新的KeepAlive請求3，并同時也開始了新的會話租期lease C2。至此，客戶端和服務(wù)端的交互都是正常的，隨后，Master發(fā)生了故障，從而無法反饋客戶端的KeepAlive請求3，在此過程中，客戶端檢測到會話租期lease C2已經(jīng)過期，它會清空本地緩存并進入寬限期，這段時間內(nèi)，客戶端無法確定Master上的會話周期是否也已經(jīng)過期，因此它不會銷毀它的本地會話，而是將所有應(yīng)用程序?qū)λ腁PI調(diào)用都阻塞住，以避免出現(xiàn)數(shù)據(jù)不一致的現(xiàn)象。同時，在客戶端寬限期開始時，客戶端會向上層應(yīng)用程序發(fā)送一個“jeopardy”事件，一段時間后，服務(wù)器開始選舉產(chǎn)生新的Master，并為該客戶端初始化了新的會話租期lease M3，當客戶端向新的Master發(fā)送KeepAlive請求4時，Master檢測到該客戶端的Master周期號已經(jīng)過期，因此會在KeepAlive響應(yīng)5中拒絕這個客戶端請求，并將最新的Master周期號發(fā)送給客戶端，之后，客戶端會攜帶上最新的Master周期號，再次發(fā)送KeepAlive請求6給Master，最終，整個客戶端和服務(wù)端之間的會話就會再次回復(fù)正常。
在Master轉(zhuǎn)化的這段時間內(nèi)，只要客戶端的寬限足夠長，那么客戶端應(yīng)用程序就可以在沒有任何察覺的情況下，實現(xiàn)Chubby的故障恢復(fù)，但如果客戶端的寬限期設(shè)置得比較短，那么Chubby客戶端就會丟棄當前會話，并將這個異常情況通知給上層應(yīng)用程序。
一旦客戶端與新的Master建立上連接之后，客戶端和Master之間會通過互相配合來實現(xiàn)對故障的平滑恢復(fù)，新的Master會設(shè)法將上一個Master服務(wù)器的內(nèi)存狀態(tài)構(gòu)建出來，同時，由于本地數(shù)據(jù)庫記錄了每個客戶端的會話信息，以及持有的鎖和臨時文件等信息，因此Chubby會通過讀取本地磁盤上的數(shù)據(jù)來恢復(fù)一部分狀態(tài)。一個新的Master服務(wù)器選舉之后，會進行如下處理。
① 確定Master周期。Master周期用來唯一標識一個Chubby集群的Master統(tǒng)治輪次，以便區(qū)分不同的Master，只要發(fā)生Master重新選舉，就一定會產(chǎn)生新的Master周期，即使選舉前后Master是同一臺機器。
② 新的Master能夠?qū)蛻舳说腗aster尋址請求進行響應(yīng)，但是不會立即開始處理客戶端會話相關(guān)的請求操作。
③ Master根據(jù)本地數(shù)據(jù)庫中存儲的會話和鎖信息來構(gòu)建服務(wù)器的內(nèi)存狀態(tài)。
④ 至此，Master已經(jīng)能夠處理客戶端的KeepAlive請求，但仍然無法處理其他會話相關(guān)的操作。
⑤ Master會發(fā)送一個Master故障切換事件給每一個會話，客戶端接收到這個事件后，會清空它的本地緩存，并警告上層應(yīng)用程序可能已經(jīng)丟失了別的事件，之后再向Master反饋應(yīng)答。
⑥ 此時，Master會一直等待客戶端的應(yīng)答，直到每一個會話都應(yīng)答了這個切換事件。
⑦ Master接收了所有客戶端的應(yīng)答之后，就能夠開始處理所有的請求操作。
⑧若客戶端使用了一個故障切換之間創(chuàng)建的句柄，Master會重新為其創(chuàng)建這個句柄的內(nèi)存對象，并執(zhí)行調(diào)用，如果該句柄在之前的Master周期中就已經(jīng)被關(guān)閉了，那么它就不能在這個Master周期內(nèi)再次被重建了，這一機制就確保了由于網(wǎng)絡(luò)原因使得Master接收到那些延遲或重發(fā)的網(wǎng)絡(luò)數(shù)據(jù)包也不會錯誤的重建一個已經(jīng)關(guān)閉的句柄。
三、Paxos協(xié)議實現(xiàn)
Chubby服務(wù)端的基本架構(gòu)大致分為三層
① 最底層是容錯日志系統(tǒng)（Fault-Tolerant Log），通過Paxos算法能夠保證集群所有機器上的日志完全一致，同時具備較好的容錯性。
② 日志層之上是Key-Value類型的容錯數(shù)據(jù)庫（Fault-Tolerant DB），其通過下層的日志來保證一致性和容錯性。
③ 存儲層之上的就是Chubby對外提供的分布式鎖服務(wù)和小文件存儲服務(wù)。
Paxos算法用于保證集群內(nèi)各個副本節(jié)點的日志能夠保持一致，Chubby事務(wù)日志（Transaction Log）中的每一個Value對應(yīng)Paxos算法中的一個Instance（對應(yīng)Proposer），由于Chubby需要對外提供不斷的服務(wù)，因此事務(wù)日志會無限增長，于是在整個Chubby運行過程中，會存在多個Paxos Instance，同時，Chubby會為每個Paxos Instance都按序分配一個全局唯一的Instance編號，并將其順序?qū)懭氲绞聞?wù)日志中去。
在多Paxos Instance的模式下，為了提升算法執(zhí)行的性能，就必須選舉出一個副本作為Paxos算法的主節(jié)點，以避免因為每一個Paxos Instance都提出提議而陷入多個Paxos Round并存的情況，同時，Paxos會保證在Master重啟或出現(xiàn)故障而進行切換的時候，允許出現(xiàn)短暫的多個Master共存卻不影響副本之間的一致性。
在Paxos中，每一個Paxos Instance都需要進行一輪或多輪的Prepare->Promise->Propose->Accept這樣完整的二階段請求過程來完成對一個提議值的選定，為了保證正確性的前提下盡可能地提高算法運行性能，可以讓多個Instance共用一套序號分配機制，并將Prepare->Promise合并為一個階段。具體做法如下：
① 當某個副本節(jié)點通過選舉成為Master后，就會使用新分配的編號N來廣播一個Prepare消息，該Prepare消息會被所有未達成一致的Instance和目前還未開始的Instance共用。
② 當Acceptor接收到Prepare消息后，必須對多個Instance同時做出回應(yīng)，這通常可以通過將反饋信息封裝在一個數(shù)據(jù)包中來實現(xiàn)，假設(shè)最多允許K個Instance同時進行提議值的選定，那么：
-當前之多存在K個未達成一致的Instance，將這些未決的Instance各自最后接受的提議值封裝進一個數(shù)據(jù)包，并作為Promise消息返回。
-同時，判斷N是否大于當前Acceptor的highestPromisedNum值（當前已經(jīng)接受的最大的提議編號值），如果大于，那么就標記這些未決Instance和所有未來的Instance的highestPromisedNum的值為N，這樣，這些未決Instance和所有未來Instance都不能再接受任何編號小于N的提議。
③ Master對所有未決Instance和所有未來Instance分別執(zhí)行Propose->Accept階段的處理，如果Master能夠一直穩(wěn)定運行的話，那么在接下來的算法運行過程中，就不再需要進行Prepare->Promise處理了。但是，一旦Master發(fā)現(xiàn)Acceptor返回了一個Reject消息，說明集群中存在另一個Master并且試圖使用更大的提議編號發(fā)送了Prepare消息，此時，當前Master就需要重新分配新的提議編號并再次進行Prepare->Promise階段的處理。
利用上述改進的Paxos算法，在Master穩(wěn)定運行的情況下，只需要使用同一個編號來依次執(zhí)行每一個Instance的Promise->Accept階段處理。
在集群的某臺機器在宕機重啟后，為了恢復(fù)機器的狀態(tài)，最簡單的辦法就是將已記錄的所有日志重新執(zhí)行一遍，但是如果機器上的日志已經(jīng)很多，則耗時長，因此需要定期對狀態(tài)機數(shù)據(jù)做一個數(shù)據(jù)快照并將其存入磁盤，然后就可以將數(shù)據(jù)快照點之前的事務(wù)日志清除。
在恢復(fù)過程中，會出現(xiàn)磁盤未損壞和損壞兩種情況，若未損壞，則通過磁盤上保存的數(shù)據(jù)庫快照和事務(wù)日志就可以恢復(fù)到之前的某個時間點的狀態(tài)，之后再向集群中其他正常運行的副本節(jié)點索取宕機后缺失的部分數(shù)據(jù)變更記錄即可；若磁盤損壞，就笑從其他副本節(jié)點索取全部的狀態(tài)數(shù)據(jù)。
四、總結(jié)
本部分詳細介紹了Chubby系統(tǒng)，并且對Paxos在Chubby中的使用也做了較為詳細的介紹，后面我們將會介紹開源分布式系統(tǒng)Zookeeper與Paxos的聯(lián)系。本部分理論知識較強（文字較多），需要慢慢研究才能理解其中的含義，謝謝各位園友的觀看~