前言

在文章2PC/3PC到底是啥中介紹了2PC這種一致性協(xié)議，從文中了解到2PC更多的被用在了狀態(tài)一致性上(分布式事務(wù))，在數(shù)據(jù)一致性中很少被使用；而Paxos正是在數(shù)據(jù)一致性中被廣泛使用，在過去十年里，Paxos基本成為了分布式領(lǐng)域內(nèi)一致性協(xié)議的代名詞。google的粗粒度鎖服務(wù)Chubby的設(shè)計(jì)開發(fā)者Burrows曾經(jīng)說過：“所有一致性協(xié)議本質(zhì)上要么是Paxos要么是其變體”。Paxos的提出者LeslieLamport也因其對(duì)分布式系統(tǒng)的杰出理論貢獻(xiàn)獲得了2013年圖靈獎(jiǎng)。

在介紹Paxos之前，先介紹一下數(shù)據(jù)一致性到底被用在什么場(chǎng)景中，下面以副本狀態(tài)機(jī)來(lái)表述

副本狀態(tài)機(jī)

在分布式環(huán)境下，一致性協(xié)議的應(yīng)用場(chǎng)景一般會(huì)采用副本狀態(tài)機(jī)來(lái)表達(dá)，這是對(duì)各種不同應(yīng)用場(chǎng)景的一種抽象化表述。

一種典型的實(shí)現(xiàn)副本狀態(tài)機(jī)的機(jī)制是采用Log副本的方式，如下圖(來(lái)源網(wǎng)上)：

集群中多臺(tái)服務(wù)器各自保存一份Log副本及內(nèi)部狀態(tài)機(jī)，Log內(nèi)順序記載客戶端發(fā)來(lái)的操作指令，服務(wù)器依次執(zhí)行Log內(nèi)的指令并將其體現(xiàn)到內(nèi)部狀態(tài)機(jī)上，如果保證每臺(tái)機(jī)器內(nèi)的Log副本內(nèi)容完全一致，那么對(duì)應(yīng)的狀態(tài)機(jī)也可以保證整體狀態(tài)一致。

一致性協(xié)議的作用就是保證各個(gè)Log副本數(shù)據(jù)的一致性，上圖中的一致性模塊就是用來(lái)保證一致性的。

再來(lái)看一個(gè)更具體的例子：在一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)「一致性算法」以保證每個(gè)節(jié)點(diǎn)看到的指令一致。

民主選舉算法

如何保證各個(gè)Log副本數(shù)據(jù)的一致性(或者說如何來(lái)實(shí)現(xiàn)這個(gè)一致性模塊)，可能最先想到的是只需要提供一個(gè)唯一一致性模塊，然后用類似2PC的方式來(lái)保證數(shù)據(jù)的一致性，但是我們也知道了2PC方式中面臨著一致性模塊的當(dāng)機(jī)以及網(wǎng)絡(luò)的異常等問題，最終導(dǎo)致數(shù)據(jù)出現(xiàn)不一致；

而本文要介紹的Paxos一致性協(xié)議就是如何在可能發(fā)生幾起宕機(jī)或網(wǎng)絡(luò)異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生以上任何異常，都不會(huì)破壞整個(gè)系統(tǒng)的一致性，主要原因還是Paxos提供了集群一致性模塊，然后以民主選舉的算法——大多數(shù)的決定會(huì)成個(gè)整個(gè)集群的統(tǒng)一決定。任何一個(gè)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案，是否通過這個(gè)提案取決于這個(gè)集群中是否有超過半數(shù)的結(jié)點(diǎn)同意（所以Paxos算法需要集群中的結(jié)點(diǎn)是單數(shù)）；

當(dāng)然這個(gè)保證是有一個(gè)前提的，這就是下面要介紹的拜占庭問題。

拜占庭問題

其故事背景是這樣的：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾，是東羅馬帝國(guó)的首都。由于當(dāng)時(shí)拜占庭羅馬帝國(guó)國(guó)土遼闊，為了防御目的，因此每個(gè)軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭(zhēng)的時(shí)候，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成一致的共識(shí)，決定是否有贏的機(jī)會(huì)才去攻打敵人的陣營(yíng)。但是，軍隊(duì)可能有叛徒和敵軍間諜，這些叛徒將軍們會(huì)擾亂或左右決策的過程。這時(shí)候，在已知有成員謀反的情況下，其余忠誠(chéng)的將軍在不受叛徒的影響下如何達(dá)成一致的協(xié)議，這就是拜占庭將軍問題。

從理論上來(lái)說，在分布式計(jì)算領(lǐng)域，試圖在異步系統(tǒng)和不可靠的通道上來(lái)達(dá)到一致性是不可能的，因此在對(duì)一致性的研究過程中，都往往假設(shè)信道是可靠的，即假設(shè)不存在拜占庭問題。

非拜占庭模型定義：

1.一致性模塊的行為可以以任意速度執(zhí)行，允許運(yùn)行失敗，在失敗后也許會(huì)重啟并再次運(yùn)行；

2.一致性模塊之間通過異步方式發(fā)送信息通信，通信時(shí)間可以任意長(zhǎng)，信息可能會(huì)在傳輸過程中丟失，也允許重復(fù)發(fā)送相同的信息，多重信息的順序可以任意。但是有一點(diǎn)：信息不允許被篡改。

Paxos的基本概念

首先是并行進(jìn)程（對(duì)應(yīng)副本狀態(tài)機(jī)上每臺(tái)服務(wù)器的一致性模塊）的角色概念，Paxos協(xié)議下不同并行進(jìn)程可能承擔(dān)的三種角色如下：

倡議者（Proposer）：倡議者可以提出提議（數(shù)值或操作命令等）以供投票表決；

接受者（Acceptor）：接受者可以對(duì)倡議者提出的提議進(jìn)行投票表決，從眾多提議中選出唯一確定的一個(gè)；

學(xué)習(xí)者（Learner）：學(xué)習(xí)者無(wú)倡議投票權(quán)，但是可以從接受者那里獲知是哪個(gè)提議最終被選中；

在一致性協(xié)議框架中，一個(gè)并行進(jìn)程可以同時(shí)承擔(dān)以上多種角色。

劃分角色后，就可以更精確的定義問題：

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

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

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

Paxos一致性協(xié)議

Paxos的目的是在非拜占庭條件下，當(dāng)多個(gè)并行進(jìn)程提出不同的倡議時(shí)，如何能夠達(dá)成一致。如果歸納Paxos協(xié)議，可以將其描述為以下兩階段過程：

階段一:Prepare階段

1.1【倡議者視角】倡議者選擇倡議編號(hào)n，然后向大多數(shù)（即超過半數(shù)以上）接受者發(fā)送Prepare請(qǐng)求，請(qǐng)求中附帶倡議編號(hào)n。

1.2【接受者視角】對(duì)于某個(gè)接受者來(lái)說，如果接收到帶有倡議編號(hào)n的Prepare請(qǐng)求，則做如下判斷：若倡議編號(hào)n比此接受者之前響應(yīng)過的任何其它Prepare請(qǐng)求附帶的倡議編號(hào)都大，那么此接受者會(huì)給倡議者以響應(yīng)，并承諾不會(huì)響應(yīng)之后接收到的其它任何倡議編號(hào)小于n的請(qǐng)求，另外，如果接受者曾經(jīng)響應(yīng)過2.2階段的Accept請(qǐng)求，則將所有響應(yīng)的Accept請(qǐng)求中倡議編號(hào)最高的倡議內(nèi)容發(fā)送給倡議者，倡議內(nèi)容包括兩項(xiàng)信息：Accept請(qǐng)求中的倡議編號(hào)以及其倡議值。若倡議編號(hào)n不比此接受者之前響應(yīng)過的任何其它Prepare請(qǐng)求附帶的倡議編號(hào)都大，那么此接受者不會(huì)給倡議者以響應(yīng)。

階段二:Accept階段

2.1【倡議者視角】如果倡議者接收到大多數(shù)接受者關(guān)于帶有倡議編號(hào)n的Prepare請(qǐng)求的響應(yīng)，那么倡議者向這些接受者發(fā)送Accept請(qǐng)求，Accept請(qǐng)求附帶兩個(gè)信息：倡議編號(hào)n以及倡議值v。倡議值v的選擇方式如下：如果在1.2階段接受者返回了自己曾經(jīng)接受的具有最高倡議編號(hào)Accept請(qǐng)求倡議內(nèi)容，則從這些倡議內(nèi)容里面選擇倡議編號(hào)最高的并將其倡議值作為倡議值v；如果1.2階段沒有收到任何接受者的Accept請(qǐng)求倡議內(nèi)容，則可以任意賦值給倡議值v。

2.2【接受者視角】如果接受者接收到了任意倡議編號(hào)為n的Accept請(qǐng)求，則接受者接受此請(qǐng)求，除非在此期間接受者響應(yīng)過具有比n更高編號(hào)的Prepare請(qǐng)求。通過以上兩階段過程即可選出唯一的倡議值，對(duì)于學(xué)習(xí)者來(lái)說，其需要從接受者那里獲知到底是哪個(gè)倡議值被選出。一個(gè)直觀的方法如下：每當(dāng)接受者執(zhí)行完2.2步驟，即接受某個(gè)Accept請(qǐng)求后，由其通知所有學(xué)習(xí)者其所接受的倡議，這樣，學(xué)習(xí)者很快習(xí)得是哪個(gè)倡議被最終選出。但是這種方式會(huì)導(dǎo)致大量通信，因?yàn)槿我庖粋€(gè)接受者會(huì)通知任意一個(gè)學(xué)習(xí)者，如果有m個(gè)接受者，n個(gè)學(xué)習(xí)者，則需要m*n次通信。一個(gè)替代策略是：從眾多學(xué)習(xí)者中選擇一個(gè)作為代表，由其從接受者那里獲知最終被選出的倡議，然后再由其通知其它學(xué)習(xí)者，這樣可以將通信量降為m+n。但是這個(gè)方案中如果這個(gè)學(xué)習(xí)者代表發(fā)生故障，其它學(xué)習(xí)者無(wú)從知曉倡議值。考慮到健壯性和通信量?jī)蓚€(gè)因素，可以采取折中方法：選出若干學(xué)習(xí)者作為代表，由這些代表從接受者那里獲知最終倡議值，然后通知其它學(xué)習(xí)者。

通過以上流程，如果有多個(gè)并發(fā)進(jìn)程提出各自的倡議值，Paxos就可以保證從中選出且只選出一個(gè)唯一確定的倡議值，以此來(lái)達(dá)到副本狀態(tài)機(jī)保持狀態(tài)一致的目標(biāo)。