Paxos算法產生的背景

(資料圖片)

Paxos算法是基于消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分布式一致性問題最有效的算法之一，其解決的問題就是在分布式系統中如何就某個值（決議）達成一致。

我自己的理解是：不要把這個Paxos算法達到的目的和分布式事務聯系起來，而是針對Zookeeper這樣的master-slave集群對某個決議達成一致，也就是副本之間寫或者leader選舉達成一致。我覺得這個算法和狹義的分布式事務不是一樣的。

在常見的分布式系統中，總會發生諸如機器宕機或網絡異常（包括消息的延遲、丟失、重復、亂序，還有網絡分區）(也就是會發生異常的分布式系統)等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正確地在集群內部對某個數據的值達成一致。也可以理解成分布式系統中達成狀態的一致性。

注：這里某個數據的值并不只是狹義上的某個數，它可以是一條日志，也可以是一條命令（command）。。。根據應用場景不同，某個數據的值有不同的含義。

對Paxos保證一致性換一種理解：

Paxos 算法是分布式一致性算法用來解決一個分布式系統如何就某個值(決議)達成一致的問題。一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個”一致性算法”以保證每個節點看到的指令一致。

分布式系統中一般是通過多副本來保證可靠性，而多個副本之間會存在數據不一致的情況。所以必須有一個一致性算法來保證數據的一致，描述如下：

假如在分布式系統中初始是各個節點的數據是一致的，每個節點都順序執行系列操作，然后每個節點最終的數據還是一致的。

Paxos算法就是解決這種分布式場景中的一致性問題。對于一般的開發人員來說，只需要知道paxos是一個分布式選舉算法即可。多個節點之間存在兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基于消息傳遞的通訊模型的。

拜占庭問題

拜占庭將軍問題：是指 拜占庭帝國軍隊的將軍們必須全體一致的決定是否gong擊某一支敵軍。問題是這些將軍在地理上是分隔開來的，只能依靠通訊員進行傳遞命令，但是通訊員中存在叛徒，它們可以篡改消息，叛徒可以欺騙某些將軍采取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。

Paxos算法的前提假設是不存在拜占庭將軍問題，即： 信道是安全的（信道可靠），發出的信號不會被篡改，因為Paxos算法是基于消息傳遞的。此問題由Lamport提出，它也是 Paxos算法的提出者。

從理論上來說，在分布式計算領域，試圖在異步系統和不可靠信道上來達到一致性狀態是不可能的。因此在對一致性的研究過程中，都往往假設信道是可靠的，而事實上，大多數系統都是部署在一個局域網中，因此消息被篡改的情況很罕見；另一方面，由于硬件和網絡原因而造成的消息不完整問題，只需要一套簡單的校驗算法即可。因此，在實際工程中，可以假設所有的消息都是完整的，也就是沒有被篡改。

Paxos算法的相關概念

在Paxos算法中，有三種角色：

在具體的實現中，一個進程可能 同時充當多種角色 。比如一個進程可能 既是Proposer又是Acceptor又是Learner 。Proposer負責提出提案，Acceptor負責對提案作出裁決（accept與否），learner負責學習提案結果。

還有一個很重要的概念叫提案（Proposal）。最終要達成一致的value就在提案里。只要Proposer發的提案被Acceptor接受（半數以上的Acceptor同意才行），Proposer就認為該提案里的value被選定了。Acceptor告訴Learner哪個value被選定，Learner就認為那個value被選定。只要Acceptor接受了某個提案，Acceptor就任務該提案里的value被選定了。

為了避免單點故障，會有一個Acceptor集合，Proposer想Acceptor集合發送提案，Acceptor集合中的每個成員都有可能同意該提案且每個Acceptor只能批準一個提案，只有當一半以上的成員同意了一個提案，就認為該提案被選定了。

Paxos算法的解決的問題描述

假設有一組可以提出（propose）value（value在提案Proposal里）的進程集合。一個一致性算法需要保證提出的這么多value中，只有一個value被選定（chosen）。如果沒有value被提出，就不應該有value被選定。如果一個value被選定，那么所有進程都應該能學習（learn）到這個被選定的value。對于一致性算法，安全性（safaty）要求如下：

Paxos的目標：保證最終有一個value會被選定，當value被選定后，進程最終也能獲取到被選定的value。

Paxos算法的過程（算法描述）

Paxos算法類似于兩階段提提交，其算法執行過程分為兩個階段。具體如下：

(a) Proposer選擇一個提案編號N，然后向半數以上的Acceptor發送編號為N的Prepare請求。Pareper（N）

(b) 如果一個Acceptor收到一個編號為N的Prepare請求，如果小于它已經響應過的請求，則拒絕，不回應或回復error。若N大于該Acceptor已經響應過的所有Prepare請求的編號（maxN），那么它就會將它已經接受過（已經經過第二階段accept的提案）的編號最大的提案（如果有的話，如果還沒有的accept提案的話返回{pok，null，null}）作為響應反饋給Proposer，同時該Acceptor承諾不再接受任何編號小于N的提案。

(a) 如果一個Proposer收到半數以上Acceptor對其發出的編號為N的Prepare請求的響應，那么它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編號最大的提案的value（某個acceptor響應的它已經通過的{acceptN，acceptV}），如果響應中不包含任何提案，那么V就由Proposer自己決定。

(b) 如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應，它就接受該提案。如果N小于Acceptor以及響應的prepare請求，則拒絕，不回應或回復error（當proposer沒有收到過半的回應，那么他會重新進入第一階段，遞增提案號，重新提出prepare請求）。

所有proposer經過上邊的不走

注意：有幾個約定：

（1）每一個Acceptor最多就只能批準一個提案（就是第二階段accept的），那么就能保證只有一個提案被選定了？？？Accept之后就不能改了？？？如果不能改的話，那Acceptor肯定不是一致的，而且這樣能達到多數？？但是，如果能改的話，倒是能達成一致，但是這樣真的可以？？我感覺是可以accept多個的，但是書上又寫了每一個Acceptor最多就只能批準一個提案。但后邊也寫了改變accept的值，不懂。。。。。。。最后，我覺得是只能accept一個，proposer會達成一致的value1，所以選出了唯一的value。應該不會出現那個始終達不成過半情況，因為畢竟發送時有先后的。所以，下邊的圖畫的還是不那么準確。

（2）因為獲取那些已經通過的提案比預測未來可能會通過的提案來的簡單。當Acceptor對一個N的prepare的提案響應后，他就會作出保證，不再接受任何小于N的提案號的提案。

具體實例理解

問題背景：假設我們有下圖的系統，想要在server1，server2，server3選一個master。

prepare階段

1. 每個server向proposer發送消息，表示自己要當leader，假設proposer收到消息的時間不一樣，順序是： proposer2 -> proposer1 -> proposer3，消息編號依次為1、2、3。

緊接著，proposer將消息發給acceptor中超過半數的子成員(這里選擇兩個)，如圖所示，proposer2向acceptor2和acceptor3發送編號為1的消息，proposer1向acceptor1和accepto2發送編號為2的消息，proposer3向acceptor2和acceptor3發送編號為3的消息。

2.假設這時proposer1發送的消息先到達acceptor1和acceptor2，它們都沒有接收過請求，所以接收該請求并返回【pok，null，null】給proposer1，同時acceptor1和acceptor2承諾不再接受編號小于2的請求；

緊接著，proposer2的消息到達acceptor2和acceptor3，acceptor3沒有接受過請求，所以返回proposer2 【pok，null，null】，acceptor3并承諾不再接受編號小于1的消息。而acceptor2已經接受proposer1的請求并承諾不再接收編號小于2的請求，所以acceptor2拒絕proposer2的請求；

最后，proposer3的消息到達acceptor2和acceptor3，它們都接受過提議，但編號3的消息大于acceptor2已接受的2和acceptor3已接受的1，所以他們都接受該提議，并返回proposer3 【pok，null，null】；

此時，proposer2沒有收到過半的回復，所以重新取得編號4，并發送給acceptor2和acceptor3，此時編號4大于它們已接受的提案編號3，所以接受該提案，并返回proposer2 【pok，null，null】。

accept階段

1

Proposer3收到半數以上（兩個）的回復，并且返回的value為null，所以，proposer3提交了【3，server3】的提案。

Proposer1也收到過半回復，返回的value為null，所以proposer1提交了【2，server1】的提案。

Proposer2也收到過半回復，返回的value為null，所以proposer2提交了【4，server2】的提案。

（這里要注意，并不是所有的proposer都達到過半了才進行第二階段，這里只是一種特殊情況）

2

Acceptor1和acceptor2接收到proposer1的提案【2，server1】，acceptor1通過該請求，acceptor2承諾不再接受編號小于4的提案，所以拒絕；

Acceptor2和acceptor3接收到proposer2的提案【4，server2】，都通過該提案；

Acceptor2和acceptor3接收到proposer3的提案【3，server3】，它們都承諾不再接受編號小于4的提案，所以都拒絕。

所以proposer1和proposer3會再次進入第一階段，但這時候Acceptor2和acceptor3已經通過了提案（AcceptN = 4，AcceptV=server2），并達成了多數，所以proposer會遞增提案編號，并最終改變其值為server2。最后所有的proposer都肯定會達成一致，這就迅速的達成了一致。

此時，過半的acceptor（acceptor2和acceptor3）都接受了提案【4，server2】，learner感知到提案的通過，learner開始學習提案，所以server2成為最終的leader。

Learner學習被選定的value（第二階段accept的）

有三種方案：

Paxos算法的活鎖問題（保證算法活性）

上邊我們介紹了Paxos的算法邏輯，但在算法運行過程中，可能還會存在一種極端情況，當有兩個proposer依次提出一系列編號遞增的議案，那么會陷入死循環，無法完成第二階段，也就是無法選定一個提案。如下圖：

通過選取主Proposer，就可以保證Paxos算法的活性。選擇一個主Proposer，并規定只有主Proposer才能提出議案。這樣一來，只要主Proposer和過半的Acceptor能夠正常進行網絡通信，那么肯定會有一個提案被批準（第二階段的accept），則可以解決死循環導致的活鎖問題。

Paxos算法的過半依據

在Paxos算法中，采用了“過半”理念，也就是少數服從多數，這使Paxos算法具有很好的容錯性。那么為什么采用過半就可以呢？

Paxos基于的過半數學原理： 我們稱大多數（過半）進程組成的集合為法定集合， 兩個法定（過半）集合必然存在非空交集，即至少有一個公共進程，稱為法定集合性質。 例如A,B,C,D,F進程組成的全集，法定集合Q1包括進程A,B,C，Q2包括進程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共進程。如果要說Paxos最根本的原理是什么，那么就是這個簡單性質。也就是說：兩個過半的集合必然存在交集，也就是肯定是相等的，也就是肯定達成了一致。

Paxos是基于消息傳遞的具有高度容錯性的分布式一致性算法。Paxos算法引入了過半的概念，解決了2PC，3PC的太過保守的缺點，且使算法具有了很好的容錯性，另外Paxos算法支持分布式節點角色之間的輪換，這極大避免了分布式單點的出現，因此Paxos算法既解決了無限等待問題，也解決了腦裂問題，是目前來說最優秀的分布式一致性算法。其中，Zookeeper的ZAB算法和Raft一致性算法都是基于Paxos的。在后邊的文章中，我會逐步介紹優秀的分布式協調服務框架，也是極優秀的工業一致性算法的實現Zookeeper使用和實現。

????