paxos算法
常常在有關(guān)分布式的文章中看到paxos算法，于是學(xué)習(xí)了一下此經(jīng)典算法愤钾，下面記錄的是我的一些個(gè)人理解镜硕。如有不正確之處癌淮，請指正瞳氓。
角色有：
proposer acceptor learner
proposer負(fù)責(zé)提出議案，每次提案都有一個(gè)全局編號(hào)违霞，編號(hào)唯一且遞增
一些約束條件：
1.acceptor必須接受第一次的收到的提案
2.一個(gè)提案被選中必須要超過半數(shù)的acceptor接受
3.acceptor不會(huì)接受編號(hào)小于acceptedN的提案
acceptor會(huì)記錄兩個(gè)值[acceptedN,acceptedK] ，分別是接受提案的編號(hào)和接受提案的值看幼。據(jù)個(gè)人理解逗物，接受提案的值只會(huì)在第二階段accept階段被記錄欠橘。
1.第一階段，prepare階段
1.a??proposer向大多數(shù)的acceptor提交一個(gè)提案（不妨設(shè)編號(hào)為K）
1.b??如果acceptor是第一次收到提案（即acceptedN=null）瞧捌，則記錄acceptedN=K棵里，并承諾不會(huì)接受編號(hào)小于K的提案,返回[K,null].
??? 如果K的值小于acceptedN润文，則拒絕。
??? 如果K的值大于acceptedN:
??????1)如果acceptedN=null殿怜，則記錄acceptedN=K典蝌，接受并返回[K,null]
??????2)如果acceptedN為非空，則記錄acceptedN=K头谜，同樣接受赠法，但是返回[K,acceptedK]
2.第二階段，Accept階段
2.a??proposer如果一段時(shí)間后乔夯，未收到超過一半的acceptor的接受應(yīng)答砖织，則修改K的值，重新進(jìn)入prepare階段
??? proposer如果收到了超過一半的acceptor的應(yīng)答:
??????1)如果返回的是[K,null]末荐，那么Proposer可以選擇任何的V值侧纯，將[K,V]發(fā)送給acceptor（稱為accept請求）.
??????2)如果返回的是[K,acceptedK],那么V=max(acceptedK)],即V的值是收到的應(yīng)答中編號(hào)最大對(duì)應(yīng)的acceptedK， Proposer將[K ,V]發(fā)送給acceptor（稱為accept請求）.
2.b??acceptor收到accept請求后甲脏，比較自己的acceptedN 和 accept請求的K值:
??????1)如果K > acceptedN眶熬，則拒絕
??????2)否則，記錄acceptedN = K 块请，acceptedV = V娜氏，并返回。
3.第三階段墩新，Decide階段
3.a??如果Learner從絕大多數(shù)Acceptor節(jié)點(diǎn)獲得贸弥，則發(fā)送給所有Learner學(xué)習(xí)；否則
3.b??如果Learner沒能獲得絕大多數(shù)Acceptor的海渊，則放棄绵疲；
下面是一個(gè)實(shí)例：
假設(shè)現(xiàn)在有五個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，此時(shí) A 節(jié)點(diǎn)打算提議 X 值臣疑，E 節(jié)點(diǎn)打算提議 Y 值盔憨，其他節(jié)點(diǎn)沒有提議。
假設(shè)現(xiàn)在 A 節(jié)點(diǎn)廣播它的提議（也會(huì)發(fā)送給自己）讯沈，由于網(wǎng)絡(luò)延遲的原因郁岩，只有 A，B缺狠，C 節(jié)點(diǎn)收到了问慎。注意即使 A，E 節(jié)點(diǎn)的提議同時(shí)到達(dá)某個(gè)節(jié)點(diǎn)儒老，它也必然有個(gè)先后處理的順序蝴乔，這里的“同時(shí)”不是真正意義上的“同時(shí)”记餐。
A驮樊，B，C接收提議之后，由于這是第一個(gè)它們接收到的提議囚衔，acceptedProposal 和 acceptedValue 都為空挖腰。
由于 A 節(jié)點(diǎn)已經(jīng)收到超半數(shù)的節(jié)點(diǎn)響應(yīng)，且返回的 acceptedValue 都為空练湿，也就是說它可以用 X 作為提議的值來發(fā)生 Accept 請求猴仑，A，B肥哎，C接收到請求之后辽俗，將 acceptedValue 更新為 X。
A篡诽，B崖飘，C 會(huì)發(fā)生 minProposal 給 A，A 檢查發(fā)現(xiàn)沒有大于 1 的 minProposal 出現(xiàn)杈女，此時(shí) X 已經(jīng)被選中朱浴。等等，我們是不是忘了D达椰，E節(jié)點(diǎn)翰蠢？它們的 acceptedValue 并不是 X，系統(tǒng)還處于不一致狀態(tài)啰劲。至此梁沧，Paxos 過程還沒有結(jié)束，
此時(shí) E 節(jié)點(diǎn)選擇 Proposal ID 為 2 發(fā)送 Prepare 請求蝇裤，結(jié)果就和上面不一樣了趁尼，因?yàn)?C 節(jié)點(diǎn)已經(jīng)接受了 A 節(jié)點(diǎn)的提議，它不會(huì)三心二意猖辫，所以就告訴 E 節(jié)點(diǎn)它的選擇酥泞，E 節(jié)點(diǎn)也很紳士，既然 C 選擇了 A 的提議啃憎，那我也選它吧芝囤。于是，E 發(fā)起 Accept 請求辛萍，使用 X 作為提議值悯姊，至此，整個(gè)分布式系統(tǒng)達(dá)成了一致贩毕，大家都選擇了 X悯许。
