Zookeeper系列（3）--Paxos演算法的原理及過程透徹理解
從上一篇我們了解了2PC和3PC之後，我們可以發現，無論是二階段提交還是三階段提交都無法徹底解決分散式的一致性問題以及無法解決太過保守及容錯性不好。Google Chubby的作者Mike Burrows說過，世上只有一種一致性演算法，那就是Paxos，所有其他一致性演算法都是Paxos演算法的不完整版。Paxos演算法是公認的晦澀，很難可能能將清楚，但是工程上也很難實現，所以有很多Paxos演算法的工程實現，如Raft，ZAB，微信的PhxPaxos等。這一篇會介紹這個公認為難於理解但是行之有效的Paxos演算法。Paxos演算法是萊斯利·蘭伯特(Leslie Lamport)1990年提出的一種基於消息傳遞的一致性演算法，它曾就此發表了《The Part-Time Parliament》，《Paxos Made Simple》，由於採用故事的方式來解釋此演算法，感覺還是很難理解。
Paxos演算法產生的背景
Paxos演算法是基於消息傳遞且具有高度容錯特性的一致性演算法，是目前公認的解決分散式一致性問題最有效的演算法之一，其解決的問題就是在分散式系統中如何就某個值（決議）達成一致。
我自己的理解是：不要把這個Paxos演算法達到的目的和分散式事務聯繫起來，而是針對Zookeeper這樣的master-slave集群對某個決議達成一致，也就是副本之間寫或者leader選舉達成一致。我覺得這個演算法和狹義的分散式事務不是一樣的。
在常見的分散式系統中，總會發生諸如機器宕機或網路異常（包括消息的延遲、丟失、重複、亂序，還有網路分區）(也就是會發生異常的分散式系統)等情況。Paxos演算法需要解決的問題就是如何在一個可能發生上述異常的分散式系統中，快速且正確地在集群內部對某個數據的值達成一致。也可以理解成分散式系統中達成狀態的一致性。
註：這裡某個數據的值並不只是狹義上的某個數，它可以是一條日誌，也可以是一條命令（command）。。。根據應用場景不同，某個數據的值有不同的含義。
對Paxos保證一致性換一種理解：
Paxos 演算法是分散式一致性演算法用來解決一個分散式系統如何就某個值(決議)達成一致的問題。一個典型的場景是，在一個分散式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個」一致性演算法」以保證每個節點看到的指令一致。
分散式系統中一般是通過多副本來保證可靠性，而多個副本之間會存在數據不一致的情況。所以必須有一個一致性演算法來保證數據的一致，描述如下：
假如在分散式系統中初始是各個節點的數據是一致的，每個節點都順序執行系列操作，然後每個節點最終的數據還是一致的。
Paxos演算法就是解決這種分散式場景中的一致性問題。對於一般的開發人員來說，只需要知道paxos是一個分散式選舉演算法即可。多個節點之間存在兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基於消息傳遞的通訊模型的。
拜占庭問題
拜占庭將軍問題：是指拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的，只能依靠通訊員進行傳遞命令，但是通訊員中存在叛徒，它們可以篡改消息，叛徒可以欺騙某些將軍採取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。
Paxos演算法的前提假設是不存在拜占庭將軍問題，即：信道是安全的（信道可靠），發出的信號不會被篡改，因為Paxos演算法是基於消息傳遞的。此問題由Lamport提出，它也是 Paxos演算法的提出者。
從理論上來說，在分散式計算領域，試圖在非同步系統和不可靠信道上來達到一致性狀態是不可能的。因此在對一致性的研究過程中，都往往假設信道是可靠的，而事實上，大多數系統都是部署在一個區域網中，因此消息被篡改的情況很罕見；另一方面，由於硬體和網路原因而造成的消息不完整問題，只需要一套簡單的校驗演算法即可。因此，在實際工程中，可以假設所有的消息都是完整的，也就是沒有被篡改。
Paxos演算法的相關概念
在Paxos演算法中，有三種角色：
Proposer
Acceptor
Learners
在具體的實現中，一個進程可能同時充當多種角色。比如一個進程可能既是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）要求如下：
只有被提出的value才能被選定。
只有一個value被選定，並且
如果某個進程認為某個value被選定了，那麼這個value必須是真的被選定的那個。
Paxos的目標：保證最終有一個value會被選定，當value被選定後，進程最終也能獲取到被選定的value。
Paxos演算法的過程（演算法描述）
Paxos演算法類似於兩階段提提交，其演算法執行過程分為兩個階段。具體如下：
階段一（prepare階段）：
(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的提案。
階段二（accept階段）：
(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使用和實現。
推薦閱讀：
