分布式鎖服務(wù)算法

1、分布式鎖服務(wù)-debby設(shè)計與實現(xiàn)單棟棟，趙東升，樊楷，蘇飛摘要：我們實現(xiàn)了一個分布式鎖服務(wù)系統(tǒng)，并能提供可靠的存儲服務(wù)。系統(tǒng)的接口非常簡 單，類似普通文件的接口。我們設(shè)計的重點在于系統(tǒng)的可靠性與可用性，而系統(tǒng)的性能放 在次要位置。同時我們也實現(xiàn)paxos協(xié)議，并用它為整個系統(tǒng)提供可靠容錯的系統(tǒng)日志。1背景介紹隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，出現(xiàn)了越來越多的分布式系統(tǒng)，我們利用這些系統(tǒng) 已提高現(xiàn)有系統(tǒng)的性能，可用性和穩(wěn)定性。盡管分布式系統(tǒng)的設(shè)計已日趨成熟，但要在分 布式系統(tǒng)中進行協(xié)調(diào)和信息交流仍然不是一件容易的，特別在松耦合的分布式系統(tǒng)中，所 有的信息傳遞只能通過網(wǎng)絡(luò)來完成，必須面臨網(wǎng)絡(luò)丟包、延

2、遲甚至癱瘓等等復雜的問題。 要在這樣的系統(tǒng)中都實現(xiàn)可靠的一致性協(xié)議來進行信息的交流，對于系統(tǒng)設(shè)計而言是非常 困難的，而且有一些是在應(yīng)用中沒有辦法實現(xiàn)的。因此，我們希望提供一種非侵入式的服 務(wù)來幫助分布式系統(tǒng)各個成員間的動作協(xié)調(diào)和信息交流，通過使用這一服務(wù)，各個分布式 系統(tǒng)的成員可以非常簡單的達成同步，而不需要在系統(tǒng)內(nèi)部加入復雜的協(xié)調(diào)機制。因此， 我們設(shè)計并實現(xiàn)了 debby分布式鎖服務(wù)系統(tǒng)，這是一個類似于提供全文件讀寫的分布式文 件系統(tǒng)的結(jié)構(gòu)，它設(shè)計的目標并非提供海量數(shù)據(jù)的存儲，而是用于提供具有高可靠性和高 可用性的鎖服務(wù)，同時可以方便高效的信息發(fā)布機制。為了保證debby系統(tǒng)的可靠性，我們的

3、系統(tǒng)設(shè)定了 5個服務(wù)器來組成一個debby實例，只有一個服務(wù)器用來向外提供服務(wù)， 而其它服務(wù)器都作為備份服務(wù)，用來在主服務(wù)器崩潰時繼續(xù)提供服務(wù)。為了在 5個服務(wù)器 之間提供一致性保證，我們還在底層實現(xiàn)了 Paxos協(xié)議，只要有半數(shù)以上的debby服務(wù)器 能夠正常運行，就可以提供服務(wù)。利用debby系統(tǒng)，現(xiàn)在分布式系統(tǒng)可以非常便捷的進行同步協(xié)調(diào)和信息發(fā)布。比如當多 臺服務(wù)器提供同一服務(wù)時，往往需要選擇其中一臺服務(wù)器來作為主服務(wù)器，把其他服務(wù)器 作為備份服務(wù)器，而且當主服務(wù)器崩潰時，又要能及時選出新的主服務(wù)器來提供服務(wù)。如 果沒有debby系統(tǒng)，在分布式系統(tǒng)內(nèi)部實現(xiàn)這樣的備份機制非常困難，唯一的辦

4、法或許就 是通過Paxos協(xié)議來達到一致性，而有的時候甚至 Paxos協(xié)議也無法派上用場，比如當只 有一個備份服務(wù)器的時候。然而利用的debby，實現(xiàn)上述功能變得非常簡單，只需要所有 的服務(wù)器都到debby系統(tǒng)中去獲取一個互斥鎖，然后獲得鎖的服務(wù)器就自動成為主服務(wù) 器。只要所有的服務(wù)器都遵守這一約定，就保證了系統(tǒng)中只會有一個主服務(wù)器。debby提供了非常簡單易用的信息發(fā)布機制，在獲取到互斥鎖后，服務(wù)器可以通過debby提供的分布式文件服務(wù)，在文件寫入自己的地址，其他服務(wù)器以及客戶就可以非常容易的通過讀取 debby文件內(nèi)容來得到服務(wù)器的地址。如果主服務(wù)器崩潰，debby系統(tǒng)會自動釋放互斥鎖，并

5、且通過事件機制來通知其它服務(wù)器來重新選擇主服務(wù)器。Google公司已經(jīng)實現(xiàn)了類似的分布式鎖服務(wù)系統(tǒng) Chubby，并廣泛的應(yīng)用于內(nèi)部系統(tǒng) 中，他們的經(jīng)驗表明這樣的系統(tǒng)具有非常好的可用性和可靠性，能夠給其他分布式應(yīng)用的 構(gòu)建帶來非常大的幫助。2. 系統(tǒng)設(shè)計2.1整體設(shè)計Debby結(jié)構(gòu)圖如圖所示，一個debby服務(wù)器可以同時為多個客戶端提供服務(wù)?？蛻舳送ㄟ^調(diào)用 debby的client library，和服務(wù)器通信?？蛻舳撕头?wù)器的通信建立在ICE遠程過程調(diào)用的基礎(chǔ)上。在服務(wù)器端，可以同時有多個 debby server，其中一個是leader，另外的是 replica （圖中有3個server）

6、。每個debby server上面獨立運行服務(wù)器端的程序，包括文 件管理，事件管理，Session管理等。服務(wù)器端的操作的一致性通過底層的 paxos協(xié)議來 實現(xiàn)。服務(wù)器提交給paxos的操作，都會記錄日志信息。2.2服務(wù)器設(shè)計服務(wù)器通過向客戶端提供接口，并且調(diào)用底層的paxos協(xié)議，來實現(xiàn)最終的鎖機制，并提供最終的可靠服務(wù)。2.2.1服務(wù)器的通信部分服務(wù)器通過ICE的遠程過程調(diào)用機制，來和客戶端通信。通過服務(wù)器為客戶端提供的 接口，debby的客戶端庫可以連接到服務(wù)器，并且得到一個唯一的連接標識。通過這個標 識，客戶端庫可以關(guān)閉連接，創(chuàng)建文件、目錄，刪除文件、目錄，讀寫文件，注冊事件， 刪除

7、事件，保持心跳，判斷文件的類型等等。當某些操作發(fā)生錯誤的時候，服務(wù)器端會向 客戶端拋出一個異常。2.2.2 一致性的保證服務(wù)器端通過調(diào)用底層的paxos協(xié)議，來保證服務(wù)器操作的一致性。每次服務(wù)器要進 行數(shù)據(jù)的修改操作的時候，例如創(chuàng)建文件，修改文件，刪除文件等，都要把操作提交給 paxos協(xié)議，paxos會保證每個操作都在服務(wù)器上執(zhí)行，或者都不能執(zhí)行。也就是是保證 操作的一致性。2.2.3 Session 的設(shè)計每個Session是一個客戶端和一個debby服務(wù)的關(guān)系。通過心跳機制，客戶端和服務(wù)器 保持聯(lián)系。在每個心跳到來的時候，服務(wù)器會把發(fā)生的事件返回給客戶端。224文件、目錄的設(shè)計對于每個S

8、ession，debby提供一個簡單的文件系統(tǒng)接口，文件和路徑的格式類似于 UNIX，例如/ls/foo/dir/file。文件系統(tǒng)向外提供通常的文件系統(tǒng)服務(wù)，例如文件、目錄的 創(chuàng)建，文件、目錄的修改、刪除等。debby應(yīng)該向客戶端提供對臨時文件進行操作的服 務(wù)。臨時文件被客戶端創(chuàng)建，在Session失效的時候，臨時文件應(yīng)該被刪除。 為了方便，以及提高性能，debby的文件和目錄都放在內(nèi)存中，定期進行snapshot，將文 件系統(tǒng)的內(nèi)容flush到磁盤。在系統(tǒng)恢復的時候，會根據(jù)磁盤的內(nèi)容恢復文件系統(tǒng)。2.2.5事件機制的設(shè)計對于每個Session，debby提供一個事件管理器，事件管理器會記錄

9、客戶端已經(jīng)注冊的 事件、和已經(jīng)發(fā)生的事件。對于已經(jīng)發(fā)生的事件，服務(wù)器會在每個keepAlive的遠程過程調(diào)用的時候，將客戶訂閱的事件捎帶返回，同時在服務(wù)器端刪除這些已經(jīng)發(fā)生的事件。2.3客戶端設(shè)計利用服務(wù)器端提供的接口，我們通過客戶端來最終實現(xiàn)鎖機制，并向外提供服務(wù)。我們希望客戶端向外提供盡量易于理解的接口，從而可以讓用戶可以方便的使用debby系統(tǒng)的服務(wù)?？蛻舳送ㄟ^ICE庫來和服務(wù)器進行遠程調(diào)用，并且通過定期的keepAlive信息保持和服務(wù)器的會話。每次客戶端與服務(wù)器建立會話后，都得到一個獨一無二的句柄，并且以后所 有的操作都通過這一句柄來完成，從而可以在每次操作時判斷用戶的身份。盡管在應(yīng)

10、用程 序中，可以有多個對象使用同一個客戶端的服務(wù)，但在服務(wù)器看來，一個客戶端只對應(yīng)唯 一的用戶?？蛻舳讼蛲馓峁┑腁PI可以分為兩個部分，一部分是實現(xiàn)類似于普通文件系統(tǒng)的目錄操 作，另外一部分則用來提供全文讀寫、鎖服務(wù)以及事件注冊。在提供目錄操作的部分，我們的接口與普通文件系統(tǒng)非常類似，具體的操作包括 create(),remove(),mkdir(),exist(),isdir(),list()。通過這些操作，用戶可以修改系統(tǒng)目錄結(jié) 構(gòu)，創(chuàng)建和刪除文件和目錄。與普通的文件系統(tǒng)不同的是，我們在create接口中提供了是否創(chuàng)建臨時文件的選項，如果創(chuàng)建的是臨時文件，那么當這個客戶端與服務(wù)器失去連接

11、后，debby服務(wù)器會自動刪除臨時文件。這可以作為一種信息發(fā)布的方式，也是我們實現(xiàn) 鎖機制利用的底層特性。我們提供了 read()和write()操作來進行全文讀寫，即一次讀或者寫整個文件的內(nèi)容。之 所以這樣設(shè)計，是因為debby中的文件其主要作用是為了提供一種信息發(fā)布的機制，而不 是作為大規(guī)模數(shù)據(jù)的存儲。為了防止用戶的誤用來對debby的整體服務(wù)性能造成影響，比如存儲非常大的文件，我們對文件的大小進行了限制，目前暫定為1M。這樣規(guī)模的文件，我們可以很方便的只提供全讀和全寫的操作，由用戶自己來確定文件內(nèi)容的格式。我 們提供了 lock()和release()操作來提供鎖服務(wù)，當多個用戶想要獲取

12、某個資源時，應(yīng)當首 先獲取對那個資源的鎖，才可以安全的使用資源。當完成對資源的使用時，用戶應(yīng)當調(diào)用 release()操作來是釋放操作，從而使得其它用戶可以使用資源。因為Chubby的使用數(shù)據(jù)表明幾乎所有用戶使用的都是互斥鎖而非共享鎖，因此目前我們只提供互斥鎖服務(wù)。我們還提供了事件機制，通過事件機制，用戶只需要在某個事件上注冊好回調(diào)，當事 件發(fā)生時，就會自動調(diào)用用戶注冊的回調(diào)函數(shù)。通過這一機制，用戶不需要通過輪詢來獲 得信息，大大減輕了服務(wù)器的負擔，使其具有更好的可擴展性。目前我們提供的事件包括 Even tCreated, Even tRemoved, Even tCha nged. Eve

13、n tLockCha nged. Even tArbitrary五種。前三個事件分別代表目錄或文件的創(chuàng)建、刪除和改變，這里目錄的內(nèi)容改變指的是目 錄內(nèi)文件的創(chuàng)建或刪除。第四個事件是指在某個路徑上的鎖發(fā)生改變，包括鎖被獲取或釋 放。第五個事件則是指在一個路徑上的所有事件，包括創(chuàng)建、刪除、改變以及鎖的改變。2.4 snapshot機制設(shè)計Debby的paxos框架保證了各個replica存放數(shù)據(jù)的一致性。也支持備份在 crush掉之后 恢復。到目前為止，所有的故障恢復均基于log，log存放在穩(wěn)定存儲器（硬盤）中。但由 此引發(fā)了新問題：隨著系統(tǒng)運行，日志將會越來越多。這有兩方面問題：log的存儲需

14、要無限量的磁盤空間，并且更糟的是，這也可能會導致恢復時間越來越長。 這里介紹的snapshot （快照）機制想法很簡單。就是要將文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)直接序列 化到磁盤上，這樣之前的日志就不再需要了。于是可通知paxos部分將log刪除。當然，paxos部分并不知道任何有關(guān)的數(shù)據(jù)結(jié)構(gòu)，因此，即plication進程必須負責snapshot的執(zhí)行。debby提供了 snapshot機制，允許客戶端應(yīng)用程序通知文件系統(tǒng)執(zhí)行 snpsoht操作。用戶 應(yīng)用程序可在任何時間發(fā)起snapshot命令。當snapshot操作完成，snapshot部分應(yīng)通知 paxos部分以刪除其過時的snap shot存儲和

15、log。當某臺服務(wù)器crush掉之后恢復時， snapshot類將負責為其從磁盤中導入最新的文件數(shù)據(jù)結(jié)構(gòu)，然后重放截斷日志，以重建 服務(wù)器的服務(wù)環(huán)境。當然snapshot機制也增加了一些復雜性：在實現(xiàn)snapshot機制之前，crush掉的服務(wù)器在 恢復時只需從其他機器獲得最近的log即可進行更新。而實現(xiàn)snapshot機制之后，如需保 持狀態(tài)的一致性，得包括進最近的log和snapshot復本。2.5容錯日志設(shè)計Debby系統(tǒng)的主要設(shè)計目標是高可靠性與高可用性，這主要依靠多臺服務(wù)器一起運行 來實現(xiàn)。一臺機器壞悼都有備份機接替工作，但如果保證系統(tǒng)中的機器數(shù)據(jù)的一致性是一 個非常大的問題。我們主

16、要用paxos一致性協(xié)議,它保證每一時刻，系統(tǒng)中的大部分機 器的狀態(tài)都是一致的，狀態(tài)不一致的機器可以通過一定方法恢復到一致的狀態(tài)。paxos保證系統(tǒng)的一致性主要靠容錯日志，系統(tǒng)的每次操作paxos都會把這個操作記錄在日志中，通過這個日志就能過從錯誤中恢復。我們的系統(tǒng)中，要寫入日志的值就可要對 數(shù)據(jù)庫進行操作的值。基本的paxos主要分為三個步驟4:一. 有多少機器中通過一些算法選出一個leader二. 選出的leader可以提交決議到系統(tǒng)中，leader發(fā)送消息給其它機器，其它機器回 復 leader三. 當 leader收至半數(shù)以上的應(yīng)答，就發(fā)消息給其它機器，表明可以記日志。 基礎(chǔ)的paxo

17、s協(xié)議沒有對那個狀態(tài)不一致的系統(tǒng)進行處理，在我們的容錯日志設(shè)計中，有第一與第二步中間加了一步準備階段。當leader被選出來已后，向其它機器發(fā)一個消 息，表明自己是leader，并把當前的系統(tǒng)狀態(tài)發(fā)給大家。其它機器根據(jù)leader發(fā)過的狀態(tài)信息，判斷自己的信息是不是最新，返回給leader自己的狀態(tài)，leader根據(jù)這些信息來決 定自己是否需要進行catch up操作，其它機器可以與leader通信，更新狀態(tài)。在基本的paxos中，如果每臺機器都給其它機器返回信息，第三步可以省略?；镜?paxos做每一次決議都要選leader，比較費時，我們通過給leader一個租約時間，在這個 時間中，其

18、它機器保證不會同意選出新的leader 0 leader在租約時間內(nèi)可經(jīng)續(xù)租約，從而 保證leader長間的成為leader。下圖是我們使用paxos對容錯日志系統(tǒng)的設(shè)計。3. 系統(tǒng)實現(xiàn)3.1服務(wù)器端實現(xiàn)在服務(wù)器端實現(xiàn)了向客戶端提供的接口，并且調(diào)用底層的paxos協(xié)議的接口，來實現(xiàn)最終的鎖機制，并提供最終的可靠服務(wù)。debby的服務(wù)器實現(xiàn)了 Session管理，心跳機制，文件、目錄的管理，事件管理，以及和客戶端、paxos協(xié)議的通信。3.1.1Session機制的實現(xiàn)對于客戶端和服務(wù)器建立的每一個連接，服務(wù)器都會保存一個handle，Session的pair，當客戶端顯示結(jié)束連接，或者沒有心跳

19、的時候，服務(wù)器會刪除對應(yīng)的Session。每個Session都會保存對應(yīng)的臨時文件信息，以及相應(yīng)的注冊事件信息。注冊的事件發(fā)生 時，Session會在心跳的基礎(chǔ)上，將事件返回，通知客戶端。3.1.2文件、目錄的實現(xiàn)考慮到實現(xiàn)的方便和高效，debby的文件和目錄是放在內(nèi)存中的。debby的文件系統(tǒng)分 為常規(guī)的文件系統(tǒng)，和臨時的文件系統(tǒng)。常規(guī)文件系統(tǒng)和臨時文件系統(tǒng)是分開實現(xiàn)的，他 們的命名空間也是相互獨立的。在常規(guī)文件目錄中，對于文件和目錄的管理，提供了通常意義下的操作，包括文件、目錄 的創(chuàng)建，文件、目錄的修改、刪除等。系統(tǒng)實現(xiàn)了兩個版本的文件、目錄系統(tǒng)。第一個是 用STL的map實現(xiàn)，整個文件系

20、統(tǒng)只有一個 map，map的每一個元素是 路徑，debby文 件的pair。這個實現(xiàn)版本效率比較差，并且操作起來非常不方便，實現(xiàn)起來比較麻煩。 考慮到文件系統(tǒng)的組織結(jié)構(gòu)，debby提供了文件系統(tǒng)的第二個實現(xiàn)版本，用樹來實現(xiàn)。在 開源的tree.hh基礎(chǔ)上，debby用模板實現(xiàn)了通用的內(nèi)存目錄 MemDir。通過MemDir，用戶 可以定義自己的in ode類型，在in ode中，用戶應(yīng)該提供相應(yīng)的方法，這些方法在 MemDir 中被調(diào)用。對于臨時文件系統(tǒng)，系統(tǒng)維護了一個從 handle到路徑名稱的map，當一個Session失效的 時候，系統(tǒng)會釋放一個handle所對應(yīng)的文件。3.1.3事件機

21、制的實現(xiàn)debby維護了一個事件管理器，事件管理器會記錄客戶端已經(jīng)注冊的事件、和已經(jīng)發(fā)生 的事件。對于已注冊的事件，系統(tǒng)維護一個事件到handle列表的map，如果某一個事件發(fā)生了，則會通知列表里面記錄的每一個連接。3.2客戶端實現(xiàn)當用戶啟動客戶端時，就會啟動一個心跳線程，專門用于向debby服務(wù)器發(fā)送keepAlive信息以維持會話。在客戶端的大部分操作都通過服務(wù)器提供的遠程調(diào)用服務(wù)來實現(xiàn)，比如 文件和目錄的創(chuàng)建、刪除等操作。對于互斥鎖的獲取和釋放操作，debby并不提供直接的支持，而是通過客戶端通過創(chuàng)建 和刪除臨時文件來完成。比如當客戶獲取"/ls/printer"的互

22、斥鎖，客戶端就會試圖創(chuàng)建"/Is/ printer.lck"文件，如果這個文件已經(jīng)存在，說明互斥鎖已經(jīng)被其他用戶獲得，服務(wù)器向 客戶端拋出異常，客戶端獲取異常后返回失敗。如果成功了創(chuàng)建了那個文件，就表明客戶 成功獲取了該互斥鎖。當用戶要釋放鎖時，客戶端就會刪除"/ls/printer.lck"文件，來表明用戶已經(jīng)釋放鎖。為了防止這樣的文件和用戶的普通文件重名，我們規(guī)定用戶不能創(chuàng)建 以""結(jié)尾的文件名。對于鎖服務(wù)，我們最需要處理的問題是當客戶端崩潰時，需要自動 的釋放鎖，臨時文件的機制使得我們可以實現(xiàn)這個功能，因為如果客戶端和服務(wù)器失去

23、連 接，服務(wù)器就會刪除用于所服務(wù)的臨時文件，也就是釋放了該用戶擁有的所有鎖。在實現(xiàn)事件機制時，盡管客戶可以在事件上注冊回調(diào)，但服務(wù)器并不需要管理回調(diào)函 數(shù)，只是通知客戶端事件的發(fā)生，對回調(diào)的管理有客戶端完成。用戶可以在一個路徑的一 個事件上注冊多個回調(diào)，只有在注冊第一個回調(diào)是需要由客戶端向服務(wù)器注冊，后續(xù)的操 作就完全由客戶端來完成。當客戶端收到一個事件時，它會調(diào)用注冊到這個事件的所有回 調(diào)。用戶也可以取消在一個路徑上注冊的所有回調(diào)?；卣{(diào)的實現(xiàn)，我們通過一個類Callback來實現(xiàn)，這個類有一個純虛函數(shù)run()，用戶要 定義自己的回調(diào)時，需要首先創(chuàng)建一個 Callback的子類，并實現(xiàn)其ru

24、n()函數(shù)作為回調(diào)函 數(shù)。當客戶端要收到事件時，對于每一個注冊的Callback，都會創(chuàng)建一個線程來調(diào)用其run()函數(shù)。在用戶的子類中，可以把任何用戶的回調(diào)函數(shù)需要的數(shù)據(jù)作為其Callback子類的成員，從而使得其回調(diào)函數(shù)可以實現(xiàn)幾乎任意強大的功能?？蛻舳肆硗庖粋€需要處理的問題是當debby服務(wù)器發(fā)生改變時如何能轉(zhuǎn)換到適當?shù)姆?wù) 器，并且能夠處理由于改變服務(wù)器導致的一段時間內(nèi)服務(wù)失效問題。我們通過ICE的多終端功能和重試功能來解決這個問題。當ICE進行初始化的時候，我們會把debby的5個服務(wù) 器地址都傳給ICE，這樣ICE會自動嘗試所有5個服務(wù)器，只要有一個服務(wù)器提供服務(wù)，就 可以建立其連

25、接并進行遠程調(diào)用。因此我們只要保證debby服務(wù)器端同一時間內(nèi)只有一個服務(wù)器在提供服務(wù)，就能夠保證debby客戶端能夠找到master。但在改變服務(wù)器期間，回 出現(xiàn)沒有任何一個服務(wù)器提供服務(wù)的情況，此時我們需要利用ICE的重試機制，即我們可以給ICE提供一個重試時間的序列，比如(1 3 5)表示如果ICE客戶端無法與服務(wù)器建立連 接，會在接下來的第1秒，第3秒和第5秒進行重試，只要在重試中能連上服務(wù)器就可正常 工作，否則認為連接失效拋出異常。我們也給我們的客戶端ICE提供了重試時間序列，為(10 30 60)，這樣只要服務(wù)器端能夠在60秒內(nèi)恢復，我們就可以向用戶提供連續(xù)的服務(wù)。3.3snaps

26、hot機制實現(xiàn)對于Google公司的Chubby，其文件系統(tǒng)以數(shù)據(jù)庫的形式采用 Berkeley DB實現(xiàn)。 Berkeley DB采用B-樹結(jié)構(gòu)，可以提供高效率的Key-value查找。在我們的版本里進一步 做了簡化。文件系統(tǒng)采用自定義的tree實現(xiàn)，于是在序列化時只需對 MemDir中的文件樹 做遍歷，記下相應(yīng)節(jié)點(INode)的信息和其父節(jié)點即可。由于 Debby系統(tǒng)采用C+編 寫，standard library中未提供序列化功能，只能自己編碼完成(考慮過用boost庫實現(xiàn)，由于使用起來不方便而作罷)。Snapshot類主要實現(xiàn)兩個函數(shù)：public static void seria

27、lize(MemDir& md);public MemDir& void Un serialize();其中，屬性DIR_PATH為序列化后的文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的存放路徑； Serialize方法將 傳入的文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)MemDir序列化后存入路徑為DIR_PATH的文件中，Un serialize 方法在服務(wù)器恢復時調(diào)用，其從路徑為 DIR_PATH的文件中恢復數(shù)據(jù)結(jié)構(gòu)MemDir并返回 之。3.4容錯日志實現(xiàn)我們主要實現(xiàn)了一個paxos框架，用paxos框架來產(chǎn)生容錯日志。對2.5小節(jié)的設(shè)計，我 們的機器共有三種角色，LOOKING表示當前機器正在尋找leader。LEAD

28、ERG表示當前 機器為leader。 FOLLOWER表示當前機器為非leader。 paxos過程如下：1. 通過leader選舉算法，得到一個leader。每臺機器要參與leader的選舉，必須提交一 個veiw號，這個號要保證是遞增的。在我們的實現(xiàn)中，每臺機器即可以推舉自己當 leader，也可以推舉別的機器當leader。所以在我們的實現(xiàn)中，每臺機器都有自己的編號 例如0N-1,當前被達成一致的view對應(yīng)的leader就是view%N對應(yīng)的機器，如果該機器 沒有起啟動，則再次選leader，如何得到leader沒有啟動，可以通過心跳機制來保證。在 我們的實現(xiàn)中，當一臺機器被選成lea

29、der，馬上就得給其它機器發(fā)心跳，而leader也是通 過心跳來續(xù)約租約時間的。這里所涉及到的消息包括viewchange消息，與heartbeat消息2. 當一臺機器被選為leader后，向大家發(fā)送一個準備信息，包括當前的 view與系統(tǒng)的狀態(tài)，向大家來同步。其它機器對這個消息進行應(yīng)答并通過自己的狀態(tài)信息。leader匯總這些信息，判斷自己的狀態(tài)是否為最新，如果不是最新，剛向收到回復消息的機器中選擇一 個狀態(tài)最新的機器，向那臺機器請求數(shù)據(jù)，以恢復來最新狀態(tài)。系統(tǒng)中必定有一臺機器的 狀態(tài)是最新的，這個可以由paxos的性質(zhì)來保證。其它服務(wù)器如果狀態(tài)不是最近，可以向 leader發(fā)請求來恢復最新

30、狀態(tài)。這里所涉及到的消息包括prepare消息，prepareok消息，catch up 消息3. 當?shù)?步完成時，leader狀態(tài)是最新的，并且系統(tǒng)中的大部分機器的狀態(tài)都是最新的，即一半以上的機器狀態(tài)一致。leader就可以響應(yīng)其它程序向paxos系統(tǒng)提交決議，其 它機器收到?jīng)Q議并向leader與其它機器應(yīng)答消息，當應(yīng)答的消息過半時，表示協(xié)議已經(jīng)達 成，每臺機器把這協(xié)議記錄在本地的日志中。如果協(xié)議沒有達成，leader可以自動重新提交協(xié)議，直到達成協(xié)議，也可直接返回協(xié)議沒有答成給調(diào)用者，由調(diào)用都重新提交協(xié)議，在paxos系統(tǒng)中，這次提交的協(xié)議號與上次失敗的協(xié)議號是相同的。這里涉及到的消息包

31、括proposal消息accept消息在系統(tǒng)的運行過程中，如果有一臺宕掉的機器起來，它首先通過一定時間偵聽當前 leader發(fā)送的心跳消息，如果沒有收到心跳消息，由進入選leader狀態(tài)。如果收到消息，向leader更新自己的狀態(tài)信息到最新。在一個已有l(wèi)eader的系統(tǒng)中，如果有別的新的機器 發(fā)選leader的消息，大家都會把它拒絕，當新的機器收到心跳消息時，自動轉(zhuǎn)變角色。4. 實驗4.1paxos 實驗我們的實驗環(huán)境主要是在單臺機器下(PM1.5GHZ 512MB)，通過多個終端來模擬多臺 機器對paxos的系統(tǒng)測試實驗。在針對paxos系統(tǒng)的一致性進行測試實驗，我們主要采用 同步提交的方法

32、，即下一次提交的協(xié)議必需等上一次提交后并且已經(jīng)得到結(jié)果了才能提 交。這些實驗我們都默認系統(tǒng)已經(jīng)把leader選出，所有的決議都leader提交。在實驗中 leader提交的策略如下：如果一次提交，再1秒鐘內(nèi)paxos系統(tǒng)還沒有對該協(xié)議達成一 致，則返回提交失敗而paxos系統(tǒng)對本次操作不記日志，否則則提交成功，paxos對這次操作記下日志。paxos記日志的方式是把提交的內(nèi)容與協(xié)議號寫入磁盤。系統(tǒng)中的通過主 要用多播實現(xiàn)，系統(tǒng)之間的catch up通過單點tcp連接進行通訊。我們總共做了四組實驗，在這四組實驗中也可以分成兩組，一組用3個終端，另一組用5個終端完成。3個終端表示我們paxos系統(tǒng)

33、中有3臺機器中，我們模擬系統(tǒng)中只剩2臺機 器，與3臺機器都存在的情況。5個終端的實驗中模擬了 3臺機器與5臺機器的情況。表一 是3臺機器的模擬結(jié)果，表二，是5臺機器的模擬結(jié)果。在實驗的結(jié)果中，我們可以看出，系統(tǒng)中機器數(shù)比較少時，達成協(xié)議的速度比較快。 在同一個系統(tǒng)中，也就是系統(tǒng)中的機器數(shù)量一定時，宕掉的機器越多出現(xiàn)提交失敗的比例 也越高，而整個系統(tǒng)特別在有許多機器的，其運行速度也越慢。表一 3個終端模擬1臺機器宕機與沒有機器宕機的情況機器數(shù)（3臺）運行時阿提交傾數(shù) （50D0fg 交）平均每秒 提交數(shù)§100 失贖率只運行2臺99.133050.7 次/ 秒0.02795,1260101.8564運行3臺126.893038Q5 次0.013128.1541130.1071表二5個終端模擬2臺機器宕機與沒有機器宕機的情況機