分布式一致性算法Paxos

　　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（中文翻譯版）
　　微信自研生產級paxos類庫PhxPaxos實現原理介紹
　　【原創】一步一步理解Paxos算法
?

后記

?
　　Paxos算法相對難以理解和實現，因此后來又出現了更容易理解和實現的Raft算法。
　　后續會單獨總結。