前言
如果世界上只有一種分布式一致性算法谭网，那就是Paxos裕坊。Paxos是出了名的晦澀難懂滋饲。
Paxos有點類似2PC和3PC，但是它解決了這兩種算法存在的問題躲雅。
先簡要介紹下2PC和3PC的做法和缺陷：
兩階段提交（2PC）
從名字上可以看出兩階段提交分為兩個階段：Propose和Commit鼎姊。
- Propose階段：
- 協(xié)調(diào)者：發(fā)起提議；
- 投票者：同意或否決提議相赁；
- Commit階段：
- 協(xié)調(diào)者：根據(jù)提議發(fā)起最終commit相寇；
-
投票者：進(jìn)行最終的commit；
兩階段提交
缺點：2PC不能處理fail-stop問題噪生，即當(dāng)在第二階段時裆赵，如果協(xié)調(diào)者和其中一個投票者（voter3）crash了，那其他投票者將會一直阻塞等待直到接收到消息為止跺嗽，這個時候就需要人工手動重啟協(xié)調(diào)者战授；在這種情況下，其他投票者不能區(qū)分第一階段中voter3是反對了提議還是同意了提議桨嫁。
三階段提交（3PC）
3PC解決了上述2PC的問題植兰，把Commit階段分成了PreCommit和Commit結(jié)算，相當(dāng)于在Commit操作之前加了個屏障璃吧，這個屏障相當(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，則每個voter可以放心的Commit毡咏，因為已經(jīng)默認(rèn)所有voters都收到propose結(jié)果了驮宴。
缺點：3PC可以處理fail-stop的問題，但是不能處理網(wǎng)絡(luò)劃分和fail-recover問題呕缭。
網(wǎng)絡(luò)劃分：當(dāng)有多個機(jī)器處于不同的網(wǎng)絡(luò)中堵泽，并且網(wǎng)絡(luò)之間不能通信，那協(xié)調(diào)者crash之后恢总，兩個網(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)者對同一個投票者可能發(fā)送不同的指令，投票者的狀態(tài)出現(xiàn)分歧滋戳。
Paxos
概念
Paxos is a mechanism for achieving consensus on a single value over unreliable communication channels.
簡單的來說就是：Paxos就是在一個不穩(wěn)定的網(wǎng)絡(luò)環(huán)境中對一個值達(dá)成一致钻蔑。
Paxos解決的問題
Paxos誕生于古希臘Paxos島上的多個法官在一個大廳對一個議案進(jìn)行表決，如何達(dá)成統(tǒng)一結(jié)果的故事奸鸯。
Paxos解決的問題是如果在一個機(jī)器宕機(jī)或者網(wǎng)絡(luò)異常等異常的分布式系統(tǒng)中，快速且正確的再集群內(nèi)部對某個數(shù)據(jù)值達(dá)成一致可帽，并且保證異常不會破壞整個系統(tǒng)的一致性娄涩。（Paxos沒辦法抵抗惡意行為的節(jié)點，比如一個節(jié)點故意返回一個相反的結(jié)果映跟，Paxos沒辦法解決這樣的問題蓄拣，因此Paxos沒辦法解決拜占庭將軍問題，除非加上各種校驗）努隙。
協(xié)議過程
基本角色
Paxos協(xié)議有三個角色：
- Proposer：提議發(fā)起者球恤；
- Acceptor：提議接受者；
- Learner：提議學(xué)習(xí)者荸镊；
協(xié)議推導(dǎo)過程
分布式一致性問題：
假設(shè)有一組可以提出value的進(jìn)程集合咽斧；一致性算法需要保證提出的這么多的value中，只有一個value被選定躬存，其他進(jìn)程都應(yīng)該能學(xué)習(xí)到這個被選定的值张惹；這樣所有的進(jìn)程都最終保存相同的值。
分布式一致性基本要求：
安全性：只有被提出的值才能被選定岭洲，只有一個value被選定宛逗；
活性：值最終會被選擇，并且所有進(jìn)程都會最終學(xué)習(xí)到這個值盾剩；
推導(dǎo)過程：
Proposer是提議的發(fā)起者雷激，不能決定最終選擇的值替蔬，因此我們從Acceptor角色看起；
假設(shè)只有一個Acceptor屎暇，只要Acceptor接收到第一個提議承桥，該提議就被選定，這樣可以保證只有一個value被選定恭垦，但是如果機(jī)器宕機(jī)了快毛，這唯一的Acceptor就不工作了，達(dá)不到問題的最終結(jié)果番挺；因此必須有多個Acceptor唠帝。（paxos協(xié)議解決了機(jī)器宕機(jī)的問題）
如果是多個Acceptor的情況，怎么保證多個Proposer和多個Acceptor下選定一個唯一的value?
假設(shè)Acceptor只要接收到第一個提議玄柏，就選中襟衰；則每個Acceptor都會選中一個唯一的value；但是由于多個Proposer提出的value會有不同粪摘，這樣根據(jù)不同的網(wǎng)絡(luò)速度瀑晒，每個Acceptor選中的值不一樣，不成立徘意。
因此苔悦，Acceptor選擇第一個值的約束不成立。這就意味著椎咧，Acceptor不能單純的選擇第一個值玖详，那么提議的值必然是要有區(qū)分，這樣才能區(qū)分Acceptor接收的是哪個值勤讽。
提議的提案={提議的值+提議的編號}蟋座。
由于Acceptor不單純選擇第一條提案，那么Acceptor就是可以接收多條提案脚牍，并從中選擇一條作為最終值向臀，如果有N個節(jié)點的Acceptor，要保證N個節(jié)點選定的是同一個值诸狭，這樣的概率非常低券膀，因此有了另一個約定：
Acceptor可以接收多個提案，但是不需要全部都是同一個值作谚，而是半數(shù)以上是同一個值三娩，就最終確定這個值，就是典型的少數(shù)服從多數(shù)的原則妹懒。
有了少數(shù)服從多數(shù)的原則雀监，我們就可以標(biāo)記多數(shù)選擇的值為最終的一致值；但是少數(shù)服從多數(shù)還會帶來一個問題：如果有三個節(jié)點選擇了提案1；三個節(jié)點選擇了提案2会前；其余都是小眾好乐；那就出現(xiàn)了平票的場景。這樣的場景最終該選擇哪個提案瓦宜？
這個就需要決定提案1和提案2的優(yōu)先級蔚万；因此提議的編號我們設(shè)置成自增。這樣就誕生了一個約定：
如果一個編號的提議值V被選擇临庇，那么每個編號更高（編號是自增的）的被Acceptor接受的提案的值必須是V反璃。
協(xié)議描述
基于上述的約定，Paxos算法大致如下假夺，和兩階段有點類似：
- 第一階段：
- Proposer選擇一個提案編號N淮蜈，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求；
- 如果一個Acceptor接收到提案編號N已卷，并且這個N大于該Acceptor已經(jīng)響應(yīng)過的所有編號梧田；那么它就會將已經(jīng)響應(yīng)的最大編號的值返回給Proposer；同時該Acceptor承諾不再接收比N小的提案侧蘸；
- 第二階段：
- 如果Proposer收到半數(shù)以上的Acceptor對其發(fā)出的編號為N的Prepare請求響應(yīng)裁眯，那么它就會發(fā)送一個[N,V]的Accept請求給半數(shù)以上的Acceptor。其中V就是響應(yīng)編號中最大的提案的那個值讳癌。如果沒有提案穿稳，則Proposer自行決定。
- 如果Acceptor收到一個針對編號為N的提案的Accept的請求晌坤，只要該Acceptor沒有對比N大的Prepare請求做過響應(yīng)司草，它就接收該提案。
Learner角色
如果計算機(jī)網(wǎng)絡(luò)中節(jié)點非常多的話泡仗，廣播一次所有節(jié)點將消耗大量的性能；因此我們可以只適用一部分的節(jié)點應(yīng)用Paxos協(xié)議猜憎；然后當(dāng)Acceptor接受最終提案后娩怎，就將最終的提案大宋給Learner；Learner的做法有好幾種：
- 提案發(fā)給所有Learner胰柑；
- 提案發(fā)給一個主Learner截亦，然后主Learner再發(fā)給其余Learner；
- 提案發(fā)給一個Learner集合柬讨；然后集合再發(fā)給其他Learner崩瓤；
幾種做法各有優(yōu)缺點，這里不詳細(xì)討論踩官。
主Proposer
上述的協(xié)議保證了基本要求中的安全性却桶；但是還存在活性的問題：
如果兩個Proposer先后提出了順序遞增的提案，那么整個過程將陷入一個死循環(huán)中；
比如Proposer1提出了N=1的提案完成了第一階段颖系；這個時候Proposer2提出了N=2的提案也繼續(xù)完成了第一階段嗅剖；那么這個時候Proposer1進(jìn)行第二階段會失敗，它會再次發(fā)起N=3的提案嘁扼；Proposer2進(jìn)行第二階段也失敗信粮，它會進(jìn)行N=4的提案；這樣就會不停的死循環(huán)下去趁啸。
因此强缘，Proposer也需要進(jìn)行一個主次的分別。
協(xié)議證明
Paxos協(xié)議最終解決了當(dāng)一個提議被多數(shù)接受后不傅，這個提議的值被選定旅掂；那么這個值就是分布式一致的；后續(xù)所有進(jìn)程選擇的都是同一個值蛤签。
其實辞友，Paxos就是一個數(shù)學(xué)問題，我們來看下數(shù)學(xué)證明：
原命題
如果一個提議{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小的編號扔字；
又因為存在{N0,V0}囊嘉，說明N0也被半數(shù)以上的Acceptor接受，并承諾不會接受比N0小的編號革为；
所以扭粱，存在一個Acceptor即接受了N1，又接受了N0震檩；
由Paxos協(xié)議得知琢蛤，這個Acceptor一定是先接受了N0，再接受了N1；
所以在發(fā)出{N1,V1}這個提議的Proposer在發(fā)出{N1,V1}之前虐块，有一個共識俩滥；必然存在一個N>=N0，并且值為V0的提議被接受贺奠；這個時候這個Proposer會從所有的Acceptor返回值中選擇一個編號最大的作為發(fā)送的請求霜旧；因此會選擇一個N>=N0,并且值為編號最大的值V0；
因此儡率，就有V0==V1挂据；矛盾，所以不存在該{N1,V1};
參考文檔
[1] Paxos made simple論文
[2] The Part-Time Parliament論文
