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