前言

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

在介紹Paxos之前，先介紹一下數據一致性到底被用在什么場景中，下面以副本狀態機來表述

副本狀態機

在分布式環境下，一致性協議的應用場景一般會采用副本狀態機來表達，這是對各種不同應用場景的一種抽象化表述。

一種典型的實現副本狀態機的機制是采用Log副本的方式，如下圖(來源網上)：

集群中多臺服務器各自保存一份Log副本及內部狀態機，Log內順序記載客戶端發來的操作指令，服務器依次執行Log內的指令并將其體現到內部狀態機上，如果保證每臺機器內的Log副本內容完全一致，那么對應的狀態機也可以保證整體狀態一致。

一致性協議的作用就是保證各個Log副本數據的一致性，上圖中的一致性模塊就是用來保證一致性的。

再來看一個更具體的例子：在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性算法」以保證每個節點看到的指令一致。

民主選舉算法

如何保證各個Log副本數據的一致性(或者說如何來實現這個一致性模塊)，可能最先想到的是只需要提供一個唯一一致性模塊，然后用類似2PC的方式來保證數據的一致性，但是我們也知道了2PC方式中面臨著一致性模塊的當機以及網絡的異常等問題，最終導致數據出現不一致；

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

當然這個保證是有一個前提的，這就是下面要介紹的拜占庭問題。

拜占庭問題

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

從理論上來說，在分布式計算領域，試圖在異步系統和不可靠的通道上來達到一致性是不可能的，因此在對一致性的研究過程中，都往往假設信道是可靠的，即假設不存在拜占庭問題。

非拜占庭模型定義：

1.一致性模塊的行為可以以任意速度執行，允許運行失敗，在失敗后也許會重啟并再次運行；

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

Paxos的基本概念

首先是并行進程（對應副本狀態機上每臺服務器的一致性模塊）的角色概念，Paxos協議下不同并行進程可能承擔的三種角色如下：

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

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

學習者（Learner）：學習者無倡議投票權，但是可以從接受者那里獲知是哪個提議最終被選中；

在一致性協議框架中，一個并行進程可以同時承擔以上多種角色。

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

1.決議（value）只有在被 proposers 提出后才能批準（未經批準的決議稱為「提案（proposal）」）；

2.在一次Paxos算法的執行實例中，只批準一個Value；

3.Learner只能獲得被批準（chosen）的Value。

Paxos一致性協議

Paxos的目的是在非拜占庭條件下，當多個并行進程提出不同的倡議時，如何能夠達成一致。如果歸納Paxos協議，可以將其描述為以下兩階段過程：

階段一:Prepare階段

1.1【倡議者視角】倡議者選擇倡議編號n，然后向大多數（即超過半數以上）接受者發送Prepare請求，請求中附帶倡議編號n。

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

階段二:Accept階段

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

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

通過以上流程，如果有多個并發進程提出各自的倡議值，Paxos就可以保證從中選出且只選出一個唯一確定的倡議值，以此來達到副本狀態機保持狀態一致的目標。