Paxos在分布式系統(tǒng)中的重要性無需多言。我們能在網(wǎng)絡上找到非常多解析Paxos原理的文章，這些文章大部分只講協(xié)議的過程，有些深入的文章還會講協(xié)議的證明，我總感覺缺少對Paxos協(xié)議“生動直觀”的理解。最終我認為最直觀解釋Paxos的文章是作者Lamport在2001年發(fā)表的《Paxos Made Simple》。作者寫這篇文檔的目的是因為1998年發(fā)表的paxos原文《The part-time parliament》被很多人吐槽晦澀難懂。在《Paxos Made Simple》文中作者對Paxos協(xié)議做了一次從簡單場景到完整協(xié)議的推演。我寫這篇文章沒有什么新奇的地方，僅僅寫我對《Paxos Made Simple》的推演過程的消化理解。
Paxos協(xié)議要解決的問題：
在一個不可靠的分布式環(huán)境中，各個實體達成一個一致的狀態(tài)。
如果系統(tǒng)中只有一個proposal，那么這個proposal的提議在大多數(shù)acceptor存活時，必須要被接受。因此
P1.? An acceptor must accept the first proposal that it receives.
如果有多個proposal，每個acceptor只接受第一個proposal而拒絕后續(xù)所有的proposal的話。那么就可能會導致每個proposal都不能被大多數(shù)acceptor接受，導致協(xié)議無法收斂。因此：
每個acceptor接受的proposal不止一個，當然，只有被大多數(shù)acceptor接收的proposal才會被chosen
因此，我們允許多個proposal被選中，但是必須保證：這些被選中的proposal都有同樣的value。也就是說：
P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.
如何來保證只要一個value為v的proposal被chosen，后續(xù)的proposal的值都為v呢？
P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.
簡單啊，只要保證后面的被acceptor的proposal的值都為v就好了。那么如何保證后面的被accept的prososal都是v呢？
P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.
簡單啊，只要后面proposer發(fā)出的proposal都為v就好了。（這不廢話嗎）
那么，如何保證一旦一個proposal被chosen，后續(xù)的proposal都跟之前的proposal有相同的value呢？
P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.
意思是我們要把好proposal的出口這一關，就是說proposal不能瞎jb提，這樣才能保證“達成一致”的這個過程最快速的收斂。P2c翻譯一下的意思就是：對于任何一個proposal(n,v)（n是提案編號，v是提案值），如果要提出這個proposal，必須要滿足一下的兩個條件之一：
1.?大多數(shù)的acceptor都沒有accept小于n的proposal；?或者
2.?大多數(shù)的acceptor?accept的提案都小于n，這其中序號最大的一個提案的值就是v
怎么理解這兩個條件呢？直觀一點講就是，如果你想提案，要么1）大多數(shù)acceptor沒有接受過任何提案；要么2)你的提案跟之前最大編號的提案一樣。
好，其實paxos本質上就是通過約束每個proposer要提出的proposal來達到快速達成一致的目的（收斂）。
那么如何來約束proposor提出的proposal呢？根據(jù)之前提出了兩個條件，因此proposer在提出proposal之前，必須先“學習”，學習當前（大多數(shù)acceptor）最大提案的值。這個學習的過程叫做"Prepare":
Prepare階段
一個Proposer要想提案，它首先得知道當前要么大部分acceptor沒有接受過任何提案，要么找到一個在大部分acceptor組成的集合中最大的提案值。因此Proposer首先獲取一個新的提案編號，然后使用這個編號N向大部分acceptor發(fā)送prepare請求。這些acceptor給proposer響應
1）要么大多數(shù)acceptor從來沒有接受過任何提案
2）要么有部分acceptor告訴proposer當前最大的提案編號和提案值
? ? 2.1?有部分Acceptor的接受的最新的提案大于等于N，不可能。因為Acceptor只返回小于N的最大編號和提案值。一個acceptor不會響應一個小于它當前提案編號的proposal。
? ? 2.2?所有的提案編號都小于N。
3）有返回的acceptor沒有達到大多數(shù)（proposal無法繼續(xù)）
我們再看Acceptor在Prepare階段的邏輯：
1）如果Acceptor沒有承諾/接受過任何提案，那么向Proposal直接返回承諾，也就是后續(xù)不會接收小于N的proposal
2）如果Acceptor?承諾過一個小于N的提案，那么Aceeptor可以直接向Proposal再次承諾N，也就是之前的小于N的Proposal將永遠不會被自己Accept
3）如果Acceptor接受過一個小于N的提案，那么返回這個提案編號和提案值
4）如果Acceptor承諾過一個大于N的提案，那么忽略當前為N的提案（承諾也沒用，因為就算承諾了N，也不可能接受N）
5）如果Acceptor接受過一個大于N的提案，那么忽略當前為N的提案
一旦Acceptor給出了Prepare階段的響應，意味著這個Acceptor將不會接受小于N的提案。什么意思呢？只要一個Proposal通過了Prepare階段，也就意味著任何一個小于N的Proposal如果還沒有Prepare，他將不能通過Prepare階段，如果通過了Prepare，它也不會被大多數(shù)acceptor接受。相當于對整個acceptor集群做了一個鎖定操作，即鎖定不會有一個小于N的proposal被chosen。
但是也會出現(xiàn)這個問題，當為N的proposal在通過prepare階段之后但是還沒有還沒有發(fā)送acceptor請求之前，另一個proposer發(fā)起了一個編號為N+1的proposal，這個時候N+1也可以通過Prepare階段，接著另一個Proposor可能再發(fā)起一個N+2的proposal，這樣整個協(xié)議過程將無法收斂。
Accept階段
Proposer在Acceptor階段的邏輯：當?shù)谝浑A段學習(Prepare)完成后，Proposal收到了大部分Acceptor的響應。
1. 如果有一個最大的Proposal被接受，也就以為著當前沒有任何一個大于N的proposal被chosen。那么Proposer將會用自己選用的Proposal編號和學習到的當前最大Proposal的值作為新提案發(fā)起Accept請求。 （是否意味著有可能已經有小于N的proposal被chosen？有可能。是否意味著有可能有多個小于N的proposal被chosen？有可能。但是沒關系，因為這些已經被chosen的提案值和當前將要發(fā)出的提案值都一樣）。
2. 如果大部分的Acceptor沒有接受過任何Proposal，那么Proposer可以自己指定任何提案值發(fā)起Accept請求。
Acceptor在Accept階段的邏輯：
P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.
也就是，如果Acceptor沒有承諾過大于N的proposal，那它就可以accept?N。（如果他Accept過小于N的proposal呢？）。一個Acceptor需要記住兩樣東西：
1.?已經承諾過的最大提案編號，用來忽略大于此編號的prepare和accept請求
2.?已經接受過的最大提案編號和提案值，用來約束后續(xù)的提案值（通過后續(xù)提案的prepare請求）
到此為止，這個協(xié)議的邏輯算講完了。
