Paxos是一種基于消息傳遞的分布式一致性算法，由Leslie Lamport（萊斯利·蘭伯特）于1990提出。
是目前公認的解決分布式一致性問題的最有效算法之一。
### **要解決的問題及應用場景**
Paxos算法要解決的問題，可以理解為：一個異步通信的分布式系統中，如何就某一個值（決議）達成一致。而此處異步通信是指，消息在網絡傳輸過程中存在丟失、超時、亂序現象。
其典型應用場景為：
在一個分布式系統中，如果各節點初始狀態一致，而且每個節點執行相同的命令序列，那么最后就可以得到一個一致的狀態。
為了保證每個節點執行相同的命令序列，即需要在每一條指令上執行一致性算法（如Paxos算法），來保證每個節點指令一致。
### **概念定義**
Proposal：為了就某一個值達成一致而發起的提案，包括提案編號和提案的值。
涉及角色如下：
* Proposer：提案發起者，為了就某一個值達成一致，Proposer可以以任意速度、發起任意數量的提案，可以停止或重啟。
* Acceptor：提案批準者，負責處理接收到的提案，響應、作出承諾、或批準提案。
* Learner：提案學習者，可以從Acceptor處獲取已被批準的提案。
### **約定**
Paxos需要遵循如下約定：
* 1、一個Acceptor必須批準它收到的第一個提案。
* 2、如果編號為n的提案被批準了，那么所有編號大于n的提案，其值必須與編號為n的提案的值相同。
### **算法描述**
階段一：準備階段
* 1、Proposer選擇一個提案編號n，向Acceptor廣播Prepare(n)請求。
* 2、Acceptor接收到Prepare(n)請求，
如果編號n大于之前已經響應的所有Prepare請求的編號，
那么將之前批準過的最大編號的提案反饋給Proposer，并承諾不再接收編號比n小的提案。
否則不予理會。
階段二：批準階段
* 1、Proposer收到半數以上的Acceptor響應后，
如果響應中不包含任何提案，那么將提案編號n和自己的值，作為提案發送Accept請求給Acceptor。
否則將編號n，與收到的響應中編號最大的提案的值，作為提案發送Accept請求給Acceptor。
* 2、Acceptor收到編號為n的Accept請求，
只要Acceptor尚未對編號大于n的Prepare請求做出響應，就可以批準這個提案。
### **死循環問題**
如果Proposer1提出編號為n1的提案，并完成了階段一。
與此同時Proposer2提出了編號為n2的提案，n2>n1，同樣也完成了階段一。
于是Acceptor承諾不再批準編號小于n2的提案，當Proposer1進入階段二時，將會被忽略。
同理，此時，Proposer1可以提出編號為n3的提案，n3>n2，又會導致Proposer2的編號為n2的提案進入階段二時被忽略。
以此類推，將進入死循環。
解決辦法：
可以選擇一個Proposer作為主Proposer，并約定只有主Proposer才可以提出提案。
因此，只要主Proposer可以與過半的Acceptor保持通信，那么但凡主Proposer提出的編號更高的提案，均會被批準。
### **Learner**
一旦Acceptor批準了某個提案，即將該提案發給所有的Learner。
為了避免大量通信，Acceptor也可以將批準的提案，發給主Learner，由主Learner分發給其他Learner。
考慮到主Learner單點問題，也可以考慮Acceptor將批準的提案，發給主Learner組，由主Learner組分發給其他Learner。
### 參考文檔
* [Paxos Made Simple（中文翻譯版）](https://github.com/oldratlee/translations/tree/master/paxos-made-simple)
* [微信自研生產級paxos類庫PhxPaxos實現原理介紹](https://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e#rd)
* [【原創】一步一步理解Paxos算法](https://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D)
### **后記**
Paxos算法相對難以理解和實現，因此后來又出現了更容易理解和實現的Raft算法。
