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

一、簡(jiǎn)介

1.1Paxos算法處理的問題

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

1.2算法簡(jiǎn)介及一致性問題場(chǎng)景

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

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

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

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

二、算法詳解

2.1一致性算法

    一個(gè)一致性算法需要保證：一次選舉中只批準(zhǔn)一個(gè)決議(value)，只有被提出(proposed)的決議才能被批準(zhǔn)，只有已經(jīng)被批準(zhǔn)的決議才能被學(xué)習(xí)(即可以執(zhí)行或保存這個(gè)決定的內(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)一個(gè) Value；

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

    這樣的表述看似簡(jiǎn)單，但實(shí)際的證明過程還是很復(fù)雜的，而在三條中最為重要的是第二條作者Lamport在Paxos made simple[2]中花大量的篇幅來加強(qiáng)第二條的約束，從而總結(jié)出一個(gè)paxos實(shí)例的兩個(gè)階段及三類角色各自的工作。如何保證在一個(gè)paxos中只選出一個(gè)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í)行在一個(gè)可靠的通訊環(huán)境中，即在異步通訊過程中不會(huì)出現(xiàn)被篡改的情況(non-Byzantine model)，但允許發(fā)送的數(shù)據(jù)出現(xiàn)丟失、延遲、重復(fù)的情況。則個(gè)角色可工作在任意速度、允許停止和重啟的錯(cuò)誤?？芍貑?restart)性質(zhì)就要求各角色"隨時(shí)"保存自己的當(dāng)前狀態(tài)，換句話說就是要把狀態(tài)寫入硬盤，所以在Paxos算法學(xué)習(xí)筆記（一）中提到的diskles paxos讓我很疑惑，有時(shí)間在研究。

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

2.2算法的內(nèi)容

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

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

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

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

2.2.1通過一個(gè)決議

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

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

通過一個(gè)決議分為兩個(gè)階段[1]：

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

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

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

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

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

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

這個(gè)過程在任何時(shí)候中斷都可以保證正確性。例如如果一個(gè) proposer 發(fā)現(xiàn)已經(jīng)有其他 proposers 提出了編號(hào)更高的提案，則有必要中斷這個(gè)過程。因此為了優(yōu)化，在上述 prepare 過程中，如果一個(gè) acceptor 發(fā)現(xiàn)存在一個(gè)更高編號(hào)的"草案"，則需要通知 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”的文字描述，過程看起來是很簡(jiǎn)單的，但實(shí)現(xiàn)時(shí)有很多細(xì)節(jié)需要注意，而更詳細(xì)的描述將放在本學(xué)習(xí)筆記的下一篇《Paxos算法的工程描述》，屆時(shí)將給出各個(gè)角色在這兩階段中的工作及涉及的變量。

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

    Paxos made simple中同樣用很大的篇幅來描述如何"Learning a Chosen Value"，并強(qiáng)調(diào)Learners學(xué)習(xí)過程中可能出現(xiàn)決議的“gap”(詳情參照原文)。實(shí)際上可以這樣理解：現(xiàn)在有兩個(gè)已經(jīng)執(zhí)行完上面P2b過程的value1和value2，即這兩個(gè)決議已經(jīng)被批準(zhǔn)(accepted)，接下來系統(tǒng)中有五個(gè)learner要學(xué)習(xí)這兩個(gè)決議，由于learners之間還是基于網(wǎng)絡(luò)的通訊，則value1和value2到達(dá)learners的順序可能是不一樣的，存在不一致的問題。怎么解決這個(gè)問題？怎么區(qū)分value1和value2的先后？可以回想一下，這兩個(gè)決議是分別由兩個(gè)不同paxos實(shí)例選舉得出，那么就可以使用實(shí)例id(instance id)來區(qū)分兩個(gè)決議的先后。規(guī)定learner必須按照實(shí)例id從小到大依次學(xué)習(xí)各決議，從而保證決議序列在所有l(wèi)earner上一致的，每一個(gè)paxos實(shí)例只能批準(zhǔn)一個(gè)決議，這樣操作系列的一致就不言而喻。所以工程實(shí)現(xiàn)時(shí)如何設(shè)計(jì)這個(gè)單增的實(shí)例id(instance id)是一個(gè)關(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個(gè)結(jié)點(diǎn)的系統(tǒng)中，paxos算法允許最多F個(gè)結(jié)點(diǎn)同時(shí)出現(xiàn)故障。假設(shè)系統(tǒng)中有五臺(tái)參與執(zhí)行paxos算法的主機(jī)S1，.....，S5，每臺(tái)主機(jī)都同時(shí)扮演proposer、accepter和learner的角色，系統(tǒng)開始時(shí)所有主機(jī)都能正常運(yùn)行，當(dāng)決議134號(hào)剛被所有l(wèi)earner學(xué)習(xí)后，S4突然掉電，系統(tǒng)繼續(xù)正常運(yùn)行，一段時(shí)間后S4重新啟動(dòng)，這時(shí)系統(tǒng)中其他learner已經(jīng)學(xué)習(xí)到191號(hào)決議，如果不做任何處理，S4將再也不能學(xué)習(xí)任何正在進(jìn)行的決議，因?yàn)镾4必須先學(xué)習(xí)135~191號(hào)決議，這就是所謂的“gap”。可以回想一下本篇文章的開頭描述的經(jīng)典場(chǎng)景“在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)”。必須是在初始狀態(tài)一致的情況下才有效，因此S4必須先先學(xué)習(xí)135~191號(hào)決議待狀態(tài)和其他四臺(tái)主機(jī)一致后，才能參與到paxos的表決過程中。學(xué)習(xí)135~191決議彌補(bǔ)“gap”的機(jī)制也被稱為catch-up機(jī)制，在工程實(shí)現(xiàn)時(shí)有使用日志方式、BerkeleyBD、快照等等。

三、算法總結(jié)

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

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

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

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