前言

如果世界上只有一種分布式一致性算法，那就是Paxos。Paxos是出了名的晦澀難懂。
Paxos有點(diǎn)類似2PC和3PC，但是它解決了這兩種算法存在的問題。
先簡要介紹下2PC和3PC的做法和缺陷：

兩階段提交（2PC）

從名字上可以看出兩階段提交分為兩個(gè)階段：Propose和Commit。

• Propose階段：
  • 協(xié)調(diào)者：發(fā)起提議；
  • 投票者：同意或否決提議；
• Commit階段：
  • 協(xié)調(diào)者：根據(jù)提議發(fā)起最終commit；

  • 投票者：進(jìn)行最終的commit；

    
    
    兩階段提交

缺點(diǎn)：2PC不能處理fail-stop問題，即當(dāng)在第二階段時(shí)，如果協(xié)調(diào)者和其中一個(gè)投票者（voter3）crash了，那其他投票者將會一直阻塞等待直到接收到消息為止，這個(gè)時(shí)候就需要人工手動重啟協(xié)調(diào)者；在這種情況下，其他投票者不能區(qū)分第一階段中voter3是反對了提議還是同意了提議。

三階段提交（3PC）

3PC解決了上述2PC的問題，把Commit階段分成了PreCommit和Commit結(jié)算，相當(dāng)于在Commit操作之前加了個(gè)屏障，這個(gè)屏障相當(dāng)于告訴所有投票者，所有投票者都收到了propose的結(jié)果；當(dāng)協(xié)調(diào)者在PreCommit之前crash，則voters可以認(rèn)為不是所有voters收到propose結(jié)果，從而放棄commit或者選擇新的協(xié)調(diào)者；如果協(xié)調(diào)者在PreCommit之后crash，則每個(gè)voter可以放心的Commit，因?yàn)橐呀?jīng)默認(rèn)所有voters都收到propose結(jié)果了。
缺點(diǎn)：3PC可以處理fail-stop的問題，但是不能處理網(wǎng)絡(luò)劃分和fail-recover問題。
網(wǎng)絡(luò)劃分：當(dāng)有多個(gè)機(jī)器處于不同的網(wǎng)絡(luò)中，并且網(wǎng)絡(luò)之間不能通信，那協(xié)調(diào)者crash之后，兩個(gè)網(wǎng)絡(luò)會選出不同的新的協(xié)調(diào)者。
fail-recover：當(dāng)協(xié)調(diào)者crash之后，選出新的協(xié)調(diào)者；當(dāng)老的協(xié)調(diào)者重啟后，新老協(xié)調(diào)者對同一個(gè)投票者可能發(fā)送不同的指令，投票者的狀態(tài)出現(xiàn)分歧。

Paxos

概念

Paxos is a mechanism for achieving consensus on a single value over unreliable communication channels.

簡單的來說就是：Paxos就是在一個(gè)不穩(wěn)定的網(wǎng)絡(luò)環(huán)境中對一個(gè)值達(dá)成一致。

Paxos解決的問題

Paxos誕生于古希臘Paxos島上的多個(gè)法官在一個(gè)大廳對一個(gè)議案進(jìn)行表決，如何達(dá)成統(tǒng)一結(jié)果的故事。
Paxos解決的問題是如果在一個(gè)機(jī)器宕機(jī)或者網(wǎng)絡(luò)異常等異常的分布式系統(tǒng)中，快速且正確的再集群內(nèi)部對某個(gè)數(shù)據(jù)值達(dá)成一致，并且保證異常不會破壞整個(gè)系統(tǒng)的一致性。（Paxos沒辦法抵抗惡意行為的節(jié)點(diǎn)，比如一個(gè)節(jié)點(diǎn)故意返回一個(gè)相反的結(jié)果，Paxos沒辦法解決這樣的問題，因此Paxos沒辦法解決拜占庭將軍問題，除非加上各種校驗(yàn)）。

協(xié)議過程

基本角色

Paxos協(xié)議有三個(gè)角色：

• Proposer：提議發(fā)起者；
• Acceptor：提議接受者；
• Learner：提議學(xué)習(xí)者；

協(xié)議推導(dǎo)過程

分布式一致性問題：
假設(shè)有一組可以提出value的進(jìn)程集合；一致性算法需要保證提出的這么多的value中，只有一個(gè)value被選定，其他進(jìn)程都應(yīng)該能學(xué)習(xí)到這個(gè)被選定的值；這樣所有的進(jìn)程都最終保存相同的值。

分布式一致性基本要求：
安全性：只有被提出的值才能被選定，只有一個(gè)value被選定；
活性：值最終會被選擇，并且所有進(jìn)程都會最終學(xué)習(xí)到這個(gè)值；

推導(dǎo)過程：
Proposer是提議的發(fā)起者，不能決定最終選擇的值，因此我們從Acceptor角色看起；
假設(shè)只有一個(gè)Acceptor，只要Acceptor接收到第一個(gè)提議，該提議就被選定，這樣可以保證只有一個(gè)value被選定，但是如果機(jī)器宕機(jī)了，這唯一的Acceptor就不工作了，達(dá)不到問題的最終結(jié)果；因此必須有多個(gè)Acceptor。（paxos協(xié)議解決了機(jī)器宕機(jī)的問題）

如果是多個(gè)Acceptor的情況，怎么保證多個(gè)Proposer和多個(gè)Acceptor下選定一個(gè)唯一的value?
假設(shè)Acceptor只要接收到第一個(gè)提議，就選中；則每個(gè)Acceptor都會選中一個(gè)唯一的value；但是由于多個(gè)Proposer提出的value會有不同，這樣根據(jù)不同的網(wǎng)絡(luò)速度，每個(gè)Acceptor選中的值不一樣，不成立。
因此，Acceptor選擇第一個(gè)值的約束不成立。這就意味著，Acceptor不能單純的選擇第一個(gè)值，那么提議的值必然是要有區(qū)分，這樣才能區(qū)分Acceptor接收的是哪個(gè)值。

提議的提案={提議的值+提議的編號}。

由于Acceptor不單純選擇第一條提案，那么Acceptor就是可以接收多條提案，并從中選擇一條作為最終值，如果有N個(gè)節(jié)點(diǎn)的Acceptor，要保證N個(gè)節(jié)點(diǎn)選定的是同一個(gè)值，這樣的概率非常低，因此有了另一個(gè)約定：

Acceptor可以接收多個(gè)提案，但是不需要全部都是同一個(gè)值，而是半數(shù)以上是同一個(gè)值，就最終確定這個(gè)值，就是典型的少數(shù)服從多數(shù)的原則。

有了少數(shù)服從多數(shù)的原則，我們就可以標(biāo)記多數(shù)選擇的值為最終的一致值；但是少數(shù)服從多數(shù)還會帶來一個(gè)問題：如果有三個(gè)節(jié)點(diǎn)選擇了提案1；三個(gè)節(jié)點(diǎn)選擇了提案2；其余都是小眾；那就出現(xiàn)了平票的場景。這樣的場景最終該選擇哪個(gè)提案？
這個(gè)就需要決定提案1和提案2的優(yōu)先級；因此提議的編號我們設(shè)置成自增。這樣就誕生了一個(gè)約定：

如果一個(gè)編號的提議值V被選擇，那么每個(gè)編號更高（編號是自增的）的被Acceptor接受的提案的值必須是V。

協(xié)議描述

基于上述的約定，Paxos算法大致如下，和兩階段有點(diǎn)類似：

• 第一階段：
• Proposer選擇一個(gè)提案編號N，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求；
• 如果一個(gè)Acceptor接收到提案編號N，并且這個(gè)N大于該Acceptor已經(jīng)響應(yīng)過的所有編號；那么它就會將已經(jīng)響應(yīng)的最大編號的值返回給Proposer；同時(shí)該Acceptor承諾不再接收比N小的提案；
• 第二階段：
• 如果Proposer收到半數(shù)以上的Acceptor對其發(fā)出的編號為N的Prepare請求響應(yīng)，那么它就會發(fā)送一個(gè)[N,V]的Accept請求給半數(shù)以上的Acceptor。其中V就是響應(yīng)編號中最大的提案的那個(gè)值。如果沒有提案，則Proposer自行決定。
• 如果Acceptor收到一個(gè)針對編號為N的提案的Accept的請求，只要該Acceptor沒有對比N大的Prepare請求做過響應(yīng)，它就接收該提案。

Paxos過程

Learner角色

如果計(jì)算機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)非常多的話，廣播一次所有節(jié)點(diǎn)將消耗大量的性能；因此我們可以只適用一部分的節(jié)點(diǎn)應(yīng)用Paxos協(xié)議；然后當(dāng)Acceptor接受最終提案后，就將最終的提案大宋給Learner；Learner的做法有好幾種：

• 提案發(fā)給所有Learner；
• 提案發(fā)給一個(gè)主Learner，然后主Learner再發(fā)給其余Learner；
• 提案發(fā)給一個(gè)Learner集合；然后集合再發(fā)給其他Learner；
  幾種做法各有優(yōu)缺點(diǎn)，這里不詳細(xì)討論。

主Proposer

上述的協(xié)議保證了基本要求中的安全性；但是還存在活性的問題：
如果兩個(gè)Proposer先后提出了順序遞增的提案，那么整個(gè)過程將陷入一個(gè)死循環(huán)中；
比如Proposer1提出了N=1的提案完成了第一階段；這個(gè)時(shí)候Proposer2提出了N=2的提案也繼續(xù)完成了第一階段；那么這個(gè)時(shí)候Proposer1進(jìn)行第二階段會失敗，它會再次發(fā)起N=3的提案；Proposer2進(jìn)行第二階段也失敗，它會進(jìn)行N=4的提案；這樣就會不停的死循環(huán)下去。
因此，Proposer也需要進(jìn)行一個(gè)主次的分別。

協(xié)議證明

Paxos協(xié)議最終解決了當(dāng)一個(gè)提議被多數(shù)接受后，這個(gè)提議的值被選定；那么這個(gè)值就是分布式一致的；后續(xù)所有進(jìn)程選擇的都是同一個(gè)值。
其實(shí)，Paxos就是一個(gè)數(shù)學(xué)問題，我們來看下數(shù)學(xué)證明：

原命題

如果一個(gè)提議{N0,V0}被多數(shù)Acceptor接受，那么不會存在提議{N1,V1}被大多數(shù)Acceptor接受，其中N0<N1，并且V0!=V1；

證明

不妨用反證法：
假設(shè)存在{N1,V1}符合條件，并且N1是滿足條件最小的提議編號。
那么提議N0，N0+1，N0+2 。。。。N1-1編號對應(yīng)的值都為V0；
由于存在{N1,V1}，說明N1被半數(shù)以上的Acceptor接受，并承諾不會接受比N1小的編號；
又因?yàn)榇嬖趝N0,V0}，說明N0也被半數(shù)以上的Acceptor接受，并承諾不會接受比N0小的編號；
所以，存在一個(gè)Acceptor即接受了N1，又接受了N0；
由Paxos協(xié)議得知，這個(gè)Acceptor一定是先接受了N0，再接受了N1；
所以在發(fā)出{N1,V1}這個(gè)提議的Proposer在發(fā)出{N1,V1}之前，有一個(gè)共識；必然存在一個(gè)N>=N0，并且值為V0的提議被接受；這個(gè)時(shí)候這個(gè)Proposer會從所有的Acceptor返回值中選擇一個(gè)編號最大的作為發(fā)送的請求；因此會選擇一個(gè)N>=N0,并且值為編號最大的值V0；
因此，就有V0==V1；矛盾，所以不存在該{N1,V1};

參考文檔

[1] Paxos made simple論文
[2] The Part-Time Parliament論文