問題：

基于消息傳遞通信模型的分布式系統(tǒng)牍蜂，不可避免的會(huì)發(fā)生以下錯(cuò)誤：進(jìn)程可能會(huì)慢漾根、被殺死或者重啟，消息可能會(huì)延遲鲫竞、丟失辐怕、重復(fù)，在基礎(chǔ)Paxos場景中从绘，先不考慮可能出現(xiàn)消息篡改即拜占庭錯(cuò)誤的情況寄疏。

作用：

Paxos算法解決的問題是在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常僵井，都不會(huì)破壞決議的一致性陕截。用于解決分布式系統(tǒng)中一致性問題。
　　“與其預(yù)測未來批什，不如限制未來”农曲，這應(yīng)該是Paxos協(xié)議的核心思想

基本術(shù)語：

角色：

Proposer(提議發(fā)起者)；Acceptor(提議接受者)驻债；Learner(提議學(xué)習(xí)者)乳规；

操作：

Proposal(提案)：由proposer提出，被aceeptor批準(zhǔn)或否決合呐，包含｛編號(hào)暮的，提案值｝
Accept(批準(zhǔn)): 表示提案被acceptor批準(zhǔn)
Choose(選擇): 表示提案“被選擇”，也就是被多數(shù)acceptor批準(zhǔn)

內(nèi)容：

Value（提案值）: 提案的值淌实，議案的組成之一
　　Proposal Number（提案編號(hào)）：提案編號(hào)不能沖突冻辩，提案的組成之一

Paxos約束條件：

P1：一個(gè)acceptor必須接受（accept）第一次收到的提案。

注意P1是不完備的翩伪。如果恰好一半acceptor接受的提案具有value A，另一半接受的提案具有value B谈息，那么就無法形成多數(shù)派缘屹，無法批準(zhǔn)任何一個(gè)value。
　　約束2并不要求只批準(zhǔn)一個(gè)提案侠仇，暗示可能存在多個(gè)提案轻姿。只要提案的value是一樣的犁珠，批準(zhǔn)多個(gè)提案不違背約束2。于是可以產(chǎn)生約束P2：

P2：一旦一個(gè)具有value v的提案被批準(zhǔn)（chosen）互亮，那么之后批準(zhǔn)（chosen）的提案必須具有value v犁享。

注：通過某種方法可以為每個(gè)提案分配一個(gè)編號(hào)，在提案之間建立一個(gè)全序關(guān)系豹休，所謂“之后”都是指所有編號(hào)更大的提案炊昆。
　　如果P1和P2都能夠保證，那么約束2就能夠保證威根。
　　批準(zhǔn)一個(gè)value意味著多個(gè)acceptor接受（accept）了該value.因此凤巨，可以對(duì)P2進(jìn)行加強(qiáng)：

P2a：一旦一個(gè)具有value v的提案被批準(zhǔn)（chosen），那么之后任何acceptor再次接受（accept）的提案必須具有value v

由于通信是異步的洛搀，P2a和P1會(huì)發(fā)生沖突敢茁。如果一個(gè)value被批準(zhǔn)后，一個(gè)proposer和一個(gè)acceptor從休眠中蘇醒留美，前者提出一個(gè) 具有新的value的提案彰檬。根據(jù)P1，后者應(yīng)當(dāng)接受谎砾，根據(jù)P2a逢倍，則不應(yīng)當(dāng)接受，這中場景下P2a和P1有矛盾棺榔。于是需要換個(gè)思路瓶堕，轉(zhuǎn)而對(duì) proposer的行為進(jìn)行約束：

P2b：一旦一個(gè)具有value v的提案被批準(zhǔn)（chosen），那么以后任何proposer提出的提案必須具有value v症歇。

由于acceptor能接受的提案都必須由proposer提出郎笆，所以P2b蘊(yùn)涵了P2a，是一個(gè)更強(qiáng)的約束忘晤。
　　但是根據(jù)P2b難以提出實(shí)現(xiàn)手段宛蚓。因此需要進(jìn)一步加強(qiáng)P2b。
　　假設(shè)一個(gè)編號(hào)為m的value v已經(jīng)獲得批準(zhǔn)（chosen）设塔，來看看在什么情況下對(duì)任何編號(hào)為n（n>m）的提案都含有value v凄吏。因?yàn)閙已經(jīng)獲得批準(zhǔn)（chosen），顯然存在一個(gè)acceptors的多數(shù)派C闰蛔，他們都接受（accept）了v痕钢。考慮到任何多數(shù)派都和C具有至少 一個(gè)公共成員序六，可以找到一個(gè)蘊(yùn)涵P2b的約束P2c：

P2c：如果一個(gè)編號(hào)為n的提案具有value v任连，那么存在一個(gè)多數(shù)派，要么他們中所有人都沒有接受（accept）編號(hào)小于n 的任何提案例诀，要么他們已經(jīng)接受（accept）的所有編號(hào)小于n的提案中編號(hào)最大的那個(gè)提案具有value v随抠。

Paxos過程：

通過一個(gè)提案分為兩個(gè)階段：

1. prepare階段：

proposer(提案發(fā)起者)選擇一個(gè)提案編號(hào)n并將提案編號(hào)n請(qǐng)求發(fā)送給acceptors中的一個(gè)多數(shù)派（acceptors的一個(gè)子集）裁着；
　　acceptor收到提案編號(hào)消息后，如果提案的編號(hào)n大于之前收到的提案編號(hào)拱她，則承諾不再回復(fù)小于n的提案二驰；如果該acceptor已經(jīng)批準(zhǔn)過提案，則將自己批準(zhǔn)的提案回復(fù)給proposer秉沼；

2. 批準(zhǔn)階段：

當(dāng)一個(gè)proposer收到了多數(shù)acceptors對(duì)提案的承若（回復(fù)）后桶雀，就進(jìn)入批準(zhǔn)階段。它要向回復(fù)提案請(qǐng)求的 acceptors發(fā)送accept請(qǐng)求氧猬，如果沒有發(fā)現(xiàn)有一個(gè)acceptor接受過一個(gè)提案背犯，那么向所有的acceptor發(fā)起自己的提案（自己的值和提案編號(hào)n），否則盅抚，從所有acceptors的回包中選擇提案編號(hào)最大的提案漠魏，將該提案的值作為此次提案的值，提案編號(hào)仍然為n妄均。
　　在不違背自己向其他proposer的承諾的前提下柱锹，acceptor收到accept請(qǐng)求后即接受這個(gè)請(qǐng)求。

簡單示例：

Proposer：P1,P2, P3
　　Acceptor: A1, A2, A3

場景一：Acceptor都未接受過提案

1. P1 向A2丰包，A3發(fā)送提案編號(hào)為1,v=p1
2. P2向A1禁熏，A2發(fā)送提案編號(hào)為2,v=p2
3. P3向A2，A3發(fā)送提案編號(hào)為3,v=p3
4. t1時(shí)刻邑彪，A1瞧毙，A2接收到P2的提案，并做出承若（編號(hào)小于2的拒絕）
5. t2時(shí)刻寄症，A2宙彪，A3接收到P1的提案，由于A2已經(jīng)做過承若有巧，如拒絕該提案释漆，A3則做出承若（編號(hào)小于1的拒絕）
6. t3時(shí)刻，A2篮迎，A3收到P3的提案男图，由于編號(hào)3大于編號(hào)1，2甜橱；故A2逊笆，A3做出承若（編號(hào)小于3的拒絕）
7. t4時(shí)刻，由于P1未能收到大部分的承若岂傲，再次發(fā)起提案难裆，編號(hào)為4；A2,A3收到提案后譬胎，由于編號(hào)4為最大的編號(hào)差牛，故A2,A3做出承若（編號(hào)小于4的拒絕）
8. t5時(shí)刻，P2由于收到大部分的承若（A1堰乔，A2）偏化，向A1，A2發(fā)送批準(zhǔn)請(qǐng)求镐侯；A1批準(zhǔn)通過侦讨，而A2最后的承若是編號(hào)不能小于4，故拒絕該批準(zhǔn)請(qǐng)求苟翻；
9. t6時(shí)刻韵卤，P3收到大部分的承若（A2，A3）崇猫，向A2沈条，A3發(fā)送批準(zhǔn)請(qǐng)求；由于A2诅炉，A3最后的承若是編號(hào)不能小于4蜡歹，故都拒絕該批準(zhǔn)請(qǐng)求；
10. t7時(shí)刻涕烧，P1收到大部分的承若（A2月而，A3），向A2议纯，A3發(fā)送批準(zhǔn)請(qǐng)求父款，A2，A3都接受該批準(zhǔn)請(qǐng)求瞻凤；至此此次提案被選出來及{4,P1}（多數(shù)派的選擇）

p1.png

場景二：存在接受過提案的Acceptor

1. 初始：A2憨攒，A3已經(jīng)接受提案{5,P2}
2. P1向A1，A2發(fā)送提案編號(hào)6
3. P3向A2鲫构，A3發(fā)送提案編號(hào)7
4. t1時(shí)刻浓恶，A1，A2收到提案结笨，A1做出承若（拒絕編號(hào)小于6的提案）包晰，A2做出承若（拒絕編號(hào)小于6的提案）同 時(shí)回給P1的包含已經(jīng)接受的提案{5,P2}
5. t2時(shí)刻，A2炕吸，A3收到提案伐憾，并做出承若（拒絕編號(hào)小于7的提案），同時(shí)會(huì)給P3的回包包含已經(jīng)接受的提案{5,P2}
6. t3時(shí)刻赫模，P1收到大部分的承若树肃，給A1，A2發(fā)送批準(zhǔn)請(qǐng)求瀑罗；A1接受該請(qǐng)求胸嘴，A2由于承若的編號(hào)為7雏掠，拒絕該請(qǐng)求；
7. t4時(shí)刻劣像，P3收到大部分的承若乡话，給A2，A3發(fā)送批準(zhǔn)請(qǐng)求耳奕；A2绑青，A3都接受該提案；

p2.png

考慮：

1. 在收到的承若回包中屋群，包含已經(jīng)接受的提議闸婴，是否可以停止提議操作？
　　2. 編號(hào)如果保證有序芍躏，如果每個(gè)提議者的編號(hào)都是賦予一個(gè)較大的值邪乍，又該如何處理？

擴(kuò)展：

二階段提交（Two-phase Commit）

二階段提交也被稱為是一種協(xié)議(Protocol)对竣。在分布式系統(tǒng)中溺欧，每個(gè)節(jié)點(diǎn)雖然可以知曉自己的操作時(shí)成功或者失敗，卻無法知道其他節(jié)點(diǎn)的操作的成功或失敗柏肪。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí)姐刁，為了保持事務(wù)的ACID特性，需要引入一個(gè)作為協(xié)調(diào)者的組件來統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)烦味。因此聂使，二階段提交的算法思路可以概括為： 參與者將操作成敗通知協(xié)調(diào)者，再由協(xié)調(diào)者根據(jù)所有參與者的反饋情報(bào)決定各參與者是否要提交操作還是中止操作谬俄。

第一階段(提交請(qǐng)求階段)

協(xié)調(diào)者節(jié)點(diǎn)向所有參與者節(jié)點(diǎn)詢問是否可以執(zhí)行提交操作柏靶，并開始等待各參與者節(jié)點(diǎn)的響應(yīng)。
　　參與者節(jié)點(diǎn)執(zhí)行詢問發(fā)起為止的所有事務(wù)操作溃论，并將Undo信息和Redo信息寫入日志屎蜓。
　　各參與者節(jié)點(diǎn)響應(yīng)協(xié)調(diào)者節(jié)點(diǎn)發(fā)起的詢問。如果參與者節(jié)點(diǎn)的事務(wù)操作實(shí)際執(zhí)行成功钥勋，則它返回一個(gè)"同意"消息炬转；如果參與者節(jié)點(diǎn)的事務(wù)操作實(shí)際執(zhí)行失敗，則它返回一個(gè)"中止"消息算灸。
　　有時(shí)候扼劈，第一階段也被稱作投票階段，即各參與者投票是否要繼續(xù)接下來的提交操作菲驴。

第二階段(提交執(zhí)行階段)

成功
　　 當(dāng)協(xié)調(diào)者節(jié)點(diǎn)從所有參與者節(jié)點(diǎn)獲得的相應(yīng)消息都為"同意"時(shí)：
　　 協(xié)調(diào)者節(jié)點(diǎn)向所有參與者節(jié)點(diǎn)發(fā)出"正式提交"的請(qǐng)求荐吵。
　　 參與者節(jié)點(diǎn)正式完成操作，并釋放在整個(gè)事務(wù)期間內(nèi)占用的資源。
　　 參與者節(jié)點(diǎn)向協(xié)調(diào)者節(jié)點(diǎn)發(fā)送"完成"消息先煎。
　　 協(xié)調(diào)者節(jié)點(diǎn)收到所有參與者節(jié)點(diǎn)反饋的"完成"消息后贼涩，完成事務(wù)。
　　失敗
　　 如果任一參與者節(jié)點(diǎn)在第一階段返回的響應(yīng)消息為"終止"薯蝎，或者 協(xié)調(diào)者節(jié)點(diǎn)在第一階段的詢問超時(shí)之前無法獲取所有參與者節(jié)點(diǎn)的響應(yīng)消息時(shí)：
　　 協(xié)調(diào)者節(jié)點(diǎn)向所有參與者節(jié)點(diǎn)發(fā)出"回滾操作"的請(qǐng)求磁携。
　　 參與者節(jié)點(diǎn)利用之前寫入的Undo信息執(zhí)行回滾，并釋放在整個(gè)事務(wù)期間內(nèi)占用的資源良风。
　　 參與者節(jié)點(diǎn)向協(xié)調(diào)者節(jié)點(diǎn)發(fā)送"回滾完成"消息。
　　 協(xié)調(diào)者節(jié)點(diǎn)收到所有參與者節(jié)點(diǎn)反饋的"回滾完成"消息后闷供，取消事務(wù)烟央。
　有時(shí)候，第二階段也被稱作完成階段歪脏，因?yàn)闊o論結(jié)果怎樣疑俭，協(xié)調(diào)者都必須在此階段結(jié)束當(dāng)前事務(wù)。

參考連接

1. https://en.wikipedia.org/wiki/Paxos_(computer_science)
2. https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
3. http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
4. http://mp.weixin.qq.com/s?__biz=MjM5MDE0Mjc4MA==&mid=2650994727&idx=1&sn=913e3123bf4cc4885ce3c15bce6b7adc&chksm=bdbf00748ac88962f607394bd8af8e73182a9b011443bf2e99c9ae07372cd59ad305ec5910f8&mpshare=1&scene=1&srcid=1115H35HtSf2C7tky37d9xlW#wechat_redirect