參考：
https://my.oschina.net/linlifeng/blog/78918
http://blog.csdn.net/cnh294141800/article/details/53768464

Paxos算法是分布式中一個(gè)著名的一致性算法紧憾。它的假設(shè)前提是风罩，在分布式系統(tǒng)中進(jìn)程之間的通信會(huì)出現(xiàn)丟失、延遲、重復(fù)等現(xiàn)象，但不會(huì)出現(xiàn)傳錯(cuò)的現(xiàn)象。Paxos算法就是為了保證在這樣的系統(tǒng)中進(jìn)程間基于消息傳遞就某個(gè)值達(dá)成一致壮韭。要理解paxos算法最好還是看作者本人(Leslie Lamport)的論文《The Part-Time Parliament》。在這里只是簡單地介紹paxos最核心的思想纹因，其實(shí)它還有很多的內(nèi)容喷屋。

Paxos算法的目的

Paxos算法的目的是為了解決分布式環(huán)境下一致性的問題。
多個(gè)節(jié)點(diǎn)并發(fā)操縱數(shù)據(jù)瞭恰，如何保證在讀寫過程中數(shù)據(jù)的一致性屯曹，并且解決方案要能適應(yīng)分布式環(huán)境下的不可靠性（系統(tǒng)如何就一個(gè)值達(dá)到統(tǒng)一）

Paxos的兩個(gè)組件

提議者和決議者是這里最重要的兩個(gè)角色，paxos最核心的算法就是定義他們之間的通訊規(guī)則來保證某個(gè)變量在分布式系統(tǒng)中的一致性惊畏。

Proposer

提議發(fā)起者恶耽，處理客戶端請求，將客戶端的請求發(fā)送到集群中颜启，以便決定這個(gè)值是否可以被批準(zhǔn)偷俭。

Acceptor

提議批準(zhǔn)者，負(fù)責(zé)處理接收到的提議缰盏，他們的回復(fù)就是一次投票涌萤。會(huì)存儲(chǔ)一些狀態(tài)來決定是否接收一個(gè)值

Paxos有兩個(gè)原則

1. 安全原則---保證不能做錯(cuò)的事
   a) 針對某個(gè)實(shí)例的表決只能有一個(gè)值被批準(zhǔn)，不能出現(xiàn)一個(gè)被批準(zhǔn)的值被另一個(gè)值覆蓋的情況口猜；(假設(shè)有一個(gè)值被多數(shù)Acceptor批準(zhǔn)了负溪，那么這個(gè)值就只能被學(xué)習(xí))
   b) 每個(gè)節(jié)點(diǎn)只能學(xué)習(xí)到已經(jīng)被批準(zhǔn)的值，不能學(xué)習(xí)沒有被批準(zhǔn)的值济炎。
2. 存活原則---只要有多數(shù)服務(wù)器存活并且彼此間可以通信川抡，最終都要做到的下列事情：
   a) 最終會(huì)批準(zhǔn)某個(gè)被提議的值；
   b) 一個(gè)值被批準(zhǔn)了冻辩，其他服務(wù)器最終會(huì)學(xué)習(xí)到這個(gè)值猖腕。

Paxos的兩個(gè)階段

第一階段（prepare）

1. 獲取一個(gè)proposal number, n；
2. 提議者向所有節(jié)點(diǎn)廣播prepare(n)請求恨闪；
3. 接收者（Acceptors比較善變倘感，如果還沒最終認(rèn)可一個(gè)值，它就會(huì)不斷認(rèn)同提案號最大的那個(gè)方案）比較n和minProposal咙咽，如果n>minProposal,表示有更新的提議minProposal=n老玛；如果此時(shí)該接受者并沒有認(rèn)可一個(gè)最終值，那么認(rèn)可這個(gè)提案，返回OK蜡豹。如果此時(shí)已經(jīng)有一個(gè)accptedValue, 將返回(acceptedProposal,acceptedValue)麸粮；
4. 提議者接收到過半數(shù)請求后，如果發(fā)現(xiàn)有acceptedValue返回镜廉，表示有認(rèn)可的提議弄诲，保存最高acceptedProposal編號的acceptedValue到本地

第二階段(Accept)

5. 廣播accept(n,value)到所有節(jié)點(diǎn)；
6. 接收者比較n和minProposal娇唯，如果n>=minProposal,則acceptedProposal=minProposal=n齐遵，acceptedValue=value，本地持久化后塔插，返回梗摇；
   否則，拒絕并且返回minProposal
7. 提議者接收到過半數(shù)請求后想许，如果發(fā)現(xiàn)有返回值>n伶授，表示有更新的提議，跳轉(zhuǎn)1（重新發(fā)起提議）流纹；否則value達(dá)成一致糜烹。

提議者是提出議案的人。每個(gè)議案都有一個(gè)議案號捧颅，議案號是區(qū)別不同議案的唯一標(biāo)識景图，而且議案號是有大小次序的较雕。這里的提議者不像我們真實(shí)世界里的提議者碉哑，這里的提議者提的議案內(nèi)容不能隨心所欲。提議者和決議者要遵循下面的規(guī)則：

1） 提議者先給議案決定一個(gè)議案號亮蒋，注意整個(gè)系統(tǒng)中議案號都不能重復(fù)的扣典。然后發(fā)消息給所有決議者，告訴他們我要提出第幾號議案慎玖。

第一階段贮尖，提議者甲向決議者A、B趁怔、C湿硝、D、E润努、F关斜、G發(fā)出議案號16的消息。

2） 決議者收到提議者發(fā)來的議案號后先看這個(gè)議案號是否是自己收到的所有議案號中最大的铺浇。如果不是痢畜，就不予理會(huì)；如果是，就把自己最后一次投票的議案發(fā)回去丁稀，如果沒投過議案就回復(fù)沒投過議案吼拥。

第二階段，決議者收到甲發(fā)來的議案號16后根據(jù)自己的情況作出回復(fù)

A线衫、D未投過任何議案所以回復(fù)(null)

B最后一次投了2號議案所以回復(fù)(2,α)

C凿可、F最后一次投了5號議案所以回復(fù)(5,β)

E的最大議案號是21所以不用回復(fù)

G由于網(wǎng)絡(luò)原因沒收到消息

3） 當(dāng)提議者收到過半回復(fù)后才能決定議案的內(nèi)容。在所有回復(fù)中議案號最大的那個(gè)議案的內(nèi)容就定為當(dāng)前議案的內(nèi)容授账。如果都回復(fù)沒投過議案矿酵，那議案內(nèi)容就由自己定了。如果只收到不過半數(shù)的回復(fù)矗积，那么這個(gè)過程就這樣結(jié)束了全肮。確定議案內(nèi)容后就要把議案發(fā)給所有決議者。到此提議者的工作就可以結(jié)束了棘捣。

第三階段辜腺，甲根據(jù)回復(fù)確定16號議案的內(nèi)容，然后正式提出16號議案乍恐。

甲收到過半數(shù)人的回復(fù)评疗，回復(fù)的內(nèi)容有(null)、(2,α)茵烈、(5,β)百匆，其中5是最大的議案號，所以16號議案的內(nèi)容就定為β,接著甲就把(16,β)發(fā)出去呜投。

4） 決議者收到議案后加匈，就要對它進(jìn)行投票。如果這個(gè)議案號是自己收到的所以議案號中最大的仑荐，就要投這個(gè)議案的票雕拼；否則就不予理會(huì)。這里的投票沒有反對或贊成的類型之分粘招。也就是可以認(rèn)為只有贊成票啥寇。到此決議者的工作就可以結(jié)束了。

第四階段洒扎，決議者收到16號議案并對它投票辑甜。

A、B袍冷、C磷醋、G收到(16,β)后，由于16號是他們的最大號难裆，所以會(huì)給這個(gè)議案投票

D子檀、E镊掖、F收到(16,β)后，由于21號是他們的最大號褂痰，所以不投票亩进。

這個(gè)算法保證了某個(gè)變量在分布式系統(tǒng)中要么沒有值，要么就只會(huì)有一個(gè)值缩歪。只要某個(gè)議案在某一刻有過半數(shù)的人投票归薛，那么這個(gè)值就永遠(yuǎn)定下來了。

如上圖匪蝙，15號議案(內(nèi)容是β)有了過半數(shù)的投票主籍，那么它的下一號16號議案內(nèi)容只能是β了，因?yàn)樵诘谌A段收到的回復(fù)如果過半數(shù)逛球，那么其中一定有(15,β)千元，而15肯定是回復(fù)中最大的號，所以內(nèi)容只能是β颤绕。而下下一號21號議案內(nèi)容也只能是β幸海，因?yàn)樗那皟蓚€(gè)議案的內(nèi)容都是β，如果收到的回復(fù)過半數(shù)的話肯定包含(15,β)或(16,β)奥务，而他們都是最大的兩個(gè)物独，所以內(nèi)容也只能是β了÷仍幔可以證明其后的所有議案內(nèi)容都是β挡篓。雖然paxos算法可以保證不會(huì)有兩個(gè)值，但顯然不能保證一定會(huì)有值帚称。這也是理論上(CAP理論)不能解決的問題官研。

這里的算法是有改動(dòng)的，提議者和決議者都還有后續(xù)的處理世杀，而且關(guān)于上面的“過半數(shù)的決議者”也并不是Paxos本身的描述阀参。Paxos本身定義的是一個(gè)更一般的“大多數(shù)”集合肝集，每個(gè)議案都有一個(gè)“大多數(shù)”的決議者集合S瞻坝，這些集合是兩兩相交的，對于每個(gè)議案杏瞻，在第三階段要收到S中所有決議者的回復(fù)才能繼續(xù)下去所刀。如果某個(gè)議案得到相應(yīng)S的全體投票，那么這個(gè)值就這么定下來了捞挥。

我們再來看一個(gè)例子

假設(shè)的3軍問題

1. 1支紅軍在山谷里扎營浮创，在周圍的山坡上駐扎著3支藍(lán)軍；
2. 紅軍比任意1支藍(lán)軍都要強(qiáng)大砌函；如果1支藍(lán)軍單獨(dú)作戰(zhàn)斩披，紅軍勝溜族；如果2支或以上藍(lán)軍同時(shí)進(jìn)攻，藍(lán)軍勝垦沉；
3. 三支藍(lán)軍需要同步他們的進(jìn)攻時(shí)間煌抒；但他們惟一的通信媒介是派通信兵步行進(jìn)入山谷，在那里他們可能被俘虜厕倍，從而將信息丟失寡壮；或者為了避免被俘虜，可能在山谷停留很長時(shí)間讹弯；
4. 每支軍隊(duì)有1個(gè)參謀負(fù)責(zé)提議進(jìn)攻時(shí)間况既；每支軍隊(duì)也有1個(gè)將軍批準(zhǔn)參謀提出的進(jìn)攻時(shí)間；很明顯组民，1個(gè)參謀提出的進(jìn)攻時(shí)間需要獲得至少2個(gè)將軍的批準(zhǔn)才有意義棒仍；
5. 問題：是否存在一個(gè)協(xié)議，能夠使得藍(lán)軍同步他們的進(jìn)攻時(shí)間臭胜？

接下來以兩個(gè)假設(shè)的場景來演繹BasicPaxos降狠；參謀和將軍需要遵循一些基本的規(guī)則

1. 參謀以兩階段提交（prepare/commit）的方式來發(fā)起提議，在prepare階段需要給出一個(gè)編號庇楞；
2. 在prepare階段產(chǎn)生沖突榜配，將軍以編號大小來裁決，編號大的參謀勝出吕晌；
3. 參謀在prepare階段如果收到了將軍返回的已接受進(jìn)攻時(shí)間蛋褥，在commit階段必須使用這個(gè)返回的進(jìn)攻時(shí)間；

兩個(gè)參謀先后提議的場景

1. 參謀1發(fā)起提議睛驳，派通信兵帶信給3個(gè)將軍烙心，內(nèi)容為（編號1）；
2. 3個(gè)將軍收到參謀1的提議乏沸，由于之前還沒有保存任何編號淫茵，因此把（編號1）保存下來，避免遺忘蹬跃；同時(shí)讓通信兵帶信回去匙瘪，內(nèi)容為（ok）；
3. 參謀1收到至少2個(gè)將軍的回復(fù)蝶缀，再次派通信兵帶信給3個(gè)將軍丹喻，內(nèi)容為（編號1，進(jìn)攻時(shí)間1）翁都；
4. 3個(gè)將軍收到參謀1的時(shí)間碍论，把（編號1，進(jìn)攻時(shí)間1）保存下來柄慰，避免遺忘鳍悠；同時(shí)讓通信兵帶信回去税娜，內(nèi)容為（Accepted）；
5. 參謀1收到至少2個(gè)將軍的（Accepted）內(nèi)容藏研，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被大家接收巧涧；
6. 參謀2發(fā)起提議，派通信兵帶信給3個(gè)將軍遥倦，內(nèi)容為（編號2）谤绳；
7. 3個(gè)將軍收到參謀2的提議，由于（編號2）比（編號1）大袒哥，因此把（編號2）保存下來缩筛，避免遺忘；又由于之前已經(jīng)接受參謀1的提議堡称，因此讓通信兵帶信回去瞎抛，內(nèi)容為（編號1，進(jìn)攻時(shí)間1）却紧；
8. 參謀2收到至少2個(gè)將軍的回復(fù)桐臊，由于回復(fù)中帶來了已接受的參謀1的提議內(nèi)容，參謀2因此不再提出新的進(jìn)攻時(shí)間晓殊，接受參謀1提出的時(shí)間断凶；

兩個(gè)參謀交叉提議的場景

1. 參謀1發(fā)起提議，派通信兵帶信給3個(gè)將軍巫俺，內(nèi)容為（編號1）认烁；
2. 3個(gè)將軍的情況如下
   a) 將軍1和將軍2收到參謀1的提議，將軍1和將軍2把（編號1）記錄下來介汹，如果有其他參謀提出更小的編號却嗡，將被拒絕；同時(shí)讓通信兵帶信回去嘹承，內(nèi)容為（ok）窗价；
   b) 負(fù)責(zé)通知將軍3的通信兵被抓，因此將軍3沒收到參謀1的提議叹卷；
3. 參謀2在同一時(shí)間也發(fā)起了提議撼港，派通信兵帶信給3個(gè)將軍，內(nèi)容為（編號2）豪娜；
4. 3個(gè)將軍的情況如下
   a) 將軍2和將軍3收到參謀2的提議餐胀，將軍2和將軍3把（編號2）記錄下來，如果有其他參謀提出更小的編號瘤载，將被拒絕；同時(shí)讓通信兵帶信回去卖擅，內(nèi)容為（ok）鸣奔；
   b) 負(fù)責(zé)通知將軍1的通信兵被抓墨技，因此將軍1沒收到參謀2的提議；
5. 參謀1收到至少2個(gè)將軍的回復(fù)挎狸，再次派通信兵帶信給有答復(fù)的2個(gè)將軍扣汪，內(nèi)容為（編號1，進(jìn)攻時(shí)間1）锨匆；
6. 2個(gè)將軍的情況如下
   a) 將軍1收到了（編號1崭别，進(jìn)攻時(shí)間1），和自己保存的編號相同恐锣，因此把（編號1茅主，進(jìn)攻時(shí)間1）保存下來；同時(shí)讓通信兵帶信回去土榴，內(nèi)容為（Accepted）诀姚；
   b) 將軍2收到了（編號1，進(jìn)攻時(shí)間1）玷禽，由于（編號1）小于已經(jīng)保存的（編號2）赫段，因此讓通信兵帶信回去，內(nèi)容為（Rejected矢赁，編號2）糯笙；
7. 參謀2收到至少2個(gè)將軍的回復(fù)，再次派通信兵帶信給有答復(fù)的2個(gè)將軍撩银，內(nèi)容為（編號2炬丸，進(jìn)攻時(shí)間2）；
8. 將軍2和將軍3收到了（編號2蜒蕾，進(jìn)攻時(shí)間2）稠炬，和自己保存的編號相同，因此把（編號2咪啡，進(jìn)攻時(shí)間2）保存下來首启，同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）撤摸；
9. 參謀2收到至少2個(gè)將軍的（Accepted）內(nèi)容毅桃，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受；
10. 參謀1只收到了1個(gè)將軍的（Accepted）內(nèi)容准夷，同時(shí)收到一個(gè)（Rejected钥飞，編號2）；參謀1重新發(fā)起提議衫嵌，派通信兵帶信給3個(gè)將軍读宙，內(nèi)容為（編號3）熬尺；
11. 3個(gè)將軍的情況如下
    a) 將軍1收到參謀1的提議讨韭，由于（編號3）大于之前保存的（編號1）框喳，因此把（編號3）保存下來坎弯；由于將軍1已經(jīng)接受參謀1前一次的提議，因此讓通信兵帶信回去桦锄，內(nèi)容為（編號1扎附，進(jìn)攻時(shí)間1）；
    b) 將軍2收到參謀1的提議结耀，由于（編號3）大于之前保存的（編號2）留夜，因此把（編號3）保存下來；由于將軍2已經(jīng)接受參謀2的提議图甜，因此讓通信兵帶信回去碍粥，內(nèi)容為（編號2，進(jìn)攻時(shí)間2）具则；
    c) 負(fù)責(zé)通知將軍3的通信兵被抓即纲，因此將軍3沒收到參謀1的提議；
12. 參謀1收到了至少2個(gè)將軍的回復(fù)博肋，比較兩個(gè)回復(fù)的編號大小低斋，選擇大編號對應(yīng)的進(jìn)攻時(shí)間作為最新的提議；參謀1再次派通信兵帶信給有答復(fù)的2個(gè)將軍匪凡，內(nèi)容為（編號3膊畴，進(jìn)攻時(shí)間2）；
13. 將軍1和將軍2收到了（編號3病游，進(jìn)攻時(shí)間2）唇跨，和自己保存的編號相同，因此保存（編號3衬衬，進(jìn)攻時(shí)間2）买猖，同時(shí)讓通信兵帶信回去，內(nèi)容為（Accepted）滋尉；
14. 參謀1收到了至少2個(gè)將軍的（accepted）內(nèi)容玉控，確認(rèn)進(jìn)攻時(shí)間已經(jīng)被多數(shù)派接受；

基本思想

Paxos主要用于保證分布式存儲(chǔ)中副本（或者狀態(tài)）的一致性狮惜。副本要保持一致高诺，那么，所有副本的更新序列就要保持一致碾篡。因?yàn)閿?shù)據(jù)的增刪改查操作一般都存在多個(gè)客戶端并發(fā)操作虱而，到底哪個(gè)客戶端先做，哪個(gè)客戶端后做开泽，這就是更新順序牡拇。如果不是分布式，那么可以利用加鎖的方法，誰先申請到鎖诅迷，誰就先操作佩番。但是在分布式條件下众旗，存在多個(gè)副本罢杉，如果依賴申請鎖+副本同步更新完畢再釋放鎖，那么需要有分配鎖的這么一個(gè)節(jié)點(diǎn)（如果是多個(gè)鎖分配節(jié)點(diǎn)贡歧，那么又出現(xiàn)分布式鎖管理的需求滩租，把鎖給哪一個(gè)客戶端又成為一個(gè)難點(diǎn)），這個(gè)節(jié)點(diǎn)又成為單點(diǎn)利朵，豈不是可靠性不行了律想，失去了分布式多副本的意義，同時(shí)性能也很差绍弟，另外技即，還會(huì)出現(xiàn)死鎖等情況。

所以樟遣，說來說去而叼，只有解決分布式條件下的一致性問題，似乎才能解決本質(zhì)問題豹悬。

Paxos解決這一問題利用的是選舉葵陵，少數(shù)服從多數(shù)的思想，只要2N+1個(gè)節(jié)點(diǎn)中瞻佛，有N個(gè)以上同意了某個(gè)決定脱篙，則認(rèn)為系統(tǒng)達(dá)到了一致，并且按照Paxos原則伤柄，最終理論上也達(dá)到了一致绊困，不會(huì)再改變。這樣的話适刀，客戶端不必與所有服務(wù)器通信秤朗，選擇與大部分通信即可；也無需服務(wù)器都全部處于工作狀態(tài)蔗彤，有一些服務(wù)器掛掉川梅，只有保證半數(shù)以上存活著，整個(gè)過程也能持續(xù)下去然遏，容錯(cuò)性相當(dāng)好贫途。