Paxos算法
標簽（空格分隔）： Paxos
轉(zhuǎn)載自: http://www.cnblogs.com/endsock/p/3480093.html
?簡介
Paxos算法是一種基于消息傳遞且具有高度容錯特性的一致性算法，其需要解決的問題就是如何在一個可能發(fā)生異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對某個數(shù)據(jù)的值達成一致，并且保證不論發(fā)生以上任何異常，都不會破壞整個系統(tǒng)的一致性。
?算法描述
在paxos算法中，分為4種角色：
? ? - Proposer ：提議者?
? ? - Acceptor：決策者
? ? - Client：產(chǎn)生議題者
? ? - Learner：最終決策學習者
上面4種角色中，提議者和決策者是很重要的，其他的2個角色在整個算法中應該算做打醬油的，Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。這里上面出現(xiàn)了個新名詞：最終決策?，F(xiàn)在來系統(tǒng)的介紹一下paxos算法中所有的行為：
- Proposer提出議題
- Acceptor初步接受 或者 Acceptor初步不接受
- 如果上一步Acceptor初步接受則Proposer再次向Acceptor確認是否最終接受
- Acceptor 最終接受 或者Acceptor 最終不接受
上面Learner最終學習的目標是Acceptor們最終接受了什么議題？注意，這里是向所有Acceptor學習，如果有多數(shù)派個Acceptor最終接受了某提議，那就得到了最終的結(jié)果，算法的目的就達到了。畫一幅圖來更加直觀：
為什么需要3個Acceptor？因為Acceptor必須是最少大于等于3個，并且必須是奇數(shù)個，因為要形成多數(shù)派嘛，如果是偶數(shù)個，比如4個，2個接受2個不接受，各執(zhí)己見，沒法搞下去了。
為什么是3個Proposer？ 其實無所謂是多少個了，1~n 都可以的；如果是1個proposer，毫無競爭壓力，很順利的完成2階段提交，Acceptor們最終批準了事。
故事舉例
????????有2個Client(老板，老板之間是競爭關系)和3個Acceptor(政府官員)：
????????現(xiàn)在需要對一項議題來進行paxos過程，議題是“A項目我要中標！”，這里的“我”指每個帶著他的秘書Proposer的Client老板。
????????Proposer當然聽老板的話了，趕緊帶著議題和現(xiàn)金去找Acceptor政府官員。
????????作為政府官員，當然想誰給的錢多就把項目給誰。
????????Proposer-1小姐帶著現(xiàn)金同時找到了Acceptor-1~Acceptor-3官員，1與2號官員分別收取了10比特幣，找到第3號官員時，沒想到遭到了3號官員的鄙視，3號官員告訴她，Proposer-2給了11比特幣。不過沒關系，Proposer-1已經(jīng)得到了1,2兩個官員的認可，形成了多數(shù)派(如果沒有形成多數(shù)派，Proposer-1會去銀行提款在來找官員們給每人20比特幣，這個過程一直重復每次+10比特幣，直到多數(shù)派的形成)，滿意的找老板復命去了，但是此時Proposer-2保鏢找到了1,2號官員，分別給了他們11比特幣，1,2號官員的態(tài)度立刻轉(zhuǎn)變，都說Proposer-2的老板懂事，這下子Proposer-2放心了，搞定了3個官員，找老板復命去了，當然這個過程是第一階段提交，只是官員們初步接受賄賂而已。故事中的比特幣是編號，議題是value。
????????這個過程保證了在某一時刻，某一個proposer的議題會形成一個多數(shù)派進行初步支持；
? ??????現(xiàn)在進入第二階段提交，現(xiàn)在proposer-1小姐使用分身術(shù)(多線程并發(fā))分了3個自己分別去找3位官員，最先找到了1號官員簽合同，遭到了1號官員的鄙視，1號官員告訴他proposer-2先生給了他11比特幣，因為上一條規(guī)則的性質(zhì)proposer-1小姐知道proposer-2第一階段在她之后又形成了多數(shù)派(至少有2位官員的贓款被更新了);此時她趕緊去提款準備重新賄賂這3個官員(重新進入第一階段)，每人20比特幣。剛給1號官員20比特幣， 1號官員很高興初步接受了議題，還沒來得及見到2,3號官員的時候
????????這時proposer-2先生也使用分身術(shù)分別找3位官員(注意這里是proposer-2的第二階段)，被第1號官員拒絕了告訴他收到了20比特幣，第2,3號官員順利簽了合同，這時2，3號官員記錄client-2老板用了11比特幣中標，因為形成了多數(shù)派，所以最終接受了Client2老板中標這個議題，對于proposer-2先生已經(jīng)出色的完成了工作；
????????這時proposer-1小姐找到了2號官員，官員告訴她合同已經(jīng)簽了，將合同給她看，proposer-1小姐是一個沒有什么職業(yè)操守的聰明人，覺得跟Client1老板混沒什么前途，所以將自己的議題修改為“Client2老板中標”，并且給了2號官員20比特幣，這樣形成了一個多數(shù)派。順利的再次進入第二階段。由于此時沒有人競爭了，順利的找3位官員簽合同，3位官員看到議題與上次一次的合同是一致的，所以最終接受了，形成了多數(shù)派，proposer-1小姐跳槽到Client2老板的公司去了。
? ??????Paxos過程結(jié)束了，這樣，一致性得到了保證，算法運行到最后所有的proposer都投“client2中標”所有的acceptor都接受這個議題，也就是說在最初的第二階段，議題是先入為主的，誰先占了先機，后面的proposer在第一階段就會學習到這個議題而修改自己本身的議題，因為這樣沒職業(yè)操守，才能讓一致性得到保證，這就是paxos算法的一個過程。原來paxos算法里的角色都是這樣的不靠譜，不過沒關系，結(jié)果靠譜就可以了。該算法就是為了追求結(jié)果的一致性。
