閱讀本文前最好能先閱讀參考文獻(xiàn)[2]。最近在寫畢業(yè)論文，導(dǎo)致這邊學(xué)習(xí)筆記也寫得很生硬........ 大家輕拍。文章為本人對paxos算法(basic paxos)的理解，水平有限難免有理解不到位的地方，歡迎批評。      

一、簡介

1.1Paxos算法處理的問題

    Paxos 算法解決的問題是一個分布式系統(tǒng)如何就某個值(決議)達(dá)成一致。一個典型的場景是，在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行"一致性算法"以保證每個節(jié)點(diǎn)看到的指令一致。節(jié)點(diǎn)通信存在兩種模型：共享內(nèi)存（Shared memory）和消息傳遞（Messages passing）。Paxos 算法就是一種基于消息傳遞模型的一致性算法[1]。

1.2算法簡介及一致性問題場景

    為描述 Paxos 算法，Lamport 虛擬了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人愿意將自己的全部時間和精力放在這種事情上。所以無論是議員，議長或者傳遞紙條的服務(wù)員都不能承諾別人需要時一定會出現(xiàn)，也無法承諾批準(zhǔn)決議或者傳遞消息的時間。但是這里假設(shè)沒有拜占庭將軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現(xiàn)錯誤的消息）；只要等待足夠的時間，消息就會被傳到。另外，Paxos 島上的議員是不會反對其他議員提出的決議的[1]。

    對應(yīng)于分布式系統(tǒng)，議員對應(yīng)于各個節(jié)點(diǎn)，制定的法律對應(yīng)于系統(tǒng)的狀態(tài)。各個節(jié)點(diǎn)需要進(jìn)入一個一致的狀態(tài)，例如在獨(dú)立Cache的對稱多處理器系統(tǒng)中，各個處理器讀內(nèi)存的某個字節(jié)時，必須讀到同樣的一個值，否則系統(tǒng)就違背了一致性的要求。一致性要求對應(yīng)于法律條文只能有一個版本。議員和服務(wù)員的不確定性對應(yīng)于節(jié)點(diǎn)和消息傳遞通道的不可靠性[1]。

    場景一：C/S模式的冗余備份的系統(tǒng)，C={C1,C2,C3,........,Cn}代表n個客戶端，S={S1,S2,S3,........,Sm}代表m個服務(wù)器。在這樣的冗余系統(tǒng)中要完成這樣的任務(wù)：讓任何一個Cx提出的請求(提交的數(shù)據(jù))，能在這m個服務(wù)器上都執(zhí)行(保存)一遍，最終所有的服務(wù)器達(dá)到一個一致的狀態(tài)（也就是說每個server相當(dāng)于一個“replica”，而外部看來似乎只有一個server提夠服務(wù)，這樣設(shè)計(jì)主要是為了容災(zāi)考慮）。這時問題就產(chǎn)生了，由于client與server、server與server之間是用網(wǎng)絡(luò)連接的，則由網(wǎng)絡(luò)協(xié)議帶來的不可靠、不確定性將會影響這m個server到達(dá)一個一致狀態(tài)。例如：C1、C2先后提出請求，C1要求更新value1，C2要求刪除value1。由于網(wǎng)絡(luò)的不確定，這兩個請求到達(dá)server的順序可能是S1（requestC1，requestC2），S2（requestC2、requestC1）.....等等，使得操作序列在m個服務(wù)器可能各不相同，如果S中的每一個server執(zhí)行了不同的合法操作序列，將會導(dǎo)致整個系統(tǒng)的不一致問題，所以一致性算法的任務(wù)就是保證S中每個處于正常工作的server都將執(zhí)行一個相同的操作序列，如（requestC1、requestC2）。C/S模式的冗余備份 系統(tǒng)常常有兩種形式：1.每一個client和所有的server連接（如圖1）。2.所有的client和一個server連接（相當(dāng)于server中的leader），再由這個leader與其他冗余server連接。不管是那種形式都會受到網(wǎng)絡(luò)不確定性的影響從而產(chǎn)生操作序列不一致問題。

    場景二：系統(tǒng)中各節(jié)點(diǎn)是對等關(guān)系，互為client/server,當(dāng)一節(jié)點(diǎn)發(fā)生改變時，其他所有節(jié)點(diǎn)也要發(fā)生相同的改變。比如在ATC（空中交通管制系統(tǒng)）中有五臺供管制員使用的席位(即五臺主機(jī))，在實(shí)際應(yīng)用中會遇到這樣的情況：管制員G1在席位1對參數(shù)value1做相應(yīng)的操作，而幾乎同時管制員G2在席位2上也對value1做操作。由于網(wǎng)絡(luò)傳輸?shù)牟淮_定性可能會導(dǎo)致這五臺主機(jī)最終的顯示結(jié)果不盡相同，產(chǎn)生不一致性的問題。paxos算法就是用來解決這類問題。

二、算法詳解

2.1一致性算法

    一個一致性算法需要保證：一次選舉中只批準(zhǔn)一個決議(value)，只有被提出(proposed)的決議才能被批準(zhǔn)，只有已經(jīng)被批準(zhǔn)的決議才能被學(xué)習(xí)(即可以執(zhí)行或保存這個決定的內(nèi)容)。Paxos算法為了完成這樣的選舉過程將參與者分為：proposers，acceptors，和 learners。proposers 提出決議，acceptors 批準(zhǔn)決議，learners“學(xué)習(xí)”決議。劃分為三類角色后，一致性算法的要求可以更精確的表述為：

1.決議（value）只有在被 proposers 提出后才能批準(zhǔn)（未經(jīng)批準(zhǔn)的決議稱為“提案（proposal）”）；

2.在一次 Paxos 算法的執(zhí)行實(shí)例中，只批準(zhǔn)一個 Value；

3.learners 只能獲得被批準(zhǔn)（chosen）的 Value。

    這樣的表述看似簡單，但實(shí)際的證明過程還是很復(fù)雜的，而在三條中最為重要的是第二條作者Lamport在Paxos made simple[2]中花大量的篇幅來加強(qiáng)第二條的約束，從而總結(jié)出一個paxos實(shí)例的兩個階段及三類角色各自的工作。如何保證在一個paxos中只選出一個value的推導(dǎo)過程建議閱讀原文或Fastpaxos[3]的The Basic Algorithm章節(jié)尤其在注意Picking a Value in Phase 2a，在本學(xué)習(xí)筆記后續(xù)文章中有較為工程化的描述，可能比較好理解一些。

    分布式領(lǐng)域的許多算法由于先決條件過于苛刻導(dǎo)致工程實(shí)現(xiàn)上的困難，相比較而言Paxos算法的先決條件要弱很多。as follow：

（1）.Paxos算法應(yīng)當(dāng)執(zhí)行在一個可靠的通訊環(huán)境中，即在異步通訊過程中不會出現(xiàn)被篡改的情況(non-Byzantine model)，但允許發(fā)送的數(shù)據(jù)出現(xiàn)丟失、延遲、重復(fù)的情況。則個角色可工作在任意速度、允許停止和重啟的錯誤?？芍貑?restart)性質(zhì)就要求各角色"隨時"保存自己的當(dāng)前狀態(tài)，換句話說就是要把狀態(tài)寫入硬盤，所以在Paxos算法學(xué)習(xí)筆記（一）中提到的diskles paxos讓我很疑惑，有時間在研究。

（2）.任何一個算法的運(yùn)行實(shí)體不會出現(xiàn)拜占庭將軍問題[4]，可以簡單的理解為結(jié)點(diǎn)群的決議序列沒有受到病毒、黑客的影響。

2.2算法的內(nèi)容

    一個Paxos算法執(zhí)行實(shí)例只能批準(zhǔn)一個決議(value)，以下描述的算法內(nèi)容都是指在一個paxos實(shí)例中。

    可以這樣理解：現(xiàn)在有C1、C2要提出保存key1、key2兩數(shù)據(jù)的請求，他們分別向server結(jié)點(diǎn)群發(fā)出請求，server結(jié)點(diǎn)群可以由一個leader(也可以是結(jié)點(diǎn)群中每一個server)負(fù)責(zé)處理這兩個請求然后發(fā)起兩個paxos執(zhí)行實(shí)例，也就是提出兩個不同的決議(value)，待acceptors進(jìn)行表決。這兩個paxos實(shí)例是相互獨(dú)立的，它們分別獨(dú)立的執(zhí)行paxos過程(round)的兩個階段，最終兩個實(shí)例得到通過后，在server結(jié)點(diǎn)群的每一臺server上按一定順序保存key1、key2(不一定是按請求到達(dá)的順序)。

    理解一個paxos實(shí)例只能批準(zhǔn)一個決議是很重要的，因?yàn)檫@點(diǎn)非常容易和paxos算法階段一的“picking a value”[3]混淆，在看論文的時候也很容易出現(xiàn)理解偏差。

    當(dāng)一個請求到來后，由proposer或leader發(fā)起新的paxos執(zhí)行實(shí)例，這時proposer會選擇一個“新”的實(shí)例id(instance id)用于和別的決議(value)進(jìn)行區(qū)分，使得這個提案能獨(dú)立的進(jìn)行paxos round。前面提到的“新”實(shí)例id，之所以新字用引號是因?yàn)檫@個實(shí)例id可能已經(jīng)被別的proposer使用。如果這個id已經(jīng)被別的proposer使用，那么一個paxos實(shí)例中就有兩個value進(jìn)行表決，這與一致性算法的第二條要求有沖突，為了保證一致性算法的性質(zhì)，paxos算法的第一階段才有了一個叫“picking a value”的過程。對于同一個paxos實(shí)例來說執(zhí)行多少次都只會“pick”相同的value，以證第二條要求。

2.2.1通過一個決議

    新的paxos執(zhí)行實(shí)例發(fā)起后，接下來就是執(zhí)行paxos算法，算法每執(zhí)行一遍叫一個paxos過程(paoxs round)，一個value的批準(zhǔn)可能經(jīng)歷多個paxos過程。下面是paxos算法的具體過程，或者說是一個paxos round的執(zhí)行過程。

proposer 提出一個提案前，首先要和足以形成多數(shù)派的 acceptors 進(jìn)行通信，獲得他們進(jìn)行的最近一次批準(zhǔn)活動的編號（prepare 過程），之后根據(jù)回收的信息決定這次提案的 value，形成提案開始投票。當(dāng)獲得多數(shù) acceptors 批準(zhǔn)后，提案獲得通過，由 proposer 將這個消息告知 learner。這個簡略的過程經(jīng)過進(jìn)一步細(xì)化后就形成了 Paxos 算法：

通過一個決議分為兩個階段[1]：

Phase1.準(zhǔn)備階段：

    (a)proposer 選擇一個提案編號 n 并將 prepare 請求發(fā)送給 acceptors 中的一個多數(shù)派；

    (b)acceptor 收到 prepare 消息后，如果提案的編號大于它已經(jīng)回復(fù)的所有 prepare 消息，則 acceptor 將自己上次的批準(zhǔn)回復(fù)給 proposer，         并承諾不再批準(zhǔn)小于 n 的提案；

Phase2. 批準(zhǔn)階段：

    (a)當(dāng)一個 proposor 收到了多數(shù) acceptors 對 prepare 的回復(fù)后，就進(jìn)入批準(zhǔn)階段。它要向回復(fù) prepare 請求的acceptors 發(fā)送 accept 請         求，包括編號 n 和根據(jù) P2c 決定的 value（如果根據(jù) P2c 沒有決定 value，那么它可以自由決定 value）。

    (b)在不違背自己向其他 proposer 的承諾的前提下，acceptor 收到 accept 請求后即批準(zhǔn)這個請求。

這個過程在任何時候中斷都可以保證正確性。例如如果一個 proposer 發(fā)現(xiàn)已經(jīng)有其他 proposers 提出了編號更高的提案，則有必要中斷這個過程。因此為了優(yōu)化，在上述 prepare 過程中，如果一個 acceptor 發(fā)現(xiàn)存在一個更高編號的"草案"，則需要通知 proposer，提醒其中斷這次提案。

兩階段的消息傳遞過程可由下圖表示[5]：

Message flow: Basic Paxos (one instance, one successful round) Client Proposer Acceptor Learner | | | | | | | X------->| | | | | | Request | X------->|->|->| | | Prepare(N) | |<-------X--X--X | | Promise(N,{Va,Vb,Vc}) | X------->|->|->| | | Accept!(N,Vn) | |<-------X--X--X----->|->| Accepted(N,Vn) |<-------------------------------X--X Response | | | | | | | 

Message flow: Basic Paxos

(one instance, one successful round)

 Client   Proposer      Acceptor     Learner

   |         |          |  |  |       |  |

   X-------->|          |  |  |       |  |  Request

   |         X--------->|->|->|       |  |  Prepare(N)

   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})

   |         X--------->|->|->|       |  |  Accept!(N,Vn)

   |         |<---------X--X--X------>|->|  Accepted(N,Vn)

   |<---------------------------------X--X  Response

   |         |          |  |  |       |  |

    以上引用是Paxos made simple[2]“Choosing a Value”的文字描述，過程看起來是很簡單的，但實(shí)現(xiàn)時有很多細(xì)節(jié)需要注意，而更詳細(xì)的描述將放在本學(xué)習(xí)筆記的下一篇《Paxos算法的工程描述》，屆時將給出各個角色在這兩階段中的工作及涉及的變量。

2.2.2學(xué)習(xí)一個決議

    Paxos made simple中同樣用很大的篇幅來描述如何"Learning a Chosen Value"，并強(qiáng)調(diào)Learners學(xué)習(xí)過程中可能出現(xiàn)決議的“gap”(詳情參照原文)。實(shí)際上可以這樣理解：現(xiàn)在有兩個已經(jīng)執(zhí)行完上面P2b過程的value1和value2，即這兩個決議已經(jīng)被批準(zhǔn)(accepted)，接下來系統(tǒng)中有五個learner要學(xué)習(xí)這兩個決議，由于learners之間還是基于網(wǎng)絡(luò)的通訊，則value1和value2到達(dá)learners的順序可能是不一樣的，存在不一致的問題。怎么解決這個問題？怎么區(qū)分value1和value2的先后？可以回想一下，這兩個決議是分別由兩個不同paxos實(shí)例選舉得出，那么就可以使用實(shí)例id(instance id)來區(qū)分兩個決議的先后。規(guī)定learner必須按照實(shí)例id從小到大依次學(xué)習(xí)各決議，從而保證決議序列在所有l(wèi)earner上一致的，每一個paxos實(shí)例只能批準(zhǔn)一個決議，這樣操作系列的一致就不言而喻。所以工程實(shí)現(xiàn)時如何設(shè)計(jì)這個單增的實(shí)例id(instance id)是一個關(guān)鍵點(diǎn)！假定value1的instance id是100，value2是101，那么learners必須學(xué)習(xí)完value1之后才能學(xué)習(xí)value2，即使value2先于value1被大部分accept通過，也不能被learners學(xué)習(xí)。

    再看看learner學(xué)習(xí)過程中的“gap”是如何形成的，在2F+1個結(jié)點(diǎn)的系統(tǒng)中，paxos算法允許最多F個結(jié)點(diǎn)同時出現(xiàn)故障。假設(shè)系統(tǒng)中有五臺參與執(zhí)行paxos算法的主機(jī)S1，.....，S5，每臺主機(jī)都同時扮演proposer、accepter和learner的角色，系統(tǒng)開始時所有主機(jī)都能正常運(yùn)行，當(dāng)決議134號剛被所有l(wèi)earner學(xué)習(xí)后，S4突然掉電，系統(tǒng)繼續(xù)正常運(yùn)行，一段時間后S4重新啟動，這時系統(tǒng)中其他learner已經(jīng)學(xué)習(xí)到191號決議，如果不做任何處理，S4將再也不能學(xué)習(xí)任何正在進(jìn)行的決議，因?yàn)镾4必須先學(xué)習(xí)135~191號決議，這就是所謂的“gap”?？梢曰叵胍幌卤酒恼碌拈_頭描述的經(jīng)典場景“在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個一致的狀態(tài)”。必須是在初始狀態(tài)一致的情況下才有效，因此S4必須先先學(xué)習(xí)135~191號決議待狀態(tài)和其他四臺主機(jī)一致后，才能參與到paxos的表決過程中。學(xué)習(xí)135~191決議彌補(bǔ)“gap”的機(jī)制也被稱為catch-up機(jī)制，在工程實(shí)現(xiàn)時有使用日志方式、BerkeleyBD、快照等等。

三、算法總結(jié)

    Paxos算法利用Majority機(jī)制的投票形式保證2F+1的容錯能力，即2F+1個結(jié)點(diǎn)的系統(tǒng)最多允許F個結(jié)點(diǎn)同時出現(xiàn)故障。使得各角色之間的結(jié)構(gòu)、聯(lián)系比較松散，加之很弱的先決條件，讓paxos算法在實(shí)際工程中易于實(shí)現(xiàn)。使用單增的實(shí)例id來標(biāo)識決議的方式，使得整個算法的并行性更好(id號大的決議可以先于id號小的決議被批準(zhǔn)，不會影響決議序列的順序)。總得來說paxos算法是很巧妙的，Lamport嚴(yán)謹(jǐn)?shù)淖C明也保證了算法的正確性。在Basic paxos算法基礎(chǔ)上發(fā)展而來的fastpaxos只用兩次消息傳遞就能通過一個value，比傳統(tǒng)的一致性算法減少了一次消息傳遞。

    這幾年，paxos算法的廣泛使用很好的證明了算法的價(jià)值。

后續(xù)：“分布式一致性Paxos算法學(xué)習(xí)筆記（三）：算法的工程描述”

    學(xué)習(xí)筆記三側(cè)重實(shí)用，使用較為工程化的語言描述算法的過程、給出消息傳遞過程中所使用到的變量的定義及三類角色在兩個階段中的任務(wù)。

References

[1]中文維基百科：http://zh./zh-cn/Paxos算法

[2]Leslie Lamport. Paxos made simple.2001,11,1

[3]Leslie Lamport.Fastpaxos. DistributedComputing,19(2):79–103,2006.

[4]Leslie Lamport. The Part-Time Parliament[J].ACM Transactions on Computer Systems,16,2(May 1998),133-169.

[5]http://en./wiki/Paxos_algorithm